arXiv:1407.4917v1 [cs.SE] 18 Jul 2014

Sliced Slices: Separating Data and Control Influences
Shrawan Kumar

Amitabha Sanyal

Uday P. Khedker

Tata Research Design
and Development Centre
Tata Consultancy Services Ltd,
Pune, India
Email: shrawan.kumar@tcs.com

Department of Computer Science
and Engineering
Indian Institute of Technology Bombay,
India
Email: as@cse.iitb.ac.in

Department of Computer Science
and Engineering
Indian Institute of Technology Bombay,
India
Email: uday@cse.iitb.ac.in

Abstract—Backward slicing has been used extensively in program understanding, debugging and scaling up of program analysis. For large programs, the size of the conventional backward
slice is about 25% of the program size. This may be too large to be
useful. Our investigations reveal that in general, the size of a slice
is influenced more by computations governing the control flow
reaching the slicing criterion than by the computations governing
the values relevant to the slicing criterion. We distinguish between
the two by defining data slices and control slices both of which
are smaller than the conventional slices which can be obtained by
combining the two. This is useful because for many applications,
the individual data or control slices are sufficient.
Our experiments show that for more than 50% of cases, the
data slice is smaller than 10% of the program in size. Besides,
the time to compute data or control slice is comparable to that
for computing the conventional slice.

I.

I NTRODUCTION

Program slicing, introduced in 1984 by Mark Weiser [?],
strips down a large program to a smaller version based on
the requirements of program observation. Many variants of
slices such as forward, backward, dynamic, and abstract slice
etc. have been devised [?]. They have been used for different purposes like program understanding, debugging, testing,
maintenance, software quality assurance and reverse engineering among others. A brief description of various applications
of program slices is given by Binkley et. al. [?].
Among static slicing techniques, backward slicing which
answers the question “which program statements can influence
the given variables at the given statement?” seems more natural
and is most common. It identifies the portion of program that
one would be interested in while understanding a computation
or debugging for an erroneous output. In safety property
checking, rather than verifying the property on whole program,
one can verify the property on the static backward slice with
respect to slicing criterion derived from the specific property
of interest. As a result, backward slice helps scaling up of
property checking techniques also.
While static slicing is efficient and scalable, the size of
the computed slice may remain a matter of concern. Empirical
studies [?] have shown that size of a static slice on an average
is about 30% of the program size. For large programs, this size
could be too large. Our investigations of the factors influencing
the size of a slices reveal that most statements are included in
a slice due to some conditions governing the reachability of
the statement involved in the slicing criteria rather than due to

the values of variables in the slicing criteria. These statements
are irrelevant for understanding the computations leading to
the values of the variables.
As a motivating example, assume that the program in
Figure 1(a) computes an erroneous value of u at line 17. It is
obvious that for slicing criterion h17, ui, no static slicing can
reduce the program anymore. Therefore using the conventional
backward slice is of no help in getting a reduced program for
debugging this program. A careful examination reveals that the
value of u does not depend on the values of variables i or t.
These variables are used in the conditions which decide the
reachability of line 17 in the execution. Since we know that a
wrong value is getting computed at line 17, reachability of line
17 is obvious and need not be established. Thus, computations
of i and t are irrelevant to our purpose.
Figure 1(b) shows a portion of the program which is
sufficient to understand the computation of u and to debug the
reason for its wrong value. Any erroneous statement responsible for an erroneous value has to be contained in this program
fragment. The statements that have been removed only alter
the reachability of line 17 and not the value computed for u.
Note that functions fn1 and fn2 have been sliced out as they
are not required any longer.
Observe that retaining the program structure requires that a
conditionally executed statement in the original program must
also be included as a conditionally executed statement in the
program slice. However, since the values of variables appearing
in the condition are irrelevant, we replace conditions by ‘*’
which stands for a random value chosen from {true, f alse}
when it is executed.
It is easy to see that the resulting slice is much smaller in
comparison to conventional backward slice (incidentally the
whole program in this case) and still sufficient to debug (or
understand) the computation of u at the slicing criterion. We
call such a slice as data slice.
Consider a contrasting requirement of debugging the program when line 17 is not getting executed a desired number
of times. For this purpose we only need to see how the
reachability of line 17 is getting influenced. How the value of
u is computed is irrelevant. Therefore we need to know how
values of i and t are getting computed as they appear in the
conditions that govern whether or not line 17 will be reached.
We show the portion of code in Figure 1(c). It is sufficient
to understand when line 17 in original program (mapped to

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

int main()
{
int i=0,j=0, k=0, st;
int l, t=0, u, v;
l=get_input();
while (fn1(l))
t+=2;
while (i<1000)
{
i= i+ fn2();
st = fn3();
if (st ==1)
{ j++; k++; }
else { j+=2; k+=1; }
u = j-k;
if (t>100)
v = u ;
}
return 0;
}
int fn1(); // a complex function
int fn2(); // a complex function
int fn3(); // some function

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

int main()
{
int j=0, k=0, st;
int u, v;
while (*)
{
st = fn3();
if (st ==1)
{ j++; k++; }
else { j+=2; k+=1; }
u = j-k;
if (*)
v = u ;
}
return 0;
}
int fn3(); // some function

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

int main()
{
int i=0;
int l, t=0, u, v;
l=get_input();
while (fn1(l))
t+=2;
while (i<1000)
{
i= i+ fn2();
if (t>100)
v = u ;
}
return 0;
}
int fn1(); // a complex function
int fn2(); // a complex function

(b) Data slice

(c) Control slice

(a) Backward slice

Fig. 1: Usual backward slice, data slice and control slice

line 12 in slice) is reachable. Functions fn1 and fn2 have
to be part of this program portion while function fn3 is not
required. We call such a slice as control slice.
In addition to debugging and program understanding, this
separation of concerns is helpful in property checking during
program verification because it reduces the size of the program
to be examined. First we derive a slicing criterion SC from
the property to be checked, compute the corresponding data
slice and check the property on the slice. If the property holds
then we are done as the property will hold in original program
also. If the property does not hold, we compute a control slice
with respect to program point related to property in question
and check the reachability of this point in the control slice. If
it is not reachable then property holds in original program.1
The contributions of this paper are: We define the concepts
of data and control slices, relate them to the conventional
slices, provide an algorithm to compute data and control
slices and show its soundness. We also provide empirical
measurements on real life programs that show that the data
slices are indeed much smaller than complete slices and are
computable in comparable time.
II.

