research-article

Effective and precise dynamic detection of hidden races for Java programs

Authors:

Lingwei CaoAuthors Info & Claims

ESEC/FSE 2015: Proceedings of the 2015 10th Joint Meeting on Foundations of Software Engineering

Pages 450 - 461

https://doi.org/10.1145/2786805.2786839

Published: 30 August 2015 Publication History

Abstract

Happens-before relation is widely used to detect data races dynami-cally. However, it could easily hide many data races as it is inter-leaving sensitive. Existing techniques based on randomized sched-uling are ineffective on detecting these hidden races. In this paper, we propose DrFinder, an effective and precise dynamic technique to detect hidden races. Given an execution, DrFinder firstly analyz-es the lock acquisitions in it and collects a set of "may-trigger" relations. Each may-trigger relation consists of a method and a type of a Java object. It indicates that, during execution, the method may directly or indirectly acquire a lock of the type. In the subsequent executions of the same program, DrFinder actively schedules the execution according to the set of collected may-trigger relations. It aims to reverse the set of happens-before relation that may exist in the previous executions so as to expose those hidden races. To effectively detect hidden races in each execution, DrFinder also collects a new set of may-trigger relation during its scheduling, which is used in its next scheduling. Our experiment on a suite of real-world Java multithreaded programs shows that DrFinder is effective to detect 89 new data races in 10 runs. Many of these races could not be detected by existing techniques (i.e., FastTrack, ConTest, and PCT) even in 100 runs.

References

[1]

GNU Classpath, version 0.98, https://www.gnu.org/software/classpath/.

[2]

Jikes RVM 3.1.3. http://jikesrvm.org/.

[3]

B. Alpern, C.R. Attanasio, A. Cocchi, D. Lieber, S. Smith, T. Ngo, J.J. Barton, S.F. Hummel, J.C. Sheperd, and M. Mergen. Implementing jalapeño in Java. In Proc. OOPSLA, 314– 324, 1999.

Digital Library

[4]

S. Bindal, S. Bansal, A. Lal. Variable and thread bounding for systematic testing of multithreaded programs. In Proc. ISSTA, 145–155, 2013.

Digital Library

[5]

M.D. Bond, K. E. Coons and K. S. Mckinley. PACER: Proportional detection of data races. In Proc. PLDI, 255–268, 2010.

Digital Library

[6]

S.M. Blackburn, R. Garner, C. Hoffmann, A.M. Khang, K.S. McKinley, R. Bentzur, A. Diwan, D. Feinberg, D. Frampton, S.Z. Guyer, M. Hirzel, A. Hosking, M. Jump, H. Lee, J. Eliot B. Moss, A. Phansalkar, D. Stefanović, T. VanDrunen, D. von Dincklage, and B. Wiedermann. The Dacapo benchmarks: Java benchmarking development and analysis. In Proc. OOPSLA, 169–190, 2006.

Digital Library

[7]

A. Bron, E. Farchi, Y. Magid, Y. Nir, and S. Ur. Applications of synchronization coverage. In Proc. PPoPP, 206–212, 2005.

Digital Library

[8]

S. Burckhardt, P. Kothari, M. Musuvathi, and S. Nagarakatte. A randomized scheduler with probabilistic guarantees of finding bugs. In Proc. ASPLOS, 167–178, 2010.

Digital Library

[9]

Y. Cai, and W.K. Chan. MagicFuzzer: scalable deadlock detection for large-scale applications. In Proc. ICSE, 606–616, 2012.

Digital Library

[10]

Y. Cai and W.K. Chan. Magiclock: scalable detection of potential deadlocks in large-scale multithreaded programs. IEEE Transactions on Software Engineering (TSE), 40(3), 266–281, 2014.

Digital Library

[11]

Y. Cai, C.J. Jia, S.R. Wu, K. Zhai, and W.K. Chan. ASN: a dynamic barrier-based approach to confirmation of deadlocks from warnings for large-scale multithreaded programs. IEEE Transactions on Parallel and Distributed Systems (TPDS), 26(1), 13–25, 2015.

[12]

Y. Cai, S.R. Wu, and W.K. Chan. ConLock: A constraintbased approach to dynamic checking on deadlocks in multithreaded programs. In Proc. ICSE, 491–502, 2014.

Digital Library

[13]

