This paper presents a randomized scheduler for finding concurrency

bugs. The scheduler improves upon current stress-testing methods by

finding bugs more effectively, and by permitting us to quantify the

probability of missing bugs. Key to its design is the characterization

of the depth of a bug as the minimum number of scheduling constraints

required to find it. In a single run of a program with $n$ threads and

$k$ steps, our scheduler detects a bug of depth $d$ with probability

at least $1/{nk^{d-1}}$. We hypothesize that in practice, many bugs

(including well-known types such as ordering errors, atomicity

violations, and deadlocks) have small bug-depths, and we confirm the

efficiency of our schedule randomization by detecting previously

unknown and known concurrency bugs in several production-scale

concurrent programs.

PDF file

Details