Coverage guided systematic concurrency testing

Chao Wang, Mahmoud Said, Aarti Gupta

Research output: Chapter in Book/Report/Conference proceedingConference contribution

73 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationICSE 2011 - 33rd International Conference on Software Engineering, Proceedings of the Conference
Pages221-230
Number of pages10
DOIs
StatePublished - Jul 7 2011
Externally publishedYes
Event33rd International Conference on Software Engineering, ICSE 2011 - Waikiki, Honolulu, HI, United States
Duration: May 21 2011May 28 2011

Publication series

NameProceedings - International Conference on Software Engineering
ISSN (Print)0270-5257

Other

Other33rd International Conference on Software Engineering, ICSE 2011
CountryUnited States
CityWaikiki, Honolulu, HI
Period5/21/115/28/11

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • concurrency
  • coverage
  • partial order reduction

Fingerprint Dive into the research topics of 'Coverage guided systematic concurrency testing'. Together they form a unique fingerprint.

Cite this