Y. Cai, K. Zhai, S.R. Wu, and W.K. Chan. TeamWork: synchronizing threads globally to detect real deadlocks for multithreaded programs. In Proc. PPoPP, 311 – 312, 2013.

Digital Library

[14]

E.M. Clarke, E.A. Emerson, and A.P. Sistla. Automatic verification of finite-state concurrent systems using temporal logic specifications. ACM Transactions on Programming Languages and Systems (TOPLAS), 8(2), 244–263, 1986.

Digital Library

[15]

O. Edelstein, E. Farchi, Y. Nir, G. Ratsaby, and S. Ur. Multithreaded java program test generation. In IBM Systems Journal, 111–125, 2002.

Digital Library

[16]

M. Eslamimehr and J. Palsberg. Race directed scheduling of concurrent programs. In Proc. PPoPP, 301–314, 2014.

Digital Library

[17]

C. Flanagan and S. N. Freund. FastTrack: efficient and precise dynamic race detection. In Proc. PLDI, 121–133, 2009.

Digital Library

[18]

C. Flanagan and S. N. Freund. The RoadRunner Dynamic analysis framework for concurrent programs. In Proc. PASTE, 1–8, 2010.

Digital Library

[19]

S. Hong, J. Ahn, S. Park, M. Kim, and M.J. Harrold. Testing concurrent programs to achieve high synchronization coverage. In Proc. ISSTA, 210–220, 2012.

Digital Library

[20]

J. Huang, P.O. Meredith, and G. Rosu. Maximal sound predictive race detection with control flow abstraction. In Proc. PLDI, 337–348, 2014.

Digital Library

[21]

P. Joshi, C.S. Park, K. Sen, amd M. Naik. A randomized dynamic program analysis technique for detecting real deadlocks. In Proc. PLDI, 110–120, 2009.

Digital Library

[22]

V. Kahlon, Y. Yang, S. Sankaranarayanan, and A. Gupta. Fast and accurate static data-race detection for concurrent programs. In Proc. CAV, 226–239, 2007.

Digital Library

[23]

B. Kasikci, C. Zamfir, and G. Candea. RaceMob: Crowdsourced data race detection. In Proc. SOSP, 406–422, 2013.

Digital Library

[24]

M. Kusano and C. Wang. Assertion guided abstraction: a cooperative optimization for dynamic partial order reduction. In Proc. ASE, 2014. To Appear.

Digital Library

[25]

L. Lamport. Time, clocks, and the ordering of events. Communications of the ACM 21(7):558–565, 1978.

Digital Library

[26]

Z. Letko, T. Vojnar, and B. Kˇrena. Coverage metrics for saturation-based and search-based testing of concurrent software. In Proc. RV, 177–192, 2011.

Digital Library

[27]

N.G. Leveson and C. S. Turner. An investigation of the Therac-25 accidents. Computer, 26(7), 18–41, 1993.

Digital Library

[28]

S. Lu, S. Park, E. Seo, and Y.Y. Zhou, Learning from mistakes: A comprehensive study on real world concurrency bug characteristics. In Proc. ASPLOS, 329–339, 2008.

Digital Library

[29]

D. Marino, M. Musuvathi, and S. Narayanasamy. LiteRace: effective sampling for lightweight data-race detection. In Proc. PLDI, 134–143, 2009.

Digital Library

[30]

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

Digital Library

[31]

W.N. Sumner and X. Zhang. Memory indexing: canonicalizing addresses across executions. In Proc. FSE, 217–226, 2010.

Digital Library

[32]

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

Digital Library

[33]

S. Nagarakatte, S. Burckhardt, M. M.K. Martin, and M. Musuvathi. Multicore acceleration of priority-based schedulers for concurrency bug detection. In Proc. PLDI, 2012, 543–554, 2012.

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 Proc. PLDI, 22–31, 2007.

Digital Library

[35]

E. Pozniansky and A. Schuster. Efficient on-the-fly data race detection in multithreaded C++ programs. In Proc. PPoPP, 179–190, 2003.

Digital Library

[36]

P. Pratikakis, J.S. Foster, and M. Hicks. LOCKSMITH: context-sensitive correlation analysis for race detection. In Proc. PLDI, 320–331, 2006.

Digital Library

[37]

