Model Checking Boolean Programs

A successful approach to push the boundaries of Modelchecking is predicate abstraction. With this method, an abstraction of a program in a high-level programming language is constructed using predicates and represented as a Boolean program. It is analyzed by a dedicated checker to determine if an error state is reachable. Boolean program verification remains, despite the reduced state space, the bottleneck within the automated abstraction-refinement loop. This book introduces techniques for efficient reachability analysis of sequential and concurrent Boolean programs. We improve on known summarization algorithms for sequential Boolean programs and propose over-approximations of procedure calls. For non-recursive concurrent Boolean programs, we introduce a transformation to a representation , which exploits the symmetry inherent in replicated programs. This allows exact verification of an unbounded number of threads.