Programing Slicing and Its applications

Indian Institute of Technology, Kharagpur
Date : 27 March-2014 Ankur Jain, Dept of Computer Sc & Engg., IIT Kgp
Presented By-
Ankur Jain (13CS60D02)

Programmer’s Nightmare…
If I change this statement in program:
What other statements would be affected?
(Impact analysis)
What other statement needs to be tested?
(Regression test)
The values live at this statement:
Defined where?
Modified Where?
(Manual Checking)
How can I abstract code?

Studies show….
Software testing contributes more then
50% of cost and time of SDLC
Maintainers spend nearly 50% of their
time trying to understand the program
Source: http://www.ece.cmu.edu/~koopman/des_s99/sw_testing/

Try...
Program Slicing!

Outline
 Introduction
 Types of Slicing
 Program Models
 Flow based
 Dependency based
 Slicing Algorithms
 Challenges
 Directions of research

Proposed by…
 Proposed by Mark Weiser in 1981
 Chief scientist at Xerox PARC
 As his PhD thesis
 Father of ubiquitous computing
Mark D. Weiser
(July 23, 1952 - April 27, 1999)

Basic Concepts…
“For statement S and variable V, the slice of program P
includes only those statements of P needed to capture the
behavior of V at S.”
Slicing Criterion (SC):
<S, V>
S = Point of interest in the program (statement)
V = Subset of variables used in the program
A program slice is a subset of a program

Example…
1 begin
2 read(x, y)
3 total := 0.0
4 sum := 0.0
5 if x <= 1
6 then sum := y
7 else begin
8 read(z)
9 total := x*y*z
10 end
11 write(total, sum)
12 end
SC = <11, sum>
2 read(x, y)
4 sum := 0.0
5 if x <= 1
6 then sum := y
Slicing Criterion

Why is Program Slicing Useful?
• Program slices are more manageable for
testing and debugging
• During testing, debugging, or understanding a program,
most of the code in the program is irrelevant to what you
are interested in.
• Program slicing provides a convenient way of filtering out
“irrelevant” code.

Slice Variants…
Types of slices:
 Static
 Dynamic
Direction of slice:
 Forward
 Backward
Executability of slice:
 Executable
 Non-executable
Amorphous, etc.

Froward Slices Vs Backward Slices
Statements which might affect
the value of variables in V
Statements which might be
affected by the values of
variables in V
int i, sum, prd;
1. read(i);
2. prd = 1;
3. sum = 0;
4. while (i<10)
5. sum = sum + i;
6. prd = prd * i;
7. i = i + 1;
8. write(sum);
9. write(prd);For SC = <9, prd>
Slice: {1, 2, 4, 6, 7}
For SC = <2, prd>
Slice: {6, 9}
Backward Slices:
Froward Slices

Static Slice | Dynamic Slice
Using dynamic information
(an execution trace)
Debugging
Set of all statements that actually
affect the value of a variable at a
program point
Using static information
(a source program)
Regression Testing
Set of all statements that may
affect the value of a variable at a
program point

Example…
int i, sum, prd;
1. read(i);
2. prd = 1;
3. sum = 0;
4. while (i<10)
5. sum = sum + i;
6. prd = prd * i;
7. i = i + 1;
8. write(sum);
9. write(prd);
Static Slice
{1, 2, 4, 6, 7}
Dynamic Slice
For Input ‘i’ = 15
{2}
For Slicing Criteria [SC] = <9, prd>
Flow based model:
Control flow
 Data flow
Dependency based model:
 Data Dependency
 Control Dependency
Slicing Criterion

Dependency Based Model
Program Code
Control Flow
Graph
(CFG)
Data
Dependency
Graph (DDG)
Program
Dependency
Graph (PDG)
Forward
Dominance Tree
Control
Dependency
Graph (CDG)

Data Dependency Graph (DDG)
int a, b, sum;
1. read(a);
2. read(b);
3. sum = 0;
4. while(a<8)
5. sum = sum + b;
6. a = a + 1;
7. write(sum);
8. sum = b;
9. write(sum);
4 5
6
7
8
9
21 3
Data Dependency Graph

Control Flow Graph (CFG)
int a, b, sum;
1. read(a);
2. read(b);
3. sum = 0;
4. while(a<8)
5. sum = sum + b;
6. a = a + 1;
7. write(sum);
8. sum = b;
9. write(sum);
Start
1
Stop
4
5
3
6
2
8
7
9
True
False
True
True
True
True
True
True
True
True
True

Dominance
Let X and Y be two nodes in a Control flow graph
X dominates Y
If and only if
Every path from Start to Y passes through X
Y forward dominates X
The forward Dominance Tree (FDT)
1. Vertices represent statement
2. Root node of tree is exit node of the CFG
3. Arcs represent immediate forward dominance

Forward Dominance Tree (FDT): Using CFG
9
4 6
7
5
8
2
3
1
Start
1
Stop
4
5
3
6
2
8
7
9
True
False
True
True
True
True
True
True
True
True
True

Control Dependency Graph: Using CFG & FDT
4
5 6
7
8
9
2
1
3
S
1. Y is control dependent on X
2. Path in the CFG from X to Y
3. Doesn’t contain the
immediate forward
dominator of X
Y
X
X
Ifdom(4)=7
X
Y

Control Dependency Graph (CDG)
int a, b, sum;
1. read(a);
2. read(b);
3. sum = 0;
4. while(a<8)
5. sum = sum + b;
6. a = a + 1;
7. write(sum);
8. sum = b;
9. write(sum);
4
5 6
7
8
9
2
1
3
S

