Efficient and precise datarace detection for multithreaded object-oriented programs

By Jong-Deok Choi, Keunwoo Lee, Alexey Loginov, Robert O'Callahan, Vivek Sarkar, Manu Sridharan. ACM-SIGPLAN Symposium on Programming Language Design and Implementation, 2002

442 citations recorded by the source corpus.

We present a novel approach to dynamic datarace detection for multithreaded object-oriented programs. Past techniques for on-the-fly datarace detection either sacrificed precision for performance, leading to many false positive datarace reports, or maintained precision but incurred significant overheads in the range of 3x to 30x. In contrast, our approach results in very few false positives and runtime overhead in the 13% to 42% range, making it both efficient and precise. This performance improvement is the result of a unique combination of complementary static and dynamic optimization techniques.

Subfields: Artificial Intelligence, Hardware and Architecture

View Paper: https://www.semanticscholar.org/paper/11bd8d0769616d29dbb7662db28cd179219b2a0a

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Hardware and Architecture

Citations in the corpus

Ownership types for safe programming: preventing data races and deadlocks (2002, methodology): “We also implemented some multithreaded server programs including elevator, a real time discrete event simulator [46, 11], an http server, a chat server, a stock quote server, a game server, and phone, a database-backed information sever.”
Learning from mistakes: a comprehensive study on real world concurrency bug characteristics (2008, unknown): “(1) Concurrency bug detection Most previous concurrency bug detection research has focused on detecting data race bugs [7, 10, 31,33,37,42] and deadlock bugs [3,10,37].”
Finding bugs is easy (2004, methodology): “Often, these techniques rely on formal methods and sophisticated program analysis.”
Race directed random testing of concurrent programs (2008, background): “A large body of research focuses on dynamic or static race detection [41, 35, 21, 43, 10, 14].”
AVIO: detecting atomicity violations via access interleaving invariants (2006, unknown): “In dynamic race detection, happens-before [7, 26, 28] and lockset algorithms [6, 34, 38] have been thoroughly studied.”
Finding and Reproducing Heisenbugs in Concurrent Programs (2008, unknown): “One possible solution is to use a dynamic data-race detection tool [46, 9] that captures the outcome of each data-race at runtime.”
RELAY: static race detection on millions of lines of code (2007, methodology): “Much recent effort has gone into lowering the overhead imposed by dynamic analysis – for example by using statically precomputed locksets to prune redundant checks [5, 30].”
Atomizer: a dynamic atomicity checker for multithreaded programs (2004, methodology): “This approach has been extended to object-orien ted languages [50] and has been improved for precision and perfo rmance [11, 45].”
FastTrack: efficient and precise dynamic race detection (2009, unknown): “Other approaches have combined dynamic analysis with a global static analysis to improve precision and performance [8, 14, 39].”
A type and effect system for atomicity (2003, methodology): “The Eraser algorithm has been extended to object-oriented languages [40] and has been improved for precision and performance [11].”
Effective static race detection for Java (2006, background): “Categories and Subject Descriptors D.2.4 [Software Engineering]: Software/Program Veri.cation Reliability; D.2.5 [Software Engineering]: Testing and Debugging Debugging aids General Terms Experimentation, Reliability Keywords static race detection, Java, synchronization, concurrency,…”
RacerX: effective, static detection of race conditions and deadlocks (2003, methodology): “ESC/Java user s manual.”
CP-Miner: A Tool for Finding Copy-paste and Related Bugs in Operating System Code (2004, methodology): “Examples of this approach include explicit model checking [15, 32, 37] and program analysis [8, 14, 17].”
KISS: keep it simple and sequential (2004, methodology): “This algorithm has been extended to object-oriented languages [40] and improved for precision and performance [10].”