Open Systems Laboratory at Illinois

Model checking multithreaded programs with asynchronous atomic methods

By Koushik Sen and Mahesh Viswanathan. In CAV, volume 4144 of Lecture Notes in Computer Science, 300–314. Springer, 2006.

Full Text:
Download PDF
Publisher Link:


In order to make multithreaded programming manageable, programmers often follow a design principle where they break the problem into tasks which are then solved asynchronously and concurrently on different threads. This paper investigates the problem of model checking programs that follow this idiom. We present a programming language Spl that encapsulates this design pattern. Spl extends simplified form of sequential Java to which we add the capability of making asynchronous method invocations in addition to the standard synchronous method calls and the ability to execute asynchronous methods in threads atomically and concurrently. Our main result shows that the control state reachability problem for finite Spl programs is decidable. Therefore, such multithreaded programs can be model checked using the counterexample guided abstraction-refinement framework.


    author = "Sen, Koushik and Viswanathan, Mahesh",
    editor = "Ball, Thomas and Jones, Robert B.",
    title = "Model Checking Multithreaded Programs with Asynchronous
             Atomic Methods",
    booktitle = "CAV",
    crossref = "conf/cav/2006",
    ee = "",
    keywords = "formal methods, software engineering",
    pages = "300-314",
    year = "2006",

    editor = "Ball, Thomas and Jones, Robert B.",
    title = "Computer Aided Verification, 18th International
             Conference, CAV 2006, Seattle, WA, USA, August 17-20, 2006,
    isbn = "3-540-37406-X",
    publisher = "Springer",
    series = "Lecture Notes in Computer Science",
    volume = "4144",
    year = "2006",