Primary initial goal of slicing was to assist with debugging.
Programmers naturally form program slices,mentally, when they debug and understand programs.
A program slice consists of the parts of a program that potentially affect the values computed at some point of interest (slicing criteria).
Example
Example
Slicing criterion: (8,z)
Which statements have a direct or inderect effect on variable z.
Backward slice consists of all statements that the computation at the slicing criteria may depend on.
Forward slice includes all statements depending on the slicing criterion.
Static slice: all possible executions of the program are taken into account.
Dynamic slice is constructed with respect to only one execution of the program (iteration number is taken into account).
Dynamic slicing criteria: (x,i,V,k).
Example (_,8,z,2)
Slicing methods
Weiser’s original approach: iteration of dataflow equations (executable slices)
The most popular approaches are based on dependency graphs (non-executable slices)
Slicing is a simple graph reachability problem
Program Dependence Graph
Interprocedural Slicing (Calling context problem)
Interprocedural Slicing (Calling context problem)
Interprocedural Slicing (Calling context problem)
Summary edges represent the transitive dependences due to procedure calls.
Slices are computed by doing a two phase traversing on the System Dependence Graph.
The main problem is the effective computation of the summary edges.
Forgács I, Gyimóthy T: An Efficient Interprocedural Slicing Method for Large Programs, Proceedings of SEKE'97, the 9th International Conference on Software Engineering & Knowledge Engineering, 1997, Madrid, Spain, pp2287
Gyimóthy, T., Paakki, J.: Static Slicing of Logic Programs, Proceedings of AADEBUG'95, 2nd International Workshop on Automated and Algorithmic Debugging, St. Malo, France, 22-24 May 1995, IRISA/INSA, (Ed. Ducassé, M.), pp. 85-105
Gy. Szilágyi, J. Maluszynski and T. Gyimóthy. Static and Dynamic Slicing of Constraint Logic Programs. Journal Of Automated Software Engineering, 9 (1), 2002, pp. 41-65.
Binary programs
Á. Kiss, J. Jász and T. Gyimóthy. Using Dynamic Information in the Interprocedural Static Slicing of Binary Executables. Software Quality Journal, 13 (3), September 2005, pp. 227-245, Springer Science Business Media, 2005.
Java programs
Kovács Gy, Magyar F, Gyimóthy T: Static Slicing of JAVA Programs, Proceedings of SPLST'97, Fifth Symposium on Programming Languages and Software Tools, Jyväskylä, 7-9 June 1997, Finland, pp. 116-128
Difficult slicing problems
Slicing arrays
Precise slice requires distinquishing the elements of arrays (dependence analysis).
Slicing pointers
Two or more variables refer to the same memory location (aliasing problem).
Dynamic Slicing
Only one execution is taken into account.
Korel&Laski proposed a data-flow approach to compute dynamic slices.(executable slices)
Agrawal&Horgan developed an approach for using dependence graphs to compute non-executable slices.(size problem)
Dynamic Dependence Graph
Dynamic slicing
Forward global computation of dynamic slices
Gyimóthy T, Beszédes Á, Forgács I: An Efficient Relevant Slicing Method for Debugging. In Proceedings of the Joint 7th European Software Engineering Conference and 7th ACM SIGSOFT International Symposium on the Foundations of Software Engineering (ESEC/FSE'99),
Beszédes Á, Gergely T, Szabó ZsM, Csirik J, and Gyimóthy T: Dynamic Slicing Method for Maintenance of Large C Programs, In: Proceedings of the 5th European Conference on Software Maintenance and Reengineering (CSMR 2001), (Eds Sousa P, Ebert J), IEEE Computer Society, 2001, pp 105-113, Lisbon, Portugal, March 14-16, 2001. Certified as the best paper of the conference.
Relevant slicing
1. x=1
2. i=0
3. if i>0 then
4. x=2
5. z=x
Gyimóthy T, Beszédes Á, Forgács I: An Efficient Relevant Slicing Method for Debugging. In Proceedings of the Joint 7th European Software Engineering Conference and 7th ACM SIGSOFT International Symposium on the Foundations of Software Engineering (ESEC/FSE'99)
Union slices
Union slice is the union of dynamic slices for a set of test cases.
Á. Beszédes, Cs. Faragó, Zs. M. Szabó, J. Csirik and T. Gyimóthy. Union Slices for Program Maintenance. Proceedings of the International Conference on Software Maintenance (ICSM 2002), Montréal, Canada, October 3-6, 2002, IEEE Computer Society, 2002, pp. 12-21
David Binkley, Sebastian Danicic, Tibor Gyimóthy, Mark Harman, Ákos Kiss, and Bogdan Korel. A Formalisation of the Relationship between Forms of Program Slicing. Science of Computer Programming, 2006. Accepted for publication.
David Binkley, Sebastian Danicic, Tibor Gyimóthy, Mark Harman, Ákos Kiss, and Bogdan Korel. Theoretical Foundations of Dynamic Program Slicing. Theoretical Computer Science, 2006. Accepted for publication.
Dave Binkley, Sebastian Danicic, Tibor Gyimóthy, Mark Harman, Ákos Kiss, and Bogdan Korel. Minimal Slicing and the Relationships between Forms of Slicing. In Proceedings of the 5th IEEE International Workshop on Source Code Analysis and Manipulation (SCAM 2005), pages 45-54, September 30 - October 1, 2005. Best paper award.
Dave Binkley, Sebastian Danicic, Tibor Gyimóthy, Mark Harman, Ákos Kiss, and Lahcen Ouarbya. Formalizing Executable Dynamic and Forward Slicing. In Proceedings of the 4th IEEE International Workshop on Source Code Analysis and Manipulation (SCAM 2004), pages 43-52, September 15-16, 2004.IEEE Computer Society, 2004.
Background
Informally:
A static slice preserves a projection of the semantics of the original program for all possible inputs.
A dynamic slice preserves the effect of the program for a fixed input.
Thus, a static slice is expected to be a valid (even if an overly large) dynamic slice.
Counter Example
1 x = 1;
2 x = 2;
3 if (x>1)
4 y = 1;
5 else
6 y = 1;
7 z = y;
Original program
Counter Example
1 x = 1;
2 x = 2;
3 if (x>1)
4 y = 1;
5 else
6 y = 1;
7 z = y;
The original program
Explanation
The reason is in the details of the definitions.
Static slicing, as defined by Weiser, does not care about the path of execution.
Dynamic slicing of Korel & Laski requires the path to be same in the original program and in the slice.
Motivation
So, our „common knowledge” does not fit to the original definitions.
We have to find out why?
Thus, we provide a formal theory, which helps us to answer this question, i.e., which helps us to compare existing slicing techniques.
The Program Projection Theory
Syntactic ordering (≤)
A partial order on programs.
Describes a property slicing minimizes on.
Semantic equivalence (≈)
An equivalence relation on programs.
Describes a property slicing keeps invariant.
Projection ((≤,≈)) describes slicing.
Syntactic Orderings
Traditional sytanctic ordering (≤): a program qis smaller than p if it can be obtained by deleting statements from p.
Other orderings are possible, e.g., amorphous slicing uses an ordering based only on the number of statements.
Semantic Equivalences
Can be defined by parameterizing a „unified equivalence relation”, U(S,V,P,X), which compares projections of state trajectories.
S: the set of initial states for which the trajectories have to be equal.
V: the set of variables of interest.
P: the set points of interest in the trajectory (line number and occurance of statement of interest).
X: a function on a pair of programs, determining which statements shall be kept in the trajectory (this captures the trajectory requirement of K&L).
Instantiations of the Framework
Parameterizations of a unified equivalence relation.
S(V,n) = U(Σ,V,{n}N,ε)
DKLi(σ,V,n(k)) = U({σ},V,{n(k)},)
Example
Tp=(1,{})(2,{x=1})(3,{x=2})(4,{x=2})(7,{x=2,y=1})
Tq=(1,{})(3,{x=1})(6,{x=1})(7,{x=1,y=1})
Example
∏S(Tp)=(7,{y=1})
∏S(Tq)=(7,{y=1})
Example
∏D(Tp)=(1,_)(3,_)(4,_)(7,{y=1})
∏D(Tq)=(1,_)(3,_)(6,_)(7,{y=1})
Comparison
Once the formal descriptions of slicing techniques is available, they can be compared.
Subsumes relation: A-slicing subsumes B-slicing iff all B-slices are valid A-slices as well.
Subsumes Relation
Minimal Slices
We moved on to investigate another relation between slicing techniques: which have smaller minimal slices than the others.
Slice minimality is defined in terms of the syntactic ordering.
Ranking slicing techniques: A-slicing is of lower (or equal) rank than B-slicing iff for all minimal B-slices there exists a smaller minimal (or equal) A-slice.
Rank Relation
Example
There is no minimal KL-dynamic slice, which is smaller than or equal to the second minimal static slice.
Relations
We found (and proved) that rank is the dual concept of subsumes relationship.
If a slicing subsumes another one then it is of lower rank.
Summary of Results
Static slicing and KL-dynamic slicing are incomparable in the subsumes relation (A static slice is not always a valid dynamic slice)
Static slicing and KL-dynamic slicing are incomparable in the rank relation (It is not always possible to find a minimal KL-dynamic slice, which is smaller than, or equal to, a minimal static slice)
Current Challenges
There is no established common notation.
How to deal with non-terminating programs? (Transfinite trajectories? Other solutions?)
Which other slicing techniques can be formalized with this framework?
What operations can we perform on sets of slices and what are their result?
