用遗传算法的测试用例最小化

回归测试就是验证对程序的修改是否迭到了预期的目的，同时检查修改是否损害了程序原有的正常功能。随着程序新版本的不断推出，测试用例集不断扩大，回归测试成本越来越高。测试用例最小化就是从已有的用例集中，找到一个测试运行代价最小的用例子集用于回归测试，并保持原来的测试覆盖率。本文主要研究用遗传算法解决测试用例最小化问题：基于测试历史数据，设计基因编码并构建初始种群；利用测试覆盖率和测试运行代价设计适应度函数；通过遗传算子完成进化过程并找到最优或近似最优解。最后本文给出了对算法进行实例研究的结果。结果表明，本文提出的用例最小化技术能有效缩减回归测试用例集，大幅度降低回归测试费用。     

面向故障定位的基于MC/DC的测试用例约简方法

对不断更新的软件进行回归测试时,持续增加的测试用例会造成累计测试用例数量庞大,进而影响测试成本。在故障定位领域,已有研究在考虑语句覆盖、路径覆盖等的基础上,提出了CMR&PVR等不同的测试用例约简方法。然而,这些方法在一定程度上影响了原始测试用例集的MC/DC(修订的条件/判定)覆盖率。提出一种以MC/DC覆盖为基础的综合测试用例约简方法MCDCR,利用该方法对原始测试用例集约简后,在确保原有故障定位准确性并保持较高约简比的同时,大幅提高了测试用例对程序的MC/DC覆盖率。采用Ochiai方法在Siemens 程序集上进行了实验及验证,结果表明MCDCR约简方法的综合效果明显优于已有的约简方法。     

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%.     

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     

利用MC/DC减少测试集大小的方法的研究

随着软件的发展，测试技术也在发展。MC／DC即修改条件／判定覆盖，是一种较新的结构覆盖准则，它是在C／DC（条件／判定覆盖）的基础上发展起来的。与其它结构覆盖准则相比，它只是线性地增加了测试用例的数量，使得软件测试更加具有可操作性。而对于测试来说，测试用例的选择和优化是至关重要的。在探讨MC／DC的基础上，利用MC／DC的特点，初步提出了利用MC／DC进行测试集减少的方法，使得减少后的测试集与原测试集对测试需求有着相同或相似的覆盖率，并对此方法的利弊做了一定的分析。     

Compositional Generation of MC/DC Integration Test Suites

We present a method for automatically generating tests for reactive systems specified by concurrently executing extended finite state machines. The generated test suites satisfy the modified condition/decision coverage criterion at unit and integration levels. The generation of MC/DC suites for eager first-order functional programs is subsumed. An industrial chip card case study illustrates the approach.     

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.     

测试用例集启发式约简算法分析与评价

在软件开发和维护过程中,为了提高对源程序变更部分的信心并且保证源程序变更部分没有对未变更部分造成负面影响,需要对软件系统进行回归测试。回归测试是一个昂贵的测试过程。测试用例集约简算法是在仍然满足测试准则的前提下,通过删除所有冗余测试用例得到测试用例集的最小约简测试用例集,用以优化回归测试过程。综述了文献中主要的测试用例集启发式约简算法,通过统一的框架和术语定义了这些算法,分析和比较了这些算法的效率和优劣,指出了未来进一步研究的方向。     

引入错误级别的测试集压缩模型研究

开发者每一次对软件的修改都会导致测试集的增长。在进行回归测试时，如果重新运行所有的测试案例，成本将是极其昂贵的。于是，一些压缩测试集的算法被提出。这些算法能够找出一个与原测试集有相同覆盖度的压缩测试集，但这些压缩后的测试集在查错方面的性能不十分令人满意。引入错误级别的概念可以对测试案例的查错能力进行更为为细致的划分。本文通过引入错误级别，改进了一个双标准测试集压缩模型，并提出了一个新的测试集压缩算法。改进后的双标准测试集压缩模型能提供关于测试案例查错能力的更具体的信息。新算法有一个重要的特点：在任何时候中断算法，仍然能得到一个满足覆盖度的压缩测试集。     

On the adoption of MC/DC and control-flow adequacy for a tight integration of program testing and statistical fault localization

ContextTesting and debugging consume a significant portion of software development effort. Both processes are usually conducted independently despite their close relationship with each other. Test adequacy is vital for developers to assure that sufficient testing effort has been made, while finding all the faults in a program as soon as possible is equally important. A tight integration between testing and debugging activities is essential.ObjectiveThe paper aims at finding whether three factors, namely, the adequacy criterion to gauge a test suite, the size of a prioritized test suite, and the percentage of such a test suite used in fault localization, have significant impacts on integrating test case prioritization techniques with statistical fault localization techniques.MethodWe conduct a controlled experiment to investigate the effectiveness of applying adequate test suites to locate faults in a benchmark suite of seven Siemens programs and four real-life UNIX utility programs using three adequacy criteria, 16 test case prioritization techniques, and four statistical fault localization techniques. We measure the proportion of code needed to be examined in order to locate a fault as the effectiveness of statistical fault localization techniques. We also investigate the integration of test case prioritization and statistical fault localization with postmortem analysis.ResultThe main result shows that on average, it is more effective for a statistical fault localization technique to utilize the execution results of a MC/DC-adequate test suite than those of a branch-adequate test suite, and is in turn more effective to utilize the execution results of a branch-adequate test suite than those of a statement-adequate test suite. On the other hand, we find that none of the fault localization techniques studied can be sufficiently effective in suggesting fault-relevant statements that can fit easily into one debug window of a typical IDE.ConclusionWe find that the adequacy criterion and the percentage of a prioritized test suite utilized are major factors affecting the effectiveness of statistical fault localization techniques. In our experiment, the adoption of a stronger adequacy criterion can lead to more effective integration of testing and debugging.     

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

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

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.

