More Web Proxy on the site http://driver.im/

research-article

FastTrack: efficient and precise dynamic race detection

Authors:

Cormac Flanagan,

Stephen N. FreundAuthors Info & Claims

ACM SIGPLAN Notices, Volume 44, Issue 6

Pages 121 - 133

https://doi.org/10.1145/1543135.1542490

Published: 15 June 2009 Publication History

Abstract

\begin{abstract}

Multithreaded programs are notoriously prone to race conditions. Prior work on dynamic race detectors includes fast but imprecise race detectors that report false alarms, as well as slow but precise race detectors that never report false alarms. The latter typically use expensive vector clock operations that require time linear in the number of program threads.

This paper exploits the insight that the full generality of vector clocks is unnecessary in most cases. That is, we can replace heavyweight vector clocks with an adaptive lightweight representation that, for almost all operations of the target program, requires only constant space and supports constant-time operations. This representation change significantly improves time and space performance, with no loss in precision.

Experimental results on Java benchmarks including the Eclipse development environment show that our FastTrack race detector is an order of magnitude faster than a traditional vector-clock race detector, and roughly twice as fast as the high-performance DJIT+ algorithm. FastTrack is even comparable in speed to Eraser on our Java benchmarks, while never reporting false alarms.

References

[1]

M. Abadi, C. Flanagan, and S. N. Freund. Types for safe locking: Static race detection for Java. TOPLAS, 28(2):207--255, 2006.

Digital Library

[2]

S. V. Adve, M. D. Hill, B. P. Miller, and R. H. B. Netzer. Detecting data races on weak memory systems. In ISCA, pages 234--243, 1991.

Digital Library

[3]

R. Agarwal and S. D. Stoller. Type inference for parameterized race-free Java. In VMCAI, pages 149--160, 2004.

[4]

A. Aiken and D. Gay. Barrier inference. In POPL, pages 243--354, 1998.

Digital Library

[5]

C. Boyapati and M. Rinard. A parameterized type system for race-free Java programs. In OOPSLA, pages 56--69, 2001.

Digital Library

[6]

CERN. Colt 1.2.0. Available at http://dsd.lbl.gov/~hoschek/colt/, 2007.

[7]

A. T. Chamillard, L. A. Clarke, and G. S. Avrunin. An empirical comparison of static concurrency analysis techniques. Technical Report 96-084, Department of Computer Science, University of Massachusetts at Amherst, 1996.

Digital Library

[8]

J.-D. Choi, K. Lee, A. Loginov, R. O'Callahan, V. Sarkar, and M. Sridhara. Efficient and precise datarace detection for multithreaded object-oriented programs. In PLDI, pages 258--269, 2002.

Digital Library

[9]

J.-D. Choi, B. P. Miller, and R. H. B. Netzer. Techniques for debugging parallel programs with flowback analysis. TOPLAS, 13(4):491--530, 1991.

Digital Library

[10]

M. Christiaens and K. D. Bosschere. Accordion clocks: Logical clocks for data race detection. In Euro-Par, pages 494--503, 2001.

Digital Library

[11]

M. Christiaens and K. D. Bosschere. TRaDe: Data Race Detection for Java. In International Conference on Computational Science, pages 761--770, 2001.

Digital Library

[12]

M. B. Dwyer and L. A. Clarke. Data flow analysis for verifying properties of concurrent programs. Technical Report 94-045, Department of Computer Science, University of Massachusetts at Amherst, 1994.

Digital Library

[13]

The Eclipse programming environment, version 3.4.0. Available at \texttthttp://www.eclipse.org, 2009.

[14]

T. Elmas, S. Qadeer, and S. Tasiran. Goldilocks: A race and transaction-aware Java runtime. In PLDI, pages 245--255, 2007.

Digital Library

[15]

D. R. Engler and K. Ashcraft. RacerX: Effective, static detection of race conditions and deadlocks. In SOSP, pages 237--252, 2003.

Digital Library

[16]

C. Flanagan and S. N. Freund. Atomizer: A dynamic atomicity checker for multithreaded programs. Sci. Comput. Program., 71(2):89--109, 2008.

Digital Library

[17]

C. Flanagan, S. N. Freund, and J. Yi. Velodrome: A sound and complete dynamic atomicity checker for multithreaded programs. In PLDI, pages 293--303, 2008.

Digital Library

[18]

E. Fleury and G. Sutre. Raja, version 0.4.0-pre4. Available at http://raja.sourceforge.net/, 2007.

[19]

D. Grossman. Type-safe multithreading in Cyclone. In TLDI, pages 13--25, 2003.

Digital Library

[20]

Java Grande Forum. Java Grande benchmark suite. Available at http://www.javagrande.org/, 2008.

[21]

