Software Engineering Methodologies
Program Slicing
Michael L. Collard, Ph.D.
Department of Computer Science, The University of Akron
Types of slices
- Backward static slice
- Executable slice
- Forward static slice
- Dynamic slice
- Execution slice
- …
Slice Researchers
- Agrawal
- Binkley
- Gallagher
- Gupta
- Horgan
- Horwitz
- Korel
- Laski
- K. Ottenstein
- L. Ottenstein
- Reps
- Soffa
- Tip
- Weiser
History 1981
- Mark Weiser
- Studied programmers during debugging
- The mental abstraction people make when they are debugging a program
- Used Data Flow Equations
History 1984
- K. Ottenstein & L. Ottenstein
- PDG (Program Dependency Graph)
History 1990
- Horowitz, Reps, & Binkley
- Interprocedural
- SDG (System Dependency Graph)
Program Slicing [Weiser'82]
- A program slice consists of the parts of a program that (potentially) affect the values computed at some point of interest, referred to as a slicing criterion
- Often a slicing criterion consists of a pair:
- (line-number, variable)
- program slicing is the task of computing program slices
- A program slice is often computed from the PDG (Program Dependency Graph)
Slice Types
- Backward static slice [Weiser]
- Executable slice
- Forward static slice
- Dynamic slice
- Execution slice
Slice Levels
- intraprocedural
- Within a particular procedure (function/method)
- interprocedural
- Between procedures (functions/methods)
Static Backward Slicing
- A backward slice of a program with respect to a program point p and set of program variables V consists of all statements and predicates in the program that may affect the value of variables in V at p
- The program point p and the variables V together form the slicing criterion, usually written <p, V>
Static Backward: Criterion <9, product>
1. int n = read();
2. int i = 1;
3. int sum = 0;
4. int product = 1;
5. while (i <= n) {
6. sum = sum + i;
7. product = product * i;
8. i = i + 1; }
9. println(sum);
10. println(product);
1. int n = read();
2. int i = 1;
3. int sum = 0;
4. int product = 1;
5. while (i <= n) {
6. sum = sum + i;
7. product = product * i;
8. i = i + 1; }
9. println(sum);
10. println(product);
Static Backward: Criterion <9, sum>
1. int n = read();
2. int i = 1;
3. int sum = 0;
4. int product = 1;
5. while (i <= n) {
6. sum = sum + i;
7. product = product * i;
8. i = i + 1; }
9. println(sum);
10. println(product);
1. int n = read();
2. int i = 1;
3. int sum = 0;
4. int product = 1;
5. while (i <= n) {
6. sum = sum + i;
7. product = product * i;
8. i = i + 1; }
9. println(sum);
10. println(product);
Static Backward: Criterion <9, product> vs Criterion <9, sum>
1. int n = read();
2. int i = 1;
3. int sum = 0;
4. int product = 1;
5. while (i <= n) {
6. sum = sum + i;
7. product = product * i;
8. i = i + 1; }
9. println(sum);
10. println(product);
1. int n = read();
2. int i = 1;
3. int sum = 0;
4. int product = 1;
5. while (i <= n) {
6. sum = sum + i;
7. product = product * i;
8. i = i + 1; }
9. println(sum);
10. println(product);
Static Backward: Criterion <9, product>
1. int n = read();
2. int sum = 0;
3. int i = 1;
4. while (i <= n) {
5. sum = sum + i;
6. i = i + 1; }
7. int product = 1;
8. int j = 1;
9. while (j <= n) {
10. product = product * j;
11. j = j + 1; }
12. println(sum);
13. println(product);
1. int n = read();
2. int sum = 0;
3. int i = 1;
4. while (i <= n) {
5. sum = sum + i;
6. i = i + 1; }
7. int product = 1;
8. int j = 1;
9. while (j <= n) {
10. product = product * j;
11. j = j + 1; }
12. println(sum);
13. println(product);
Static Backward: Criterion <9, sum>
1. int n = read();
2. int sum = 0;
3. int i = 1;
4. while (i <= n) {
5. sum = sum + i;
6. i = i + 1; }
7. int product = 1;
8. int j = 1;
9. while (j <= n) {
10. product = product * j;
11. j = j + 1; }
12. println(sum);
13. println(product);
1. int n = read();
2. int sum = 0;
3. int i = 1;
4. while (i <= n) {
5. sum = sum + i;
6. i = i + 1; }
7. int product = 1;
8. int j = 1;
9. while (j <= n) {
10. product = product * j;
11. j = j + 1; }
12. println(sum);
13. println(product);
Static Backward: Criterion <9, product> vs Criterion <9, sum>
1. int n = read();
2. int sum = 0;
3. int i = 1;
4. while (i <= n) {
5. sum = sum + i;
6. i = i + 1; }
7. int product = 1;
8. int j = 1;
9. while (j <= n) {
10. product = product * j;
11. j = j + 1; }
12. println(sum);
13. println(product);
1. int n = read();
2. int sum = 0;
3. int i = 1;
4. while (i <= n) {
5. sum = sum + i;
6. i = i + 1; }
7. int product = 1;
8. int j = 1;
9. while (j <= n) {
10. product = product * j;
11. j = j + 1; }
12. println(sum);
13. println(product);
Executable Slicing
- A slice is an executable slice if the statements in the slice form a syntactically correct program that can be executed
- If the slice is computed correctly (safely), the results of running the program that is the executable slice produces the same result for variables in V at p for all inputs
Executable Slicing: Criterion <9, product>
1. int n = read();
2. int i = 1;
3. int sum = 0;
4. int product = 1;
5. while (i <= n) {
6. sum = sum + i;
7. product = product * i;
8. i = i + 1; }
9. println(sum);
10. println(product);
1. int n = read();
2. int i = 1;
3. int sum = 0;
4. int product = 1;
5. while (i <= n) {
6. sum = sum + i;
7. product = product * i;
8. i = i + 1; }
9. println(sum);
10. println(product);
Static Forward Slicing
- A forward slice of a program with respect to a program point p and set of program variables V consists of all statements and predicates in the program that may be affected by the value of variables in V at p
- The program point p and the variables V together form the slicing criterion, usually written <p,V>
Static Forward Slicing: Criterion <3,sum>
1. int n = read();
2. int i = 1;
3. int sum = 0;
4. int product = 1;
5. while (i <= n) {
6. sum = sum + i;
7. product = product * i;
8. i = i + 1; }
9. println(sum);
10. println(product);
1. int n = read();
2. int i = 1;
3. int sum = 0;
4. int product = 1;
5. while (i <= n) {
6. sum = sum + i;
7. product = product * i;
8. i = i + 1; }
9. println(sum);
10. println(product);
Static Backward: Criterion <1, n>
1. int n = read();
2. int i = 1;
3. int sum = 0;
4. int product = 1;
5. while (i <= n) {
6. sum = sum + i;
7. product = product * i;
8. i = i + 1; }
9. println(sum);
10. println(product);
1. int n = read();
2. int i = 1;
3. int sum = 0;
4. int product = 1;
5. while (i <= n) {
6. sum = sum + i;
7. product = product * i;
8. i = i + 1; }
9. println(sum);
10. println(product);
Dynamic Slicing
- A dynamic slice of a program with respect to an input value of a variable v at a program point p for a particular execution e of the program is the set of all statements in the program that affect the value of v at p.
- The program point p, the variables v, and the input i for e form the slicing criterion, usually written <i, v, p>
- The slicing uses the execution history for the program with input i
Dynamic Slicing
1. int n = read();
2. for (i in 1...n) {
3. int a = 2;
4. if (c1) {
5. if (c2) {
6. a = 4;
7. } else {
8. a = 6; } }
9. z = a; }
10. println(z);
Input: n = 1, c1 is true, c2 is true
Execution History: 1, 2, 3, 4, 5, 6, 9, 2, 10
Criterion: <1, 10, z>
Dynamic Slicing
1. int n = read();
2. for (i in 1...n) {
3. int a = 2;
4. if (c1) {
5. if (c2) {
6. a = 4;
7. } else {
8. a = 6; } }
9. z = a; }
10. println(z);
Input: n = 1, c1 is true, c2 is true
Execution History: 1, 2, 3, 4, 5, 6, 9, 2, 10
Criterion: <1, 10, z>
Static Slicing
1. int n = read();
2. for (i in 1...n) {
3. int a = 2;
4. if (c1) {
5. if (c2) {
6. a = 4;
7. } else {
8. a = 6; } }
9. z = a; }
10. println(z);
Criterion: <10, z>
Dynamic Slicing vs. Static Slicing
Criterion <1, 10, z>
1. int n = read();
2. for (i in 1...n) {
3. int a = 2;
4. if (c1) {
5. if (c2) {
6. a = 4;
7. } else {
8. a = 6; } }
9. z = a; }
10. println(z);
Criterion <10, z>
1. int n = read();
2. for (i in 1...n) {
3. int a = 2;
4. if (c1) {
5. if (c2) {
6. a = 4;
7. } else {
8. a = 6; } }
9. z = a; }
10. println(z);
Dynamic Slicing
1. int n = read();
2. for (i in 1...n) {
3. int a = 2;
4. if (c1) {
5. if (c2) {
6. a = 4;
7. } else {
8. a = 6; } }
9. z = a; }
10. println(z);
Input: n = 2, c1 is true, c2 is false on 1st iteration, true on 2nd
Execution History: 1, 2, 3, 4, 9, 2, 3, 4, 5, 6, 9, 2,10
Criterion: <1, 10, z>
Dynamic Slicing
1. int n = read();
2. for (i in 1...n) {
3. int a = 2;
4. if (c1) {
5. if (c2) {
6. a = 4;
7. } else {
8. a = 6; } }
9. z = a; }
10. println(z);
Input: n = 2, c1 is true, c2 is false on 1st iteration, true on 2nd
Execution History: 1, 2, 3, 4, 9, 2, 3, 4, 5, 6, 9, 2,10
Criterion: <1, 10, z>
Execution Slicing
- An execution slice of a program with respect to an input value of a variable v is the set of statements in the program that are executed with input v.
Execution Slicing
1. int n = read();
2. for (i in 1...n) {
3. int a = 2;
4. if (c1) {
5. if (c2) {
6. a = 4;
7. } else {
8. a = 6; } }
9. z = a; }
10. println(z);
Input: n = 1, c1 is true, c2 is true
Execution History: 1, 2, 3, 4, 5, 6, 9, 2, 10
Criterion: <1, 10, z>
Execution Slicing
1. int n = read();
2. for (i in 1...n) {
3. int a = 2;
4. if (c1) {
5. if (c2) {
6. a = 4;
7. } else {
8. a = 6; } }
9. z = a; }
10. println(z);
Input: n = 1, c1 is true, c2 is true
Execution History: 1, 2, 3, 4, 5, 6, 9, 2, 10
Criterion: <1, 10, z>
Creating Slices
- Data sources:
- Program Dependency Graph (PDG)
- execution traces
- Challenge: interprocedural (approaches, but can be complicated)
- Challenge: scalability