GAMBIT: Effective Unit Testing for Concurrency Libraries - Coons, Katherine E.; Musuvathi, Madan; Burckhardt, Sebastian (Proceedings of the 15th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming, 2010)
As concurrent programming becomes prevalent, software providers are investing in concurrency libraries to improve programmer productivity. Concurrency libraries improve productivity by hiding error-prone, low-level synchronization from programmers and providing higher-level concurrent abstractions. Testing such libraries is difﬁcult, however, because concurrency failures often manifest only under particular scheduling circumstances. Current best testing practices are often inadequate: heuristic-guided fuzzing is not systematic, systematic schedule enumeration does not ﬁnd bugs quickly, and stress testing is neither systematic nor fast. To address these shortcomings, we propose a prioritized search technique called GAMBIT that combines the speed beneﬁts of heuristic-guided fuzzing with the soundness, progress, and reproducibility guarantees of stateless model checking. GAMBIT combines known techniques such as partial-order reduction and preemption-bounding with a generalized best-ﬁrst search framework that prioritizes schedules likely to expose bugs. We evaluate GAMBIT’s effectiveness on newly released concurrency libraries for Microsoft’s .NET framework. Our experiments show that GAMBIT ﬁnds bugs more quickly than prior stateless model checking techniques without compromising coverage guarantees or reproducibility.