Материал: + An Orchestrated Survey on Automated Software TestCase Generation

142 and 1,246, respectively. In the study conducted by Zhou et al. (2013), they used four numerical programs written in C from GNU Scientific Library with seeded faults. They used two ART algorithms, and hence there were eight comparison scenarios between ART and RT. Their results showed that in one of the eight comparison scenarios, the F-measure of ART was about 107% of the F-measure for RT, and for the remaining seven out of the eight comparison scenarios, the F-measure of ART was between 25% and 75% of the F-measure for RT. Tappenden and Miller (2009) used simulations to compare ART and RT. They observed that “All of the testing methods (eAR, FSCS, RRT, and the Sobol sequence) s-significantly outperformed RT with respect to the block failure pattern.”, “With respect to the strip pattern, [...] ART methods s-significantly outperformed RT for all failure rates.”, and “Point pattern simulation yielded results similar to the strip pattern; ART methods performed slightly better, and not worse than RT, with s-significant e ect sizes ranging from r=0.009 to r=0.030.”. Arcuri and Briand have observed that for one mutant of a program, the F-measures for RT and ART were 72,237 and 56,382, respectively (see Table 4 in (Arcuri and Briand, 2011)). So, there has been a general consensus that ART is better than RT with respect to the F- measure. The superiority of ART over RT with respect to the F-measure is intuitively expected as the concept of even spreading of test cases originates from the objective of hitting the contiguous failure regions using fewer test cases. Furthermore, the F-measure improvement is quite significant and is in no way diminished by any potential challenge to previous experiments’

A recent analytical study (Chen and Merkel, 2008) proves that even if we know the shapes, sizes and orientations of the failure regions, but not their locations, it is impossible to have a strategy that guarantees the detection of a failure with its F- measure being less than half of the F-measure for RT. In other words, 50% of RT’s F-measure is an upper bound of the e ectiveness improvement that we can possibly achieve when we know the sizes, shapes and orientations of the failure regions (in reality, we are not able to know the sizes, shapes and orientations of the failure regions prior to testing). Since ART never uses nor assumes such information, ART shall not have a lower F-measure than the optimal strategy which is designed according to such information. When interpreted with the simulation and experimental results of the F-measures of ART, this theoretical result implies a rather surprising but most welcome conclusion that ART is close to the optimal strategy, and that the upper bound is indeed a tight bound. As shown in the proofs and examples in (Chen and Merkel, 2008), technically speaking, the optimal strategy is to construct a grid of test cases according to the sizes, shapes and orientations of the failure regions. An even spreading of test cases is a lightweight approach to implement an approximation to such a grid, and hence ART can be viewed as a lightweight approach to implementing the optimal strategy. In other words, it seems unlikely that there are other testing techniques which can use significantly fewer test cases than ART to detect the first failure, unless there is access to the information about the locations of the failure regions, which is usually not possible. An immediate conclusion is that future

research shall be focused on either how to use the information of the location of failure-causing input to develop new testing strategies that can outperform ART (for example, see (Zhou et al., 2013)), or how to improve the e ciency of ART by reducing the cost for test case generation (for example, see (Chan et al., 2006a; Chen et al., 2006b)).

As pointed out by Arcuri and Briand (2011), previous empirical studies or simulations only involved failure rates larger

than RT for extremely low failure rates. However, both the proofs of the theoretical analysis (Chen and Merkel, 2008) and the results of a simulation study (Chen et al., 2007) about the impact of the geometry of failure regions show that the fewer the distinct failure regions are, the better performance of F- measure ART has. This implies that ART will have a better F- measure performance than RT at later stages (relatively fewer distinct failure regions and lower failure rates) than at earlier stages (relatively more distinct failure regions and higher failure rates) of software development. As far as we know, all existing ART algorithms tend to achieve increasingly even spreading with more test cases. In other words, lower failure rates are actually favourable scenarios for ART with respect to F- measures. We are not aware of any work showing that at lower failure rates, RT has a lower F-measure than ART. Obviously, it is worthwhile to see more experimental data on this aspect. In summary, there is no challenge to the fact that ART has a significantly lower F-measure than that of RT.

than 10 6, and hence were perhaps not comprehensive enough. Therefore,Manuscriptit is worthwhile to conduct further experiments to verify whether or not ART does still have a lower F-measure

