Many designs intermingle large memories with wide data paths and nontrivial control. Verifying such systems is challenging, and users often get little traction when applying model checking to decide full or partial end-to-end correctness of such designs. Interestingly, a subclass of these systems can be proven correct by reasoning only about a small number of the memory entries at a limited number of time points. In this paper, we leverage this fact to abstract certain memories in a sound way, and we demonstrate how our memory abstraction coupled with an abstraction refinement algorithm can be used to prove correctness properties for three challenging designs from industry and academia. Key features of our approach are that we operate on standard safety property verification problems, that we proceed completely automatically without any need for abstraction hints, that we can use any bit-level model checker as a back-end decision procedure, and that our algorithms fit seamlessly into a standard transformational verification paradigm.

A standard approach to improving circuit performance is to use an N-phase design style where combinational logic is interspersed freely between level sensitive latches controlled by separate clocks. Unfortunately, the use of an N-phase design style will increase the number of state variables by a factor of N, making formal verification many orders of magnitude harder. Previous approaches to solving this problem restrict the kind of designs that can be handled severely and construct an abstracted netlist with fewer state variables by a syntactic analysis that requires the user to identify clocks. We extend the current state of the art by introducing a phase abstraction algorithm that (1) poses no restrictions on the design style that can be used, that (2) avoids an error prone syntactic analysis, that (3) requires no input from users, and that (4) can be integrated into any model checker without requiring HDL code analysis.

In this paper, we present a method for finding failure traces for safety properties that are out of reach for traditional approaches to counter example generation. We do this by guiding bounded model checking (BMC) with information gathered from counter example guided abstraction refinement. Unlike previously described approaches based on reconstructing abstract counter examples on the concrete machines, we do not limit ourselves to search for failures of the same length as the current abstract counterexample. We also describe a combination of previously known methods for choosing registers to include in the abstraction that we have found works very well together with our technique for finding failures. Our experimental results show that the resulting method can find counter examples that are out of range for both standard BMC and two previously published approaches to abstraction-guided BMC.

The choice of representation for circuits and Boolean formulae in a formal verification tool is important for two reasons. First of all, representation compactness is necessary in order to keep the memory consumption low. This is witnessed by the importance of maximum processable design size for equivalence checkers. Second, many formal verification algorithms are sensitive to redundancies in the design that is processed. To address these concerns, three different auto-compressing representations for Boolean circuit networks and formulas have been suggested in the literature. We attempt to find a blend of features from these alternatives that allows us to remove as much redundancy as possible while not sacrificing runtime. By studying how the network representation size varies when we change parameters, we show that the use of only one operator node is suboptimal, and demonstrate that the most powerful of the proposed reduction rules, two-level minimization, actually can be harmful. We correct the bad behavior of two-level optimization by devising a simple linear simplification algorithm that can remove tens of thousands of nodes on examples where all obvious redundancies already have been removed. The combination of our compactor with the simplest representation outperforms all of the alternatives we have studied, with a theoretical runtime bound that is at least as good as the three studied representations.

Design automation problems can often be encoded in propositional logic, and solved by applying propositional logic proof methods. Unfortunately, there exists no single proof method with adequate performance for all problems of interest. It is, therefore, critical to be able to combine different approaches, and to quickly be able to test how different compositions affect overall performance. In this paper, we present a proof engine framework where individual methods are viewed as strategies-functions between different proof states. By defining our proof engine in such a way that we can compose strategies to form new, more powerful, strategies we achieve synergistic effects between the individual methods. Unlike previous approaches, our framework is flexible enough to allow users to quickly come up with specially tailored composite analyses for problems from any of the different subdomains of design automation. We show how several known analyses for solving design automation problems encoded in propositional logic can be integrated as base strategies in our framework. As a proof-of-concept, and to demonstrate the power inherent in the framework, we also present experimental results that show the performance of two default composite strategies that we have developed using the framework over a period of several years. These strategies are often one to two magnitudes faster when compared with binary decision diagram-based techniques and search-based satisfiability solvers such as ZCHAFF. The introduction of the framework was the key facilitator in the development of these default strategies.

There are many approaches available for solving combinational design automation problems encoded as tautology or satisfiability checks. Unfortunately there exists no single analysis that gives adequate performance for all problems of interest, and it is therefore critical to be able to combine approaches.In this paper, we present a proof engine framework where individual analyses are viewed as strategies---functions between different proof states. By defining our proof engine in such a way that we can compose strategies to form new, more powerful, strategies we achieve synergistic effects between the individual methods. The resulting framework has enabled us to develop a small set of powerful composite default strategies.We describe several strategies and their interplay; one of the strategies, variable instantiation, is new. The strength of our approach is demonstrated with experimental results showing that our default strategies can achieve up to several magnitudes of speed-up compared to BDD-based techniques and search-based satisfiability solvers such as ZChaff.

Lava is a tool to assist circuit designers in specifying, designing, verifying and implementing hardware. It is a collection of Haskell modules. The system design exploits functional programming language features, such as monads and type classes, to provide multiple interpretations of circuit descriptions. These interpretations implement standard circuit analyses such as simulation, formal verification and the generation of code for the production of real circuits.Lava also uses polymorphism and higher order functions to provide more abstract and general descriptions than are possible in traditional hardware description languages. Two Fast Fourier Transform circuit examples illustrate this.