## Introduction

Software is tested from two different perspectives:

- Internal program logic is exercised using “white box” test case design techniques.
- Software requirements are exercised using “black box” test case design techniques.

In both cases, the intent is to find the maximum number of errors with the minimum amount of effort and time.

White-box testing of software is predicated on close examination of procedural detail. Logical paths through the software are tested by providing test cases that exercise specific sets of conditions and/or loops. The "status of the program" may be examined at various points to determine if the expected or asserted status corresponds to the actual status.

## White Box Testing Techniques

White-box testing, sometimes called glass-box testing is a test case design method that uses the control structure of the procedural design to derive test cases.

Using white-box testing methods, the software engineer can derive test cases that:

- guarantee that all independent paths within a module have been exercised at least once
- exercise all logical decisions on their true and false sides
- execute all loops at their boundaries and within their operational bounds, and
- exercise internal data structures to ensure their validity

## Basis Path Testing

Basis path testing is a white-box testing technique first proposed by Tom McCabe. The basis path method enables the test case designer to derive a logical complexity measure of a procedural design and use this measure as a guide for defining a basis set of execution paths. Test cases derived to exercise the basis set are guaranteed to execute every statement in the program at least one time during testing.

#### Flow Graph Notation

The flow graph depicts logical control flow which is used to depict the program control structure.

Referring to the figure, each circle, called a flow graph node, represents one or more procedural statements. A sequence of process boxes and a decision diamond can map into a single node. The arrows on the flow graph, called edges or links, represent flow of control and are analogous to flowchart arrows. An edge must terminate at a node, even if the node does not represent any procedural statements (e.g., see the symbol for the `if`

-`then`

-`else `

construct). Areas bounded by edges and nodes are called regions. When counting regions, we include the area outside the graph as a region. Each node that contains a condition is called a predicate node and is characterized by two or more edges emanating from it.

#### Cyclomatic Complexity / Independent Program Path

Cyclomatic complexity is software metric that provides a quantitative measure of the logical complexity of a program. When used in the context of the basis path testing method, the value computed for cyclomatic complexity defines the number of independent paths in the basis set of a program and provides us with an upper bound for the number of tests that must be conducted to ensure that all statements have been executed at least once.

An independent path is any path through the program that introduces at least one new set of processing statements or a new condition. When stated in terms of a flow graph, an independent path must move along at least one edge that has not been traversed before the path is defined.

Fig A

Fig B

Fig C

#### Example:

For example, a set of independent paths for the flow graph illustrated in Figure B is:

path 1: 1-11

path 2: 1-2-3-4-5-10-1-11

path 3: 1-2-3-6-8-9-10-1-11

path 4: 1-2-3-6-7-9-10-1-11

Note that each new path introduces a new edge.

The path 1-2-3-4-5-10-1-2-3-6-8-9-10-1-11 is not considered to be an independent path because it is simply a combination of already specified paths and does not traverse any new edges.

Paths 1, 2, 3, and 4 constitute a basis set for the flow graph in Figure B.

That is, if tests can be designed to force execution of these paths (a basis set), every statement in the program will have been guaranteed to be executed at least one time and every condition will have been executed on its true and false sides. It should be noted that the basis set is not unique. In fact, a number of different basis sets can be derived for a given procedural design.

How do we know how many paths to look for? The computation of cyclomatic complexity provides the answer. Cyclomatic complexity has a foundation in graph theory and provides us with an extremely useful software metric. Complexity is computed in one of three ways:

- The number of regions of the flow graph correspond to the cyclomatic complexity.
- Cyclomatic complexity, V(G), for a flow graph, G, is defined as V(G) = E - N + 2 where E is the number of flow graph edges, N is the number of flow graph nodes.
- Cyclomatic complexity, V(G), for a flow graph, G, is also defined as V(G) = P + 1 where P is the number of predicate nodes contained in the flow graph G.

Referring once more to the flow graph in Figure B, the cyclomatic complexity can be computed using each of the algorithms just noted:

- The flow graph has four regions.
- V(G) = 11 edges - 9 nodes + 2 = 4.
- V(G) = 3 predicate nodes + 1 = 4.

Therefore, the cyclomatic complexity of the flow graph in Figure B is 4.

More important, the value for V(G) provides us with an upper bound for the number of independent paths that form the basis set and, by implication, an upper bound on the number of tests that must be designed and executed to guarantee coverage of all program statements.

#### Deriving Test Cases

Fig A

**1. Using the design or code as a foundation, draw a corresponding flow graph. **A flow graph is created using the symbols and construction rules. Referring to the PDL for average in Figure A, a flow graph is created by numbering those PDL statements that will be mapped into corresponding flow graph nodes. The corresponding flow graph is in Figure B.

**2. Determine the cyclomatic complexity of the resultant flow graph. **The cyclomatic complexity, V(G), is determined. It should be noted that V(G) can be determined without developing a flow graph by counting all conditional statements in the PDL (for the procedure average, compound conditions count as two) and adding 1. Referring to Figure B,

V(G) = 6 regions

V(G) = 17 edges _ 13 nodes + 2 = 6

V(G) = 5 predicate nodes + 1 = 6

Fig B

**3. Determine a basis set of linearly independent paths. **The value of V(G) provides the number of linearly independent paths through the program control structure. In the case of procedure average, we expect to specify six paths:

path 1: 1-2-10-11-13

path 2: 1-2-10-12-13

path 3: 1-2-3-10-11-13

path 4: 1-2-3-4-5-8-9-2-. . .

path 5: 1-2-3-4-5-6-8-9-2-. . .

path 6: 1-2-3-4-5-6-7-8-9-2-. . .

The ellipsis (. . .) following paths 4, 5, and 6 indicates that any path through the remainder of the control structure is acceptable. It is often worthwhile to identify predicate nodes as an aid in the derivation of test cases. In this case, nodes 2, 3, 5, 6, and 10 are predicate nodes.

**4. Prepare test cases that will force execution of each path in the basis set. **Data should be chosen so that conditions at the predicate nodes are appropriately set as each path is tested. Test cases that satisfy the basis set just described are:

**Path 1 test case: **

value(k) = valid input, where k < i for 2 = i = 100

value(i) = -999 where 2 = i = 100

Expected results: Correct average based on k values and proper totals.

Note: Path 1 cannot be tested stand-alone but must be tested as part of path 4, 5, and 6 tests.

**Path 2 test case: **

value(1) = -999

Expected results: Average = -999; other totals at initial values.

**Path 3 test case: **

Attempt to process 101 or more values. First 100 values should be valid.

Expected results: Same as test case 1.

**Path 4 test case: **

value(i) = valid input where i < 100

value(k) < minimum where k < i

Expected results: Correct average based on k values and proper totals.

**Path 5 test case: **

value(i) = valid input where i < 100

value(k) > maximum where k <= i

Expected results: Correct average based on n values and proper totals.

**Path 6 test case: **

value(i) = valid input where i < 100

Expected results: Correct average based on n values and proper totals.

Each test case is executed and compared to expected results. Once all test cases have been completed, the tester can be sure that all statements in the program have been executed at least once.

It is important to note that some independent paths (e.g., path 1 in our example) cannot be tested in stand-alone fashion. That is, the combination of data required to traverse the path cannot be achieved in the normal flow of the program. In such cases, these paths are tested as part of another path test.

**Note:** Errors are much more common in the neighbourhood of logical conditions than they are in the locus of the sequential processing.

Cyclomatic complexity provides the upper bound on the number of test cases that must be executed to guarantee that every statement in a component has been executed at least once.

## History

- 9
^{th} June, 2009: Initial post