Chen et al. (2006a) have used simulations to compare the P- measure between ART and RT, and have found that ART outperforms RT. Recently, Shahbazi et al. (2012) have proposed an innovative approach to use the concept of Centroidal Voronoi Tessellations to evenly spread random test cases over the input domain and developed RT-RBCVT and RT-RBCVT-Fast methods, which also belong to the ART approach as they evenly spread random test cases over the input domain. A very important result is that their RT-RBCVT-Fast method is of the same order of computational complexity as RT. In the application of their methods, the size of a set of test cases is defined first. In both their simulations, which used various types of failure patterns, and their empirical analysis, which used mutants, the RTRBCVT method consistently demonstrated higher P-measures than RT, as reported that “RBCVT is significantly superior to all approaches for the block pattern in the simulation framework at all failure rates as well as the studied mutants at all test set sizes. Although the magnitude of improvement in testing e ectiveness results is higher for the block pattern compared to the point pattern, the results demonstrate statistically significant improvement in the point pattern”.

In Arcuri and Briand’s empirical analysis using mutants (Arcuri and Briand, 2011), it was reported that ”Although the results in Figure 3 suggest that ART can be better than random testing (the odds ratios are lower than 0.5 in most cases), the results in Figure 4 show that ART is still very unlikely to detect faults. In most of the cases the P-measure is lower than 0.01, i.e., ART would have less than 1% chance of finding fail-

ure”. By definition, the P-measure for RT or ART is a function of the size of the test set. Furthermore, the value of the P-measure for RT or ART will be increased if the size of the test set is increased. As an example for illustration, consider a program with failure rate of 0.0001. On average, RT needs to use 10,000 test cases to detect a failure. In other words, the P-measure for RT using 10,000 test cases will be very close to 1. Thus, if the size of the test set is chosen to be 100,000, then the P-measure for both RT and ART will be even closer to 1. On the other hand, if the size of the test set is chosen to be 10, then obviously the P-measures for RT and ART will be close to 0. Furthermore, for the scenarios of using 100,000 and 10 test cases, the di erences between their P-measures for RT and ART, if any, are likely to be very small. Therefore, when comparing the P-measures of RT and ART, a full range of the sizes of the test set should be used in order to get a comprehensive and meaningful comparison. However, this problem may not occur when RT (or ART) is compared to other testing strategies which require a particular number of test cases for a specific program. Suppose that a program has k paths. For path coverage testing, a set of k test cases is required. In this case, when P-measure is used as the e ectiveness metric to compare RT and path coverage testing, it is not only meaningful but also fair that a random test set of k elements for RT should be compared with a path coverage test set of k elements, irrespectively of the failure rate for the program under test. This specific value of k is not arbitrarily chosen and there is a justification. However, when P-measure is used to compare RT and ART, an immedi-

ate question is what should be the appropriate size of the test set used, simply becauseAcceptedthe size of the test set has significant

impact on the returned values of the P-measure. Hence, the F-measure is more appropriate than the P-measure in the comparison of RT and ART.

Compared to the F-measure, the P-measure has been less often used in evaluating ART. Nevertheless, all studies have consistently shown that ART outperforms RT with respect to the P-measure. This universal observation is consistent with an analytical result that the P-measure of the Proportional Sampling Strategy (PSS) is not lower than that of RT (Chen et al., 2001). PSS is a test case selection strategy for subdomain testing, which allocates a number of test cases to a subdomain in proportion to the subdomain’s size. PSS is in fact an ART algorithm, using a partitioning approach. Thus, it is intuitively appealing to expect the P-measure of other ART algorithms to be not lower than that of RT. Furthermore, it is important to note that PSS has been proved to be a necessary and su cient condition for partition testing to outperform RT with respect to the P-measure. With regard to the E-measure, PSS and RT have been theoretically proved to have the same E-measure (Chen et al., 2001).

In addition to the F-measure and P-measure, the amount of time to taken to detect the first failure (or fault) has been used as a performance metric by Ciupa et al. (2008) in their investigation using real-life faulty programs, and Lin et al. (2009) in their investigation using open source Java programs with seeded faults. Strictly speaking, the measurement of the time to detect the first failure is better interpreted as a cost-e ectiveness met-

16

ric rather than an e ectiveness metric. Ciupa et al. found that ART required an average of 1.6 times the amount of time required by RT to detect the first failure, but Lin et al. found that ART required an average of 0.13 times the amount. The apparently di erent observations are understandable, because this metric depends on the characteristics of the programs, which are di erent in these two studies. Ciupa et al. have proposed using a clustering technique to reduce the distance computation

