Dynamic Race Detection with O(1) Samples CCS: Software and its engineering Software testing and debugging
Mosaad Al Thokair*, Minjian Zhang* †, Umang Mathur, Mahesh Viswanathan · 2025
Read Dynamic Race Detection with O(1) Samples CCS: Software and its engineering Software testing and debugging by Mosaad Al Thokair*, Minjian Zhang* †, Umang Mathur, Mahesh Viswanathan (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-20127.txt.
Introduction
Mosaad Al Thokair, Minjian Zhang, Umang Mathur, and Mahesh Viswanathan present a fast sampled method to find data races in programs, in a 2025 paper. A data race occurs when two parts of a program touch the same data in a clashing order. Standard dynamic checks are sound but costly, since they update a clock record at every event, which limits them to in-house testing.
Their detector samples only a constant number of events from a run trace, no matter how long the trace is. That makes it the first race detector that runs in less than linear time, the authors say. It never reports a false race. On traces that sit far from any race-free trace, it finds a race with high probability. Tests against leading exact and sampled detectors showed far lower running time, with races still found often.
Catalog record
| CREATOR | Mosaad Al Thokair*, Minjian Zhang* †, Umang Mathur, Mahesh Viswanathan |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 93 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-20127
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Dynamic Race Detection with O(1) Samples CCS: Software and its engineering Software testing and debugging Mosaad Al Thokair*, Minjian Zhang* †, Umang Mathur, Mahesh Viswanathan Abstract . Happens before-based dynamic analysis is the go-to technique for detecting data races in large scale software projects due to the absence of false positive reports. However, such analyses are expensive since they employ expensive vector clock updates at each event, rendering them usable only for in-house testing. In this paper, we present a sampling-based, randomized race detector that processes only constantly many events of the input trace even in the worst case. This is the first sub-linear time (i.e., running in o ( n ) o(n) time where n n is the length of the trace) dynamic race detection algorithm; previous sampling based approaches like Pacer run in linear time (i.e., O ( n ) O(n) ). Our algorithm is a property tester for HB -race detection — it is sound in that it never reports any false positive, and on traces that are far, with respect to hamming distance, from any race-free trace, the algorithm detects an HB -race with high probability. Our experimental evaluation of the algorithm and its comparison with state-of-the-art deterministic and sampling based race detectors shows that the algorithm does indeed have significantly low running time, and detects races quite often. 1 1 footnotetext: These authors contributed equally to this work. 2 2 footnotetext: Corresponding author: [email protected] 1. Introduction A concurrent program is said to have a data race (or simply a race) if it has an execution in which a pair of threads access a shared memory location consecutively and in which one of the accesses writes a value to the shared memory location. Data races are one of the most common source of bugs in concurrent programs and are the cause of more serious problems like data corruption ( Boehm 2011 ; Kasikci et al. 2013 ; Narayanasamy et al. 2007 ) . Absence of data races is often a pre-requisite for the semantics of programs to be well defined ( Boehm and Adve 2008 ; Zhivich and Cunningham 2009 ) and for compiler optimizations to be sound ( Ševčík and Aspinall 2008 ; Ševčík 2011 ) . Sound dynamic data race prediction is a popular approach to identify such bugs in concurrent programs. Here one observes a single execution of the program, and the goal of the analysis is to see if the execution provides evidence for the presence of a data race in the program. This requires reasoning about alternate re-orderings of the events of the observed execution to determine if an execution with a data race is possible. The simplest and most commonly used dynamic data race detection technique is based on Lamport’s happens-before ( HB ) partial order ( Lamport 1978 ) . The idea is to (implicitly) compute the HB partial order on the events of the observed execution and check if there are a pair of conflicting accesses to a shared memory location that are unordered by HB . Happens before based data race detection is known to be sound — the presence of HB unordered memory accesses is proof that the program has a data race. Early vector clock based algorithms ( Mattern 1988 ; Fidge 1991 ) for happens before race detection have been improved over the years to the extent that it is the go-to data race detection in practice ( Serebryany and Iskhodzhanov 2009 ; Serebryany et al. 2011 ) . However, the analysis has high runtime costs ( Marino et al. 2009 ; Bond et al. 2010 ; Biswas et al. 2017 ) due to expensive metadata updates at each event, despite optimizations introduced ( Flanagan and Freund 2009 ; Pozniansky and Schuster 2003 ) . This makes dynamic race detection suitable only for in-house testing, and makes an otherwise lucrative premise of data races exceptions ( Elmas et al. 2007 ; Adve 2010 ) rather impractical. One approach that attempts to reduce the analysis cost in HB race detection uses sampling ( Bond et al. 2010 ) . The informal idea behind this approach is to sample some events of the observed trace, and analyze only the sampled subset of events to determine if the program has data races, with the hope being that the sampled subset will be small compared to the whole trace and that often it will be sufficient to find a race. Though the algorithm presented in ( Bond et al. 2010 ) ( Pacer ) is experimentally shown to run faster than known deterministic race detection algorithms, its expected running time is linear and in the worst case it can be shown to be no better than a deterministic algorithm — there are examples on which, with non-zero probability, Pacer will analyze all the events in the trace. The motivation behind this work is to explore the possibility of a sound race detection algorithm that analyzes, even in the worst case, a sub-linear number of events in an execution (i.e., “little o ” of the length of the trace), but nonetheless has provable mathematical guarantees of precision. The hope is that such an algorithm will help scale sound dynamic race detection beyond in-house testing. To achieve our goal, we investigate the design of a property tester ( Goldreich 2017 ) for HB race detection. A (one-sided) (\epsilon,\delta) -property tester for a decision problem L is an algorithm A that meets the following obligation: on an input x\in L , A answers “yes” with probability 1 , while on an input that is “ \epsilon -far” from any input in L , A answers “no” with probability at least 1-\delta . Notice that the definition of a property tester is based on a distance metric on input strings. The standard notion of distance used in property testing is hamming distance. Therefore, rephrasing and specializing to HB race detection, we have the following. A property tester for HB race detection is an algorithm A such that on any HB race-free execution \sigma , A answers “yes”, and on any execution \sigma in which at least \epsilon fraction of the events must be modified to obtain a race-free execution, A answers “no” with probability at least 1-\delta . Any sound and complete algorithm for HB race detection is, by definition, a property tester for race detection since it distinguishes between race-free and racy executions. However, a property tester has weaker obligations and solves a decision problem approximately — on executions \sigma that have an HB race but at the same time are very close to a race-free execution, a property tester has no obligation to correctly classify them as having an HB race. This flexibility has enabled computer scientists to design extremely fast, but nonetheless useful, algorithms for a variety of decision problems ( Goldreich 2017 ) and has led to sub-linear algorithm design being a vibrant field of study for the past 25 years. In this paper we present a (\epsilon,\delta) -property tester RPT ( R ace P roperty T ester) for HB-race detection that provably examines only constantly many events in the observed program execution. More precisely, let