C.S. Park, K. Sen, P. Hargrove, and C. Iancu. Efficient data race detection for distributed memory parallel programs. In Proc. SC, 2011.

Digital Library

[38]

K. Poulsen. Software bug contributed to blackout. http://www.securityfocus.com/news/8016, Feb. 2004

[39]

N. Rungta, E.G. Mercer, W. Visser. Efficient testing of concurrent programs with abstraction-guided symbolic execution. In Proc. SPIN, 174–191, 2009.

Digital Library

[40]

S. Savage, M. Burrows, G. Nelson, P. Sobalvarro and T. Anderson. Eraser: a dynamic data race detector for multithreaded programs. ACM TOCS, 15(4), 391–411, 1997.

Digital Library

[41]

K. Sen. Race Directed Random Testing of Concurrent Programs. In Proc. PLDI, 11–21, 2008.

Digital Library

[42]

K. Serebryany and T. Iskhodzhanov. ThreadSanitizer: data race detection in practice. In Proc. WBIA, 62–71, 2009.

Digital Library

[43]

Y. Smaragdakis, J. Evans, C. Sadowski, J. Yi, and C. Flanagan. Sound predictive race detection in polynomial time. In Proc. POPL, 387–400, 2012.

Digital Library

[44]

F. Sorrentino, A. Farzan, and P. Madhusudan. PENELOPE: weaving threads to expose atomicity violations. In Proc. FSE, 37–46, 2010.

Digital Library

[45]

K. Vineet and C. Wang. Universal causality graphs: a precise happens-before model for detecting bugs in concurrent programs. In Proc. CAV, 434–449, 2010.

Digital Library

[46]

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

Digital Library

[47]

C. Wang, K. Hoang. Precisely Deciding Control State Reachability in Concurrent Traces with Limited Observability. In Proc. VMCAI, 376–394, 2014.

[48]

C. Wang, M. Said, and A. Gupta. Coverage guided systematic concurrency testing. In Proc. ICSE, 221–230, 2011.

Digital Library

[49]

X.W. Xie and J.L. Xue. Acculock: Accurate and Efficient detection of data races. In Proc. CGO, 201–212, 2011.

Digital Library

[50]

J. Yu, S. Narayanasamy, C. Pereira, and G. Pokam. Maple: a coverage-driven testing tool for multithreaded programs. In Proc. OOPSLA, 485–502, 2012.

Digital Library

[51]

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

Digital Library

[52]

K. Zhai, B.N. Xu, W.K. Chan, and T.H. Tse. CARISMA: a context-sensitive approach to race-condition sample-instance selection for multithreaded applications. In Proc. ISSTA, 221–231, 2012.

Digital Library

[53]

H. Zhu. A formal analysis of the subsume relation between software test adequacy criteria. IEEE Transactions on Software Engineering (TSE), 22(4), 248–255, 1996.

Digital Library

Cited By

Chatterjee NMajumdar SDas PChakrabarti A(2023)ParallelC-Assist: Productivity Accelerator Suite Based on Dynamic InstrumentationIEEE Access10.1109/ACCESS.2023.329352511(73599-73612)Online publication date: 2023
https://doi.org/10.1109/ACCESS.2023.3293525
Yavuz T(2022)SIFT: A Tool for Property Directed Symbolic Execution of Multithreaded Software2022 IEEE Conference on Software Testing, Verification and Validation (ICST)10.1109/ICST53961.2022.00049(433-443)Online publication date: Apr-2022
https://doi.org/10.1109/ICST53961.2022.00049
Cai YYun HWang JQiao LPalsberg JSpinellis DGousios GChechik MDi Penta M(2021)Sound and efficient concurrency bug predictionProceedings of the 29th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3468264.3468549(255-267)Online publication date: 20-Aug-2021
https://dl.acm.org/doi/10.1145/3468264.3468549
Show More Cited By

Recommendations

Efficient noise injection for exposing hidden data races
Abstract
The happens-before (HB) relation is widely used to precisely detect data races, which are among the major causes of concurrency bugs. However, the HB relation is sensitive to thread interleaving; thus, hidden races that can be revealed in other ...
Accurate and efficient runtime detection of atomicity errors in concurrent programs
PPoPP '06: Proceedings of the eleventh ACM SIGPLAN symposium on Principles and practice of parallel programming

