プログラムスライス
井上克郎
大阪大学/
奈良先端科学技術大学院大学

Empirical Evaluation of theProgram Slicing for Fault
Localization

Background of Research• Software Systems are becoming large andcomplex– Debugging, testing, and maintaining costs areincreasing• To reduce development costs, techniques for
improving efficiency of such activities are
essentialLocalization• Handling large source programs is difficult• If we could select specific portions in thesource programs and we can concentrate ourattentions only to those portions, theperformance of the activities would increaseProgram Slicing• A technique of extracting all program
statements affecting the value of a variable• Specify a variable concerned and extract theaffecting statements• Developers can concentrate their attentions
to the extracted statements
Slicing: Extraction
Slice: Collection of extracted statements

Static Slicing• All statements possibly affecting the value of
Slice Criterion (a variable concerned)• Method(1) Construct Program Dependence Graph (PDG)
Nodes: statements in program
Edges:• Data Dependence (DD): variable definition and its
reference• Control Dependence (CD): predicate and statementdominated by the predicate(2) Collect all reachable nodes on PDG to a slice
criterion (statement, variable)

Example of PDG
s1 begins2a:=3;s3b:=3;s4
readln(c);s5if c=0 then
s6
begin
s7
d:=functionA(a);s8e:=ds9end;s10 else
s11 begins12
d:=functionB(b);s13e:=ds14 end;
s15 writeln(e)s16end.

Example of Static Slices1 begins2a:=3;s3b:=3;s4
readln(c);s5if c=0 then
s6
begin
s7
d:=functionA(a);s8e:=ds9end;s10 else
s11 begins12d:=functionB(b);s13e:=ds14 end;
Slicing criterion (s13, d)
s15 writeln(e)s16end.

Example of Static Slice (2)s1 begins2a:=3;s3b:=3;s4
readln(c);s5if c=0 then
s6
begin
s7
d:=functionA(a);s8e:=ds9end;s10 else
s11 begins12d:=functionB(b);s13e:=ds14 end;
s15 writeln(e)Slicing criterion (s15, e)s16end.

Debug Supporting Tool
• Target language: subset of Pascal– conditional, assignment, iterative, input/output,
procedure-call, compound statement etc.
– variables : integer, string, boolean, and arrays ofthem.

• Functions:– Calculate static slice.
– Step execution, referring the values of variables,
setting the breakpoints, etc

Snapshot of Osaka Slicing System

Objective• We aim to empirically evaluate the potential
usefulness of the program slicing to the fault
localization.

Process of Experiment• Step1: To conduct the experiments efficiently,
we construct software debugging support tool
based on the static slicing.
• Step2: We conduct two experimental projects
to evaluate the usefulness of the slicing for
fault localization.
– Experiment 1: (with debugging support tool)– Experiment 2:

Experiment 1
Objective• We empirically evaluate the following twohypotheses:– (H1)Using slicing technique reduces the fault
localizing effort.
– (H2)There exists some kinds of faults that arelocalized effectively.

Experiment 1Overview
Group1(Three subjects)

Group2(Three subjects)

PG1/Slicing-based
Trial1
fault localization

PG1/Conventional
debugger-based
fault localization

PG2/Conventional
Trial2 debugger-based
fault localizationPG2/ Slicing-based
fault localization

Experiment 1Programs• W used two programs (PG1 and PG2) whichwere developed based on the samespecification for the inventory control programat wine shop.
• Since they were developed independently,
their data structures and the algorithms werenot identical.

Experiment 1
Type of Faults
Faults in PG1• Lack of the output
processing,• Illegal assignment,• Illegal conditional statement,• Omission of the initialization,• Lack of the procedure call,• Wrong data renovation,• Wrong parameter for theprocedure call, and• Wrong execution order forsome procedure calls.

Faults in PG2• Illegal conditional statement,• Illegal conditional statement,• Wrong reference to array variable,• Wrong execution order for someprocedure calls,• Wrong parameter for theprocedure call,• Lack of the procedure call,• Wrong data renovation,• Illegal output,• Wrong registration for database.

Experiment 1- Analysis for (H1) Group1

Group2

Trial1122 (min.)(slice)155 (min.)(no slice)

Trial2133 (min.)(no slice)

114 (min.)(slice)

The group that used the slicing technique couldlocalize the faults effectively.

Experiment 1- Analysis for (H2) -Trial1

Trial2Type of fault

Average time tolocalize

Illegal conditional
statementGroup1: 14 (min.)Group2: 33 (min.)Lack ofprocedure callGroup1: 19 (min.)Group2: 34 (min.)Wrong data
renovation

Group1: 12 (min.)Group2: 19 (min.)Illegal conditional
statementGroup2: 19 (min.)Group1: 34 (min.)Wrong registration
for database

Group2: 12 (min.)Group1: 19 (min.)This difference isconfirmed by the theWelch test (α=0.05)

Slicing is effective to localize these faults.

