Dynamic Race Detection with O(1) Samples
summary
Claims a randomized, one-sided property tester that samples O(1) samples (constant many events when thread and lock counts are fixed) and runs FastTrack on uniformly chosen subtraces to detect HB races with no false positives. The implemented tool RPT uses parameters epsilon=0.01 delta=0.1, is proven to detect a race with high probability if the trace is epsilon-far in Hamming distance, was evaluated on 149 benchmarks (50 runs each), shows constant analysis time and much lower runtime than full FastTrack, but misses extremely sparse races (e.g., billions of events with only a few races).
AI-written summary · about
chapters (13)
- 0:00Intro
- 0:52Dynamic Analysis for Detecting Data Races
- 1:30Happens-Before Races
- 2:27HB Race Detection
- 4:10Soundness for Sampling Race Detection
- 4:44A General Framework of Sampling
- 7:51A One Sided Property Tester
- 10:54RPT, A Property Tester For Race Detection
- 12:29Experiment setup
- 14:18Running Time
- 14:50Constant Analysis Time
- 15:55Detecting One Race
- 17:31Conclusion
related talks
22mData race detection
21mWhat happens-after the first race? enhancing the predictive power of dynamic race detection
01h 04mDebugging data races
19mEfficient Timestamping for Sampling-Based Race Detection
07mRace Conditions in Details
19mRuntime Detection of Data Races in OCaml with ThreadSanitizer
17mSSRD: Shapes and Summaries for Race Detection in Concurrent Data Structures
40mProperty-testing async code in Rust to build reliable distributed systems