skip to main content
10.1145/2483760.2483765acmconferencesArticle/Chapter ViewAbstractPublication PagesisstaConference Proceedingsconference-collections
research-article

Practical static race detection for Java parallel loops

Published: 15 July 2013 Publication History

Abstract

Despite significant progress in recent years, the important problem of static race detection remains open. Previous techniques took a general approach and looked for races by analyzing the effects induced by low-level concurrency constructs (e.g., java.lang.Thread). But constructs and libraries for expressing parallelism at a higher level (e.g., fork-join, futures, parallel loops) are becoming available in all major programming languages.
We claim that specializing an analysis to take advantage of the extra semantic information provided by the use of these constructs and libraries improves precision and scalability.
We present IteRace, a set of techniques that are specialized to use the intrinsic thread, safety, and data-flow structure of collections and of the new loop-parallelism mechanism to be introduced in Java 8. Our evaluation shows that IteRace is fast and precise enough to be practical. It scales to programs of hundreds of thousands of lines of code and it reports few race warnings, thus avoiding a common pitfall of static analyses. The tool revealed six bugs in real-world applications. We reported four of them, one had already been fixed, and three were new and the developers confirmed and fixed them.

References

[1]
CIlib bug. https://github.com/cilib/cilib/issues/111.
[2]
Concurrency JSR-166 Interest Site - ParallelArray. http://gee.cs.oswego.edu/dl/concurrency-interest/.
[3]
JDK8. http://jdk8.java.net.
[4]
Microsoft TPL. http://msdn.microsoft.com/enus/library/dd460717.aspx.
[5]
State of the Lambda: Libraries Edition. http://cr.openjdk.java.net/ briangoetz/lambda/sotc3.html.
[6]
Threading Building Blocks. http://threadingbuildingblocks.org/.
[7]
WALA documentation. http://wala.sourceforge.net/.
[8]
M. Abadi, C. Flanagan, and S. N. Freund. Types for safe locking: Static race detection for java. TOPLAS, 28:207–255, March 2006.
[9]
S. V. Adve, M. D. Hill, B. P. Miller, and R. H. B. Netzer. Detecting data races on weak memory systems. SIGARCH Comput. Archit. News, 19:234–243, April 1991.
[10]
R. Agarwal and S. Stoller. Type inference for parameterized race-free Java. In B. Steffen and G. Levi, editors, VMCAI, volume 2937 of Lecture Notes in Computer Science, pages 77–108. Springer Berlin / Heidelberg, 2004.
[11]
E. Bengtson and D. Roth. Understanding the value of features for coreference resolution. In Proceedings of the Conference on Empirical Methods in Natural Language Processing, pages 294–303. Association for Computational Linguistics, 2008.
[12]
S. M. Blackburn, R. Garner, C. Hoffman, A. M. Khan, K. S. McKinley, R. Bentzur, A. Diwan, D. Feinberg, D. Frampton, S. Z. Guyer, M. Hirzel, A. Hosking, M. Jump, H. Lee, J. E. B. Moss, A. Phansalkar, D. Stefanovi´ c, T. VanDrunen, D. von Dincklage, and B. Wiedermann. The DaCapo benchmarks: Java benchmarking development and analysis. In Proceedings of the 21st ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, OOPSLA ’06, pages 169–190, New York, NY, USA, Oct. 2006. ACM Press.
[13]
E. Bodden and K. Havelund. Racer: effective race detection using AspectJ. In Proceedings of the 2008 international symposium on Software testing and analysis, ISSTA ’08, pages 155–166, New York, NY, USA, 2008. ACM.
[14]
C. Boyapati, R. Lee, and M. Rinard. Ownership types for safe programming: preventing data races and deadlocks. In Proceedings of the 17th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, OOPSLA ’02, pages 211–230, New York, NY, USA, 2002. ACM.
[15]
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 ’01, pages 56–69, New York, NY, USA, 2001. ACM.
[16]
J. M. Bull, L. A. Smith, M. D. Westhead, D. S. Henty, and R. A. Davey. A benchmark suite for high performance Java. In Java Grande, pages 81–88. ACM Press, 1999.
[17]
B. Cahoon and K. McKinley. Data flow analysis for software prefetching linked data structures in Java. In Parallel Architectures and Compilation Techniques, 2001. Proceedings. 2001 International Conference on, pages 280 –291, 2001.
[18]
F. Chen, T. F. ¸ Serbănu¸tă, and G. Ro¸su. jPredictor: a predictive runtime analysis tool for Java. In Proceedings of the 30th International Conference on Software Engineering, ICSE ’08, pages 221–230, New York, NY, USA, 2008. ACM.
[19]
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 Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, PLDI ’02, pages 258–269, New York, NY, USA, 2002. ACM.
[20]
J.-D. Choi, A. Loginov, and V. Sarkar. Static datarace analysis for multithreaded object-oriented programs. Technical report, IBM Research Division, Thomas J. Watson Research Centre, 2001.
[21]
J.-D. Choi, B. P. Miller, and R. H. B. Netzer. Techniques for debugging parallel programs with flowback analysis. TOPLAS, 13:491–530, October 1991.
[22]
M. Christiaens and K. De Bosschere. TRaDe, a topological approach to on-the-fly race detection in Java programs. In Proceedings of the 2001 Symposium on JavaTM Virtual Machine Research and Technology Symposium - Volume 1, JVM’01, pages 15–15, Berkeley, CA, USA, 2001. USENIX Association.
[23]
D. Dig, J. Marrero, and M. D. Ernst. Refactoring sequential java code for concurrency via concurrent libraries. In Proceedings of the 31st International Conference on Software Engineering, ICSE ’09, pages 397–407, Washington, DC, USA, 2009. IEEE Computer Society.
[24]
D. Dig, M. Tarce, C. Radoi, M. Minea, and R. Johnson. Relooper: refactoring for loop parallelism in Java. In Proceedings of the 24th ACM SIGPLAN conference companion on Object oriented programming systems languages and applications, OOPSLA ’09, pages 793–794, New York, NY, USA, 2009. ACM.
[25]
A. Dinning and E. Schonberg. An empirical comparison of monitoring algorithms for access anomaly detection. SIGPLAN Not., 25:1–10, February 1990.
[26]
D. Engler and K. Ashcraft. RacerX: effective, static detection of race conditions and deadlocks. SIGOPS Oper. Syst. Rev., 37:237–252, October 2003.
[27]
C. Flanagan and S. N. Freund. Type-based race detection for Java. In Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, PLDI ’00, pages 219–232, New York, NY, USA, 2000. ACM.
[28]
C. Flanagan and S. N. Freund. Detecting race conditions in large programs. In Proceedings of the 2001 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, PASTE ’01, pages 90–96, New York, NY, USA, 2001. ACM.
[29]
C. Flanagan and S. N. Freund. Type inference against races. Sci. Comput. Program., 64:140–165, January 2007.
[30]
C. Flanagan and S. N. Freund. FastTrack: efficient and precise dynamic race detection. In Proceedings of the 2009 ACM SIGPLAN conference on Programming language design and implementation, PLDI ’09, pages 121–133, New York, NY, USA, 2009. ACM.
[31]
D. Grossman. Type-safe multithreading in cyclone. In Proceedings of the 2003 ACM SIGPLAN international workshop on Types in languages design and implementation, TLDI ’03, pages 13–25, New York, NY, USA, 2003. ACM.
[32]
A. Gyori, D. Dig, L. Franklin, and J. Lahoda. Crossing the gap from imperative to functional programming through refactoring. In Proceedings of the 9th joint meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on the Foundations of Software Engineering, ESEC/FSE ’13, 2013.
[33]
M. Hall, E. Frank, G. Holmes, B. Pfahringer, P. Reutemann, and I. H. Witten. The WEKA data mining software: an update. SIGKDD Explor. Newsl., 11(1):10–18, Nov. 2009.
[34]
R. L. Halpert, C. J. F. Pickett, and C. Verbrugge. Component-based lock allocation. In Proceedings of the 16th International Conference on Parallel Architecture and Compilation Techniques, PACT ’07, pages 353–364, Washington, DC, USA, 2007. IEEE Computer Society.
[35]
T. A. Henzinger, R. Jhala, and R. Majumdar. Race checking by context inference. In Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, PLDI ’04, pages 1–13, New York, NY, USA, 2004. ACM.
[36]
M. Hind. Pointer analysis: haven’t we solved this problem yet? In Proceedings of the 2001 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, PASTE ’01, pages 54–61, New York, NY, USA, 2001. ACM.
[37]
R. Jhala and R. Majumdar. Interprocedural analysis of asynchronous programs. SIGPLAN Not., 42:339–350, January 2007.
[38]
V. Kahlon, N. Sinha, E. Kruus, and Y. Zhang. Static data race detection for concurrent programs with asynchronous calls. In Proceedings of the 7th joint meeting of the European software engineering conference and the ACM SIGSOFT symposium on The foundations of software engineering on European software engineering conference and foundations of software engineering symposium, ESEC/FSE ’09, pages 13–22, New York, NY, USA, 2009. ACM.
[39]
P. Liang, O. Tripp, M. Naik, and M. Sagiv. A dynamic evaluation of the precision of static heap abstractions. In Proceedings of the ACM international conference on Object oriented programming systems languages and applications, OOPSLA ’10, pages 411–427, New York, NY, USA, 2010. ACM.
[40]
D. Marino, M. Musuvathi, and S. Narayanasamy. LiteRace: effective sampling for lightweight data-race detection. In Proceedings of the 2009 ACM SIGPLAN conference on Programming language design and implementation, PLDI ’09, pages 134–143, New York, NY, USA, 2009. ACM.
[41]
J. Mellor-Crummey. On-the-fly detection of data races for programs with nested fork-join parallelism. In Proceedings of the 1991 ACM/IEEE conference on Supercomputing, ICS ’91, pages 24–33, New York, NY, USA, 1991. ACM.
[42]
A. Milanova, A. Rountev, and B. G. Ryder. Parameterized object sensitivity for points-to analysis for Java. ACM Trans. Softw. Eng. Methodol., 14:1–41, January 2005.
[43]
M. Naik and A. Aiken. Conditional must not aliasing for static race detection. In Proceedings of the 34th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, POPL ’07, pages 327–338, New York, NY, USA, 2007. ACM.
[44]
M. Naik, A. Aiken, and J. Whaley. Effective static race detection for Java. In Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, PLDI ’06, pages 308–319, New York, NY, USA, 2006. ACM.
[45]
M. Naik, P. Liang, and M. Sagiv. Static Thread-Escape Analysis vis Dynamic Heap Abstractions. from Naik’s website, 2010.
[46]
H. Nishiyama. Detecting data races using dynamic escape analysis based on read barrier. In VM, pages 10–10, Berkeley, CA, USA, 2004. USENIX Association.
[47]
R. O’Callahan and J. Choi. Hybrid dynamic data race detection. In Proceedings of the ninth ACM SIGPLAN symposium on Principles and practice of parallel programming, volume 38 of PPoPP ’03, pages 167–178. ACM, 2003.
[48]
S. Okur and D. Dig. How do developers use parallel libraries? In Proceedings of the ACM SIGSOFT 20th International Symposium on the Foundations of Software Engineering, ESEC/FSE ’12, pages 54–65, New York, NY, USA, 2012. ACM.
[49]
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.
[50]
P. Pratikakis, J. S. Foster, and M. Hicks. LOCKSMITH: context-sensitive correlation analysis for race detection. In Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, PLDI ’06, pages 320–331, New York, NY, USA, 2006. ACM.
[51]
P. Pratikakis, J. S. Foster, and M. Hicks. LOCKSMITH: Practical static race detection for C. ACM Trans. Program. Lang. Syst., 33:3:1–3:55, January 2011.
[52]
S. Qadeer and D. Wu. Kiss: keep it simple and sequential. In Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, PLDI ’04, pages 14–24, New York, NY, USA, 2004. ACM.
[53]
T. Reps, S. Horwitz, and M. Sagiv. Precise interprocedural dataflow analysis via graph reachability. In Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, POPL ’95, pages 49–61, New York, NY, USA, 1995. ACM.
[54]
M. Ronsse and K. De Bosschere. RecPlay: a fully integrated practical record/replay system. ACM Trans. Comput. Syst., 17:133–152, May 1999.
[55]
J. Rose, N. Swamy, and M. Hicks. Dynamic inference of polymorphic lock types. Science of Computer Programming, 58(3):366 – 383, 2005.
[56]
S. Savage, M. Burrows, G. Nelson, P. Sobalvarro, and T. Anderson. Eraser: a dynamic data race detector for multithreaded programs. ACM Trans. Comput. Syst., 15:391–411, November 1997.
[57]
D. Schonberg. On-the-fly detection of access anomalies. SIGPLAN Not., 24:285–297, June 1989.
[58]
M. Sharir and A. Pnueli. Two approaches to interprocedural data flow analysis. ACM Trans. Program. Lang. Syst., 1981.
[59]
T. Sheng, N. Vachharajani, S. Eranian, R. Hundt, W. Chen, and W. Zheng. RACEZ: a lightweight and non-invasive race detection tool for production applications. In Proceedings of the 33rd International Conference on Software Engineering, ICSE ’11, pages 401–410, New York, NY, USA, 2011. ACM.
[60]
Y. Smaragdakis, J. Evans, C. Sadowski, J. Yi, and C. Flanagan. Sound predictive race detection in polynomial time. In Proceedings of the 39th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, POPL ’12, pages 387–400, New York, NY, USA, 2012. ACM.
[61]
C. von Praun and T. R. Gross. Object race detection. In Proceedings of the 16th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, OOPSLA ’01, pages 70–82, New York, NY, USA, 2001. ACM.
[62]
C. von Praun and T. R. Gross. Static conflict analysis for multi-threaded object-oriented programs. In Proceedings of the ACM SIGPLAN 2003 Conference on Programming language design and implementation, PLDI ’03, pages 115–128, 2003.
[63]
J. W. Voung, R. Jhala, and S. Lerner. RELAY: static race detection on millions of lines of code. In Proceedings of the the 6th joint meeting of the European software engineering conference and the ACM SIGSOFT symposium on The foundations of software engineering, ESEC-FSE ’07, pages 205–214, New York, NY, USA, 2007. ACM.
[64]
Y. Yu, T. Rodeheffer, and W. Chen. RaceTrack: efficient detection of data race conditions via adaptive tracking. SIGOPS Oper. Syst. Rev., 39:221–234, October 2005.