Experiment 2- Objective • In Experiment 1, we could not collect enoughsubjects to statistically confirm all hypotheses
because of its expensiveness.
• To resolve this limitation, we have also
carried out an inexpensive experiment, called
Experiment 2, which aimed to examine
usefulness of the slicing to the fault
localization for small scale programs withmore subjects and less management effort.

Experiment 2
Overview
Group1(15 subjects)

Group2(19 subjects)

Six programs(P1’-P6’)
Six programs (P1-P6)/Conventional
Slicing-based
Targetdebugger-based
fault localization
fault localization
P1-P6: programs with slicing information
P1’-P6’: only programs

Experiment 2
Programs• Six kinds of Pascal programs each of which
includes one fault (illegal conditional or illegal
assignment statement )– (P1)Factorization,– (P2)Decision whether the input number is a primenumber,– (P3)Construction of a Triangle of Pascal,– (P4)Numerical operations,– (P5)Permutation ,– (P6)Sorting.

Experiment 2- Analysis for (H1) -AveragetimeGroup1

Group240.73 (min.)(slice)49.11(min.)(no slice)
This difference is confirmed by the the Welch test (α=0.05)

The group that used the slicing technique could
localize the faults effectively.

Experiment 2- Analysis for (H2) Type of fault

Average time tolocalize

Illegal conditional
statement in P3

Group1: 7.13 (min.)Group2: 11.63min.)Illegal conditional
statement in P6

Group1: 3.07 (min.)Group2: 4.53 (min.)

These faults are included in such programs that it isvery difficult to grasp the correspondence its
algorithm to its code.

Findings• We have empirically evaluated the potential
usefulness of the program slicing to the faultlocalization.
• Number of subjects are small. However, wewould say that the program slicing is usefulfor the fault localization.

Lightweight Semi-Dynamic
Slicing Methods

Dynamic Slicing• All statements actually affecting the value of aslice criterion for an execution with a particular
input data
• Useful for debugging with testcase• Method(1) Execute program with an input data and record theexecution trace(2) Determine DD and CD on each statement of thetrace(3) Collect reachable statements to a slice criterion(input-data, execution-point, variable)

Example of Dynamic Slicing
s1 begins2a:=3;s3b:=3;s4readln(c);s5if c=0 thens6begins7d:=functionA(a);s8e:=ds9end;s10 else
s11 begins12d:=functionB(b);s13e:=ds14 end;
s15 writeln(e)s16end.

e1 begine2a:=3;e3b:=3;e4readln(c);e5if c=0 then
e6
begin
e7
d:=functionA(a);e8e:=de9end;

Source(1) Execute Trace with Input c=0

e15 writeln(e)e16end.

Example of Dynamic Slicing (cont.)
e1 begine2a:=3;e3b:=3;ae4readln(c);c e5
if c=0 then
e6
begin
e7
d:=functionA(a);d e8e:=de9end;

eSlicing Criterion (c=0, s15, e)e15 writeln(e)e16end.
(2) Determine DD and CDDDCD

s1 begins2a:=3;s3b:=3;s4
readln(c);s5if c=0 then
s6
begin
s7
d:=functionA(a);s8e:=ds9end;s10 else
s11 begins12
d:=functionB(b);s13e:=ds14 end;
s15 writeln(e)s16end.
(3) Collect Statements

Static and Dynamic Slicing• Analysis cost:static < dynamic– Recording execution trace is exhaustive– Determining DD & CD on execution trace isexpensive
PDG << Execution Trace• Slice size:

static> dynamic– Static slicing considers all possible flows– Dynamic slicing only considers one traceUnifying Static and Dynamic Information

Static information+Lightweight dynamic information

Efficient and effective slicing

Approach to Call-Mark(CM) Slicing• (static slice
unexecuted programstatements)• Unexecuted statements are explored by– Checking activation of procedure/function calls– Delete unexecuted call statements and associatedstatements– The associated statements: executiondependency (statically determined)Execution Dependency and CED• s1 is executionally dependent (ED) on s2 iffs1 cannot be executed when s2 is not
executed– Easily obtained by flow analysis• CED(s) is a set of caller statements on whichfunctionXs is executionally depending– If any of CED(s) is known to be unexecuted,...
then we know that s is never executed
functionY– Also by flow analysis
...

...
s...

s2...
...

s1

Example of CED
s1
s2
s3s4s5functionA ;if a=1 thenbeginb:= c;
functionB ;ED(part of)CED(s2) = {s1}CED(s4) = {s1, s5}

Steps for Call-Mark Slicing(1) Construct PDG and compute CED for each statement(pre-execution analysis)(2) Prepare a flag for each call statement, and executeprogram with input data. Mark the flag if the callstatement is executed(3) Delete unexecuted nodes and associated edges fromPDG
if any flag in CED(s) is not marked, s is know to be unexecuted(4) Collect reachable statements to a slice criterion

Example of Call-Mark Slice (Step1)
s1 begins2a:=3;s3b:=3;s4readln(c);s5if c=0 thens6begins7d:=functionA(a);s8e:=ds9end;s10 else
s11 begins12d:=functionB(b);s13e:=ds14 end;
s15 writeln(e)s16end.

