Report

Data Flow Coverage Criteria All-Defs Coverage (ADC): For each def-path set S = du(n, v), TR contains at least one path d in S. All-Uses Coverage (AUC): For each def-pair set S = du(ni , nj , v), TR contains at least one path d in S. All-du-Paths Coverage (ADUPC): For each def-pair set S = du(ni , nj, v), TR contains every path d in S. 1 Data Flow Coverage Criteria All-Defs Coverage requires that each def reaches at least one use, All-Uses Coverage requires that each def reaches all possible uses All-du-Paths Coverage requires that each def reaches all possible uses through all possible du-paths. The formal definitions of the criteria are simply appropriate selections from the appropriate set. 2 Differences Among the three Data Flow Coverage Criteria The graph has one def, so only one path is needed to satisfy all-defs. The def has two uses, so two paths are needed to satisfy all-uses. Since two paths go from the def to each use, four paths are needed to satisfy all-du-paths. 3 Annotated Control Graph Nodes 4 and 6 are final nodes, corresponding to the return statements. Node 2 is introduced to capture the for loop; it has no executable use(3)= statements. DU (def-use) pairs are shown as a variable name followed by the def node, then the use node. def (5) = { i } use (5) = { i } Def -Use Pairs = { (1, 1,x), (1,3,x), (1,3,y), (1, 2,i), (1, 3,i), (1,5,i), (1,6,i), (5, 2,i), (5, 3,i), ( 5, 6,i), (5, 5,i)} example of a graph annotated with defs and uses 5 public static void computeStats (int [ ] numbers) { int length = numbers.length; double med, var, sd, mean, sum, varsum; sum = 0; for (int i = 0; i < length; i++) { sum += numbers [ i ]; } med = numbers [ length / 2]; mean = sum / (double) length; 1 2 i=0 3 varsum = 0; for (int i = 0; i < length; i++) 4 { 5 varsum = varsum + ((numbers [ I ] - mean) * (numbers [ I ] - mean)); i=0 } var = varsum / ( length - 1.0 ); sd = Math.sqrt ( var ); 6 System.out.println ("length: " + length); i < length System.out.println ("mean: " + mean); i >= length System.out.println ("median: " + med); 7 System.out.println ("variance: " + var); 8 System.out.println ("standard deviation: " + sd); } i++ 6 CFG for ComputeStats – With Defs & Uses 1 def (1) = { numbers, sum, length } 2 def (2) = { i } 3 use (3, 5) = { i, length } use (3, 4) = { i, length } 4 def (4) = { sum, i } use (4) = { sum, numbers, i } 5 6 def (5) = { med, mean, varsum, i } use (5) = { numbers, length, sum } use (6, 8) = { i, length } use (6, 7) = { i, length } 7 def (7) = { varsum, i } use (7) = { varsum, numbers, i, mean } 8 def (8) = { var, sd } use (8) = { varsum, length, mean, med, var, sd } 7 Defs and Uses Tables for ComputeStat Node 1 2 3 4 5 Def Use { numbers, sum, length } {i} { numbers } { sum, i } { med, mean, varsum, i } { numbers, i, sum } { numbers, length, sum } 8 { varsum, i } { var, sd } Use (1, 2) (2, 3) (3, 4) (4, 3) { i, length } (3, 5) { i, length } (5, 6) 6 7 Edge { varsum, numbers, i, mean } { varsum, length, var, mean, med, var, sd } (6, 7) { i, length } (7, 6) (6, 8) { i, length } 8 DU Pairs for ComputeStat variable DU Pairs Defs come before uses, do not count as DU pairs numbers (1, 4) (1, 5) (1, 7) length (1, 5) (1, 8) (1, (3,4)) (1, (3,5)) (1, (6,7)) (1, (6,8)) med var sd mean sum varsum i (5, 8) defs after use in loop, these (8, 8) are valid DU pairs (8, 8) (5, 7) (5, 8) No def-clear path … (1, 4) (1, 5) (4, 4) (4, 5) different scope for i (5, 7) (5, 8) (7, 7) (7, 8) (2, 4) (2, (3,4)) (2, (3,5)) (2, 7) (2, (6,7)) (2, (6,8)) (4, 4) (4, (3,4)) (4, (3,5)) (4, 7) (4, (6,7)) (4, (6,8)) (5, 7) (5, (6,7)) (5, (6,8)) No path through graph from (7, 7) (7, (6,7)) (7, (6,8)) nodes 5 and 7 to 4 or 3 9 DU Paths for Stats variable numbers length med var sd sum DU Pairs DU Paths (1, 4) (1, 5) (1, 7) [ 1, 2, 3, 4 ] [ 1, 2, 3, 5 ] [ 1, 2, 3, 5, 6, 7 ] (1, 5) (1, 8) (1, (3,4)) (1, (3,5)) (1, (6,7)) (1, (6,8)) [ 1, 2, 3, 5 ] [ 1, 2, 3, 5, 6, 8 ] [ 1, 2, 3, 4 ] [ 1, 2, 3, 5 ] [ 1, 2, 3, 5, 6, 7 ] [ 1, 2, 3, 5, 6, 8 ] (5, 8) (8, 8) (8, 8) (1, 4) (1, 5) (4, 4) (4, 5) [ 5, 6, 8 ] No path needed No path needed [ 1, 2, 3, 4 ] [ 1, 2, 3, 5 ] [ 4, 3, 4 ] [ 4, 3, 5 ] variable mean DU Pairs (5, 7) (5, 8) DU Paths [ 5, 6, 7 ] [ 5, 6, 8 ] varsum (5, 7) (5, 8) (7, 7) (7, 8) [ 5, 6, 7 ] [ 5, 6, 8 ] [ 7, 6, 7 ] [ 7, 6, 8 ] i (2, 4) (2, (3,4)) (2, (3,5)) (4, 4) (4, (3,4)) (4, (3,5)) (5, 7) (5, (6,7)) (5, (6,8)) (7, 7) (7, (6,7)) (7, (6,8)) [ 2, 3, 4 ] [ 2, 3, 4 ] [ 2, 3, 5 ] [ 4, 3, 4 ] [ 4, 3, 4 ] [ 4, 3, 5 ] [ 5, 6, 7 ] [ 5, 6, 7 ] [ 5, 6, 8 ] [ 7, 6, 7 ] [ 7, 6, 7 ] [ 7, 6, 8 ] 10