Dynamic Data-Race Detection Through the Fine-Grained Lens

Rucha Kulkarni, Umang Mathur, Andreas Pavlogiannis

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-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.

Original languageEnglish
Title of host publication32nd International Conference on Concurrency Theory (CONCUR 2021)
EditorsSerge Haddad, Daniele Varacca
Number of pages23
PublisherSchloss Dagstuhl--Leibniz-Zentrum für Informatik
Publication date2021
Pages16:1-16:23
ISBN (Print)978-3-95977-203-7
ISBN (Electronic)9783959772037
DOIs
Publication statusPublished - 2021
Event32nd International Conference on Concurrency Theory - Virtual
Duration: 20 Aug 202124 Aug 2021
Conference number: 32

Conference

Conference32nd International Conference on Concurrency Theory
Number32
LocationVirtual
Period20/08/202124/08/2021
SeriesLeibniz International Proceedings in Informatics
Volume203
ISSN1868-8969

Keywords

  • Data races
  • Dynamic analyses
  • Fine-grained complexity

Fingerprint

Dive into the research topics of 'Dynamic Data-Race Detection Through the Fine-Grained Lens'. Together they form a unique fingerprint.

Cite this