基于冗余测试用例的最小测试用例集生成方法

提出一种最小测试用例集的生成方法。保留在某个测试标准下冗余,但在其他测试标准下不冗余的测试用例,即在测试用例集简化期间通过有选择性地保留测试用例来生成一个测试用例集。与已有方法相比,该方法能在不影响测试组大小范围的情况下有效提高错误检测效率。     

Regression testing minimization,selection and prioritization: a survey

Regression testing is a testing activity that is performed to provide confidence that changes do not harm the existing behaviour of the software. Test suites tend to grow in size as software evolves, often making it too costly to execute entire test suites. A number of different approaches have been studied to maximize the value of the accrued test suite: minimization, selection and prioritization. Test suite minimization seeks to eliminate redundant test cases in order to reduce the number of tests to run. Test case selection seeks to identify the test cases that are relevant to some set of recent changes. Test case prioritization seeks to order test cases in such a way that early fault detection is maximized. This paper surveys each area of minimization, selection and prioritization technique and discusses open problems and potential directions for future research. Copyright © 2010 John Wiley & Sons, Ltd.     

Test suite reduction methods that decrease regression testing costs by identifying irreplaceable tests

ContextIn software development and maintenance, a software system may frequently be updated to meet rapidly changing user requirements. New test cases will be designed to ensure the correctness of new or modified functions, thus gradually increasing the test suite’s size. Test suite reduction techniques aim to decrease the cost of regression testing by removing the redundant test cases from the test suite and then obtaining a representative set of test cases that still yield a high level of code coverage.ObjectiveMost of the existing reduction algorithms focus on decreasing the test suite’s size. Yet, the differences in execution costs among test cases are usually significant and it may take a lot of execution time to run a test suite consisting of a few long-running test cases. This paper presents and empirically evaluates cost-aware algorithms that can produce the representative sets with lower execution costs.MethodWe first use a cost-aware test case metric, called Irreplaceability, and its enhanced version, called EIrreplaceability, to evaluate the possibility that each test case can be replaced by others during test suite reduction. Furthermore, we construct a cost-aware framework that incorporates the concept of test irreplaceability into some well-known test suite reduction algorithms.ResultsThe effectiveness of the cost-aware framework is evaluated via the subject programs and test suites collected from the Software-artifact Infrastructure Repository — frequently chosen benchmarks for experimentally evaluating test suite reduction methods. The empirical results reveal that the presented algorithms produce representative sets that normally incur a low cost to yield a high level of test coverage.ConclusionThe presented techniques indeed enhance the capability of the traditional reduction algorithms to reduce the execution cost of a test suite. Especially for the additional Greedy algorithm, the presented techniques decrease the costs of the representative sets by 8.10–46.57%.     

Analysis of test suite reduction with enhanced tie-breaking techniques

Test suite minimization techniques try to remove redundant test cases of a test suite. However, reducing the size of a test suite might reduce its ability to reveal faults. In this paper, we present a novel approach for test suite reduction that uses an additional testing criterion to break the ties in the minimization process. We integrated the proposed approach with two existing algorithms and conducted experiments for evaluation. The experiment results show that our approach can improve the fault detection effectiveness of reduced suites with a negligible increase in the size of the suites. Besides, under specific conditions, the proposed approach can also accelerate the process of minimization.     

测试用例集约简问题研究及其进展

测试用例集约简问题是软件测试中的关键问题之一,其目的是使用尽可能少的测试用例充分满足给定的测试目标,从而提高测试效率、降低测试成本。在简要介绍了测试用例集约简问题基本概念的基础上,总结了求解该问题的几种主要方法,分析比较了这些方法的效率和特性。随后探讨了与测试用例集约简问题强相关的测试用例集错误检测效率的问题,并研究了测试用例优先级技术。最后指出了测试用例集约简问题的下一步研究方向。     

Empirical studies of a safe regression test selection technique

Regression testing is an expensive testing procedure utilized to validate modified software. Regression test selection techniques attempt to reduce the cost of regression testing by selecting a subset of a program's existing test suite. Safe regression test selection techniques select subsets that, under certain well-defined conditions, exclude no tests (from the original test suite) that if executed would reveal faults in the modified software. Many regression test selection techniques, including several safe techniques, have been proposed, but few have been subjected to empirical validation. This paper reports empirical studies on a particular safe regression test selection technique, in which the technique is compared to the alternative regression testing strategy of running all tests. The results indicate that safe regression test selection can be cost-effective, but that its costs and benefits vary widely based on a number of factors. In particular, test suite design can significantly affect the effectiveness of test selection, and coverage-based test suites may provide test selection results superior to those provided by test suites that are not coverage-based     

