Symmetry-Aware Predicate Abstraction for Shared-Variable Concurrent Programs

February 16, 2011
Alastair Donaldson | University of Oxford

Predicate abstraction is a key enabling technology for applying finite-state model checkers to programs written in mainstream languages. It has been used very successfully for debugging sequential system-level C code. Although model checking was originally designed for analyzing concurrent systems, there is little evidence of fruitful applications of predicate abstraction to shared-variable concurrent software. The goal of this paper is to close this gap. We have developed a symmetry-aware predicate abstraction strategy: it takes into account the replicated structure of C programs that consist of many threads executing the same procedure, and generates a Boolean program template whose multi-threaded execution soundly over approximates the concurrent C program. State explosion during model checking parallel instantiations of this template can now be absorbed by exploiting symmetry. We have implemented our method in the SATABS predicate abstraction framework, and demonstrate its superior performance over alternative approaches on a large range of synchronization programs.

Joint work with Alexander Kaiser, Daniel Kroening and Thomas Wahl.

Speaker Details

Alastair Donaldson is a Postdoctoral Research Fellow at the Oxford University Computing Laboratory. His current research interests include formal verification of multicore software, high-level models for parallel programming, and multicore compilation techniques. Before joining Oxford, he obtained a PhD from the University of Glasgow, on symmetry detection and reduction techniques for explicit-state model checking, and then worked in industry at Codeplay Software Ltd., an Edinburgh-based company specializing in compilers and development tools for multicore processors.