Adaptive random testing (ART) was developed as an enhanced version of random testing to increase the effectiveness of detecting failures in programs by spreading the test cases evenly over the input space. However, heavy computation may be incurred. In this paper, three enhanced algorithms for fixed-size-candidate-set ART (FSCS-ART) are proposed based on the k-dimensional tree (KD-tree) structure. The first algorithm Naive-KDFC constructs a KD-tree by splitting the input space with respect to every dimension successively in a round-robin fashion. The second algorithm SemiBal-KDFC improves the balance of the KD-tree by prioritizing the splitting according to the spread in each dimension. In order to control the number of traversed nodes in backtracking, the third algorithm LimBal-KDFC introduces an upper bound for the nodes involved. Simulation and empirical studies have been conducted to investigate the efficiency and effectiveness of the three algorithms. The experimental results show that these algorithms significantly reduce the computation time of the original FSCS-ART for low dimensions and for the case of high dimensions with low failure rates. The efficiency of SemiBal-KDFC is better than that of Naive-KDFC when the dimension is no more than 8, but LimBal-KDFC is the most efficient of all three. Although limited backtracking leads only to an approximate nearest neighbor in LimBal-KDFC, its failure-detection effectiveness is, in fact, better than FSCS-ART in high-dimensional input spaces and has no significant deterioration in low-dimensional spaces. Index Terms Adaptive random testing, KD-tree, test case generation, software testing, computation time, efficiency, effectiveness.

1. This work was supported in part by the National Natural Science Foundation of China (Grant Nos. 61462030 and 61762040), the Natural Science Foundation of the Jiangxi Province (Grant Nos. 20162BCB23036 and 20171ACB21031), and the Science Foundation of the Jiangxi Educational Committee (Grant No. GJJ150465). 2. School of Software and Communication Engineering, Jiangxi University of Finance and Economics, Nanchang 330013, China. 3. (Corresponding author.) Department of Computer Science, The University of Hong Kong, Pokfulam, Hong Kong. Email: 4. Department of Computer Science and Software Engineering, Swinburne University of Technology, John Street, Hawthorn, VIC 3122, Australia.

EVERY VISITOR COUNTS: