Control Flow Testing

Control Flow Testing

In White box testing we test the code of the application. We can understand the code testing with time and space analogy. The time and space analogy is a universal use case to understand and solve most of the mathematical problems. There is no change in the universe until the time or space does not change. The time and space are two factors that bring any change. While testing a code, we can take the code as a small universe. The flow of control in the code is a factor of time and the memory storage of the variables is the actually space of the code. In this section, we are going to test the code with flow of control.

You can take the code of any application like different paths of a city. When you want to do a task in the application, you start your journey from some point in the code and end your journey on some other point. There are as many paths in the code as many tasks the software can do.

Note: the control flow testing makes sure that the tester tests every possible path of flow through the code.

The first step in control flow testing is drawing the control flow graph. Let us see how to draw a control flow graph.

Control flow graph

In control flow graph, we represent the code statements or process blocks by circles or nodes and the flow of control by the arrows or edges. It has following components.

Process block

Process block may be a single statement or a group of statement. We draw circle to represent the process block.

 

Decision point

The decision point represents where the flow can take more than one paths. As I already stated, you can conceive the flow testing as different paths in the code. The decision point is equivalent to the turns in the path. The decision point may refer to different programming features.

If-Else: Decision point

In If-Else decision point, the control flow has just two paths, the true one and the false one.

Switch-case: decision point

In switch-case decision point, the number of paths depend upon the number of cases we use inside the switch statement.

Loop: decision point

The programming loops are binary true false conditions, so they are equivalent to if-else decision points in the sense that they have two paths, one for true condition and the other for false condition.

Junction Point

The junction point is where more than one path merge into single path. In programming, the junction points are at the lines where the flow converges from some type of decision point i.e. if-else, switch-case or looping condition.

Control flow graph example

Type code here like

C:\Users\rehan.abbas\Downloads\Untitled Diagram.jpg

In the diagram, the nodes 4 and 7 are decision points and the node 7 is a junction point.

Statement Coverage.

In statement coverage, our goal is to cover all the statements of the code. In the control flow graph, the circles or the nodes refer to the code statements. So while traversing the graph, if we cover all the nodes, we will be covering all the statements.

Statement coverage example 1.

 

In this diagram, for statement coverage, we have to cover all the nodes. We will find the minimum possible attempts that can cover all the nodes. Those attempts will correspond to the number of test cases. For this diagram, we can cover all the nodes in only one attempt that is.

P1 = 1,2,3,4,5,6,7

The test case for above path would be as under

id input expected output actual output status
1 x=10, y =10 Hello from line 3, Hello from line 6

Statement coverage example 2.

Now see the following diagram.

 

In how many attempts, we can traverse all the nodes. Definitely, we cannot do it in one attempts. We need at least two attempts to cover all the nodes.

Path 1 = E, H, K, N, Q                      //setting both conditions true

Path 2 = E, G, K, M, Q                  //setting both conditions false

Note, these are not the only paths for statement coverage. We can traverse the graph in any order. Our purpose is to cover all the nodes.

test cases:

id input expected output actual output status
1 x=10, y =10 Hello from line 2, Hello from line 6
2 x=0, y =0  Hello from line 4, Hello from line 8

Practice

Now guess in how many test cases are required for the statement coverage of the following code snippet.

// give link to the answer as well.

Branch coverage.

In statement coverage, we write test cases to cover every statement. Apparently, it seems quite enough to find out all the bugs in the code. But it is not. If we test the below code using statement coverage, we will be missing the bug. It will show zero fines if the late days are more than maximum limit. In such case, we need to make the condition false.

 

Branch coverage is also called decision coverage. For branch or decision coverage, we traverse the control flow graph to cover all the edges or branches.

Branch Coverage Example 1

 

In this diagram, we can cover all the nodes in one attempt but to cover all the edges (lines) we need at least two attempts. Therefore, there are two paths

Path 1 = 1,2,3,4,5,6,7

Path 2 = 1, 2, 4, 5, 7

id input expected output actual output status
1 x=10, y =10 Hello from line 3, Hello from line 6
2 x=0, y =0

