research-article

Adversarial memory for detecting destructive races

Authors:

Cormac Flanagan,

Stephen N. FreundAuthors Info & Claims

PLDI '10: Proceedings of the 31st ACM SIGPLAN Conference on Programming Language Design and Implementation

Pages 244 - 254

https://doi.org/10.1145/1806596.1806625

Published: 05 June 2010 Publication History

Abstract

Multithreaded programs are notoriously prone to race conditions, a problem exacerbated by the widespread adoption of multi-core processors with complex memory models and cache coherence protocols. Much prior work has focused on static and dynamic analyses for race detection, but these algorithms typically are unable to distinguish destructive races that cause erroneous behavior from benign races that do not. Performing this classification manually is difficult, time consuming, and error prone.

This paper presents a new dynamic analysis technique that uses adversarial memory to classify race conditions as destructive or benign on systems with relaxed memory models. Unlike a typical language implementation, which may only infrequently exhibit non-sequentially consistent behavior, our adversarial memory implementation exploits the full freedom of the memory model to return older, unexpected, or stale values for memory reads whenever possible, in an attempt to crash the target program (that is, to force the program to behave erroneously). A crashing execution provides concrete evidence of a destructive bug, and this bug can be strongly correlated with a specific race condition in the target program.

Experimental results with our Jumble prototype for Java demonstrate that adversarial memory is highly effective at identifying destructive race conditions, and in distinguishing them from race conditions that are real but benign. Adversarial memory can also reveal destructive races that would not be detected by traditional testing (even after thousands of runs) or by model checkers that assume sequential consistency.

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 and K. Gharachorloo. Shared memory consistency models: A tutorial. IEEE Computer, 29(12):66--76, 1996.

Digital Library

[3]

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

[4]

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

[5]

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

Digital Library

[6]

M. D. Bond, K. E. Coons, and K. S. McKinley. Pacer: Proportional detection of data races. In PLDI, 2010.

Digital Library

[7]

G. Boudol and G. Petri. Relaxed memory models: an operational approach. In POPL, pages 392--403, 2009.

Digital Library

[8]

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

Digital Library

[9]

J. Burnim, K. Sen, and C. Stergiou. Sound and complete monitoring of sequential consistency in relaxed memory models. Technical Report UCB/EECS-2010-31, EECS Department, University of California, Berkeley, 2010.

[10]

J. Burnim, K. Sen, and C. Stergiou. Testing concurrent programs on relaxed memory models. Technical Report UCB/EECS-2010-32, EECS Department, University of California, Berkeley, 2010.

[11]

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

[12]

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

[13]

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

[14]

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

Digital Library

[15]

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

Digital Library

[16]

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

Digital Library

[17]

C. Flanagan and S. N. Freund. FastTrack: Efficient and precise dynamic race detection. In PLDI, pages 121--133, 2009.

Digital Library

[18]

C. Flanagan and S. N. Freund. The RoadRunner dynamic analysis framework for concurrent programs. In ACM Workshop on Program Analysis for Software Tools and Engineering, 2010.

Digital Library

[19]

K. Gharachorloo. Memory Consistency Models for Shared-Memory Multiprocessors. PhD thesis, Stanford University, 1995.

Digital Library

[20]

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

Digital Library

[21]

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

[22]

L. Lamport. How to make a multiprocessor computer that correctly executes multiprocess programs. IEEE Trans. Comput., 28(9):690--691, 1979.

Digital Library

[23]

R. J. Lipton. Reduction: A method of proving properties of parallel programs. Communications of the ACM, 18(12):717--721, 1975.

Digital Library

[24]

S. Lu, S. Park, C. Hu, X. Ma, W. Jiang, Z. Li, R. A. Popa, and Y. Zhou. Muvi: automatically inferring multi-variable access correlations and detecting related semantic and concurrency bugs. In SOSP, pages 103--116, 2007.

Digital Library

[25]

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

Digital Library

[26]

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

[27]

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

[28]

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

Digital Library

[29]

S. Narayanasamy, Z. Wang, J. Tigani, A. Edwards, and B. Calder. Automatically classifying benign and harmful data races using replay analysis. In PLDI, pages 22--31, 2007.

Digital Library

[30]

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

[31]

S. Owens, S. Sarkar, and P. Sewell. A better x86 memory model: x86-TSO. In TPHOLs, pages 391--407, 2009.

Digital Library

[32]

E. Pozniansky and A. Schuster. Efficient on-the-fly data race detection in multihreaded C++ programs. In PPOPP, pages 179--190, 2003.

Digital Library

[33]

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

[34]

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

Digital Library

[35]

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

[36]

K. Sen. Race directed random testing of concurrent programs. In PLDI, pages 11--21, 2008.

Digital Library

[37]

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

[38]

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

[39]

M. Vaziri, F. Tip, and J. Dolby. Associating synchronization constraints with data in an object-oriented language. In POPL, pages 334--345, 2006.

Digital Library

[40]

W. Visser and P. C. Mehlitz. Model checking programs with Java PathFinder. In SPIN, page 27, 2005.

Digital Library

[41]

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

Digital Library

[42]

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

Digital Library

[43]

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

[44]

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

Digital Library

[45]

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