BACKGROUND

A. Variants of Program Slices
The classical backward slicing tries to find the program
fragment that influences a slicing criterion. Forward slicing [?]
discovers the statements that are influenced by a given slicing
criterion. Chopping [?] discovers statements influenced by a
source criterion on paths to a target criterion. A dynamic
slice [?] computes a subset of program statements which affect
a slicing criterion in a particular run of the program. Assertion
slicing [?], [?], [?] is a technique which computes set of
statements which are sufficient to ensure a post condition or
1 However,

if it is found reachable then the answer is not straight forward.

the statements which will be executed starting from a given pre
condition. All these variants use control and data influences in
an integrated manner. To the best of our knowledge there is no
work which distinguishes between data and control influences.

B. Control flow graph and data dependence
Program model. We present our ideas in context of imperative programs modeled in terms of assignment statements,
conditional statements, while loops, and procedure calls. We
also allow break and continue statements in loops. Without any
loss of generality, we restrict ourselves to goto-less programs
with single-entry loops and two-way branching conditional
statements at the source level.
Control Flow Graph (CFG). We use the standard notion
of control flow graph (CFG) G = hN, Ei where N is the set
of nodes, E is a set of directed edges in N ×N [?]. ENTRY and
EXIT are distinguished nodes representing the entry and exit
l

of program. We use s  t and s  t to denote unconditional
and conditional edges respectively, where l ∈ {true, f alse}
indicates the branch outcome. We assume that two special
edges ENTRY  EXIT and EXIT  EXIT are added in CFG.
There is a one-to-one correspondence between nodes of CFG
and statements of the program, hence we will use the terms
statement and node interchangeably.
Data dependence. A definition d of a variable v in node
p is said to be reaching definition [?] for a node point q, if
there is a control flow path from p to q devoid of any other
definition of v. A variable x at location l is said to be data
dependent on a definition d of x, if d is reaching definition
for l. The set of definitions of variables in X reaching l is
denoted by DU (l, X) = {d | ∃v ∈ X.v at l is data dependent
on d}. We will use REF (t) to denote set of variables whose
value is referred in a statement t.

C. Program states and traces
Let V be set of all variables in program P and < be the
set of all values which the variables can take in P .
Definition 1: (Program state). A program state is a valuation of all variables in the program at a given instant during
program execution. It is represented by a map θ : V → < such
that θ(v) denotes the value of v ∈ V in the program state θ.
Definition 2: (Restricted program state). Given X ⊆ V , a
X-restriction of program state θ, denoted as bθcX , is a map
X → < such that ∀x ∈ X.bθcX (x) = θ(x).
Definition 3: (Execution state). An execution state is a pair
hn, θi where θ is a program state and n is a CFG node.
Execution of a program can be seen as a sequence of
execution states starting with execution state hENTRY, σ0 i
where σ0 0 is0 initial program state. The subsequent execution
state hn , σ i for a given execution state hn, σi is decided by
semantics of statement corresponding to node n and program
state σ. Let function T RAN (hn, σi) provide the subsequent
execution state of hn, σi.
Definition 4: (Trace). A (possibly infinite) sequence of
execution states [hni , σi i], i ≥ 0 is said to be a trace, provided
n0 = ENTRY and σ0 is given initial program state, and
∀i ≥ 0 : hni+1 , σi+1 i = T RAN (hni , σi i).
When the trace sequence is finite and ends with an execution
state hEXIT, θi then the trace is called a terminating trace.
Unless stated otherwise, a trace means a terminating trace in
the rest of this paper.
D. Post-dominance and control dependence
Backward slicing algorithms are implemented efficiently
using post-dominance and control dependence [?], [?].
Definition 5: (Post-dominance). A node n2 post-dominates
a node n1 if every path from n1 to EXIT contains n2 . If, in
addition n1 6= n2 then n2 is said to strictly post-dominate n1 .
Definition 6: (Control dependence). A node n3 is control
l

dependent on an edge n1  n2 if n3 post-dominates n2 , and
n3 does not strictly post-dominate n1 .
Later Podgurski and Clarke [?] introduced concept of strong
post-dominance and weak control dependence, to consider
execution of a statement being dependent on loop termination. The previous definition of post-dominance and control
dependence were termed as weak post-dominance and strong
control dependence respectively.
Definition 7: (Strong post-dominance). A node n2 strongly
post-dominates a node n1 if every infinite path starting at n1
contains n2 . If in addition, n1 6= n2 then n2 strictly strongly
post-dominates n1 .
Definition 8: (Weak control dependence). A node n3 is
l

weakly control dependent on an edge n1  n2 if n3 strongly
post-dominates n2 , and n3 does not strictly strongly postdominate n1 .
Only EXIT node strongly post-dominates a loop exit edge.
Therefore, all the nodes that weakly post-dominate a loop condition are weakly control dependent on loop exit edge. Bilardi

and Pingali [?] give efficient algorithms for computing strong
post-dominance and weak control dependence relationship.
For our purpose, we will need to know whether a statement
is controlled by a condition through a chain of weak/strong
control dependence. For this, we define a transitive closure of
weak/strong control dependence.
Definition 9: (Transitive control dependence). For given
statement s and condition c, if there is a path π in PDG from
c to s consisting of only (weakly/strongly) control dependent
edges then we say that s is transitive control dependent on c,
written as c
s. If π consists of only strong control dependent
edges then we say s is strongly transitive control dependent
on c, written as c −→ s.
If π starts with a control dependent edge labeled as e then
we qualify the transitive control dependence with edge e as
e
e
e
e
c
s or c −→ s. Obviously, c −→ s =⇒ c
s.
Following properties are obvious, for the programs under
our discourse.
SP1
SP2

e

e

1
2
(c −→
s ∧ c −→
s) =⇒ e1 = e2
e
c −→ s =⇒ no path to s from an edge ē 6= e of c
can bypass e.

E. Subprogram and backward slice
An important requirement of a slice is that the behaviour of
the slice must be a specified subset of the original program’s
behaviour. A subset of original program’s behaviour is specified through a pair Υ = hl, V i, known as slicing criterion,
where l is a statement location and V is set of variables. It
is interpreted as values of variables V just before executing
statement at l. We will use Υ and hl, V i interchangeably to
denote a slicing criterion. Where context is clear, we will use
l and V to denote the location and variables set components,
respectively. We will use LV (t) to denote the slicing criterion
ht, REF (t)i.
A subprogram of a program P is a program carved out
of P by deleting some statements such that program structure
remains intact in that for each statement n that appears in
subprogram, if n is enclosed by a condition in P , then n must
be enclosed by a condition in subprogram too.
An augmented program (P A ) is the result of transforming a
given program P for a slicing criterion Υ = hl, V i by inserting
a SKIP statement at location l. Obviously, an augmented
program is equivalent to the original program. To compute
a slice of program P with respect to Υ, we compute the
slice S of the augmented program with respect to Υ with the
restriction that the inserted SKIP statement is retained in S.
Now with l standing for SKIP statement, Υ can be seen
as specification for the desired subset of original program’s
behaviour for P , P A and S. Henceforth, we assume that
SKIP statement, inserted at location l, is part of every slice
with respect to Υ.
Henceforth, we will assume that each statement in P is
labeled uniquely and the nodes in CFG are labeled with
corresponding statement label. Statements in subprogram will
get their label from the ones given in P . As a result, in CFG,
Gs = hN s , E s i constructed for a sub program S of program
P , having CFG, G : hN, Ei, N s ⊆ N . To be more explicit,

given a node ns ∈ N s and n ∈ N , ns = n would mean that
they represent statement with same label. This also holds for
special nodes ENTRY and EXIT.
Definition 10: (SC execution state). Given a program P
and slicing criterion hl, V i, execution states of P having
statement location as l are called SC execution states.
Given a program P and slicing criterion Υ = hl, V i, let
τ : [(ni , σi )], 0 ≤ i ≤ k. be the trace for input I with m SCexecution states. Let τ s : [(nsi , σis )], 0 ≤ i ≤ k s , be trace for a
slice S of P , on same input I with ms SC-execution states. Let
[hnlj , σlj i], 1 ≤ j ≤ m and [hnslj , σlsj i], 1 ≤ j ≤ ms be the
sequence of SC-execution states in in τ and τ s respectively.
We say, hnlj , σlj i and hnslj , σlsj i for 0 < j < min(m, ms )
are corresponding SC-execution states. Now the window of
observation for Υ = hl, V i is the sequence of V-restricted
program states [bσlj cV ], 1 ≤ j ≤ m. We will call such a
sequence as the trace window of observation T W (P, I, Υ).
Definition 11: (SC-equivalent trace). A trace τ of P on an
input I is called SC-equivalent to trace τ s on slice S for same
input I, if T W (P, I, Υ) = T W (S, I, Υ).
We express the definition of a backward slice PΥB for a
program P and a slicing criterion Υ as follows.
1)
2)

PΥB is subprogram of P A .
For every input I on which original program terminates,
T W (P, I, Υ) = T W (PΥB , I, Υ).

Of all methods that use some form of data flow to compute
the backward slice, the methods of Ferrante et al. [?] and
Horwitz et al. [?] using program dependence graphs (PDG)
produce the minimal slice.
III.

Q2

We now formalize the notions of control and data slice.
A. Control slice
A control slice of a program P wrt. to the slicing criterion
Υ = hl, V i, denoted PΥC , is the backward slice of P with
respect to the slicing criterion hl, ∅i.
Thus, the sliced program P C contains those statements of
the original program which merely caused the program control
reach the program point l. We now show that the control slice
is contained in the backward slice.
Lemma 1: PΥC ⊆ PΥB
Proof: From the definition of control slice, we have
B
PΥC = Phl,∅i
. Further, backward slices have the property [?]
B
B
B
B
V1 ⊂ V2 implies Phl,V
⊂ Phl,V
and thus Phl,∅i
⊆ Phl,V
i.
1i
2i
B
C
Consequently PΥ ⊆ PΥ
Since computing backward slice is a well studied problem,
we can compute the control slice by computing the backward
slice with respect to the slicing criterion hl, ∅i following any
of the existing approaches.

DATA AND CONTROL SLICES

A backward slice is the answer to the question “Given a
slicing criterion Υ = hl, V i, which program statements can
affect the values of the variables V ?” This question can be
meaningfully split into two parts:
Q1

To obtain the data slice for P1 for the same slicing criterion,
we reason as follows. The value of y at line 13 is given by
assignment at 11 and the condition at line 12 has no impact
on this value. Therefore line 11 is included in the data slice
but line 12 is not. The value of x assigned to y at line 11 is
computed by lines 10 and 4. Of these, the value that reaches
line 11 during execution is decided by condition at line 9.
Therefore lines 4, 9 and 10 are also included in the data slice.
Further, line 6 is also included, as it computes the value to be
used in the condition at line 9. No other statement affects the
value of y at line 13. The resulting program P3 is the data
slice.

Which statements decide whether program control
will reach l?
Assuming that control reaches l, which program
statements decide the values of the variables V .

As mentioned in the motivating example of Figure1, often
we are interested in the separate answers to questions Q1
or Q2, even if we want to use them together. We call the
subprogram resulting from the answer to Q1 as a control slice
and that to Q2 as a data slice.
In Figure 2, P1 is the original program in which the codes
for the functions fn1 and fn2 are not shown. P2 is the control
slice for the slicing criterion h13, {y}i. The conditions c1 and
x < 10 at lines 7 and 12 decide whether program control
reaches line 13, and therefore they are part of the control slice.
Further, the value of the condition x < 10 may be decided by
the assignment at line 10, which, in turn, is controlled by the
condition at line 9. Therefore both line 12 and line 10 are in
the control slice. For similar reasons, lines 4, 5, and 6 also
have to be included.

