Interprocedual data flow testing

ABSTRACT

As current trends in programming encourage a high degree of modularity, the number of procedure calls and returns executed in a module continues to grow. This increase in procedures mandates the efficient testing of the interactions among procedures. In this paper, we extend the utility of data flow testing to include the testing of data dependencies that exist across procedure boundaries. An interprocedural data flow analysis algorithm is first presented that enables the efficient computation of information detailing the locations of definitions and uses needed by an interprocedural data flow tester. To utilize this information, a technique to guide the selection and execution of test cases, that takes into account the various associations of names with definitions and uses across procedures, is also presented. The resulting interprocedural data flow tester handles global variables, reference parameters and recursive procedure calls, and is compatible with the current intraprocedural data flow testing techniques. The testing tool has been implemented on a Sun 3/50 Workstation.

REFERENCES

• 1: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 2: F. E. Allen, "Interprocedural data flow analysis," in IFIP Information Processing 74, North-Holland Publishing Company, 1974.
• 3: John P. Banning, An efficient way to find the side effects of procedure calls and the aliases of variables, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.29-41, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567756]
• 4: Jeffrey M. Barth, A practical interprocedural data flow analysis algorithm, Communications of the ACM, v.21 n.9, p.724-736, Sept. 1978 [doi>10.1145/359588.359596]
• 5: D. Callahan, The program summary graph and flow-sensitive interprocedual data flow analysis, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.47-56, June 20-24, 1988, Atlanta, Georgia, United States
• 6: Martin Carroll , Barbara G Ryder, An incremental algorithm for software analysis, Proceedings of the second ACM SIGSOFT/SIGPLAN software engineering symposium on Practical software development environments, p.171-179, December 09-11, 1986, Palo Alto, California, United States
• 7: M. D. Carroll , B. G. Ryder, Incremental data flow analysis via dominator and attribute update, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.274-284, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73584]
• 8: 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
• 9: K. D. Cooper , K. Kennedy, Interprocedural side-effect analysis in linear time, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.57-66, June 20-24, 1988, Atlanta, Georgia, United States
• 10: P. G. Frankl, S. N. Weiss, and E. J. Weyuker, "ASSET: A system to select and evaluate tests," Proceedings of the IEEE Conference on Software Tools, New York, April 1985.
• 11: 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]
• 12: M. J. Harrold, "An approach to incremental testing," Technical Report 89-l Department of Computer Science, University of Pittsburgh, January 1989.
• 13: M. J. Harrold and M. L. Soffa, "An incremental data flow testing tool," Proceeding of the Sixth International Conference on Testing Computer Software, Washington, DC, May 1989.
• 14: B. Korel , J. Laski, A tool for data flow oriented program testing, Proceedings of the second conference on Software development tools, techniques, and alternatives, p.34-37, December 1985, San Francisco, California, United States
• 15: J. W. Laski and B. Korel, "A data flow oriented program testing strategy," IEEE Transactions on Software Engineering, vol. SE-g, no. 3, pp. 347- 354, May 1983.
• 16: D. B. Lomet, "Data flow analysis in the presence of procedure calls," IBM Journal of Research and Development, vol. 21, no. 6, pp. 559-571, November 1977.
• 17: Eugene M. Myers, A precise inter-procedural data flow algorithm, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.219-230, January 26-28, 1981, Williamsburg, Virginia [doi>10.1145/567532.567556]
• 18: Simeon C. Ntafos, An evaluation of required element testing strategies, Proceedings of the 7th international conference on Software engineering, p.250-256, March 26-29, 1984, Orlando, Florida, United States
• 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]

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques
          Subjects: Modules and interfaces

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

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Reliability, Verification