PDL Abstract

Efficient Exploratory Testing of Concurrent Systems

Carnegie Mellon University Parallel Data Lab Technical Report CMU-PDL-11-113. Nov. 2011.

Jiri Simsa, Randy Bryant, Garth A. Gibson, Jason Hickey (Google)

Carnegie Mellon University
Pittsburgh, PA 15213


In our experience, exploratory testing has reached a level of maturity that makes it a practical and often the most cost-effective approach to testing. Notably, previous work has demonstrated that exploratory testing is capable of finding bugs even in well-tested systems [4, 17, 24, 23]. However, the number of bugs found gives little indication of the efficiency of a testing approach. To drive testing efficiency, this paper focuses on techniques for measuring and maximizing the coverage achieved by exploratory testing. In particular, this paper describes the design, implementation, and evaluation of Eta, a framework for exploratory testing of multithreaded components of a large-scale cluster management system at Google. For simple tests (with millions to billions of possible executions), Eta achieves complete coverage one to two orders of magnitude faster than random testing. For complex tests, Eta adopts a state space reduction technique to avoid the need to explore over 85% of executions and harnesses parallel processing to explore multiple test executions concurrently, achieving a throughput increase of up to 17.5X.

KEYWORDS: Exploratory Testing, State Space Exploration, State Space Size Estimation, State Space Reduction, Parallel Processing

FULL TR: pdf