overheads, with the basic idea being to only compute the distancesManuscriptto the cluster centres, rather than to each of the already executed test cases. Their preliminary study shows “an average

improvement of the time to first fault over ARTOO of 25% at no cost in terms of faults found”. Since the time to detect first failure for ART is 1.6 times that for RT in their study, a 25% improvement is in fact a very encouraging result that justifies more research being conducted in this area.

In summary, both simulations as well as empirical analyses using real-life faulty programs and mutants have consistently shown that ART outperforms RT with respect to the P-measure and the F-measure, but ART may still use less time to detect the first failure than RT, despite the fact that ART requires more computation time for test generation because of the additional task of evenly spreading the test cases across the input domain.

6.4. E ciency

Compared to RT, ART algorithms are expected to use more computation time and memory because of the additional task of evenly spreading the test cases (Chen et al., 2004). As explained above, we will only consider computation time in this section. Obviously, di erent ART algorithms have di erent orders of complexity for the generation of test case, ranging from the highest order of n2, n log n, to n, where n denotes the number of already executed test cases. Intuitively speaking, algorithms with higher orders of complexity for test case generation are expected to have better even spreading of test cases, and hence are expected to have a better fault detection capability. Such an expectation normally occurs but not always. Since di erent methods are used to achieve an even spread of test cases, we have different ART algorithms, each of which has its own strengths and weaknesses, as well as favourable and unfavourable conditions for its application. For example, a conventional implementation of FSCS-ART has n2 complexity. Therefore, it would be inappropriate to apply FSCS-ART to programs with very small failure rates, unless the program execution time and test setup time are considerably larger than the time required by FSCSART to generate a test case.

There exist general techniques that are applicable to most of the ART algorithms to reduce their cost of test case generation. As discussed above, Ciupa et al. (2008) have proposed to use the technique of clustering to reduce the distance computation overheads, and have obtained positive results. Another technique is called mirroring (Chen et al., 2006b). Its basic idea is to divide the input domain into k partitions, of which one partition is referred to as the source partition and the other partitions are referred to as the mirror partitions. ART is applied only on the source partition to generate test cases within it. With

simple mappings, the test cases generated in the source partition are mapped into the mirror partitions to generate new test cases within themselves. For FSCS-ART, its test case generation overheads can be e ectively reduced by a factor of (1=k)2. Another technique is called forgetting (or aging) (Chan et al., 2006a). Instead of using all already executed test cases to determine the next test case, we use only a portion or a constant number of already executed test cases to determine the next test case. If the option of a constant number of already executed test cases is used, the order of complexity for generating the next test case will be independent of n. Generally speaking, when a reduction method for distance computations is applied, the reduction may bring in new kinds of overheads and may be at the expense of the fault detection capability. However, such a deterioration of fault detection capability does not always occur. One instance is observed by Ciupa et al. (2008) in their investigation on the technique of clustering that “an average improvement of the time to first fault over ARTOO of 25% at no cost in terms of faults found”. Apart from Ciupa et al.’s study which involved real-life faulty programs, other investigations into the impact of reduction techniques have used simulations and mutants. Therefore, it is important to have further experiments using real-life faulty programs to investigate the impact of these general reduction techniques on the e ciency of ART.

6.5. Frameworks for Cost E ective Application of ART

After discussing the e ectiveness and e ciency of ART, we

are now ready to discuss how to apply ART in practice. As a reminder, this section onlyAcceptedcompares ART and RT. Therefore,

our objective is to determine how to use ART as a cost-e ective alternate to RT when RT has been chosen as a viable testing method to test a system.

There are two possible application scenarios, one with a fixed number of test cases (equivalently, a limited resource) and the other without such a constraint. For the first scenario, our recommendation is to use Tappenden and Miller’s RT-RBCVT- Fast method, because it has the same order of computational complexity as RT but it has a higher P-measure than RT.

