Producing scheduling that causes concurrent programs to fail

ABSTRACT

A noise maker is a tool that seeds a concurrent program with conditional synchronization primitives (such as yield()) for the purpose of increasing the likelihood that a bug manifest itself. This work explores the theory and practice of choosing where in the program to induce such thread switches at runtime. We introduce a novel fault model that classifies locations as ¿good¿, ¿neutral¿, or ¿bad,¿ based on the effect of a thread switch at the location. We validate our approach by experimenting with a set of programs taken from publicly available multi-threaded benchmark. Our empirical evidence demonstrates that real-life behavior is similar to that derived from the model.

REFERENCES

• 1: Yosi Ben-Asher , Eitan Farchi , Yaniv Eytani, Heuristics for Finding Concurrent Bugs, Proceedings of the 17th International Symposium on Parallel and Distributed Processing, p.288.1, April 22-26, 2003
• 2: O. Edelstein, E. Farchi, Y. Nir, G. Ratsaby, and S. Ur. ¿Multithreaded Java Program Test Generation.¿ IBM Systems Journal, Vol. 41, No. 1, 2002.
• 3: Y. Eytani, K. Havelund, S. D. Stoller, and S. Ur. "Toward a Framework and Benchmark for Testing Tools for Multi-Threaded Programs". Concurrency and Computation: Practice & Experience, to appear.
• 4: 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
• 5: 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
• 6: H. H. Hallal , E. Alikacem , W. P. Tunney , S. Boroday , A. Petrenko, Antipattern-Based Detection of Deficiencies in Java Multithreaded Software, Proceedings of the Quality Software, Fourth International Conference on (QSIC'04), p.258-267, September 08-10, 2004 [doi>10.1109/QSIC.2004.8]
• 7: Brad Long , Paul Strooper, A Classification of Concurrency Failures in Java Components, Proceedings of the 17th International Symposium on Parallel and Distributed Processing, p.287.1, April 22-26, 2003
• 8: 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]
• 9: S. D. Stoller. "Testing Concurrent Java Programs Using Randomized Scheduling." In Workshop on Runtime Verification (RV), Volume 70(4), Electronic Notes in Theoretical Computer Science. Elsevier, 2002.

INDEX TERMS

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

General Terms:
Experimentation, Reliability, Verification