POPULATION SIZE

The goal of the current effort is to find all code blocks within the MUT by producing stable sub-populations of test cases traversing as many paths as possible through the module under test. The paths are analogous to the phenotype of an organism in a natural system. Each sub-population forms a niche. The test cases occupying a niche all exhibit the same phenotype, forming a species. In future work, speciation could be promoted using a marriage restriction operator.

It was mentioned earlier that the number of distinct paths through a module can quickly become unmanageable, especially if loops are present within the MUT. Though this issue did not arise while testing trityp-easy (it does not contain any loops), a method of handling paths with loops is needed. The easiest method might be to ignore multiple iterations through the loop, counting the nodes within the loop only once. However, one significant issue remains after this discussion of forming stable sub-populations. How large should these sub-populations be so that they exhibit sufficient genetic diversity and are insensitive to periodically losing a few members?

A multiplier of some measurable software attribute quickly comes to mind. The number of distinct paths through a software module (as noted earlier) can be infinite. Other choices are the number of code blocks (nodes in the control graph) and complexity. Here, McCabe’s [5] cyclometric complexity metric was chosen for use as a multiplier. Complexity is a good choice if the proposed utility’s parser were able to reduce and instrument complex logic expressions. In the current effort, population size was varied from four to fourteen times trityp-easy’s cyclometric complexity in an effort to find a suitable multiplier value. Population size is the product of complexity and the population multiplier.

RESULTS

The IPP and the LBTPB fitness algorithms were compared side by side in multiple runs of the Simple Genetic Algorithm (SGA) developed by David Goldberg [6]. Population size was varied as a fixed multiple of the test module’s cyclometric complexity. The test module was the“trityp-easy”program referenced in Watkins [3]. Trityp-easy has a cyclometric complexity of 21 and contains eighteen code blocks. Each run of the GA was initialized with a unique random seed and lasted for 50 generations. Each data point referenced here represents an ensemble average of 200 runs.

Table 4.3 shows the generation number when the two fitness algorithms converged to the eighteen possible code blocks in the trityp-easy program. Both algorithms had difficulty finding all eighteen for low population multipliers. The LBTPB fitness algorithm converged by generation 33 with a multiplier of 8. Increasing the multiplier value advanced the point of convergence. The IPP fitness algorithm was much slower to converge than the LBTPB algorithm, generally converging twenty generations later. Differences between the two fitness algorithms were less pronounced at larger multiplier values. This is because large populations do not adequately challenge the GA. Large initial populations usually contain enough diversity to allow the GA to rapidly traverse all eighteen nodes. However, larger population sizes do consume additional computational resources.

Figure 4.4 depicts the convergence of the LBTPB and IPP fitness algorithms when using a population multiplier of 10. The LBTPB algorithm (solid line in Figure 4.4) gave a bonus of 5 fitness points to data sets which traversed a node with at least one untraversed child node.

By providing a bonus, the GA encourages the formation of test data sets for untraversed code blocks. These highly fit individuals cross with other highly fit individuals in the hope of generating test data which are capable of traversing new sections of the module under test. This is what helps the GA converge earlier as shown in Table 4.3 above.

Lower bonus values were less effective, while larger bonus values tended to hinder convergence. The GA is forced to continually rediscover and lose blocks of code when individuals with extremely large fitness values monopolize reproduction at the expense of others.

Figure 4.4 shows convergence of the IPP and LBTPB fitness algorithms. Convergence of the IPP fitness algorithm takes much longer than the LBTPB algorithm. Convergence is shown in greater detail in Figure 4.5, which presents results for the two algorithms with population multipliers of 10 and 12.

Figure 4.4  Convergence of LBTPB and IPP fitness algorithms to optimal (18).

Figure 4.5 shows that detection of the remaining code blocks by the two fitness functions stalls momentarily near the optimal value of 18. The LBTPB algorithm clearly performs better than the IPP. Since each trace is actually an average of 200 runs, the plateaus seen near the top indicate that some of the runs have the GA searching for the last few remaining undiscovered sections of the program. This is to be expected from the IPP algorithm because it does not distinguish between unique or common blocks of code when calculating fitness. That these plateaus occurs for the LBTPB algorithm is then somewhat perplexing until we remember that the LBTPB fitness algorithm bases fitness on unique terminal blocks of code. As mentioned earlier, the LBTPB fitness algorithm is really just a special case of a fitness algorithm which rewards traversal of unique nodes found along the entire path through the control graph. This more generic form of the LBTPB fitness algorithm is currently under development.

Figure 4.5  Block coverage near the optimum.