Cited By

View all
  • (2023)Tolerate Control-Flow Changes for Sound Data Race PredictionProceedings of the 45th International Conference on Software Engineering10.1109/ICSE48619.2023.00118(1342-1354)Online publication date: 14-May-2023
  • (2023)Sound Predictive Fuzzing for Multi-threaded Programs2023 IEEE 47th Annual Computers, Software, and Applications Conference (COMPSAC)10.1109/COMPSAC57700.2023.00110(810-819)Online publication date: Jun-2023
  • (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
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
ISSTA 2013: Proceedings of the 2013 International Symposium on Software Testing and Analysis
July 2013
381 pages
ISBN:9781450321594
DOI:10.1145/2483760
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

In-Cooperation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 15 July 2013

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. Java
  2. Static race detection
  3. static analysis
  4. synchronization

Qualifiers

  • Research-article

Conference

ISSTA '13
Sponsor:

Acceptance Rates

Overall Acceptance Rate 58 of 213 submissions, 27%

Upcoming Conference

ISSTA '25

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)4
  • Downloads (Last 6 weeks)0
Reflects downloads up to 19 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2023)Tolerate Control-Flow Changes for Sound Data Race PredictionProceedings of the 45th International Conference on Software Engineering10.1109/ICSE48619.2023.00118(1342-1354)Online publication date: 14-May-2023
  • (2023)Sound Predictive Fuzzing for Multi-threaded Programs2023 IEEE 47th Annual Computers, Software, and Applications Conference (COMPSAC)10.1109/COMPSAC57700.2023.00110(810-819)Online publication date: Jun-2023
  • (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
  • (2021)Automatically detecting and fixing concurrency bugs in go software systemsProceedings of the 26th ACM International Conference on Architectural Support for Programming Languages and Operating Systems10.1145/3445814.3446756(616-629)Online publication date: 19-Apr-2021
  • (2019)Programmers do not favor lambda expressions for concurrent object-oriented codeEmpirical Software Engineering10.1007/s10664-018-9622-924:1(103-138)Online publication date: 1-Feb-2019
  • (2018)What happens-after the first race? enhancing the predictive power of happens-before based dynamic race detectionProceedings of the ACM on Programming Languages10.1145/32765152:OOPSLA(1-29)Online publication date: 24-Oct-2018
  • (2018)Debugging Multithreaded Programs as if They Were SequentialIEEE Access10.1109/ACCESS.2018.28356726(40024-40040)Online publication date: 2018
  • (2018)AdaptiveLock: Efficient Hybrid Data Race Detection Based on Real-World Locking PatternsInternational Journal of Parallel Programming10.1007/s10766-018-0579-547:5-6(805-837)Online publication date: 4-Jun-2018
  • (2017)Experimental Performance Comparison of Dynamic Data Race Detection TechniquesETRI Journal10.4218/etrij.17.0115.102739:1(124-134)Online publication date: 1-Feb-2017
  • (2017)Software Analysis Techniques for Detecting Data RaceIEICE Transactions on Information and Systems10.1587/transinf.2017EDR0004E100.D:11(2674-2682)Online publication date: 2017
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media