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

research-article

Race directed random testing of concurrent programs

Author:

Koushik SenAuthors Info & Claims

ACM SIGPLAN Notices, Volume 43, Issue 6

Pages 11 - 21

https://doi.org/10.1145/1379022.1375584

Published: 07 June 2008 Publication History

Abstract

Bugs in multi-threaded programs often arise due to data races. Numerous static and dynamic program analysis techniques have been proposed to detect data races. We propose a novel randomized dynamic analysis technique that utilizes potential data race information obtained from an existing analysis tool to separate real races from false races without any need for manual inspection. Specifically, we use potential data race information obtained from an existing dynamic analysis technique to control a random scheduler of threads so that real race conditions get created with very high probability and those races get resolved randomly at runtime. Our approach has several advantages over existing dynamic analysis tools. First, we can create a real race condition and resolve the race randomly to see if an error can occur due to the race. Second, we can replay a race revealing execution efficiently by simply using the same seed for random number generation--we do not need to record the execution. Third, our approach has very low overhead compared to other precise dynamic race detection techniques because we only track all synchronization operations and a single pair of memory access statements that are reported to be in a potential race by an existing analysis. We have implemented the technique in a prototype tool for Java and have experimented on a number of large multi-threaded Java programs. We report a number of previously known and unknown bugs and real races in these Java programs.

References

[1]

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

Digital Library

[2]

R. Agarwal, A. Sasturkar, L. Wang, and S. D. Stoller. Optimized run-time race detection and atomicity checking using partial discovered types. In 20th IEEE/ACM international Conference on Automated software engineering (ASE), pages 233--242. ACM, 2005.

Digital Library

[3]

R. Agarwal and S. D. Stoller. Type inference for parameterized race-free java. In Verification, Model Checking, and Abstract Interpretation, 5th International Conference (VMCAI), pages 149--160, 2004.

[4]

A. Aiken and D. Gay. Barrier inference. In 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, pages 342--354. ACM, 1998.

Digital Library

[5]

