In my previous post, I argued that a system can be declared successfully tested when:
- all the regulations, requirements, specifications, or imposed conditions have been tested
- the product meets all the clearly stated needs of all the stakeholders.
In some applications, especially those critical for safety and security, that’s not enough: it’s necessary to know also how much code has been tested, if there’s unreachable code around, how many conditions have been evaluated, etc. This is known also as code coverage.
A lot of different metrics exists to evaluate the coverage given a set of tests, being branch, condition and modified condition/decision coverage the most used. In these cases, unless otherwise required by the regulations, the termination condition follows the Pareto’s rule: try to reach the 80% of code coverage according to a chosen metric, since the effort needed to cover the remaining 20% is too high to be worth it (and experts tend to discourage setting a high coverage requirement on tests, since they believe that developers will only try to achieve the requested coverage without thinking if they’re really adding value – a.k.a. Assertion Free Testing).
An interesting and rather neglected research on this topic was made by Thomas McCabe, starting back in the ’80s, with his studies on Cyclomatic Complexity: a measure of the number of linearly independent paths through a program’s source code, whose aim is to indicate the complexity of a program in a quantitative way. A rule of thumb says that if a function/method has a Cyclomatic Complexity higher than 15, you should refactor it (or find a valid explanation not to refactor).
The metric that calculates the coverage over all the possible paths in the code is known as Basis Path Testing and has not yet been widely recognized by the industry as others metrics are (statement, branch or MC/DC), probably due to to the fact that the Cyclomatic Complexity grows fast as new decision points are added to the code, and so the number of tests for a full path coverage, even if some tools already provides some automatic test generation features.
I won’t delve into the details of the Graph Theory used to compute the Cyclomatic Complexity (the original paper is available for free online), but only quote two of its properties:
- it is an upper bound of the number of tests necessary to achieve 100% branch coverage.
- it is is a lower bound for the number of possible paths (the Cyclomatic Complexity does not take into account unreachable paths)
This information is invaluable to developers and project managers, allowing them to estimate the effort needed for testing and to schedule the work. Using the words of Jack Ganssle, an internationally-recognized embedded systems engineer:
Cyclomatic Complexity is a metric that gives us a lower bound on the efficacy of the test regime. It says nothing about the maximum number needed, which may be a lot higher for complex conditions. But at least it gives us a bound, a sanity check to insure our tests don’t fall below the minimum needed.