Maple
Authors:
Open Access
- 19 October 2012
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGPLAN Notices
- Vol. 47 (10) , 485-502
Abstract
Testing multithreaded programs is a hard problem, because it is challenging to expose those rare interleavings that can trigger a concurrency bug. We propose a new thread interleaving coverage-driven testing tool called Maple that seeks to expose untested thread interleavings as much as possible. It memoizes tested interleavings and actively seeks to expose untested interleavings for a given test input to increase interleaving coverage. We discuss several solutions to realize the above goal. First, we discuss a coverage metric based on a set of interleaving idioms. Second, we discuss an online technique to predict untested interleavings that can potentially be exposed for a given test input. Finally, the predicted untested interleavings are exposed by actively controlling the thread schedule while executing for the test input. We discuss our experiences in using the tool to expose several known and unknown bugs in real-world applications such as Apache and MySQL.Keywords
This publication has 46 references indexed in Scilit:
- FastTrackCommunications of the ACM, 2010
- A randomized scheduler with probabilistic guarantees of finding bugs2010
- GAMBIT2010
- VelodromeACM SIGPLAN Notices, 2008
- Applications of synchronization coverage2005
- Dynamic partial-order reduction for model checking software2005
- RacerX2003
- A type and effect system for atomicityACM SIGPLAN Notices, 2003
- Multithreaded Java program test generationIBM Systems Journal, 2002
- Generating representative Web workloads for network and server performance evaluation1998