Understanding Structural Testing in Software Development

Structural Testing

Structural Testing Also known as White-box testing Test cases derived solely from source code Control Flow Testing To ensure that all statements are covered; no unreachable code To show that all dependencies in program variables are tested To ensure that all paths are satisfactorily tested Data Flow Testing To ensure that data flows in the right path through the code 2

Control Flow Testing Control flow graph of a source code can be used for several purposes To view the entire program and its flow To select and test a portion of a program To simplify the flow using graph theory To justify test coverage using graph theory Identify the execution path(s) using the control flow graph Create and execute test cases to cover the execution paths 3

Control flow graph of a source code Directed graph Each node represents a statement (or a series of statements with no branches see the next slide for details of this type of statements) An edge from a node ni to nj represents that the statement(s) in node ni is(are) executed before the statement(s) in nj Sequential execution of statements Only executable statements in the source code are represented There must be exactly one initial edge where the execution begins Any edge leaving a node but not connected afterwards is considered to be a terminating point of execution for that graph 4

Patterns in control flow graph Statements with no branches (assignment statement, print statement, ) x = y; x = y x = y; z = p+ y; System.out.print( z = + z); x = y x = y z = p + y System.out.print( ) OR z = p + y System.out.print( ) 5

if statements a > b if (a > b) { x = a * a; } y = a + b; F T x = a * a y = a + b a > b if (a > b) { x = a * a; } else { x = b * b; } y = a + b; F T x = a * a x = b * b y = a + b 6

while statement product = 1 i = n product = 1; i = n; while (i > 0) { product = product * i; i = i - 1; } System.out.print (product); i > 0 F T product = product * i i = i - 1 System.out.print ( ) 7

for statement i = 1 for (i = 1; i <= n; i++) { sum = sum + i; System.out.print(i + + sum); } System.out.print ( Sum = + sum); F i <= n T sum = sum + i System.out.print (i + ) i++ System.out.print ( Sum = ) 8

switch statement i = scanner.nextInt() switch(i) 0 i = scanner.nextInt(); switch (i) { case 0: i = 0; break; case 1: i = i * i; break; case 2: i = i + i; j = i * i; break; case 3: b = (i < 0); break; default: System.out.print(i); } if (b) x = - i; default 1 2 3 i = i * i break b = i < 0 break i = 0 break i = i + i j = i * i break System.out.print( ) F b T x = -i 9

Exercise Draw the flow graphs (separately) for the following two code fragments. sum = 0; i = n; do { sum = sum + i; i = i- 1; } while i <= 0; System.out.print (sum); sum = 0; i = n; do { sum = sum + i; i = i 1; } while i > 0; System.out.print (sum); 10

