AtomRace: data race and atomicity violation detector and healer

ABSTRACT

The paper proposes a novel algorithm called AtomRace for a dynamic detection of data races. Data races are detected as a special case of atomicity violations on atomic sections specially defined to span just particular read/write instructions and the transfer of control to and from them. A key ingredient allowing AtomRace to efficiently detect races on such short atomic sections is a use of techniques for a careful injection of noise into the scheduling of the monitored programs. The approach is very simple, fully automated, avoids false alarms, and allows for a lower overhead and better scalability than many other existing dynamic data race detection algorithms. We illustrate these facts by a set of experiments with a prototype implementation of AtomRace. Further, AtomRace can also be applied to detect atomicity violations on more general atomic sections than those used for the data race detection. They can be defined by the user or obtained by some static analysis.

REFERENCES

• 1: C. Artho, K. Havelund, and A. Biere. High-level data races, 2003.
• 2: Nathaniel Ayewah , William Pugh , J. David Morgenthaler , John Penix , YuQian Zhou, Using FindBugs on production software, Companion to the 22nd ACM SIGPLAN conference on Object oriented programming systems and applications companion, October 21-25, 2007, Montreal, Quebec, Canada [doi>10.1145/1297846.1297897]
• 3: 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
• 4: O. Edelstein, E. Farchi, E. Goldin, Y. Nir, G. Ratsaby, and S. Ur. Framework for testing multi-threaded java programs. Concurrency and Computation: Practice and Experience, 15(3--5):485--499, 2003.
• 5: T. Elmas, S. Qadeer, and S. Tasiran. Precise data-race detection and efficient model checking using locksets. Technical Report MSR-TR-2005-118, Microsoft Research, March 2006.
• 6: 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
• 7: Dawson Engler , Ken Ashcraft, RacerX: effective, static detection of race conditions and deadlocks, ACM SIGOPS Operating Systems Review, v.37 n.5, December 2003
• 8: Cormac Flanagan , Stephen N. Freund, Type-based race detection for Java, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.219-232, June 18-21, 2000, Vancouver, British Columbia, Canada
• 9: Cormac Flanagan , Stephen N Freund, Atomizer: a dynamic atomicity checker for multithreaded programs, ACM SIGPLAN Notices, v.39 n.1, p.256-267, January 2004
• 10: T. Henzinger, R. Jhala, R. Majumdar, and S. Qadeer. Thread-modular abstraction refinement. In Proceedings of the 15th International Conference on Computer-Aided Verification (CAV), pages 262--274. Lecture Notes in Computer Science 2725, Springer-Verlag, January 2003.
• 11: David H. Hovemeyer , William W. Pugh, Simple and effective static analysis to find bugs, University of Maryland at College Park, College Park, MD, 2005
• 12: V. Kahlon, Y. Yang, S. Sankaranarayanan, and A. Gupta. Fast and accurate static data-race detection for concurrent programs. In CAV, pages 226--239, 2007.
• 13: Bohuslav Krena , Zdenek Letko , Rachel Tzoref , Shmuel Ur , Tomáš Vojnar, Healing data races on-the-fly, Proceedings of the 2007 ACM workshop on Parallel and distributed systems: testing and debugging, July 09-09, 2007, London, United Kingdom [doi>10.1145/1273647.1273658]
• 14: 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]
• 15: Z. Letko. Dynamic data race detection and self-healing in java programs. Master's thesis, Faculty of Information Technology, Brno University of Technology, 2008.
• 16: Shan Lu , Joseph Tucek , Feng Qin , Yuanyuan Zhou, AVIO: detecting atomicity violations via access interleaving invariants, Proceedings of the 12th international conference on Architectural support for programming languages and operating systems, October 21-25, 2006, San Jose, California, USA
• 17: F. Mattern. Virtual time and global states of distributed systems. In Parallel and Distributed Algorithms: proceedings of the International Workshop on Parallel and Distributed Algorithms. 1988.
• 18: R. Nagpaly, K. Pattabiramanz, D. Kirovski, and B. Zorn. Position paper - tolerace: Tolerating and detecting races. In STMCS: Second Workshop on Software Tools for Multi-Core Systems (STMCS), 2007.
• 19: Mayur Naik , Alex Aiken , John Whaley, Effective static race detection for Java, ACM SIGPLAN Notices, v.41 n.6, June 2006
• 20: Yarden Nir-Buchbinder , Shmuel Ur, ConTest listeners: a concurrency-oriented infrastructure for Java test and heal tools, Fourth international workshop on Software quality assurance: in conjunction with the 6th ESEC/FSE joint meeting, September 03-04, 2007, Dubrovnik, Croatia [doi>10.1145/1295074.1295077]
• 21: 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
• 22: Tim Peierls , Brian Goetz , Joshua Bloch , Joseph Bowbeer , Doug Lea , David Holmes, Java Concurrency in Practice, Addison-Wesley Professional, 2005
• 23: Polyvios Pratikakis , Jeffrey S. Foster , Michael Hicks, LOCKSMITH: context-sensitive correlation analysis for race detection, ACM SIGPLAN Notices, v.41 n.6, June 2006
• 24: Amit Sasturkar , Rahul Agarwal , Liqiang Wang , Scott D. Stoller, Automated type-based analysis of data races and atomicity, Proceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programming, June 15-17, 2005, Chicago, IL, USA [doi>10.1145/1065944.1065956]
• 25: Stefan Savage , Michael Burrows , Greg Nelson , Patrick Sobalvarro , Thomas Anderson, Eraser: a dynamic data race detector for multi-threaded programs, Proceedings of the sixteenth ACM symposium on Operating systems principles, p.27-37, October 05-08, 1997, Saint Malo, France
• 26: Javier Soriano , Miguel Jimenez , Jose M. Cantera , Juan J. Hierro, Delivering Mobile Enterprise Services on Morfeo's MC Open Source Platform, Proceedings of the 7th International Conference on Mobile Data Management, p.139, May 10-12, 2006 [doi>10.1109/MDM.2006.63]
• 27: Rachel Tzoref , Shmuel Ur , Elad Yom-Tov, Instrumenting where it hurts: an automatic concurrent debugging technique, Proceedings of the 2007 international symposium on Software testing and analysis, July 09-12, 2007, London, United Kingdom [doi>10.1145/1273463.1273469]
• 28: Mandana Vaziri , Frank Tip , Julian Dolby, Associating synchronization constraints with data in an object-oriented language, Conference record of the 33rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.334-345, January 11-13, 2006, Charleston, South Carolina, USA
• 29: C. von Praun and T. Gross. Static detection of atomicity violations in object-oriented programs, 2003.
• 30: 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
• 31: Min Xu , Rastislav Bodík , Mark D. Hill, A serializability violation detector for shared-memory server programs, ACM SIGPLAN Notices, v.40 n.6, June 2005
• 32: Yuan Yu , Tom Rodeheffer , Wei Chen, RaceTrack: efficient detection of data race conditions via adaptive tracking, ACM SIGOPS Operating Systems Review, v.39 n.5, December 2005

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.4 Software/Program Verification

General Terms:
Verification