Test case prioritization: a family of empirical studies

To reduce the cost of regression testing, software testers may prioritize their test cases so that those which are more important, by some measure, are run earlier in the regression testing process. One potential goal of such prioritization is to increase a test suite's rate of fault detection. Previous work reported results of studies that showed that prioritization techniques can significantly improve rate of fault detection. Those studies, however, raised several additional questions: 1) Can prioritization techniques be effective when targeted at specific modified versions; 2) what trade-offs exist between fine granularity and coarse granularity prioritization techniques; 3) can the incorporation of measures of fault proneness into prioritization techniques improve their effectiveness? To address these questions, we have performed several new studies in which we empirically compared prioritization techniques using both controlled experiments and case studies     

On the Use of Mutation Faults in Empirical Assessments of Test Case Prioritization Techniques

Regression testing is an important activity in the software life cycle, but it can also be very expensive. To reduce the cost of regression testing, software testers may prioritize their test cases so that those which are more important, by some measure, are run earlier in the regression testing process. One potential goal of test case prioritization techniques is to increase a test suite's rate of fault detection (how quickly, in a run of its test cases, that test suite can detect faults). Previous work has shown that prioritization can improve a test suite's rate of fault detection, but the assessment of prioritization techniques has been limited primarily to hand-seeded faults, largely due to the belief that such faults are more realistic than automatically generated (mutation) faults. A recent empirical study, however, suggests that mutation faults can be representative of real faults and that the use of hand-seeded faults can be problematic for the validity of empirical results focusing on fault detection. We have therefore designed and performed two controlled experiments assessing the ability of prioritization techniques to improve the rate of fault detection of test case prioritization techniques, measured relative to mutation faults. Our results show that prioritization can be effective relative to the faults considered, and they expose ways in which that effectiveness can vary with characteristics of faults and test suites. More importantly, a comparison of our results with those collected using hand-seeded faults reveals several implications for researchers performing empirical studies of test case prioritization techniques in particular and testing techniques in general     

Prioritizing test cases for regression testing

Test case prioritization techniques schedule test cases for execution in an order that attempts to increase their effectiveness at meeting some performance goal. Various goals are possible; one involves rate of fault detection, a measure of how quickly faults are detected within the testing process. An improved rate of fault detection during testing can provide faster feedback on the system under test and let software engineers begin correcting faults earlier than might otherwise be possible. One application of prioritization techniques involves regression testing, the retesting of software following modifications; in this context, prioritization techniques can take advantage of information gathered about the previous execution of test cases to obtain test case orderings. We describe several techniques for using test execution information to prioritize test cases for regression testing, including: 1) techniques that order test cases based on their total coverage of code components; 2) techniques that order test cases based on their coverage of code components not previously covered; and 3) techniques that order test cases based on their estimated ability to reveal faults in the code components that they cover. We report the results of several experiments in which we applied these techniques to various test suites for various programs and measured the rates of fault detection achieved by the prioritized test suites, comparing those rates to the rates achieved by untreated, randomly ordered, and optimally ordered suites     

Prioritizing JUnit Test Cases: An Empirical Assessment and Cost-Benefits Analysis

Test case prioritization provides a way to run test cases with the highest priority earliest. Numerous empirical studies have shown that prioritization can improve a test suite's rate of fault detection, but the extent to which these results generalize is an open question because the studies have all focused on a single procedural language, C, and a few specific types of test suites. In particular, Java and the JUnit testing framework are being used extensively to build software systems in practice, and the effectiveness of prioritization techniques on Java systems tested under JUnit has not been investigated. We have therefore designed and performed a controlled experiment examining whether test case prioritization can be effective on Java programs tested under JUnit, and comparing the results to those achieved in earlier studies. Our analyses show that test case prioritization can significantly improve the rate of fault detection of JUnit test suites, but also reveal differences with respect to previous studies that can be related to the language and testing paradigm. To investigate the practical implications of these results, we present a set of cost-benefits models for test case prioritization, and show how the effectiveness differences observed can result in savings in practice, but vary substantially with the cost factors associated with particular testing processes.     

Putting your best tests forward

Test case prioritization orders tests so that they help you meet your testing goals earlier during regression testing. Prioritization techniques can, for example, order tests to achieve coverage at the fastest rate possible, exercise features in order of expected frequency of use, or reveal faults as early as possible. We focus on the last goal, which we describe as "increasing a test suite's rate of fault detection" or the speed with which the test suite reveals faults. A faster fault detection rate during regression testing provides earlier feedback on a system under test, supporting earlier strategic decisions about release schedules and letting engineers begin debugging sooner. Also, if testing time is limited or unexpectedly reduced, prioritization increases the chance that testing resources will have been spent as cost effectively as possible in the available time.     