Atomicity is an important correctness condition for concurrent systems. Informally, atomicity is the property that every concurrent execution of a set of transactions is equivalent to some serial execution of the same transactions. In multi-threaded ...
Dynamic Data Race Detection in Java-Programs Using Synchronization Contracts
TMPA '13: Proceedings of the 2013 Tools & Methods of Program Analysis

Data race occurs in a multi-threaded program when several threads simultaneously access the same memory location and at least one of them is a write access. Data races can damage global data structures and it's hard to detect them manually, so research ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

ESEC/FSE 2015: Proceedings of the 2015 10th Joint Meeting on Foundations of Software Engineering

August 2015

1068 pages

ISBN:9781450336758

DOI:10.1145/2786805

General Chair:
Elisabetta Di Nitto
Politecnico di Milano, Italy
,
Program Chairs:
Mark Harman
University College London, UK
,
Patrick Heymans
University of Namur, Belgium

Copyright © 2015 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 the author(s) 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

SIGSOFT: ACM Special Interest Group on Software Engineering

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 30 August 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

National Natural Science Foundation of China

Conference

ESEC/FSE'15

Sponsor:

SIGSOFT

ESEC/FSE'15: Joint Meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on the Foundations of Software Engineering

August 30 - September 4, 2015

Bergamo, Italy

Acceptance Rates

Overall Acceptance Rate 112 of 543 submissions, 21%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

31
Total Citations
View Citations
398
Total Downloads

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

Reflects downloads up to 19 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Chatterjee NMajumdar SDas PChakrabarti A(2023)ParallelC-Assist: Productivity Accelerator Suite Based on Dynamic InstrumentationIEEE Access10.1109/ACCESS.2023.329352511(73599-73612)Online publication date: 2023
https://doi.org/10.1109/ACCESS.2023.3293525
Yavuz T(2022)SIFT: A Tool for Property Directed Symbolic Execution of Multithreaded Software2022 IEEE Conference on Software Testing, Verification and Validation (ICST)10.1109/ICST53961.2022.00049(433-443)Online publication date: Apr-2022
https://doi.org/10.1109/ICST53961.2022.00049
Cai YYun HWang JQiao LPalsberg JSpinellis DGousios GChechik MDi Penta M(2021)Sound and efficient concurrency bug predictionProceedings of the 29th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3468264.3468549(255-267)Online publication date: 20-Aug-2021
https://dl.acm.org/doi/10.1145/3468264.3468549
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
Terragni VPezzè M(2021)Statically driven generation of concurrent tests for thread‐safe classesSoftware Testing, Verification and Reliability10.1002/stvr.177431:4Online publication date: 4-May-2021
https://doi.org/10.1002/stvr.1774
Genç KRoemer JXu YBond M(2019)Dependence-aware, unbounded sound predictive race detectionProceedings of the ACM on Programming Languages10.1145/33606053:OOPSLA(1-30)Online publication date: 10-Oct-2019
https://dl.acm.org/doi/10.1145/3360605
Cai YZhu BMeng RYun HHe LSu PLiang BDumas MPfahl DApel SRusso A(2019)Detecting concurrency memory corruption vulnerabilitiesProceedings of the 2019 27th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3338906.3338927(706-717)Online publication date: 12-Aug-2019
https://dl.acm.org/doi/10.1145/3338906.3338927
Qi XZhou H(2019)A Splitting Strategy for Testing Concurrent Programs2019 IEEE 26th International Conference on Software Analysis, Evolution and Reengineering (SANER)10.1109/SANER.2019.8668040(388-398)Online publication date: Feb-2019
https://doi.org/10.1109/SANER.2019.8668040
Majumdar SPapdeja SDas PGhosh S(2019)SMARTKT: A Search Framework to Assist Program Comprehension using Smart Knowledge Transfer2019 IEEE 19th International Conference on Software Quality, Reliability and Security (QRS)10.1109/QRS.2019.00026(97-108)Online publication date: Jul-2019
https://doi.org/10.1109/QRS.2019.00026
Sun YCheung SGuo SCheng M(2019)Disclosing and Locating Concurrency Bugs of Interrupt-Driven IoT ProgramsIEEE Internet of Things Journal10.1109/JIOT.2019.29252916:5(8945-8957)Online publication date: Oct-2019
https://doi.org/10.1109/JIOT.2019.2925291
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