A Randomized Scheduler with Probabilistic Guarantees of Finding Bugs

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.