TY - GEN
T1 - Coverage guided systematic concurrency testing
AU - Wang, Chao
AU - Said, Mahmoud
AU - Gupta, Aarti
PY - 2011
Y1 - 2011
N2 - Shared-memory multi-threaded programs are notoriously difficult to test, and because of the often astronomically large number of thread schedules, testing all possible interleavings is practically infeasible. In this paper 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 been 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. These ordering constraints are treated as likely invariants since they are respected by all the tested runs. Second, during the process of systematic testing, we use the learned ordering constraints to guide the selection of interleavings for future test execution. Our experiments on public domain multithreaded C/C++ programs show that, by focusing on only the high-risk interleavings rather than enumerating all possible interleavings, our method can increase the coverage of important concurrency scenarios with a reasonable cost and detect most of the concurrency bugs in practice.
AB - Shared-memory multi-threaded programs are notoriously difficult to test, and because of the often astronomically large number of thread schedules, testing all possible interleavings is practically infeasible. In this paper 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 been 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. These ordering constraints are treated as likely invariants since they are respected by all the tested runs. Second, during the process of systematic testing, we use the learned ordering constraints to guide the selection of interleavings for future test execution. Our experiments on public domain multithreaded C/C++ programs show that, by focusing on only the high-risk interleavings rather than enumerating all possible interleavings, our method can increase the coverage of important concurrency scenarios with a reasonable cost and detect most of the concurrency bugs in practice.
KW - concurrency
KW - coverage
KW - partial order reduction
UR - http://www.scopus.com/inward/record.url?scp=79959860491&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=79959860491&partnerID=8YFLogxK
U2 - 10.1145/1985793.1985824
DO - 10.1145/1985793.1985824
M3 - Conference contribution
AN - SCOPUS:79959860491
SN - 9781450304450
T3 - Proceedings - International Conference on Software Engineering
SP - 221
EP - 230
BT - ICSE 2011 - 33rd International Conference on Software Engineering, Proceedings of the Conference
T2 - 33rd International Conference on Software Engineering, ICSE 2011
Y2 - 21 May 2011 through 28 May 2011
ER -