We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
Finding Atomicity-Violation Bugs through Unserializable Interleaving Testing.
- Authors
Lu, Shan; Park, Soyeon; Zhou, Yuanyuan
- Abstract
Multicore hardware is making concurrent programs pervasive. Unfortunately, concurrent programs are prone to bugs. Among different types of concurrency bugs, atomicity violations are common and important. How to test the interleaving space and expose atomicity-violation bugs is an open problem. This paper makes three contributions. First, it designs and evaluates a hierarchy of four interleaving coverage criteria using 105 real-world concurrency bugs. This study finds a coverage criterion (Unserializable Interleaving Coverage) that balances the complexity and the capability of exposing atomicity-violation bugs well. Second, it studies stress testing to understand why this common practice cannot effectively expose atomicity-violation bugs from the perspective of unserializable interleaving coverage. Third, it designs CTrigger following the unserializable interleaving coverage criterion. CTrigger uses trace analysis to identify feasible unserializable interleavings, and then exercises low-probability interleavings to expose atomicity-violation bugs. We evaluate CTrigger with real-world atomicity-violation bugs from seven applications. CTrigger efficiently exposes these bugs within 1-235 seconds, two to four orders of magnitude faster than stress testing. Without CTrigger, some of these bugs do not manifest even after seven days of stress testing. Furthermore, once a bug is exposed, CTrigger can reliably reproduce it, usually within 5 seconds, for diagnosis.
- Subjects
CODING theory; COMPUTER input-output equipment; COMPUTER systems; COMPLEXITY (Philosophy); SYNCHRONIZATION; DEBUGGING; COMPUTER programming
- Publication
IEEE Transactions on Software Engineering, 2012, Vol 38, Issue 4, p844
- ISSN
0098-5589
- Publication type
Article
- DOI
10.1109/TSE.2011.35