LTL Model Checking for Systems with Unbounded Number of Dynamically Created Threads and Objects

Eran Yahav, Thomas Reps, and Mooly Sagiv

One of the stumbling blocks to applying model checking to a concurrent language such as Java is that a program's data structures (as well as the number of threads) can grow and shrink dynamically, with no fixed upper bound on their size or number. This paper presents a method for verifying LTL properties of programs written in such a language. It uses a powerful abstraction mechanism based on 3-valued logic, and handles dynamic allocation of objects (including thread objects) and references to objects. This allows us to verify many programs that dynamically allocate thread objects, and even programs that create an unbounded number of threads.

(Click here to access the paper: PostScript, PDF.)