Example Compute binary value public String computeBinary (int n) { // assume n >= 0 && n <= 15 String result = ""; while (n > 0) { result = (n % 2) + result; n = n / 2; } switch (result.length()) { case 3: result = "0" + result; break; case 2: result = "00" + result; break; case 1: result = "000" + result; break; case 0: result = "0000"; break; default: // nothing } // end switch return result; } 11

Node numbers are useful for further analysis and report 1 result = 2 F result.length() 4 n > 0 T default 3 result = (n%2) + result n = n / 2 0 3 2 1 result = 000 + result break 7 result = 0 +result break 5 6 result = 00 +result break result = 0000 break 8 return result 9 Only executable statements are included; informative and declarative statements are ignored 12

Example computing factorial int factorial (int n) { int i, ret = 0; if (n < 0) return ret; i = n; ret = 1; while (i > 0) { ret = ret * i; i = i - 1; } return ret; } 13

Flow graph for the factorial example ret = 0 1 3 T n < 0 return ret 2 F i = n; ret = 1 4 i > 0 5 F T ret = ret * i; i = i - 1 6 7 return ret Only executable statements are included; informative and declarative statements are ignored 14

Exercise Draw the control flow graph for the following code. The code describes a method which is part of a merge sort. The method accepts an integer array, a left pointer, a right pointer and a middle pointer. It is assumed that left <= mid <= right Such constraints will be taken care of by the calling program. The method assumes that the part of the array to the left of mid pointer is sorted and the part of the array on the right of the mid pointer is sorted. This method merges the two sorted subarrays in such a way that the resulting array is also sorted. 15

public void merge(int[] array, int left, int mid, int right) { int i, j, k; int[] temp = new int[array.length]; i = left; j = mid; k = left; while(i <= mid - 1 && j <= right) { if (array[i] <= array [j]) { temp[k] = array[i]; k++; i++; } else { temp[k] = array[j]; k++; j++; } } while(i <= mid - 1) { temp[k] = array[i]; k++; i++; } while(j <= right) { temp[k] = array[j]; k++; j++; } for(i = left; i <= right; i++) array[i] = temp[i]; } 16

Path and subpath A path P in a control flow graph is a sequence of nodes n1, n2, , nk such that there is an edge from ni to nj, 1 i (k-1), 2 j k Generally, a path has a minimum of two nodes; sometimes it may have one node or even empty (rare) A subpath S of a path P is a subsequence of nodes of P if P is a sequence of n1, n2, , nk then S will contain the sequence of nodes ni, ni+1, , nj where i 1 and j k A path itself can be considered as a subpath 17

Path and subpath (continued) A path/subpath is said to be cyclic if the starting node and ending node are the same A path contains a cycle if it has at least one subpath that is cyclic 18

Independent paths An independent path is one that is not included in any other path An independent path may have a cycle Two independent paths may have some nodes in common There can be one or more independent paths in a control flow graph The union of all nodes in all independent paths cover the entire set of nodes in the flow graph 19

Independent paths for the factorial example Independent paths described using the node numbers in the graph Path 1: 1,2,3 Path 2: 1,2,4,5,7 Path 3: 1,2,4,5,6,5,7 These paths describe three different scenarios of execution 20

Exercise Find the independent paths for the Compute Binary Value problem. Find the independent paths for the merge method given in the previous exercise. 21

Test coverage metrics Goal is to derive sufficient number of test cases to cover one or more of the following: Statement coverage Ensures that every statement is covered Predicate coverage Ensure that every outcome (true and false) of every SIMPLE predicate is covered, then it is an exhaustive coverage of predicates strong coverage E.g., (x < y) is a simple predicate E.g., ((x < y) & (y < z)) is a compound predicate which contains two simple predicates 22

Test coverage metrics (continued) Loop coverage Ensure that every loop is covered for all possible execution scenarios Loop is skipped Loop is iterated through only once Loop is iterated through many times Sometimes, one or more of the above three conditions cannot be met E.g., for (i = 0; i < N; i++) given N > 0 This loop cannot be skipped. 23

Statement coverage for factorial problem Test case # Input (n) Statements covered 1 Any negative value 1,2,3 2 0 1,2,4,5,7 3 Any positive value 1,2,4,5,6,7 24

Predicate coverage for factorial problem Test case # Input (n) Node number Predicate Outcome (True/False) 1 Any negative value (< 0) 2 n < 0 True 2 0 2 n < 0 False 3 Any positive value ( > 0) 5 i > 0 True 4 0 5 i > 0 False 25

Loop coverage for factorial problem There is only one loop (a while loop at node 5) in the code Test case # Input (n) Node number for the condition in the loop Outcome (skipped/executed once/executed many times) skipped 1 Any negative value (< 0) or zero 1 5 2 5 executed once 3 Any positive value ( > 0) 5 Executed more than once 26

Exercise Generate test cases for Compute Binary Value problem to address Statement coverage Predicate coverage (all possible outcomes of all simple predicates) Loop coverage Generate test cases for Merge method to address Statement coverage Predicate coverage (all possible outcomes of all simple predicates) Loop coverage 27

Program calling another program public char reportGrade (int[] marks) { int s,i; char ch; ch = ; if (marks.length == 0) return ch; s = sum (marks) / marks.length; if (s >= 90) ch = 'A'; else if (s < 90 && s >= 75) ch = 'B'; else if (s < 75 && s >= 60) ch = 'C'; else if (s < 60 && s >= 50) ch = 'D'; else ch = 'F'; return ch; } public int sum (int[] marks) { int n, ret; ret = 0; for (n = 0; n < marks.length; n++) ret = ret + marks[n]; return ret; } 28

Options Option 1 All the code can be combined into one single piece of code and then generate test case for the entire code (see the flow graph in the next slide) Option 2 First, each independent piece of code is tested individually. When a program P calls another program Q (assuming that Q is independently tested), the calling statement can be tested only to see whether the parameters are passed correctly. 29

1 ch = ; 3 2 T s1 return ch ret = 0 marks.len == 0 F s6 4 n = 0 s2 s = sum return ret s3 T 5 s >= 90 ch = A F n < marks.len 6 F T T 7 75 <= s < 90 ch = B ret=ret+marks[n] s4 8 F T 9 60 <= s < 75 ch = C n++ 10 F s5 T 12 11 50 <= s < 60 ch = D F 13 ch = F return ch 14 30