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

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.     

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     

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.     

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.     

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.     

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.     

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     

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.     

Selecting a Cost-Effective Test Case Prioritization Technique

Regression testing is an expensive testing process used to validate modified software and detect whether new faults have been introduced into previously tested code. 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 goal of prioritization is to increase a test suite's rate of fault detection. Previous empirical studies have shown that several prioritization techniques can significantly improve rate of fault detection, but these studies have also shown that the effectiveness of these techniques varies considerably across various attributes of the program, test suites, and modifications being considered. This variation makes it difficult for a practitioner to choose an appropriate prioritization technique for a given testing scenario. To address this problem, we analyze the fault detection rates that result from applying several different prioritization techniques to several programs and modified versions. The results of our analyses provide insights into which types of prioritization techniques are and are not appropriate under specific testing scenarios, and the conditions under which they are or are not appropriate. Our analysis approach can also be used by other researchers or practitioners to determine the prioritization techniques appropriate to other workloads.     

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.     

基于定值-引用链的测试用例优先级排序算法

测试用例优先级排序作为一种高效实用的回归测试技术,通常以测试用例的覆盖度作为优先级排序的量化指标,忽略了测试用例的其他测试性能。针对该问题,提出一种基于DU链的测试用例优先级排序算法。该算法 综合考虑 测试用例的DU链覆盖度和回归测试的错误检测能力,对测试用例优先级进行量化。与已有算法相比,该算法基于数据流覆盖,充分利用了测试执行的历史信息和程序模块的耦合信息,在排序过程中动态计算测试用例的优先级量化值。实验结果表明,采用优先级排序算法的测试用例集能在测试过程中以较短的时间发现更多的错误,有效地提高了回归测试的检错效率。     

基于需求的系统级黑盒测试用例优先化方法

测试用例优先化技术有利于提高测试的质量和效率。文章提出了一种在系统测试阶段基于需求的测试用例优先化方法TRP,并通过实验结果加以验证。与随机方法对测试用例排序的测试相比,TRP方法能尽早发现软件严重缺陷并提高缺陷检测率。     

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.     

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.     

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

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

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

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

XML-manipulating test case prioritization for XML-manipulating services

A web service may evolve autonomously, making peer web services in the same service composition uncertain as to whether the evolved behaviors are compatible with its original collaborative agreement. Although peer services may wish to conduct regression testing to verify the agreed collaboration, the source code of the former service may be inaccessible to them. Owing to the black-box nature of peer services, traditional code-based approaches to regression testing are inapplicable. In addition, traditional techniques assume that a regression test suite for verifying a web service is available. The location to store a regression test suite is also a problem. On the other hand, we note that the rich interface specifications of a web service provide peer services with a means to formulate black-box testing strategies. In this paper, we provide a strategy for black-box service-oriented testing. We also formulate new test case prioritization strategies using tags embedded in XML messages to reorder regression test cases, and reveal how the test cases use the interface specifications of web services. We experimentally evaluate the effectiveness of these black-box strategies in revealing regression faults in modified WS-BPEL programs. The results show that the new techniques can have a high chance of outperforming random ordering. Moreover, our experiment shows that prioritizing test cases based on WSDL tag coverage can achieve a smaller variance than that based on the number of tags in XML messages in regression test cases, even though their overall fault detection rates are similar.     

Comprehensive analysis of FBD test coverage criteria using mutants

Function block diagram (FBD), a graphical modeling language for programmable logic controllers, has been widely used to implement safety critical system software such as nuclear reactor protection systems. With the growing importance of structural testing for FBD models, structural test coverage criteria for FBD models have been proposed and evaluated using mutation analysis in our previous work. We extend the previous work by comprehensively analyzing the relationships among fault detection effectiveness, test suite size, and coverage level through several research questions. We generate a large number of test suites achieving an FBD test coverage ranging from 0 to 100 %, and we also generate many artificial faults (i.e. mutants) for the FBD models. Our analysis results show that the fault detection effectiveness of the FBD coverage criteria increases with increasing coverage levels, and the coverage criteria are highly effective at detecting faults in all subject models. Furthermore, the test suites generated with the FBD coverage criteria are more effective and efficient than the randomly generated test suites. The FBD coverage criteria are strong at detecting faults in Boolean edges, while relatively weak at detecting wrong constants in FBD models. Empirical knowledge regarding our experiments provide the validity of using the FBD coverage criteria, and therefore, of FBD model-based testing.