The implications of program dependencies for software testing, debugging, and maintenance

ABSTRACT

This paper presents a formal, general model of program dependencies. Two generalizations of control and data dependence, called weak and strong syntactic dependence, are presented. Some of the practical implications of program dependencies are determined by relating weak and strong syntactic dependence to a relation called semantic dependence. Informally, one program statement is semantically dependent on another if the latter statement can affect the execution behavior of the former. It is shown that weak syntactic dependence is a necessary condition for semantic dependence, but that neither weak nor strong syntactic dependence are sufficient conditions. The implications of these results for software testing, debugging, and maintenance are then explored.

REFERENCES

• Aho74: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• Aho86: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• Berg85: Jean-Francois Bergeretti , Bernard A. Carré, Information-flow and data-flow analysis of while-programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.1, p.37-61, Jan. 1985 [doi>10.1145/2363.2366]
• Cart89: E. Cartwright , M. Felleisen, The semantics of program dependence, ACM SIGPLAN Notices, v.24 n.7, p.13-27, July 1989
• DeMi88: DeMillo, R.A., Guindi, D.S., King, K.N., McCracken, W.M., and Offutt, A.J. An extended overview of the Mothra software testing environment. Proceedings of the Second Workshop on Software Testing, Verification und Analysis, Banff, Alberta, July 1988, pp. 142-151.
• Denn77: Dorothy E. Denning , Peter J. Denning, Certification of programs for secure information flow, Communications of the ACM, v.20 n.7, p.504-513, July 1977 [doi>10.1145/359636.359712]
• Ferr87: 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]
• Fosd76: Lloyd D. Fosdick , Leon J. Osterweil, Data Flow Analysis in Software Reliability, ACM Computing Surveys (CSUR), v.8 n.3, p.305-330, Sept. 1976 [doi>10.1145/356674.356676]
• Fran87: Phyllis G. Frankl, The use of data flow information for the selection and evaluation of software test data, 1987
• Grei75: Sheila A. Greibach, Theory of Program Structures: Schemes, Semantics, Verification, Springer-Verlag New York, Inc., Secaucus, NJ, 1985
• Horw88a: 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]
• Horw88b: S. Horwitz , J. Prins , T. Reps, Integrating non-intering versions of programs, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.133-145, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73572]
• Kore87: Bogdan Korel, The program dependence graph in static program testing, Information Processing Letters, v.24 n.2, p.103-108, January 1987 [doi>10.1016/0020-0190(87)90102-5]
• Lask83: Laski, J. W. and Korel, B. A data flow oriented program testing strategy. IEEE Transactions on Software Engineering, Vol. SE-g, No. 3, May 1983, pp. 347- 354.
• Mann74: Zohar Manna, Introduction to Mathematical Theory of Computation, McGraw-Hill, Inc., New York, NY, 1974
• More84: Larry Joe Morell, A theory of error-based testing, 1983
• Ntaf84: Ntafos, S. C. On Required Element Testing. IEEE Transac2ions on Software Engineering, Vol. SE- 10, No. 6, Nov. 1984, pp. 795-803.
• Padu86: David A. Padua , Michael J. Wolfe, Advanced compiler optimizations for supercomputers, Communications of the ACM, v.29 n.12, p.1184-1201, Dec. 1986 [doi>10.1145/7902.7904]
• Podg89: Andy Podgurski , Lori Clarke, The Implications of Program Dependences for Software Testing, Debugging,, University of Massachusetts, Amherst, MA, 1989
• Rapp85: 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]
• Reps89: Reps, T. and Yang, W. The semantics of program slicing. Technical report, University of Wisconsin-Madison, 1989.
• Rich88: R h d ic ar son, D. J. and Thompson, M. C. The RELAY model of error detection and its application. Proc. Second Workshop on Software Testing, Verification, and Analysis, Banff, Canada, 1988.
• Selk89: R. Parsons-Selke, A rewriting semantics for program dependence graphs, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.12-24, January 11-13, 1989, Austin, Texas, United States [doi>10.1145/75277.75279]
• Weis79: Mark David Weiser, Program slices: formal, psychological, and practical investigations of an automatic program abstraction method, 1979
• Weis82: Mark Weiser, Programmers use slices when debugging, Communications of the ACM, v.25 n.7, p.446-452, July 1982 [doi>10.1145/358557.358577]
• Weis84: Weiser, M. Program slicing. IEEE Transactions on Software Engineering, Vol. SE-lo, No. 4, July 1984, pp. 352-356.

INDEX TERMS

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

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

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.3 Software Management
          Subjects: Software maintenance

General Terms:
Algorithms, Management, Reliability