Coverage Guided Systematic Concurrency Testing

Chao Wang, Mahmoud Said, and Aarti Gupta
NEC Laboratories America, USA; Western Michigan University, USA

Concurrent programs are notoriously difficult to test, and because of the often large number of thread schedules, testing all possible interleavings is practically infeasible. We propose a coverage-guided systematic testing framework where we use dynamically learned ordering constraints over shared object accesses to select only high-risk interleavings for test execution. An interleaving is of high-risk if it has not be covered by the ordering constraints, meaning that it has concurrency scenarios that have not been tested. Our method consists of two components. First, we utilize dynamic information collected from good test runs to learn ordering constraints over the memory-accessing and synchronization statements. Second, during systematic testing, we use the learned ordering constraints to guide the selection of interleavings for future testing. Our experiments show that the new method can increase the coverage of important concurrency scenarios with a reasonable cost and detect most of the concurrency bugs in practice.