A study of interleaving coverage criteria

ABSTRACT

Concurrency bugs are becoming increasingly important due to the prevalence of concurrent programs. A fundamental problem of concurrent program bug detection and testing is that the interleaving space is too large to be thoroughly explored. Practical yet effective interleaving coverage criteria are desired to systematically explore the interleaving space and effectively expose concurrency bugs.

This paper proposes a concurrent program interleaving coverage criteria hierarchy, including seven (including five new) coverage criteria. These criteria are all designed based on different concurrency fault models. Their cost ranges from exponential to linear.

REFERENCES

• 1: Boris Beizer, Software testing techniques (2nd ed.), Van Nostrand Reinhold Co., New York, NY, 1990
• 2: Arkady Bron , Eitan Farchi , Yonit Magid , Yarden Nir , Shmuel Ur, Applications of synchronization coverage, 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.1065972]
• 3: L. A. Clarke , A. Podgurski , D. J. Richardson , S. J. Zeil, A Formal Evaluation of Data Flow Path Selection Criteria, IEEE Transactions on Software Engineering, v.15 n.11, p.1318-1332, November 1989 [doi>10.1109/32.41326]
• 4: O. Edelstein, E. Farchi, Y. Nir, G. Ratsaby, and S. Ur. Multi-threaded java program test generation. IBM Systems Journal, 2002.
• 5: M. Factor , E. Farchi , Y. Lichtenstein , Y. Malka, Testing concurrent programs: a formal evaluation of coverage criteria, Proceedings of the 7th Israeli Conference on Computer-Based Systems and Software Engineering, p.119, June 10-12, 1996
• 6: P. G. Frankl , E. J. Weyuker, An Applicable Family of Data Flow Testing Criteria, IEEE Transactions on Software Engineering, v.14 n.10, p.1483-1498, October 1988 [doi>10.1109/32.6194]
• 7: M. J. Harrold and B. A. Malloy. Data flow testing of parallelized code. In Proceedings of the International Conference on Software Maintenance, 1992.
• 8: 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
• 9: Shaz Qadeer , Dinghao Wu, KISS: keep it simple and sequential, Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, June 09-11, 2004, Washington DC, USA
• 10: 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]
• 11: Richard N. Taylor , David L. Levine , Cheryl D. Kelly, Structural Testing of Concurrent Programs, IEEE Transactions on Software Engineering, v.18 n.3, p.206-215, March 1992 [doi>10.1109/32.126769]
• 12: 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
• 13: S. N. Weiss. A formal framework for the study of concurrent program testing. In Proceedings of the Second Workshop on Software Testing, Verification and Analysis, 1988.
• 14: E. J. Weyuker, More Experience with Data Flow Testing, IEEE Transactions on Software Engineering, v.19 n.9, p.912-919, September 1993 [doi>10.1109/32.241773]
• 15: Cheer-Sun D. Yang , Amie L. Souter , Lori L. Pollock, All-du-path coverage for parallel programs, Proceedings of the 1998 ACM SIGSOFT international symposium on Software testing and analysis, p.153-162, March 02-04, 1998, Clearwater Beach, Florida, United States
• 16: Hong Zhu , Patrick A. V. Hall , John H. R. May, Software unit test coverage and adequacy, ACM Computing Surveys (CSUR), v.29 n.4, p.366-427, Dec. 1997 [doi>10.1145/267580.267590]

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:
Reliability

Keywords:
concurrent program, coverage criteria, interleaving