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

article

RaceTrack: efficient detection of data race conditions via adaptive tracking

Authors:

Tom Rodeheffer,

Wei ChenAuthors Info & Claims

ACM SIGOPS Operating Systems Review, Volume 39, Issue 5

Pages 221 - 234

https://doi.org/10.1145/1095809.1095832

Published: 20 October 2005 Publication History

Abstract

Bugs due to data races in multithreaded programs often exhibit non-deterministic symptoms and are notoriously difficult to find. This paper describes RaceTrack, a dynamic race detection tool that tracks the actions of a program and reports a warning whenever a suspicious pattern of activity has been observed. RaceTrack uses a novel hybrid detection algorithm and employs an adaptive approach that automatically directs more effort to areas that are more suspicious, thus providing more accurate warnings for much less over-head. A post-processing step correlates warnings and ranks code segments based on how strongly they are implicated in potential data races. We implemented RaceTrack inside the virtual machine of Microsoft's Common Language Runtime (product version v1.1.4322) and monitored several major, real-world applications directly out-of-the-box,without any modification. Adaptive tracking resulted in a slowdown ratio of about 3x on memory-intensive programs and typically much less than 2x on other programs,and a memory ratio of typically less than 1.2x. Several serious data race bugs were revealed, some previously unknown.

References

[1]

S. V. Adve, M. D. Hill, B. P. Miller, and R. H. B. Netzer. Detecting data races on weak memory systems. In Proceedings of the 18th Annual International Symposium on Computer Architecture (ISCA), pages 234--243, May 1991.

Digital Library

[2]

C. Boyapati and M. Rinard. A parameterized type system for race-free Java programs. In Proceedings of the 16th ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications (OOPSLA), Oct. 2001.

Digital Library

[3]

A. Broder, S. Glassman, M. Manasse, and G. Zweig. Syntactic clustering of the web. In Proceedings of the 6th International World Wide Web Conference, 1997.

Digital Library

[4]

J.-D. Choi, K. Lee, A. Loginov, R. O'Callahan, V. Sarkar, and M. Sridharan. Efficient and precise data race detection for object oriented programs. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), pages 285--297, 2002.

Digital Library

[5]

J.-D. Choi, B. P. Miller, and R. H. B. Netzer. Techniques for debugging parallel programs with flowback analysis. ACM Transactions on Programming Languages and Systems, 13(4):491--530, October 1991.

Digital Library

[6]

M. Christiaens and K. De Bosschere. TRaDe, a topological approach to on-the-fly race detection in Java programs. In Proceedings of the Java Virtual Machine Research and Technology Symposium (JVM), Apr. 2001.

Digital Library

[7]

A. Dinning and E. Schonberg. An empirical comparison of monitoring algorithms for access anomaly detection. In Proceedings of the 2nd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), pages 1--10, 1990.

Digital Library

[8]

A. Dinning and E. Schonberg. Detecting access anomalies in programs with critical sections. In PADD '91: Proceedings of the 1991 ACM/ONR workshop on Parallel and distributed debugging, pages 85--96, New York, NY, USA, 1991. ACM Press.

Digital Library

[9]

Ecma International. Standard ECMA-335: Common language infrastructure (CLI), 2002. http://www.ecma-international.org/publications/standards/Ecma335.htm.

[10]

D. Engler and K. Ashcraft. RacerX: Effective, static detection of race conditions and deadlocks. In Proceedings of the 19th ACM Symposium on Operating Systems Principles (SOSP), pages 237--252, October 2003.

Digital Library

[11]

C. Flanagan and S. N. Freund. Type-based race detection for Java. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), pages 219--232, 2000.

Digital Library

[12]

J. Gough and K. Gough. Compiling for the .NET Common Language Runtime. Prentice Hall PTR, 2001.

Digital Library

[13]

J. J. Harrow. Runtime checking of multithreaded applications with visual threads. In Proceedings of the 7th International SPIN Workshop on SPIN Model Checking and Software Verification, pages 331--342, London, UK, 2000. Springer-Verlag.

Digital Library

[14]

T. Henzinger, R. Jhala, and R. Majumder. Race checking by context inference. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), June 2004.

Digital Library

[15]

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

