3-Valued Abstraction for (Bounded) Model Checking

Model Checking is the problem of verifying that a given model satisfies a specification, given in a formal specification language. Abstraction is one of the most successful approaches to avoiding the state explosion problem in model checking. It simplifies the model being checked, in order to save memory and time.

3-valued abstraction is a strong type of abstraction that can be used for both verification and refutation. For hardware verification, 3-valued abstraction can be obtained by letting state variables and inputs range over the ternary domain 0,1,X, where X stands for “unknown”. X is used to abstract away parts of the circuit that are irrelevant for the property being checked. For 3-valued abstractions, checking an abstract model may result in 1 or 0, indicating that the checked property holds or fails, respectively, on the original model. Alternatively, model checking may result in X, indicating that it is impossible to determine whether the property holds or fails due to a too coarse abstraction. In the latter case, the abstract model is refined by replacing some of the X’s with the relevant parts of the circuit. The 3-valued abstraction and refinement can be applied either automatically or manually.

In this talk we present an automata theoretic approach to 3-valued abstraction in hardware model checking. We show how our 3-valued framework can be incorporated into SAT based bounded model checking and induction based unbounded model checking.

Our method enables applying formal verification of LTL formulae on very large industrial designs. We developed our method within Intel’s bounded and unbounded model checking framework, implemented on top of a state-of-the-art CNF SAT solver. We used it for checking real life assertions on a large CPU design, and obtained outstanding results.

This is a joint work with Avi Yadgar, Alon Flaisher, and Michael Lifshits.