G. A. Venkatesh
Abstract
Program slicing is a program analysis technique that has been studied in the context of several different applications in the construction, optimization, maintenance, testing, and debugging of programs. Algorithms are available for constructing slices for a particular execution of a program (dynamic slices), as well as to approximate a subset of the behavior over all possible executions of a program (static slices). However, these algorithms have been studied only in the context of small abstract languages. Program slicing is bound to remain an academic exercise unless one can not only demonstrate the feasibility of building a slicer for nontrivial programs written in a real programming language, but also verify that a type of slice is sufficiently thin, on the average, for the application for which it is chosen. In this article, we present results from using SLICE, a dynamic program slicer for C programs, designed and implemented to experiment with several different kinds of program slices and to study them both qualitatively and quantitatively. Several application programs, ranging in size (i.e., number of lines of code) over two orders of magnitude, were sliced exhaustively to obtain average worst-case metrics for the size of program slices.
- AGRAWAL, H. 1991. Towards automatic debugging of computer programs. Tech. Rep. SERC- TR-103-P, SERC, Purdue Univ., West Lafayette, Ind. Aug.Google Scholar
- AGRAWAL, H. AND HORGAN, B. 1990. Dynamic program slicing. In Proceedings of the SIGPLAN 90 Conference on Programming Language Design and implementatwn. ACM SIGPLAN Not. 25, 6 (June), 246-256. Google Scholar
- BALL, T. AND LARUS, J. R. 1994. Optimally profiling and tracing programs. ACM Trans. Program. Lang. Syst. 16, 4 (July), 1319-1360. Google Scholar
- COOPER, K. 1985. Analyzing aliases of reference formal parameters. In Proceedings 12th ACM Symposium on Principles of Programming Languages (New Orleans, La., Jan. 14-16). ACM, New York, 281-290. Google Scholar
- COOPER, K. AND KENNEDY, K. 1989. Fast interprocedural alias analysis. In Proceedings 16th ACM Symposium on Principles of Programming Languages (Austin, Tex., Jan. 11-13). ACM, New York, 49-59. Google Scholar
- ERNST, M. 1994. Practical fine-grained static slicing of optimized code. Tech. Rep. MSR-TR-94- 14, Microsoft Research, Redmond, Wash.Google Scholar
- HORWITZ, S., PFEIFFER, P., AND REPS, T. 1989. Dependence analysis for pointer variables, in Proceedings of the SIGPLAN '89 Conference on Programming Language Design and Implementation. ACM SIGPLAN Not. 24, 7 (June), 28-40. Google Scholar
- Hol%WlTZ, ~., PRINS, J., AND REPS, T. 1988. Integrating non-interfering versions of programs. In Proceedings 15th ACM Symposium on Principles of Programming Languages (San Diego, Calif., Jan. 13-15). ACM, New York, 133-145. Google Scholar
- HORWITZ, S., REPS, T., AND BINKLEY, D 1990. Interprocedural slicing using dependence graphs. ACM Trans. Program. Lang. Syst. 12, i (Jan.), 26-60. Google Scholar
- JIANG, J., ZHOU, X., AND ROBSON, D.J. 1991. Program slicing for C--The problems in implementation. In Proceedings Conference on Software Maintenance (Sorrento, Italy, Oct. 15-17). IEEE, New York, 182-190.Google Scholar
- KOREL, B. AND LASKI, J. 1988. Dynamic program slicing. Inf. Process. Lett. 29, 3 (Oct.), 155-163. Google Scholar
- LANDI, W., RYDER, B. G., AND ZHANG, S. 1993. tnterprocedural modification side effect analysis with pointer aliasing. In Proceedings of the SIGPLAN '93 Conference on Programming Language Design and Implernentatwn. ACM SIGPLAN Not. 28, 6 (June), 56-67. Google Scholar
- LIVADAS, P. E. AND RoY, P.K. 1992. Program dependence analysis. In Proceedings Conference on Software Maintenance (Orlando, Fla., Nov. 9-12). IEEE, New York, 356-365.Google Scholar
- OTTENSTEIN, K. J. AND OTTENSTEIN, L.M. 1984. The program dependence graph in a software development environment. In Proceedings of the ACM SIGSOFT/SIGPLAN Symposium on Practical SDEs. ACM SIGPLAN Not. 19, 5 (May), 177-184. Google Scholar
- VENKATESH, G.A. 1990. The semantic approach to program slicing. In Proceedings SIGPLAN 91 Conference on Programming Language Design and Implementation. ACM SIGPLAN Not. 26, 6 (June), 107-119. Google Scholar
- WEIHL, W.E. 1980. Interprocedural data flow analysis in the presence of pointers, procedure variables and label variables. In Proceedings 7th ACM Symposium on Principles of Programming Languages (Las Vegas, Nev., Jan. 28-30). ACM, New York, 83-94. Google Scholar
- WEISER, M. 1984. Program slicing. IEEE Trans. Softw. Eng. SE-IO, 4 (July), 352-357.Google Scholar
Index Terms
- Experimental results from dynamic slicing of C programs
Recommendations
A brief survey of program slicing
Program slicing is a technique to extract program parts with respect to some special computation. Since Weiser first proposed the notion of slicing in 1979, hundreds of papers have been presented in this area. Tens of variants of slicing have been ...
Abstract program slicing: from theory towards an implementation
ICFEM'10: Proceedings of the 12th international conference on Formal engineering methods and software engineeringIn this paper we extend the formal framework proposed by Binkley et al. for representing and comparing forms of program slicing. This framework describes many well-known forms of slicing in a unique formal structure based on (abstract) projections of ...
Static and Dynamic Slicing of Constraint Logic Programs
Slicing is a program analysis technique originally developed for imperative languages. It facilitates understanding of data flow and debugging.
This paper discusses slicing of Constraint Logic Programs. Constraint Logic Programming (CLP) is an emerging ...
Reviews
R. Clayton
Given an execution of a program and a variable in the program, what are all the statements that affected the variable during the program's execution__?__ Questions of this kind can be answered by a program analysis technique called dynamic slicing. This paper presents the results of applying a dynamic slicing tool to production programs. The tool can extract eight types of slices, and was applied exhaustively to nine programs written in C. The results are characterized by the time and space required per slice compar<__?__Pub Caret>ed to the type of the slice and the variable's function (for example, input parameter or loop index) within the program. Taken together, the results indicate that the time and space overhead for slicing would be acceptable in situations where slicing may have some use. The paper is well written and self-contained, although practitioners will probably want to consult the references for more details about the dynamic slicing tool.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments