Dynamic Data-Race Detection Through the Fine-Grained Lens

Rucha Kulkarni, Umang Mathur, Andreas Pavlogiannis

Publikation: Bidrag til bog/antologi/rapport/proceedingKonferencebidrag i proceedingsForskningpeer review

Abstract

Data races are among the most common bugs in concurrency. The standard approach to data-race detection is via dynamic analyses, which work over executions of concurrent programs, instead of the program source code. The rich literature on the topic has created various notions of dynamic data races, which are known to be detected efficiently when certain parameters (e.g., number of threads) are small. However, the fine-grained complexity of all these notions of races has remained elusive, making it impossible to characterize their trade-offs between precision and efficiency. In this work we establish several fine-grained separations between many popular notions of dynamic data races. The input is an execution trace σ with N events, T threads and L locks. Our main results are as follows. First, we show that happens-before HB races can be detected in O(N · min(T ,L)) time, improving over the standard O(N · T ) bound when L = o(T ). Moreover, we show that even reporting an HB race that involves a read access is hard for 2-orthogonal vectors (2-OV). This is the first rigorous proof of the conjectured quadratic lower-bound in detecting HB races. Second, we show that the recently introduced synchronization-preserving races are hard to detect for 3-OV and thus have a cubic lower bound, when T = Ω(N). This establishes a complexity separation from HB races which are known to be strictly less expressive. Third, we show that lock-cover races are hard for 2-OV, and thus have a quadratic lower-bound, even when T = 2 and L = ω(logN). The similar notion of lock-set races is known to be detectable in O(N · L) time, and thus we achieve a complexity separation between the two. Moreover, we show that lock-set races become hitting-set (HS)-hard when L = Θ(N), and thus also have a quadratic lower bound, when the input is sufficiently complex. To our knowledge, this is the first work that characterizes the complexity of well-established dynamic race-detection techniques, allowing for a rigorous comparison between them.

OriginalsprogEngelsk
Titel32nd International Conference on Concurrency Theory (CONCUR 2021)
RedaktørerSerge Haddad, Daniele Varacca
Antal sider23
ForlagSchloss Dagstuhl--Leibniz-Zentrum für Informatik
Publikationsdato2021
Sider16:1-16:23
ISBN (Trykt)978-3-95977-203-7
ISBN (Elektronisk)9783959772037
DOI
StatusUdgivet - 2021
Begivenhed32nd International Conference on Concurrency Theory - Virtual
Varighed: 20 aug. 202124 aug. 2021
Konferencens nummer: 32

Konference

Konference32nd International Conference on Concurrency Theory
Nummer32
LokationVirtual
Periode20/08/202124/08/2021
NavnLeibniz International Proceedings in Informatics
Vol/bind203
ISSN1868-8969

Fingeraftryk

Dyk ned i forskningsemnerne om 'Dynamic Data-Race Detection Through the Fine-Grained Lens'. Sammen danner de et unikt fingeraftryk.

Citationsformater