Verifying Multi-threaded C Programs with SPIN

Anna Zaks and Rajeev Joshi

Abstract:

A key challenge in model checking software is the difficulty of verifying properties of implementation code, as opposed to checking an abstract algorithmic description. We describe a tool for verifying multithreaded C programs that uses the SPIN model checker. Our tool works by compiling a multi-threaded C program into a typed bytecode format, and then using a virtual machine that interprets the bytecode and computes new program states under the direction of SPIN. Our virtual machine is compatible with most of SPIN's search options and optimization flags, such as bitstate hashing and multi-core checking. It provides support for dynamic memory allocation (the malloc and free family of functions), and for the pthread library, which provides primitives often used by multi-threaded C programs. A feature of our approach is that it can check code after compiler optimizations, which can sometimes introduce race conditions. We describe how our tool addresses the state space explosion problem by allowing users to define data abstraction functions and to constrain the number of allowed context switches. We also describe a reduction method that reduces context switches using dynamic knowledge computed on-the-fly, while being sound for both safety and liveness properties. Finally, we present initial experimental results with our tool on some small examples.

Bibtex:

@inproceedings{ZJ2008,
      Author = {Anna Zaks and Rajeev Joshi},
      Title = {Verifying Multi-threaded {C} Programs with {SPIN}},
      Booktitle = {15th International SPIN Workshop on Model Checking of Software (SPIN 2008)},
      Address = {Los Angeles, USA},
      Month = {August},
      Year = 2008
}

Download:

Verifying Multi-threaded C Programs with SPIN (PDF)