Experimental results from dynamic slicing of C programs

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.

REFERENCES

• 1: AGRAWAL, H. 1991. Towards automatic debugging of computer programs. Tech. Rep. SERC- TR-103-P, SERC, Purdue Univ., West Lafayette, Ind. Aug.
• 2: Hiralal Agrawal , Joseph R. Horgan, Dynamic program slicing, ACM SIGPLAN Notices, v.25 n.6, p.246-256, Jun. 1990
• 3: Thomas Ball , James R. Larus, Optimally profiling and tracing programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.4, p.1319-1360, July 1994 [doi>10.1145/183432.183527]
• 4: Keith D. Cooper, Analyzing aliases of reference formal parameters, Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.281-290, January 14-16, 1985, New Orleans, Louisiana, United States [doi>10.1145/318593.318658]
• 5: K. D. Cooper , K. Kennedy, Fast interprocedual alias analysis, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.49-59, January 11-13, 1989, Austin, Texas, United States [doi>10.1145/75277.75282]
• 6: ERNST, M. 1994. Practical fine-grained static slicing of optimized code. Tech. Rep. MSR-TR-94- 14, Microsoft Research, Redmond, Wash.
• 7: S. Horwitz , P. Pfeiffer , T. Reps, Dependence analysis for pointer variables, ACM SIGPLAN Notices, v.24 n.7, p.28-40, July 1989
• 8: 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]
• 9: 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]
• 10: 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.
• 11: 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]
• 12: William Landi , Barbara G. Ryder , Sean Zhang, Interprocedural modification side effect analysis with pointer aliasing, ACM SIGPLAN Notices, v.28 n.6, p.56-67, June 1993
• 13: 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.
• 14: 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
• 15: G. A. Venkatesh, The semantic approach to program slicing, ACM SIGPLAN Notices, v.26 n.6, p.107-119, June 1991
• 16: William E. Weihl, Interprocedural data flow analysis in the presence of pointers, procedure variables, and label variables, Proceedings of the 7th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.83-94, January 28-30, 1980, Las Vegas, Nevada [doi>10.1145/567446.567455]
• 17: WEISER, M. 1984. Program slicing. IEEE Trans. Softw. Eng. SE-IO, 4 (July), 352-357.

INDEX TERMS

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

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.6 Programming Environments
          Subjects: Interactive environments
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers; Optimization

General Terms:
Experimentation, Languages, Performance

Keywords:
program analysis, program slice