Open Systems Laboratory at Illinois

A race-detection and flipping algorithm for automated testing of multi-threaded programs

By Koushik Sen and Gul Agha. In Haifa Verification Conference, volume 4383 of Lecture Notes in Computer Science, 166–182. Springer, 2006.

Publisher Link:
http://dx.doi.org/10.1007/978-3-540-70889-6_13

Abstract

Testing concurrent programs that accept data inputs is notoriously hard because, besides the large number of possible data inputs, nondeterminism results in an exponentially large number of interleavings of concurrent events. In order to efficiently test shared-memory multi-threaded programs, we develop an algorithm based on race-detection and flipping and illustrate how it can be combined with concolic execution (a simultaneous symbolic and concrete execution method) to test multi-threaded programs with data inputs. The goal of our algorithm is to minimize redundant executions while ensuring that all reachable statements in a program are executed. To achieve this, our algorithm explores all distinct causal structures of a multi-threaded program (i.e., the partial order among events generated during an execution). Because our algorithm is based on race-detection, it enables us to report potential data races and deadlocks. We have implemented our algorithm in a tool called jCUTE. We describe the results of applying jCUTE to real-world multi-threaded Java applications and libraries. In particular, we discovered several undocumented potential concurrency-related bugs in the widely used Java collection framework distributed with the Sun Microsystems’ JDK 1.4.

BibTeX

@inproceedings{conf/hvc/SenA06,
    author = "Sen, Koushik and Agha, Gul",
    editor = "Bin, Eyal and Ziv, Avi and Ur, Shmuel",
    title = "A Race-Detection and Flipping Algorithm for Automated
             Testing of Multi-threaded Programs",
    booktitle = "Haifa Verification Conference",
    crossref = "conf/hvc/2006",
    ee = "http://dx.doi.org/10.1007/978-3-540-70889-6_13",
    pages = "166-182",
    year = "2006",
}

@proceedings{conf/hvc/2006,
    editor = "Bin, Eyal and Ziv, Avi and Ur, Shmuel",
    title = "Hardware and Software, Verification and Testing, Second
             International Haifa Verification Conference, HVC 2006, Haifa,
             Israel, October 23-26, 2006. Revised Selected Papers",
    isbn = "978-3-540-70888-9",
    publisher = "Springer",
    series = "Lecture Notes in Computer Science",
    volume = "4383",
    year = "2007",
}