Enhancing mirror adaptive random testing through dynamic partitioning

ContextAdaptive random testing (ART), originally proposed as an enhancement of random testing, is often criticized for the high computation overhead of many ART algorithms. Mirror ART (MART) is a novel approach that can be generally applied to improve the efficiency of various ART algorithms based on the combination of “divide-and-conquer” and “heuristic” strategies.ObjectiveThe computation overhead of the existing MART methods is actually on the same order of magnitude as that of the original ART algorithms. In this paper, we aim to further decrease the order of computation overhead for MART.MethodWe conjecture that the mirroring scheme in MART should be dynamic instead of static to deliver a higher efficiency. We thus propose a new approach, namely dynamic mirror ART (DMART), which incrementally partitions the input domain and adopts new mirror functions.ResultsOur simulations demonstrate that the new DMART approach delivers comparable failure-detection effectiveness as the original MART and ART algorithms while having much lower computation overhead. The experimental studies further show that the new approach also delivers a better and more reliable performance on programs with failure-unrelated parameters.ConclusionIn general, DMART is much more cost-effective than MART. Since its mirroring scheme is independent of concrete ART algorithms, DMART can be generally applied to improve the cost-effectiveness of various ART algorithms.     

Adaptive Random Testing: The ART of test case diversity

Random testing is not only a useful testing technique in itself, but also plays a core role in many other testing methods. Hence, any significant improvement to random testing has an impact throughout the software testing community. Recently, Adaptive Random Testing (ART) was proposed as an effective alternative to random testing. This paper presents a synthesis of the most important research results related to ART. In the course of our research and through further reflection, we have realised how the techniques and concepts of ART can be applied in a much broader context, which we present here. We believe such ideas can be applied in a variety of areas of software testing, and even beyond software testing. Amongst these ideas, we particularly note the fundamental role of diversity in test case selection strategies. We hope this paper serves to provoke further discussions and investigations of these ideas.     

Adaptive random testing based on distribution metrics

Random testing (RT) is a fundamental software testing technique. Adaptive random testing (ART), an enhancement of RT, generally uses fewer test cases than RT to detect the first failure. ART generates test cases in a random manner, together with additional test case selection criteria to enforce that the executed test cases are evenly spread over the input domain. Some studies have been conducted to measure how evenly an ART algorithm can spread its test cases with respect to some distribution metrics. These studies observed that there exists a correlation between the failure detection capability and the evenness of test case distribution. Inspired by this observation, we aim to study whether failure detection capability of ART can be enhanced by using distribution metrics as criteria for the test case selection process. Our simulations and empirical results show that the newly proposed algorithms not only improve the evenness of test case distribution, but also enhance the failure detection capability of ART.     

失效区域紧致性对适应性随机测试的性能影响

适应性随机测试是一种增强的随机测试方法.已有的研究发现:失效区域的紧致程度是影响适应性随机测试性能的几个基本因素之一,并仅在失效区域为长方形的情形下验证了上述猜想.采用仿真实验的方法进一步研究失效区域的紧致程度与适应性随机测试的性能之间的精确关系.研究了几种基本规则形状的和不规则形状的失效区域.实验结果表明:适应性随机测试方法的性能随着失效区域的紧致程度的增强而提高.该研究进一步地揭示了适应性随机测试优于随机测试的基本条件.     

Distributing test cases more evenly in adaptive random testing

Adaptive random testing (ART) has recently been proposed to enhance the failure-detection capability of random testing. In ART, test cases are not only randomly generated, but also evenly spread over the input domain. Various ART algorithms have been developed to evenly spread test cases in different ways. Previous studies have shown that some ART algorithms prefer to select test cases from the edge part of the input domain rather than from the centre part, that is, inputs do not have equal chance to be selected as test cases. Since we do not know where the failure-causing inputs are prior to testing, it is not desirable for inputs to have different chances of being selected as test cases. Therefore, in this paper, we investigate how to enhance some ART algorithms by offsetting the edge preference, and propose a new family of ART algorithms. A series of simulations have been conducted and it is shown that these new algorithms not only select test cases more evenly, but also have better failure detection capabilities.     

Enhancing adaptive random testing for programs with high dimensional input domains or failure-unrelated parameters

Adaptive random testing (ART), an enhancement of random testing (RT), aims to both randomly select and evenly spread test cases. Recently, it has been observed that the effectiveness of some ART algorithms may deteriorate as the number of program input parameters (dimensionality) increases. In this article, we analyse various problems of one ART algorithm, namely fixed-sized-candidate-set ART (FSCS-ART), in the high dimensional input domain setting, and study how FSCS-ART can be further enhanced to address these problems. We propose to add a filtering process of inputs into FSCS-ART to achieve a more even-spread of test cases and better failure detection effectiveness in high dimensional space. Our study shows that this solution, termed as FSCS-ART-FE, can improve FSCS-ART not only in the case of high dimensional space, but also in the case of having failure-unrelated parameters. Both cases are common in real life programs. Therefore, we recommend using FSCS-ART-FE instead of FSCS-ART whenever possible. Other ART algorithms may face similar problems as FSCS-ART; hence our study also brings insight into the improvement of other ART algorithms in high dimensional space.

一种针对高维输入域的适应性随机测试改进性算法

适应性随机测试ART能够保证测试用例在输入域中更加均匀地分布,从而在失效检测能力上明显强于基本的随机测试,其中,固定候选集规模的ART算法 FSCS ART因具备较好的揭错能力而被广泛采用。然而随着输入域维度的升高,FSCS ART的失效检测效果显著降低。针对该问题,在从候选集中选择正式用例时综合考虑两种距离：候选点与已测用例之间的距离和它与中心点之间的距离,这样,输入域边缘的候选点的优先级得以降低,有效地克服了FSCS ART趋向于边缘的弊端。实验结果表明,改进后的算法针对高维输入域表现出更强的失效检测能力。     

3n镜像适应性随机测试算法

针对适应性随机测试中的边缘效应问题,借鉴镜像适应性随机测试(MART)的基本思想,在引入镜像距离的基础上,提出3n MART算法,通过改变候选用例与成功用例之间的距离判断策略,使其产生的用例在输入域中更均匀地分布。仿真实验结果证明,该算法可以较好地解决边缘效应问题,相比基于距离的适应性随机测试算法与MART算法,失效发现效率更高。     

一种改进的软件自适应随机测试策略

针对自适应随机测试(ART)存在的高维和距离度量问题,提出一种改进的软件自适应随机测试策略。分析ART的局限性,扩展ART的前提假设,基于测试用例特征相似性度量选择最佳的测试用例。实验结果表明,与传统随机测试策略相比,改进策略能更多地触发软件失效,测试效果更优。     

基于约束的软件失效域识别与特征分析

随机测试是实践中广泛采用的一种黑盒测试方法.近年来提出的适应性随机测试方法改进了随机测试的不足,仿真实验结果表明,改进效果取决于软件失效域的特征.提出以测试约束刻画软件失效域在输入域上的分布,探讨了基于现有的程序分析技术构造测试约束的过程,讨论了基于测试约束的软件失效域的特征分析方法.以一个实例软件验证所提出的测试约束构造过程及其软件失效域特征分析方法.测试约束揭示了软件故障的触发与传播的内在机制,基于测试约束的软件失效域的特征分析方法有助于改进测试用例的设计质量以及评价适应性随机测试方法的适用性.