Program Slicing: Theory and Practice Tibor Gyimóthy



Yüklə 445 b.
tarix28.10.2017
ölçüsü445 b.
#18780


Program Slicing: Theory and Practice

  • Tibor Gyimóthy

  • Department of Software Engineering

  • University of Szeged


Co-authors

  • Árpád Beszédes

  • David Binkley(USA)

  • Bogdan Korel(USA)

  • János Csirik

  • Sebastian Danacic(UK)

  • Csaba Faragó

  • István Forgács

  • Peter Fritzson(S)

  • Tamás Gergely

  • Tamás Horváth

  • Mark Harman(UK)



Motivation

  • 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



Slicing approaches for programming languages

  • Logic programs

  • 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



Union slices



Applications

  • Debugging

  • Regression testing

  • Software maintenance

    • Architecture reconstruction
    • Identify reusable functions
    • Reverse engineering
    • Slice metrics
    • Program comprehension


Theory of program slicing

  • 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 q is 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)

  • Subsumes and rank are dual concepts

  • 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?

  • How do these results apply to schemas?



Yüklə 445 b.

Dostları ilə paylaş:




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©muhaz.org 2024
rəhbərliyinə müraciət

gir | qeydiyyatdan keç
    Ana səhifə


yükləyin