FastTrack: efficient and precise dynamic race detection

ABSTRACT

\begin{abstract}

Multithreaded programs are notoriously prone to race conditions. Prior work on dynamic race detectors includes fast but imprecise race detectors that report false alarms, as well as slow but precise race detectors that never report false alarms. The latter typically use expensive vector clock operations that require time linear in the number of program threads.

This paper exploits the insight that the full generality of vector clocks is unnecessary in most cases. That is, we can replace heavyweight vector clocks with an adaptive lightweight representation that, for almost all operations of the target program, requires only constant space and supports constant-time operations. This representation change significantly improves time and space performance, with no loss in precision.

Experimental results on Java benchmarks including the Eclipse development environment show that our FastTrack race detector is an order of magnitude faster than a traditional vector-clock race detector, and roughly twice as fast as the high-performance DJIT+ algorithm. FastTrack is even comparable in speed to Eraser on our Java benchmarks, while never reporting false alarms.

REFERENCES

• 1: Martin Abadi , Cormac Flanagan , Stephen N. Freund, Types for safe locking: Static race detection for Java, ACM Transactions on Programming Languages and Systems (TOPLAS), v.28 n.2, p.207-255, March 2006 [doi>10.1145/1119479.1119480]
• 2: Sarita V. Adve , Mark D. Hill , Barton P. Miller , Robert H. B. Netzer, Detecting data races on weak memory systems, Proceedings of the 18th annual international symposium on Computer architecture, p.234-243, May 27-30, 1991, Toronto, Ontario, Canada
• 3: R. Agarwal and S. D. Stoller. Type inference for parameterized race-free Java. In VMCAI, pages 149--160, 2004.
• 4: Alexander Aiken , David Gay, Barrier inference, Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.342-354, January 19-21, 1998, San Diego, California, United States [doi>10.1145/268946.268974]
• 5: Chandrasekhar Boyapati , Martin Rinard, A parameterized type system for race-free Java programs, Proceedings of the 16th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.56-69, October 14-18, 2001, Tampa Bay, FL, USA
• 6: CERN. Colt 1.2.0. Available at http://dsd.lbl.gov/~hoschek/colt/, 2007.
• 7: A. T. Chamillard , L. A. Clarke , G. S. Avrunin, Experimental Design for Comparing Static Concurrency Analysis, University of Massachusetts, Amherst, MA, 1996
• 8: Jong-Deok Choi , Keunwoo Lee , Alexey Loginov , Robert O'Callahan , Vivek Sarkar , Manu Sridharan, Efficient and precise datarace detection for multithreaded object-oriented programs, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 9: Jong-Deok Choi , Barton P. Miller , Robert H. B. Netzer, Techniques for debugging parallel programs with flowback analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.4, p.491-530, Oct. 1991 [doi>10.1145/115372.115324]
• 10: Mark Christiaens , Koenraad De Bosschere, Accordion Clocks: Logical Clocks for Data Race Detection, Proceedings of the 7th International Euro-Par Conference Manchester on Parallel Processing, p.494-503, August 28-31, 2001
• 11: Mark Christiaens , Koenraad De Bosschere, TRaDe: Data Race Detection for Java, Proceedings of the International Conference on Computational Science-Part II, p.761-770, May 28-30, 2001
• 12: Matthew B. Dwyer , Lori A. Clarke, Data Flow Analysis for Verifying Properties of Concurrent Programs, University of Massachusetts, Amherst, MA, 1994
• 13: The Eclipse programming environment, version 3.4.0. Available at \texttthttp://www.eclipse.org, 2009.
• 14: Tayfun Elmas , Shaz Qadeer , Serdar Tasiran, Goldilocks: a race and transaction-aware java runtime, Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation, June 10-13, 2007, San Diego, California, USA
• 15: Dawson Engler , Ken Ashcraft, RacerX: effective, static detection of race conditions and deadlocks, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 16: Cormac Flanagan , Stephen N. Freund, Atomizer: A dynamic atomicity checker for multithreaded programs, Science of Computer Programming, v.71 n.2, p.89-109, April, 2008 [doi>10.1016/j.scico.2007.12.001]
• 17: Cormac Flanagan , Stephen N. Freund , Jaeheon Yi, Velodrome: a sound and complete dynamic atomicity checker for multithreaded programs, Proceedings of the 2008 ACM SIGPLAN conference on Programming language design and implementation, June 07-13, 2008, Tucson, AZ, USA
• 18: E. Fleury and G. Sutre. Raja, version 0.4.0-pre4. Available at http://raja.sourceforge.net/, 2007.
• 19: Dan Grossman, Type-safe multithreading in cyclone, Proceedings of the 2003 ACM SIGPLAN international workshop on Types in languages design and implementation, January 18-18, 2003, New Orleans, Louisiana, USA
• 20: Java Grande Forum. Java Grande benchmark suite. Available at http://www.javagrande.org/, 2008.
• 21: Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
• 22: Jeremy Manson , William Pugh , Sarita V. Adve, The Java memory model, Proceedings of the 32nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.378-391, January 12-14, 2005, Long Beach, California, USA
• 23: F. Mattern. Virtual time and global states of distributed systems. In Workshop on Parallel and Distributed Algorithms, 1988.
• 24: John Mellor-Crummey, On-the-fly detection of data races for programs with nested fork-join parallelism, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.24-33, November 18-22, 1991, Albuquerque, New Mexico, United States [doi>10.1145/125826.125861]
• 25: M. Musuvathi, S. Qadeer, T. Ball, G. Basler, P. A. Nainar, and I. Neamtiu. Finding and reproducing heisenbugs in concurrent programs. In OSDI, 2008.
• 26: Mayur Naik , Alex Aiken , John Whaley, Effective static race detection for Java, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 27: Hiroyasu Nishiyama, Detecting data races using dynamic escape analysis based on read barrier, Proceedings of the 3rd conference on Virtual Machine Research And Technology Symposium, p.10-10, May 06-07, 2004, San Jose, California
• 28: Robert O'Callahan , Jong-Deok Choi, Hybrid dynamic data race detection, Proceedings of the ninth ACM SIGPLAN symposium on Principles and practice of parallel programming, June 11-13, 2003, San Diego, California, USA
• 29: Eli Pozniansky , Assaf Schuster, Efficient on-the-fly data race detection in multithreaded C++ programs, Proceedings of the ninth ACM SIGPLAN symposium on Principles and practice of parallel programming, June 11-13, 2003, San Diego, California, USA
• 30: Eli Pozniansky , Assaf Schuster, MultiRace: efficient on-the-fly data race detection in multithreaded C++ programs: Research Articles, Concurrency and Computation: Practice & Experience, v.19 n.3, p.327-340, March 2007 [doi>10.1002/cpe.v19:3]
• 31: Michiel Ronsse , Koen De Bosschere, RecPlay: a fully integrated practical record/replay system, ACM Transactions on Computer Systems (TOCS), v.17 n.2, p.133-152, May 1999 [doi>10.1145/312203.312214]
• 32: Caitlin Sadowski , Stephen N. Freund , Cormac Flanagan, SingleTrack: A Dynamic Determinism Checker for Multithreaded Programs, Proceedings of the 18th European Symposium on Programming Languages and Systems: Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2009, March 22-29, 2009, York, UK [doi>10.1007/978-3-642-00590-9_28]
• 33: Stefan Savage , Michael Burrows , Greg Nelson , Patrick Sobalvarro , Thomas Anderson, Eraser: a dynamic data race detector for multithreaded programs, ACM Transactions on Computer Systems (TOCS), v.15 n.4, p.391-411, Nov. 1997 [doi>10.1145/265924.265927]
• 34: D. Schonberg, On-the-fly detection of access anomalies, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.285-297, June 19-23, 1989, Portland, Oregon, United States
• 35: Standard Performance Evaluation Corporation. SPEC benchmarks. http://www.spec.org/, 2003.
• 36: N. Sterling. Warlock: A static data race analysis tool. In USENIX Winter Technical Conference, pages 97--106, 1993.
• 37: Sun Microsystems. The java.util.concurrent package. Available at http://java.sun.com/javase/6/docs/api/, 2008.
• 38: Christoph von Praun , Thomas R. Gross, Object race detection, Proceedings of the 16th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.70-82, October 14-18, 2001, Tampa Bay, FL, USA
• 39: Christoph von Praun , Thomas R. Gross, Static conflict analysis for multi-threaded object-oriented programs, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 40: Jan Wen Voung , Ranjit Jhala , Sorin Lerner, RELAY: static race detection on millions of lines of code, Proceedings of the the 6th joint meeting of the European software engineering conference and the ACM SIGSOFT symposium on The foundations of software engineering, September 03-07, 2007, Dubrovnik, Croatia [doi>10.1145/1287624.1287654]
• 41: Eran Yahav, Verifying safety properties of concurrent Java programs using 3-valued logic, Proceedings of the 28th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.27-40, January 2001, London, United Kingdom
• 42: Yuan Yu , Tom Rodeheffer , Wei Chen, RaceTrack: efficient detection of data race conditions via adaptive tracking, Proceedings of the twentieth ACM symposium on Operating systems principles, October 23-26, 2005, Brighton, United Kingdom

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.4 Software/Program Verification
          Subjects: Reliability

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Monitors; Testing tools (e.g., data generators, coverage testing)

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.1 Specifying and Verifying and Reasoning about Programs

General Terms:
Algorithms, Languages, Verification

Keywords:
concurrency, dynamic analysis, race conditions