KD-RRT: Restricted Random Testing based on K-Dimensional Tree

Adaptive random testing (ART) improves the failure-detection capability of Random Testing (RT) by making the generated test cases as evenly distributed as possible within the input domain. Restricted Random Testing (RRT) is one of the most classical ART algorithms, which defines an exclusion region around each executed test case, and generates subsequent test cases from outside all the exclusion regions. RRT requires calculating the distances to the executed test cases sequentially for each candidate test case. When the number of executed test cases is large, the time overhead will be very high. In this paper, we propose a method to reduce the time overhead of RRT by using a K-Dimensional Tree (KD-Tree), called KD-RRT. KD-RRT only calculates the distances of executed test cases that are close to the candidate test cases, and ignores the test cases that are farther away. Thus, KD-RRT cuts down the number of distance calculations and reduces the time overhead of RRT. To verify the effectiveness and efficiency of KD-RRT, a series of simulations and empirical studies are designed in this paper. The data results show that KD-RRT ensures the effectiveness of RRT and significantly reduces the time overhead of RRT.