D. F. Bacon, R. E. Strom, and A. Tarafdar. Guava: a dialect of java without data races. In ACM SIGPLAN Conference on Object-Oriented Programming Systems, Languages and Applications (OOPSLA'00), pages 382--400, 2000.

Digital Library

[6]

C. Boyapati and M. C. Rinard. A parameterized type system for race-free java programs. In ACM SIGPLAN Conference on Object-Oriented Programming Systems, Languages and Applications (OOPSLA'01), pages 56--69, 2001.

Digital Library

[7]

D. Bruening. Systematic testing of multithreaded Java programs. Master's thesis, MIT, 1999.

[8]

S. Burckhardt, R. Alur, and M. M. K. Martin. Checkfence: checking consistency of concurrent data types on relaxed memory models. In CM SIGPLAN 2007 Conference on Programming Language Design and Implementation (PLDI), pages 12--21, 2007.

Digital Library

[9]

R. H. Carver and Y. Lei. A general model for reachability testing of concurrent programs. In 6th International Conference on Formal Engineering Methods (ICFEM'04), volume 3308 of LNCS, pages 76--98, 2004.

[10]

J. D. Choi, K. Lee, A. Loginov, R. O'Callahan, V. Sarkar, and M. Sridharan. Efficient and precise datarace detection for multithreaded object-oriented programs. In Proc. of the ACM SIGPLAN Conference on Programming language design and implementation, pages 258--269, 2002.

Digital Library

[11]

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

Digital Library

[12]

J.-D. Choi and A. Zeller. Isolating failure-inducing thread schedules. In ISSTA '02: Proceedings of the 2002 ACM SIGSOFT international symposium on Software testing and analysis, pages 210--220. ACM, 2002.

Digital Library

[13]

M. Christiaens and K. D. Bosschere. Trade, a topological approach to on-the-fly race detection in java programs. In JavaTM Virtual Machine Research and Technology Symposium (JVM), pages 15--15. USENIX Association, 2001.

Digital Library

[14]

A. Dinning and E. Schonberg. Detecting access anomalies in programs with critical sections. In Proc. of the ACM/ONR Workshop on Parallel and Distributed Debugging, 1991.

Digital Library

[15]

M. B. Dwyer, S. Elbaum, S. Person, and R. Purandare. Parallel randomized state-space search. In 29th International Conference on Software Engineering (ICSE), pages 3--12. IEEE, 2007.

Digital Library

[16]

M. B. Dwyer, J. Hatcliff, Robby, and V. P. Ranganath. Exploiting object escape and locking information in partial-order reductions for concurrent object-oriented programs. Form. Methods Syst. Des., 25(2--3):199--240, 2004.

Digital Library

[17]

J. E. M. Clarke, O. Grumberg, and D. A. Peled. Model checking. MIT Press, 1999.

Digital Library

[18]

O. Edelstein, E. Farchi, Y. Nir, G. Ratsaby, and S. Ur. Multithreaded Java program test generation. IBM Systems Journal, 41(1):111--125, 2002.

Digital Library

[19]

D. R. Engler and K. Ashcraft. Racerx: effective, static detection of race conditions and deadlocks. In 19th ACM Symposium on Operating Systems Principles (SOSP), pages 237--252, 2003.

Digital Library

[20]

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

Digital Library

[21]

C. Flanagan and S. N. Freund. Detecting race conditions in large programs. In Proc. of the Program Analysis for Software Tools and Engineering Conference, 2001.

Digital Library

[22]

C. Flanagan and S. N. Freund. Atomizer: a dynamic atomicity checker for multithreaded programs. In 31st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL), pages 256--267, 2004.

Digital Library

[23]

C. Flanagan and S. Qadeer. A type and effect system for atomicity. In ACM SIGPLAN 2003 Conference on Programming Language Design and Implementation, pages 338--349, 2003.

Digital Library

[24]

D. Gay, P. Levis, R. von Behren, M. Welsh, E. Brewer, and D. Culler. The nesC language: A holistic approach to networked embedded systems. In ACM SIGPLAN Conference on Programming language design and implementation, pages 1--11, 2003.

Digital Library

[25]

P. Godefroid. Model checking for programming languages using verisoft. In 24th Symposium on Principles of Programming Languages, pages 174--186, 1997.

Digital Library

[26]

R. Grosu and S. A. Smolka. Monte carlo model checking. In 11th International Conference Tools and Algorithms for the Construction and Analysis of Systems (TACAS 2005), volume 3440 of LNCS, pages 271--286, 2005.

Digital Library

[27]

K. Havelund and T. Pressburger. Model Checking Java Programs using Java PathFinder. Int. Journal on Software Tools for Technology Transfer, 2(4):366--381, 2000.

[28]

T. A. Henzinger, R. Jhala, and R. Majumdar. Race checking by context inference. SIGPLAN Not., 39(6):1--13, 2004.

Digital Library

[29]

G. Holzmann. The Spin model checker. IEEE Transactions on Software Engineering, 23(5):279--295, 1997.

Digital Library

[30]

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

Digital Library

[31]

M. Musuvathi and S. Qadeer. Iterative context bounding for systematic testing of multithreaded programs. In ACM Symposium on Programming Language Design and Implementation (PLDI'07), 2007.

Digital Library

[32]

M. Naik and A. Aiken. Conditional must not aliasing for static race detection. In 34th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 327--338, 2007.

Digital Library

[33]

M. Naik, A. Aiken, and J. Whaley. Effective static race detection for java. In ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 308--319, 2006.

Digital Library

[34]

S. Narayanasamy, Z. Wang, J. Tigani, A. Edwards, and B. Calder. Automatically classifying benign and harmful data races using replay analysis. In ACM SIGPLAN 2007 Conference on Programming Language Design and Implementation (PLDI), pages 22--31, 2007.

Digital Library

[35]

R. Netzer and B. Miller. Detecting data races in parallel program executions. In Advances in Languages and Compilers for Parallel Computing. MIT Press, 1990.

[36]

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

[37]

R. O'Callahan and J.-D. Choi. Hybrid dynamic data race detection. In ACM SIGPLAN symposium on Principles and practice of parallel programming, pages 167--178. ACM, 2003.

Digital Library

[38]

E. Pozniansky and A. Schuster. Efficient on-the-fly data race detection in multithreaded c++ programs. In Ninth ACM SIGPLAN symposium on Principles and practice of parallel programming (PPoPP), pages 179--190. ACM, 2003.

Digital Library

[39]

P. Pratikakis, J. S. Foster, and M. Hicks. LOCKSMITH: context-sensitive correlation analysis for race detection. In ACM SIGPLAN conference on Programming language design and implementation (PLDI), pages 320--331. ACM, 2006.

Digital Library

[40]

S. Qadeer and D. Wu. Kiss: keep it simple and sequential. In ACM SIGPLAN 2004 conference on Programming language design and implementation (PLDI), pages 14--24. ACM, 2004.

Digital Library

[41]

B. Richards and J. R. Larus. Protocol-based data-race detection. In Proc. of the SIGMETRICS symposium on Parallel and distributed tools, pages 40--47, 1998.

Digital Library

[42]

M. Ronsse and K. D. Bosschere. Recplay: a fully integrated practical record/replay system. ACM Trans. Comput. Syst., 17(2):133--152, 1999.

Digital Library

[43]

S. Savage, M. Burrows, G. Nelson, P. Sobalvarro, and T. E. Anderson. Eraser: A dynamic data race detector for multithreaded programs. ACM Trans. Comput. Syst., 15(4):391--411, 1997.

Digital Library

[44]

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

Digital Library

[45]

K. Sen. Effective random testing of concurrent programs. In 22nd IEEE/ACM nternational Conference on Automated Software Engineering (ASE'07), 2007.

Digital Library

[46]

K. Sen and G. Agha. A race-detection and flipping algorithm for automated testing of multi-threaded programs. In Haifa verification conference 2006 (HVC'06), Lecture Notes in Computer Science. Springer, 2006.

Digital Library

[47]

O. Shacham, M. Sagiv, and A. Schuster. Scaling model checking of dataraces using dynamic information. J. Parallel Distrib. Comput., 67(5):536--550, 2007.

Digital Library

[48]

S. F. Siegel, A. Mironova, G. S. Avrunin, and L. A. Clarke. Using model checking with symbolic execution to verify parallel numerical programs. In International symposium on Software testing and analysis (ISSTA), pages 157--168. ACM Press, 2006.

Digital Library

[49]

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

[50]

S. D. Stoller. Testing concurrent Java programs using randomized scheduling. In Workshop on Runtime Verification (RV'02), volume 70 of ENTCS, 2002.

[51]

M. Vaziri, F. Tip, and J. Dolby. Associating synchronization constraints with data in an object-oriented language. In 33rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL), pages 334--345, 2006.

Digital Library

[52]

W. Visser, K. Havelund, G. Brat, and S. Park. Model checking programs. In 15th International Conference on Automated Software Engineering (ASE). IEEE, 2000.

Digital Library

[53]

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

Digital Library

[54]

Y. Yu, T. Rodeheffer, and W. Chen. Racetrack: efficient detection of data race conditions via adaptive tracking. SIGOPS Oper. Syst. Rev., 39(5):221--234, 2005.

Digital Library

Cited By

Ito HMatsubara YTakada H(2024)Race Directed Fuzzing for More Effective Concurrency TestingProceedings of the 2024 The 6th World Symposium on Software Engineering (WSSE)10.1145/3698062.3698063(1-6)Online publication date: 13-Sep-2024
https://dl.acm.org/doi/10.1145/3698062.3698063
Guo XQi XLi YWu C(2024)PredRacer: Predictively Detecting Data Races in Android Applications2024 IEEE International Conference on Software Analysis, Evolution and Reengineering (SANER)10.1109/SANER60148.2024.00031(239-249)Online publication date: 12-Mar-2024
https://doi.org/10.1109/SANER60148.2024.00031
Menard CLohstroh MBateni SChorlian MDeng ADonovan PFournier CLin SSuchert FTanneberger TKim HCastrillon JLee E(2023)High-performance Deterministic Concurrency Using Lingua FrancaACM Transactions on Architecture and Code Optimization10.1145/361768720:4(1-29)Online publication date: 26-Oct-2023
https://dl.acm.org/doi/10.1145/3617687
Show More Cited By

Index Terms

Race directed random testing of concurrent programs
1. General and reference
  1. Cross-computing tools and techniques
    1. Reliability
2. Software and its engineering
  1. Software creation and management
    1. Software verification and validation
      1. Software defect analysis
        Software testing and debugging
  2. Software organization and properties
    1. Extra-functional properties
      1. Software reliability

Recommendations

Race directed random testing of concurrent programs
PLDI '08: Proceedings of the 29th ACM SIGPLAN Conference on Programming Language Design and Implementation

Bugs in multi-threaded programs often arise due to data races. Numerous static and dynamic program analysis techniques have been proposed to detect data races. We propose a novel randomized dynamic analysis technique that utilizes potential data race ...
Randomized active atomicity violation detection in concurrent programs
SIGSOFT '08/FSE-16: Proceedings of the 16th ACM SIGSOFT International Symposium on Foundations of software engineering

Atomicity is an important specification that enables programmers to understand atomic blocks of code in a multi-threaded program as if they are sequential. This significantly simplifies the programmer's job to reason about correctness. Several modern ...
Sound predictive race detection in polynomial time
POPL '12: Proceedings of the 39th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages

Data races are among the most reliable indicators of programming errors in concurrent software. For at least two decades, Lamport's happens-before (HB) relation has served as the standard test for detecting races--other techniques, such as lockset-based ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 43, Issue 6

PLDI '08

June 2008

382 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/1379022

Issue’s Table of Contents

PLDI '08: Proceedings of the 29th ACM SIGPLAN Conference on Programming Language Design and Implementation
June 2008
396 pages
ISBN:9781595938602
DOI:10.1145/1375581
General Chair:
Rajiv Gupta
University of California, Riverside, USA
,
Program Chair:
Saman Amarasinghe
Massachusetts Institute of Technology, USA

Copyright © 2008 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: 07 June 2008

Published in SIGPLAN Volume 43, Issue 6

Check for updates

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

380
Total Citations
View Citations
2,121
Total Downloads

Downloads (Last 12 months)51
Downloads (Last 6 weeks)3

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ito HMatsubara YTakada H(2024)Race Directed Fuzzing for More Effective Concurrency TestingProceedings of the 2024 The 6th World Symposium on Software Engineering (WSSE)10.1145/3698062.3698063(1-6)Online publication date: 13-Sep-2024
https://dl.acm.org/doi/10.1145/3698062.3698063
Guo XQi XLi YWu C(2024)PredRacer: Predictively Detecting Data Races in Android Applications2024 IEEE International Conference on Software Analysis, Evolution and Reengineering (SANER)10.1109/SANER60148.2024.00031(239-249)Online publication date: 12-Mar-2024
https://doi.org/10.1109/SANER60148.2024.00031
Menard CLohstroh MBateni SChorlian MDeng ADonovan PFournier CLin SSuchert FTanneberger TKim HCastrillon JLee E(2023)High-performance Deterministic Concurrency Using Lingua FrancaACM Transactions on Architecture and Code Optimization10.1145/361768720:4(1-29)Online publication date: 26-Oct-2023
https://dl.acm.org/doi/10.1145/3617687
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
Deligiannis PSenthilnathan ANayyar FLovett CLal A(2023)Industrial-Strength Controlled Concurrency Testing for Programs with Tools and Algorithms for the Construction and Analysis of Systems10.1007/978-3-031-30820-8_26(433-452)Online publication date: 22-Apr-2023
https://dl.acm.org/doi/10.1007/978-3-031-30820-8_26
Ghosh RGhosh H(2023)Process to Process CommunicationDistributed Systems10.1002/9781119825968.ch3(37-62)Online publication date: 10-Feb-2023
https://doi.org/10.1002/9781119825968.ch3
Zhu XWen SCamtepe SXiang Y(2022)Fuzzing: A Survey for RoadmapACM Computing Surveys10.1145/351234554:11s(1-36)Online publication date: 9-Sep-2022
https://dl.acm.org/doi/10.1145/3512345
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://doi.org/10.1109/TSE.2020.2989171
Shen YPeng YChen JShi LDeng F(2022)Interruption-driven resource competition defect model and testing methodology2022 IEEE 6th Advanced Information Technology, Electronic and Automation Control Conference (IAEAC )10.1109/IAEAC54830.2022.9930087(602-616)Online publication date: 3-Oct-2022
https://doi.org/10.1109/IAEAC54830.2022.9930087
Neubaum AAl Sardy LSpisländer MSaglietti FKretschmer S(2022)A Guided Search for Races Based on Data Flow PatternsComputer Safety, Reliability, and Security. SAFECOMP 2022 Workshops10.1007/978-3-031-14862-0_10(47-58)Online publication date: 7-Sep-2022
https://doi.org/10.1007/978-3-031-14862-0_10
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