In sections 2 and 5, cyclomatic complexity and the structured testing methodology are discussed at the level of individual modules and unit testing. This section generalizes the approach to the integration level, addressing the complexity and integration testing of design structures that consist of multiple modules.

7.1 Integration strategies

Very small systems are often assembled and tested in one phase. For most real systems, this is impractical for two major reasons. First, the system would fail in so many places at once that the debugging and retesting effort would be impractical [PRESSMAN]. Second, satisfying any white box testing criterion would be very difficult, because of the vast amount of detail separating the input data from the individual code modules. In fact, most integration testing has been traditionally limited to ``black box'' techniques [HETZEL]. Large systems may require many integration phases, beginning with assembling modules into low-level subsystems, then assembling subsystems into larger subsystems, and finally assembling the highest level subsystems into the complete system.

To be most effective, an integration testing technique should fit well with the overall integration strategy. In a multi-phase integration, testing at each phase helps detect errors early and keep the system under control. Performing only cursory testing at early integration phases and then applying a more rigorous criterion for the final stage is really just a variant of the high-risk "big bang" approach. However, performing rigorous testing of the entire software involved in each integration phase involves a lot of wasteful duplication of effort across phases. The key is to leverage the overall integration structure to allow rigorous testing at each phase while minimizing duplication of effort.

It is important to understand the relationship between module testing and integration testing. In one view, modules are rigorously tested in isolation using stubs and drivers before any integration is attempted. Then, integration testing concentrates entirely on module interactions, assuming that the details within each module are accurate. At the other extreme, module and integration testing can be combined, verifying the details of each module's implementation in an integration context. Many projects compromise, combining module testing with the lowest level of subsystem integration testing, and then performing pure integration testing at higher levels. Each of these views of integration testing may be appropriate for any given project, so an integration testing method should be flexible enough to accommodate them all. The rest of this section describes the integration-level structured testing techniques, first for some special cases and then in full generality.

7.2 Combining module testing and integration testing

The most obvious combined strategy is pure "big bang" integration, in which the entire system is assembled and tested in one step without even prior module testing. As discussed earlier, this strategy is not practical for most real systems. However, at least in theory, it makes efficient use of testing resources. First, there is no overhead associated with constructing stubs and drivers to perform module testing or partial integration. Second, no additional integration-specific tests are required beyond the module tests as determined by structured testing. Thus, despite its impracticality, this strategy clarifies the benefits of combining module testing with integration testing to the greatest feasible extent.

It is also possible to combine module and integration testing with the bottom-up integration strategy. In this strategy, using test drivers but not stubs, begin by performing module-level structured testing on the lowest-level modules using test drivers. Then, perform module-level structured testing in a similar fashion at each successive level of the design hierarchy, using test drivers for each new module being tested in integration with all lower-level modules. Figure 7-1 illustrates the technique. First, the lowest-level modules "B" and "C" are tested with drivers. Next, the higher-level module "A" is tested with a driver in integration with modules "B" and "C." Finally, integration could continue until the top-level module of the program is tested (with real input data) in integration with the entire program. As shown in Figure 7-1, the total number of tests required by this technique is the sum of the cyclomatic complexities of all modules being integrated. As expected, this is the same number of tests that would be required to perform structured testing on each module in isolation using stubs and drivers.

Figure 7-1. Combining module testing with bottom-up integration.

7.3 Generalization of module testing criteria

More useful generalizations adapt the module testing criterion to focus on interactions between modules rather than attempting to test all of the details of each module's implementation in an integration context. The statement coverage module testing criterion, in which each statement is required to be exercised during module testing, can be generalized to require each module call statement to be exercised during integration testing. Although the specifics of the generalization of structured testing are more detailed, the approach is the same. Since structured testing at the module level requires that all the decision logic in a module's control flow graph be tested independently, the appropriate generalization to the integration level requires that just the decision logic involved with calls to other modules be tested independently. The following subsections explore this approach in detail.

7.4 Module design complexity

Rules 1 through 4 are intended to be applied iteratively until none of them can be applied, at which point the design reduction is complete. By this process, even very complex logic can be eliminated as long as it does not involve any module calls.

Figure 7-2. Design reduction rules.

Figure 7-3 shows a control flow graph before and after design reduction. Rules 3 and 4 can be applied immediately to the original graph, yielding the intermediate graph. Then rule 1 can be applied three times to the left conditional branch, at which point rule 3 can be applied again, after which five more applications of rule 1 complete the reduction. The second application of rule 3 illustrates that a conditional structure may be eliminated even if its body contains a call node, as long as there is at least one path through its body that does not contain any call nodes.

Figure 7-3. Design reduction example.

