By Hoa Le from Ho Chi Minh City Software Testing Club
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.
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:
- 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:
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:
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
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.