Analysing the effectiveness of rule-coverage as a reduction criterion for test suites of grammar-based software

The term grammar-based software describes software whose input can be specified by a context-free grammar. This grammar may occur explicitly in the software, in the form of an input specification to a parser generator, or implicitly, in the form of a hand-written parser. Grammar-based software includes not only programming language compilers, but also tools for program analysis, reverse engineering, software metrics and documentation generation. Hence, ensuring their completeness and correctness is a vital prerequisite for their use. In this paper we propose a strategy for the construction of test suites for grammar based software, and illustrate this strategy using the ISO C^+ + grammar. We use the concept of grammar-rule coverage as a pivot for the reduction of an implementation-based test suite, and demonstrate a significant decrease in the size of this suite. The effectiveness of this reduced test suite is compared to the original test suite with respect to code coverage and more importantly, fault detection. This work greatly expands upon previous work in this area and utilises large scale mutation testing to compare the effectiveness of grammar-rule coverage to that of statement coverage as a reduction criterion for test suites of grammar-based software. This work finds that when grammar rule coverage is used as the sole criterion for reducing test suites of grammar based software, the fault detection capability of that reduced test suite is greatly diminished when compared to other coverage criteria such as statement coverage.

基于NSGA-II的信息物理系统RESTful API测试套件最小化#br#

测试最小化技术旨在识别和消除测试套件中的冗余测试用例,以减少要执行的测试用例总数,从而提高测试效率。在将计算、通信和过程控制技术紧密结合的信息物理系统中,使用RESTful架构编写的接口,能够轻松实现跨平台跨语言调用。但缺乏对RESTful API测试工作的研究,给信息物理系统中RESTful API的测试以及测试用例的优化带来了挑战。最小化测试套件需要在尽可能覆盖所有测试需求的同时保持较高的故障检测能力。本文使用NSGA-Ⅱ和Random Search来最小化用于测试信息物理系统中RESTful API的测试套件,实验结果表明使用NSGA-Ⅱ优化后的测试套件性能明显优于使用Random Search以及原始的测试套件。     

基于图分析的测试用例集优化

根据被测系统接口参数之间的关系,研究接口参数集与二部图之间的联系,提出接口参数集的相关定义、分类和性质并证明这些性质。在此基础上提出一种基于图的测试用例集优化算法,用于约简和优化测试用例集。实例分析表明该方法能够在保持测试用例覆盖率不减的情况下,较大地减小被测系统的测试用例集规模,提高测试效率。     

Improving Fault Detection Capability by Selectively Retaining Test Cases during Test Suite Reduction

Software testing is a critical part of software development. As new test cases are generated over time due to software modifications, test suite sizes may grow significantly. Because of time and resource constraints for testing, test suite minimization techniques are needed to remove those test cases from a suite that, due to code modifications over time, have become redundant with respect to the coverage of testing requirements for which they were generated. Prior work has shown that test suite minimization with respect to a given testing criterion can significantly diminish the fault detection effectiveness (FDE) of suites. We present a new approach for test suite reduction that attempts to use additional coverage information of test cases to selectively keep some additional test cases in the reduced suites that are redundant with respect to the testing criteria used for suite minimization, with the goal of improving the FDE retention of the reduced suites. We implemented our approach by modifying an existing heuristic for test suite minimization. Our experiments show that our approach can significantly improve the FDE of reduced test suites without severely affecting the extent of suite size reduction     

基于变异分析的测试用例约简方法

针对回归测试过程中由于测试需求的变更导致测试用例规模不断扩大、测试成本不断增加的问题,提出一种基于变异分析的测试用例约简方法（RTM）。首先,以测试用例能否检测到指定变异体为依据,对测试用例进行划分并创建二进制数值形式的变异体事务集矩阵;然后,应用改进的关联挖掘算法获取测试用例间的关联关系;最后,根据这些关联关系有效约简测试用例。6个经典程序仿真实验结果表明,RTM能够使约简后的测试用例约简率达到37%,与传统贪心算法和启发式算法相比,测试用例约简率提高了6%,且在提高测试用例约简率的同时,保证了测试覆盖率,单个测试用例的测试覆盖率平均提高了11%。所提方法能够利用尽可能少的测试用例满足更多的测试需求,有效提高了测试效率,降低了测试成本。     