Now, let us consider the other scenario. Since di erent programs may have di erent execution times, di erent test setup times and di erent test case generation times, obviously an ART algorithm may be cost-e ective for one program, but not cost-e ective for another, as compared with RT. Therefore, for a given program, it is a challenging problem to select a cost-e ective ART algorithm, let alone to select the most cost- e ective ART algorithm. Let us explain the di culty by first visiting the problem of selecting a cost-e ective sorting algorithm for a given file. Similar to ART, there are many sorting algorithms which have di erent orders of computation complexity, and favourable and unfavourable conditions for their applications. However, when we are going to do sorting, normally we have some information about the file to be sorted. Such information will help us to choose an appropriate sorting algorithm. For example, if the file is known to be nearly ordered, we would use bubble-sort instead of quick-sort; if the file is known to be random or nearly random, then quick-sort rather

17

than bubble-sort should be used. Similarly, if we know the execution time, test setup time and failure rate of the software under test, we would be able to use the information about test case generation complexity for an ART algorithm to determine whether it is more cost-e ective than RT to test the software. But, in reality, though we may know some information about the execution time and test setup time of the software under test, we do not know its failure rate. In other words, we do not have

su cient information to determine whether an ART algorithm isManuscriptmore cost-e ective than RT for this given software. Then, does it mean that ART is practically useless, as we are not able

to determine whether an ART algorithm is more cost-e ective than RT for the given program? The answer is no. Some potential frameworks for cost-e ective applications of ART are presented as follows.

A simple framework is to successively apply RT-RBCVT- Fast with test sets of sizes n1; n2; n3; ; nk. An estimation of the failure rate should first be made, which is then used to determine the value of n1. An over estimation of the failure rate is recommended. As an example for illustration, if some available information (such as, past testing history and program size) suggests that the failure rate for the software under test is not less than 0.001, then we may assume the estimated failure rate to be 0.01. With a failure rate of 0.01, RT needs to use on average 100 test cases in order to detect failure. Thus, we may set n1 = 100. If RT-RBCVT-Fast cannot find failure with a random set of 100 test cases, then one of the many possible ways is to set n2, n3, and nk such that n2 = 2n1; n3 = 2n2; ; nk = 2nk 1, and successively apply RT-RBCVT-Fast using test sets of sizes n2, n3, and nk.

Another framework can be built upon the technique of adaptive testing. By adaptive testing, it basically means that in the process of software testing, a testing method may be replaced by another testing method in response to some on-line collected feedbacks (Cai, 2002). Suppose we are required to test a program P. Let E denote its average execution time and G(n) denote its generation time for the nth test case. Since the F- measure of ART shall not be less than half of the F-measure of RT (as proved analytically (Chen and Merkel, 2008)), obviously it is only worthwhile to continue ART if G(n) is less than E. Suppose that we have ART-A, ART-B and ART-C whose test case generation complexities are of the orders of n2, n log n, and n, respectively. As a note, normally the higher the order of complexity is, the higher the fault detection e ectiveness an ART algorithm has. Here, we assume ART-A performs better than ART-B which in turn performs better than ART-C, with respect to F-measure or P-measure. We shall start testing with ART-A first until we reach G(n) E. Then, we use ART-B until we

reach a new n0 such that G(n0) E. Then, we use ART-C until we reach a new n00 such that that G(n00) E. By then, we

may apply RT-RBCV-Fast successively with di erent test sets as explained in the immediately preceding paragraph, or use the general reduction techniques to keep the cost of generating a new test case steady (such as, the technique of forgetting using a constant number of already executed test cases in distance computation).

The above sketches of the frameworks are very high level,

but they are conceptually feasible. Obviously, a lot of technical details need to be defined in the actual application. Also, new types of overheads may be introduced. Therefore, the cost- e ectiveness of these proposed frameworks needs to be validated by experimental analysis involving real-life programs.

6.6. Applications of ART and Tools

an even spreading of test cases across the input domain. In fact, the majority of the processes of ensuring an even spreading of test cases are quite simple. Therefore, it is not di cult to build one’s own ART tool on top of a random test case generator. In other words, it should be quite straightforward to plugin ART’s even spreading component into an existing RT tool.

Compared to RT, ART has been applied to fewer real-life programs. However, we expect a growth in the application of ART to real-life programs, because more and more e cient ART algorithms have been emerging. Chen et al. (2004) have applied ART to testing open source numerical analysis programs written in C++, using mutants. Ciupa et al. (2008) have compared RT and ART using real-life faulty versions of objectoriented programs selected from Ei elBase Library. Their experimental results showed that ART used significantly fewer test cases to detect the first failure than RT (0.19 times), but ART used more time to detect the first failure than RT (1.6 times). Also observed is that ART revealed faults that RT did not reveal in the same allocated time. Iqbal et al. (2011) have compared RT, ART and Search-Based Testing using Genetic Algorithms and the (1+1) Evolutionary Algorithm. Their study included a real-life real-time embedded system which was a seismic system. They have observed that ART was the best performer, but “there is a 9% probability of wrongly claiming that ART is better than RT if that is actually not the case” (Iqbal et al., 2011). Hemmati et al. (2010, 2011) have used ART to test a safety monitoring component of a safety-critical con-

