On even spread of test cases in adaptive random testing

Random testing (RT) is a basic and simple software testing technique. However, it is controversial whether RT is an effective method to detect software failures. Based on the common observation that inputs revealing software failures tend to cluster into contiguous regions, adaptive random testing (ART) has been proposed to enhance the failure-detection capability of RT. The basic intuition of ART is to evenly spread random test cases over the whole input domain. This thesis investigates a number of topics about such an “even spread” intuition. It has been generally believed that how evenly an ART algorithm spreads test cases has an impact on how effectively it detects software failures, and an even distribution of test cases brings a good failure-detection capability. This thesis investigates some existing ART algorithms, and proposes several families of new ART algorithms. Some simulations are conducted and the experimental results show that these new algorithms significantly enhance the failure-detection capability of ART. Test case distributions of these new ART algorithms are also examined, and it is observed that there is a strong correlation between the evenness of test case distribution and the failure-detection capability of an ART algorithm. All previous studies have used the failure-detection capability to measure the effectiveness of ART. This thesis proposes two new measurements to evaluate the performance of ART, which are also correlated to the even spread of test cases. One measurement is the coverage achieved by ART. A series of experiments are conducted in this thesis, and it is shown that test cases selected by ART can cover the program under test more thoroughly than those generated by RT. It is further observed that the more evenly test cases are spread, the higher coverage an ART algorithm can achieve. The other measurement proposed in this thesis is the mutant-killing capability of ART. Mutants refer to a set of fault-seeded programs derived from a basic program, and killing a mutant means detecting a failure in the mutant. Experimental results show that ART generally kills more mutants than pure RT, and the mutant-killing capability of ART becomes better with the improvement of the even spread of test cases. In summary, this thesis significantly contributes to the research on ART, especially to the areas related to the basic “even spread” intuition of ART.