research-article

Race directed random testing of concurrent programs

Author:

Koushik SenAuthors Info & Claims

PLDI '08: Proceedings of the 29th ACM SIGPLAN Conference on Programming Language Design and Implementation

Pages 11 - 21

https://doi.org/10.1145/1375581.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

Ragab HMambretti AKurmus AGiuffrida CBalzarotti DXu W(2024)GhostRaceProceedings of the 33rd USENIX Conference on Security Symposium10.5555/3698900.3699246(6185-6202)Online publication date: 14-Aug-2024
https://dl.acm.org/doi/10.5555/3698900.3699246
Borgarelli AEnea CMajumdar RNagendra S(2024)Reward Augmentation in Reinforcement Learning for Testing Distributed SystemsProceedings of the ACM on Programming Languages10.1145/36897798:OOPSLA2(1928-1954)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689779
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
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

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

Information & Contributors

Information

Published In

cover image ACM Conferences

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

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

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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 June 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

PLDI '08

Sponsor:

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

June 7 - 13, 2008

AZ, Tucson, USA

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

381
Total Citations
View Citations
2,132
Total Downloads

Downloads (Last 12 months)44
Downloads (Last 6 weeks)6

Reflects downloads up to 08 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Ragab HMambretti AKurmus AGiuffrida CBalzarotti DXu W(2024)GhostRaceProceedings of the 33rd USENIX Conference on Security Symposium10.5555/3698900.3699246(6185-6202)Online publication date: 14-Aug-2024
https://dl.acm.org/doi/10.5555/3698900.3699246
Borgarelli AEnea CMajumdar RNagendra S(2024)Reward Augmentation in Reinforcement Learning for Testing Distributed SystemsProceedings of the ACM on Programming Languages10.1145/36897798:OOPSLA2(1928-1954)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689779
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
Wolff DShi ZDuck GMathur URoychoudhury ATsafrir DMusuvathi MGupta RAbu-Ghazaleh N(2024)Greybox Fuzzing for Concurrency TestingProceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 210.1145/3620665.3640389(482-498)Online publication date: 27-Apr-2024
https://dl.acm.org/doi/10.1145/3620665.3640389
Guo YZhu SCai YHe LZhang JRoychoudhury APaiva AAbreu RStorey M(2024)Reorder Pointer Flow in Sound Concurrency Bug PredictionProceedings of the IEEE/ACM 46th International Conference on Software Engineering10.1145/3597503.3623300(1-13)Online publication date: 20-May-2024
https://dl.acm.org/doi/10.1145/3597503.3623300
Gerlits E(2024)RaceHunter Dynamic Data Race DetectorProgramming and Computer Software10.1134/S036176882470033650:6(467-481)Online publication date: 19-Nov-2024
https://doi.org/10.1134/S0361768824700336
Cai YYao PYe CZhang CCalandrino JTroncoso C(2023)Place your locks wellProceedings of the 32nd USENIX Conference on Security Symposium10.5555/3620237.3620446(3727-3744)Online publication date: 9-Aug-2023
https://dl.acm.org/doi/10.5555/3620237.3620446
Yuan MZhao BLi PLiang JHan XLuo XZhang CCalandrino JTroncoso C(2023)DDRaceProceedings of the 32nd USENIX Conference on Security Symposium10.5555/3620237.3620397(2849-2866)Online publication date: 9-Aug-2023
https://dl.acm.org/doi/10.5555/3620237.3620397
Sun CDai HGeng NLiu HChen TWu PCai YWang J(2023)An Interleaving Guided Metamorphic Testing Approach for Concurrent ProgramsACM Transactions on Software Engineering and Methodology10.1145/360718233:1(1-21)Online publication date: 23-Nov-2023
https://dl.acm.org/doi/10.1145/3607182
Liang JYuan MDing ZMa SHan XZhang C(2023)RaceBench: A Triggerable and Observable Concurrency Bug BenchmarkProceedings of the 2023 ACM Asia Conference on Computer and Communications Security10.1145/3579856.3595787(415-428)Online publication date: 10-Jul-2023
https://dl.acm.org/doi/10.1145/3579856.3595787
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 Table of Conten