Basis Path Coverage

A path represents the flow of execution from the start of a method to its exit. A method with N decisions has 2^N possible paths, and if the method contains a loop, it may have an infinite number of paths. Fortunately, you can use a metric called cyclomatic complexity to reduce the number of paths you need to test.

The cyclomatic complexity of a method is one plus the number of unique decisions in the method. Cyclomatic complexity helps you define the number of linearly independent paths, called the basis set, through a method. The definition of linear independence is beyond the scope of this article, but, in summary, the basis set is the smallest set of paths that can be combined to create every other possible path through a method.

Like branch coverage, testing the basis set of paths ensures that you test every decision outcome, but, unlike branch coverage, basis path coverage ensures that you test all decision outcomes independently of one another. In other words, each new basis path “flips” exactly one previously executed decision, leaving all other executed branches unchanged.

This is the crucial factor that makes basis path coverage more robust than branch coverage and allows you to see how changing that one decision affects the method’s behavior.

I’ll use the same example to demonstrate.

Figure: Code sample

To achieve 100 percent basis path coverage, you need to define your basis set. The cyclomatic complexity of this method is four (one plus the number of decisions), so you need to define four linearly independent paths. To do this, you pick an arbitrary first path as a baseline and then flip decisions one at a time until you have your basis set.

Path 1: Any path will do for your baseline, so pick true for the decisions’ outcomes (represented as TTT). This is the first path in your basis set.

Path 2: To find the next basis path, flip the first decision (only) in your baseline, giving you FTT for your desired decision outcomes.

Path 3: You flip the second decision in your baseline path, giving you TFT for your third basis path. In this case, the first baseline decision remains fixed with the true outcome.

Path 4: Finally, you flip the third decision in your baseline path, giving you TTF for your fourth basis path. In this case, the first baseline decision remains fixed with the true outcome.

So, your four basis paths are TTT, FTT, TFT, and TTF. Now, make up your tests and see what happens.

Test Return Input Int Boolean Boolean BooleanFTT () found the bug that was missed by your statement and branch coverage efforts. Further, the number of basis paths grows linearly with the number of decisions, not exponentially, keeping the number of required tests on par with the number required to achieve full branch coverage. In fact, because basis path testing covers all statements and branches in a method, it effectively subsumes branch and statement coverage.

But, why didn’t you test that the other potential paths? Remember, the goal of basis path testing is to test all decision outcomes independently of one another. Testing the four basis paths achieves this goal, making the other paths extraneous.

If you had started with FFF as your baseline path, you’d wind up with the basis set of (FFF, TFF, FTF, FFT) making the TTT path extraneous. Both basis sets are equally valid, and either satisfies your independent decision outcome criterion.

Creating Test Data

Achieving 100 percent basis path coverage is easy in this example, but fully testing a basis set of paths in the real world will be more challenging, even impossible. Because basis path coverage tests the interaction between decisions in a method, you need to use test data that causes execution of a specific path, not just a single decision outcome, as is necessary with branch coverage. Injecting data to force execution down a specific path is difficult, but there are a few coding practices that you can keep in mind to make the testing process easier.

  • Keep your code simple. The lower the cyclomatic complexity of your methods, the better. Refactor when you can to lower your numbers. The higher the number, the harder it is to test, and the numbers above 10 are essentially untestable. Not only does this reduce the number of basis paths that you need to test, but it reduces the number of decisions along each path.
  • Avoid duplicate decisions.
  • Avoid data dependencies.

Consider the following example Basis path testing:

The variable x depends indirectly on the object1 parameter, but the intervening code makes it difficult to see the relationship. As a method grows more complex, it may be nearly impossible to see the relationship between the method’s input and the decision expression.

Summary

Although statement and branch coverage metrics are easy to compute and achieve, both can leave critical defects undiscovered, giving developers and managers a false sense of security. Basis path coverage provides a more robust and comprehensive approach for uncovering these missed defects without exponentially increasing the number of tests required

Was this article helpful?

Related Articles