Data Race Satisfiability on Array Elements
Junhyung Shim, Quazi Ishtiaque Mahmud, Ali Jannesari · 2025
Read Data Race Satisfiability on Array Elements by Junhyung Shim, Quazi Ishtiaque Mahmud, Ali Jannesari (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-2503-13864.txt.
Introduction
Junhyung Shim, Quazi Ishtiaque Mahmud, and Ali Jannesari tackle false alarms in race detection for parallel code in this 2025 paper. Data races, where threads clash over shared data, break OpenMP programs in hard-to-see ways. Tools that run the code are slow; tools that scan it cry wolf.
Their focus is races on array elements, where index math decides whether two accesses truly collide. Framing the question as satisfiability lets a solver judge each clash exactly. The approach aims to keep static speed while cutting false positives. Programmers then chase real bugs instead of ghosts. The work serves the many codes that share arrays across threads.
Catalog record
| CREATOR | Junhyung Shim, Quazi Ishtiaque Mahmud, Ali Jannesari |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 46 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-13864
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Data Race Satisfiability on Array Elements Junhyung Shim, Quazi Ishtiaque Mahmud, Ali Jannesari Abstract Detection of data races is one of the most important tasks for verifying the correctness of OpenMP parallel codes. Two main models of analysis tools have been proposed for detecting data races: dynamic analysis and static analysis. Dynamic analysis tools such as Intel Inspector, ThreadSanitizer, and Helgrind + can detect data races through the execution of the source code. However, source code execution can be quite time-consuming when analyzing computation-intensive programs. There are also static analysis tools such as LLOV, and OpenRace. These tools statically detect data races using algorithms that often do not require the execution of the source code. Although both detection techniques assist programmers in analyzing the correct behavior of OpenMP programs, they still produce false positives that often defeat the purpose of applying automatic analysis. Therefore, we present DRS-oNE (Data Race Satisfiability on aNy Element), a data race detector that detects data races on array elements by solving for race constraints with the Z3 SMT solver. DRS-oNE is available at https://anonymous.4open.science/r/ompdart-DRS-extension-4152/README.md I INTRODUCTION Recently, Kadosh et al. [ 1 ] reported that about 45 \% of HPCorpus dataset utilize OpenMP libraries. While only 0.16 \% - 0.54 \% of all C/C++ for loops in the dataset were parallelized [ 1 ] , correct parallelization of such for loops is still necessary to guarantee consistent computation. One important factor of consistent computation under parallelization is ensuring that the parallel region is data race-free. A data race is said to occur when two or more threads try to access the same memory location simultaneously, and at least one access is a write. It is relatively easier to detect data races on variables within a parallelized loop than that of array elements, as one just needs to find at least one read-write or write-write pair of a variable. However, detecting data races on array elements may not be so apparent once the indexing involves integer arithmetic operations. Listing 1 shows an example of the mentioned problem. Once a thread works on i=2 , and simultaneously, another thread works on i=7 , then there is a data race on arr[14]. ⬇ 1 int arr [1000]; 2 #pragma omp parallel for 3 for ( int i = 0; i < 10; i ++){ 4 arr [ i %6 + 6* i ] = arr [2* i ]; 5 } Fig. 1: Data race on an array element Dynamic analysis tools [ 2 , 3 , 4 , 5 ] are effective in detecting such data races, but, dynamic detection may result in a long execution time or may fail to detect data races due to the manifestation of nondeterministic behavior of thread interleavings during the execution of the code. Static analysis tools avoid these issues by statically analyzing the textual representation of the source code. Recent static analysis data race detection tools such as LLOV and OpenRace have been reported to achieve precisions 1 1 1 precision = \frac{TP}{TP+FP} of 0.91 [ 6 ] and 0.89 [ 7 ] , respectively. Since precision indicates the ratio of true positives out all all positive detections (true positives + false positives), there still exists a need to eliminate false positives for the mentioned tools. False positives occur in LLOV mainly due to relying on polyhedral model [ 8 ] to detect data races which require parallel loops to be affine. In the case of non-affine loops, LLOV relies on LLVM’s Alias Analysis (AA) [ 9 ] , but due to AA’s conservative nature, it is possible for LLOV to create false positives. OpenRace [ 7 ] deploys modular, domain-specific analysis techniques to accurately detect data races. Currently, OpenRace consists of five stages: Preprocessing, Pointer Analysis, Function Summarization, Trace Building, and Analysis. However, the authors of OpenRace have stated that OpenRace ignores paths to avoid the path explosion problem. Due to this design choice, false positives occur when there is a data race inside an infeasible path. In this work, we Identify false positives reported by LLOV and OpenRace using a subset of DataRaceBench 1.4.0 [ 10 ] along with a set of seven handwritten test cases to show that the race detection using constraint solving is effective in reducing false positive detections. We, therefore, present DRS-oNE, a static analysis tool that detects data races on array elements. DRS-oNE is control flow aware such that it can avoid false positives once control statements involve integer variables or macros that can be determined statically. DRS-oNE can effectively avoid false positives by checking the constraints required for the read-write or write-write operations to occur. These constraints are referred to as race constraints as described in [ 11 ] . DRS-oNE extends race constraints by assuring that certain values of integer variables must hold if they can be determined statically. This allows for modeling constraints that depend on the values of integer variables declared outside the loop. DRS-oNE is built on top of OMPDart [ 12 ] to utilize its recordings of array access information and the hybrid data structure, AST-CFG, that combines an Abstract Syntax Tree (AST) with a Control Flow Graph (CFG). Using OMPDart’s AST-CFG and array access information, we encoded source code information into race constraints that can be solved by the Z3 SMT solver [ 13 ] . By checking for constraints retrieved from CFG with the Z3 SMT solver, our detection tool can avoid infeasible paths that can be evaluated statically, which ultimately reduces false positive detections. A detailed explanation of DRS-oNE is described in Sections IV and V. Currently, our detection tool only supports analysis for direct access to the array elements in a loop parallelized either with “#pragma omp for” or “#pragma omp simd”. That is, the array was declared statically (i.e., int arr[N];), and accessing the memory region is only done by indexing the array identifier (i.e., arr[i];). Furthermore, it does not support data race caused by data race on a scalar variable. We, therefore, used a subset of Data Race Bench 1.4.0 [ 10 ] , consisting of 55 files 2 2 2 files with more than one parallel construct, nested parallelism, GPU-related directives, data races on scalar variables, and indirect accesses of arrays were removed to evaluate the performance of its effectiveness in detecting data races on array elements. Using the subset of Data Race Bench and seven handwritten test cases, we show that race detection using our implementation of the augmented race constraints can effectively reduce false positives. We make the following contributions in this paper: • Extension of OMPDart to support data race detection of array elements within a parallelized loop • Openly available implementation of augmented race constraints that originates from Pathg [ 11 ] • Benchmark results to show the effectiveness of our augmented race constraints through testing with a subset of Data Race Bench 1.4.0 [ 10 ] and seven additional test cases. The remainder of the paper is structured as follows. Section II provides the related work. Section III provides motivating examples. Section IV provides the definition of race constraints and how we augmented the constraints. Section V describes the implementation details of DRS-oNE. Section VI describes