B. Data slice
While P3 is an answer to the question Q2 posed for
the criterion h13, {y}i and can therefore be regarded as a
data slice, it is not suitable for applications like program
understanding and debugging. For example, the information
that the statement at line 13 may not be executed at all is
missing from P3. Thus apart from the statements that decide
on the values of variables at a slicing criterion, we also need
to include statements that explicate the paths along which the
computation of such values takes place.
Therefore, we also include conditions that impact the
reachability of l. This is shown in P4, and the included
conditions are shown as ‘*’ indicating a non-deterministic
branch. We make such conditions non-deterministic because
their values are inconsequential for our purpose. Further, if
these conditions were made concrete, then we would also have
to include additional statements affecting their values, increasing the size of the slice. We call such a non-deterministic
conditional as abstract conditional. During execution, such a
conditional can randomly evaluate to true or f alse.
The form of the slice as shown in P4 is good for program
understanding and debugging. However it falls short if used
for property verification. The reason is that while the abstract
conditional helps in keeping the size of the sliced program

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

proc (int z)
{
int w,x,y;
x = z;
c1 = fn1();
c2 = fn2();
if (c1)
{
if (c2)
x = z+5;
y = x;
if (x < 10)
w = y;
}
}

1
2
3
4
5
6
7
8
9
10

proc (int z)
{
int w,x,y;
x = z;
c1 = fn1();
c2 = fn2();
if (c1)
{
if (c2)
x = z+5;

11

2
3
4

proc (int z)
{
int w,x,y;
x = z;

1
2
3
4

5

13

}

14

c2 = fn2();

6
7

7

8

8

if (c2)
x = z+5;

9
10

(a) P1

13

15

(b) P2

9
10
11

y = x;
w = y;

12

12
13
14

}

15

1
2
3
4
5

c2 = fn2();
if (*)
{
if (c2)
x = z+5;
y = x;
if (*)
w = y;
}

6

14

}

proc (int z)
{
int w,x,y;
x = z;

5

11

if (x < 10)
w = y;

12

15

1

}

(c) P3

6
7
8
9
10
11
12
13
14
15

(d) P4

proc (int z)
{
int w,x,y;
x = z;
c1 = *;
c2 = fn2();
if (c1)
{
if (c2)
x = z+5;
y = x;
if (x < 10)
w = y;
}
}
(e) P5

Fig. 2: Various forms of data slices

small, it elides path conditions that are important for verification. As an example, suppose we want to check the property
y < 20 at line 13. This property holds in original program
but does not hold in P4. However, if we retain the included
conditionals in concrete form and abstract out instead those
assignment statements that assign to the variables involved in
the conditional, we get P5. The property y < 20 holds for this
program. Note that the assignments to x cannot be eliminated
since they also determine the value of the variables of the
slicing criterion.
An abstract assignment of the form x = * assigns to x
a random value from some domain. If x is an integer, for
example, then x is assigned an integer value between −231 to
231 − 1.2
Due to inclusion of abstract conditions and assignments,
there will be multiple execution paths on a given input. In
general, the slice produced by abstract assignments will have
less number of possible executions paths for same input in
comparison to the one produced by abstract conditionals. For
example, P4 may have 4 different execution paths on a given
input while P5 will have only two such paths on same input.
As a result, the slice produced through abstract assignments
is more useful in property checking. The flip side is that slice
produced by abstract assignments may be larger than the one
produced by abstract conditionals. Given a program P , we
shall call a subprogram of P in which some of the assignments
and conditionals have been replaced by their abstract versions
as an abstract subprogram.
Now we will formally define a data slice and identify the
statements which should be part of the data slice.
C. Data slice: Formalization
Given a slicing criterion hl, V i, a data slice is required
to retain the program’s behavior in computing the value set
of the variables in V , but is not required to visit l as many
times as the original program. However, whatever value sets
are computed by the slice should match those computed by the
original program in a sense that we shall make precise now.
2 Assuming

a 4 byte 2s complement representation.

Consider program P7 of Figure 3. Assume that the number
of times the outer loop iterates depends on the input and the
inner loop iterates a fixed number of times, say 3. If the outer
loop executes twice for an input I, the values of x at line 8
will be 3,6,9,3,6,9. However, if both the while conditions are
replaced by ‘*’ in a slice, then for the same input, 3,3 is one
of the sequence of values generated for x. This sequence does
not match the sequence generated by the concrete program. On
the other hand, if only the outer loop condition is replaced by
‘*’, then the output produced will be zero or more occurrences
of sequence 3,6,9. These sequences are considered to match
the sequence produced by the original program.
Based on these considerations, we identify the necessary
properties of a data slice P D for a given program P and slicing
criterion hl, V i.
1)
2)
3)

P D is an abstract subprogram of P
For every input I, on which augmented program
terminates with trace τ , there exists a trace τ d of P D
on same input I, such that τ and τ d are SC-equivalent.
Let τ d and τ be traces of P D and P A respectively on
an input I. Let k be the minimum of the numbers of
SC-execution states in τ and τ d . Then for all i ≤ k,
the V-restricted program states of ith SC-execution
states of τ and τ d are the same.

Clearly, a backward slice P B also satisfies the properties of
data slice mentioned above. Therefore, P D ⊆ P B
Given a slicing criterion hl, V i, we now identify statements
which are necessarily in the data slice. We call such statements value-impacting and define the term shortly. Informally
speaking, a chain of assignments that determine the value set
of V is value-impacting. Further, a condition that determines
which of the several values generated by value-impacting
statements reaches l during execution is also value-impacting.
In subsequent discussions, we shall often use “value-impacting
statements” to mean both value-impacting assignments and
conditionals.
Definition 12: (Value-impacting statement) A statement s
value-impacts Υ, if any of the following conditions hold:
1)
2)

s is the augmented SKIP statement.
s is an assignment, and s ∈ DU (Υ).

3)
4)

s is an assignment, and there exists a statement t such
that t value-impacts Υ and s ∈ DU (LV (t)).
s is a condition c, and the following holds: From c
there exist paths π1 , π2 to l starting from edges e1
and e2 respectively. Further, there exists a statement
t such that t value-impacts Υ and
a) t is the first value-impacting statement along
π1
b) t is not the first value-impacting statement
along π2 .