L. Lamport. Time, clocks, and the ordering of events in a distributed system. Commun. ACM, 21(7):558--565, 1978.

Digital Library

[22]

J. Manson, W. Pugh, and S. V. Adve. The Java memory model. In POPL, pages 378--391, 2005.

Digital Library

[23]

F. Mattern. Virtual time and global states of distributed systems. In Workshop on Parallel and Distributed Algorithms, 1988.

[24]

J. M. Mellor-Crummey. On-the-fly detection of data races for programs with nested fork--join parallelism. In Supercomputing, pages 24--33, 1991.

Digital Library

[25]

M. Musuvathi, S. Qadeer, T. Ball, G. Basler, P. A. Nainar, and I. Neamtiu. Finding and reproducing heisenbugs in concurrent programs. In OSDI, 2008.

Digital Library

[26]

M. Naik, A. Aiken, and J. Whaley. Effective static race detection for Java. In PLDI, pages 308--319, 2006.

Digital Library

[27]

H. Nishiyama. Detecting data races using dynamic escape analysis based on read barrier. In Virtual Machine Research and Technology Symposium, pages 127--138, 2004.

Digital Library

[28]

R. O'Callahan and J.-D. Choi. Hybrid dynamic data race detection. In PPOPP, pages 167--178, 2003.

Digital Library

[29]

E. Pozniansky and A. Schuster. Efficient on-the-fly data race detection in multihreaded C programs. In Proceedings of the ACM Symposium on Principles and Practice of Parallel Programming, pages 179--190, 2003.

Digital Library

[30]

E. Pozniansky and A. Schuster. MultiRace: Efficient on-the-fly data race detection in multithreaded C programs. Concurrency and Computation: Practice and Experience, 19(3):327--340, 2007.

Digital Library

[31]

M. Ronsse and K. D. Bosschere. RecPlay: A fully integrated practical record/replay system. TCS, 17(2):133--152, 1999.

Digital Library

[32]

C. Sadowski, S. N. Freund, and C. Flanagan. SingleTrack: A dynamic determinism checker for multithreaded programs. In ESOP, 2009.

Digital Library

[33]

S. Savage, M. Burrows, G. Nelson, P. Sobalvarro, and T. E. Anderson. Eraser: A dynamic data race detector for multi-threaded programs. TOCS, 15(4):391--411, 1997.

Digital Library

[34]

E. Schonberg. On-the-fly detection of access anomalies. In PLDI, pages 285--297, 1989.

Digital Library

[35]

Standard Performance Evaluation Corporation. SPEC benchmarks. http://www.spec.org/, 2003.

[36]

N. Sterling. Warlock: A static data race analysis tool. In USENIX Winter Technical Conference, pages 97--106, 1993.

[37]

Sun Microsystems. The java.util.concurrent package. Available at http://java.sun.com/javase/6/docs/api/, 2008.

[38]

C. von Praun and T. Gross. Object race detection. In OOPSLA, pages 70--82, 2001.

Digital Library

[39]

C. von Praun and T. Gross. Static conflict analysis for multi-threaded object-oriented programs. In PLDI, pages 115--128, 2003.

Digital Library

[40]

J. W. Voung, R. Jhala, and S. Lerner. Relay: static race detection on millions of lines of code. In FSE, pages 205--214, 2007.

Digital Library

[41]

E. Yahav. Verifying safety properties of concurrent Java programs using 3-valued logic. In POPL, pages 27--40, 2001.

Digital Library

[42]

Y. Yu, T. Rodeheffer, and W. Chen. RaceTrack: Efficient detection of data race conditions via adaptive tracking. In SOSP, pages 221--234, 2005.

Digital Library

Cited By

Zhao JFu YWu YDong JHong R(2025)Thread-sensitive fuzzing for concurrency bug detectionComputers & Security10.1016/j.cose.2024.104171148(104171)Online publication date: Jan-2025
https://doi.org/10.1016/j.cose.2024.104171
Sun XGupta RBond MLee JPayer H(2024)SSRD: Shapes and Summaries for Race Detection in Concurrent Data StructuresProceedings of the 2024 ACM SIGPLAN International Symposium on Memory Management10.1145/3652024.3665505(68-81)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3652024.3665505
Arora JMuller SAcar U(2024)Disentanglement with Futures, State, and InteractionProceedings of the ACM on Programming Languages10.1145/36328958:POPL(1569-1599)Online publication date: 5-Jan-2024
https://dl.acm.org/doi/10.1145/3632895
Show More Cited By

Recommendations

FastTrack: efficient and precise dynamic race detection
PLDI '09: Proceedings of the 30th ACM SIGPLAN Conference on Programming Language Design and Implementation

\begin{abstract}