Branch Coverage Example 2

 

In this diagram, again we need at least two attempts to cover all the edges.

Path 1 = E, G, K, M, Q

Path 2 = E, H, K, N, Q

Note, these are not the only paths for branch coverage. We can traverse the graph in any order. Our purpose is to cover all the edges.

 

id input expected output actual output status
1 x=10, y =10 Hello from line 2, Hello from line 6
2 x=0, y =0  Hello from line 4, Hello from line 8

Practice:

Now guess, how many test cases are required the following code snippet.

Condition coverage.

In branch or decision coverage, we focus on the decision points and try to cover all the branches or decisions on those decision points. But the decision point may also include sub-conditions. For instance see the code.

The code has two decision points. However, every decision point is made up of two sub-conditions. There may be even more sub-conditions for every decision point.

In condition coverage, our concern is to test every sub-conditions. These sub-conditions follow the predicate logic, so we make the true and false.

For above code snippet, we can do the condition coverage in different way.

Option 1:

  1. Make all the sub-conditions true i.e. (a>0), (c==1), (b==3), (d<0) in first test case.
  2. Make all the sub-conditions false i.e. (a>0), (c==1), (b==3), (d<0) in second test case.

Option 2:

  1. Make (a>0), (b==3) true and (c==1), (d<0) false in first test case.
  2. Make (a>0), (b==3) false and (c==1), (d<0) true in second test case.

Option 2:

  1. Make (a>0), (b==3) false and (c==1), (d<0) true in first test case.
  2. Make (a>0), (b==3) true and (c==1), (d<0) false in second test case.

In short, you can choose any pattern; the goal is to cover every sub-condition with true and false scenario.

Condition-Decision Coverage.

If you observe the option 1 of condition coverage, you will see it is automatically doing branch or decision coverage. Nevertheless, in option 2 and 3, we are doing condition coverage but branch or decision coverage is missing. The reason is, in option 2 and 3, the first decision point is always false and the second decision point is always true. As, you know the && operator demands that both the sub-conditions should be true and the || operator demands that it would be true if either of the two or both conditions are true.

Hence, in Option 1 and 2 of condition coverage, we are doing condition coverage but not branch or decision coverage. Whereas in Option 1, we are not only doing condition coverage but as well as branch coverage.

The conditions coverage that also includes the branch or decision coverage is called condition – decision coverage.

In other words, to meet the criteria of condition-decision coverage, we need to choose the test cases wisely so that they also implicitly include the branch coverage.

Multiple condition coverage.

Multiple condition coverage is a nice and systematic way to cover all branches as well as sub-conditions. For multiple condition coverage, we draw the control flow graph in such a way that it treats the sub-conditions as  separate decision points. In fact, every sub-condition in any decision point is definitely a decision point. Let us once again study the same example.

Here, we would treat (a>0), (c==1), (b ==3 ) and (d<0) as separate decision points and draw the control flow graph accordingly that is.

After drawing the control flow graph, we write test cases to traverse the graph so that every branch or decision is covered. For above, let us calculate how many test cases would be enough to cover all the branches.

Path 1: 1,2,3,4,5,6,end

Path 2: 1,2,4,6,end

Path3: 1, 4, 5, end.

Hence, in three attempts or test cases we can cover all the branches of the control flow graph made by multiple condition coverage.

 

Path coverage.

Path coverage is the next step to the branch coverage. Here, we not only make sure to cover all the edges but also try to cover all the possible options of going from starting point to the end. In following diagram of a simple control flow graph, we can cover all the branches or edges in two steps.

But there are four different options to move from E to Q. Those options are

  1. EHKNQ
  2. EGKMQ
  3. EHKMQ
  4. EGKNQ

Covering all these options is called path coverage. The path coverage is applicable to the codes where cyclomatic complexity is not that high. As the count of decision points increases, the paths become too many to cover.

For instance, for two if-else type decision points there are four paths

3 if-else = 8 paths

4 if-else = 16

5 if-else = 32

30 if-else = over one billion