Gao MChakraborty SOzkan BAamodt TJerger NSwift M(2023)Probabilistic Concurrency Testing for Weak Memory ProgramsProceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 210.1145/3575693.3575729(603-616)Online publication date: 27-Jan-2023
https://dl.acm.org/doi/10.1145/3575693.3575729
Wong WGao RLi YAbreu RWotawa FLi D(2023)Software Fault Localization: an Overview of Research, Techniques, and ToolsHandbook of Software Fault Localization10.1002/9781119880929.ch1(1-117)Online publication date: 21-Apr-2023
https://doi.org/10.1002/9781119880929.ch1
Luo WDemsky BSherwood TBerger EKozyrakis C(2021)C11Tester: a race detector for C/C++ atomicsProceedings of the 26th ACM International Conference on Architectural Support for Programming Languages and Operating Systems10.1145/3445814.3446711(630-646)Online publication date: 19-Apr-2021
https://dl.acm.org/doi/10.1145/3445814.3446711
Show More Cited By

Recommendations

FastTrack: efficient and precise dynamic race detection
PLDI '09

\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 ...
Adversarial memory for detecting destructive races
PLDI '10

Multithreaded programs are notoriously prone to race conditions, a problem exacerbated by the widespread adoption of multi-core processors with complex memory models and cache coherence protocols. Much prior work has focused on static and dynamic ...
Detecting concurrency memory corruption vulnerabilities
ESEC/FSE 2019: Proceedings of the 2019 27th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering

Memory corruption vulnerabilities can occur in multithreaded executions, known as concurrency vulnerabilities in this paper. Due to non-deterministic multithreaded executions, they are extremely difficult to detect. Recently, researchers tried to apply ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PLDI '10: Proceedings of the 31st ACM SIGPLAN Conference on Programming Language Design and Implementation

June 2010

514 pages

ISBN:9781450300193

DOI:10.1145/1806596

General Chair:
Ben Zorn
Microsoft Research
,
Program Chair:
Alex Aiken
Stanford University

ACM SIGPLAN Notices Volume 45, Issue 6
PLDI '10
June 2010
496 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/1809028
Issue’s Table of Contents

Copyright © 2010 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]

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 June 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

PLDI '10

Sponsor:

SIGPLAN

PLDI '10: ACM SIGPLAN Conference on Programming Language Design and Implementation

June 5 - 10, 2010

Ontario, Toronto, Canada

Acceptance Rates

Overall Acceptance Rate 406 of 2,067 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

76
Total Citations
View Citations
676
Total Downloads

Downloads (Last 12 months)19
Downloads (Last 6 weeks)4

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Gao MChakraborty SOzkan BAamodt TJerger NSwift M(2023)Probabilistic Concurrency Testing for Weak Memory ProgramsProceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 210.1145/3575693.3575729(603-616)Online publication date: 27-Jan-2023
https://dl.acm.org/doi/10.1145/3575693.3575729
Wong WGao RLi YAbreu RWotawa FLi D(2023)Software Fault Localization: an Overview of Research, Techniques, and ToolsHandbook of Software Fault Localization10.1002/9781119880929.ch1(1-117)Online publication date: 21-Apr-2023
https://doi.org/10.1002/9781119880929.ch1
Luo WDemsky BSherwood TBerger EKozyrakis C(2021)C11Tester: a race detector for C/C++ atomicsProceedings of the 26th ACM International Conference on Architectural Support for Programming Languages and Operating Systems10.1145/3445814.3446711(630-646)Online publication date: 19-Apr-2021
https://dl.acm.org/doi/10.1145/3445814.3446711
Lidbury CDonaldson AMcKinley KFisher K(2019)Sparse record and replay with controlled schedulingProceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/3314221.3314635(576-593)Online publication date: 8-Jun-2019
https://dl.acm.org/doi/10.1145/3314221.3314635
Liu LMillstein TMusuvathi MMcKinley KFisher K(2019)Accelerating sequential consistency for Java with speculative compilationProceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/3314221.3314611(16-30)Online publication date: 8-Jun-2019
https://dl.acm.org/doi/10.1145/3314221.3314611
Roemer JGenç KBond M(2018)High-coverage, unbounded sound predictive race detectionACM SIGPLAN Notices10.1145/3296979.319238553:4(374-389)Online publication date: 11-Jun-2018
https://dl.acm.org/doi/10.1145/3296979.3192385
Roemer JGenç KBond MFoster JGrossman D(2018)High-coverage, unbounded sound predictive race detectionProceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/3192366.3192385(374-389)Online publication date: 11-Jun-2018
https://dl.acm.org/doi/10.1145/3192366.3192385
Islam MMuzahid A(2018)Bugaroo: Exposing Memory Model Bugs in Many-Core Systems2018 IEEE 29th International Symposium on Software Reliability Engineering (ISSRE)10.1109/ISSRE.2018.00028(178-188)Online publication date: Oct-2018
https://doi.org/10.1109/ISSRE.2018.00028
Fava DSteffen MStolz V(2018)Operational Semantics of a Weak Memory Model with Channel SynchronizationFormal Methods10.1007/978-3-319-95582-7_15(258-276)Online publication date: 12-Jul-2018
https://doi.org/10.1007/978-3-319-95582-7_15
Zhang MBiswas SBond M(2017)Avoiding consistency exceptions under strong memory modelsACM SIGPLAN Notices10.1145/3156685.309227152:9(115-127)Online publication date: 18-Jun-2017
https://dl.acm.org/doi/10.1145/3156685.3092271
Show More Cited By

View Options

Get Access

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 Table of Contents