The triplet hπ1 , π2 , ti due to which a condition c satisfies
rule (4) will be called a witness for a value-impacting condition. Obviously, there can be more than one witnesses for a
condition to be value-impacting. The set of all such witnesses
will be referred as W V I(c, Υ).
In Figure 3 we show some examples of value-impacting
statements. The CFGs of these programs are shown in Figure 4.
In P6, lines 1 and 8 are value-impacting for h11, {x}i because
the values of x generated at these statements reach 11. In
addition, condition c2 is also value-impacting for the reason
that of the two paths from c2 to 11, only one has x = z + 5
as the first value-impacting statement. As a consequence c2
determines whether the value generated at line 1 or at line
8 reaches 11. However, notice that while line 8 is valueimpacting for h9, {x}i, condition c2 is not, because there is no
path to line 9 from the false edge of c2. Similarly, condition
c1 value-impacts h13, {x}i.
In P7 of Figure 3, the definition of x at lines 4 and 7
are value-impacting for h7, {x}i. Since line 7 is not reachable
along the false edge of c2 without passing through line 4, c2
also becomes value-impacting for h7, {x}i. In P8, we can see
that, c2 is value-impacting for h7, {x}i.
Obviously, if a statement s value-impacts a slicing criterion
Υ = hl, V i, then s can be the cause of an erroneous value of
some v ∈ V at l and should be examined while debugging.
Therefore, s must be part of P D .
Let V I(Υ) be the set of value-impacting statements of Υ.
Let AC(Υ) be conditional statements that are not by themselves value-impacting, but on which other value impacting
statements are strongly (and transitively) control dependent.
Formally:
[
AC(Υ) = (
{c | c −→ t}) \ V I(Υ)
t∈V I(Υ)

states in τ and τ 0 such that n0 = n00 = EN T RY and for
i > 0 and j > 0 ni , n0j ∈ V I(Υ). Let K be minimum of the
number of elements in τs and τs0 . Since l occurs at least once
in τ and in τ 0 , K > 0. We will prove by induction on i that for
all i ≤ K, ni = n0i and bσi cZ = bσi0 cZ , where Z = REF (ni ).
Base step : i=0. It holds trivially as n0 = n00 = EN T RY ∧
σ0 = σ00 = I.
Induction step: Let the hypothesis be true for i ≤ K and
assume that i + 1 ≤ K (else the proof holds vacuously). Since
bσi cZ = bσi0 cZ , the edge followed from ni and n0i in τ and
τ 0 have to be same. Assume that ni+1 6= n0i+1 . Let c be a
common condition, with edges e1 and e2 , occurring between
ni and ni+1 in τ and between n0i and n0i+1 in τ 0 . Clearly
there is such a c, otherwise ni+1 would have been the same
as n0i+1 . Since both traces have occurrence of l and ni+1 and
n0i+1 are the first value-impacting statements on paths from e1
and e2 , the condition c ∈ V I(Υ) according to the definition.
This is contrary to our assumption that ni+1 and n0i+1 are the
first value-impacting statements in τ and τ 0 after ni and n0i
respectively. Therefore, ni+1 = n0i+1 .
Now suppose that for some variable x ∈ Z, σi+1 (x) 6=
0
σi+1
(x). Let d be statement which provides value of x at ni+1 .
But then d ∈ V I(Υ). If d occurs before or at ni then it must
0
be there in τ 0 also and therefore, σi+1 (x) = σi+1
(x). If d
occurs after ni then hni+1 , σi+1 i can not be the first element
of τs after hni , σi i. This is contrary to our assumption and
0
therefore σi+1 (x) = σi+1
(x).
Now we prove our claim that P S is a data slice. We shall
show this by constructing a trace τ 0 for P S from a given trace
τ of P A on an input I. This will establish that P S satisfies
property (2) of data slice. Using lemma 2, we shall show that
P S satisfies property (3) as well.
Theorem 1: The abstract subprogram P S satisfies the
property for data slice.
Proof: Let τ be a trace for program P A on input I that
has K ≥ 0 execution states. Let τ 0 = [hni , σi i], 0 ≤ i ≤ K,
be the sub-sequence of τ such that ni , i ≥ 0 are nodes in
CFG of P S . We show by induction on i that for each i ≤ K,
[hni , σi i] is also the prefix of a trace for P S .
Base step: i = 0. The lemma holds trivially as n0 =
EN T RY .

We construct an abstract subprogram P S = V I(Υ) ∪ AC(Υ)
in which the conditionals in AC(Υ) appear in an abstract form.
Obviously, P S retains the structure of P A with respect to all
statements included in P S . We claim that P S is a data slice.
To show this, we shall first prove that the value sets of Υ
produced by execution of P S match those produced by P A .

Induction step: Assume that the hypothesis holds for some
i ≤ K. Let ni be a condition. If ni ∈ AC(Υ) then it is abstract
and can take either branch. If ni ∈ V I(Υ) then by lemma 2 it
will have the same value as in trace τ . So for any edge taken
out of ni in τ , there is a trace of P S which takes the same
edge.

Lemma 2: Let τ and τ 0 be traces of programs P A and P S
for an input I. Also assume that both the traces go through l
at least once. Then the corresponding SC-execution states of
τ and τ 0 will be the same when restricted to the variables in
V.

Now assume that for none of the traces of P S is the
(i + 1)th node same as ni+1 . This must be because of some
condition c before ni+1 , but after ni , in τ . But then c −→ ni+1
and therefore c ∈ P S . So hni+1 , σi+1 i can not be the first
execution state after hni , σi i in τ 0 , a contradiction.

Proof: Let τs
=
[hni , σi i],
i
≥
0 and
τs0 = [hn0j , σj0 i], j ≥ 0 be the sequence of execution

Thus, property (3) is satisfied. By lemma 2, it is obvious
that property (2) is also satisfied.

1
2
3
4
5
6
7
8
9
10
11
12
13

x = z;
c1 = fn1(z);
c2 = fn2(z);
if (c1)
{
if (c2)
{
x = z+5;
t = x;
}
y = x;
}
w = x;

1
2
3
4
5
6
7
8
9
10
11

c1=fn1(x);
while (c1)
{
x = 0;
while (c2)
{
x = x+3;
y = x;
}
c1=fn1();
}

1
2
3
4
5
6
7
8
9
10
11

x = 0;
c1 = fn1(x);
while (c1)
{
c2 = fn2(x);
if (c2)
y = x;
else
x = x+3;
c1 = fn1(x);
}

(b) P7

(c) P8

(a) P6

Fig. 3: Programs to explain value-impact

Fig. 5: Program dependence graphs

As seen from the examples, to capture value-impact we
need to consider both strong and weak control dependence.
For this we make use of transitive control dependence.
Fig. 4: Control flow graphs

D. Computing data slice using data and control flow
We now relate V I(Υ) to control and data dependence. In
Figure 5, we show PDG for programs of Fig. 3. Solid, normal and dotted arrows show data dependence, strong control
dependence and weak control dependence respectively. In P6
of Fig. 3, c2 is value-impacting for h11, {x}i. In terms of
control-dependence, line 11 is not control dependent on c2
while the value-impacting assignment at line 8 is. For exactly
similar reasons, condition c1 is value-impacting for h13, {x}i.
We generalize the identified condition for a slicing criterion
Υ = hl, V i as cond1 : l is not control dependent on condition
c and a value-impacting statement for Υ is transitively control
dependent on c.
In P7, c2 is value-impacting for h7, {x}i, a slicing criterion
whose program point (line 7) is strongly true-control dependent
on c2. The value-impacting assignment for this criterion at
line 4 is weakly false-transitively control dependent on c2.
Similarly, in the case of P8, condition c2 is value-impacting
for h7, {x}i and 7 is strongly true-control dependent on c2.
Moreover, the value-impacting assignment at line 9 is strongly
false-control dependent on c2. From these observations, we
identify a second condition cond2 : l is control dependent on
c and l is reachable from one edge and a value-impacting
statement is reachable from other edge. We show that the
disjunction of cond1 and cond2 is a necessary condition for
value-impact. Thus we can use the disjunction to compute an
over-approximation of value impacting conditions.

We now make the following connections between transitive
control dependence and weak post dominance.
Claim 1: Given a condition c and a statement s, assume
e
that c −→ s. If there is a statement t distinct from c such that
there is a path from c to s starting from the edge ē 6= e and
ē
going through t, then c
t.
Claim 2: Let c be a condition and u be a statement distinct
from c such that u is the immediate post-dominator of c. If
there is a statement t distinct from c and u such that there is
a path from c to u starting with edge e and passing through t,
e
then c −→ t.
We shall now establish that if a condition c is valueimpacting, then there must be another value-impacting statement which is transitively-control dependent on c.
Lemma 3: Assume that for a slicing criterion Υ = hl, V i,
c ∈ V I(Υ). Then one of the following holds:
∃hπ1 , π2 , ti ∈ W V I(c, Υ) : (¬(c −→ l) ∧ c −→ t), or
e
e2
e2
∃hπ1 , π2 , ti ∈ W V I(c, Υ) : (c −→
l ∧ ¬(c −→
t) ∧ c 1 t).
where e1 and e2 are starting edges of paths π1 and π2
respectively.
Proof: Let c ∈ V I(Υ). The proof is by case analysis:
Case 1: Assume ¬(c −→ l). Then there must exist u 6=
c such that u is immediate post dominator of c. Since c ∈
V I(Υ), by definition 12 there are paths π1 and π2 starting
from e1 and e2 and a value-impacting statement t such that at
least one of the π1 and π2 should have t before u. Without
loss of generality, assume that t is on π1 . Then by claim 2,
c −→ t. Thus we have proved that for the witness hπ1 , π2 , ti ∈
W V I(c, Υ), ¬(c −→ l) and c −→ t.

Case 2: Assume c−→l, and call the starting edge in the
e2
l.
chain of control dependence from c to l as e2 , i.e. c −→
From the definition of value-impacting condition, there is a
path from c to l that has a statement, say t, as the first valueimpacting statement and another that does not have t as the
first value-impacting statement. Now there are two cases:
1. Let the path that has t as the first value-impacting
statement leave c through the edge e1 . For the kind of programs
under consideration, no path from c to l can bypass e2 .
Therefore t on π1 must be between e1 and e2 . Thus we have
e
e2
t), and by claim 1, c 1 t. The witness in this case
¬(c −→
being hπ1 , π2 , ti.

Proof: Once again the proof is by induction on
M LP (s, l).
Base case: i = 0. s must be the augmented SKIP
statement and and therefore s ∈ P B
Induction step : Let the hypothesis be true for all s such
that M LP (s, l) ≤ i and consider a s for which M LP (s, l) =
i + 1 and s ∈ CVI (Υ ). By definition of CVI (Υ ), we have
the following cases:
1)
2)