The density algorithm for pairwise interaction testing

There are many published algorithms for generating interaction test suites for software testing, exemplified by AETG, IPO, TCG, TConfig, simulated annealing and other heuristic search, and combinatorial design techniques. Among these, greedy one‐test‐at‐a‐time methods (such as AETG and TCG) have proven to be a reasonable compromise between the needs for small test suites, fast test‐suite generation, and flexibility to accommodate a variety of testing scenarios. However, such methods suffer from the lack of a worst‐case logarithmic guarantee on test suite size, while methods that provide such a guarantee at present are less efficient or flexible, or do not produce test suites that are competitive in size for practical testing scenarios. In this paper, a new algorithm establishes that efficient, greedy, one‐test‐at‐a‐time methods can indeed produce a logarithmic worst‐case guarantee on the test suite size. In addition, this can be done while still producing test suites that are of competitive size, and in a time that is comparable to the published methods. It is deterministic, guaranteeing reproducibility. It generates only one candidate test at a time, permits users to ‘seed’ the test suite with specified tests, and allows users to specify constraints of combinations that should be avoided. Further, statistical analysis examines the impact of five variables used to tune this density algorithm for execution time and test suite size: weighting of density for factors, scaling of density, tie‐breaking, use of multiple candidates, and multiple repetitions using randomization. Copyright © 2007 John Wiley & Sons, Ltd.     

基于提交排序和预测模型的测试套件选择方法

为在持续集成（CI）环境下减少回归测试集、提升回归测试的效率,提出一种适用于CI环境的回归测试套件选择方法。首先,根据每个提交的测试套件历史失败率和执行率信息,进行提交排序;然后,采用机器学习方法,对提交涉及的测试套件进行失败率预测,并选择具有较高失败率的测试套件。该方法综合使用提交排序技术和测试套件选择技术,从而保证既提高故障检测率又能在一定程度上降低测试成本。在Google的开源数据集上进行的实验结果表明：与同样采用提交排序的方法和采用测试套件选择的方法相比,所提方法的开销感知平均故障检测率APFDc提高了1%~27%;在相同的测试时间成本下,所提方法的测试召回提高了33.33~38.16个百分点,变更召回提高了15.67~24.52个百分点,测试套件选择率降低了约6个百分点。     

基于事件处理函数的GUI测试用例集约简技术

GUI测试用例集约简是降低GUI软件测试成本的有效手段.GUI软件的消息循环机制以及事件驱动特性,导致传统的基于控制流和数据流的测试用例集约简技术难以直接应用于GUI测试用例集约简.如何在尽可能保持原有测试用例集缺陷发现能力的基础上,尽可能地降低GUI测试用例集规模,是GUI测试用例集约简的一个挑战.以事件处理函数为核心,结合控制流和数据流技术,根据事件处理函数代码结构特征以及事件处理函数之间的数据依赖关系定义测试冗余规则,制定并实现了3种测试用例集约简技术.实验结果表明:与已有技术相比,其中两种根据事件处理函数之间的数据依赖关系制定的测试用例集约简技术达到了较好的约简效果.     

On the use of a similarity function for test case selection in the context of model‐based testing

Test case selection in model‐based testing is discussed focusing on the use of a similarity function. Automatically generated test suites usually have redundant test cases. The reason is that test generation algorithms are usually based on structural coverage criteria that are applied exhaustively. These criteria may not be helpful to detect redundant test cases as well as the suites are usually impractical due to the huge number of test cases that can be generated. Both problems are addressed by applying a similarity function. The idea is to keep in the suite the less similar test cases according to a goal that is defined in terms of the intended size of the test suite. The strategy presented is compared with random selection by considering transition‐based and fault‐based coverage. The results show that, in most of the cases, similarity‐based selection can be more effective than random selection when applied to automatically generated test suites. Copyright © 2009 John Wiley & Sons, Ltd.     

Reducing execution profiles: techniques and benefits

