Softpanorama (slightly skeptical) Open Source Software Educational Society

May the source be with you, but remember the KISS principle ;-) Softpanorama Search

Program Slicing as Decomplation/Program Reconstruction Technique

The concept of program slicing was introduced by Mark Weiser (Computer Science Department University of Maryland College Park, MD 20742). In his paper he noted:

Program slicing is a method used by experienced computer programmers for abstracting from pro- grams. 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.

Slicing is applied to programs after they are written, and is therefore useful  reconstruction of the logic of the program. Slicing starts with the observation that these are times when only a portion of a program's produces a subset of  program behavior that needs to be understood, improved or replaced. In these cases, a programmer starts from the program behavior and proceeds to find and modify the corresponding portions of program code. Code not having to do with behavior of interest is ignored.

A programmer maintaining a large, unfamiliar program would almost have to use this behavior- first approach to the code. Understanding an entire system to change only a small piece would take too much time. Since most program maintenance is done by persons other than the program designers, and since 67% of programming effort goes into maintenance (Zelkowitz, Shaw, and Gannon 1979), decomposing programs by behavior must be a common occurrence. Automatic slicing requires that behavior be specified in a certain form. If the behavior of interest can be expressed as the values of some sets of variables at some set oi statements, then this specification is said to be a criterion. Dataflow analysis (Hecht 1977] can find all the program code which might have influenced the specified behavior, and this code is called a slice of the program. A slice is itself an executable program, whose behavior must be identical to the specified subset of the original program's behavior. Figure 1 gives examples of some slicing criteria and their corresponding slices.  There are usually many different slices for a given program and slicing criterion, depending on how minimal a slice is desired. The issue of minimality  is discussed further below. There is always at least one slice--the program  itself. The interesting slices are the ones which, compared to the original program, are significantly smaller and simpler.

 

Dr. Nikolai Bezroukov

Old News ;-)

IBM Program Analysis, Transformation and Visualization Group

