Enhancing the efficiency of adaptive random testing through partitioning and collaboration

Abstract

One of the prime processes in the engineering of test harnesses is test case selection. Random Testing (RT) is straightforward and low cost, but there has been concern on its failure-detection capability. Empirical studies have shown that failure-causing inputs tend to have contiguous failure regions, and hence an even spreading of test cases across the input domain is important. Adaptive Random Testing (ART) is introduced to realize an even spreading distribution of test cases across the input domain by taking into account previously executed test cases before generating the next test case. However, the computational complexity of ART algorithms may be quadratic or higher, so that efficiency is an issue especially when a large number of previously executed test cases involved. Some efficiency improvement techniques are developed to overcome this hurdle, empirical studies show that these efficiency improvement techniques have strength and weakness. In accordance with above motivation, this thesis proposes two efficiency improvement techniques, namely ART by Divide and Conquer (DC) and ART by Collaborative Divide and Conquer (CDC), to tackle the efficiency issue of ART. ART by DC makes good use of recursive partitioning intuition to decompose the large problem into several smaller sub-problems when number of previously executed test cases reached to a certain ceiling for limiting the growth of computational operation. Moreover, recursive partitioning intuition ensures equal-number-equal-size characteristic to achieve even spreading outcome across sub-domains. Experimental results show that ART by DC successfully reduces the computational complexity of traditional ART algorithms from quadratic or higher order to linear order, as well as preserves the effectiveness performance. ART by CDC is an enhanced version of ART by DC. It makes better use of the collaboration idea to share the historical knowledge of previously executed test cases to neighboring input sub-domains, in order to eliminate the virtual boundary effect created by ART by DC. The results in evaluation exercises demonstrate that ART by CDC inherits the good characteristics from ART by DC to reduce the computational complexity of ART algorithms to linear order successfully, and provides better effectiveness performance than basic ART algorithms in block pattern of simulation framework and some faulty programs in real-life environment. Last but not least, this thesis further proposes a new and innovative density-based ART approach, namely ART by Restrictive Partitioning (RP). It utilizes an additional restrictive grid layer on top of the fundamental layer to provide guidance and checking distribution of test cases generation, in order to enforce equal-number-equal-size characterizes across two layers to achieve even spreading objective. The experimental results show that ART by RP is able to dilute the impact of effectiveness performance from dimensionality of the input domain, and further demonstrate that ART by RP is capable to provide linear order computational complexity, as well as acceptable effectiveness performance especially in high-dimensional cases. (464 words)