have used Evolutionary ART in their cookie collection testing of six open-source web applications. Faults were detected in five out of the six web applications. Their results showed that Evolutionary ART was an e ective testing method. Lin et al. (2009) have used six open source Java software artifacts with manually seeded faults in evaluating their ART method. Five of the six subjects were from Apache common library and the other was Siena.

trol system written in C++Acceptedand a core component of a videoconference system written in C. Tappenden and Miller (2013)

With regard to the automated ART tools, AutoTest (Ciupa et al., 2008) supports ART for object-oriented programs. A very good design feature of AutoTest is to use ARTOO as a plug-in strategy for input generation. With such a feature, other ART algorithms could be easily supported by AutoTest. In the study by Shahbazi et al. (2012), programs were developed to support FSCS-ART, Restricted Random Testing (ART by Exclusion), Evolutionary ART, RBCVT and RBCVT-Fast.12 Iqbal et al. (2011) have developed an automated test framework which can support ART to test real-time embedded systems, and the framework has been found e ective. Lin et al. (2009) have developed the tool ARTGen that supports the testing of Java programs using a divergence-oriented approach to ART. The majority of ART algorithms consist of two processes, namely, a process for random generation of inputs and a process to ensure

12The software is available at URL: http://www.steam.ualberta. ca/main/Papers/RBCVT

18

6.7. Future Challenges and Work

Manuscript1. Majority of the previous ART investigations involved simulations and failure rates greater than 10 6. Therefore, it is

important to have more investigations which will involve lower failure rates using real-life faulty programs or mutants. Empirical analysis is required to validate the conjecture that lower failure rate is a favourable condition for ART with respect to F-measure, as discussed above.

2. As explained above, further research should be focused on reducing the cost of test case generation for ART algorithms in order to enhance their cost-e ectiveness. So far, the investigated reduction techniques include clustering, mirroring and forgetting. With the exception of Ciupa et al.’s preliminary investigation on the technique of clustering, which involved real-life faulty programs, other investigations on the general reduction techniques only involved simulations and mutants. Though Ciupa et al.’s results are very positive for the technique of clustering, the impact of the other reduction techniques should be further analysed using more real-life programs.

3. The proposed framework for how to apply ART using the technique of adaptive testing has been briefly outlined above. The sketches of the framework are very high level but the framework is conceptually feasible. A lot of technical details need to be defined in actual application, such as, how to deal with the already executed test cases after switching from one ART algorithm to another ART algorithm. Obviously, its feasibility needs to be validated by experimental analysis involving real-life programs.

4. Failure patterns provide valuable information to help us to develop new and e ective test case selection strategies. We coined this area as failure-based testing. The domain test strategy proposed by White and Cohen (1980) is not only a fault-based testing strategy as stated by them, but also a failure-based testing technique. It is indeed the first failure-based testing technique. Its target is the domain fault which gives rise to a specific failure pattern in the input domain. The concept of geometry is applied to the resultant failure pattern to design test cases that guarantee to detect the relevant fault. ART is a failure-based testing method using the most primitive information of the contiguity of failure-causing inputs. Since failure patterns also have other information, there is still great potential benefit to be gained from the use of this other information to develop new testing strategies. The search-based testing community has developed many searching techniques, some of which may become, or be adapted to become, new search techniques for failure regions.

6.8. Conclusion on Adaptive Random Testing

All existing investigations have consistently shown that ART outperforms RT with respect to the F-measure and P- measure. These investigations include simulations and experimental analysis using both mutants and real-life faulty programs. The positive results of these simulation and experimental investigations are consistent with the interpretations and results of the theoretical analysis. Though the scope of existing investigations may not be considered su ciently comprehensive (Arcuri and Briand, 2011), the superiority of ART over RT with respect to the F-measure and P-measure is unlikely to be challenged. Nevertheless, more comprehensive experiments on the F-measure and P-measure of RT and ART will still be worthwhile.

