Verification of Software and Hardware using Quantified Boolean Formulas (QBF)

Abstract.  Many problems in formal verification of digital hardware circuits and other finite-state systems are naturally expressed in the language of quantified boolean formulas (QBF). The first two parts of this thesis proposal present techniques that advance the state-of-the-art in solving such QBF problems, thereby enabling the verification of more complex hardware designs. The third part proposes a new technique for software verification using a solver for QBF with free variables.

Traditionally, QBF solvers have required that their input formulas be transformed into a special form known as prenex CNF. However, although prenex CNF has the benefit of being simple, it is now recognized that transformation to this form can be detrimental to advanced solvers because it obscures features of the input formula that could be useful to the solver. We present two contributions to the development of non-prenex, non-CNF solvers. First, we reformulate clause/cube learning, an important technique in prenex solvers, and we extend it to non-prenex instances. Second, we introduce a propagation technique using ghost literals that exploits the structure of a non-CNF instance in a manner that is symmetric between the universal and existential variables.

The second part of this thesis proposal discusses an approach to QBF using Counterexample-Guided Abstraction Refinement (CEGAR). The approach recursively solves QBF instances with multiple quantifier alternations. Experimental results show that the CEGAR-based solver outperforms existing types of solvers on many publicly-available benchmark families. In addition, we present a method of combining the CEGAR technique with DPLL-based solvers and show that it improves the DPLL solver in many instances.

The third part of this thesis proposal presents a method for automatically inferring universally quantified loop invariants for programs with dynamically allocated heap data structures. Our technique works by computing an overapproximation of the set of reachable states via a fixed-point procedure. We target a small dynamically typed intermediate language. Sets of states are described by formulas in a fragment of first-order logic augmented with transitive closure; the fragment includes equality, uninterpreted functions, and total order. We introduce an abstraction function that summarizes the heap memory, returning a formula of bounded size. Summarization of memory locations is based, in part, on how they can be reached from the program variables. The inferred invariants can be used to verify the absence of failed assertions and other run-time errors.