Search papers, labs, and topics across Lattice.
The paper introduces a framework for detecting "short races" in execution traces, where a race condition occurs within a specified window size *w*. They instantiate this framework for happens-before and sync-preserving races, achieving improved space and time complexity compared to existing algorithms like FastTrack and SyncP. Experiments demonstrate that their algorithms detect more races with less resource usage, balancing resource usage and predictive power.
Find more race conditions, faster and with less memory, by focusing on "short races" within a sliding window of events.
We introduce and study the problem of detecting short races in an observed trace. Specifically, for a race type $R$, given a trace $\sigma$ and window size $w$, the task is to determine whether there exists an $R$-race $(e_1, e_2)$ in $\sigma$ such that the subtrace starting with $e_1$ and ending with $e_2$ contains at most $w$ events. We present a monitoring framework for short-race prediction and instantiate the framework for happens-before and sync-preserving races, yielding efficient detection algorithms. Our happens-before algorithm runs in the same time as FastTrack but uses space that scales with $\log w$ as opposed to $\log |\sigma|$. For sync-preserving races, our algorithm runs faster and consumes significantly less space than SyncP. Our experiments validate the effectiveness of these short-race detection algorithms: they run more efficiently, use less memory, and detect significantly more races under the same budget, offering a reasonable balance between resource usage and predictive power.
