Forward computation of dynamic program slices

ABSTRACT

A dynamic program slice is an executable part of the program whose behavior is identical, for the same program input, to that of the original program with respect to a variable(s) of interest at some execution position. It has been shown that dynamic slicing is useful for the purpose of debugging, testing and software maintenance. The existing methods of dynamic slice computation are based on “backward” analysis, i.e., after the execution trace of the program is first recorded, the dynamic slice algorithm traces backwards the execution trace to derive dynamic dependence relations that are then used to compute dynamic slices. For many programs, during their execution extremely high volume of information may be recorded that may prevent accurate dynamic slice computation. In this paper we present a novel approach of dynamic slice computation, referred to as forward approach of dynamic slice computation. In this method, dynamic slices are computed during program execution without major recording of the execution trace. The major advantage of the forward approach is that space complexity is bounded as opposed to the backward methods of slice computation.

REFERENCES

• Agr90: Hiralal Agrawal , Joseph R. Horgan, Dynamic program slicing, ACM SIGPLAN Notices, v.25 n.6, p.246-256, Jun. 1990
• Agr93: Hiralal Agrawal , Richard A. Demillo , Eugene H. Spafford, Debugging with dynamic slicing and backtracking, Software—Practice & Experience, v.23 n.6, p.589-616, June 1993 [doi>10.1002/spe.4380230603]
• Bal69: R. Balzer, "Exdams: Extendible debugging and Monitoring system," Proc. Spring Joint Computer Conf., AFIPS Press, Reston, Va., 1969, pp. 567-580.
• Bal93: Thomas Ball , Susan Horwitz, Slicing Programs with Arbitrary Control-flow, Proceedings of the First International Workshop on Automated and Algorithmic Debugging, p.206-222, May 03-05, 1993
• Che93: Jingde Cheng, Slicing Concurrent Programs - A Graph-Theoretical Approach, Proceedings of the First International Workshop on Automated and Algorithmic Debugging, p.223-240, May 03-05, 1993
• Cho91: Jong-Deok Choi , Barton P. Miller , Robert H. B. Netzer, Techniques for debugging parallel programs with flowback analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.4, p.491-530, Oct. 1991 [doi>10.1145/115372.115324]
• Due92: Evelyn Duesterwald , Rajiv Gupta , Mary Lou Soffa, Distributed Slicing and Partial Re-execution for Distributed Programs, Proceedings of the 5th International Workshop on Languages and Compilers for Parallel Computing, p.497-511, August 03-05, 1992
• Fer92: Roger Clark Ferguson, Test data generation for sequential and distributed programs, Wayne State University, Detroit, MI, 1993
• Gal91: Keith Brian Gallagher , James R. Lyle, Using Program Slicing in Software Maintenance, IEEE Transactions on Software Engineering, v.17 n.8, p.751-761, August 1991 [doi>10.1109/32.83912]
• Gop91: R. Gopal, "Dynamic program slicing based on dependence relations," Proceedings of the Conference on Software Maintenance 1991, Sorrento, Italy, 1991, pp. 191-200.
• Gup92: R. Gupta, M. Harrold, M. Sofia, "An approach to regression testing using slicing," Conference on Software Maintenance, 1992, pp. 299-308.
• Hor90: 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]
• Kam93a: M. Kamkar, Interprocedural Dynamic Slicing with Applications to Debugging and Testing, Ph.D. Thesis, Linkoping University, 1993.
• Kam93b: Mariam Kamkar , Peter Fritzson , Nahid Shahmehri, Interprocedural Dynamic Slicing Applied to Interprocedural Data How Testing, Proceedings of the Conference on Software Maintenance, p.386-395, September 01, 1993
• Kor87: 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]
• Kor88a: B. Korel, PELAS-Program Error-Locating Assistant System, IEEE Transactions on Software Engineering, v.14 n.9, p.1253-1260, September 1988 [doi>10.1109/32.6169]
• Kor88b: B. Korel , J. Laski, Dynamic program slicing, Information Processing Letters, v.29 n.3, p.155-163, October 26, 1988 [doi>10.1016/0020-0190(88)90054-3]
• Kor90a: 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]
• Kor90b: Bogdan Korel , Janusz Laski, Dynamic slicing of computer programs, Journal of Systems and Software, v.13 n.3, p.187-195, Nov. 1990 [doi>10.1016/0164-1212(90)90094-3]
• Kor92: B. Korel, R. Ferguson, "Dynamic slicing of distributed programs," Applied Mathematics & Computer Science Journal, vol. 2, No. 2, 1992, pp. 199-215.
• Kor93: Bogdan Korel, Identifying Faulty Modifications in Software Maintenance, Proceedings of the First International Workshop on Automated and Algorithmic Debugging, p.315-332, May 03-05, 1993
• Lyl86: Mark Weiser , Jim Lyle, Experiments on slicing-based debugging aids, Papers presented at the first workshop on empirical studies of programmers on Empirical studies of programmers, p.187-197, June 1986, Washington, D.C., United States
• Sid91: K. Siddiqui, Experimental comparison of static and dynamic program slicing, Master Essay, Department of Computer Science, Wayne State University, 1991.
• Wei82: 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]
• Wei84: M. Weiser, "Program slicing," IEEE Trans. on Software Engineering, vol. SE-10, No. 4, July 1982, pp. 352-357.
• Whi92: IEEE Micro Staff, On the Edge: Regression testability, IEEE Micro, v.12 n.2, p.81-84, March 1992 [doi>10.1109/40.127586]

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging

          Nouns: DEBUG

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

General Terms:
Algorithms, Languages, Theory, Verification