Compared to RT, ART has the additional task of evenly spreading the test cases. Therefore, ART will unavoidably consume more computation time and memory than RT. Hence, it is understandable that an ART algorithm is not necessarily more cost-e ective than RT for a given program, despite the fact that it is superior to RT with respect to the F-measure and the P- measure. On the other hand, with respect to the metric of time required to find the first failure or fault, RT is not always superior to ART even though ART incurs more computation time than RT. This is also understandable because the characteristics of the programs under test will a ect the value of this metric. Obviously, the characteristics of the program under test must be considered when determining whether an ART algorithm will

be more cost-e ective than RT.

complexity as RT. Accepted

Since its inception, the ART research has been focused on

the development of new algorithms which would have a lower F-measure. As explained above, a recent analytical result shows that ART is in fact a lightweight approach to implementing the optimal strategy which is essentially equivalent to constructing a grid of test cases according to the sizes, shapes and orientations of the failure regions. An immediate conclusion is that ART has great potential to be a cost-e ective alternate to RT. Attention should then be shifted from the e ectiveness to the e ciency of ART, that is, to the reduction in time and space complexity, in order to make ART a cost-e ective alternate to RT. Conceptually speaking, reduction in the computation and memory overheads are possible but may be at the expense of the degree of even spreading which in turn may a ect the e ectiveness. However, the recently published method of RT-RBCVT- Fast shows that ART can indeed serve as a cost-e ective alternate to RT, because it has the same order of computational

7. Test Data Generation in Search-Based Software Testing

By Mark Harman, Phil McMinn, John Clark and Edmund Burke 13

13Acknowledgements: The authors would like to thank Yue Jia for Figure 4.

19

Search Based Software Testing (SBST) is a branch of Search Based Software Engineering (SBSE), in which optimisation algorithms are used to automate the search for test data that maximises the achievement of test goals, while minimising testing costs. There has been much interest in SBST, leading to several recent surveys. This paper presents some emerging challenges and open problems for the development of this exciting research agenda. These include hybrids of SBST and DSE (Dynamic Symbolic Execution); optimizing to best handle demands of the

Manuscriptoracle; co-evolving tests and software simultaneously; “hyperheuristics” where SBST may be integrated into other aspects

of SBSE, e.g. requirements prioritisation; and optimization of failures for ease of debugging.

7.1. Introduction to Search-Based Testing

As this paper shows, the problem of automatically generating test inputs is hard. For example, even the most basic activities, such as seeking to cover a branch in the code involve reachability questions that are known to be undecidable in general (Weyuker, 1979). The testing community has therefore focused on techniques that seek to identify test sets that cover near optimal sets of branches in reasonable time. Many of these techniques are covered in other sections of this paper.

This section is concerned with the area of Search-Based Software Testing (SBST). SBST is a branch of Search-Based Software Engineering (SBSE) (Harman and Jones, 2001), in which optimisation algorithms are used to automate the search for test data that maximises the achievement of test goals, while minimising testing costs. There has been much interest in SBST, leading to several recent surveys. This section presents some emerging challenges and open problems for the development of this exciting research agenda.

SBST is the process of generating test cases (or often the inputs of test cases) using search-based optimisation algorithms, guided by a fitness function that captures the current test objective. SBST has been applied to a wide variety of testing goals including structural (Harman and McMinn, 2010; McMinn et al., 2012a; Michael et al., 2001; Tonella, 2004), functional (Wegener and Buhler,¨ 2004), non-functional (Wegener and Grochtmann, 1998) and state-based properties (Derderian et al., 2006).

Search-based approaches have been developed to address a wide and diverse range of domains, including testing approaches based on agents (Nguyen et al., 2009), aspects (Harman et al., 2009), interactions (Cohen et al., 2003), integration (Colanzi et al., 2011; Briand et al., 2002), mutation (Harman et al., 2011; Zhan and Clark, 2005), regression (Walcott et al., 2006; Yoo et al., 2009), stress (Grosso et al., 2005) and web applications (Alshahwan and Harman, 2011).

In all approaches to SBST, the primary concern is to define a fitness function (or set of fitness functions) that capture the test objectives. The fitness function is used to guide a search-based optimisation algorithm, which searches the space of test inputs to find those that meet the test objectives. Because any test objective can, in principle, be re-cast as a fitness function, the approach is highly generic and therefore widely applicable (as the foregoing list of testing applications demonstrates). There are many di erent search-based optimisation algorithms to choose