The module design complexity, iv(G), is defined as the cyclomatic complexity of the reduced graph after design reduction has been performed. In Figure 7-3, the module design complexity is 2. The design flow graph in Figure 7-4 displays the logic that contributes to module design complexity superimposed on the entire control flow graph for a module with cyclomatic complexity 6 and module design complexity 3.

Figure 7-4. Design graph with v(G) = 6, iv(G) = 3.

When structured testing has already been performed at the module level, module design complexity can be used to drive integration testing, requiring a basis set of paths through each module's reduced graph to be tested in integration. For the bottom-up integration strategy discussed in section 7-2, the total number of integration tests becomes the sum of the module design complexities of all modules being integrated. Since module design complexity can be significantly less than cyclomatic complexity, this technique reduces the number of integration tests. It also simplifies the process of deriving data for each test path, since there are fewer constraints on paths through the reduced graph than on paths through the full graph.

7.5 Integration complexity

Figure 7-5 shows an example program with integration complexity 4, giving the control structure, cyclomatic complexity, and module design complexity for each module and a set of four independent integration tests.

Figure 7-5. Integration complexity example.

Although a basis set of paths through each module's design-reduced control flow graph can typically be exercised with fewer than S₁ integration tests, more tests are never required. For the most rigorous level of structured testing, a complete basis set of S₁ integration tests should be performed.

Integration complexity can be approximated from a structured design [YOURDON], allowing integration test effort to be predicted before coding begins. The number of design predicates in a structure chart (conditional and iterative calls) can be used to approximate the eventual integration complexity. Recall the simplified formula for cyclomatic complexity from section 4.1, that for modules with only binary decisions and p decision predicates, v(G) = p + 1. The corresponding formula for integration complexity is that for programs with d design predicates, S₁ will be approximately d + 1. The reason is that each design predicate (conditional or iterative call) tends to be implemented by a decision predicate in the design-reduced graph of a module in the eventual implemented program. Hence, recalling that iv(G) is the cyclomatic complexity of the design-reduced graph, combine the v(G) and S₁ formulas to calculate the approximation that S₁ = SUM iv(G) - n + 1 = SUM (iv(G) - 1) + 1 = SUM (v(G_Reduced) - 1) + 1 = d + 1, where d is the total number of decision predicates in the design-reduced graphs of the modules of the implemented program, and approximately equal to the number of design predicates in the original program design. Figure 7-6 shows a structured design representation with three design predicates and therefore an expected integration complexity of four.

Figure 7-6. Predicting integration complexity.

7.6 Incremental integration

As a simple example of the approach, recall the statement coverage module testing criterion and its integration-level variant from section 7.2 that all module call statements should be exercised during integration. Although this criterion is certainly not as rigorous as structured testing, its simplicity makes it easy to extend to support incremental integration. Although the generalization of structured testing is more detailed, the basic approach is the same. To extend statement coverage to support incremental integration, it is required that all module call statements from one component into a different component be exercised at each integration stage. To form a completely flexible "statement testing" criterion, it is required that each statement be executed during the first phase (which may be anything from single modules to the entire program), and that at each integration phase all call statements that cross the boundaries of previously integrated components are tested. Given hierarchical integration stages with good cohesive partitioning properties, this limits the testing effort to a small fraction of the effort to cover each statement of the system at each integration phase.

Structured testing can be extended to cover the fully general case of incremental integration in a similar manner. The key is to perform design reduction at each integration phase using just the module call nodes that cross component boundaries, yielding component-reduced graphs, and exclude from consideration all modules that do not contain any cross-component calls. Integration tests are derived from the reduced graphs using the techniques of sections 7.4 and 7.5. The complete testing method is to test a basis set of paths through each module at the first phase (which can be either single modules, subsystems, or the entire program, depending on the underlying integration strategy), and then test a basis set of paths through each component-reduced graph at each successive integration phase. As discussed in section 7.5, the most rigorous approach is to execute a complete basis set of component integration tests at each stage. However, for incremental integration, the integration complexity formula may not give the precise number of independent tests. The reason is that the modules with cross-component calls may not be connected in the design structure, so it is not necessarily the case that one path through each module is a result of exercising a path in its caller. However, at most one additional test per module is required, so using the S₁ formula still gives a reasonable approximation to the testing effort at each phase.

Figure 7-7 illustrates the structured testing approach to incremental integration. Modules A and C have been previously integrated, as have modules B and D. It would take three tests to integrate this system in a single phase. However, since the design predicate decision to call module D from module B has been tested in a previous phase, only two additional tests are required to complete the integration testing. Modules B and D are removed from consideration because they do not contain cross-component calls, the component module design complexity of module A is 1, and the component module design complexity of module C is 2.

Figure 7-7. Incremental integration example.