|
|
The semantic perspective distinguishes the difference on the behaviors of the computed criteria on certain input. A static behavior is preserved by static slicing criteria and a dynamic behavior is preserved by dynamic criteria. The difference is, static slicing works by statically examining the code without actually executing the program, while dynamic slicing dynamically analyzes the code by executing the program with a given input. A dynamic slice is concerned with finding all statements that did affect its value for the current input, but not all the statements that could influence the value of the variable for any inputs.
A static slicing is constructed by deleting those parts of the program that are
irrelevant to the values stored in the chosen set of variables at the chosen point of
interest. A point of interest in other words, a statement to be sliced, can be
mathematically represented by given variable v and a point of interest at line n.
This is called the slicing criterion, constructed for v at line n, and is
expressed as (n,V ), where s is the slice we are interested in, [1, 4] e.g. (8,x)
represents the slicing criteria on variable x at line 8. A program slice is
then computed by removing statements that have no effects to the slice
criterion.
In order to choose a slicing criterion, there are two approaches to consider, a
backward slicing or a forward slicing.
A backward slice is defined to contain the statements of the program that are
affecting the slicing criterion. In practice, the backward approach can be used in
locating the bug by examining all previously executed statements with respect to
a variable v at statement n, where output of v is found incorrect at that
point.
To see how static slicing works, consider the following pseudo code example:
|
The PDG diagram of the example is shown in next page. The for-statement in line 4
depends on variable x, declared in the 1st statement. Value of z in line 5 relies on
its initial declaration at the 3rd statement, for-loop statement at the 4th
statement and manipulation of y in the 6th statement. Finally, the output of y in
line 8 is affected by all statements related to y in statements 2, 4 and
6.
Assume we are only interested in effect of this piece of code upon variable y. We
can now construct a backward slicing on y in line 8. All statements that
have some affect on y are preserved in the slice. The result is shown
below:
|
In contrast, a forward slice contains those statements of the program which are
affected by the slicing criterion. A practical application of forward slicing can
be used on keeping track of regression bugs due to a fix being made to
the statement that was previously buggy and now becomes our slicing
criterion.
Assume now we change our focus on affects upon changing variable y in line 2,
and we construct a forward slicing on y. All statements that are effected by y are
preserved:
|
Please note that variable of x has no direct affect upon y and z. However, since x is used in the for statement, thus it must be included due to the range of influence on y and z.
Dynamic slicing is constructed with respect to an growing slicing criterion, containing with a sequence of inputs, which cause the program to go wrong for a particular execution. The slices preserve the effect of the original program on v at n, when the program is executed with the input sequence I =< i1,i2,… >[3]. Consider the following example of Algorithm 4.2, and the PDG diagram of the example is shown below it. User input variable n controls loop statement in line 4. Both s and p are depends on their initial declaration and for-loop statement in statement 4.
|
The goal of this program is to calculate the sum and product from 1 to n.
Apparently, the sum would yield correct result, but product would go
wrong.
A static slice on p would only simplify the program, but is not powerful enough
to help us find the bug.
|
Next, we construct a dynamic slice upon p. Since p keeps multiplying i
from itself, which is always a 0. Thus, the only value that p would get
is 0. Thus, the sequence of p corresponding to each given input is
< 0,(0 ⋅ 0),…,(
n times) >. Dynamic slices will give us the result of
p = 0:
|
Hence, a bug is thus detected using dynamic slicing approach.
Consequently, dynamic slicing is more useful than static slicing for testing and
debugging. However, static slicing is still useful for some application, such as
program comprehension, reusing, or maintenance, where the slice has
to cover every possible executions. On the other hands, static slicing
needs larger space to perform. This contradiction highlights the trade-off
between the static and dynamic methods. Static slicing needs more resource
to perform, but will perform every possible execution of the original
program; dynamic slicing needs less space, but will execute for a particular
execution.
Despite of the two extremes of static and dynamic approaches, conditioned
slicing is another form of slicing that bridges the gap of static and dynamic
slicing. The conditioned slicing criterion include the set of states in which the
program is to executed, allowing the programmer to specify, not only the
variables of interests, but also the initial conditions of interest. Any statements,
which we know it will not execute, may be omitted afterwards. This not only
shows the initial awareness of knowledge about the condition in which the
program is to be executed, but also has the advantage that it allows for
additional simplification during slice construction. This characteristics is
practically used in a tool-assisted form of analysis a program by cases (one per
condition), and makes it attractive as a supporting technique for program
comprehension.
