Code-Based Approaches

Basis Testing Overview

Basis Testing is a White Box test case technique employing control flow graph representations of program module logic. Control flow graphs are network diagrams graphically depicting the logical pathways through a module. Test cases are created based on a set of independent paths enumerated from the graph. Thomas J. McCabe developed this method, formally known as Structured Testing and informally called basis testing. McCabe's approach will be discussed as a White Box test case development strategy and not as a testing methodology. For a comprehensive discussion of McCabe's methodology, see his original work (11,12).

The major advantage of McCabe's approach is that it incorporates the Cyclomatic Number as a measure of program/module complexity. The disadvantage is that the control flow charts are generated either from a flow chart before a module is coded or from the source listing after construction is completed. There are two problems with this approach. First, control flow graphs are logical in nature, while flowcharts and source listings are inherently physical or implementation dependent. Second, there are no explicit guidelines for systematically converting the physical information contained in flow charts and source listings into the logical detail depicted in control flow graphs.

Control flow graph construction occurs earlier in the design process, and test case design happens before physical design (via flowcharts) and coding. This facilitates design reviews, Walkthroughs, and Inspections; more important, however, is the fact that program and module testing are placed within the framework of a formal structured systems design methodology.

The Basis Testing Technique

Basis Testing, as described by McCabe, uses source code or flowcharts to generate Control Flow Graphs of program modules. The flow graphs are used to enumerate the independent control paths and to calculate the Cyclomatic number V(G), a measure of procedural complexity (see Myers's extension to the Cyclomatic complexity measure [17]). A basis set of test cases covering the independent paths is then created (11).

A Control Flow Graph is a network diagram in which nodes represent program segments and edges are connectors from given segments to other program segments. Edges depict a transfer of control from one node to another and can represent any form of conditional or unconditional transfer. A node represents a decision with multiple emanating edges. A loop is a node with an emanating edge that returns to the node. A region is an area within a graph that is completely bounded by nodes and edges. Each graph has entry and exit nodes. A path is a route through a graph that traverses edges from node to node beginning with the entry node and ending with the exit node (11).

A node is a block of sequentially executed (imperative) actions, and an edge is a transfer of control from one block to another. The If/Then/Else/Endif and nested If/Then/Else/Endif are also examples of statements that conditionally transfer control to specific groups of actions.

Internal structural complexity in program modules is a consequence of the number of functions the module implements, the number of inputs to the module and outputs from the module, and the number of decisions in the module. Structured programming doctrine dictates that a module should implement one and only one function (21,22). If this basic rule of thumb is followed, complexity due to the number of functions is minimized. Structured programming dogma also stands on the premise that each module has but a single entry point and a single exit point. If such is the case, complexity due to the number of inputs and outputs can be controlled because the module interface is simplified. This leaves the number of decisions as the major structural dimension contributing to module complexity.

McCabe's complexity measure is an indication of a module's decision structure—it measures procedural complexity as a function of the number of decisions in the Control Flow Graph (11,12). Cyclomatic complexity is a useful metric because it is also representative of perceived complexity. Miller found that the maximum amount of information the human mind can simultaneously process is 3 bits (defining a bit as the amount of information required in order to discriminate between two equally likely alternatives). The total number of alternatives is 2 raised to a power equal to the number of discriminations that are involved in a complex decision (13).

Based on his findings, Miller formulated the seven ± two rule. Seven alternatives is optimal for memorization, because each choice is a discrimination alternative. Miller determined that the maximum number of alternatives humans can handle simultaneously is 9 (13). If this principle is applied to the decision structure of program modules, the number of bits a programmer must process to understand a complex decision is a function of 2 raised to a power that represents of the number of conditions contained in the decision. An If/Else nest three levels deep has 2³, or 8, alternatives to comprehend, which is below the limit established by Miller. Adding one more nested decision raises the number of alternatives to 16—well beyond the inherent limit. Consequently, a module with a Cyclomatic complexity greater that 10 is too complex for human short-term memory to comprehend all at one time. If C is greater than 10, a module should be reconstructed or it may be untestable.

The Cyclomatic Number can be calculated using any of three simple equations. The first equation representing the Cyclomatic number is

C = E − N + 2

where C is the Cyclomatic Number (C has been substituted for V(G), 2 is used instead of 2P (P is usually 0) to simplify and make the notation more meaningful), E is the number of edges, and N is the number of nodes. The Cyclomatic Complexity is computed as a function of the relationship of edges to nodes.

Complexity can also be computed as a function of the regions in the control flow graph. Edges cannot cross one another, and regions formed by violations of this rule are not legitimate regions. Only legitimate regions can be included in the calculation of complexity.

The equation based on the number of regions is

C = R + 1

where C is again the Cyclomatic Number, and R is the number of legitimate regions.

The Cyclomatic Number can also be computed based upon the number of primitive decisions in the graph. A primitive decision is one evaluating the condition states associated with a single condition. Nested conditions and conditions connected by logical operators (AND, OR, etc.) should be treated as though they were completely separate decisions.

The equation is

C = D + 1

where D is the number of primitive decisions.

The advantage of the latter two equations is that they are easier to understand and use. In fact, the control flow graph does not have to be constructed to use the third equation. The number of decisions in the program flowchart or source listing can be counted and substituted for D in the equation.

These three equations are applied to individual program modules. A measure of the total program complexity can be derived based on the sum of the individual module complexities with a factor subtracted for redundant nodes. A redundant node is a node in a high-level module, such as the mainline module, that would be replaced by a subdiagram if the called module were called in line as part of the superordinate module.

The equation is

C_t = C_i + 2 − (N − 1)

where C_t represents the total program complexity, C_i represents the individual module complexities, and N is the number of modules in the program.

The value of C in each module represents the upper boundary for the maximum number of independent paths through a given program unit. If a set of control paths is constructed equal to C, test cases that exercise those paths will adequately test the module and constitute the basis set of test cases. The basis set does not necessarily execute all possible paths through a segment, but rather a subset from which all other paths can be fabricated.

Once the Cyclomatic Number is known, the independent paths can be enumerated. To enumerate the basis set of paths:

When no unmarked edges remain, the basis set of paths is complete. The total number of paths must equal C. If a set of paths cannot be created which equals C, then the module is poorly designed and overly complex. It is best to redesign such modules.

It is extremely helpful when constructing the test cases to annotate the decision nodes with the condition being tested and to label the true and false branching edges. One test case is created that will execute each independent path at least once. The basis set of test cases must also exercise each conditional branch at least once. A test case is an input data record containing either a valid or an invalid value for each data field. Figure 3.6 illustrates this technique.