KDFC-ART: a KD-tree approach to enhancing Fixed-size-Candidate-set Adaptive Random Testing
KDFC-ART: a KD-tree approach to enhancing Fixed-size-Candidate-set Adaptive Random Testing
复制标题
KDFC-ART：增强固定大小候选集自适应随机测试的 KD 树方法
DOI：
10.1109/tr.2019.2892230
复制
发表时间：
2019-03
影响因子：
5.9
通讯作者：
Tsong Yueh Chen
中科院分区：
文献类型：
--
作者：
Chengying Mao;Xuzheng Zhan;T.H.Tse;Tsong Yueh Chen
自适应随机测试（ART）是随机测试的增强版本，通过将测试用例均匀地分布在输入空间上来提高程序故障检测的有效性。然而，可能引起繁重的计算。本文提出了三种基于k维树结构的固定大小候选集ART（FSCS ART）增强算法。第一个算法Naive-KDFC通过以循环方式连续地关于每个维度分裂输入空间来构造KD树。第二种算法SemiBal-KDFC通过根据每个维度的分布来优先考虑拆分，从而提高了KD树的平衡性。第三种算法LimBal-KDFC为了控制回溯过程中遍历的节点数，引入了一个节点数的上限。仿真和实验研究已经进行了调查的效率和有效性的三种算法。实验结果表明，这些算法显着减少了计算时间的原始FSCS-ART的低维和高维的情况下，低故障率。当维数不超过8时，SemiBal-KDFC的效率优于Naive-KDFC，而LimBal-KDFC的效率最高。虽然有限的回溯只会导致一个近似的最近邻LimBal-KDFC，其故障检测的有效性，事实上，在高维输入空间比FSCS-ART，并没有显着恶化在低维空间。
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 the 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.
登录
查看更多内容
DOI：
10.1007/978-3-540-30502-6_23
发表时间：
2004-12
期刊：
--
影响因子：
--
作者：
Tsong Yueh Chen;H. Leung;I. K. Mak
通讯作者：
Tsong Yueh Chen;H. Leung;I. K. Mak
DOI：
10.1145/1292414.1292424
发表时间：
2007-11
期刊：
--
影响因子：
--
作者：
R. Gerlich;R. Gerlich;T. Boll
通讯作者：
R. Gerlich;R. Gerlich;T. Boll
影响因子：
1.9
作者：
F. Wilcoxon
通讯作者：
F. Wilcoxon
影响因子：
7.4
作者：
L. White;Edward I. Cohen
通讯作者：
L. White;Edward I. Cohen
DOI：
10.1109/wst.1988.5376
发表时间：
1988-07
期刊：
[1988] Proceedings. Second Workshop on Software Testing, Verification, and Analysis
影响因子：
--
作者：
R. Hamlet;R. Taylor
通讯作者：
R. Hamlet;R. Taylor