Precise and Maximal Race Detection from Incomplete Traces Conference Paper

abstract

• We present RDIT, a novel dynamic technique to detect data races in multithreaded programs with incomplete trace information, i.e., in the presence of missing events. RDIT is both precise and maximal: it does not report any false alarms and it detects a maximal set of true traces from the observed incomplete trace. RDIT is underpinned by a sound BarrierPair model that abstracts away the missing events by capturing the invocation data of their enclosing methods. By making the least conservative abstraction that a missing method introduces synchronization only when it has a memory address in scope that overlaps with other events or other missing methods, and by formulating maximal thread causality as logical constraints, RDIT guarantees to precisely detect races with maximal capability. RDIT has been applied in seven real-world large concurrent systems and has detected dozens of true races with zero false alarms. Comparatively, existing algorithms such as Happens-Before, Causal- Precedes, and Maximal-Causality which are known to be precise all report many false alarms when missing synchronizations.

authors

• Huang, Jeff

published proceedings

• ACM SIGPLAN NOTICES

author list (cited authors)

• Huang, J., & Rajagopalan, A. K.

citation count

• 4

complete list of authors

• Huang, Jeff||Rajagopalan, Arun K

publication date

• December 2016

publisher

• Association for Computing Machinery (ACM)  Publisher

published in

• ACM SIGPLAN NOTICES  Journal

keywords

• Algorithms
• Data Race
• Design
• Incomplete Trace
• Maximal
• Precise
• Theory

Digital Object Identifier (DOI)

• 10.1145/3022671.2984024

International Standard Book Number (ISBN) 13

• 9781450344449

start page

• 462

end page

• 476

volume

• 51

issue

• 10

URL

• http://dx.doi.org/10.1145/3022671.2984024