How does branch coverage handle loops?

Question

I know how code coverage works in general, and I know what branch coverage is. But I can not seem to find an explanation for how branch coverage handles loops.

Does it work like path coverage? Where a loop which runs 10 times is a different path from the exact same loop running 11 times. Or would those two cases be the same thing in branch coverage?

Answer 1

Branch coverage and path coverage are distinct concepts.

Branch coverage

To measure branch coverage, we look for all the points where branching can take place. At each branching point, both branches should have been executed at least once. E.g. in this pseudo-code:

A
if B:
  C
else:
  D
E
if F:
  G
I

we have two branch points – the if B and if F conditionals. To get full branch coverage, each of these conditionals should execute the true and false branch, i.e. both B and F would have to each be false and true each. A test plan could be:

Run 1:
  B = false
  F = false
  # executes A B _ D E F _ I
Run 2:
  B = true
  F = true
  # executes A B C _ E F G I

As you can see, full branch coverage implies full statement coverage.

When dealing with loops, it might be helpful to “compile” it to a more low-level representation that only has conditionals and gotos. E.g.:

// C99 code
A;
for (int i = 0; i < length; ++i)
  B;
C;

could be understood as

// Block 1
  A;
  int i = 0;

// Block 2
loop_start:
  if (!(i < length))
    goto loop_end;  // -> Block 4

// Block 3
  B;
  ++i;
  goto loop_start;

// Block 4
loop_end:
  C;

There is only one conditional here, in block 2. So to get full branch coverage, it must once evaluate both false and true. A test plan could be:

Run 1:
  length = 1
  # executes B1 B2 B3 B2 B4

So the loop condition will evaluate to both true and false with this test plan. But clearly, this is not a satisfactory test: what happens when the loop is skipped altogether (e.g. with length = 0)? What happens if the loop body modifies some state, will it still work with hundreds of iterations?

Path coverage

When we group the code into a control flow graph, path coverage measures the fraction of paths taken from all possible paths. Path coverage implies branch coverage. When we look back at the first example, we could get branch coverage with only two test cases. But to get path coverage we will need 4 cases: two for each path through the first conditional, multiplied by two cases for the second conditional:

Run 1:
  B = false
  F = false
  # executes A B _ D E F _ I
Run 2:
  B = false
  F = true
  # executes A B _ D E F G I
Run 3:
  B = true
  F = false
  # executes A B C _ E F _ I
Run 4:
  B = true
  F = true
  # executes A B C _ E F G I

When our control flow graph includes loops, there are in general infinitely many possible paths. In some cases, the number of loop iterations is bounded by a constant and can be tested, but in general this is not the case. Since complete path coverage is useful but not reachable, we tend to use other coverage metrics.

When I write tests, I tend to ignore full path coverage for loops (path coverage for simple conditionals is still very useful). However, multiple paths could be grouped into equivalence classes for testing – running the code with 0, 1, 2, and “many” iterations should be a decent approximation. A possible test plan:

Run 1:
  length = 0
  # executes B1 B2 B5
Run 2:
  length = 1
  # executes B1 B2 B3 B2 B5
Run 3:
  length = 2
  # executes B1 B2 B3 B2 B3 B2 B5
Run 4:
  length = 123
  # executes B1 B2 B3 B2 B3 ... B2 B3 B2 B5

There are also formal code metrics that allow us to quantify loop tests, such as Linear code sequence and jump-coverage. However, I have never used it.

Testing loops via recursion

When loops are expressed as recursion, the loop is not explicit and thus “hidden” from path coverage. Is this a problem? Kind of. The loop is still present in the control flow graph of the program as whole, but not in the CFG of the recursive function.

However, it is far easier to show that the loop is correct when expressed recursively. We can test the base cases, and a non-base case. Since each non-base-case result is constructed from the base cases (which we have already shown to be correct), then the function as whole can be presumed to be correct. This is analogue to the proof by induction technique, except that tests aren't proofs of correctness, but merely examples of correctness.