This introduction is adapted from section 1 of NISTIR 5737.
One of the biggest problems in unit testing is how to determine test cases. The tester has to ensure that there are enough tests to do thorough testing, but not so many tests that all of the limited testing time is used up. There are several different techniques to pick test cases including using boundary cases, dataflow testing and branch testing. No single technique can supply sufficient test cases, so usually a combination of techniques are used. This paper address one of those techniques, basis set testing. A basis set is a set of linearly independent paths that can be used to construct any path through the program flow graph.
Testing techniques can be divided into various categories. Black box testing ignores the internals of the software unit. Structured testing is, on the other hand, "Testing that takes into account the internal mechanism of a system or component"(IEEE Standard 610). This can be further subdivided into different types including path testing, "Testing designed to execute all or selected paths through a computer program"(IEEE Standard 610) and branch testing, "Testing designed to execute each outcome of each decision point in a computer program"(IEEE Standard 610). Basis testing, also known as Structured Testing(see NIST SP500-99), is a hybrid between these two techniques. The test paths in a basis set fulfill the requirements of branch testing and also test all of the paths that could be used to construct any arbitrary path through the graph.
Any function in a program can be represented as a control flow graph. The nodes in this graph are program statements, while the directed edges are flow of control. Two nodes can be either unconnected, connected by an edge in either direction or connected by an edge in each direction. When tracing a path from the source to the sink, a backedge is a edge that leads back to a node that has already been visited. A flowgraph contains one source node and one sink. A source node is a node which has no incoming edges, while a sink node is a node with no outgoing edges. A program function may have more than one sink, but this graph can be converted into a graph with only one sink. Some languages also allow more than one source. This construct is very rare and not used in Structured Programming.
A basis set is a set of linearly independent test paths. A path can be associated with a vector, where each element in the vector is the number of times that an edge is traversed. For example, consider a graph with 4 edges: a, b, c and d. The path ac can be represented by the vector [1 0 1 0]. Paths are combined by adding or subtracting the paths' vector representations. Each path in the basis set can not be formed as a combination of other paths in the basis set. Also, any path through the control flow graph can be formed as a combination of paths in the basis set.
This figure shows a simplified control flow graph. While a complete flow graph would not have two edges going to the same destination, this requirement has been relaxed to keep the number of paths to a manageable size for this example. A basis set for this graph is {ac, ad, bc}. The path bd can be constructed by the combination bc + ad - ac as shown in this table.
| Edge | bd | bc | bc + ad | bc + ad - ac |
| a | 0 | 0 | 1 | 0 |
| b | 1 | 1 | 1 | 1 |
| c | 0 | 1 | 1 | 0 |
| d | 1 | 0 | 1 | 1 |
McCabe's complexity measure is a software metric that attempts to evaluate how complex a function is. The number of paths in the basis set is equal to the complexity measure of that function. The value of the complexity measure is equal to the cyclomatic complexity of the flowgraph if all of the edges were undirected instead of directed. This can be calculated as equal to e - n + 2, where e is the number of edges and n is the number of nodes.
We are currently doing further development on the prototype tool developed as part of NISTIR 5737 and applying it to the Java programming language. This tool will be part of an integrated set of testing tools.
T. McCabe, "A Complexity Measure", IEEE Transactions on Software Engineering, Vol SE-2, Number 4, December 1976, pg. 308-320.
T. McCabe, "NBS Special Publication 500-99 Structured Testing: A Software Testing Methodology Using the Cyclomatic Complexity Measure", December, 1982.
G. Myers, "An Extension to the Cyclomatic Measure of Program Complexity", SIGPLAN Notices, October, 1977.
J. Poole, "NISTIR 5737 A Method to Determine a Basis Set of Paths to Perform Program Testing", Department of Commerce, November, 1995.
Investigator: Joseph Poole