Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Coverage measures help to determine whether a test suite exercises a program adequately according to a testing criterion. Many existing measures, however, are defined over coverage domains that cannot be precisely calculated, rendering them of limited value in assessing the extent of testing activities. To exploit the use of such measures, we formalize saturation-based test adequacy, a form of adequacy focused on the rate at which coverage increases during test suite execution. We define a family of coverage metrics for concurrent program testing that are well-suited to saturation-based adequacy and present a study that explores their cost and effectiveness. The results of this study suggest that saturation-based testing can serve as an effective complement to traditional notions of coverage-based testing.

REFERENCES

• 1: R-squared. http://en.wikipedia.org/wiki/R-squared.
• 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: R. Carver , K. C. Tai, Deterministic execution testing of concurrent Ada programs, Proceedings of the conference on Tri-Ada '89: Ada technology in context: application, development, and deployment, p.528-544, January 1989, Pittsburgh, Pennsylvania, United States [doi>10.1145/74261.74301]
• 4: Jong-Deok Choi , Harini Srinivasan, Deterministic replay of Java multithreaded applications, Proceedings of the SIGMETRICS symposium on Parallel and distributed tools, p.48-59, August 03-04, 1998, Welches, Oregon, United States [doi>10.1145/281035.281041]
• 5: Jeffrey Dean , David Grove , Craig Chambers, Optimization of Object-Oriented Programs Using Static Class Hierarchy Analysis, Proceedings of the 9th European Conference on Object-Oriented Programming, p.77-101, August 07-11, 1995
• 6: M. B. Dwyer, J. Hatcliff, M. Hoosier, V. Ranganath, Robby, and T. Wallentine. Evaluating the effectiveness of program slicing for model reduction of concurrent object-oriented programs. In Proc. of the Twelfth Int'l. Conf. Tools and Alg. for the Const. and Anal. of Sys., 2006.
• 7: Matthew B. Dwyer , Suzette Person , Sebastian Elbaum, Controlling factors in evaluating path-sensitive error detection techniques, Proceedings of the 14th ACM SIGSOFT international symposium on Foundations of software engineering, November 05-11, 2006, Portland, Oregon, USA [doi>10.1145/1181775.1181787]
• 8: O. Edelstein, E. Farchi, Y. Nir, G. Ratsaby, and S. Ur. Multithreaded java program test generation. IBM Systems Journal, 41(1):111--125, 2002.
• 9: http://home.att.net/ ddavies/NewSmulator.html.
• 10: Yaniv Eytani , Klaus Havelund , Scott D. Stoller , Shmuel Ur, Towards a framework and a benchmark for testing tools for multi-threaded programs: Research Articles, Concurrency and Computation: Practice & Experience, v.19 n.3, p.267-279, March 2007 [doi>10.1002/cpe.v19:3]
• 11: 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
• 12: Cormac Flanagan , Patrice Godefroid, Dynamic partial-order reduction for model checking software, ACM SIGPLAN Notices, v.40 n.1, p.110-121, January 2005
• 13: John B. Goodenough , Susan L. Gerhart, Toward a theory of test data selection, Proceedings of the international conference on Reliable software, p.493-510, April 21-23, 1975, Los Angeles, California
• 14: Richard L. Halpert , Christopher J. F. Pickett , Clark Verbrugge, Component-Based Lock Allocation, Proceedings of the 16th International Conference on Parallel Architecture and Compilation Techniques, p.353-364, September 15-19, 2007 [doi>10.1109/PACT.2007.23]
• 15: T. J. LeBlanc , J. M. Mellor-Crummey, Debugging Parallel Programs with Instant Replay, IEEE Transactions on Computers, v.36 n.4, p.471-482, April 1987 [doi>10.1109/TC.1987.1676929]
• 16: Yu Lei , Richard H. Carver, Reachability Testing of Concurrent Programs, IEEE Transactions on Software Engineering, v.32 n.6, p.382-403, June 2006 [doi>10.1109/TSE.2006.56]
• 17: Shan Lu , Weihang Jiang , Yuanyuan Zhou, A study of interleaving coverage criteria, 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.1287703]
• 18: A. P. Mathur. Foundations of Software Testing. Pearson, 2008.
• 19: NASA Ames Research Center. Java PathFinder. http://javapathfinder.sourceforge.net.
• 20: M. Ohba , X.-M. Chou, Does imperfect debugging affect software reliability growth?, Proceedings of the 11th international conference on Software engineering, p.237-244, May 1989, Pittsburgh, Pennsylvania, United States [doi>10.1145/74587.74619]
• 21: http://research.microsoft.com/ qadeer/cav-issta.htm.
• 22: G. Ramalingam, Context-sensitive synchronization-sensitive analysis is undecidable, ACM Transactions on Programming Languages and Systems (TOPLAS), v.22 n.2, p.416-430, March 2000 [doi>10.1145/349214.349241]
• 23: Fragment Class Analysis for Testing of Polymorphism in Java Software, IEEE Transactions on Software Engineering, v.30 n.6, p.372-387, June 2004 [doi>10.1109/TSE.2004.20]
• 24: Sable Research Group. Soot. http://www.sable.mcgill.ca/soot.
• 25: 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]
• 26: Koushik Sen, Effective random testing of concurrent programs, Proceedings of the twenty-second IEEE/ACM international conference on Automated software engineering, November 05-09, 2007, Atlanta, Georgia, USA [doi>10.1145/1321631.1321679]
• 27: E. Sherman. State coverage for the dynamic analysis of concurrent programs. Master's thesis, University of Nebraska-Lincoln, 2008.
• 28: S. D. Stoller. Testing concurrent Java programs using randomized scheduling. In Proc. Second Workshop on Runtime Verification (RV), volume 70(4) of Electronic Notes in Theoretical Computer Science. Elsevier, July 2002.
• 29: 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]
• 30: E. J. Weyuker, The evaluation of program-based software test data adequacy criteria, Communications of the ACM, v.31 n.6, p.668-675, June 1988 [doi>10.1145/62959.62963]
• 31: T. Williams, M. Mercer, J. Mucha, and R. Kapur. Code coverage, what does it mean in terms of quality? In Proceedings of the Reliability and Maintainability Symposium, pages 420--424, 2001.
• 32: Murray Wood , Marc Roper , Andrew Brooks , James Miller, Comparing and combining software defect detection techniques: a replicated empirical study, Proceedings of the 6th European SOFTWARE ENGINEERING conference held jointly with the 5th ACM SIGSOFT international symposium on Foundations of software engineering, p.262-277, September 22-25, 1997, Zurich, Switzerland
• 33: 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
• 34: R.-D. Yang , C.-G. Chung, Path analysis testing of concurrent programs, Information and Software Technology, v.34 n.1, p.43-56, Jan. 1992 [doi>10.1016/0950-5849(92)90093-5]

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, Verification

Keywords:
concurrent programs, coverage, test adequacy criteria