|IEEE Transactions on Reliability (2019). doi: 10.1109/TR.2019.2892230.|
Chengying Mao 2 , Xuzheng Zhan 2 , T.H. Tse 3 , and Tsong Yueh Chen 4
[paper from IEEE Xplore | technical report TR-2019-01]
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
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.
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
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.
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.
|EVERY VISITOR COUNTS:|