TY - GEN
T1 - A randomized scheduler with probabilistic guarantees of finding bugs
AU - Burckhardt, Sebastian
AU - Kothari, Pravesh
AU - Musuvathi, Madanlal
AU - Nagarakatte, Santosh
PY - 2010
Y1 - 2010
N2 - 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.
AB - 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.
KW - Concurrency
KW - Race conditions
KW - Randomized algorithms
KW - Testing
UR - http://www.scopus.com/inward/record.url?scp=77952272763&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=77952272763&partnerID=8YFLogxK
U2 - 10.1145/1736020.1736040
DO - 10.1145/1736020.1736040
M3 - Conference contribution
AN - SCOPUS:77952272763
SN - 9781605588391
T3 - International Conference on Architectural Support for Programming Languages and Operating Systems - ASPLOS
SP - 167
EP - 178
BT - ASPLOS XV - 15th International Conference on Architectural Support for Programming Languages and Operating Systems
T2 - 15th International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS XV
Y2 - 13 March 2010 through 17 March 2010
ER -