Program slicing

ABSTRACT

Program slicing is a method used by experienced computer programmers for abstracting from programs. Starting from a subset of a program's behavior, slicing reduces that program to a minimal form which still produces that behavior. The reduced program, called a “slice”, is an independent program guaranteed to faithfully represent the original program within the domain of the specified subset of behavior.

Finding a slice is in general unsolvable. A dataflow algorithm is presented for approximating slices when the behavior subset is specified as the values of a set of variables at a statement. Experimental evidence is presented that these slices are used by programmers during debugging. Experience with two automatic slicing tools is summarized. New measures of program complexity are suggested based on the organization of a program's slices.

References

1. 1.Aho, A.V. and Ullman, J.D. 1977 Principles of Compiler Design. Addison-Wesley, 1977.
2. 2.Arsac, J.J. 1979 Syntactic Source to Source TransformaHs and Program Manipulation. CACM 22, 1 (Jan. 1979) pp. 43-53.
3. 3.Ashcroft and Manna 1973 The Translation of GOTO Programs into WHILE programs. Information Processing 71, North Holland Pub. Co. Amsterdam, pp. 250-255.
4. 4.Aygun, B.O. 1973 Dynamic analysis of execution: possibilities, techniques, and problems. PhD thesis, Carnegie-Mellon University Sept. 1973.
5. 5.Baker, B. 1977 An Algorithm for Structuring Flowgraphs. JACM 24, 1 (Jan. 1977) pp. 98-120.
6. 6.Barth, J.M. 1978 A Practical Interprocedural Dataflow Analysis Algorithm. CACM 21, 9 (Sept. 1978) pp. 724-736.
7. 7.Basili, V.R. 1976 The design and implementation of a family of application-oriented languages. Fifth Texas Conference on Computing Systems. pp. 6-12.
8. 8.Browne, J.C. and Johnson, D.B. 1978 FAST: A second generation program analysis system. Third int'l conference on software engineering. IEEE catalog no. 78CH1317-7C. May 1978. pp. 142-148.
9. 9.Denning, D.E. and Denning, P.J. 1977 Certification of programs for secure information flow. CACM 20, 7 (July 1977) pp. 504-513.
10. 10.Fosdick. L.D. and Osterweil, L.J. 1976 Data Flow Analysis in Software Reliability. ACM Computing Surveys 8, 3 (Sept. 1976) pp. 305-330.
11. 11.Gannon, J.D. and Rosenberg, J. 1979 Implementing data abstraction features in a stack-based language. Software-Practice and Experience, Vol. 9, pp. 547-560.
12. 12.Gerhart, S. 1975 Correctness Preserving Program Transformations. Second Conference on the Principles of Programming Languages. ACM (Jan. 1975) pp. 54-66.
13. 13.Gould, J.D. and Drongowski, P. 1974 An Exploratory Study of Computer Program Debugging. Human Factors 1, 6. pp. 258-277.
14. 14.Graham, S.L., and Wegman, M. 1976 A fast and usually linear algorithm for global flow analysis. JACM 23, 1. January 1976, pp. 172-202.
15. 15.Halstead, M. 1977 Elements of Software Science. Elsevier Computer Science Library. 1977.
16. 16.Hecht, M.S. 1977 Flow Analysis of Computer Programs. North-Holland (1977).
17. 17.IBM 1968 Scientific Subroutine Package (PL/I). 360-ACM-07X. Program Description and Operations Manual. Form 6H20-0586-0.
18. 18.Lengauer, T. and Tarjan, R.E. 1979 A fast algorithm for finding dominators in a flowgraph. ACM T. on Prog. Lan. and Systems, Vol 1, no. 1 July 1979, pp. 121-141.
19. 19.Liskov, B.H. and Zilles, S.N. 1975 Specification techniques for data abstractions. IEEE Trans of Software Engineering. March 1975.
20. 20.Loveman, D.B. 1977 Program Improvement by Source to Source Transformation. JACM 24, 1 (Jan. 1977) pp. 121-145.
21. 21.Luckham, D.C. and Suzuki, N. 1979 Verification of array, record, and pointer operations in Pascal. ACM T. on Prog. Lan. and Systems, Vol. 1, no. 2 Oct. 1979, pp. 226-244.
22. 22.McCabe, Thomas J. 1976 A Complexity Measure. IEEE Transactions on Software Engineering. SE-2,
23. 23.Parnas, D.L. 1972 On the criteria used in decomposing systems into modules. CACM 15, 12 (Dec. 1972) pp. 1053-1058.
24. 24.Schwartz, J.T. 1971 An overview of bugs. in Debugging techniques in large systems. Rustin, Randall, ed. Prentice-Hall.
25. 25.Shneiderman, B. 1976 a Exploratory Experiments in Programmer Behavior. International J. of Computer and Information Sciences, 5, 2.
26. 26.Stay, J.F. 1976 HIPO and integrated program design. IBM systems journal.
27. 27.Tarjan, R.E. and Valdes, J. 1980 Prime subprogram parsing of a program. Seventh annual ACM symposium on the principles of programming languages. Jan. 1980, pp. 95-105.
28. 28.U.S.D.O.D. 1979 Preliminary Ada reference manual and rationale. Sigplan notices 14, 6.
29. 29.Wegbreit, Ben 1976 Goal-directed program transformation IEEE Transactions on Software Engineering. Vol SE-2, 2 (June 1976) pp. 69-80.
30. 30.Weihl, W.E. 1980 Interprocedural data flow analysis in the presence of pointers, procedure variables and label variables. Seventh ACM Symposium on the Principles of Programming Languages pp. 83-94.
31. 31.Weiser, M.D. 1979 Program Slices: Foraml Psychological, and Practical Investigations of an Automatic Program Abstraction Method. Ph.D. Thesis, Computer and Communication Sciences Dept., University of Michigan.
32. 32.Weiser, M.D. 1980 Color dominance: a new graph coloring program with applications to computer program optimization. In preparation.
33. 33.Zelkowitz, M.W., Shaw, A.C., and Gannon, J.D. 1979 Principles of software engineering and design. Prentice-Hall.

Index Terms

• Software and its engineering

  • Software creation and management

    • Designing software

      • Software implementation planning

        • Software design techniques

    • Software development process management

    • Software verification and validation

      • Empirical software validation

      • Software defect analysis

        • Software testing and debugging

  • Software organization and properties

    • Software functional properties

      • Formal methods