Incremental program testing using program dependence graphs

ABSTRACT

Program dependence graphs have been proposed for use in optimizing, vectorizing, and parallelizing compilers, and for program integration. This paper proposes their use as the basis for incremental program testing when using test data adequacy criteria. Test data adequacy is commonly used to provide some confidence that a particular test suite does a reasonable job of testing a program. Incremental program testing using test data adequacy criteria addresses the problem of testing a modified program given an adequate test suite for the original program. Ideally, one would like to create an adequate test suite for the modified program that reuses as many files from the old test suite as possible. Furthermore, one would like to know, for every file that is in both the old and the new test suites, whether the program components exercised by that file have been affected by the program modification; if no components have been affected, then it is not necessary to rerun the program using that file. In this paper we define adequacy criteria based on the program dependence graph, and propose techniques based on program slicing to identify components of the modified program that can be tested using files from the old test suite, and components that have been affected by the modification. This information can be used to reduce the time required to create new test files, and to avoid unproductive retesting of unaffected components. Although exact identification of the components listed above is, in general, undecidable, we demonstrate that our techniques provide safe approximations.

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: S. Bates and S. Horwitz, "Incremental Program Testing Using Program Dependence Graphs," technical report in reparation, Computer Sciences Department, University of Wisconsin, Madison, WI (1992).
• 3: S. Bates and S. Horwitz, "On integrating Programs with Input," in preparation, Computer Sciences Department, University of Wisconsin, Madison, WI (1992).
• 4: S. Bates and S. Horwitz, "Test Data Adequacy Criteria Based on Program Dependence Graphs," in preparation, Computer Sciences Department, University of Wisconsin, Madison, WI (1992).
• 5: T. Chusho, "Coverage Measure for Path Testing Based on the Concept of Essential Branches," Journal of Information Processing 6(4) pp. 199-205 (1983).
• 6: T. Chusho, Test data selection and quality estimation based on the concept of essential branches for path testing, IEEE Transactions on Software Engineering, v.13 n.5, p.509-517, May 1987 [doi>10.1109/TSE.1987.233196]
• 7: L.A. Clarke, "A System to Generate Test Data and Symbolically Execute Programs," IEEE Transactions on Software Engineering SE-2(3) pp. 215-222 (September 1976).
• 8: Richard A. DeMillo , A. Jefferson Offutt, Constraint-Based Automatic Test Data Generation, IEEE Transactions on Software Engineering, v.17 n.9, p.900-910, September 1991 [doi>10.1109/32.92910]
• 9: V. Donzeau-Gouge, G. Huet, G. Kahn, and B. Lang, "Programming environments based on structured editors: The MENTOR experience," pp. 128-140 in Interactive Programming Environments, ed. D. Barstow, E. Sandewall, and H. Shrobe,MeGraw-Hiil, New York, NY (1984).
• 10: Jeanne Ferrante , Karl J. Ottenstein , Joe D. Warren, The program dependence graph and its use in optimization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.3, p.319-349, July 1987 [doi>10.1145/24039.24041]
• 11: R. Gupta and M. L. Sofia, "Automatic Generation of a Compact Test Suite," Technical Report, University of Pittsburgh, Pittsburgh, PA (1991).
• 12: M.J. Harrold and M. L. Sofia, "An Incremental Approach to Unit Testing during Maintenance," Proceedings of the Conference on Software Maintenance (Phoenix, Arizona), pp. 362-367 (October 24-27, 1988).
• 13: S. Horwitz , J. Prins , T. Reps, On the adequacy of program dependence graphs for representing programs, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.146-157, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73573]
• 14: S. Horwitz , P. Pfeiffer , T. Reps, Dependence analysis for pointer variables, ACM SIGPLAN Notices, v.24 n.7, p.28-40, July 1989
• 15: Susan Horwitz , Jan Prins , Thomas Reps, Integrating noninterfering versions of programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.11 n.3, p.345-387, July 1989 [doi>10.1145/65979.65980]
• 16: Susan Horwitz , Thomas Reps , David Binkley, Interprocedural slicing using dependence graphs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.1, p.26-60, Jan. 1990 [doi>10.1145/77606.77608]
• 17: Susan Horwitz , Thomas Reps, Efficient comparison of program slices, Acta Informatica, v.28 n.9, p.713-732, Nov. 1991
• 18: W.E. Howden, "Reliability of the Path Analysis Testing Strategy," IEEE Transactions on Software Engineering SE- 2(3) pp. 208-215 (September 1976).
• 19: J. C. Huang, An Approach to Program Testing, ACM Computing Surveys (CSUR), v.7 n.3, p.113-128, Sept. 1975 [doi>10.1145/356651.356652]
• 20: B. Korel, Automated Software Test Data Generation, IEEE Transactions on Software Engineering, v.16 n.8, p.870-879, August 1990 [doi>10.1109/32.57624]
• 21: K.W. Krause, R. W. Smith, and M. A. Goodwin, "Optimal Software Test Planning Through Automated Network Analysis," Record of the 1973 IEEE Symposium on Computer Software Reliability (New York, New York), pp. 18-22 (April 30-May 2, 1973).
• 22: J. R. Larus , P. N. Hilfinger, Detecting conflicts between structure accesses, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.24-31, June 20-24, 1988, Atlanta, Georgia, United States
• 23: J.W. Laski and B. Korel, "A Data Flow Oriented Program Testing Strategy," IEEE Transactions on Software Engineering SE-9(3) pp. 347-354 (May 1983).
• 24: B. Mariek, "A Survey of Test Effectiveness and Cost Studies," Report No. UIUCDCS-R-90-1652, Department of Computer Science, University of Illinois at Urbana- Champaign, Urbana, IL (December 1990).
• 25: D. Notkin, R. Ellison, B. Staudt, G. Kaiser, E. Kant, A. Habermann, V. Ambriola, and C. Montangero, Special issue on the GANDALF project, Journal of Systems and Software 5(2)(May 1985).
• 26: S.C. Ntafos, "On Required Element Testing," IEEE Transactions on Software Engineering SE-10(6)pp. 795-803 (November 1984).
• 27: T.J. Ostrand and E. J. Weyuker, "Using Data Flow Analysis for Regression Testing," Proceedings of the Sixth Annual Pacific Northwest Software Quality Conference (Portland, Oregon), (September 19-20, 1988).
• 28: Karl J. Ottenstein , Linda M. Ottenstein, The program dependence graph in a software development environment, Proceedings of the first ACM SIGSOFT/SIGPLAN software engineering symposium on Practical software development environments, p.177-184, April 1984
• 29: 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]
• 30: Thomas W. Reps , Tim Teitelbaum, The synthesizer generator: a system for constructing language-based editors, Springer-Verlag New York, Inc., New York, NY, 1989
• 31: Thomas W. Reps , Wuu Yang, The Semantics of Program Slicing and Program Integration, Proceedings of the International Joint Conference on Theory and Practice of Software Development, Volume 2: Advanced Seminar on Foundations of Innovative Software Development II and Colloquium on Current Issues in Programming Languages, p.360-374, March 13-17, 1989
• 32: E. Schatz and B. G. Ryder, "Directed Tracing to Detect Race Conditions," LCSR-TR-176, Laboratory for Computer Science Research, Rutgers University, New Brunswick, NJ (February 1992).
• 33: A. Taha, S. M. Thebaut, and S. Liu, "An Approach to Software Fault Localization and Revalidation Based on Incremental Data Flow Analysis," Proceedings of the Thir. teenth Annual International Computer Software & Applications Conference (orlando, Florida), pp. 552-558 (September 20-22, 1989).
• 34: M. Weiser, "Program Slicing," IEEE Transactions on Software Engineering SE-10(4) pp. 352-357 (July 1984).
• 35: Wuu Yang, Identifying syntactic differences between two programs, Software—Practice & Experience, v.21 n.7, p.739-755, July 1991 [doi>10.1002/spe.4380210706]

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures
  F.3 LOGICS AND MEANINGS OF PROGRAMS

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

General Terms:
Algorithms, Languages