Digital Library

[16]

J. MacCormick, N. Murphy, M. Najork, C. A. Thekkath, and L. Zhou. Boxwood: Abstractions as the foundation for storage infrastructure. In Proceedings of the 6th Symposium on Operating Systems Design and Implementation (OSDI), pages 105--120, Dec. 2004.

Digital Library

[17]

F. Mattern. Virtual time and global states of distributed systems. In C. M. et al., editor, Proc. Workshop on Parallel and Distributed Algorithms, pages 215--226, North-Holland / Elsevier, 1989.

[18]

J. Mellor-Crummey. On-the-fly detection of data races for programs with nested fork-join parallelism. In Proceedings of Supercomputing, November 1991.

Digital Library

[19]

Microsoft Corporation. Basic class library communities. http://msdn.microsoft.com/netframework/programming/classlibraries/.

[20]

Microsoft Corporation. Shared source common language infrastructure 1.0 release, Nov. 2002. http://msdn.microsoft.com/net/sscli.

[21]

H. Nishiyama. Detecting data races using dynamic escape analysis based on read barrier. In Proceedings of the 3rd Virtual Machine Research and Technology Symposium (VM), May 2004.

Digital Library

[22]

R. O'Callahan and J.-D. Choi. Hybrid dynamic data race detection. In Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), pages 167--178, 2003.

Digital Library

[23]

D. Perković and P. J. Keleher. Online data-race detection via coherency guarantees. In The Second Symposium on Operating Systems Design and Implementation (OSDI), pages 47--57, Oct. 1996.

Digital Library

[24]

E. Pozniansky and A. Schuster. Efficient on-the-fly race detection in multithreaded C++ programs. In Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), 2003.

Digital Library

[25]

C. Praun and T. Gross. Object race detection. In Proceedings of the 16th ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications (OOPSLA), pages 70--82, 2001.

Digital Library

[26]

M. O. Rabin. Fingerprinting by random polynomials. Report TR--15--81, Department of Computer Science, Harvard University, 1981.

[27]

M. Ronsse and K. De Bosschere. RecPlay: A fully integrated practical record/replay system. ACM Transactions on Computer Systems, 17(2):133--152, May 1999.

Digital Library

[28]

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

Digital Library

[29]

D. C. Schmidt and T. Harrison. Double-checked locking: An optimization pattern for efficiently initializing and accessing thread-safe objects. In M. Buschmann and D. Riehle, editors, Pattern Languages of Program Design 3. Addison-Wesley, Reading, MA, 1997.

Digital Library

[30]

E. Schonberg. On-the-fly detection of access anomalies. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), pages 285--297, 1989.

Digital Library

[31]

Standard Performance Evaluation Corporation. SPEC JBB2000. http://www.spec.org/jbb2000/.

[32]

N. Sterling. Warlock: A static data race analysis tool. In Proceedings of USENIX Winter Technical Conference, January 1993.

[33]

Valgrind project. Helgrind: a data-race detector, 2005. http://valgrind.org/docs/manual/hg-manual.html.

Cited By

Alsofyani MWang L(2024)Detecting Data Races in OpenMP with Deep Learning and Large Language ModelsWorkshop Proceedings of the 53rd International Conference on Parallel Processing10.1145/3677333.3678160(96-103)Online publication date: 12-Aug-2024
https://dl.acm.org/doi/10.1145/3677333.3678160
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
Sales EInverso OTuosto E(2024)Accurate Static Data Race Detection for CFormal Methods10.1007/978-3-031-71162-6_23(443-462)Online publication date: 11-Sep-2024
https://doi.org/10.1007/978-3-031-71162-6_23
Show More Cited By

Index Terms

RaceTrack: efficient detection of data race conditions via adaptive tracking
1. Information systems
  1. Data management systems
    1. Middleware for databases
      1. Distributed transaction monitors
2. Software and its engineering
  1. Software creation and management
    1. Software verification and validation
  2. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Process management
        Monitors

Recommendations

RaceTrack: efficient detection of data race conditions via adaptive tracking
SOSP '05: Proceedings of the twentieth ACM symposium on Operating systems principles

