Bogdan Korel
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.
- Agr90.H. Agrawal, J. Horgan, "Dynamic program slicing" SIGPLAN Notices, Vol. 25, No. 6, June 1990, pp. 246-256. Google Scholar
Digital Library
- Agr93.H. Agrawal, R. DeMillo, E. Spafford, "Debugging with dynamic slicing and backtracking," Software Practice & Experience, vol. 23, No. 6, 1993, pp. 589-616. Google ScholarDigital Library
- Bal69.R. Balzer, "Exdams: Extendible debugging and Monitoring system," Proc. Spring Joint Computer Conf., AFIPS Press, Reston, Va., 1969, pp. 567-580.Google Scholar
- Bal93.T. Ball, S. Horwitz, "Slicing programs with arbitrary control-flow," Proceedings of the 1-st International Workshop on Automated and Algorithmic Debugging, Linkoping, Sweden, 1993, pp. 228-243. Google ScholarDigital Library
- Che93.J. Cheng, "Slicing concurrent programs," Proceedings of the 1-st International Workshop on Automated and Algorithmic Debugging, Linkoping, Sweden, 1993, pp. 244-261. Google ScholarDigital Library
- Cho91.J. Choi, B. Miller, R. Netzer, "Techniques for debugging parallel programs with flow back analysis," ACM Tran. on Programming Languages and Systems, vol. 13, No. 4, October 1991, 491-530. Google ScholarDigital Library
- Due92.E. Duesterwald, R. Gupta, M. L. Sofia, "Distribute~ slicing and partial re-execution for distributed programs," Proc. 5th Workshop on Languages and Compilers for Parallel Computing, 1992, pp. 329-337. Google ScholarDigital Library
- Fer92.R. Ferguson, "Test Data Generation for Sequential and Distributed Programs," Ph.D. Thesis, Wayne State University, 1992. Google ScholarDigital Library
- Gal91.K. Gallagher, J. Lyle, "Using program slicing in software maintenance," IEEE Transactions on Software Engineering, vol. 17, No. 8, August 1991, pp. 751-761. Google ScholarDigital Library
- Gop91.R. Gopal, "Dynamic program slicing based on dependence relations," Proceedings of the Conference on Software Maintenance 1991, Sorrento, Italy, 1991, pp. 191-200.Google Scholar
- Gup92.R. Gupta, M. Harrold, M. Sofia, "An approach to regression testing using slicing," Conference on Software Maintenance, 1992, pp. 299-308.Google Scholar
- Hor90.S. Horwitz, T. Reps, D. Binkley, "interprocedural slicing using dependence graphs," Trans. on Programming Languages and Systems, vol. 12, No. 1, pp. 26-60, 1990. Google ScholarDigital Library
- Kam93a.M. Kamkar, Interprocedural Dynamic Slicing with Applications to Debugging and Testing, Ph.D. Thesis, Linkoping University, 1993.Google Scholar
- Kam93b.M. Kamkar, P. Fritzson, N. Shahmehri, "Interprocedural dynamic slicing applied to interpmce3ural data flow testing," Conference on Software Maintenance, Montreal, 1993, pp. 386-395. Google ScholarDigital Library
- Kor87.B. Korel, "The program dependence graph in static program testing," Information Processing Letters, vol. 24, Jan. 1987, pp. 103-108 Google ScholarDigital Library
- Kor88a.B. Korel, "PELAS - Program Error Locating Assistant System," IEEE Trans. on Software Engineering, vol. SE-14, No. 9, September 1988, pp. 1253-1260. Google ScholarDigital Library
- Kor88b.B. Korel, J. Laski, "Dynamic program slicing," Information Processing Letters, vol. 29, No. 3, October 1988, pp. 155-163. Google ScholarDigital Library
- Kor90a.B. Korel, "Automated software test data generation," IEEE Trans. on Software Engineering, vol. SE-16, No. 8, 1990, pp. 870- 879. Google ScholarDigital Library
- Kor90b.B. Korel, J. Laski, "Dynamic slicing in computer programs," The Journal of Systems and Software, vol. 13, No. 3, 1990, pp. 187- 195. Google ScholarDigital Library
- Kor92.B. Korel, R. Ferguson, "Dynamic slicing of distributed programs," Applied Mathematics & Computer Science Journal, vol. 2, No. 2, 1992, pp. 199-215.Google Scholar
- Kor93.B. Korel, "Identifying faulty modifications in software maintenance," Proceedings of the l-st International Workshop on Automated and Algorithmic Debugging, Linkoping, Sweden, 1993, pp. 341-356. Google ScholarDigital Library
- Lyl86.J. Lyle, M. Weiser, ""Experiments on slicingbased debugging tools," ProceeMings of the First Conference on Empirical Studies of Programming, June 1986, pp. 187-197. Google ScholarDigital Library
- Sid91.K. Siddiqui, Experimental comparison of static and dynamic program slicing, Master Essay, Department of Computer Science, Wayne State University, 1991.Google Scholar
- Wei82.M. Weiser, "Programmers use slices when debugging," Comm. of ACM, vol. 25, No. 7, July 1982, pp. 446-452. Google ScholarDigital Library
- Wei84.M. Weiser, "Program slicing," IEEE Trans. on Software Engineering, vol. SE-10, No. 4, July 1982, pp. 352-357.Google ScholarDigital Library
- Whi92.L. White, H. Leung, "Regression testability," IEEE Micro, April 1992, pp. 81-85. Google ScholarDigital Library
Index Terms
- Forward computation of dynamic program slices
Recommendations
Computation of Dynamic Program Slices for Unstructured Programs
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. The existing algorithms of ...
Memoized Forward Computation of Dynamic Slices
ISSRE '06: Proceedings of the 17th International Symposium on Software Reliability EngineeringForward computation of dynamic slices is necessary to support interactive debugging and online analysis of long running programs. However, the overhead of existing forward computing algorithms limits their use to nonprocessing intensive applications. ...
Efficient Forward Computation of Dynamic Slices Using Reduced Ordered Binary Decision Diagrams
ICSE '04: Proceedings of the 26th International Conference on Software EngineeringDynamic slicing algorithms can greatly reduce the debuggingeffort by focusing the attention of the user on a relevantsubset of program statements. Recently algorithms forforward computation of dynamic slices have beenproposed which maintain dynamic ...
Comments