• T.B. Dinesh and Frank Tip, A Slicing-Based Approach for Locating Type Errors, To appear in Proceedings of USENIX Conference on Domain-Specific Languages (DSL'97), (Santa Barbara, CA, October 15-17 1997).
• Frank Tip and Peter F. Sweeney, Class Hierarchy Specialization, To appear in Proceedings of the Twelfth Annual Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA'97), (Atlanta, GA, October 5-9 1997).
• G. Ramalingam, On Sparse Evaluation Representations, To appear in the Proceedings of the Fourth International Static Analysis Symposium, (Paris, France, September, 1997).
• G. Ramalingam and Harini Srinivasan, A Member Lookup Algorithm for C++, In Proceedings of the ACM SIGPLAN '97 Conference on Programming Language Design and Implementation, (Las Vegas, NV, June 15-18, 1997), pp.18-30.
• Frank Tip, Jong-Deok Choi, John Field, and G. Ramalingam, Slicing class hierarchies in C++, In Proceedings of the Eleventh Annual Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA'96), (San Jose, CA, October 6-10, 1996), pp. 179-197.
• J.A. Bergstra, T.B. Dinesh, John Field, and J. Heering, A Complete Transformational Toolkit for Compilers, In Proceedings of the European Symposium on Programming (ESOP'96), (Linkoping, Sweden, April 1996), Springer-Verlag LNCS Vol. 1058, extended version to appear in ACM Transactions on Programming Languages and Systems.
•  Frank Tip, A survey of program slicing techniques, Journal of Programming Languages 3(3), (1995), 121-189.
•  A Log N Line Crossing Algorithm for Levelled Graphs, Vance Waddle and A. Malhotra IBM Research Report RC 20685
•  G. Ramalingam, Bounded Incremental Computation, Lecture Notes in Computer Science, Vol. 1089, Springer-Verlag (1996). (A revised version of Ramalingam's Ph.D. Thesis.)
•  G. Ramalingam, Data Flow Frequency Analysis, In Proceedings of the ACM SIGPLAN '96 Conference on Programming Language Design and Implementation, (Philadelphia, PA, May 21-24, 1996), pp.267-277.
•  John Field, G. Ramalingam, and Frank Tip, Parametric program slicing, In Conference Record of the Twenty-Second ACM Symposium on Principles of Programming Languages , (San Francisco, CA, January 23-25, 1995), pp. 379-392.

[PPT] Static Analysis for Software-Engineering Tools: Problems and ...

[July 17, 1999] Thomas W. Reps's Home Page

[July 7, 1999] Program Slicing -- [updated link -- page was moved] nice page that is actively maintained by Jens Krinke (jkrinke@gmx.de)

• Projects

• Bibliography

• People

Program Slicing Internet Resources

Slicing References

Home page of the Wisconsin Program-Slicing Project 

Recommended Links

---

In case of broken links please try to use Google search. If you find the page please notify us about new location

• A Survey of Program Slicing Techniques - Tip (ResearchIndex)

  Abstract: A program slice consists of the parts of a program that (potentially) affect the values computed at some point of interest, referred to as a slicing criterion. The task of computing program slices is called program slicing. The original definition of a program slice was presented by Weiser in 1979. Since then, various slightly different notions of program slices have been proposed, as well as a number of methods to compute them. An important distinction is that between a static and a dynamic... (Update)

• Constructing Control Flow From Control Dependence - Ball, Horwitz (ResearchIndex)

  This paper addresses the inverse problem: we define an algorithm that, given a control dependence graph C, finds a corresponding control-flow graph G (i.e., a graph G such that CDG(G) is isomorphic to C), or determines that no such control-flow graph exists. We call this process CDG-reconstitution (Update)

• Measuring Functional Cohesion - Bieman, Ott (1994)   (24 citations)  (Correct)

  ....is based on data flow analysis. It is suggested in [27] that a program depen dence graph representation can be used to compute slices more eciently and precisely. An algorithm for computing slices using a program dependence graph representation is presented by Horwitz, Reps, and Binkley [16] [31]. A slice is obtained by walking backwards over the program dependence graph to obtain all nodes which have an effect on the value of the variable of interest. Similarly, a forward slice [16] can be obtained by walking forward over the program dependence graph to obtain all nodes which are ....
   

• Reasoning Systems - software reverse engineering for COBOL and legacy systems. Program slicing and parsing.
• Postscript Versions of Selected Papers -- large collection of papers
• Binkley, D., Precise executable interprocedural slices. ACM Letters on Programming Languages and Systems 2, 1-4 (1993), 31-45.
• Binkley, D., and Gallagher, K., Program slicing. Advances in Computers, Vol. 43, M. Zelkowitz (ed.), Academic Press, San Diego, CA, 1996.
• Horwitz, S., Prins, J., and Reps, T., Integrating non-interfering versions of programs. ACM Transactions on Programming Languages and Systems 11, 3 (July 1989), 345-387.
• Horwitz, S. and Reps, T., The use of program dependence graphs in software engineering. In Proceedings of the Fourteenth International Conference on Software Engineering, (May 11-15, 1992, Melbourne, Australia), ACM, New York, NY, 1992, pp. 392-411.
• Horwitz, S., Reps, T., and Binkley, D., Interprocedural slicing using dependence graphs. ACM Transactions on Programming Languages and Systems 12, 1 (January 1990), 26-60.
• Reps, T., Horwitz, S., Sagiv, M., and Rosay, G., Speeding up slicing. In SIGSOFT '94: Proceedings of the Second ACM SIGSOFT Symposium on the Foundations of Software Engineering, (New Orleans, LA, December 7-9, 1994), ACM SIGSOFT Software Engineering Notes 19, 5 (December 1994), pp. 11-20.
• Reps, T. and Rosay, G., Precise interprocedural chopping. In SIGSOFT '95: Proceedings of the Third ACM SIGSOFT Symposium on the Foundations of Software Engineering, (Washington, DC, October 10-13, 1995), ACM SIGSOFT Software Engineering Notes 20, 4 (1995), pp. 41-52.
• Static Slicing of Threaded Programs - Static program slicing is an established method for analyzing sequential programs, especially for program understanding, debugging and testing

In Memoriam Mark Weiser -- pioneer of program slicing

• The Wisconsin Program-Slicing Tool Version 1.0.1
• The Unravel Program Slicing Tool
• Microsoft Research's Program Analysis project

• The Ghinsu Project - An Xwindows program slicing tool - static and dynamic analysis.

• C Metrics
• C++ Program Analyzers
• Graph Drawing Tools
• Lexical Analysis
• Program Slicing (Mark)
• Resources for Programming Language Research
• Program Slicing Material
• Program Understanding Tools Directory (Related)
• Program Slicing Internet Resources
• Program Comprehension and Software Reengineering
• Static Slicing of Threaded Programs
• Identifying Reusable Functions Using Specification Driven Program Slicing A Case Study
• I&ST Special Issue on Program Slicing
• LiEP CIS-1997-009-05 Application of Dynamic Slicing in Program Debugging.
• Juergen Rilling's Program Slicing Home Page
• Amorphous Program Slicing
• Understanding Function Behaviors through Program Slicing ( 7-Sep-1995)