Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
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