A Randomized Scheduler with Probabilistic Guarantees of Finding Bugs

sebastian burckhardt, Pravesh Kothari, Madanlal Musuvathi, and Santosh Nagarakatte

Abstract

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/nkd-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.

Details

Publication typeTechReport
NumberMSR-TR-2010-3
> Publications > A Randomized Scheduler with Probabilistic Guarantees of Finding Bugs