2. Now let the path that has t as the first value-impacting
statement leave c through the edge e2 . Once again the path
that goes from c to l through e1 must go through e2 and there
must be a first value-impacting statement w between e1 and
e2
w),
e2 . Now we have a witness hπ1 , π2 , wi for which ¬(c −→
e1
w.
and by claim 1, c

3)

Based on lemma 3, we shall give criteria for computing a set of
statements CVI (Υ ), (computed value-impacting statements).
CVI uses data and control dependence and computes an overapproximation of VI .

s is an assignment and s ∈ DU (Υ). Clearly s ∈ P B .
s is assignment and ∃t ∈ CVI (Υ ) : s ∈
DU (LV (t)). Clearly M LP (t, l) ≤ i and therefore
t ∈ P B . By construction of backward slice, s ∈ P B .
s is a condition c, say with two edges e1 and e2 . By
definition of CVI (Υ ), ∃t : t ∈ CVI (Υ ), satisfying
one of the following:
Case a: c −→ t ∧ ¬(c −→ l). Obviously,
M LP (t, l) ≤ i and c −→ t. By the induction
hypothesis, t ∈ P B . Therefore c ∈ P B .
e
e1
e1
Case b: c −→
l ∧ ¬(c −→
t) ∧ c 2 t. In this case
c −→ l and therefore, by construction of backward
slice, c ∈ P B .

A statement s is in CVI (Υ ) if:
1)
2)
3)
4)

