Classification and improvements of Adaptive Random Testing methods

Adaptive Random Testing (ART) is an effective enhancement of RT, which is based on the observations that failure-causing inputs are normally clustered in one or a few contiguous regions in the input domain. Hence, it has been proposed that test case generation should refer to the locations of successful test cases (those that have been executed but not revealed a failure) to achieve an even spread of test cases throughout the input domain. Recently, several ART methods (algorithms) have been proposed, which have their own advantages and disadvantages. Since no proper classification of existing ART methods in previous studies, the relationships among ART methods were unclear. These are the main focuses of this thesis. Firstly, this thesis examines existing ART methods and establishes a taxonomy for them, which is a framework for further studies of ART methods. Existing ART methods are classified into 2 categories based on different interpretations of the basis of ART. They are 'far apart' ART methods and Proportional Sampling Strategy (PSS) ART methods. Based on this classification, characteristics for each category of ART methods can be summarized; improvements can be proposed for each category of ART methods rather than individual methods; new ART methods can also be inspired. Secondly, this thesis focuses on the shortcomings of these ART methods. For 'far apart' ART methods, two major shortcomings are extensive computational overhead and boundary effect (test cases prefer to be near the boundary of the input domain). For PSS ART methods, a common problem is that test cases still have chances to be clustered together, which has adverse impact on the fault-detection capability. This thesis investigates the reasons behind and proposes improvements of the original methods. Finally, with regard to the practicality of ART methods in high dimensional input domains, this thesis proposes a new ART method, ART by balancing, based on an distinctive interpretation of an even spread of test cases, which requires that the centroid of test cases in a partition should be close to the centroid of that partition. This method has a good fault-detection capability, especially in high dimensional input domains.