Iulian Neamtiu, Systematic Testing of Concurrent Programs Using CheSS
Concurrent programs are hard to write, hard to understand, and consequently hard to test and debug. The status quo in testing concurrent programs is dismal: in order to test all possible interleavings of a concurrent program, developers fire a large number of threads, and run the test a large number of times, hoping that scheduling will give rise to a "bad" interleaving that exposes a bug. This approach has two problems: insufficient coverage and lack of repeatability.
To address these problems, we have built CheSS, a Checker for Systems Software. CheSS combines systematic exploration with model checking in order to expose concurrency problems. Given a test suite/agent and a binary to be tested (library or executable), CheSS will explore all the possible thread interleavings in the binary program, for the given test suite. On top of systematic exploration, CheSS can do lightweight, on-the-fly model checking to find problems such as races, deadlocks or memory errors. We have run CheSS on a couple of production and upcoming concurrency libraries and have (re)discovered some data races.