Testing concurrent software: challenges and tools

Testing concurrent software is hard due to its non-deterministic behavior. Concurrency bugs triggering the failure of a test are difficult to reproduce. When debugging, the failing behavior might disappear altogether, a so-called Heisenbug. The cause of these concurrency problems is non-deterministic thread interleaving, introducing data races and race conditions. In literature, three categories of techniques have been described to effectively test concurrent software. First, random testing or fuzzing approaches have been implemented in a tool such as Contest. These techniques force threads to interleave at random intervals. As fuzzing strategies encounter a faulty set of thread interleaving by chance these might increase the chances of finding a bug. However they provide no guarantee regarding the detection of race conditions. Next, model checking tools, such as Goldilocks, provide a model for the concurrent code. On the one hand the lockset model determines that shared data must be properly guarded by a locking primitive, such as a mutex, semaphore, etc. On the other hand the happens-before model explores the causal relationship between events. Both models suffer from false-positive results when data is shared, yet by design a race condition can never occur. Finally, a technique called state space exploration employs tests to explore the set of possible states of a program, as implemented by Chess, Java Pathfinder and Basset. However, this strategy suffers from the state space explosion problem which inevitably occurs when threads can be interleaved at any moment. This problem is partially solved by limiting the number of interleaving threads. Despite their limitations these techniques are adopted in tools, which help the tester to identify concurrency issues.status: publishe