A randomized scheduler with probabilistic guarantees of finding bugs

Sebastian Burckhardt, Pravesh Kothari, Madanlal Musuvathi, Santosh Nagarakatte

Research output: Chapter in Book/Report/Conference proceedingConference contribution

123 Scopus citations

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

Original languageEnglish (US)
Title of host publicationASPLOS XV - 15th International Conference on Architectural Support for Programming Languages and Operating Systems
Pages167-178
Number of pages12
DOIs
StatePublished - May 19 2010
Event15th International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS XV - Pittsburgh, PA, United States
Duration: Mar 13 2010Mar 17 2010

Publication series

NameInternational Conference on Architectural Support for Programming Languages and Operating Systems - ASPLOS

Other

Other15th International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS XV
CountryUnited States
CityPittsburgh, PA
Period3/13/103/17/10

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems
  • Hardware and Architecture

Keywords

  • Concurrency
  • Race conditions
  • Randomized algorithms
  • Testing

Fingerprint Dive into the research topics of 'A randomized scheduler with probabilistic guarantees of finding bugs'. Together they form a unique fingerprint.

Cite this