The interest in leveraging data mining and statistical techniques to enable dynamic program analysis has increased tremendously in recent years. Researchers have presented numerous techniques that mine and analyze execution profiles to assist software testing and other reliability enhancing approaches. Previous empirical studies have shown that the effectiveness of such techniques is likely to be impacted by the type of profiled program elements. This work further studies the impact of the characteristics of execution profiles by focusing on their size; noting that a typical profile comprises a large number of program elements, in the order of thousands or higher. Specifically, the authors devised six reduction techniques and comparatively evaluated them by measuring the following: (1) reduction rate; (2) information loss; (3) impact on two applications of dynamic program analysis, namely, cluster‐based test suite minimization (App‐I), and profile‐based online failure and intrusion detection (App‐II). The results were promising as the following: (a) the average reduction rate ranged from 92% to 98%; (b) three techniques were lossless and three were slightly lossy; (c) reducing execution profiles exhibited a major positive impact on the effectiveness and efficiency of App‐I; and (d) reduction exhibited a positive impact on the efficiency of App‐II, but a minor negative impact on its effectiveness. Copyright © 2014 John Wiley & Sons, Ltd.     

Using hybrid algorithm for Pareto efficient multi-objective test suite minimisation

Test suite minimisation techniques seek to reduce the effort required for regression testing by selecting a subset of test suites. In previous work, the problem has been considered as a single-objective optimisation problem. However, real world regression testing can be a complex process in which multiple testing criteria and constraints are involved. This paper presents the concept of Pareto efficiency for the test suite minimisation problem. The Pareto-efficient approach is inherently capable of dealing with multiple objectives, providing the decision maker with a group of solutions that are not dominated by each other. The paper illustrates the benefits of Pareto efficient multi-objective test suite minimisation with empirical studies of two and three objective formulations, in which multiple objectives such as coverage and past fault-detection history are considered. The paper utilises a hybrid, multi-objective genetic algorithm that combines the efficient approximation of the greedy approach with the capability of population based genetic algorithm to produce higher-quality Pareto fronts.     

Call-Stack Coverage for GUI Test Suite Reduction

Graphical user interfaces (GUIs) are used as front ends to most of today's software applications. The event-driven nature of GUIs presents new challenges for testing. One important challenge is test suite reduction. Conventional reduction techniques/tools based on static analysis are not easily applicable due to the increased use of multilanguage GUI implementations, callbacks for event handlers, virtual function calls, reflection, and multithreading. Moreover, many existing techniques ignore code in libraries and fail to consider the context in which event handlers execute. Consequently, they yield GUI test suites with seriously impaired fault-detection abilities. This paper presents a reduction technique based on the call-stack coverage criterion. Call stacks may be collected for any executing program with very little overhead. Empirical studies in this paper compare reduction based on call-stack coverage to reduction based on line, method, and event coverage, including variations that control for the size and optional consideration of library methods. These studies show that call-stack-based reduction provides unique trade-offs between the reduction in test suite size and the loss of fault detection effectiveness, which may be valuable in practice. Additionally, an analysis of the relationship between coverage requirements and fault-revealing test cases is presented.     

基于弱变异准则的测试用例约简方法

针对为数较多的测试用例增加了回归测试成本的问题，提出一种基于弱变异准则的测试用例约简方法。首先，基于弱变异准则获得测试用例和变异分支关系矩阵；然后，重复约简4种无效测试需求和子集测试用例；最后，结合人工鱼群算法选择当前最优测试用例，并且交替执行简化和测试用例选择操作直至覆盖所有测试需求。该方法针对6个经典程序与贪心算法和HGS算法相比，基于弱变异准则并且不改变或稍微改变变异评分的条件下，约简率分别提高了73.4%和8.2%，且耗时分别降低了25.3%和56.1%。实验结果表明，所提方法在回归测试中可有效约简测试用例，降低测试代价。     

一种有效的边界测试点选取策略

借鉴组合逻辑电路固定型故障的诊断原理,提出一种软件边界测试点选取策略.根据RSDIMU容错软件需求规范开发出52个测试用例,同时采用边界值分析、健壮性测试等边界值测试方法设计了2组测试用例,对34个版本的RSDIMU程序和429个变异体进行了测试.实验结果表明:该方法是一种有效的边界测试点选取策略,可以克服测试的盲目性,降低测试成本,明显地提高故障覆盖程度.