Mirror adaptive random testing

Recently, adaptive random testing (ART) has been introduced to improve the fault-detection effectiveness of random testing for non-point types of failure patterns. However, ART requires additional computations to ensure an even spread of test cases, which may render ART less cost-effective than random testing. This paper presents a new technique, namely mirror ART, to reduce these computations. It is an integration of the technique of mirroring and ART. Our simulation results clearly show that mirror ART does improve the cost-effectiveness of ART.     

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.     

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.     

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.

An experimental study of adaptive testing for software reliability assessment

Adaptive testing is a new form of software testing that is based on the feedback and adaptive control principle and can be treated as the software testing counterpart of adaptive control. Our previous work has shown that adaptive testing can be formulated and guided in theory to minimize the variance of an unbiased software reliability estimator and to achieve optimal software reliability assessment. In this paper, we present an experimental study of adaptive testing for software reliability assessment, where the adaptive testing strategy, the random testing strategy and the operational profile based testing strategy were applied to the Space program in four experiments. The experimental results demonstrate that the adaptive testing strategy can really work in practice and may noticeably outperform the other two. Therefore, the adaptive testing strategy can serve as a preferable alternative to the random testing strategy and the operational profile based testing strategy if high confidence in the reliability estimates is required or the real-world operational profile of the software under test cannot be accurately identified.     

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.     

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

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

Comparison of adaptive random testing and random testing under various testing and debugging scenarios

Adaptive random testing is an enhancement of random testing. Previous studies on adaptive random testing assumed that once a failure is detected, testing is terminated and debugging is conducted immediately. It has been shown that adaptive random testing normally uses fewer test cases than random testing for detecting the first software failure. However, under many practical situations, testing should not be withheld after the detection of a failure. Thus, it is important to investigate the effectiveness with respect to the detection of multiple failures. In this paper, we compare adaptive random testing and random testing under various scenarios and examine whether adaptive random testing is still able to use fewer test cases than random testing to detect multiple software failures. Our study delivers some interesting results and highlights a number of promising research projects. Copyright © 2011 John Wiley & Sons, Ltd.     

基于失效聚集度改进自适应随机测试算法

对于现有的自适应随机测试(ART)算法针对点状失效模式普遍存在有效性和效率均比随机测试(RT)差的问题,提出一种基于失效聚集度的自适应随机测试(CLART)算法,对传统的ART——固定候选集(FSCS)、区域排除随机测试(RRT)等算法进行改进。首先,根据被测程序的输入域估计主失效聚集度,确定局部搜索区域;然后,在区域内使用传统ART算法生成若干测试用例(TC)进行测试;若未发现错误,重新选择局部区域生成TC;重复这一过程直至发现错误。仿真实验显示在点状失效模式和块状失效模式下CLART算法的有效性比FSCS算法提高约20%,效率比FSCS算法提高约60%。实验结果表明CLART算法利用多个局部区域依次搜索可以快速锁定引发失效输入分布密集高的失效区域,从而提高测试的有效性和效率。     

随机测试用例的优化技术研究

提出了一种基于粗糙集的不完备测试数据填补方法。该方法首先利用粗糙集中下近似集的性质对随机生成的测试数据进行填补,然后根据属性数据的取值概率函数求出的结果进行二次填补,从而完成对不完备测试数据的完备化处理,生成最优测试用例。采用本方法可以较好地反映待测系统所蕴含的规则,且可以避免测试数据的冲突。     

Optimal and adaptive testing for software reliability assessment

Optimal software testing is concerned with how to test software such that the underlying testing goal is achieved in an optimal manner. Our previous work shows that the optimal testing problem for software reliability growth can be treated as closed-loop or feedback control problem, where the software under test serves as a controlled object and the software testing strategy serves as the corresponding controller. More specifically, the software under test is modeled as controlled Markov chains (CMCs) and the control theory of Markov chains is used to synthesize the required optimal testing strategy. In this paper, we show that software reliability assessment can be treated as a feedback control problem and the CMC approach is also applicable to dealing with the optimal testing problem for software reliability assessment. In this problem, the code of the software under test is frozen and the software testing process is optimized in the sense that the variance of the software reliability estimator is minimized. An adaptive software testing strategy is proposed that uses the testing data collected on-line to estimate the required parameters and selects next test cases. Simulation results show that the proposed adaptive software testing strategy can really work in the sense that the resulting variance of the software reliability estimate is much smaller than that resulting from the random testing strategies. The work presented in this paper is a contribution to the new area of software cybernetics that explores the interplay between software and control.     

A uniform random test data generator for path testing

Path-oriented Random Testing (PRT) aims at generating a uniformly spread out sequence of random test data that execute a single control flow path within a program. The main challenge of PRT lies in its ability to build efficiently such a test suite in order to minimize the number of rejects (test data that execute another control flow path). We address this problem with an original divide-and-conquer approach based on constraint reasoning over finite domains, a well-recognized Constraint Programming technique. Our approach first derives path conditions by using backward symbolic execution and computes a tight over-approximation of their associated subdomain by using constraint propagation and constraint refutation. Second, a uniform random test data generator is extracted from this approximated subdomain. We implemented this approach and got experimental results that show the practical benefits of PRT based on constraint reasoning. On average, we got a two-order magnitude CPU time improvement over standard Random Testing on a set of paths extracted from classical benchmark programs.     

基于概率统计的测试用例生成技术研究

软件可靠性测试是软件工程中的一个新的研究领域。为了缩短软件测试周期,测试用例的生成是关键,提出将测试用例的生成问题转化为一个数学问题。通过实例证明,这种测试技术具有一定实用性和有效性。     

一种优化软件可靠性测试费用的模型研究

软件复用是提高软件开发效率和改善软件质量的一项重要技术。把领域工程中可复用思想应用到测试用例的复用中,提出了测试用例的复用技术模型。通过实例说明,该模型能提高测试的可靠性以及测试效率,具有可行性。     

一种软件可靠性测试模型研究

在马尔可夫链模型的基础上,将测试问题转化为一个数学问题。通过建立软件的使用链,根据使用链进行序列抽样,产生测试用例,将软件测试结果的分析问题转化为一个经典概率问题。运用实例证明,这种技术具有一定的实用性和有效性。     

A semantic approach for automated test oracle generation

This paper presents the design, implementation, and applications of a software testing tool, TAO, which allows users to specify and generate test cases and oracles in a declarative way. Extended from its previous grammar-based test generation tool, TAO provides a declarative notation for defining denotational semantics on each productive grammar rule, such that when a test case is generated, its expected semantics will be evaluated automatically as well, serving as its test oracle. TAO further provides a simple tagging mechanism to embed oracles into test cases for bridging the automation between test case generation and software testing. Two practical case studies are used to illustrate how automated oracle generation can be effectively integrated with grammar-based test generation in different testing scenarios: locating fault-inducing input patterns on Java applications; and Selenium-based automated web testing.