Program slicing: Difference between revisions

Revision as of 15:53, 21 September 2010

Latest revision as of 21:33, 16 March 2025

(48 intermediate revisions by 39 users not shown)

Line 1:

{{Short description|Set of software engineering methods}}

{{About|program slicing|other uses of |slicing|Slicing (disambiguation)}}

{{more footnotes|date=August 2012}}

In [[computer programming]], '''program slicing''' is the computation of the set of programsprogram statements, the '''program slice''', that may affect the values at some point of interest, referred to as a '''slicing criterion'''. Program slicing can be used in [[debugging]] to locate source of errors more easily. Other applications of slicing include [[software maintenance]], [[Optimization (computer science)|optimization]], [[Program analysis (computer science)|program analysis]], and [[Non-interference (security)|information flow control]].

Slicing techniques have been seeing a rapid development since the original definition by [[Mark Weiser]]. At first, slicing was only static, i.e., applied on the source code with no other information than the source code. [[Bogdan Korel]] and [[Janusz Laski]] introduced ''dynamic slicing'', which works on a specific execution of the program (for a given execution trace).<ref>{{cite journal |last1=Korel |first1=Bogdan |last2=Laski |first2=Janusz |title=Dynamic Program Slicing |journal=Information Processing Letters |date=1988 |volume=29 |issue=3 |pages=155–163 |doi=10.1016/0020-0190(88)90054-3 |citeseerx=10.1.1.158.9078 }}</ref> Other forms of slicing exist, for instance path slicing.<ref>{{Cite book|last1=Jhala|first1=Ranjit|last2=Majumdar|first2=Rupak|title=Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation |chapter=Path slicing |date=2005|series=PLDI '05|___location=New York, NY, USA|publisher=ACM|pages=38–47|doi=10.1145/1065010.1065016|isbn=9781595930569|s2cid=5065847 }}</ref>

== Static slicing ==

Based on the original definition of Weiser,<ref>{{Cite thesis|last=Weiser|first=Mark David|title=Program Slices: Formal, Psychological, and Practical Investigations of an Automatic Program Abstraction Method|date=1979|degree=PhD Thesis|publisher=University of Michigan|url=https://dl.acm.org/citation.cfm?id=909356|place=Ann Arbor, MI, USA}}</ref> informally, a static program slice S consists of all statements in program P that may affect the value of variable v atin somea pointstatement px. The slice is defined for a slicing criterion C=(x,Vv), where x is a statement in program P and Vv is a subset of variablesvariable in Px. A static slice includes all the statements that can affect the value of variable v at statement x for aany setpossible ofinput. Static slices are computed by backtracking dependencies between statements. More specifically, to compute the static slice for (x,v), we first find all possiblestatements inputsthat atcan directly affect the pointvalue of interestv (i.ebefore statement x is encountered. Recursively, atfor each statement y which can affect the value of v in statement x)., Staticwe compute the slices arefor computedall byvariables findingz consecutivein setsy that affect the value of indirectlyv. relevant statements,The accordingunion toof [[dataall dependency|data]]those andslices controlis dependenciesthe static slice for (x,v).

=== Example ===

<source lang="c">

For example, consider the C program below. Let's compute the slice for ( write(sum), sum ). The value of sum is directly affected by the statements "sum = sum + i + w" if N>1 and "int sum = 0" if N <= 1. So, slice( write(sum), sum) is the union of three slices and the "int sum = 0" statement which has no dependencies:

<ol>

<li>slice( sum = sum + i + w, sum),</li>

<li>slice( sum = sum + i + w, i),</li>

<li>slice( sum = sum + i + w, w), and</li>

<li>{ int sum=0 }.</li>

</ol>

It is fairly easy to see that slice( sum = sum + i + w, sum) consists of "sum = sum + i + w" and "int sum = 0" because those are the only two prior statements that can affect the value of sum at "sum = sum + i + w". Similarly, slice( sum = sum + i + w, i) only contains "for(i = 1; i < N; ++i) {" and slice( sum = sum + i + w, w) only contains the statement "int w = 7".

When we union all of those statements, we do not have executable code, so to make the slice an executable slice we merely add the end brace for the for loop and the declaration of i. The resulting static executable slice is shown below the original code below.

<sourcesyntaxhighlight lang="c">

int i;

int sum = 0;

int product = 1;

int w = 7;
for(i = 01; i < N; ++i) {

sum = sum + i + w;

product = product * i;

}

write(sum);

write(product);

</syntaxhighlight>

</source>

ThisThe newstatic programexecutable isslice afor valid slicing of the above program with respect to the criterioncriteria (<code>write(sum)</code>,{ sum}): is the new program shown below.

<sourcesyntaxhighlight lang="c">

int i;

int sum = 0;

int w = 7;

for(i = 01; i < N; ++i) {

sum = sum + i + w;

}

write(sum);

</syntaxhighlight>

</source>

In fact, most static slicing techniques, including Weiser's own technique, will also remove the <code>write(sum)</code> statement. IndeedSince, at the statement <code>write(sum)</code>, the value of <code>sum</code> is not dependent on the statement itself. Often a slice for a particular statement x will include more than one variable. If V is a set of variables in a statement x, then the slice for (x, V) is the union of all slices with criteria (x, v) where v is a variable in the set V.

== Lightweight forward static slicing approach ==

A very fast and scalable, yet slightly less accurate, slicing approach is extremely useful for a number of reasons. Developers will have a very low cost and practical means to estimate the impact of a change within minutes versus days. This is very important for planning the implementation of new features and understanding how a change is related to other parts of the system. It will also provide an inexpensive test to determine if a full, more expensive, analysis of the system is warranted. A fast slicing approach will open up new avenues of research in metrics and the mining of histories based on slicing. That is, slicing can now be conducted on very large systems and on entire version histories in very practical time frames. This opens the door to a number of experiments and empirical investigations previously too costly to undertake.<ref>{{Cite journal|last1=Alomari|first1=Hakam W.|last2=Collard|first2=Michael L.|last3=Maletic|first3=Jonathan I.|last4=Alhindawi|first4=Nouh|last5=Meqdadi|first5=Omar|date=2014-05-19|title=srcSlice: very efficient and scalable forward static slicing|journal=Journal of Software: Evolution and Process|language=en|volume=26|issue=11|pages=931–961|doi=10.1002/smr.1651|issn=2047-7473|citeseerx=10.1.1.641.8891|s2cid=18520643 }}</ref>

== Dynamic slicing ==

MakesDynamic slicing makes use of information about a particular execution of a program. A dynamic slice contains all statements that actually affect the value of a variable at a program point for a particular execution of the program rather than all statements that may have affected the value of a variable at a program point for any arbitrary execution of the program.

An example to clarify the difference between static and dynamic slicing. Consider a small piece of a program unit, in which there is an iteration block containing an if-else block. There are a few statements in both the <code>if</code> and <code>else</code> blocks that have an affecteffect on a variable. In the case of static slicing, since we look at the whole program unit is looked at irrespective of a particular execution of the program, the affected statements in both blocks would be included in the slice. But, in the case of dynamic slicing we consider a particular execution of the program, wherein the <code>if</code> block gets executed and the affected statements in the <code>else</code> block do not get executed. So, that is why in this particular execution case, the dynamic slice would contain only the statements in the <code>if</code> block.

==See also==

Line 46 ⟶ 64:

* [[Data dependency]]

* [[Frama-C]] a tool which implements slicing algorithms on [[C program]]s.

* [[Partial dead code elimination]]

== Notes ==

{{reflist}}

== References ==

* [[Mark Weiser]]. "Program slicing". Proceedings of the 5th International Conference on Software Engineering, pages 439&ndash;449, [[IEEE Computer Society]] Press, March 1981.

* [[Mark Weiser]]. "Program slicing". IEEE Transactions on Software Engineering, Volume 10, Issue 4, pages 352&ndash;357, [[IEEE Computer Society]] Press, July 1984.

* [[Susan B. Horwitz|Susan Horwitz]], [[Thomas W. Reps|Thomas Reps]], and David Binkley, Interprocedural slicing using dependence graphs, ACM Transactions on Programming Languages and Systems, Volume 12, Issue 1, pages 26-60, January 1990.

* Frank Tip. "A survey of program slicing techniques". Journal of Programming Languages, Volume 3, Issue 3, pages 121–189, September 1995.

* David Binkley and Keith Brian Gallagher. "Program slicing". Advances in Computers, Volume 43, pages 1–50, [[Academic Press]], 1996.

Line 56 ⟶ 79:

* David Binkley and Mark Harman. "A survey of empirical results on program slicing", Advances in Computers, Volume 62, pages 105-178, [[Academic Press]], 2004.

* Jens Krinke. "Program Slicing", In Handbook of Software Engineering and Knowledge Engineering, Volume 3: Recent Advances. [[World Scientific Publishing]], 2005

* Silva, Josep. "A vocabulary of program slicing-based techniques", ACM Computing Surveys, Volume 44, Issue 3, [[Association for Computing Machinery]], June 2012

*[http://www.users.miamioh.edu/alomarhw/ Alomari HW] et al. "srcSlice: very efficient and scalable forward static slicing". [https://onlinelibrary.wiley.com/journal/20477481 Wiley Journal of Software: Evolution and Process] ('''JSEP'''), DOI: 10.1002/smr.1651, Vol. 26, No. 11, pp. 931-961, 2014.

==External links==

Line 61 ⟶ 86:

* [http://indus.projects.cis.ksu.edu/index.shtml Indus Project] (part of Bandera checker)

* [http://www.cs.wisc.edu/wpis/html/ Wisconsin Program-Slicing Project]

* [[Softwaremining | SoftwareMining]] Extracting Business Rules/Program Slices from COBOL programs. (Web: [http://www.softwaremining.com/ www.softwaremining.com])

{{Program analysis}}

[[Category:Debugging]]

[[Category:CompilerProgram optimizationsanalysis]]

[[Category:Program transformation]]

[[Category:Software maintenance]]

{{software-eng-stub}}

[[de:Slicing]]

[[es:Rebanamiento estático]]

[[mk:Статично сечење]]