Estimating the number of test cases required to satisfy the all-du-paths testing criterion

ABSTRACT

The all-du-paths software testing criterion is the most discriminating of the data flow testing criteria of Rapps and Weyuker. Unfortunately, in the worst case, the criterion requires an exponential number of test cases. To investigate the practicality of the criterion, we develop tools to count the number of complete program paths necessary to satisfy the criterion. This count is an estimate of the number of test cases required. In a case study of an industrial software system, we find that in eighty percent of the subroutines the all-du-paths criterion is satisfied by testing ten or fewer complete paths. Only one subroutine out of 143 requires an exponential number of test cases.

REFERENCES

• BBC87: A. Baker, J. Bieman, and P. Clites. Implications for formal specifications - results of specifying a software engineering tool. Proc. IEEE Computer Society's Eleventh Annual International Computer Software & Applications Conference (COMPSA C87), 131-140, October 1987. Tokyo, Japan.
• BBC*88: James M. Bieman , Albert L. Baker , Paul N. Clites , David A. Gustafson , Austin C. Melton, A standard representation of imperative language programs for data collection and software measures specification, Journal of Systems and Software, v.8 n.1, p.13-37, January 1988 [doi>10.1016/0164-1212(88)90041-6]
• BHB86: Albert L. Baker, James W. Howatt, and James M. Bieman. Criteria for finite sets of paths that characterize control flow. Proc. 19th Hawaii International Conference on System Sciences (HICSS-19) IIA:158-163, January 1986.
• CPRZ85: Lori A. Clarke , Andy Podgurski , Debra J. Richardson , Steven J. Zeil, A comparison of data flow path selection criteria, Proceedings of the 8th international conference on Software engineering, p.244-251, August 28-30, 1985, London, England
• DBB86: K. Doh, J. Bieman, and A. Baker. Generating a Standard Representation from Pascal Programs. Technical Report TR 86-15, Dept. of Computer Science, Iowa State University, Ames, Iowa, 1986.
• FW85: Phyllis G. Frankl , Elaine J. Weyuker, A data flow testing tool, Proceedings of the second conference on Software development tools, techniques, and alternatives, p.46-53, December 1985, San Francisco, California, United States
• FW88: 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]
• FWW85: P. G. Frankl, S. N. Weiss, and E. J. Weyuker. Asset: a system to select and evaluate tests. Proc. IEEE Conference on Software Tools, 72- 79, April 1985.
• Hay87: Ian Hayes, Specification case studies, Prentice Hall International (UK) Ltd., Hertfordshire, UK, 1987
• Hec77: Matthew S. Hecht, Flow Analysis of Computer Programs, Elsevier Science Inc., New York, NY, 1977
• Jon86: C B Jones, Systematic software development using VDM, Prentice Hall International (UK) Ltd., Hertfordshire, UK, 1986
• JW85: Kathleen Jensen , Niklaus Wirth, Pascal-User Manual and Report, Springer-Verlag New York, Inc., Secaucus, NJ, 1975
• KP78: Brian W. Kernighan , P. J. Plauger, The Elements of Programming Style, McGraw-Hill, Inc., New York, NY, 1982
• Nta88: S. C. Ntafos, A Comparison of Some Structural Testing Strategies, IEEE Transactions on Software Engineering, v.14 n.6, p.868-874, June 1988 [doi>10.1109/32.6165]
• RW85: Sandra Rapps , Elaine J. Weyuker, Selecting software test data using data flow information, IEEE Transactions on Software Engineering, v.11 n.4, p.367-375, April 1985 [doi>10.1109/TSE.1985.232226]
• Sch88: J. L. Schultz. Measuring the Cardinality of Execution Path Subsets Meeting the All-DU-Paths Testing Criterion. Master's project, Department of Computer Science, Iowa State University, Ames, IA, 1988.
• Wey84: Elaine J. Weyuker, The complexity of data flow criteria for test data selection, Information Processing Letters, v.19 n.2, p.103-109, August 1984 [doi>10.1016/0020-0190(84)90106-6]
• WGM85: M. D. Weiser, J. D. Gannon, and P. R. McMullin. Comparison of structured test coverage metrics. IEEE Software, 2(2):80-85, March 1985.

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.4 Software/Program Verification
          Subjects: Validation

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Debugging aids

General Terms:
Algorithms, Reliability, Verification