Healing data races on-the-fly

ABSTRACT

Testing of concurrent software is extremely difficult. Despite all the progress in the testing and verification technology, concurrent bugs, the most common of which are deadlocks and races, make it to the field. This paper describes a set of techniques, implemented in a tool called ConTest, allowing concurrent programs to self-heal at run-time. Concurrent bugs have the very desirable property for healing that some of the interleaving produce correct results while in others bugs manifest. Healing concurrency problems is about limiting, or changing the probability of interleaving, such that bugs will be seen less. When healing concurrent programs, if a deadlock does not result from limiting the interleaving, we are sure that the result of the healed program could have been in the original program and therefore no new functional bug has been introduced. In this initial work which deals with different types of data races, we suggest three types of healing mechanisms: (1) changing the probability of interleaving by introducing sleep or yield statements or by changing thread priorities, (2) removing interleaving using synchronisation commands like locking and unlocking certain mutexes or waits and notifies, and (3) removing the result of "bad interleaving" by replacing the value of variables by the one that "should" have been taken. We also classify races according to the relevant healing strategies to apply.

REFERENCES

• 1: 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
• 2: C. Artho, K. Havelund, and A. Biere. High-level Data Races. In Proc. of VVEIS'03, Angers, France, 2003.
• 3: C. Artho, K. Havelund, and A. Biere. Using Block-Local Atomicity to Detect Stale-Value Concurrency Errors. In Proc. of ATVA'04, LNCS 3299, 2004. Springer.
• 4: Vasanth Balasundaram , Ken Kennedy, Compile-time detection of race conditions in a parallel program, Proceedings of the 3rd international conference on Supercomputing, p.175-185, June 05-09, 1989, Crete, Greece [doi>10.1145/318789.318809]
• 5: Thomas Ball , Sriram K. Rajamani, The SLAM Toolkit, Proceedings of the 13th International Conference on Computer Aided Verification, p.260-264, July 18-22, 2001
• 6: Utpal Banerjee , Brian Bliss , Zhiqiang Ma , Paul Petersen, A theory of data race detection, Proceeding of the 2006 workshop on Parallel and distributed systems: testing and debugging, July 17-17, 2006, Portland, Maine, USA [doi>10.1145/1147403.1147416]
• 7: W. Beaton and J. d. Rivieres. Eclipse Platform Technical Overview. Technical report, The Eclipse Foundation, 2006.
• 8: T. P. e. a. Brian Goetz. Java Concurrency in Practice. Addison-Wesley, 2006.
• 9: S. Chaki , E. Clarke , A. Groce , J. Ouaknine , O. Strichman , K. Yorav, Efficient Verification of Sequential and Concurrent C Programs, Formal Methods in System Design, v.25 n.2-3, p.129-166, September-November 2004 [doi>10.1023/B:FORM.0000040026.56959.91]
• 10: Guang-Ien Cheng , Mingdong Feng , Charles E. Leiserson , Keith H. Randall , Andrew F. Stark, Detecting data races in Cilk programs that use locks, Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.298-309, June 28-July 02, 1998, Puerto Vallarta, Mexico [doi>10.1145/277651.277696]
• 11: J. Choi, K. Lee, A. Loginov, R. O'Callahan, V. Sarkar, and M. Sridharan. Efficient and Precise Data Race Detection for Multithreaded Object-Oriented Programs, 2002.
• 12: Edmund M. Clarke, Jr. , Orna Grumberg , Doron A. Peled, Model checking, MIT Press, Cambridge, MA, 2000
• 13: A. Dinning , E. Schonberg, An empirical comparison of monitoring algorithms for access anomaly detection, Proceedings of the second ACM SIGPLAN symposium on Principles & practice of parallel programming, p.1-10, March 14-16, 1990, Seattle, Washington, United States
• 14: Anne Dinning , Edith Schonberg, Detecting access anomalies in programs with critical sections, Proceedings of the 1991 ACM/ONR workshop on Parallel and distributed debugging, p.85-96, May 20-21, 1991, Santa Cruz, California, United States
• 15: Perry A. Emrath , David A. Padua, Automatic detection of nondeterminacy in parallel programs, Proceedings of the 1988 ACM SIGPLAN and SIGOPS workshop on Parallel and distributed debugging, p.89-99, May 05-06, 1988, Madison, Wisconsin, United States
• 16: Eitan Farchi , Yarden Nir , Shmuel Ur, Concurrent Bug Patterns and How to Test Them, Proceedings of the 17th International Symposium on Parallel and Distributed Processing, p.286.2, April 22-26, 2003
• 17: Cormac Flanagan , Stephen N. Freund, Detecting race conditions in large programs, Proceedings of the 2001 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, p.90-96, June 2001, Snowbird, Utah, United States [doi>10.1145/379605.379687]
• 18: Cormac Flanagan , Stephen N Freund, Atomizer: a dynamic atomicity checker for multithreaded programs, Proceedings of the 31st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.256-267, January 14-16, 2004, Venice, Italy
• 19: T. Elmas, S. Qadeer, and S. Tasiran. Goldilocks: Efficiently computing the happens-before relation using locksets. Proceedings of the Workshop on Formal Approaches to Testing and Runtime Verification, 2006.
• 20: Cormac Flanagan , Shaz Qadeer, Types for atomicity, Proceedings of the 2003 ACM SIGPLAN international workshop on Types in languages design and implementation, January 18-18, 2003, New Orleans, Louisiana, USA
• 21: Cormac Flanagan , Stephen N. Freund , Shaz Qadeer, Exploiting Purity for Atomicity, IEEE Transactions on Software Engineering, v.31 n.4, p.275-291, April 2005 [doi>10.1109/TSE.2005.47]
• 22: T. A. Henzinger, R. Jhala, R. Majumdar, and G. Sutre. Software Verification with Blast. In Proc. of 10th SPIN Workshop, LNCS 2648, 2003. Springer.
• 23: Ayal Itzkovitz , Assaf Schuster , Oren Zeev-Ben-Mordehai, Toward integration of data race detection in DSM systems, Journal of Parallel and Distributed Computing, v.59 n.2, p.180-203, Nov. 1999 [doi>10.1006/jpdc.1999.1574]
• 24: Richard J. Lipton, Reduction: a method of proving properties of parallel programs, Communications of the ACM, v.18 n.12, p.717-721, Dec. 1975 [doi>10.1145/361227.361234]
• 25: John Mellor-Crummey, Compile-time support for efficient data race detection in shared-memory parallel programs, Proceedings of the 1993 ACM/ONR workshop on Parallel and distributed debugging, p.129-139, May 17-18, 1993, San Diego, California, United States
• 26: Neeraj Mittal , Vijay K. Garg, Finding missing synchronization in a distributed computation using controlled re-execution, Distributed Computing, v.17 n.2, p.107-130, August 2004 [doi>10.1007/s00446-003-0104-x]
• 27: R. Nagpaly, K. Pattabiramanz, D. Kirovski, and B. Zorn. ToleRace: Tolerating and Detecting Races. In Proc. of STMCS'07, 2007.
• 28: R. Netzer and B. Miller. Detecting Data Races in Parallel Program Executions. In Advances in Languages and Compilers for Parallel Computing, 1990 Workshop, 1990. MIT Press.
• 29: Robert H. B. Netzer , Barton P. Miller, Improving the accuracy of data race detection, Proceedings of the third ACM SIGPLAN symposium on Principles and practice of parallel programming, p.133-144, April 21-24, 1991, Williamsburg, Virginia, United States
• 30: Robert H. B. Netzer , Barton P. Miller, What are race conditions?: Some issues and formalizations, ACM Letters on Programming Languages and Systems (LOPLAS), v.1 n.1, p.74-88, March 1992 [doi>10.1145/130616.130623]
• 31: Dejan Perkovic , Peter J. Keleher, A Protocol-Centric Approach to on-the-Fly Race Detection, IEEE Transactions on Parallel and Distributed Systems, v.11 n.10, p.1058-1072, October 2000 [doi>10.1109/71.888645]
• 32: 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
• 33: Brad Richards , James R. Larus, Protocol-based data-race detection, Proceedings of the SIGMETRICS symposium on Parallel and distributed tools, p.40-47, August 03-04, 1998, Welches, Oregon, United States [doi>10.1145/281035.281040]
• 34: 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]
• 35: 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]
• 36: Ashis Tarafdar , Vijay K. Garg, Software Fault Tolerance of Concurrent Programs Using Controlled Re-execution, Proceedings of the 13th International Symposium on Distributed Computing, p.210-224, September 27-29, 1999
• 37: 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]
• 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: L. Wang and S. D. Stoller. Run-time Analysis for Atomicity. In Proc. of RV'03, ENTCS 89(2), 2003. Elsevier.
• 40: Liqiang Wang , Scott D. Stoller, Static analysis of atomicity for programs with non-blocking synchronization, 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.1065953]

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging

General Terms:
Algorithms, Verification

Keywords:
concurrency, self-healing, testing