A randomized scheduler with probabilistic guarantees of finding bugs
- 5 March 2010
- journal article
- conference paper
- Published by Association for Computing Machinery (ACM) in ACM SIGPLAN Notices
- Vol. 45 (3), 167-178
- https://doi.org/10.1145/1735971.1736040
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.Keywords
This publication has 23 references indexed in Scilit:
- Execution replay of multiprocessor virtual machinesPublished by Association for Computing Machinery (ACM) ,2008
- Learning from mistakesPublished by Association for Computing Machinery (ACM) ,2008
- Effective random testing of concurrent programsPublished by Association for Computing Machinery (ACM) ,2007
- Iterative context bounding for systematic testing of multithreaded programsPublished by Association for Computing Machinery (ACM) ,2007
- GoldilocksPublished by Association for Computing Machinery (ACM) ,2007
- Producing scheduling that causes concurrent programs to failPublished by Association for Computing Machinery (ACM) ,2006
- A serializability violation detector for shared-memory server programsPublished by Association for Computing Machinery (ACM) ,2005
- Framework for testing multi‐threaded Java programsConcurrency and Computation: Practice and Experience, 2003
- Isolating failure-inducing thread schedulesACM SIGSOFT Software Engineering Notes, 2002
- Achieving service rate objectives with decay usage schedulingIEEE Transactions on Software Engineering, 1993