It means, the path coverage becomes nearly impossible task as the count of if-else increases. To deal such situation, we have the idea of basis path or structured path testing. The basis paths or the structured paths depend upon the cyclomatic complexity of the code.

Cyclomatic Complexity.

The cyclomatic complexity of the code depends upon the count of decision points. You can calculate it in different ways, but the idea is the same. The general formulae to calculate the cyclomatic complexity from the control flow graph is:

Cyclomatic Complexity = E – N + 2

Where

E = Count of Edges

N = Count of Nodes.

For instance, look at the following control flow graph.

It has eight edges and seven nodes. So

CC = 8 – 7 + 2 = 3

Another simpler way is counting the predicate nodes and adding 1 to it. The predicate node here means the decision point with true and false paths i.e. two options only. Simply putting, the predicate node is actually the “if statement”. We count the number of If statements in our code and add 1 to it to get the cyclomatic complexity. In above control flow graph, we have two predicate nodes so

CC = Predicate nodes + 1

CC = 2 + 1

But what about switch case and other type of decision points? In such cases, we can translate such decision points to equivalent if-else statements and then can calculate the cyclomatic complexity.

There is also another generic technique to compute the cyclomatic complexity from control flow graph. In this technique, we start with the fact that for any code the minimum cyclomatic complexity is one. Therefore, we assume a default path from start to the end. Then, at every decision point, we count the extra options or paths that are available in addition to the default path. Let us understand the concept with the help of the same control flow graph.

Here we assume that there is a default path from start to the end. So, we start with 1, the minimum cyclomatic complexity of any program.

You can choose any default path from start to the end. Next, at each decision point, we count extra options and add to the cyclomatic complexity.

Initial cyclomatic complexity with a default path = 1

There are two decision points E and K.

There is an extra path at E.

Cyclomatic complexity = Cyclomatic complexity + count of extra options at E.

Cyclomatic complexity = 1 + 1.

Similarly, there is an extra path at decision point at K.

Cyclomatic complexity = Cyclomatic complexity + count of extra options at E.

Cyclomatic complexity = 2 + 1. = 3.

Another Example:

Let us find the cyclomatic complexity from the following control flow graph.

We know that the minimum cyclomatic where there is no decision point in the graph is always  1 (one) . So, we start with that minimum cyclomactic complexity for an assumed path through the graph.

Cyclomatic Complexity = 1 // the initial cyclomatic complexity for an assumed path.

Now, we need to find out the decision point and have to count how many extra paths we are getting from every decision point.

The first decision point at node A is a binary one that has two paths. One path would be part of the assumed default path, so it offers one extra paths. We add up it to the cyclomatic complexity.

Cyclomatic Complexity = Cyclomatic Complexity + 1 = 1 + 1 = 2

The next decision point at node D also offers two paths. One path would be part of the assumed default path, so here again we get one extra path.

Cyclomatic Complexity = Cyclomatic Complexity + 1 = 2 + 1 = 3

The next decision point at node F has four paths in total. One of these four paths may be considered as part of the initially assumed default path. Therefore, we are left with three extra paths.

Cyclomatic Complexity = Cyclomatic Complexity + 3 = 3 + 3 = 6

Another decision point is at node H. It is also a binary decision point.

Cyclomatic Complexity = Cyclomatic Complexity + 1 = 6 + 1 = 7

The last predicate node or the binary decision point is at node M.

Cyclomatic Complexity = Cyclomatic Complexity + 1 = 7 + 1 = 8

Therefore, the final cyclomatic complexity computed from this control flow graph is 8.

Basis Path Testing or Structured Testing.

As we saw earlier, the path testing becomes nearly impossible as the count of decision points keeps on increasing. If there are thirty predicate nodes, there would be more than a billion possible paths. In such scenario, the concept of basis path comes to rescue. The set of basis paths include the linearly independent paths. The condition of linearly independent paths is that every new path should introduces at least a new edge that has never been used in other paths. Therefore, the basis paths are equal to the cyclomatic complexity of the code.

How to compute the basis paths

