The baseline method, described in this section, is a technique for identifying a set of control paths to satisfy the structured testing criterion. The technique results in a basis set of test paths through the module being tested, equal in number to the cyclomatic complexity of the module. As discussed in section 2, the paths in a basis are independent and generate all paths via linear combinations. Note that "the baseline method" is different from "basis path testing." Basis path testing, another name for structured testing, is the requirement that a basis set of paths should be tested. The baseline method is one way to derive a basis set of paths. The word "baseline" comes from the first path, which is typically selected by the tester to represent the "baseline" functionality of the module. The baseline method provides support for structured testing, since it gives a specific technique to identify an adequate test set rather than resorting to trial and error until the criterion is satisfied.

6.1 Generating a basis set of paths

6.2 The simplified baseline method

In addition to a basis set of paths, which is a basis for the rows of the path/edge matrix if all possible paths were represented, it is possible to also consider a basis set of edges, which is a basis for the columns of the same matrix. Since row rank equals column rank, the cyclomatic complexity is also the number of edges in every edge basis. The overall approach of this section is to first select a basis set of edges, then use that set in the algorithm to generate each successive path, and finally use the resulting path/edge matrix restricted to basis columns to show that the set of generated paths is a basis.

First, for every decision in the module, select an outcome with the shortest (in terms of number of other decisions encountered) path to the module exit. Ties can be broken arbitrarily. Mark these selected decision outcomes non-basic. Call these outcomes non-basic because all other decision outcome edges, along with the module entry edge, form the column basis. The key to the simplified baseline method is to execute exactly one new basis edge with each successive path. This is possible because from any node in the control flow graph, there is a path to the exit node that avoids all basis columns (taking the non-basic outcome of every decision encountered, which also gives a shortest path in terms of decisions encountered to the exit).

The simplified baseline algorithm can now be described. For the initial baseline path, take the non-basic outcome of every decision encountered. Note that this gives a shortest path through the module. For each successive path, first pick any decision that has had the non-basic outcome traversed by an earlier path, but that has a basis outcome that has not been executed by any earlier path. Then, construct the path by following the earlier path up to that decision point, traverse that new basis outcome edge, and then follow only non-basic decision outcomes to the module exit. At each step, exactly one new basis edge is added, so the total number of paths generated is the cyclomatic complexity. It is sufficient to show that they are linearly independent to complete the proof that they are a basis set of paths. To see that, consider the path/edge matrix with the generated set of paths in order as the rows and the basis edges as the columns, with the columns ordered by the index of the path which first traversed each corresponding edge. The matrix is then lower-triangular with all major diagonal entries equal to "1," so all rows are linearly independent. Thus, the simplified baseline algorithm generates a basis.

6.3 The baseline method in practice

The first step is to pick a functional "baseline" path through the program that represents a legitimate function and not just an error exit. The selection of this baseline path is somewhat arbitrary. The key, however, is to pick a representative function rather than an exceptional condition. The exceptional conditions will of course be tested on some path generated by the method, but since many of the decision outcomes along the baseline path tend to be shared with several other paths it is helpful to make them as "typical" as possible. To summarize, the baseline should be, in the tester's judgement, the most important path to test. It is usually helpful to devote extra effort to the baseline path, exercising all its functional requirements and developing several data sets that might expose errors.

To generate the next path, change the outcome of the first decision along the baseline path while keeping the maximum number of other decision outcomes the same as the baseline path. That is, once the baseline path is "rejoined," it should be followed to the module exit. Any decisions encountered that are not part of the baseline path may be taken arbitrarily, and, as with the baseline path, it is a good idea to follow a robust functional path subject to the constraint of varying just the first baseline decision. To generate the third path, begin again with the baseline but vary the second decision outcome rather than the first. When all of the decisions along the baseline have been flipped, proceed to the second path, flipping its new decisions as if it were the baseline. When every decision in the module has been flipped, the test path set is complete. Multiway decisions must of course be flipped to each of their possible outcomes in turn.

Sometimes a tester wants even more flexibility, relaxing the requirement that once rejoined, the path from which a decision was flipped is followed to the end. Unfortunately, this may result in a linearly dependent set of paths, not satisfying the structured testing criterion (although weak structured testing is still satisfied). For complete freedom in selecting test paths for structured testing, the answer lies with an automated tool. The tester can specify arbitrary paths by their decision outcome sequence, and the tool then determines whether each new path is linearly independent of the previous ones in the same way that it would analyze the execution trace if the paths were actually executed during testing. Similarly, the tool can at any stage produce a minimal set of paths to complete the basis set, which the tester can either accept or change. Even with the standard baseline method, it may be worth having a tool verify that a basis has indeed been generated, since it takes much less effort to correct the test set in the test planning stage than after the tests have already been executed.

6.4 Example of the baseline method

Figure 6-1. Graph of "count" with decision outcomes marked.

