Program Slicing Xiangyu Zhang What is a slice? Void main ( ) { int I=0; int sum=0; while (I

Testing Differencing Program understanding Software maintenance Complexity measurement / Functional Cohesion Program integration Reverse engineering Software Quality Assurance Old!

CS590F Software Reliability What Now Security Malware detection; Software piracy Software Transactional Memory Architecture Program optimization Value speculation PRE A program implement multiple semantic Data Lineage

functions. All are not relevant! More to come CS590F Software Reliability Outline Slicing ABC Dynamic slicing Efficiency Effectiveness Challenges CS590F Software Reliability Slicing Classification Static vs. Dynamic Backward vs. Forward Executable vs. Non-Executable

More CS590F Software Reliability How to do slicing? b=0 Static analysis a=2 Input insensitive May analysis 1 <=i <=N T if ((i++)%2= =1) Dependence Graph Characteristics

T F a=a+1 b=a*2 F Very fast Very imprecise z=a+b print(z) CS590F Software Reliability Why is a static slice imprecise? All possible program paths S1:x= S2:x= L1:=x Use of Pointers static alias analysis is very imprecise S1:a= S2:b= L1:=*p

Use of function pointers hard to know which function is called, conservative expectation results in imprecision CS590F Software Reliability Dynamic Slicing Korel and Laski, 1988 Dynamic slicing makes use of all information about a particular execution of a program and computes the slice based on an execution history (trace) A dynamic slice query is a triple Trace consists control flow trace and memory reference trace ` Smaller, more precise, more helpful to the user CS590F Software Reliability Dynamic Slicing Example -background For input N=2, 1: b=0 2: a=2 3: for i= 1 to N do 4: if ((i++)%2==1) then `

5: a = a+1 else 6: b = a*2 endif done 7: z = a+b 8: print(z) 11: b=0 [b=0] 21: a=2 31: for i = 1 to N do [i=1] 41: if ( (i++) %2 == 1) then [i=1] 51: a=a+1 [a=3] 32: for i=1 to N do [i=2] 42: if ( i%2 == 1) then [i=2]

61: b=a*2 [b=6] 71: z=a+b [z=9] 81: print(z) [z=9] Reliability CS590F Software Issues about Dynamic Slicing Precision perfect Running history very big ( GB ) Algorithm to compute dynamic slice - slow and very high space requirement. CS590F Software Reliability Backward vs. Forward 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 } An Example Program & its forward slice w.r.t. <3, sum> CS590F Software Reliability

Executable vs. Non-Executable CS590F Software Reliability Comments Want to know more? Frank Tips survey paper (1995) Static slicing is very useful for static analysis Code transformation, program understanding, etc. Points-to analysis is the key challenge Not as useful in reliability as dynamic slicing We will focus on dynamic slicing Precise

good for reliability. Solution space is much larger. There exist hybrid techniques. CS590F Software Reliability Outline Slicing ABC Dynamic slicing Efficiency Effectiveness Challenges CS590F Software Reliability Efficiency How are dynamic slices computed? Execution traces

control flow trace -- dynamic control dependences memory reference trace -- dynamic data dependences Construct a dynamic dependence graph Traverse dynamic dependence graph to compute slices CS590F Software Reliability How to Detect Dynamic Dependence Dynamic Data Dependence Virtual Space Shadow Space Shadow space (SS) Addr Abstract State [r2] s1x [r1] s1x: ST r1, [r2] SS(r2)=s1x

s2y: LD [r1], r2 s2y SS(r1)=s1x Dynamic control dependence is more tricky! CS590F Software Reliability Dynamic Dependence Graph Sizes Statements Executed (Millions) Dynamic Dependence Graph Size(MB) 300.twolf 140 1,568 256.bzip2 67 1,296 255.vortex 108 1,442 197.parser

123 1,816 181.mcf 118 1,535 134.perl 220 1,954 130.li 124 1,745 126.gcc 131 1,534 099.go 138 1,707 Program

On average, given an execution of 130M instructions, the constructed dependence graph requires 1.5GB space. CS590F Software Reliability Conventional Approaches [Agrawal &Horgan, 1990] presented three algorithms to trade-off the cost with precision. Algo.I Static Analysis Cost: low Precision: low Algo.II Algo.III Precise dynamic analysis high high CS590F Software Reliability Algorithm One This algorithm uses a static dependence graph in

which all executed nodes are marked dynamically so that during slicing when the graph is traversed, nodes that are not marked are avoided as they cannot be a part of the dynamic slice. Limited dynamic information - fast, imprecise (but more precise than static slicing) CS590F Software Reliability Algorithm I Example 1: b=0 For input N=1, the trace is: 2: a=2 11 3: 1 <=i <=N 21 T 4: if ((i++)%2= =1) T F 5: a=a+1 6: b=a*2 7: z=a+b

8: print(z) F 31 41 51 32 71 81 CS590F Software Reliability Algorithm I Example 1: b=0 2: a=2 DS={1,2,5,7,8} 3: 1 <=i <=N 4: if ((i++)%2= =1) 5: a=a+1 Precise! 6: b=a*2 7: z=a+b 8: print(z) CS590F Software Reliability Imprecision introduced by Algorithm I

Input N=2: 4 7 9 Killed definition counted as reaching! Aliasing! 1 2 3 4 5 6 7 8 9 for (a=1; a

A dependence edge is introduced from a load to a store if during execution, at least once, the value stored by the store is indeed read by the load (mark dependence edge) No static analysis is needed. CS590F Software Reliability Algorithm II Example 1: b=0 For input N=1, the trace is: 11 2: a=2 3: 1 <=i <=N 21 T 4: if ((i++)%2= =1) T F 5: a=a+1 6: b=a*2 7: z=a+b F

31 41 51 71 81 8: print(z) CS590F Software Reliability Algorithm II Compare to Algorithm I More precise Algo. II Algo. I x= x= =x =x =x =x CS590F Software Reliability Imprecision introduced by Algorithm II A statically distinct load/store may be executed several times

during program execution. Different instances of a load may be dependent on different store instructions or different instances of a store instructions. S1:x= <1,1> S2:x= < 2, 1 > L1:=x Algo. 2 uses unlabeled edges. Therefore, upon inclusion of the load in the slice it will always include both the stores. CS590F Software Reliability Algorithm III First preprocess the execution trace and introduces labeled dependence edges in the dependence graph. During slicing the instance labels are used to traverse only relevant edges. CS590F Software Reliability Dynamic Dependence Graph Sizes (revisit) Statements Executed (Millions) Dynamic Dependence Graph Size(MB) 300.twolf

140 1,568 256.bzip2 67 1,296 255.vortex 108 1,442 197.parser 123 1,816 181.mcf 118 1,535 134.perl 220 1,954

130.li 124 1,745 126.gcc 131 1,534 099.go 138 1,707 Program On average, given an execution of 130M instructions, the constructed dependence graph requires 1.5GB space. CS590F Software Reliability Dynamic Dep. Graph Representation N=2: 1: sum=0 2: i=1 3: while ( i

4: i=i+1 5: sum=sum+i 3: while ( i

4: i=i+1 5: sum=sum+i 3 3: while ( i

CS590F Software Reliability Infer: Local Dependence Labels: Full Elimination (...,20) ... X= X= X= Y= X Y= X (10,10) (20,20) (30,30) Y= X 10,20,30 (20,21) ... =Y 21 CS590F Software Reliability Transform: Local Dependence Labels: Elimination In Presence of Aliasing

X= *P = Y= X 10,20 X= (10,10) X= (20,20) *P = *P = Y= X Y= X (20,21) ... =Y 11,21 CS590F Software Reliability Transform: Local Dependence Labels: Elimination In Presence of Aliasing X= *P =

X= (10,10) Y= X 10,20 (20,20) *P = Y= X (10,11) (20,21) X= X= *P = *P = Y= X Y= X 10 =Y 20 (10,11) (20,21)

=Y 11,21 11,21 CS590F Software Reliability Transform: Coalescing Multiple Nodes into One 1 1 2 2 3 4 4 5 6 3 5 7 7 3 6 8

3 4 6 7 9 1 1 2 2 3 3 4 3 5 46 6 6 7 7 8 9 99 53 5 6 88 9 9 10 10

CS590F Software Reliability Group: Labels Across Non-Local Dependence Edges X= X= 10 Y= 20 Y= X= X= Y= Y= =Y =X X= (10,21) (20,11) (20,11)

Y= (10,21) =Y =X X= (10,21) Y= (20,11) =Y =X 11,21 CS590F Software Reliability Space: Compacted Graph Sizes Graph Size (MB) Program Before / After Explicit Dependences (%) Before After 300.twolf

1,568 210 7.72 13.40 256.bzip2 1,296 51 25.68 3.89 255.vortex 1,442 65 22.26 4.49 197.parser 1,816 70

26.03 3.84 181.mcf 1,535 170 9.02 11.09 164.gzip 835 52 16.19 6.18 134.perl 1,954 21 93.40 1.07 130.li

1,745 97 18.09 5.53 126.gcc 1,534 75 20.54 4.87 099.go 1,707 131 13.01 7.69 Average 1,543 94

25.2 6.21 CS590F Software Reliability Breakdowns of Different Optimizations Infer Transform Group Others Explicit CS590F Software Reliability Efficiency: Summary For an execution of 130M instructions: space requirement: reduced from 1.5GB to 94MB (I further reduced the size by a factor of 5 by designing a generic compression technique [MICRO05]). time requirement: reduced from >10 Mins to <30 seconds. CS590F Software Reliability Generic Compression Traversable in compressed form Sequitur

Context-based Using value predictors;( M. Burtsher and M. Jeeradit, PACT2003) Bidirectional!! Queries may require going either direction The system should be able to answer multiple queries CS590F Software Reliability Compression using value predictors Value predictors Last n values; FCM (finite context method). Example, FCM-3 Uncompressed Left Context lookup table XYZ A XYZ A Compressed 1

CS590F Software Reliability Compression using value predictors Value predictors Last n values; FCM (finite context method). Example, FCM-3 Uncompressed Left Context lookup table XYZ B XYZ B A Compressed B Length(Compressed) = n/32 + n*(1- predict rate) Only forward traversable; CS590F Software Reliability Enable bidirectional traversal - idea Previous predictor compression: Compressed

Bidirection idea: CS590F Software Reliability Enable bidirectional traversal Forward compressed, backward traversed (uncompressed) FCM Traditional FCM is forward compressed, forward traversed Right Context lookup table Left Context lookup table Uncompressed XYZ A Compressed 1X Y Z A Uncompressed current context X YYZZ A A Bidirectional FCM

Right Context lookup table Left Context lookup table CS590F Software Reliability Bidirectional FCM - example 1A X XY Y Z1 111 Right Context lookup table A XYZ Left Context lookup table AXY Z CS590F Software Reliability Outline Slicing ABC Dynamic slicing Dynamic slicing practices Efficiency

Effectiveness Challenges CS590F Software Reliability The Real Bugs Nine logical bugs Four unix utility programs grep 2.5, grep 2.5.1, flex 2.5.31, make 3.80. Six memory bugs [AccMon project (UIUC)] Six unix utility programs gzip, ncompress, polymorph, tar, bc, tidy. CS590F Software Reliability Classic Dynamic Slicing in Debugging Buggy Runs LOC EXEC (%LOC)

BS (%EXEC) flex 2.5.31(a) 26754 1871 (6.99%) 695 (37.2%) flex 2.5.31(b) 26754 2198 (8.2%) 272 (12.4%) flex 2.5.31(c) 26754 2053 (7.7%) 50 (2.4%) grep 2.5 8581 1157 (13.5%) NA

grep 2.5.1(a) 8587 509 (5.9%) NA grep 2.5.1(b) 8587 1123 (13.1%) NA grep 2.5.1(c) 8587 1338 (15.6%) NA make 3.80(a) 29978 2277 (7.6%) 981 (43.1%) make 3.80(b)

29978 2740 (9.1%) 1290 (47.1%) gzip-1.2.4 8164 118 (1.5%) 34 (28.8%) ncompress-4.2.4 1923 59 (3.1%) 18 (30.5%) polymorph-0.4.0 716 45 (6.3%) 21 (46.7%) tar 1.13.25 25854 445 (1.7%)

105 (23.6%) bc 1.06 8288 636 (7.7%) 204 (32.1%) Tidy 31132 1519 (4.9 %) 554 (36.5%) 2.4-47.1% EXEC Avg 30.9% CS590F Software Reliability Looking for Additional Evidence Buggy Execution Classic dynamic slicing algorithms investigate bugs through negative evidence of the wrong output input0 input_x

input2 Other types of evidence: Failure inducing input predicate_x predicate_x output0 output1 Critical Predicate Partially correct output Benefits of More Evidence Narrow the search for fault Broaden the applicability output_x output_x CS590F Software Reliability Negative: Failure Inducing Input [ASE05] strcpy.c iname[1025]: aaaaaaaaa...aaaa

a ... (2) 40: for (; (*to = * from)!=0; ++from; ++to); ... gzip.c ... 193: char *env; 198: CHAR ifname[1024]; ... (1) 844: strcpy (ifname, iname); ... (3) 1344: ... free(env), ... The rationale

CS590F Software Reliability Negative: Failure Inducing Input [ASE05] Given a failed run: Identify a minimal failure inducing input ([Delta Debugging - Andreas Zeller]) This input should affect the root cause. Compute forward dynamic slice (FS) of the input identified failure inducing above input Input FS Output (a) CS590F Software Reliability Negative: Critical Predicate [ICSE06] The rationale CS590F Software Reliability Searching Strategies Execution Trace:

if (P1) ...... if (P2) if (P2) (3) (2) if (P1) ...... ...... (3) if (P3) ...... (2) if (P4) ...... (1) if (P5) (1) if (P4) ...... output() Dependence Distance Ordering

...... output() Control Flow Distance Ordering CS590F Software Reliability Slicing with Critical Predicate Given a failed run: Identify the critical predicate The critical predicate should AFFECT / BE AFFECTED BY the root cause. Compute bidirectional slice (BiS) of the critical predicate Input BiS(CP) FS(CP) + CP Output (a) CS590F Software Reliability All Negative Evidence Combined failure inducing

input Input BiS(CP) FS(CP) BS FS BS^FS + CP Output CS590F Software Reliability Negative Evidences Combined in Slicing Buggy Runs BS^FS^BiS (%BS) BS flex 2.5.31(a) 695 27 (3.9%) flex 2.5.31(b) 272

102 (37.5%) flex 2.5.31(c) 50 5 (10%) grep 2.5 NA 86 (7.4%*EXEC) grep 2.5.1(a) NA 25 (4.9%*EXEC) grep 2.5.1(b) NA 599 (53.3%*EXEC) grep 2.5.1(c) NA 12 (0.9%*EXEC) make 3.80(a) 981

739 (81.4%) make 3.80(b) 1290 1051 (75.3%) Average=36.0% * (BS) gzip-1.2.4 34 3 (8.8%) ncompress-4.2.4 18 2 (14.3%) polymorph-0.4.0 21 3 (14.3%) tar 1.13.25 105 45 (42.9%) bc 1.06

204 102 (50%) tidy 554 161 (29.1%) CS590F Software Reliability Positive Evidence Correct outputs produced in addition to wrong output. BS(Owrong) BS (Ocorrect) is problematic. 10. A = 1 (Correct: A=3) ... 20. B = A % 2 30. C = A + 2 40. Print (B) BS([email protected])= {10, 30, 41} BS([email protected])= {10, 20, 40} BS([email protected])-BS([email protected]) = {30,41} 41. Print (C)

CS590F Software Reliability Confidence Analysis [PLDI06] n ??? Assign a confidence value to each node, C(n) = 1 means n must contain the correct value, C(n) = 0 means there is no evidence of n having the correct value. Given a threshold t, BS should only contain the nodes C(n) < t . If a node n can only reach the correct output, C(n) = 1. If a node n can only reach the wrong output, C(n) = 0. If a node n can reach both the correct output and the wrong output, the CONFIDENCE of the node n is defined as: C (n) 1 log |range ( n )| | Alt (n) | Alt(n) is a set of possible LHS values at n, assigning any of which to n does not change any same correct output. |Alt(n)| >=1; C(n)=1 when |Alt(n)| =1. CS590F Software Reliability Confidence Analysis: Example

If a node n can only reach only the correct output, C(n) = 1. If a node n can only reach the wrong output, C(n) = 0. If a node n can reach both the correct output and the wrong output, the CONFIDENCE of the node n is defined as: C (n) 1 log |range ( n )| | Alt (n) | Alt(n) is a set of possible LHS values at n, assigning any of which to n produces the same correct output. 10. A = 1 (Correct: A=3) C (10) 1 log|range ( A)| ... 20. B = A % 2 | range( A) | log|range ( A)| 2 2 C (20) 1 30. C = A + 2 C (30) 0 40. Print (B)

C (40) 1 41. Print (C) C (41) 0 CS590F Software Reliability Computing Alt(n) C(S1)=1-log|alt(S1)|=1 (T,...)= (1,...) (3,...) (5,...) (8,...) (9,...) alt(S1) =alt([email protected]) ^ alt ([email protected]) = {9} S1: T=... alt([email protected])={9} S2: X=T+1 10 9 alt([email protected])={1,3,9} S3: Y=T%3 0 alt(S2)={10}

alt(S3)={0,1} C(S2)=1-log|alt(S2)|=1 C(S3)=...=1-log32 (X,T)= (6,5) (9,8) (10,9) (Y,T)=( 0,3) (0,9) (1,1) (2,5) (2,8) CS590F Software Reliability Evaluation on injected bugs We pruned the slices by removing all the statements with C(n)=1 Program BS Pruned Slice Pruned Slice / BS print_tokens

110 35 31.8% print_tokens2 114 55 48.2% replace 131 60 45.8% schedule 117 70 59.8% schedule2 90

58 64.4% gzip 357 121 33.9% flex 727 27 3.7% Average=41.1% CS590F Software Reliability Effectiveness Analyze Runtime BS=30.9% *EXEC Behavior

BS^FS^BiS = 36% * BS For many memory type bugs, slices can be reduced to just a few statements. Pruned Slice = 41.1% * BS For some benchmarks, the pruned slices contain only the dependence paths leading from the root cause to the wrong output. CS590F Software Reliability Comments False positive FS > PS / Chop > DS False negative DS > FS=PS=Chop Cost

PS/Chop > FS > DS CS590F Software Reliability Challenges Execution omission errors Input x=-1 y=10 if (x>0) /*error, should be x<0*/ y=y+1 print(y) For long running programs, multithreading programs Making slices smaller More evidence? CS590F Software Reliability Next Background (done)

Ideas, papers (start from next lecture) Will try to schedule a lecture on static tools. Probably in late March. CS590F Software Reliability