Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Thread Quantification for Concurrent Shape Analysis

Josh Berdine, Tal Lev-Ami, Roman Manevich, Ganesan Ramalingam, and Mooly Sagiv

Abstract

We present new algorithms for automatically verifying properties of programs with an unbounded number of threads. Our algorithms are based on a new abstract domain whose elements represent thread-quantified invariants: i.e., invariants satisfied by all threads.We exploit existing abstractions to represent the invariants. Thus, our technique lifts existing abstractions by wrapping universal quantification around elements of the base abstract domain.

Such abstractions are effective because they are thread-modular: e.g., they can capture correlations between the local variables of the same thread as well as correlations between the local variables of a thread and global variables, but forget correlations between the states of distinct threads. (The exact nature of the abstraction, of course, depends on the base abstraction lifted in this style.

We present techniques for computing sound transformers for the new abstraction by using transformers of the base abstract domain. We illustrate our technique in this paper by instantiating it to the Boolean Heap abstraction, producing a Quantified Boolean Heap abstraction. We have implemented an instantiation of our technique with Canonical Abstraction as the base abstraction and used it to successfully verify linearizability of data-structures in the presence of an unbounded number of threads.

Details

Publication typeTechReport
URLhttp://www.cs.tau.ac.il/~tla/2008/papers/TR-2008-01TQ.pdf
NumberTR-2008-01TQ
InstitutionTel Aviv University, School of Computer Science
> Publications > Thread Quantification for Concurrent Shape Analysis