A Formal Evaluation of Data Flow Path Selection Criteria

ABSTRACT

The authors report on the results of their evaluation of path-selection criteria based on data-flow relationships. They show how these criteria relate to each other, thereby demonstrating some of their strengths and weaknesses. A subsumption hierarchy showing their relationship is presented. It is shown that one of the major weaknesses of all the criteria is that they are based solely on syntactic information and do not consider semantic issues such as infeasible paths. The authors discuss the infeasible-path problem as well as other issues that must be considered in order to evaluate these criteria more meaningfully and to formulate a more effective path-selection criterion.

REFERENCES

• 1: 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
• 2: Lori A. Clarke , Debra J. Richardson, Applications of symbolic evaluation, Journal of Systems and Software, v.5 n.1, p.15-35, Feb. 1985 [doi>10.1016/0164-1212(85)90004-4]
• 3: {3} R. A. DeMillo, D. S. Guindi, W. M. McCracken, A. J. Offut, and K. N. King, "An extended overview of the mothra software testing environment," in <i>Proc. ACM SIGSOFT/IEEE Second Workshop Software Testing, Verification, and Analysis</i>, IEEE Comput. Soc., Banff, Alberta, Canada, July 1988, pp. 142-151.
• 4: {4} P. G. Frankl and E. J. Weyuker, "Data flow testing in the presence of unexecutable paths," in <i>Proc. ACM SIGSOFT/IEEE Workshop Software Testing</i>, IEEE Comput. Soc., Banff, Alberta, Canada, July 1986, pp. 4-13.
• 5: {5} P. M. Herman, "A data flow analysis approach to program testing," <i>Australian Comput. J.</i>, vol. 8, no. 3, Nov. 1976.
• 6: {6} W. E. Howden, "Methodology for the generation of program test data," <i>IEEE Trans. Comput.</i>, vol. C-24, no. 5, pp. 554-559, May 1975.
• 7: W E Howden, A functional approach to program testing and analysis, IEEE Transactions on Software Engineering, v.12 n.10, p.997-1005, Oct. 1986
• 8: {8} J. W. Laski, "On the comparative analysis of some data flow testing strategies," Dep. Eng. Comput. Sci., Oakland Univ., Rochester, MI, Tech. Rep. 87-05, May 1987.
• 9: {9} J. W. Laski and B. Korel, "A data flow oriented program testing strategy," <i>IEEE Trans. Software Eng.</i>, vol. SE-9, no. 3, pp. 347- 354, May 1983.
• 10: {10} L. J. Morell, "Theoretical insights into fault-based testing," in <i>Proc. ACM SIGSOFT/IEEE Second Workshop Software Testing, Verification, and Analysis</i>, IEEE Comput. Soc., Banff, Alberta, Canada, July 1988, pp. 45-62.
• 11: {11} S. C. Ntafos, "On testing with required elements," in <i>Proc. COMPSAC '81</i>, IEEE Comput. Soc., Nov. 1981, pp. 132-139.
• 12: {12} S. C. Ntafos, "On required element testing," Comput. Sci. Program, Univ. Texas, Dallas, Tech. Rep. 123, Nov. 1982.
• 13: {13} S. C. Ntafos, "On required element testing," <i>IEEE Trans. Software Eng.</i>, vol. SE-10, no. 6, pp. 795-803, Nov. 1984.
• 14: {14} S. C. Ntafos, "A comparison of some structural testing strategies," Comput. Sci. Program, Univ. Texas, Dallas, Tech. Rep. 210, June 1985.
• 15: 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]
• 16: {16} L. J. Osterweil and L. D. Fosdick, "DAVE--A validation, error detection, and documentation system for Fortran programs," <i>Software Practice and Experience</i>, vol. 6, no. 4, pp. 473-486, Oct. 1976.
• 17: A. Podgurski , L. Clarke, The implications of program dependencies for software testing, debugging, and maintenance, Proceedings of the ACM SIGSOFT '89 third symposium on Software testing, analysis, and verification, p.168-178, December 13-15, 1989, Key West, Florida, United States
• 18: Sandra Rapps , Elaine J. Weyuker, Data flow analysis techniques for test data selection, Proceedings of the 6th international conference on Software engineering, p.272-278, September 13-16, 1982, Tokyo, Japan
• 19: 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]
• 20: Debra J. Richardson , Margaret C. Thompson, An Analysis of Text Data Selection Criteria Using the RELAY Model of, University of Massachusetts, Amherst, MA, 1986
• 21: {21} D. J. Richardson and M. C. Thompson, "The RELAY model of error detection and its application," in <i>Proc. ACM SIGSOFT/IEEE Second Workshop Software Testing, Analysis and Verification</i>. IEEE Comput. Soc., Banff, Alberta, Canada, July 1988, pp. 223-230.
• 22: {22} L. G. Stucki, "Automatic generation of self-metric software," in <i>Rec. 1973 IEEE Symp. Software Reliability</i>, IEEE Comput. Soc., Apr. 1973, pp. 94-100.
• 23: 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]
• 24: {24} E. J. Weyuker, "An empirical study of the complexity of data flow testing," in <i>Proc. ACM SIGSOFT/IEEE Second Workshop Software Testing, Verification, and Analysis</i>, IEEE Comput. Soc., Banff, Alberta, Canada, July 1988, pp. 188-195.
• 25: {25} M. R. Woodward, D. Hedley, and M. A. Hennel, "Experience with path analysis and testing of programs," <i>IEEE Trans. Software Eng.</i>, vol. SE-6, no. 3, pp. 278-286, May 1980.
• 26: {26} S. J. Zeil, "Selectivity of data-flow and control-flow path criteria," in <i>Proc. ACM SIGSOFT/IEEE Second Workshop Software Testing, Verification, and Analysis</i>, IEEE Comput. Soc., Banff, Alberta, Canada, July 1988, pp. 216-222.
• 27: Steven J. Zeil, Perturbation Techniques for Detecting Domain Errors, IEEE Transactions on Software Engineering, v.15 n.6, p.737-746, June 1989 [doi>10.1109/32.24727]

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Design, Theory, Verification

Keywords:
data flow path selection criteria, data-flow relationships, flowcharting, formal evaluation, infeasible-path problem, software engineering, subsumption hierarchy, syntactic information