Basis Path Testing

In software testing, there are many paths between the entry and exit of a software program. So it’s difficult to fully test all paths of even a simple unit. This is a challenge when we design test cases. We need to eliminate redundant tests by providing adequate test coverage for effective testing. One of the ways to do so, we can apply a method called basis path testing.

First of all, basis path testing is a white box method for designing test cases. The method was first proposed by McCabe in 1980's. It is a hybrid of path testing and branch testing methods. Path testing is designed to execute all or selected paths through a computer program. And branch testing is designed to execute each outcome from each decision point in a computer program. Thus, basis path testing analyzes the control flow graph of the program and uses McCabe Cyclomatic complexity to determine the number of independent paths to generate test cases for each path. It guarantees complete branch coverage (all control flow graphs’ edges), but without covering all possible control flow graphs.

The principle behind basis path testing is that all independent paths of the program have to be tested at least once. Below are the steps of this technique:

-          Draw a control flow graph.

-          Determine Cyclomatic complexity.

-          Find a basis set of paths.

-          Generate test cases for each path.

Step 1: Draw a control flow graph

Basic control flow graph structures: 

    On a control flow graph, we can see that: 

             Arrows  or edges represent flows of control.

-          Circles or nodes represent actions.

-          Areas bounded by edges and nodes are called regions.

-          A predicate node is a node containing a condition. 

    Below is an example of control flow graph:

Step 2: Determine Cyclomatic complexity

Cyclomatic complexity is a software metric used to indicate the complexity of a program. It is a measure of the number of linearly independent paths.

There are several different methods to calculate Cyclomatic complexity:

1.      Cyclomatic complexity = edges - nodes + 2p

Where p = number of unconnected parts of the graph.

From the example in Step 1we see that the graph has 8 edges and7 nodes, and the number of unconnected parts of the graph is 1 so the Cyclomatic complexity = 8-7+ 2*1= 3.

2.      Cyclomatic complexity= Number of Predicate Nodes + 1

From the example in Step 1, we can redraw it as below to show predicate nodes clearly:

As we see, there are two predicate nodes in the graph. So the Cyclomatic complexity = 2+1= 3.

3.      Cyclomatic complexity =number of regions in the control flow graph

Follow our example, we have three regions in the control flow graph as below

So the Cyclomatic complexity = 3.

Step 3: Find a basis set of paths

The Cyclomatic complexity tells us the number of paths to evaluate for basis path testing. In the example, we have 3 paths, and our basis set of paths is:

Path 1: 1, 2, 3, 5, 6, 7.

Path 2: 1, 2, 4, 5, 6, 7.

Path 3: 1, 6, 7.

Step 4: Generate test cases for each path

After determining the basis set of path, we can generate the test case for each path. Usually we need at least one test case to cover one path. In the example, however, Path 3 is already covered by Path 1 and 2 so we only need to write 2 test cases.

In conclusion, basis path testing helps us to reduce redundant tests. It suggests independent paths from which we write test cases needed to ensure that every statement and condition can be executed at least one time.

                                                                                                                         Hoa Le