SwE 455 Program Slicing
Program slicing is a powerful technique that helps in debugging code effectively by reducing complexity, writing robust programs, and saving testing time. This analysis method, introduced by Mark Weiser, identifies program parts influenced by specific criteria, aiding in code maintenance and optimization. Explore variants like static, backward, forward slicing for efficient program analysis.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
SwE 455 Program Slicing
Our Goals Debug your thousands lines of code easily by reducing the complexity of the program Write a robust program before testing your code Save your regression testing time by limiting the tests to only those that exercise the changed code
Approach Break your code into smaller pieces
Program Slicing What is it? - A well-known program analysis and transformation technique that uses program statement dependence information to identify parts of a program that influence or are influenced by an initial set of program points of interest which is called the slice criteria - Introduced by Mark Weiser in his Ph.D. thesis (1979)
Program Slicing (contd) indirectly relevant Slice Slicing Criterion Source program Resulting slice slicing criterion is provided by the user
Variants of Program Slicing Many different variants of program slicing exist 1. Static Slicing 2. Backward Slicing 3. Forward Slicing 4. Dynamic Slicing 5. Conditional Slicing 6. Chopping Also Many Different tools, however Most program slicing tools are written for C but there are also some for C++ and Java Most of these have problems with dynamic binding, inheritance, polymorphism and performance
Example of backward slicing Static Slice criterion <12,i> 1 main( ) 2 { 3 int i, sum; 4 sum = 0; 5 i = 1; 6 while(i <= 10) 7 { 8 Sum = sum + 1; 9 ++ i; 10 11 12 13 } Cout<< sum; Cout<< i; }
Backward Slice Example public class SimpleExample { static int add(int a, int b){ return(a+b); } public static void main(final String[] arg){ } } int i = 1; int sum = 0; while (i < 11) { sum = add(sum, i); i = add(i, 1); } System.out.println("sum = " + sum); System.out.println("i = " + i); Slicing Criterion
Example of forward static slicing Slice criterion <3,sum> 1 main( ) 2 { 3 int i, sum; 4 sum = 0; 5 i = 1; 6 while(i <= 10) 7 { 8 sum = sum + 1; 9 ++ i; 10 } 11 Cout<< sum; 12 Cout<< i; 13}
Forward Slice Example public class SimpleExample { static int add(int a, int b){ return(a+b); } public static void main(final String[] arg){ } } Slicing Criterion int i = 1; int sum = 0; while (i < 11) { sum = add(sum, i); i = add(i, 1); } System.out.println("sum = " + sum); System.out.println("i = " + i);
What is program slicing? Program slice must satisfy the following conditions Slice S(V,n) must be derived from P by deleting statements from P Slice S(V,n) must be syntactically correct For all executions of P, the value of V in the execution of S(V,n) just before the location n must be the same value of V in the execution of the program P just before location n
Example of program slicing Original program: Slice criterion: <9, x> 1 begin 2 read(x,y) begin Slice criterion: 3 total := 0.0 read(x,y) <12, z> 4 sum := 0.0 end. begin Slice criterion: 5 if x <= 1 read(x,y) <12, total> 6 then sum := y if x <= 1 7 else begin begin then 8 read(z) read(x,y) else read(z) 9 total := x*y total := 0 end. 10 end if x <= 1 11 write(total, sum) then 12 end. else total := x*y end.
Variants of program slicing Static slices Slice criterion <p, V> Where p is a program point and V is a subset of program variables Program slice on the slicing criterion <p, V> is a subset of program statements that preserves the behavior of the original program at the program point p with respect to the program variables in V
Variants of program slicing Static slices Slices derived from the source code for all possible input values No assumptions about input values May lead to relatively big slices Contains all statements that may affect a variable for every possible execution Current static methods can only compute approximations
Static slices example Slice criterion (12,i) 1 main( ) 2 { 3 int i, sum; 4 sum = 0; 5 i = 1; 6 while(i <= 10) 7 { 8 sum = sum + 1; 9 ++ i; 10 11 12 13 } Cout<< sum; Cout<< i; }
Example of dynamic slices Assumptions Input n is 1 C1, c2 both true Execution history is 11, 21, 31, 41, 51, 61, 91, 22, 101 Slice criterion<1, 101, z> 1. read (n) 2. for I := 1 to n do 3. a := 2 4. if c1==1 then 5. if c2==1 then 6. a := 4 7. else 8. a := 6 9. z := a 10. write (z)
Applications of program slices Program debugging Was introduced by Mark Weiser as debugging aid Slicing visualizes control and data dependencies It highlights statements influencing the slice Testing: reduce cost of regression testing after modifications (only run those tests that needed) Integration : merging two programs A and B that both resulted from modifications to BASE
Applications of program slices Program understanding Reverse engineering: comprehending the design by abstracting out of the source code the design decisions Software maintenance: changing source code without unwanted side effects Software quality assurance: validate interactions between safety-critical components