Bugs due to data races in multithreaded programs often exhibit non-deterministic symptoms and are notoriously difficult to find. This paper describes RaceTrack, a dynamic race detection tool that tracks the actions of a program and reports a warning ...
TRADE: Precise Dynamic Race Detection for Scalable Transactional Memory Systems

As other multithreaded programs, transactional memory (TM) programs are prone to race conditions. Previous work focuses on extending existing definitions of data race for lock-based applications to TM applications, which requires all transactions to be ...
Fast&Furious: A Tool for Detecting Covert Racing
PARMA-DITAM '15: Proceedings of the 6th Workshop on Parallel Programming and Run-Time Management Techniques for Many-core Architectures

Existing multi-threaded applications perform synchronization either in an explicit way, e.g., making use of the functionality provided by synchronization libraries or in an implicit or "covert" way, e.g., using shared variables. Unfortunately, the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGOPS Operating Systems Review

ACM SIGOPS Operating Systems Review Volume 39, Issue 5

SOSP '05

December 2005

290 pages

ISSN:0163-5980

DOI:10.1145/1095809

Issue’s Table of Contents

SOSP '05: Proceedings of the twentieth ACM symposium on Operating systems principles
October 2005
259 pages
ISBN:1595930795
DOI:10.1145/1095810
General Chair:
Andrew Herbert
Microsoft Research, UK
,
Program Chair:
Ken Birman
Cornell University, USA

Copyright © 2005 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: 20 October 2005

Published in SIGOPS Volume 39, Issue 5

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

387
Total Citations
View Citations
1,658
Total Downloads

Downloads (Last 12 months)56
Downloads (Last 6 weeks)10

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Alsofyani MWang L(2024)Detecting Data Races in OpenMP with Deep Learning and Large Language ModelsWorkshop Proceedings of the 53rd International Conference on Parallel Processing10.1145/3677333.3678160(96-103)Online publication date: 12-Aug-2024
https://dl.acm.org/doi/10.1145/3677333.3678160
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
Sales EInverso OTuosto E(2024)Accurate Static Data Race Detection for CFormal Methods10.1007/978-3-031-71162-6_23(443-462)Online publication date: 11-Sep-2024
https://doi.org/10.1007/978-3-031-71162-6_23
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
Mathur UPavlogiannis ATunç HViswanathan MFalsafi BFerdman MLu SWenisch T(2022)A tree clock data structure for causal orderings in concurrent executionsProceedings of the 27th ACM International Conference on Architectural Support for Programming Languages and Operating Systems10.1145/3503222.3507734(710-725)Online publication date: 28-Feb-2022
https://dl.acm.org/doi/10.1145/3503222.3507734
Wang YGao FWang LYu TZhao JLi X(2022)Automatic Detection, Validation, and Repair of Race Conditions in Interrupt-Driven Embedded SoftwareIEEE Transactions on Software Engineering10.1109/TSE.2020.298917148:1(346-363)Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1109/TSE.2020.2989171
Khanna DPurandare RSharma S(2021)Synthesizing Multi-threaded Tests from Sequential Traces to Detect Communication Deadlocks2021 14th IEEE Conference on Software Testing, Verification and Validation (ICST)10.1109/ICST49551.2021.00013(1-12)Online publication date: Apr-2021
https://doi.org/10.1109/ICST49551.2021.00013
Chen DJiang YXu CMa X(2021)On interleaving space exploration of multi-threaded programsFrontiers of Computer Science: Selected Publications from Chinese Universities10.1007/s11704-020-9501-615:4Online publication date: 1-Aug-2021
https://dl.acm.org/doi/10.1007/s11704-020-9501-6
Bora UDas SKukreja PJoshi SUpadrasta RRajopadhye S(2020)LLOVACM Transactions on Architecture and Code Optimization10.1145/341859717:4(1-26)Online publication date: 22-Dec-2020
https://dl.acm.org/doi/10.1145/3418597
Pavlogiannis A(2019)Fast, sound, and effectively complete dynamic race predictionProceedings of the ACM on Programming Languages10.1145/33710854:POPL(1-29)Online publication date: 20-Dec-2019
https://dl.acm.org/doi/10.1145/3371085
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.

Media

Figures

Other

Tables

View Issue’s Table of Contents