We know the count of basis paths is equal to the cyclomatic complexity of the code and in every new path, we should introduce at least a new edge of branch of the control flow graph.

Method 1:

  1. Draw the first path in the control flow graph by making all the decision paths as true.
  2. In next attempt, make the first decision point as false and set the rest as true.
  3. In next attempt, make the second decision point as false and set the rest as true.
  4. Similarly keep on doing this process till you set the last decision point as false and set the rest as true.

It is obvious from this method, that the count of basis paths is equal to the cyclomatic complexity. In first attempt, we set all the decision points as true. That is equal to the assumed default path and then we draw as many paths as many if statements in the code.

Method 2:

It is also similar to method 1. Of course, it is little more generic. The decision point does not always means if-statements. So in this method we follow the following steps.

  1. Draw the first path as an arbitrary path. You may set all the decision points true of false. If there is switch statement in the code, there is no concept of true or false then you may choose any path through the control flow graph.
  2. In next attempt, you would flip the path in first decision point and the rest of the path would remain the same.
  3. In next attempt, if there is no new path left in first decision point, you would move to next decision point and flip its path whereas keeping the rest of the path as same.
  4. The process should continue till you reach at the end of the control flow graph and there is no edge that is not covered.

Example 1.

Let us find out the basis paths from this control flow graph.

  1. We choose the first arbitrary path, may it be all true, all false, or whatever you prefer. I choose
    E—G—K—N—Q
  2. In next attempt, we flip the path at first decision point, that is E and keep the rest path the same as E—H—K—N—Q
  3. In next attempt, we flip the path at second decision point K and keep the rest path the same as
    E—G—K—M—Q .

That is it. There is no other decision point left. So we have three basis paths and three was the cyclomatic complexity.

Example 2

Now, let us try the following control flow graph.

It has total six predicate nodes (every node has just true and false options), so the cyclomatic complexity for this graph is : CC = Predicate Nodes + 1 = 6 + 1 = 7

  1. First, we choose an arbitrary path through this graph as in below image.
  2. Next, we flip the path at first decision point and keep the rest as same as in below diagram.
  3. Next, we would flip the path at second decision point that is D. Here when we flip the path, we have to go to a very new branch with nested if-else statements. Here again, we choose an arbitrary path in the new block of nested predicate nodes. This arbitrary path would also be remembered later on.

  1. We continue the process of flipping a new decision point at every new attempt while keeping the rest of the path same.

So, we found out seven paths from the above graph.

From above discussion, we can conclude that basis path coverage and branch coverage are similar in the sense that in both techniques our focus is to cover the branches or edges. The difference is that in branch coverage, our purpose is to cover branches in minimum possible attempts. Whereas in basis path coverage, we take a default path at first and then try to introduce only one new branch or edge in every new path.

Loop coverage

While testing the loop, the test cases may become impractical as the loop iterations increase. For instance, consider the following piece of code

Function fun(int count){

While( count< 1000) {
Print(“Hello wordl”);
count++; }

}

Suppose, this loop iterates 1000 times. It means, we need to write 1000 test cases. Writing 1000 test cases is not an impossible task but it is not sensible to waste so much time and energy for such a trivial piece of code. If you have been writing the code for loops, you must be aware of the fact that the logical errors in loops usually occur at boundaries. Therefore, we would test the loop code mainly for its iterations. The general formula to write the test cases for loops is as under.

  1. Write test case for zero iteration.
  2. Write test case for 1 iteration.
  3. Write test case for n iterations, n may be any number in between the legal range.
  4. Write test case for m-1 iterations where m is the maximum number of iterations for the given application.
  5. Write test case for m iterations.
  6. Write test case for m+1 iterations.

For the above piece of code, we know the maximum legal iterations are 1000. Therefore, we can write the following test cases.

 

Id Input Expected output Actual output Status
1 Count = 2000 Zero iterations – no 0utput
2 Count = 999 Hello World
3 Count = 500 Hello Word 500 times
4 Count = 1 Hello Word 999 times
5 Count = 0 Hello world 1000 times
6 Count = -1 Hello World 10001 Times