一个划算的回归测试用例排序的成本-收益模型

回归测试是一个昂贵的测试过程,它验证修改的软件,确认是否给已经测试的代码引进了新的错误.因为在软件开发的过程中,测试人员给测试包中增加了新的测试用例,使软件确认更加困难.为了使回归测试更经济划算,提出了很多技术和方法.测试用例选择,测试包缩减,测试用例排序可以帮助我们减少需要运行的测试用例数目,同时能够更快地满足测试目标.测试用例排序是在满足某个性能目标的基础上,保证在测试过程中首先执行更重要的功能.以前的研究提出了一个性能目标:缺陷发现率(APFD),以及很多改善缺陷发现率的技术.但是这些技术运用起来非常昂贵,而且可能不会减少回归测试的成本.在以往研究的基础上,提出了一个成本-收益模型,为比较各种排序算法提供了一定依据.并在此基础上,提供了一个测试用例排序算法.     

Experiments with test case prioritization using relevant slices

Software testing and retesting occurs continuously during the software development lifecycle to detect errors as early as possible and to gain confidence that changes to software do not introduce defects. Once developed, test suites are reused and updated frequently, and their sizes grow as software evolves. Due to time and resource constraints, an important goal during regression testing of software is to prioritize the execution of test cases in a suite so as to improve the chances of increasing the rate of fault detection. Prior techniques for test case prioritization are based on the total number of coverage requirements exercised by the test cases. In this paper, we present a new approach to prioritize test cases that takes into account the coverage requirements present in the relevant slices of the outputs of test cases. We have implemented three different heuristics based on our relevant slicing based approach to prioritize test cases and conducted experiments to compare the effectiveness of our techniques with those of the traditional techniques that only account for the total requirement coverage. Our detailed experimental study and results provide interesting insights into the effectiveness of using relevant slices for test case prioritization in terms of ability to achieve high rate of fault detection.     

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     

A history-based cost-cognizant test case prioritization technique in regression testing

Software testing is typically used to verify whether the developed software product meets its requirements. From the result of software testing, developers can make an assessment about the quality or the acceptability of developed software. It is noted that during testing, the test case is a pair of input and expected output, and a number of test cases will be executed either sequentially or randomly. The techniques of test case prioritization usually schedule test cases for regression testing in an order that attempts to increase the effectiveness. However, the cost of test cases and the severity of faults are usually varied. In this paper, we propose a method of cost-cognizant test case prioritization based on the use of historical records. We gather the historical records from the latest regression testing and then propose a genetic algorithm to determine the most effective order. Some controlled experiments are performed to evaluate the effectiveness of our proposed method. Evaluation results indicate that our proposed method has improved the fault detection effectiveness. It can also been found that prioritizing test cases based on their historical information can provide high test effectiveness during testing.     

Prioritizing test cases for early detection of refactoring faults

Refactoring edits are error‐prone, requiring cost‐effective testing. Regression test suites are often used as a safety net for decreasing the chances of behavioural changes. Because of the high costs related to handling massive test suites, prioritization techniques can be applied to reorder test case execution, fostering early fault detection. However, traditional prioritization techniques are not specifically designed for detecting refactoring‐related faults. This article proposes refactoring‐based approach (RBA), a refactoring‐aware strategy for prioritizing regression test cases. RBA reorders an existing test sequence, using a set of proposed refactoring fault models that define the refactoring's impact on program methods. Refactoring‐based approach's evaluation shows that it promotes early detection of refactoring faults and outperforms well‐known prioritization techniques in 71% of the cases. Moreover, it prioritizes fault‐revealing test cases close to one another in 73% of the cases, which can be useful for fault localization. Those findings show that RBA can considerably improve prioritization of test cases during perfective evolution, both by increasing fault‐detection rates as well as by helping to pinpoint defects introduced by an incorrect refactoring. Copyright © 2016 John Wiley & Sons, Ltd.     

基于动态相似度的错误定位优先排序方法

在软件测试中,错误定位优先排序通过优化测试用例的执行次序来提高错误定位的效果,并将检测错误和定位错误相结合,以降低测试成本。 提出了一种基于动态相似度的错误定位优先排序方法,在相似度计算中,引入了语句怀疑度,提高了相似度计算的有效性以及错误定位的准确度;同时分析并验证了不同测试用例优先排序算法对后续定位错误的影响。在6个C基准程序上,针对3种广泛采用的测试用例优先排序算法和2种错误定位技术进行了实验,结果表明提出的方法能提高错误定位的准确度和效率。     