s is the augmented SKIP statement at l.
s is an assignment such that s ∈ DU (Υ).
s is an assignment, and there is a statement t such
that t ∈ CVI (Υ ) and s ∈ DU (LV (t)).
s is a condition c, with two outgoing edges, labeled
as e1 and e2 , and ∃t ∈ CVI (Υ ) satisfying one of the
following:
a) c −→ t ∧ ¬(c −→ l)
e
e1
e1
b) c −→
l ∧ ¬(c −→
t) ∧ c 2 t

Condition 4) of CVI is motivated by lemma 3.
We shall now show that CVI (Υ ) computes an over approximation of value-impacting statements V I(Υ). In subsequent
proofs, we use M LP (s1 , s2 ) to denote maximum length of
a loop free path in a CFG from s1 to s2 . In particular,
M LP (s, s) = 0.
Lemma 4: V I(Υ) ⊆ CVI (Υ )
Proof: Let s ∈ V I(Υ). We will prove the result by
induction on M LP (s, l).
Base step: M LP (s, l) = 0. s must be the augmented
SKIP statement and therefore in CVI (Υ ).
Induction step: Let the hypothesis be true for all s such that
M LP (s, l) ≤ i and consider a s for which M LP (s, l) = i + 1
and s ∈ V I(Υ). If s is an assignment, then s ∈ CVI (Υ ) from
definition. Let s be a condition c. Let hπ1 , π2 , ti ∈ W V I(c, Υ)
satisfy the criteria of lemma 3. Obviously M LP (t, l) ≤ i.
and t ∈ CVI (Υ ) by the induction hypothesis. By definition,
c ∈ CVI (Υ ).
We will now show that though CVI is an overapproximation of VI , it is contained within the backward slice
P B.
Lemma 5: CVI (Υ ) ⊂ PΥB .

IV.

DATA SLICE COMPUTATION

As stated earlier, CVI (Υ ) provides the core set of statements of the data slice. To make the slice executable, conditions are added using one of the methods of creating abstract
sub programs described before. We present an algorithm to
compute CVI only; adding the abstract conditions and assignments is straightforward. As an example, the conditions c
to be abstracted are given by {c | c −→ l}\CVI (Υ ).
Algorithm 1 Identifying CVI conditions
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:

procedure getCVIConds(t, lconds)
begin
R=∅
tconds = tcntrls(t)
for all conditions c appearing in tconds do
lsttab[T ] = (hc, T, truei ∈ lconds)
lsttab[F ] = (hc, F, truei ∈ lconds)
tsttab[T ] = (hc, T, truei ∈ tconds)
tsttab[F ] = (hc, F, truei ∈ tconds)
tswtab[T ] = (hc, T, f alsei ∈ tconds)
tswtab[F ] = (hc, F, f alsei ∈ tconds)
if (¬lsttab[T ] ∧ ¬lsttab[F ] ∧ (tsttab[T ] ∨ tsttab[F ]))
then
add c to R
else
if ((lsttab[T ] ∧ ¬tsttab[T ] ∧ tswtab[F ])) ∨
(lsttab[F ] ∧ ¬tsttab[F ] ∧ tswtab[T ]) then
add c to R
end if
end if
end for
return R
end

A. Computing CVI (Υ )
In computing CVI (Υ ), the critical part is to identify
conditional expressions which satisfy criteria for being in CVI .
We assume that the P DG already exists with weak and strong
control dependences and data dependences. Such a P DG can
be computed efficiently by algorithm of Bilardi and Pingali
[?]. From the PDG, for a given statement s, we can find
e
the set conds(s) of pairs hc, e, bi, such that c
s when
e
b = f alse and c −→ s when b = true. Using conds(s), we
can compute the set of conditions on which s is transitively
control depdendent. We call this set as tcntrls(s). We do so by
traversing the PDG and taking a transitive closure of conds(s).
By the definition of CVI (Υ ), we need to examine only the
conditions c which appear in tcntrls(t) for a given statement t.
Algorithm 1 computes the set of conditions which satisfy the
criteria for CVI (Υ ) for a given statement t which is already
in CVI (Υ ). Lines 6 to 11 identify the kinds of transitive
control dependence that t has on the outgoing edges of c.
e
While tsttab[e] = true means c −→ t, tswtab[e] = true means
e
c
t. Algorithm 2 computes the complete set CVI (Υ ) using
a worklist based approach. A node comes on the worklist only
once. The final result is denoted by a boolean array inslice
having value true for every statement included in CVI (Υ ).
Algorithm 2 Computation of CVI (Υ )
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:

procedure computeCVISet(l, V)
begin
initialize inslice, inwl with f alse
inslice[l] = true ; lconds = tcntrls(l)
wl = {}
duset = DU (l, V )
for all s ∈ duset do
add s to wl ; inwl[s] = true
end for
while wl is not empty do
remove next element w from wl
inslice[w] = true
duset = DU (LV (w))
cset = getCV ICond(w, lconds)
for all s ∈ (duset ∪ cset) do
if inwl[s] = f alse then
add s to wl ; inwl[s] = true
end if
end for
end while
end

B. Algorithm complexity
Assume there are N nodes, E d data dependent edges and
E c control dependent edges, giving a total of E = E d + E c
edges in the PDG. In getCV IConds, computing tcntrls for
the given node, will take O(E c ) time. The checks in lines 6 to
11 can be done in O(1) time with a space complexity of O(N ).
Since the checks have to be made for all conditions occurring
in tcntrls, the worst case complexity of getCV IConds would
be O(N +E c ). In algorithm, computeCV ISet, a node goes in
the worklist only once, therefore there would be maximum N
invocations of getCV IConds. The worst case complexity of
entire algorithm is O(E c ×N +N 2 +E d ). However in practice,

the loop at line 5 in getCV IConds will be executed much
fewer times than N and nodes going in worklist will also be of
the size of the data slice. As a result, the algorithm’s average
complexity will be O(N +E c +E d ). In contrast, the backward
slice is computed in O(E) time, in worst case. Note that in
both cases the time complexity is arrived at by assuming that
P DG have already been built. In practice, our results have
also shown that there is only a marginal increase in time in
computing data slice from that taken in backward slice when
compared to time taken in building the PDG itself.
V.

I MPLEMENTATION AND MEASUREMENTS

