Decision procedures for verification of computer systems
The rigorous mathematical analysis and verification of safety-critical computer systems ultimately relies on the availability of robust, general, and fast decision procedures for logical theories modelling simple data types (such as integer, reals, and bit-vectors), functional data structures (such as lists, arrays, sets, multisets, and graphs), and pointer-based data structures (such as linked lists and binary search trees).
In this talk we describe how decision procedures are used in the verification of safety-critical computer systems. Furthermore, we present a general algorithm that can decide the satisfiability of every quantifier-free verification condition spanning over simple data types, functional data structures, and pointer-based data structures. This algorithm is based on the eager approach to decision procedures: the verification condition to be checked for satisfiability is converted into an equisatisfiable propositional formula, which can be sent to a state-of-the-art BDD package or SAT solver.