A Randomized Scheduler with Probabilistic Guarantees of Finding Bugs

作者：Burckhardt Sebastian; Kothari Pravesh; Musuvathi Madanlal; Nagarakatte Santosh

来源：ACM Sigplan Notices, 2010, 45(3): 167-178.

DOI：10.1145/1735971.1736040

• Algorithms
• Reliability
• Verification
• Concurrency
• Race Conditions
• Randomized Algorithms
• Testing

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.

• 出版日期2010-3