Graph Coverage for Source Code
This chapter discusses the application of graph criteria in testing software source code, focusing on control flow graphs, node coverage, edge coverage, loops, and data flow coverage. It explains how to model control structures, translate statements into graphs, and handle scenarios such as if statements, loops, and switch structures.
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
Introduction to Software Testing Chapter 2.3 Graph Coverage for Source Code Paul Ammann & Jeff Offutt
Overview The most common application of graph criteria is to program source Graph : Usually the control flow graph (CFG) Node coverage : Execute every statement Edge coverage : Execute every branch Loops : Looping structures such as for loops, while loops, etc. Data flow coverage : Augment the CFG defs are statements that assign values to variables uses are statements that use variables 2
Control Flow Graphs A CFG models all executions of a method by describing control structures Nodes : Statements or sequences of statements (basic blocks) Edges : Transfers of control Basic Block : A sequence of statements such that if the first statement is executed, all statements will be (no branches) CFGs are sometimes annotated with extra information branch predicates defs uses Rules for translating statements into graphs 3
CFG : The if Statement if (x < y) { y = 0; x = x + 1; } else { x = y; } 1 x < y x >= y y = 0 x = x + 1 2 3 x = y 4 1 if (x < y) { y = 0; x = x + 1; } x < y y = 0 x = x + 1 x >= y 2 3 4
CFG : The if-Return Statement if (x < y) { return; } print (x); return; 1 x < y x >= y return 2 print (x) return 3 No edge from node 2 to 3. The return nodes must be distinct. 5
Loops Loops require extra nodes to be added Nodes that do not represent statements or basic blocks 6
CFG : while and for Loops 1 x = 0 x = 0; while (x < y) { y = f (x, y); x = x + 1; } dummy node 2 implicitly initializes loop x < y x >= y 1 x = 0 3 4 y =f(x,y) x = x + 1 2 x < y x >= y for (x = 0; x < y; x++) { y = f (x, y); } 3 5 y = f (x, y) 4 x = x + 1 implicitly increments loop 7
CFG : The case (switch) Structure read ( c) ; switch ( c ) { case N : y = 25; break; case Y : y = 50; break; default: y = 0; break; } print (y); read ( c ); 1 c == N c == Y default 2 3 4 y = 25; break; y = 0; break; y = 50; break; 5 print (y); 8
Example Control Flow Stats 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; varsum = 0; for (int i = 0; i < length; i++) { varsum = varsum + ((numbers [ I ] - mean) * (numbers [ I ] - mean)); } var = varsum / ( length - 1.0 ); sd = Math.sqrt ( var ); System.out.println ("length: " + length); System.out.println ("mean: " + mean); System.out.println ("median: " + med); System.out.println ("variance: " + var); System.out.println ("standard deviation: " + sd); } 9
Control Flow Graph for Stats public static void computeStats (int [ ] numbers) { int length = numbers.length; double med, var, sd, mean, sum, varsum; 1 sum = 0; for (int i = 0; i < length; i++) { sum += numbers [ i ]; } med = numbers [ length / 2 ]; mean = sum / (double) length; i = 0 2 i >= length 3 i < length varsum = 0; for (int i = 0; i < length; i++) { varsum = varsum + ((numbers [ I ] - mean) * (numbers [ I ] - mean)); } var = varsum / ( length - 1.0 ); sd = Math.sqrt ( var ); 4 i++ 5 i = 0 6 System.out.println ("length: " + length); System.out.println ("mean: " + mean); System.out.println ("median: " + med); System.out.println ("variance: " + var); System.out.println ("standard deviation: " + sd); } i < length i >= length 7 8 i++ 10
Control Flow Graph for Stats ( numbers ) sum = 0 length = numbers.length 1 i = 0 2 3 i >= length i < length mean = sum / (double) length; med = numbers [ length / 2 ] varsum = 0 i = 0 4 5 sum += numbers [ i ] i++ 6 i >= length i < length var = varsum / ( length - 1.0 ) sd = Math.sqrt ( var ) print (length, mean, med, var, sd) 8 7 varsum = i++ 11
Control Flow TRs and Test Paths EC 1 Edge Coverage 2 TR Test Path A. [ 1, 2 ] B. [ 2, 3 ] C. [ 3, 4 ] D. [ 3, 5 ] E. [ 4, 3 ] F. [ 5, 6 ] G. [ 6, 7 ] H. [ 6, 8 ] I. [ 7, 6 ] [ 1, 2, 3, 4, 3, 5, 6, 7, 6, 8 ] 3 4 5 6 7 8 12
Control Flow TRs and Test Paths EPC 1 Edge-Pair Coverage TR Test Paths A. [ 1, 2, 3 ] B. [ 2, 3, 4 ] C. [ 2, 3, 5 ] D. [ 3, 4, 3 ] E. [ 3, 5, 6 ] F. [ 4, 3, 5 ] G. [ 5, 6, 7 ] H. [ 5, 6, 8 ] I. [ 6, 7, 6 ] J. [ 7, 6, 8 ] K. [ 4, 3, 4 ] L. [ 7, 6, 7 ] i. [ 1, 2, 3, 4, 3, 5, 6, 7, 6, 8 ] ii. [ 1, 2, 3, 5, 6, 8 ] iii. [ 1, 2, 3, 4, 3, 4, 3, 5, 6, 7, 6, 7, 6, 8 ] 2 3 4 sidetrips TP TRs toured 5 i A, B, D, E, F, G, I, J A, C, E, H C, H ii C, H iii A, B, D, E, F, G, I, J, K, L 6 7 8 13
Control Flow TRs and Test Paths PPC Prime Path Coverage 1 TR Test Paths A. [ 3, 4, 3 ] B. [ 4, 3, 4 ] C. [ 7, 6, 7 ] D. [ 7, 6, 8 ] E. [ 6, 7, 6 ] F. [ 1, 2, 3, 4 ] G. [ 4, 3, 5, 6, 7 ] H. [ 4, 3, 5, 6, 8 ] I. [ 1, 2, 3, 5, 6, 7 ] J. [ 1, 2, 3, 5, 6, 8 ] i. [ 1, 2, 3, 4, 3, 5, 6, 7, 6, 8 ] ii. [ 1, 2, 3, 4, 3, 4, 3, 5, 6, 7, 6, 7, 6, 8 ] iii. [ 1, 2, 3, 4, 3, 5, 6, 8 ] iv. [ 1, 2, 3, 5, 6, 7, 6, 8 ] v. [ 1, 2, 3, 5, 6, 8 ] 2 Infeasible test path Infeasible test path 3 4 5 TP TRs toured sidetrips i A, D, E, F, G A, B, C, D, E, F, G, H, I, J H, I, J ii 6 J iii A, F, H J iv D, E, F, I 7 8 v J 14
Test Cases and Test Paths Test Case : numbers = [2, 10, 15] ; length = 3 Test Path : [ 1, 2, 3, 4, 3, 4, 3, 4, 3, 5, 6, 7, 6, 7, 6, 7, 6, 8 ] - 100% node and edge coverage achieved - More than one loop iteration Test Case : numbers = [44] ; length = 1 Test Path : [ 1, 2, 3, 4, 3, 5, 6, 7, 6, 8 ] - 100% node and edge coverage achieved - Exactly one loop iteration Test Case : numbers = [] ; length = 0 Test Path : [ 1, 2, 3, 5, 6, 8 ] But the method fails with divide by zero on the statement mean = sum / (double) length; - 75% (=6/8) node and 41.7 % = (5/12) edge coverage achieved - 0 loop iteration A bug found 15
