Code Coverage – Part IV: Honest Coverage

This post is part of a four-part series on code coverage:

• Part I: An Introduction
• Part II: A short example
• Part III: Statement coverage and some myths
• Part IV: Honest Coverage

---

We saw in the last post that statement coverage isn’t enough. While it gives us some signal if a service is insufficiently tested, it doesn’t necessarily give us a good gauge of how much of the code logic is actually being tested.

What kinds of code coverage should I actually care about?

Let’s compare it to Branch Coverage.

Given a piece of software, we can model all possible paths that the system can operate using a control-flow graph. Instead of asking how many lines of code are executed during testing, edge coverage asks how many edges have been traversed in the control-flow graph during testing.

Statement coverage asks, “Has each statement in the program been executed?” Edge coverage asks, “Has every edge in the control-flow graph been executed?”

Edge coverage is the proportion of edges in the control-flow graph of the code that has been executed.

Let’s visit a few examples:

Given two boolean functions f() and g(), say we have the following two blocks of code:

if f() && g() {
    // some code...
}

if f() || g() {
    // some code...
}

Some questions:

1. How many test cases are needed to yield full statement/edge coverage for Code Block I?
2. How many test cases are needed to yield full statement/edge coverage for Code Block II? </aside>

For both code blocks, only a single test case is required to yield 100% statement coverage – just rig one that cause both f() and g() to return true. Just one test case! However, your speedy intuition may tell you this isn’t enough. 

Indeed, if we draw out the control flow graph for each of the code blocks, they will look something like this:

In order to get 100% edge coverage, each code block needs at least 3 test cases (try it yourself!)

Of course, this is just a small example. The more complex the code you are testing, the more paths and edges there will be through the code. Every edge represents a possible point of weakness in the system, and the more complex the code, the harder it will be to debug or patch up vulnerabilities. The more complex the code is, the more test cases will be required to test a system. The more complex the code is, the less we can rely on statement coverage to give us an accurate picture of how much our automated tests are actually testing the system logic.

Can I obtain full edge coverage?

High edge coverage is especially important when testing crucial systems with high security risk. However, more tests doesn’t necessarily mean more coverage. Understanding the program’s control flow is key to improving edge coverage.

Analysing our code and drawing out its control flow graph is one strategy to designing a test plan that will cover all paths in the logic. Once it’s drawn out, we can actually calculate the number of test cases we need for full edge coverage. This metric is called Cyclomatic Complexity (see here and here for more information).

Cyclomatic complexity is a measure of the logical complexity of a module and the minimum effort necessary to qualify a module.  It is the number of linearly independent paths and, consequently, the minimum number of paths that one should (theoretically) test.

Here’s some great advice from the guy who coined the term:

Get to know your code. Get to know how the pieces work and how they talk to each other. The more broad a view you have of the system being programmed, the more likely you will catch those pieces of the puzzle that don’t quite fit together, or spot the place a method on some object is being called for some purpose it might not be fully suited.

Tom McCabe, Department of Homeland Security Software Assurance Working Group (2008)

And that’s it for this series! See you in the next one 🙂