We implemented the algorithm to compute data slices
using our in-house data flow analysis framework called PRISM
which is based on the JAVA platform. It can construct PDGs
and can compute the conventional backward slices. It has been
used for developing static analysis tools [?], [?]. We have used
a context and flow sensitive points-to analysis. The backward
slicing algorithm is also context sensitive and field sensitive.
Thus it represents the state of the art in backward slicing.
We computed data slice using condition abstraction approach
which is suitable for debugging and program understanding.
Although we have described our algorithm at an intraprocedural level, our implementation performs interprocedural
analysis by summarising procedure calls by a sequence of
assignments simulating the use-def summary of called procedure. We trigger additional slicing criteria at call points based
upon the values needed at procedure entry point in a context
sensitive manner. We computed data slice for these additional
slicing criteria and at the end took a union of all of them. This
may introduce some imprecision but is sound.
Our experiments have been carried out on 3.0 GHz Intel Core2Duo processor with 2 GB RAM and 32 bit OS.
Measurements were peformed on 42 modules of varying sizes
of a proprietary code base of a large navigational system of
an automobile. Due to space constraints, we have presented
summary data of only 20 modules in Figure 6. Column (1)
gives anonymized program names. Column (2) lists the number
of CFG nodes. Column (3) gives number of slices computed
for the program. For this purpose we randomly selected the
return statements of functions returning some value as the
slicing criterion. For each program, we picked up maximum
ten such slicing criteria. In all, we created slices for total 391
such slicing criteria spread over 42 programs.
Columns (4), (5) and (6) provide the average sizes of slices
in terms of the number of nodes for backward slice (BS), data
slice (DS) and control slice (CS) respectively. Columns (7), (8)
and (9) provide the average sizes of slices as a percentage of
the program size (as given in column (3)) for BS, DS and CS
respectively. The average time taken (in seconds) in computing
these slices is shown in columns (10), (11) and (12) in same
order. This time includes the time taken for constructing PDGs.
Figure 7 shows the distribution of sizes of slices in terms of
percentage of program sizes through a graph. The X axis shows
the size of the slice and Y axis shows the percentage of slicing
criteria exhibiting that size. In the figure, BS, DS and CS stand
for backward slice, data slice and control slice respectively. It
is clear that in more than 60% of the cases, the size of a data
slice is smaller than 10% of the code size. Besides, the time

Program
(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Overall

Size
(nodes)
(2)
1063
1183
2944
881
1607
2246
2493
2635
2992
1625
3413
3105
4452
5236
2616
3883
802
8116
6746
11104

number of
slices
(3)
10
10
10
10
10
10
5
10
9
10
10
5
1
1
10
10
10
10
10
10

Avg. Size (in
BS
DS
(4)
(5)
229
60
266
123
360
257
148
62
226
137
447
348
167
81
842
257
437
149
190
94
733
341
571
412
369
70
982
25
948
761
1202 180
92
56
3489 1637
1928 1558
4096 1214

nodes)
CS
(6)
227
240
236
148
203
444
163
842
429
178
728
563
317
982
945
1202
90
3143
1923
4053

Avg Size as % of program
BS
DS
CS
(7)
(8)
(9)
21.63 5.65
21.37
22.49 10.43
20.36
12.26 8.75
8.03
16.89 7.12
16.81
14.08 8.55
12.65
19.93 15.49
19.79
6.70
3.26
6.54
31.98 9.79
31.97
14.63 5.01
14.34
11.70 5.84
10.98
21.50 10.01
21.35
18.41 13.29
18.13
8.29
1.57
7.12
18.75 0.48
18.75
36.27 29.12
36.15
30.97 4.64
30.96
11.48 7.01
11.28
42.99 20.18
38.73
28.58 23.10
28.51
36.89 10.94
36.50
24.89 10.66
24.04

time in seconds
BS
DS
CS
(10)
(11)
(12)
26.33
26.34
26.32
32.05
32.07
32.04
38.15
38.21
38.13
60.43
60.47
60.42
39.46
39.51
39.45
56.47
57.24
56.45
51.45
51.48
51.42
44.20
44.31
44.19
52.67
52.76
52.65
63.80
63.83
63.79
92.74
92.97
92.70
71.41
89.70
71.35
102.29 102.27 102.26
116.92 116.47 116.53
208.23 230.40 208.24
215.99 216.14 215.97
53.85
53.86
53.84
447.69 512.58 447.30
272.10 293.40 271.74
301.26 322.31 301.13

Fig. 6: Average slice sizes and computation time

the slicing criterion rather than the value computed. It is not
surprising then that the size of a control slice is comparable
to that of the corresponding backward slice in majority of the
cases. The average size of control slice turns out to be of 24.4%
of program size which is comparable to the size of backward
slice (24.89%).
VI.

C ONCLUSION

Different applications of program understanding require
different combinations of influences governing data computations and control flow. For example, in the case of debugging
for wrong output values, the influences governing the reachability of the statement of interest are irrelevant.
Fig. 7: Slice size distribution. X-axis shows slice size as
percentage of program size and Y-axis shows percentage of
slicing criteria for which this size was observed.

required to compute a data slice is comparable to the time
taken for computing a backward slice.
Note that the average size of backward slices is 25% of the
code size which matches the observation by Binkley et al. [?].
suggesting our slices are comparable in precision. Average size
of data slice is found to be 10% of the code size. Given
such a reduction, data slices may be very helpful in debugging, property checking and program understanding. This data
corroborates our intuition that most statement are included in
a backward slice because they influence the reachability of

It follows that separating the influences of data and control
in a backward slice by constructing separate data and control
slices is an effective way of producing smaller programs for
debugging, program understanding and property checking. In
the case of debugging for wrong output values, a data slice
provides a much smaller piece of code to investigate than that
provided by a backward slice for the same slicing criterion.
We have provided formal definitions of data and control
slices, defined algorithms to compute them, have shown the
soundness of the algorithms, and have presented the results of
our empirical experiments. Our measurements show that a data
slice is indeed much smaller than the corresponding backward
slice and is computable in comparable time.
In future, we would like to investigate the minimality of
data slices and efficient algorithms to compute them. We would
also like to explore the effectiveness of data slices for much
larger programs.

