Computer Science Department
School of Computer Science, Carnegie Mellon University
Systematic and Scalable Testing of Concurrent Programs
The challenge this thesis addresses is to speed up the development
of concurrent programs by increasing the efficiency with which concurrent
programs can be tested and consequently evolved. The goal of this thesis is to
generate methods and tools that help software engineers increase confidence
in the correct operation of their programs. To achieve this goal, this thesis
advocates testing of concurrent software using a systematic approach capable
of enumerating possible executions of a concurrent program.
The practicality of the systematic testing approach is demonstrated by presenting a novel software infrastructure that repeatedly executes a program test, controlling the order in which concurrent events happen so that different behaviors can be explored across different test executions. By doing so, systematic testing circumvents the limitations of traditional ad-hoc testing, which relies on chance to discover concurrency errors.
However, the idea of systematic testing alone does not quite solve the problem of concurrent software testing. The combinatorial nature of the number of ways in which concurrent events of a program can execute causes an explosion of the number of possible interleavings of these events, a problem referred to as state space explosion.
To address the state space explosion problem, this thesis studies tech- niques for quantifying the extent of state space explosion and explores several directions for mitigating state space explosion: parallel state space exploration, restricted runtime scheduling, and abstraction reduction. In the course of its research exploration, this thesis pushes the practical limits of systematic testing by orders of magnitude, scaling systematic testing to real-world programs of unprecedented complexity.