Cosmin Radoi
Danny Dig
Skip Abstract Section
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 dataflow structure of collections and of the new loop parallelism mechanism 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 reports very few race warnings, thus avoiding a common pitfall of static analyses. In five out of the seven case studies, IteRace reported no false warnings. Also, it 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.
Furthermore, we evaluate the effect of each specialization technique on the running time and precision of the analysis. For each application, we run the analysis under 32 different configurations. This allows to analyze each technique's effect both alone and in all possible combinations with other techniques.
- Martin Abadi, Cormac Flanagan, and Stephen N. Freund. 2006. Types for safe locking: Static race detection for Java. ACM Trans. Program. Lang. Syst. 28, 2, 207--255. Google Scholar
Digital Library
- Sarita V. Adve, Mark D. Hill, Barton P. Miller, and Robert H. B. Netzer. 1991. Detecting data races on weak memory systems. SIGARCH Comput. Archit. News 19, 3, 234--243. Google ScholarDigital Library
- Rahul Agarwal and Scott Stoller. 2004. Type inference for parameterized race-free Java. In Proceedings of the 5th International Conference on Verification, Model Checking, and Abstract Interpretation (VMCAI'04). 149--160.Google ScholarCross Ref
- Vamshi Basupalli, Tomofumi Yuki, Sanjay Rajopadhye, Antoine Morvan, Steven Derrien, Patrice Quinton, and David Wonnacott. 2011. ompVerify: Polyhedral analysis for the OpenMP programmer. In Proceedings of the 7th International Conference on OpenMP in the Petascale Era (IWOMP'11). Springer, 37--53. Google ScholarDigital Library
- Eric Bengtson and Dan Roth. 2008. Understanding the value of features for coreference resolution. In Proceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP'08). Association for Computational Linguistics, 294--303. Google ScholarDigital Library
- Stephen M. Blackburn, Robin Garner, Chris Hoffman, Asjad M. Khan, Kathryn S. Mckinley, et al. 2006. The DaCapo Java benchmarking development and analysis. In Proceedings of the 21st ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA'06). ACM Press, New York, 169--190. Google ScholarDigital Library
- Eric Bodden and Klaus Havelund. 2008. Racer: Effective race detection using AspectJ. In Proceedings of the International Symposium on Software Testing and Analysis (ISSTA'08). ACM Press, New York, 155--166. Google ScholarDigital Library
- Chandrasekhar Boyapati, Robert Lee, and Martin Rinard. 2002. 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). ACM Press, New York, 211--230. Google ScholarDigital Library
- Chandrasekhar Boyapati and Martin Rinard. 2001. 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). ACM Press, New York, 56--69. Google ScholarDigital Library
- J. Mark Bull, Lorna A. Smith, Martin D. Westhead, David S. Henty, and Robert A. Davey. 1999. A benchmark suite for high performance Java. In Proceedings of the ACM Java Grande Conference (JAVA'99). ACM Press, New York, 81--88.Google Scholar
- Brendon Cahoon and Kathryn S. Mckinley. 2001. Data flow analysis for software prefetching linked data structures in Java. In Proceedings of the International Conference on Parallel Architectures and Compilation Techniques (PACT'01). 280--291. Google ScholarDigital Library
- Feng Chen, Traian Florin Serbanuta, and Grigore Rosu. 2008. jPredictor: A predictive runtime analysis tool for Java. In Proceedings of the 30th International Conference on Software Engineering (ICSE'08). ACM Press, New York, 221--230. Google ScholarDigital Library
- Jong-Deok Choi, Keunwoo Lee, Alexey Loginov, Robert O'Callahan, Vivek Sarkar, and Manu Sridharan. 2002. Efficient and precise datarace detection for multithreaded object-oriented programs. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI'02). ACM Press, New York, 258--269. Google ScholarDigital Library
- Jong-Deok Choi, Alexey Loginov, and Vivek Sarkar. 2001. Static datarace analysis for multithreaded object-oriented programs. Tech. rep. 22146, IBM Research Division, Thomas J. Watson Research Centre.Google Scholar
- Jong-Deok Choi, Barton P. Miller, and Robert H. B. Netzer. 1991. Techniques for debugging parallel programs with flowback analysis. ACM Trans. Program. Lang. Syst. 13, 4, 491--530. Google ScholarDigital Library
- Mark Christiaens and Koen De Bosschere. 2001. TRaDe, A topological approach to on-the-fly race detection in Java programs. In Proceedings of the Symposium on Java Virtual Machine Research and Technology (JVM'01). USENIX Association, 15. Google ScholarDigital Library
- CILIB. 2015. CIlib bug. https://github.com/CIlib/CIlib/issues/111.Google Scholar
- Danny Dig, John Marrero, and Michael D. Ernst. 2009a. Refactoring sequential Java code for concurrency via concurrent libraries. In Proceedings of the 31st International Conference on Software Engineering (ICSE'09). IEEE Computer Society, 397--407. Google ScholarDigital Library
- Danny Dig, Mihai Tarce, Cosmin Radoi, Marius Minea, and Ralph Johnson. 2009b. 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). ACM Press, New York, 793--794. Google ScholarDigital Library
- Anne Dinning and Edith Schonberg. 1990. An empirical comparison of monitoring algorithms for access anomaly detection. ACM SIGPLAN Not. 25, 3, 1--10. Google ScholarDigital Library
- Dawson Engler and Ken Ashcraft. 2003. RacerX: Effective, static detection of race conditions and deadlocks. SIGOPS Oper. Syst. Rev. 37, 5, 237--252. Google ScholarDigital Library
- Paul Feautrier. 1991. Dataflow analysis of array and scalar references. Int. J. Parallel Program. 20, 1, 23--53.Google ScholarCross Ref
- Cormac Flanagan and Stephen N. Freund. 2000. Type-based race detection for Java. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI'00). ACM Press, New York, 219--232. Google ScholarDigital Library
- Cormac Flanagan and Stephen N. Freund. 2001. Detecting race conditions in large programs. In Proceedings of the ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering (PASTE'01). ACM Press, New York, 90--96. Google ScholarDigital Library
- Cormac Flanagan and Stephen N. Freund. 2007. Type inference against races. Sci. Comput. Program. 64, 1, 140--165. Google ScholarDigital Library
- Cormac Flanagan and Stephen N. Freund. 2009. FastTrack: Efficient and precise dynamic race detection. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI'09). ACM Press, New York, 121--133. Google ScholarDigital Library
- Dan Grossman. 2003. Type-safe multithreading in cyclone. In Proceedings of the ACM SIGPLAN International Workshop on Types in Languages Design and Implementation (TLDI'03). ACM Press, New York, 13--25. Google ScholarDigital Library
- Alex Gyori, Lyle Franklin, Danny Dig, and Jan Lahoda. 2013. Crossing the gap from imperative to functional programming through refactoring. In Proceedings of the 9th Joint Meeting on Foundations of Software Engineering (ESEC/FSE'13). ACM Press, New York, 543--553. Google ScholarDigital Library
- Mark Hall, Eibe Frank, Geoffrey Holmes, Bernhard Pfahringer, Peter Reutemann, and Ian H. Witten. 2009. The WEKA data mining software: An update. ACM SIGKDD Explor. Newslett. 11, 1, 10--18. Google ScholarDigital Library
- Richard L. Halpert, Christopher J. F. Pickett, and Clark Verbrugge. 2007. Component-based lock allocation. In Proceedings of the 16th International Conference on Parallel Architecture and Compilation Techniques (PACT'07). IEEE Computer Society, 353--364. Google ScholarDigital Library
- Thomas A. Henzinger, Ranjit Jhala, and Rupak Majumdar. 2004. Race checking by context inference. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI'04). ACM Press, New York, 1--13. Google ScholarDigital Library
- Michael Hind. 2001. Pointer analysis: Haven't we solved this problem yet? In Proceedings of the ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering (PASTE'01). ACM Press, New York, 54--61. Google ScholarDigital Library
- JDK. 2015. JDK8. http://jdk8.java.net.Google Scholar
- Ranjit Jhala and Rupak Majumdar. 2007. Interprocedural analysis of asynchronous programs. ACM SIGPLAN Not. 42, 1, 339--350. Google ScholarDigital Library
- Vineet Kahlon, Nishant Sinha, Erik Kruus, and Yun Zhang. 2009. 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 (ESEC/FSE'09). ACM Press, New York, 13--22. Google ScholarDigital Library
- LAMBDA. 2015. State of the lambda: Libraries edition. http://openjdk.java.net/projects/lambda/.Google Scholar
- Percy Liang, Omer Tripp, Mayur Naik, and Mooly Sagiv. 2010. 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). ACM Press, New York, 411--427. Google ScholarDigital Library
- Yu Lin and Danny Dig. 2013. CHECK-THEN-ACT misuse of Java concurrent collections. In Proceedings of the 6th IEEE International Conference on Software Testing, Verification, and Validation (ICST'13). IEEE Computer Society, 164--173. Google ScholarDigital Library
- Daniel Marino, Madanlal Musuvathi, and Satish Narayanasamy. 2009. LiteRace: Effective sampling for lightweight data-race detection. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI'09). ACM Press, New York, 134--143. Google ScholarDigital Library
- John Mellor-Crummey. 1991. On-the-fly detection of data races for programs with nested fork-join parallelism. In Proceedings of the ACM/IEEE Conference on Supercomputing (ICS'91). ACM Press, New York, 24--33. Google ScholarDigital Library
- Ana Milanova, Atanas Rountev, and Barbara G. Ryder. 2005. Parameterized object sensitivity for points-to analysis for Java. ACM Trans. Softw. Engin. Methodol. 14, 1, 1--41. Google ScholarDigital Library
- Mayur Naik and Alex Aiken. 2007. 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). ACM Press, New York, 327--338. Google ScholarDigital Library
- Mayur Naik, Alex Aiken, and John Whaley. 2006. Effective static race detection for Java. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI'06). ACM Press, New York, 308--319. Google ScholarDigital Library
- Mayur Naik, Percy Liang, and Mooly Sagiv. 2010. Static thread-escape analysis vis dynamic heap abstractions. http://pag.gatech.edu/naik/.Google Scholar
- Hiroyasu Nishiyama. 2004. Detecting data races using dynamic escape analysis based on read barrier. In Proceedings of the 3rd Conference on Virtual Machine Research and Technology Symposium (VM'04). USENIX Association, 10. Google ScholarDigital Library
- Robert O'callahan and Jong-Deok Choi. 2003. Hybrid dynamic data race detection. In Proceedings of the 9th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP'03). Vol. 38. ACM Press, New York, 167--178. Google ScholarDigital Library
- Semih Okur and Danny Dig. 2012. How do developers use parallel libraries? In Proceedings of the 20th ACM SIGSOFT International Symposium on the Foundations of Software Engineering (FSE'12). Google ScholarDigital Library
- Parallelarray. 2015. Concurrency JSR-166 interest site - ParallelArray. http://g.oswego.edu/dl/concurrency-interest/.Google Scholar
- Eli Pozniansky and Assaf Schuster. 2007. MultiRace: Efficient on-the-fly data race detection in multi-threaded C++ programs. Concurr. Comput. Pract. Exper. 19, 3, 327--340. Google ScholarDigital Library
- Polyvios Pratikakis, Jeffrey S. Foster, and Michael Hicks. 2006. LOCKSMITH: Context-sensitive correlation analysis for race detection. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI'06). ACM Press, New York, 320--331. Google ScholarDigital Library
- Polyvios Pratikakis, Jeffrey S. Foster, and Michael Hicks. 2011. LOCKSMITH: Practical static race detection for C. ACM Trans. Program. Lang. Syst. 33, 1. Google ScholarDigital Library
- Shaz Qadeer and Dinghao Wu. 2004. KISS: Keep it simple and sequential. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI'04). ACM Press, New York, 14--24. Google ScholarDigital Library
- Yao Qi, Raja Das, Zhi Da Luo, and Martin Trotter. 2009. Multicoresdk: A practical and efficient data race detector for real-world applications. In Proceedings of the 7th Workshop on Parallel and Distributed Systems: Testing, Analysis, and Debugging (PADTAD'09). Google ScholarDigital Library
- Cosmin Radoi and Danny Dig. 2013. Practical static race detection for Java parallel loops. In Proceedings of the International Symposium on Software Testing and Analysis (ISSTA'13). ACM Press, New York, 178--190. Google ScholarDigital Library
- Raghavan Raman, Jisheng Zhao, Vivek Sarkar, Martin Vechev, and Eran Yahav. 2010. Efficient data race detection for async-finish parallelism. In Proceedings of the 1st International Conference on Runtime Verification (RV'10). Springer, 368--383. Google ScholarDigital Library
- Raghavan Raman, Jisheng Zhao, Vivek Sarkar, Martin Vechev, and Eran Yahav. 2012. Scalable and precise dynamic datarace detection for structured parallelism. In Proceedings of the 33rd ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI'12). ACM Press, New York, 531--542. Google ScholarDigital Library
- Thomas Reps, Susan Horwitz, and Mooly Sagiv. 1995. Precise interprocedural dataflow analysis via graph reachability. In Proceedings of the 22nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL'95). ACM Press, New York, 49--61. Google ScholarDigital Library
- Michiel Ronsse and Koen De Bosschere. 1999. RecPlay: A fully integrated practical record/replay system. ACM Trans. Comput. Syst. 17, 2, 133--152. Google ScholarDigital Library
- James Rose, Nikhil Swamy, and Michael Hicks. 2005. Dynamic inference of polymorphic lock types. Sci. Comput. Program. 58, 3, 366--383. Google ScholarDigital Library
- Stefan Savage, Michael Burrows, Greg Nelson, Patrick Sobalvarro, and Thomas Anderson. 1997. Eraser: A dynamic data race detector for multithreaded programs. ACM Trans. Comput. Syst. 15, 4, 391--411. Google ScholarDigital Library
- D. Schonberg. 1989. On-the-fly detection of access anomalies. ACM SIGPLAN Not. 24, 7, 285--297. Google ScholarDigital Library
- Micha Sharir and Amir Pnueli. 1981. Two approaches to interprocedural data flow analysis. In Program Flow Analysis: Theory and Applications. Prentice-Hall, 189--233.Google Scholar
- Tianwei Sheng, Neil Vachharajani, Stephane Eranian, Robert Hundt, Wenguang Chen, and Weimin Zheng. 2011. RACEZ: A lightweight and non-invasive race detection tool for production applications. In Proceedings of the 33rd International Conference on Software Engineering (ICSE'11). ACM Press, New York, 401--410. Google ScholarDigital Library
- Yannis Smaragdakis, Jacob Evans, Caitlin Sadowski, Jaeheon Yi, and Cormac Flanagan. 2012. Sound predictive race detection in polynomial time. In Proceedings of the 39th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL'12). ACM Press, New York, 387--400. Google ScholarDigital Library
- TBB. 2015. Threading building blocks. http://threadingbuildingblocks.org/.Google Scholar
- Weslley Torres, Gustavo Pinto, Benito Fernandes, Joao Paulo Oliveira, Filipe Alencar Ximenes, and Fernando Castor. 2011. Are Java programmers transitioning to multicore? A large scale study of Java FLOSS. In Proceedings of the Compilation of the Co-located Workshops on DSM'11, TMC'11, AGERE!'11, AOOPES'11, NEAT'11, and VMIL'11 (SPLASH'11Workshops). ACM Press, New York, 123--128. Google ScholarDigital Library
- TPL. 2015. Microsoft TPL. http://msdn.microsoft.com/en-us/library/dd460717.aspx.Google Scholar
- Christoph Von Praun and Thomas R. Gross. 2001. Object race detection. In Proceedings of the 16th ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA'01). ACM Press, New York, 70--82. Google ScholarDigital Library
- Christoph Von Praun and Thomas R. Gross. 2003. Static conflict analysis for multi-threaded object-oriented programs. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI'03). 115--128. Google ScholarDigital Library
- Jan Wen Voung, Ranjit Jhala, and Sorin Lerner. 2007. RELAY: Static race detection on millions of lines of code. In Proceedings of the 6th Joint Meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on the Foundations of Software Engineering (ESEC/FSE'07). ACM Press, New York, 205--214. Google ScholarDigital Library
- WALA. 2015. WALA documentation. http://wala.sourceforge.net/.Google Scholar
- Yourkit. 2015. YourKit Java profiler. http://www.yourkit.com.Google Scholar
- Yuan Yu, Tom Rodeheffer, and Wei Chen. 2005. RaceTrack: Efficient detection of data race conditions via adaptive tracking. ACM SIGOPS Oper. Syst. Rev. 39, 5, 221--234. Google ScholarDigital Library
- Tomofumi Yuki, Paul Feautrier, Sanjay Rajopadhye, and Vijay Saraswat. 2013. Array dataflow analysis for polyhedral X10 programs. In Proceedings of the 18th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP'13). ACM Press, New York, 23--34. Google ScholarDigital Library
Index Terms
- Effective Techniques for Static Race Detection in Java Parallel Loops
Recommendations
Practical static race detection for Java parallel loops
ISSTA 2013: Proceedings of the 2013 International Symposium on Software Testing and AnalysisDespite 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., ...
Effective static race detection for Java
PLDI '06: Proceedings of the 27th ACM SIGPLAN Conference on Programming Language Design and ImplementationWe present a novel technique for static race detection in Java programs, comprised of a series of stages that employ a combination of static analyses to successively reduce the pairs of memory accesses potentially involved in a race. We have implemented ...
Effective static race detection for Java
Proceedings of the 2006 PLDI ConferenceWe present a novel technique for static race detection in Java programs, comprised of a series of stages that employ a combination of static analyses to successively reduce the pairs of memory accesses potentially involved in a race. We have implemented ...
Comments