A Randomized Scheduler with Probabilistic Guarantees of Finding Bugs

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/{nk^{d-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.

PDF file
PowerPoint presentation

In  Proceedings of the Fifteenth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS 2010)

Publisher  Association for Computing Machinery, Inc.
Copyright © 2007 by the Association for Computing Machinery, Inc. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from Publications Dept, ACM Inc., fax +1 (212) 869-0481, or permissions@acm.org. The definitive version of this paper can be found at ACM’s Digital Library --http://www.acm.org/dl/.



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