Figure 6-2 shows the set of test paths constructed by the method. The baseline path corresponds to input "AB", a representative functional input (which happens to expose the module's bug, the goal of every baseline test). It takes "=A" TRUE, "=3B" TRUE, "=B" FALSE (note, this does not count as flipping the "=B" decision!), "=C" FALSE, and "!=`\0'" FALSE. The second path is generated by flipping the first decision along the baseline, so it takes "=A" FALSE, and there are no other decisions before the module exit. It corresponds to input "X". The third path flips the second decision along the baseline, so it takes "=A" TRUE (following the first decision), "=B" FALSE (flipping the second decision), "=C" FALSE (picking up the baseline again), and "!=`\0'" FALSE (following the baseline to the end). It corresponds to input "A". The fourth path flips the third decision along the baseline, so it takes "=A" TRUE (following the first decision), "=B" TRUE (following the second decision), "=B" FALSE (still following the second decision -- when a decision is revisited due to looping it is not considered a separate decision for flipping purposes), "=C" TRUE (flipping the third decision), "=B" FALSE (picking up the baseline at the last occurrence of the "=B" decision rather than going through the loop again), "=C" FALSE (continuing to follow the rest of the baseline), "!=`\0'" FALSE (following the baseline to the end). It corresponds to input "ABC". The fifth and final path flips the fourth and final decision, so it takes "=A" TRUE (following), "=B" TRUE (following), "=B" FALSE (following), "=C" FALSE (following), "!=`0'" TRUE (flipping), "=B" FALSE (picking up the baseline again), "=C" FALSE (following), "!=`\0'" FALSE (following to the end). It corresponds to input "ABX".

Test Path 1 (baseline): 0 1 2 3 4 5 2 3 6 7 10 11 14 16 17 11( 1): string[index]=='A' ==> TRUE 13( 3): string[index]=='B' ==> TRUE 13( 3): string[index]=='B' ==> FALSE 18( 7): string[index]=='C' ==> FALSE 25( 11): string[index]!='\0' ==> FALSE Test Path 2: 0 1 15 16 17 11( 1): string[index]=='A' ==> FALSE Test Path 3: 0 1 2 3 6 7 10 11 14 16 17 11( 1): string[index]=='A' ==> TRUE 13( 3): string[index]=='B' ==> FALSE 18( 7): string[index]=='C' ==> FALSE 25( 11): string[index]!='\0' ==> FALSE Test Path 4: 0 1 2 3 4 5 2 3 6 7 8 9 2 3 6 7 10 11 14 16 17 11( 1): string[index]=='A' ==> TRUE 13( 3): string[index]=='B' ==> TRUE 13( 3): string[index]=='B' ==> FALSE 18( 7): string[index]=='C' ==> TRUE 13( 3): string[index]=='B' ==> FALSE 18( 7): string[index]=='C' ==> FALSE 25( 11): string[index]!='\0' ==> FALSE Test Path 5: 0 1 2 3 4 5 2 3 6 7 10 11 12 13 2 3 6 7 10 11 14 16 17 11( 1): string[index]=='A' ==> TRUE 13( 3): string[index]=='B' ==> TRUE 13( 3): string[index]=='B' ==> FALSE 18( 7): string[index]=='C' ==> FALSE 25( 11): string[index]!='\0' ==> TRUE 13( 3): string[index]=='B' ==> FALSE 18( 7): string[index]=='C' ==> FALSE 25( 11): string[index]!='\0' ==> FALSE

Figure 6-2. Test paths generated with the baseline method.

Of the tests in Figure 6-2, the baseline and test 5 both detect the error in the module. Although this is a different set of test paths than the ones shown (by input data only) in Figure 5-5, both sets satisfy the structured testing criterion and both sets detect the module's error. One of the strengths of both the structured testing criterion and the baseline method is that testers have a great deal of freedom when developing tests, yet the resultant tests have a guaranteed level of rigor.

6.5 Completing testing with the baseline method

The technique is to first run the functional test suite and (again, automation is key) fill matrices with the paths that were executed. Next, for those modules that did not have a complete basis set tested, use the baseline method to generate a basis set of paths. Then, for each of the paths resulting from the basis set, determine whether it increases the matrix rank. If it does, execute it; if it does not, discard it. The new independent paths that were not discarded form a minimal set of additional paths to complete testing.

This technique works because, in essence, it extends an independent subset of the functionally-tested paths to form a basis. Regardless of the initial set of paths, adding each independent member of a basis results in a set of tests that generates that basis and therefore also generates all possible paths by linear combination. Additionally, no matter which basis is selected first, each non-discarded member of the basis increases the rank of the matrix by exactly one. The new tests are therefore guaranteed to be a minimal set. In fact, the number of new tests will be the cyclomatic complexity minus the rank of the original set of functional tests.

It may seem that since an automated tool is required to perform the path tracing of the functional test suite and the determination whether each member of the basis generated by the baseline method is independent, it is also possible to use just the minimal set of additional test paths provided by the tool rather than using the baseline method at all. Much of the time this is true. However, just as testers benefit from using the baseline method rather than the simplified baseline method when planning structured testing from scratch, so also the freedom to select candidate completion tests after functional testing is often valuable.