A Randomized Scheduler with Probabilistic Guarantees of Finding Bugs

Madanlal Musuvathi, Sebastian Burckhardt, Pravesh Kothari, and Santosh Nagarakatte

Abstract

This paper presents a randomized scheduler for finding concurrency

bugs. Like current stress-testing methods, it repeatedly runs a

given test program with supplied inputs. However, it improves on

stress-testing by finding buggy schedules more effectively and by

quantifying the probability of missing concurrency bugs. Key to its

design is the characterization of the depth of a concurrency 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 concurrency bug of depth d with probability at

least 1/nkd-1. We hypothesize that in practice, many

concurrency 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 typeInproceedings
Published inProceedings of the Fifteenth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS 2010)
PublisherAssociation for Computing Machinery, Inc.

Previous versions

sebastian burckhardt, Pravesh Kothari, Madanlal Musuvathi, and Santosh Nagarakatte. A Randomized Scheduler with Probabilistic Guarantees of Finding Bugs, January 2010.

> Publications > A Randomized Scheduler with Probabilistic Guarantees of Finding Bugs