How well does test case prioritization integrate with statistical fault localization?

ContextEffective test case prioritization shortens the time to detect failures, and yet the use of fewer test cases may compromise the effectiveness of subsequent fault localization.ObjectiveThe paper aims at finding whether several previously identified effectiveness factors of test case prioritization techniques, namely strategy, coverage granularity, and time cost, have observable consequences on the effectiveness of statistical fault localization techniques.MethodThis paper uses a controlled experiment to examine these factors. The experiment includes 16 test case prioritization techniques and four statistical fault localization techniques using the Siemens suite of programs as well as grep, gzip, sed, and flex as subjects. The experiment studies the effects of the percentage of code examined to locate faults from these benchmark subjects after a given number of failures have been observed.ResultsWe find that if testers have a budgetary concern on the number of test cases for regression testing, the use of test case prioritization can save up to 40% of test case executions for commit builds without significantly affecting the effectiveness of fault localization. A statistical fault localization technique using a smaller fraction of a prioritized test suite is found to compromise its effectiveness seriously. Despite the presence of some variations, the inclusion of more failed test cases will generally improve the fault localization effectiveness during the integration process. Interestingly, during the variation periods, adding more failed test cases actually deteriorates the fault localization effectiveness. In terms of strategies, Random is found to be the most effective, followed by the ART and Additional strategies, while the Total strategy is the least effective. We do not observe sufficient empirical evidence to conclude that using different coverage granularity levels have different overall effects.ConclusionThe paper empirically identifies that strategy and time–cost of test case prioritization techniques are key factors affecting the effectiveness of statistical fault localization, while coverage granularity is not a significant factor. It also identifies a mid-range deterioration in fault localization effectiveness when adding more test cases to facilitate debugging.     

Factor oriented requirement coverage based system test case prioritization of new and regression test cases

Test case prioritization involves scheduling test cases in an order that increases the effectiveness in achieving some performance goals. One of the most important performance goals is the rate of fault detection. Test cases should run in an order that increases the possibility of fault detection and also that detects the most severe faults at the earliest in its testing life cycle. In this paper, we propose to put forth a model for system level test case prioritization (TCP) from software requirement specification to improve user satisfaction with quality software that can also be cost effective and to improve the rate of severe fault detection. The proposed model prioritizes the system test cases based on the six factors: customer priority, changes in requirement, implementation complexity, completeness, traceability and fault impact. The proposed prioritization technique is validated with two different validation techniques and is experimented in three phases with student projects and two sets of industrial projects and the results show convincingly that the proposed prioritization technique improves the rate of severe fault detection.     

融合聚类算法和缺陷预测的测试用例优先排序方法

持续集成环境下,软件快速更新加快了回归测试执行的频率,但缺陷快速反馈的需求对回归测试又提出了更高要求。测试用例优先排序技术研究测试用例的重要性,通常将缺陷探测能力强的测试用例优先执行,使其提早发现软件缺陷,其可解决持续集成环境下的快速反馈需求。缺陷预测技术可通过被测系统代码特征和历史缺陷来预估信息预测软件在新版本中发现缺陷的可能性,传统基于聚类的测试用例优先排序方法大多未考虑不同类簇数和特征子集对聚类结果的影响。文中将缺陷预测应用到聚类优先排序方法,构建测试用例和代码关联矩阵,对测试用例进行聚类分析,结合缺陷预测结果和最大最小距离策略指导簇间和簇内排序。通过实验验证发现,类簇数和聚类特征子集选择对排序效果有一定影响,当未能获取最佳类簇数和特征子集时,相比单一的聚类优先排序方法,所提方法可更有效地提高回归测试效率。     

回归测试中的测试用例优先排序技术述评

测试用例优先排序(test case prioritization,简称TCP)问题是回归测试研究中的一个热点.通过设定特定排序准则,对测试用例进行排序以优化其执行次序,旨在最大化排序目标,例如最大化测试用例集的早期缺陷检测速率.TCP问题尤其适用于因测试预算不足以致不能执行完所有测试用例的测试场景.首先对TCP问题进行描述,并依次从源代码、需求和模型这3个角度出发对已有的TCP技术进行分类;然后对一类特殊的TCP问题(即测试资源感知的TCP问题)的已有研究成果进行总结;随后依次总结实证研究中常用的评测指标、评测数据集和缺陷类型对实证研究结论的影响;接着依次介绍TCP技术在一些特定测试领域中的应用,包括组合测试、事件驱动型应用测试、Web服务测试和缺陷定位等;最后对下一步工作进行展望.     