Multithreaded programs are notoriously prone to race conditions. Prior work on dynamic race detectors includes fast but imprecise race detectors that report false alarms, as well as slow but precise race detectors that never report ...
Tiddle: a trace description language for generating concurrent benchmarks to test dynamic analyses
WODA '09: Proceedings of the Seventh International Workshop on Dynamic Analysis

Dynamic analysis is a promising technique for finding concurrency bugs in multithreaded programs. However, testing a dynamic analysis tool can be difficult. Researchers end up writing large amounts of small benchmark programs. Since the benchmarks ...
On-the-fly race detection in multi-threaded programs
PADTAD '08: Proceedings of the 6th workshop on Parallel and distributed systems: testing, analysis, and debugging

Multi-core chips enable parallel processing for general purpose applications. Unfortunately, parallel programs may contain synchronization defects. Such defects are difficult to detect due to nondeterministic interleavings of parallel threads. Current ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 44, Issue 6

PLDI '09

June 2009

478 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/1543135

Issue’s Table of Contents

PLDI '09: Proceedings of the 30th ACM SIGPLAN Conference on Programming Language Design and Implementation
June 2009
492 pages
ISBN:9781605583921
DOI:10.1145/1542476
General Chair:
Michael Hind
IBM Research, USA
,
Program Chair:
Amer Diwan
University of Colorado at Boulder, USA

Copyright © 2009 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 15 June 2009

Published in SIGPLAN Volume 44, Issue 6

Check for updates

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

689
Total Citations
View Citations
3,224
Total Downloads

Downloads (Last 12 months)274
Downloads (Last 6 weeks)74

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Zhao JFu YWu YDong JHong R(2025)Thread-sensitive fuzzing for concurrency bug detectionComputers & Security10.1016/j.cose.2024.104171148(104171)Online publication date: Jan-2025
https://doi.org/10.1016/j.cose.2024.104171
Sun XGupta RBond MLee JPayer H(2024)SSRD: Shapes and Summaries for Race Detection in Concurrent Data StructuresProceedings of the 2024 ACM SIGPLAN International Symposium on Memory Management10.1145/3652024.3665505(68-81)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3652024.3665505
Arora JMuller SAcar U(2024)Disentanglement with Futures, State, and InteractionProceedings of the ACM on Programming Languages10.1145/36328958:POPL(1569-1599)Online publication date: 5-Jan-2024
https://dl.acm.org/doi/10.1145/3632895
Westrick SFluet MRainey MAcar U(2024)Automatic Parallelism ManagementProceedings of the ACM on Programming Languages10.1145/36328808:POPL(1118-1149)Online publication date: 5-Jan-2024
https://dl.acm.org/doi/10.1145/3632880
Niskov FKutovoy EKurmangaleev S(2024)Enhanced S2E for Analysis of Multi-Thread SoftwareProgramming and Computer Software10.1134/S036176882309007449:S1(S39-S44)Online publication date: 26-Jan-2024
https://doi.org/10.1134/S0361768823090074
Pätzold CSchwitanski SJenke JTomski FMüller M(2024)Correctness Checking of MPI+OpenMP Applications Using Vector Clocks in MUSTProceedings of the SC '24 Workshops of the International Conference on High Performance Computing, Network, Storage, and Analysis10.1109/SCW63240.2024.00035(227-231)Online publication date: 17-Nov-2024
https://dl.acm.org/doi/10.1109/SCW63240.2024.00035
Jacobson JBurtscher MGopalakrishnan G(2024)HiRace: Accurate and Fast Data Race Checking for GPU ProgramsSC24: International Conference for High Performance Computing, Networking, Storage and Analysis10.1109/SC41406.2024.00042(1-14)Online publication date: 17-Nov-2024
https://doi.org/10.1109/SC41406.2024.00042
Costea ATiwari AChianasta SR KRoychoudhury ASergey I(2023)Hippodrome: Data Race Repair Using Static Analysis SummariesACM Transactions on Software Engineering and Methodology10.1145/354694232:2(1-33)Online publication date: 31-Mar-2023
https://dl.acm.org/doi/10.1145/3546942
Zhao YWang ZLiu SSun JChen JChen X(2023)Achieving High MAP-Coverage Through Pattern Constraint ReductionIEEE Transactions on Software Engineering10.1109/TSE.2022.314448049:1(99-112)Online publication date: 1-Jan-2023
https://doi.org/10.1109/TSE.2022.3144480
Khan AZou MKim KXu DBianchi ATian D(2023)Fuzzing SGX Enclaves via Host Program Mutations2023 IEEE 8th European Symposium on Security and Privacy (EuroS&P)10.1109/EuroSP57164.2023.00035(472-488)Online publication date: Jul-2023
https://doi.org/10.1109/EuroSP57164.2023.00035
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents