The Problem with Path Code Coverage
Why do so few available tools support path coverage?
High number of paths
The number of possible code paths typically increases exponentially with the cyclomatic complexity of a method. Achieving a high percentage of path coverage by manually writing test cases is effectively impossible for any method that contains more than just a handful of lines. Even automated test generation tools may have a difficult time generating test cases for complete path coverage, especially when nested loops are involved. For example, a method with a sequence of 10 non-nested if statements already has 1024 (or 210) possible paths. The code path for a loop that terminates after 499 iterations is different from the code path of the same loop terminating after 500 iterations. Similarly, an array store operation throwing an exception because of a null reference and that same operation throwing an ArrayStoreException need to be treated as different code paths.
Types of Code Coverage
Path coverage is one of many types of code coverage metrics. To review, here are the types of coverage support by Parasoft test tools:
|Basic Block||A sequence of non-branching statements; a linear sequence of code with no control flow route branchings.|
In C++, a boolean expression is simply an expression that has a 'bool' type.
In C, C++test treats the following as boolean expressions:
An atomic boolean non-constant expression that is a part of the MC/DC decision.
A sub-expression of the MC/DC decision is considered to be a condition if it does not contain boolean operators (&&, ||, !).
If a given atomic expression appears more than once in a decision, each occurrence is a distinct condition.
|Decision/Branch||Decision/Branch is the possible control flow decision to be taken at the branching point in the code. C++test considers if-else, for, while, do-while, and switch instructions as the branching points. C++test does not take into account such dynamic branching points as exception handlers (throw-catch statements).|
|MC/DC Decision||A top-level boolean expression composed of conditions and zero or more boolean operators. C++test computes MC/DC and SCC on all boolean non-constant expressions in the source code except constructor initializers and function default arguments.|
|Path||A unique sequence of basic blocks starting from the function entry to the point of exit.|
Difficulty identifying and covering paths
Automated test generation tools for path coverage first need to determine which code paths are possible and which ones are not, and then need to be able to generate test inputs that cover all possible paths. Both steps are very time-intensive, and the accuracy of the results cannot really be guaranteed because the required analysis involves problems that are known to be NP-hard or even undecidable (like the infamous halting problem).
Unlike statement and branch coverage, path coverage is difficult to visualize. Marking lines or expressions with different colors is not enough to convey this type of coverage information. Due to this lack of an easily understandable visualization, path coverage remains a difficult concept for many developers.
The practical approaches for achieving path coverage are similar for automated and manual test generation. Instead of trying to find all possible code paths, it is helpful to focus on “interesting” code paths. It makes little sense to write a test case that would execute a loop 499 times and then add another test case that executes the loop 500 times if nothing really different happens.
Rather than using a top-down approach, it is often more useful to use a bottom-up approach that starts at possible points of failure and then finds code paths that would lead to the failures. The potential troublemakers include not only possible null references (NullPointerException), type incompatibilities (ClassCastException, ArrayStoreException), array boundary violations (ArrayIndexOutOfBoundsException), but also divisions by zero (ArithmeticException) or potential synchronization issues (IllegalMonitorStateException). The tricky part is that these exceptions occur as a side effect of low-level bytecode instructions and are not declared anywhere. Testing tools that are capable of performing a flow analysis of the tested code can be very helpful in identifying code paths that need further testing.
public static int add(int a, int b)
return a + b;
public class Listing4Test extends junit.framework.TestCase
public void testAdd0()
int result = Listing4.add(0, 0);
Listing 4: A method that has only one code path and its corresponding JUnit test
class Listing4 // Listing 5, actually
public static int add(int a, int b)
Listing 5: An oversimplified implementation that would still pass the test
Image credit: brightsea
Parasoft’s industry-leading automated software testing tools support the entire software development process, from when the developer writes the first line of code all the way through unit and functional testing, to performance and security testing, leveraging simulated test environments along the way.