Optimal Prediction of Synchronization-Preserving Races
summary
Paper gives a sound and complete algorithm SyncP that predicts synchronization-preserving races and runs in Õ(N) time and space on a trace of length N, with a matching space lower bound of Ω(N / log^2 N). Allowing even one synchronization reversal makes detection NP-complete and W[1]-hard. Implementation inside the Rapid tool compares against SHB, WCP and M2, finds more races than SHB/WCP, misses only two M2-only reports while M2 times out on some inputs, and shows most real races are sync-preserving.
AI-written summary · about
chapters (6)
related talks
19mEfficient Timestamping for Sampling-Based Race Detection
31mRace Conditions - Practical Tools & Techniques for Testing, Preventing, and Debugging C++/C Code
15mSafeRace: Assessing and Addressing WebGPU Memory Safety in the Presence of Data Races
42mUnderstanding Data Races in the Linux Kernel
16mPreventing Data Races in Async Coroutines
34mDetecting Race Conditions on macOS
35mShowTime: CPU Timing Attacks With the Human Eye
28mData Race Detection by Digest-Driven Abstract Interpretation