Program Dependency Graph (PDG)
int a, b, sum;
1. read(a);
2. read(b);
3. sum = 0;
4. while(a<8)
5. sum = sum + b;
6. a = a + 1;
7. write(sum);
8. sum = b;
9. write(sum);
Union of CDG and DDG
1
4
6
5
8
29
3
7
Data dependence
Control dependence
Limitation: A PDG can model programs with a single
function Not suitable for inter-procedural slicing

System Dependency Graph Model: by- Horwitz
Basic Idea:
Connect PDGs with auxiliary dependence edges
• Parse source code - one procedure at a time.
– Construct the CDG for each procedure including main.
• Add actual and formal parameter nodes:
– Connect using parameter-in, parameter-out edges
• Represent function calls
– Using call edges
• Find data dependencies:
– Perform data flow analysis of the CDGs
– Connect data dependence edges
• Add summary edges
Steps in SDG Construction

System Dependency Graph (SDG)
Control Dependence
Data Dependence
Call, Parameter−in,
Parameter−out
Summary Edge
bin = b
ain = a
entry add
Entry main
a = 0
b = 1
add(a, b)
a =ain
b = bin
a = a+b
c = aout
aout = a
main(){
int a, b;
a = 0;
b = 1;
c=add(a, b);
}
void add(int a, int b)
{
a = a + b;
return a;
}

Slicing an SDG: Two phase algorithm
Proposed by Horwitz et al
• Pass1: From the slice point:
• Traverse backward along all edges except
parameter-out edges
• Mark the reached vertices
• Pass 2: From vertices marked in Pass 1
• Traverse backwards along all edges:
• Except call and parameter-in edges

Slicing an SDG: Pass-1
Control Dependence
Data Dependence
Parameter−out
Summary Edge
main(){
int a, b;
a = 0;
b = 1;
c=add(a, b);
}
{
a = a + b;
return a;
}
entry main
a = 0
b = 1
add(a, b)
entry add
a =ain
b = bin
a = a+b
aout = a
c = aout
bin = b
ain = a
Slice Point
Except parameter-out edges

Slicing an SDG: Pass-2
Control Dependence
Data Dependence
Parameter−out
Summary Edge
main(){
int a, b;
a = 0;
b = 1;
c=add(a, b);
}
{
a = a + b;
return a;
}
entry
main
a = 0
b = 1 add(a, b)
entry add
a =ain
b = bin
a = a+b
aout = a
c = aout
bin = b
ain = a
Slice Point
Except call and parameter-in edges

Dynamic Slicing: Example cont…
Consider the following program:
Computing:
product of odd (p), sum of even (s)
Execution Trace, N=3
1,2,3,4 //intial
5,6,8,9 //i=1
5,6,7,9 //i=2
5,10 //i=3, end
Which part of the
program is responsible
for computing sum?

We need to compute a backward slice with slicing criterion
<(10, s)>
Dependencies:
Dynamic Data Dependence:
which variable assignment was propagated to the value of `s' ?
Dynamic Control Dependence:
which are the conditional branches that executed till line 10
and in what order?

For N=3

The Dynamic Slice w.r.t. (10,s)

Slicing Tools
• Unravel : Static slicing tool for ANSI C
• WET : Whole Execution Traces, dynamic slicing
• CodeSurfer : Commercial static slicing tool for C
• Performs data flow and control dependence analysis
• Indus : Static slicer for Java
• Available for Eclipse via Kaveri plugin
• JSlice : Dynamic slicing tool for Java
• SPYDER: Debugging tool
• Performs both static and dynamic slice

Further Reduction in Size of Slice…
Amorphous Slice:
 No Syntax Preservation
 Retaining the semantic property
Applications:
 Re-engineering
 Component Re-use
 Program Comprehension
 Testing & Maintenance
 Program Integration

Amorphous Slice: Example
for(i = 0,sum = a[0], biggest = sum; i<19; sum = a[++i])
if (a[i+1] > biggest)
{
biggest = a[i+1];
average = sum/20;
}
Amorphous slice
for(i = 1, biggest = a[0]; i<20; ++i)
{
if (a[i]>biggest)
biggest = a[i];
}
Traditional slice
for(i = 0,sum = a[0], biggest = sum; i<19;
sum = a[++i])
if (a[i+1] > biggest)
{
biggest = a[i+1];
}
Slicing Criterion
Loop unrolling

Challenges: For further reading…
 Slicing Object-Oriented Programs
 Effect of Exceptions on Control Flow
 Slicing UML Models
 Slicing of threaded programs
 Slicing Concurrent and Distributed Programs

Directions of Research
A Novel Fault Localization Technique

References
[1] M Weiser. 1984. “Program slicing”
IEEE Transactions on Software Engineering 10(4):352–57
[2] F. Tip. 1995. A survey of program slicing techniques. Journal of
Programming Languages 3(3): 121–89
[3] D. P.Mohapatra, R.Mall, and R. Kumar. 2006.
“ An overview of slicing techniques for object-oriented
programs” Informatica 30(2):253–77
[4] G. B.Mund, R.Mall, and S. Sarkar. 2003. “Computation of intra-procedural
dynamic program slices. Information and Software Technology 45(8):499–512.

Questions

Programing Slicing and Its applications

Recommended

More Related Content

What's hot (20)

Viewers also liked (20)

Similar to Programing Slicing and Its applications (20)

Recently uploaded (20)

Programing Slicing and Its applications