Abstract Interactive theorem provers (ITPs) exploit the collaboration between humans and computers, enabling proof of complex theorems. Further, ITPs allow extraction of provably correct implementations from proofs. However, often, the extracted code interface with external libraries containing real-life complexities—proprietary library calls, remote/cloud APIs, complex models like ML models, inline assembly, highly non-linear arithmetic, vector instructions etc. We refer to such functions/operations as closed-box components . For such components, the user has to provide appropriate assumed lemmas to model the behavior of these functions. However, we found instances where these assumed lemmas are inconsistent with the actual semantics of these closed-box components. Hence, even correct-by-construction code extracted from an ITP may still behave incorrectly when interfaced with such closed-box components . To this end, we propose StarFuzz , that allows the $$\text {F}^\star $$ F ⋆ interactive theorem prover to provide better end-to-end assurance on the application— even when interfaced with the closed-box components . Under the hood, StarFuzz rides on Sādhak , an SMT solver that combines fuzz testing to allow satisfiability checking over closed-box components. On the $$\text {F}^\star $$ F ⋆ library that includes external implementations in OCaml, StarFuzz discovered four bugs—one bug that revealed an error on the assumed lemmas for a closed-box function, and three bugs in the external implementations of these components.

Program analysis, verification and testing are important topics in programming languages and software engineering. They aim to produce engineers who are not only capable of empirically evaluating but, also formally reasoning on the correctness of software systems. We propose a specialized framework, Chiron, designed to teach graduate-level courses on these topics. Chiron has a small code base for easy understanding, uses a unified intermediate representation across all its analysis modules, maintains a modular architecture for plugging in new algorithms and uses a “fun” programming language to provide a gamified experience. Currently, it packages a dataflow analysis engine for driving compiler optimizations, an abstract interpretation engine for verification, a symbolic execution engine, a fuzzer and an evolutionary test generator for program testing, and a spectrum based statistical bug localization module. Within Chiron, program analysis tasks are posed in an unconventional setting (as adventures of a turtle) to provide a gamified experience; the accompanying animations (showing the movements of the turtle) allow the student to understand the underlying concepts better, and the detailed logs allow the teaching assistants in their grading activities. Chiron has been used in two offerings of a graduate level course on program analysis, verification and testing. In response to our survey questionnaire, all the students unanimously held the opinion that Chiron was extremely helpful in aiding their learning, and recommended its use in similar courses.

This paper addresses the problem of creating abstract transformers automatically. The method we present automates the construction of static analyzers in a fashion similar to the way yacc automates the construction of parsers. Our method treats the problem as a program-synthesis problem. The user provides specifications of (i) the concrete semantics of a given operation op , (ii) the abstract domain A to be used by the analyzer, and (iii) the semantics of a domain-specific language L in which the abstract transformer is to be expressed. As output, our method creates an abstract transformer for op in abstract domain A , expressed in L (an “ L -transformer for op over A ”). Moreover, the abstract transformer obtained is a most-precise L -transformer for op over A ; that is, there is no other L -transformer for op over A that is strictly more precise. We implemented our method in a tool called AMURTH. We used AMURTH to create sets of replacement abstract transformers for those used in two existing analyzers, and obtained essentially identical performance. However, when we compared the existing transformers with the transformers obtained using AMURTH, we discovered that four of the existing transformers were unsound, which demonstrates the risk of using manually created transformers.

Programming languages and software engineering tools routinely encounter components that are difficult to reason on via formal techniques or whose formal semantics are not even available—third-party libraries, inline assembly code, SIMD instructions, system calls, calls to machine learning models, etc. However, often access to these components is available as input-output oracles—interfaces are available to query these components on certain inputs to receive the respective outputs. We refer to such functions as closed-box functions . Regular SMT solvers are unable to handle such closed-box functions. We propose Sādhak, a solver for SMT theories modulo closed-box functions. Our core idea is to use a synergistic combination of a fuzzer to reason on closed-box functions and an SMT engine to solve the constraints pertaining to the SMT theories. The fuzz and the SMT engines attempt to converge to a model by exchanging a rich set of interface constraints that are relevant and interpretable by them. Our implementation, Sādhak, demonstrates a significant advantage over the only other solver that is capable of handling such closed-box constraints: Sādhak solves 36.45% more benchmarks than the best-performing mode of this state-of-the-art solver and has 5.72x better PAR-2 score; on the benchmarks that are solved by both tools, Sādhak is (on an average) 14.62x faster.

Automated validation of security properties in modern systems-on-chip (SoC) designs is challenging due to three reasons: (i) specification of security in the presence of adversarial behavior, (ii) co-validation of hardware (HW) and firmware (FW) as security bugs may span the HW/FW interface, and (iii) scaling verification to the analysis of large systems-on-chip designs.

Many important specifications of hardware and software systems, such as secure information flow and determinism are expressible only as hyperproperties. In contrast to the well-studied class of trace properties, which specify sets of valid runs (aka traces) of a system, hyperproperties can specify relations that must hold between the traces of a system. While hyperproperties have many applications, primarily in security verification, coming up with hyperproperties for SoC validation is challenging. In this paper, we work toward addressing this challenge by introducing a framework for mining hyperproper-ties from execution traces of SoC designs. We introduce novel algorithms based on coverage-guided fuzzing that enable the generation of good input traces for the hyperproperty miner. We also present novel optimistic and pessimistic semantics for Hyper Linear Temporal Logic (HyperLTL) that enable principled evaluation of HyperLTL formulas over finite traces. Finally, we propose algorithms for scalably evaluating non-trivial satisfaction of candidate hyperproperties on sets of traces. Experiments on a small but realistic SoC design show the framework is effective in identifying useful hyperproperties.

Verification and validation of system-level security primitives is a pressing challenge in systems-on-chip (SoC) design and verification. This is a difficult problem to tackle for three reasons. First, no general frameworks exist that can enable adversary modeling for SoC platforms. Second, succinct specification of the desired security properties is not possible with current property specification languages. Finally, verification of a security specification is more challenging than functional verification. In this paper, we introduce a formal framework that enables general adversary modeling for SoC platforms and a security property specification language for this framework. We present formal semantics for the framework and illustrate its utility through a case study of an authenticated firmware load protocol.

An important primitive in ensuring security of modern systems-on-chip designs are protocols for authenticated firmware load. These loaders read a firmware binary image from an untrusted input device, authenticate the image using cryptography and load the image into memory for execution if authentication succeeds. While these protocols are an essential part of the hardware root of trust in almost all modern computing devices, verification techniques for reasoning about end-to-end security of these protocols do not exist.This paper takes a step toward addressing this gap by introducing a system model, adversary model and end-to-end security property that enable reasoning about the security of authenticated load protocols. We then present a decomposition of the security hyperproperty into two simpler 2-safety properties that enables more scalable verification. Experiments on a protocol model demonstrate viability of the methodology.