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:

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).

Representation challenges

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.

class Listing4  {      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);          assertEquals(0, result);      }  }

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)      {          return 0;      }  }

Listing 5: An oversimplified implementation that would still pass the test

***

Image credit: brightsea