测试用例最小化研究*

给出了测试用例最小化问题的形式化描述,提出并实现了两个新的用于用例最小化的算法.与现有其他最小化算法不同,这两个算法在考虑了每个用例测试覆盖度的同时,还考虑了用例的测试运行代价,目的是提高最小化效率.最后给出了对这两个算法进行实例研究的实验结果.结果表明,用例最小化技术能有效缩减回归测试用例集的尺寸,大幅度降低回归测试费用,提高最小化效率.     

A correlation study between automated program repair and test-suite metrics

Automated program repair is increasingly gaining traction, due to its potential to reduce debugging cost greatly. The feasibility of automated program repair has been shown in a number of works, and the research focus is gradually shifting toward the quality of generated patches. One promising direction is to control the quality of generated patches by controlling the quality of test-suites used for automated program repair. In this paper, we ask the following research question: “Can traditional test-suite metrics proposed for the purpose of software testing also be used for the purpose of automated program repair?” We empirically investigate whether traditional test-suite metrics such as statement/branch coverage and mutation score are effective in controlling the reliability of generated repairs (the likelihood that repairs cause regression errors). We conduct the largest-scale experiments of this kind to date with real-world software, and for the first time perform a correlation study between various test-suite metrics and the reliability of generated repairs. Our results show that in general, with the increase of traditional test suite metrics, the reliability of repairs tend to increase. In particular, such a trend is most strongly observed in statement coverage. Our results imply that the traditional test suite metrics proposed for software testing can also be used for automated program repair to improve the reliability of repairs.     

测试用例排序的研究

回归测试是一个成本很高的测试过程。为了减少回归测试的成本,可以使用测试用例排序技术。测试用例排序是指按照事先确定的目标重新安排测试用例集中测试用例的执行次序,使得具有高优先级的测试用例比低优先级的测试用例在测试过程中更早执行。本文描述了测试用例排序问题;给出了两个一般测试用例排序算法,即总计排序算法和 附加排序算法;根据不同的覆盖准则（如语句、分支和定义-使用等）,可以从这两个一般算法得到对应的排序算法;最后,讨论了测试用例排序算法的有效性。     

应用MC/DC准则时需考虑的问题及其改进方法

MC／DC(修订的条件／判定覆盖)准则是一种实用的软件结构覆盖率测试准则。目前，MC／DC在国际上已被广泛地应用于软件验证和测试过程中，在我国也被应用于一些软件项目中。介绍了MC／DC准则，提出了用此准则进行结构覆盖率分析时需注意的两个问题：结构覆盖率分析的问题和复杂逻辑语句的问题。最后，详细讨论了用MC／DC准则检查逻辑表达式错误时需考虑的3个方面及相应的改进方法，这3个方面包括逻辑式中操作符OR与XOR的误写、括号的位置不正确和逻辑组元被误写。     

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.     

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

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

Making a concolic tester achieve increased MC/DC

Concolic testing techniques do not necessarily aim to achieve a specific MC/DC coverage. On the other hand, MC/DC is considered as a standard and a strong test coverage criterion. It is mandated for many categories of applications such as safety critical software. We present an automated code transformation technique that can be used as a front end to a concolic tester for achieving high MC/DC. Our experimentation on seventeen moderately complex programs shows that our approach achieves higher MC/DC over traditional concolic tester on the average by 24.84 %, for the code we tested.     

On the effect of test-suite reduction on automatically generated model-based tests

Model checking techniques can be successfully employed as a test-case generation technique to generate tests from formal models. The number of tests-cases produced, however, is typically large for complex coverage criteria such as MC/DC. Test-suite reduction can provide us with a smaller set of test-cases that preserve the original coverage—often a dramatically smaller set. Nevertheless, one potential drawback with test-suite reduction is that this might affect the quality of the test-suite in terms of fault finding. Previous empirical studies provide conflicting evidence on this issue. To further investigate the problem and determine its effect when testing implementations derived from formal models of software we performed an experiment using a large case example of a Flight Guidance System, generated reduced test-suites for a variety of structural coverage criteria while preserving coverage, and recorded their fault finding effectiveness. Our results indicate that the size of the specification based test-suites can be dramatically reduced and that the fault detection of the reduced test-suites is adversely affected. In this report we describe our experiment, analyze the results, and discuss the implications for testing based on formal specifications. This work has been partially supported by NASA grant NAG-1-224 and NASA contract NCC-01001. We also want to thank the McKnight Foundation for their generous support over the years.

---