CED(s2) = {}...
CED(s7) = {s7}CED(s8) = {s7}CED(s12) = {s12}CED(s13) = {s12}CED(s15) = {}Example of Call-Mark Slice (Step2)
s1 begins2a:=3;s3b:=3;s4readln(c);s5if c=0 thens6begins7d:=functionA(a);s8e:=ds9end;s10 else
s11 begins12d:=functionB(b);s13e:=ds14 end;
s15 writeln(e)s16end.

Execution with input c=0

X Flag(s7)Flag(s12)
Flag(s7) : marked
Flag(s12) : not marked

Example of Call-Mark Slice(Step3 & 4)
CED(s2) = {}...
CED(s7) = {s7}CED(s8) = {s7}CED(s12) = {s12}CED(s13) = {s12}CED(s15) = {}DDCDEDs1 begins2a:=3;s3b:=3;s4
readln(c);s5if c=0 thens6begins7d:=functionA(a);s8e:=ds9end;s10 else
s11 begins12d:=functionB(b);s13e:=ds14 end;
s15 writeln(e)s16end.

Slice criterion (c=0, s15, e)Implementation of Call-Mark Slicing• Implement steps (1) - (4)– flag <--> each call statement• Flags are not necessary to be associated withcaller codes• Modify calling mechanism and do not modify
other codes– Steal the return addresses from the calling stack– Determine which caller statements are actuallyexecutedArchitecture of Osaka Slicing System

Osaka Slicing System

Approach to Dependence-Cache Slicing• Limitation of static analyses for arrays andpointer variables?

1: a[0]:=0;
2: a[1]:=3;
3: readln(b);?
4: a[b]:=2;
5: c:=a[0]+4;
6: writeln(c);Overview of Dependence-Cache Slicing• Control dependences are analyzed statically• Data dependences are collected dynamicallyat program execution– Use dependence cache for each variables• PDGDC is constructed when program halts• PDGDC is traversed from a slice criterionDependence Analysis
Change of Caches

Input: b=0

1: a[0]:=0;
2: a[1]:=3;
b3: readln(b);a[0] 4: a[b]:=2;
c 5: c:=a[0]+4;
6: writeln(c);1:2:3:4:
5:
6:

a[0]
11
14
4
4

a[1]
22222b3
3
3
3

c5
5

Evaluation (1)• Experiments with several sample programsSize of Various Slices (lines of code)

ProgramP1(85lines)
P2(387lines)
P3(871lines)

Static Call-Mark D-Cache Dynamic
21
17
15
5182
162
16
5187
166
61
8

Evaluation (2)Pre-Execution Analysis Time
(ms by Celeron 450MHz with 128MB)

ProgramP1P2P3

StaticCall-Mark D-Cache Dynamic
1114
5
N/A
213
215
19
N/A
710
698
48
N/A

Evaluation (3)Execution Time
(ms by Celeron 450MHz with 128MB)

Program
P1P2P3

StaticCall-Mark D-Cache Dynamic
4747
51
174
43
43
45
4,540
4,700
4,731
4,834 216,464

Evaluation (4)Slice Construction Time
(ms by Celeron 450MHz with 128MB)

Program
P1
P2
P3

StaticCall-Mark D-Cache Dynamic
0.4
0.6
0.3
76.0
1.9
1.8
0.7
101.0
3.0
3.0
1.2 24,969.3

Discussions• Analysis cost:static ≤ call-mark < d-cache << dynamic
Slice size:
static > call-mark > d-cache > dynamic• Reasonable slice results with reasonable
analysis time• Promising approach to get effective program
localization

Related Works• Optimized Approaches for DynamicSlicing(Agrawal & Horgan)– Still large execution overhead• Hybrid Slicing(Guputa & Soffa)– Collect all traces between break points and proc.
calls– Need to specify break points/ Trace can be huge

• Parametric Slicing(Field & Ramalingam)– Generalize static and dynamic slicing by symbolic
execution with input data subset– Practicability and usefulness are unknown

On-Going Works• Compiler-based lightweight semi-dynamic
slicing environment• Java program analysis– Bytecode analyses– Alias analysis for Java programs– GUI for alias information

課題• プログラムスライスの研究動向調査• プログラムスライスの原点の論文の要約• プログラムスライスの応用に関する調査 田中、
岡本– 応用分野– 商用システム

1:
2:
3:
4:
5:
6:
7:
8:
9:

prod :=1 ;sum :=0 ;x:=1 ;
while x=<10 do begin
prod:= prod*x ;sum := sum + x ;x:= x +1 ;end;
mean:= sum/10 ;writeln(prod,sum,mean);

123
45678get(low,high,step,A)
min:=A[low];
max:=A[low];
sum:=A[low];
i:=low+step;
While i=< high do
if max<A[i] thenmin:=A[i] ;end if
9if min>A[i] then10min:=A[i];end if11
sum:=sum+A[i];12i:=i+step ;end loop;
13 put(min,max,sum);