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