Prioritizing MCDC test cases by spectral analysis of Boolean functions

Test case prioritization aims at scheduling test cases in an order that improves some performance goal. One performance goal is a measure of how quickly faults are detected. Such prioritization can be performed by exploiting the fault exposing potential (FEP) parameters associated to the test cases. The FEP is usually approximated by mutation analysis under certain fault assumptions. Although this technique is effective, it could be relatively expensive compared to the other prioritization techniques. This study proposes a cost‐effective FEP approximation for prioritizing modified condition decision coverage (MCDC) test cases. A strict negative correlation between the FEP of an MCDC test case and the influence value of the associated input condition allows to order the test cases easily without the need of an extensive mutation analysis. The method is entirely based on mathematics and it provides useful insight into how spectral analysis of Boolean functions can benefit software testing.     

An improved method for test case prioritization by incorporating historical test case data

Test case prioritization reorders test cases from a previous version of a software system for the current release to optimize regression testing. We have previously introduced a technique for test case prioritization using historical test case performance data. The technique was based on a test case prioritization equation, which directly computes the priority of each test case using the historical information of the test case using an equation with constant coefficients. This technique was compared just with random ordering approach. In this paper, we present an enhancement of the aforementioned technique in two ways. First, we propose a new prioritization equation with variable coefficients gained according to the available historical performance data, which acts as a feedback from the previous test sessions. Second, a family of comprehensive empirical studies has been conducted to evaluate the performance of the technique. We have compared the proposed technique with our previous technique and the technique proposed by Kim and Porter. The experimental results demonstrate the effectiveness of the proposed technique in accelerating the rate of fault detection in history-based test case prioritization.     

Improving test efficiency through system test prioritization

Software testing is an expensive process consuming at least 50% of the total development cost. Among the types of testing, system testing is the most expensive and complex. Companies are frequently faced with budgetary constraints, which may limit their ability to effectively complete testing efforts before delivering a software product. We build upon prior test case prioritization research and present a system-level approach to test case prioritization called Prioritization of Requirements for Test (PORT). PORT prioritizes system test cases based on four factors for each requirement: customer priority, implementation complexity, fault proneness, and requirements volatility. Test cases for requirements with higher priority based upon a weighted average of these factors are executed earlier in system test. An academic feasibility study and three post hoc industrial studies were conducted. Results indicate that PORT can be used to improve the rate of failure detection when compared with a random and operational profile-driven random approach. Furthermore, we investigated the contribution of the prioritization factors towards the improved rate of failure detection and found customer priority was the most significant contributor. Tool support is provided for the PORT scheme which allows for automatic collection of the four factor values and the resultant test case prioritization.     

Similarity-based test case prioritization using ordered sequences of program entities

Test suites often grow very large over many releases, such that it is impractical to re-execute all test cases within limited resources. Test case prioritization rearranges test cases to improve the effectiveness of testing. Code coverage has been widely used as criteria in test case prioritization. However, the simple way may not reveal some bugs, such that the fault detection rate decreases. In this paper, we use the ordered sequences of program entities to improve the effectiveness of test case prioritization. The execution frequency profiles of test cases are collected and transformed into the ordered sequences. We propose several novel similarity-based test case prioritization techniques based on the edit distances of ordered sequences. An empirical study of five open source programs was conducted. The experimental results show that our techniques can significantly increase the fault detection rate and be effective in detecting faults in loops. Moreover, our techniques are more cost-effective than the existing techniques.     

Understanding the effects of changes on the cost‐effectiveness of regression testing techniques

Regression testing is an expensive testing process used to validate modified software. Regression test selection and test‐case prioritization can reduce the costs of regression testing by selecting a subset of test cases for execution, or scheduling test cases to meet testing objectives better. The cost‐effectiveness of these techniques can vary widely, however, and one cause of this variance is the type and magnitude of changes made in producing a new software version. Engineers unaware of the causes and effects of this variance can make poor choices in designing change integration processes, selecting inappropriate regression testing techniques, designing excessively expensive regression test suites and making unnecessarily costly changes. Engineers aware of causal factors can perform regression testing more cost‐effectively. This article reports the results of an embedded multiple case study investigating the modifications made in the evolution of four software systems and their impact on regression testing techniques. The results of this study expose tradeoffs and constraints that affect the success of techniques and provide guidelines for designing and managing regression testing processes. Copyright © 2003 John Wiley & Sons, Ltd.