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

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.     

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.     

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     

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.     

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.     

Improving the effectiveness of test suite reduction for user-session-based testing of web applications

ContextTest suite reduction is the problem of creating and executing a set of test cases that are smaller in size but equivalent in effectiveness to an original test suite. However, reduced suites can still be large and executing all the tests in a reduced test suite can be time consuming.ObjectiveWe propose ordering the tests in a reduced suite to increase its rate of fault detection. The ordered reduced test suite can be executed in time constrained situations, where, even if test execution is stopped early, the best test cases from the reduced suite will already be executed.MethodIn this paper, we present several approaches to order reduced test suites using experimentally verified prioritization criteria for the domain of web applications. We conduct an empirical study with three subject applications and user-session-based test cases to demonstrate how ordered reduced test suites often make a practical contribution. To enable comparison between test suites of different sizes, we develop Mod_APFD_C, a modification of the traditional prioritization effectiveness measure.ResultsWe find that by ordering the reduced suites, we create test suites that are more effective than unordered reduced suites. In each of our subject applications, there is at least one ordered reduced suite that outperforms the best unordered reduced suite and the best prioritized original suite.ConclusionsOur results show that when a tester does not have enough time to execute the entire reduced suite, executing an ordered reduced suite often improves the rate of fault detection. By coupling the underlying system’s characteristics with observations from our study on the criteria that produce the best ordered reduced suites, a tester can order their reduced test suites to obtain increased testing effectiveness.     

Variability testing in the wild: the Drupal case study

Variability testing techniques search for effective and manageable test suites that lead to the rapid detection of faults in systems with high variability. Evaluating the effectiveness of these techniques in realistic settings is a must, but challenging due to the lack of variability-intensive systems with available code, automated tests and fault reports. In this article, we propose using the Drupal framework as a case study to evaluate variability testing techniques. First, we represent the framework variability using a feature model. Then, we report on extensive non-functional data extracted from the Drupal Git repository and the Drupal issue tracking system. Among other results, we identified 3392 faults in single features and 160 faults triggered by the interaction of up to four features in Drupal v7.23. We also found positive correlations relating the number of bugs in Drupal features to their size, cyclomatic complexity, number of changes and fault history. To show the feasibility of our work, we evaluated the effectiveness of non-functional data for test case prioritization in Drupal. Results show that non-functional attributes are effective at accelerating the detection of faults, outperforming related prioritization criteria as test case similarity.     

Fault-based test suite prioritization for specification-based testing

Context

Existing test suite prioritization techniques usually rely on code coverage information or historical execution data that serve as indicators for estimating the fault-detecting ability of test cases. Such indicators are primarily empirical in nature and not theoretically driven; hence, they do not necessarily provide sound estimates. Also, these techniques are not applicable when the source code is not available or when the software is tested for the first time.

Objective

We propose and develop the novel notion of fault-based prioritization of test cases which directly utilizes the theoretical knowledge of their fault-detecting ability and the relationships among the test cases and the faults in the prescribed fault model, based on which the test cases are generated.

Method

We demonstrate our approach of fault-based prioritization by applying it to the testing of the implementation of logical expressions against their specifications. We then validate our proposal by an empirical study that evaluates the effectiveness of prioritization techniques using two different metrics.

Results

A theoretically guided fault-based prioritization technique generally outperforms other techniques under study, as assessed by two different metrics. Our empirical results also show that the technique helps to reveal all target faults by executing only about 72% of the prioritized test suite, thereby reducing the effort required in testing.

Conclusions

The fault-based prioritization approach is not only applicable to the instance empirically validated in this paper, but should also be adaptable to other fault-based testing strategies. We also envisage new research directions to be opened up by our work.     

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.     

Empirical studies of test‐suite reduction

Test‐suite reduction techniques attempt to reduce the costs of saving and reusing test cases during software maintenance by eliminating redundant test cases from test suites. A potential drawback of these techniques is that reducing the size of a test suite might reduce its ability to reveal faults in the software. Previous studies have suggested that test‐suite reduction techniques can reduce test‐suite size without significantly reducing the fault‐detection capabilities of test suites. These studies, however, involved particular programs and types of test suites, and to begin to generalize their results, further work is needed. This paper reports on the design and execution of additional studies, examining the costs and benefits of test‐suite reduction, and the factors that influence these costs and benefits. In contrast to previous studies, results of these studies reveal that the fault‐detection capabilities of test suites can be severely compromised by test‐suite reduction. Copyright © 2002 John Wiley & Sons, Ltd.     

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     

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.     

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.     

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.     

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.     

A dynamic code coverage approach to maximize fault localization efficiency

Spectrum-based fault localization is amongst the most effective techniques for automatic fault localization. However, abstractions of program execution traces, one of the required inputs for this technique, require instrumentation of the software under test at a statement level of granularity in order to compute a list of potential faulty statements. This introduces a considerable overhead in the fault localization process, which can even become prohibitive in, e.g., resource constrained environments. To counter this problem, we propose a new approach, coined dynamic code coverage (DCC), aimed at reducing this instrumentation overhead. This technique, by means of using coarser instrumentation, starts by analyzing coverage traces for large components of the system under test. It then progressively increases the instrumentation detail for faulty components, until the statement level of detail is reached. To assess the validity of our proposed approach, an empirical evaluation was performed, injecting faults in six real-world software projects. The empirical evaluation demonstrates that the dynamic code coverage approach reduces the execution overhead that exists in spectrum-based fault localization, and even presents a more concise potential fault ranking to the user. We have observed execution time reductions of 27% on average and diagnostic report size reductions of 77% on average.     

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

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

Test-suite reduction and prioritization for modified condition/decision coverage

Software testing is particularly expensive for developers of high-assurance software, such as software that is produced for commercial airborne systems. One reason for this expense is the Federal Aviation Administration's requirement that test suites be modified condition/decision coverage (MC/DC) adequate. Despite its cost, there is evidence that MC/DC is an effective verification technique and can help to uncover safety faults. As the software is modified and new test cases are added to the test suite, the test suite grows and the cost of regression testing increases. To address the test-suite size problem, researchers have investigated the use of test-suite reduction algorithms, which identify a reduced test suite that provides the same coverage of the software according to some criterion as the original test suite, and test-suite prioritization algorithms, which identify an ordering of the test cases in the test suite according to some criteria or goals. Existing test-suite reduction and prioritization techniques, however, may not be effective in reducing or prioritizing MC/DC-adequate test suites because they do not consider the complexity of the criterion. This paper presents new algorithms for test-suite reduction and prioritization that can be tailored effectively for use with MC/DC. The paper also presents the results of empirical studies of these algorithms.