3.1 Structural Criterion

Among all criteria, structural coverage is the mostly used one. In particular, a structural coverage criterion is defined as the percentage of structural units covered by a test case [136–142]. For example, the widely used structural coverage criterion is statement coverage, which measures to what extent a test case covers statements during test-case execution. Higher statement coverage indicates larger fault-detection capability because without covering faulty statements a test case cannot reveal the corresponding faults.

Besides statement coverage [29], some other structural units like functions/methods [30], blocks [67], and modified condition/decision [32] have also been considered as a type of structural coverage criterion.

Interestingly, the experiment results in the work of Rothermel et al. [29, 30] showed that in most cases, branch coverage outperformed statement coverage using a set of C programs. But in more recent work of Lu et al. [68], statement coverage usually performs best among these coverage criteria on a set of real-world Java programs. One potential reason could be that branches are less prevalent for the object-oriented Java programs than the procedural C programs, making branch coverage ineffective for Java.

3.2 Model-Level Criterion

Though structural criteria are widely used, sometimes, structural coverage can be unavailable for black-box or can be quite expensive to obtain for large systems. System models can capture the different behaviors of a system and there are some modeling languages proposed to model state-based software systems. Recently, model-based techniques have been adopted in software testing, such as test-case generation [143, 144], test-suite reduction [145], and test-case prioritization [117, 146–150]

Korel et al. [147] presented a novel test-case prioritization based on state-based models which execution information of the original and modified models is used for retesting the modified software system. Furthermore, Korel et al. [146] further proposed several model-based test-case prioritization heuristics and empirically investigated the improvements of these heuristics strategies. Xu and Ding [117] proposed an aspect-related test-case prioritization based on the incremental testing paradigm. Aspects are incremental modifications to the base classes, thus the tests targeting the aspects would be selected to execute first for they are more likely to detect the failures.

3.3 Fault-Related Criterion

As testing criteria are usually used to measure the fault-detection capability of a test case or a test suite, some researchers presented some fault-detection criteria directly because the preceding code-based coverage criteria cannot sufficiently assess the capability of a test case or a test suite [151–156].

In particular, Rothermel et al. [84] introduced mutation score to represent each test case's fault-exposing-potential, which regarded mutation-killing-capability as fault-detection-capability. Elbaum et al. [157] used the fault-index to estimate the fault proneness for each program unit, which had been proved effective in previous work [158, 159]. The calculation process of fault-index was as follows: (1), each function was associated with some measurable attributes; (2), all attribute values were standardized according to a group of baseline values; (3), the set would be reduced to a smaller one by principal components analysis [160]; (4), the left values were represented by a linear function which could generate one fault-index for each function in the program.

Ma and Zhao [125] proposed a new prioritization index called testing-importance of module (TIM), which consisted of two factors: fault proneness and importance of module, which acted as a new metric to measure the severe fault proneness for module covered by test cases. Lou et al. [95] seeded mutation on the changed code between versions to imitate the real faults introduced during software evolution. Therefore, the capability of killing these mutants can represent the capability of detecting real faults to some extent.

3.4 Test Input-Based Criterion

Since the structural coverage, model information and mutation analysis can be costly to obtain, recently researchers started to measure the fault-detection capability of test cases based on the input data alone rather than the execution information of test cases. That is, this type of criteria measures the fault-detection capability by calculating the difference between test input data, which are usually regarded as strings or vectors.

In particular, Ledru [161] proposed a prioritization approach which compared the string distance between test cases with a greedy algorithm. Chen et al. [162] proposed a test-vector-based approach to prioritizing test programs for compilers by analyzing the extracted features of test programs to solve the efficiency problem of compiler testing [163]. Recently, Chen et al. [164] proposed to predict the bug-revealing probabilities per unit time of test programs for compilers via machine learning, and schedule the execution order of these test programs based on the descending order of these bug-revealing probabilities per unit time. Chen et al. [89] transformed test cases into a form of vectors for clustering. Jiang et al. [165] proposed a novel family of input-based prioritization techniques, which calculates the difference between test cases by three types of distance functions.

3.5 Change Impact-Based Criterion

Change information are also used very frequently in prioritization criteria [166, 167]. For example, the modified condition mentioned in structural unit level criteria also used the change information during program evolution. However, there is a category of criteria analyzing the change code in a more specific way, so this section introduce these criteria individually.

Haraty et al. [168] proposed a clustering prioritization approach based on code change relevance, which mainly prioritized clusters of test cases based on their relevance to code changes. Alves et al. [169] proposed a refactoring-based approach to prioritizing tests for detecting refactoring bugs. The approach first collected the change edits between two versions of a program and then analyzed the change impact based on a number of refactoring fault models to determine the execution order of test cases.

Panda et al. [170] presented a static analysis approach to prioritizing test cases based on affected component coupling of object-oriented programs. It first constructed affected slice graph whose nodes had different fault-proneness and then scheduled execution order based on the nodes covered by each test case.

3.6 Other Criteria

Besides, some studies are hard to categorize into aforementioned categories.

4.1 Greedy Algorithm

Greedy algorithms are widely used to address the test-case prioritization problem, which focus on always selecting the current “best” test case during test-case prioritization. The greedy algorithms can be classified into two groups. The first group aims to select tests covering more statements, whereas the second group aims to select tests that is farthest from the selected tests.

Regarding to the first group, the most popular greedy algorithms are the total and additional algorithms. In particular, the total algorithm prioritizes test cases based on the descendent order of statements covered by each test case, whereas the additional algorithm prioritizes test cases based on the descendent order of statements that are covered by each unselected test case but uncovered by the existing selected test cases. As the total and additional algorithms can have best performance in different cases, Zhang et al. [174, 175] proposed a unified prioritization model, which uses a probabilistic model to bridge the gap between the total and additional algorithms so that the total and additional algorithms can be regarded as its two extreme instances. Moreover, this model yields a spectrum of specific prioritization algorithms between the total and additional algorithms. Besides, Li et al. [72] proposed the 2-optimal strategy which was based on K-optimal algorithm [176] where K = 2. Different from approaches mentioned above, the 2-optimal approach tries to select “next two best” test cases according to coverage ability of each pair of test cases.

Regarding to the second group, the typical greedy algorithm is adaptive random test-case prioritization [177], which is proposed based on adaptive random testing [178, 179]. In particular, it first iteratively generates a candidate set of test cases and selects one test case based on a selecting algorithm. The selecting algorithm aims to select a test case that is the farthest from the already selected test cases based on a distance definition function f1 and a farthest selection function f2. In particular, this work proposed to use Jaccard distance to define f1 and defined three types of selection function f2.

The greedy algorithms focus on searching the local optimal solution to prioritization, and thus their prioritization results may not be the optimal solution.

4.2 Search-Based Algorithm

Since the prioritization problem is an NP-hard problem, greedy algorithms can not always obtain the optimal solution within the solution space. Therefore, some search-based algorithms are applied to solve the prioritization problem, aiming to achieve better prioritization results with acceptable computation cost.

In particular, Li et al. [72] applied meta-heuristic search-based algorithms to test-case prioritization. That is, they applied steepest ascent hill-climbing and genetic algorithms. In particular, steepest ascent hill climbing is a local search algorithm, where each test permutation is regarded as a state. This algorithm iteratively switches to best state among all neighbors of the current state. The genetic algorithm [72] is based on the processes of natural selection according to Darwinian theory of biological evolution. In this algorithm, each test sequence is encoded in an N-sized array representing an instance of chromosome. In the initial step, a group of test sequences is generated randomly as the initial individuals. Iteratively, a new generation is generated by combining selected individuals guided by the fitness function. The whole search process will be terminated until certain requirement is satisfied.

Besides the traditional single-objective test-case prioritization, there is another form of test-case prioritization problem, called multiobjective test-case prioritization. Given a test suite T, the set of T′s permutations PT, and a vector of M objective functions, f_i(i = 1, 2, …, M), multiobjective test-case prioritization aims at finding $T\prime \subset PT$ such that T′ is a Pareto-optimal permutation set with respect to the objective functions, f_i(i = 1, 2, …, M). The objective functions usually are some important prioritization criteria. Pareto-optimal means that strategy A improves strategy B without making things worse.

Epitropakis et al. [180] investigated multiobjective test-case prioritization through three objectives: average percentage of coverage, average percentage of coverage of changed code, and average percentage of past fault coverage and evaluated the fault-detection capabilities in the experiment.

Solving multiobjective problem in software engineering by multiobjective evolutionary algorithms usually faces with the challenge of scalability problem due to the population size and iterations. Therefore, Li et al. [181] proposed a novel GPU-based parallel fitness evaluation algorithm for test-case prioritization, which implemented the fitness evaluation and crossover computation by graphic processing units on GPU.

Overall, the characteristics of search-based prioritization algorithms lie in searching for the optimal solution guided by the predefined fitness function within the searching space.

4.3 Integrate-Linear-Programming-Based Algorithm

Integrated linear programming (abbreviated as ILP) is a mathematical optimization or feasibility program where all the variables, objective functions, and constraints are linear, which is an NP-hard problem. Recently, researchers applied ILP to describe the problem of test-case prioritization and thus the solutions to the ILP formula are the prioritization results. That is, the problem of test-case prioritization is transformed into formula construction and solving process.

In particular, Zhang et al. [82] firstly applied ILP to solve time-aware test-case prioritization. In particular, this approach first selects a set of test cases by solving the ILP formula describing time-aware test-case prioritization, and then prioritizes selected test cases through some greedy strategies. Recently, to investigate the bound of coverage-based test-case prioritization, Hao et al. [182] used ILP to represent coverage-based test-case prioritization so as to learn the performance of optimal coverage-based test-case prioritization techniques.

4.4 Information-Retrieval-Based Algorithm

Information retrieval (abbreviated as IR) techniques [183] aim to obtain information needed from a collection of information resources, which have been fully studied in the last 40 years and applied to various domains, including software engineering. The main idea of information-retrieval-based algorithm is as follows: (1) it uses test case information such as execution information or source code of each test case to construct the corresponding document collection for each test case, namely, each document represents one test case; (2) it uses source code information (usually the changed part of source code) serving as the input query of IR, and IR will return a ranked list of the documents constructed in the first step, which in fact is a ranked list of test cases by the relevance to the input information.

In particular, Nguyen et al. [184] proposed an IR-based approach to prioritizing test cases for web services, which used the identifier documents extracted from the execution trace to represent each test case and used the web service change description as the input query of IR.

Kwon et al. [185] proposed an IR-based approach which adapted term frequency (TF) and inverse document frequency (IDF) to prioritize test cases. This approach considers not only code coverage information but also how many times a coverage element is executed by a test case (TF) and source code elements are tested by few test cases (IDF). Linear regression model is applied to weigh the value of the information.

Later on, Saha et al. [186] proposed an IR-based approach to prioritize JUnit test cases. Their approach used the test source code to construct the relative document for each test case and used the changed code of the program under test as the input query to get a ranked list of test cases by their relevance to program changes.

4.5 Machine-Learning-Based Algorithm

Machine learning is a data-analysis technique that builds a model from sample input to make prediction for new data. Typically, machine learning techniques consist of supervised learning and unsupervised learning (called clustering as well).

Tonella et al. [133] presented a machine-learning-based test-case prioritization approach which incorporated user knowledge by case-based ranking model. This approach used the indicator of priority, which was defined by user cases, and test case information such as coverage and fault proneness metrics as features to train a model to predict the priority of test cases. Chen et al. [162] proposed a test-vector based approach to prioritizing test programs for compilers, which did not need to collect coverage information but only analyze necessary features from each test program itself to prioritize test programs for compilers. More recently, Chen et al. [164] developed LET (short for learning to test), which learned from existing test programs to accelerate future test execution. LET first designed and extracted a lot of features from the source code of test programs (e.g., address features and pointer comparison features). Then, LET trained a capability model to predict the bug-revealing probability of each new test program, and a time model to predict the execution time of each new test program, based on these features. Finally, LET prioritized new test programs as the descending order of their bug-revealing probabilities in unit time.

5.1 APFD

Rothermel et al. [29] proposed the first measurement for assessing the effectiveness of test-case prioritization, which is called weighted average of the percentage of faults detected (APFD). APFD measures how rapidly a prioritized test suite detects faults. Higher APFD values mean faster fault-detection rates. Formula (1) shows how to calculate APFD values for a test-case prioritization technique. In this formula, TF_j refers to the first test case in prioritized test suite that detects the jth fault, n refers to the number of test cases, and m refers to the number of faults detected by the test suite. APFD has already become one of the most widely used measurements for assessing the performance of test-case prioritization in the literature [71].

$\begin{array}{l}\hfill \text{APFD}=1-\frac{\sum _{j=1}^{m}T{F}_j}{nm}+\frac{1}{2n}\end{array}$

5.2 AFPD_C

Actually, APFD does not reflect the practical performance of test-case prioritization, since it ignores the influence of test execution costs and fault severity. Therefore, Elbaum et al. [33] further proposed another measurement to measure the practical performance of test-case prioritization by considering the influence of the two factors, which is called cost-cognizant weighted average percentage of faults detected (APFD_C). APFD_C is actually adapted from APFD, which is defined as Formula (2). In this formula, f_i refers to the severity of the ith fault detected by the prioritized test suite, and t_j refers to the test cost of the jth test case in the prioritized test suite.

$\begin{array}{l}\hfill {\text{APFD}}_C=\frac{\sum _{j=1}^m\left(f_i*\left(\sum _{i=T{F}_j}^n{t}_i-\frac{1}{2}*t_{T{F}_j}\right)\right)}{\sum _{j=1}^n{t}_j*\sum _{j=1}^m{f}_j}\end{array}$

In practice, it tends to be quite difficult to know the severity of each fault in advance. Therefore, a simplified APFD_C is usually used to measure the performance of test-case prioritization by treating all faults as sharing the same severity [180]. The simplified APFD_C is shown as Formula (3).

$\begin{array}{l}\hfill {\text{APFD}}_C(\text{simplified})=\frac{\sum _{j=1}^m\left(\sum _{i=T{F}_j}^n{t}_i-\frac{1}{2}*t_{T{F}_j}\right)}{\sum _{j=1}^n{t}_j*m}\end{array}$

5.3 APXC

In order to measure the performance of test-case prioritization before test-case execution, researchers [72, 182] also proposed to leverage the average percentage of some structural coverage (abbreviated as APXC) as a measurement. APXC has the similar formula with APFD. For APXC, TF_j in Formula (1) refers to the first test case in prioritized test suite that covers structural units (e.g., statement and block) j, and m refers to the total number of structural units covered by the test suite. In particular, higher APXC values mean faster coverage rates.

According to the general definition of APXC, we may have APBC to measure the rate at which a prioritized test suite covers the blocks, APSC to measure the rate at which a prioritized test suite covers the statements. Such measurements are defined based on structural units, which are not the ultimate goal. Therefore, they are actually widely used as an intermediate goal (e.g., fitness function) during search-based test-case prioritization to guide test-case prioritization, rather than as a measurement for the performance of test-case prioritization.

5.4 WGFD

Higher APFD values mean faster fault detection. However, the problem is how to define “fastness.” In different testing scenarios, “fastness” tends to have different definitions. Therefore, Lv et al. [187] proposed a new generalized measurement from a control theory viewpoint, which is called the weighted gain of faults detected (WGFD). The basic idea is to weight and sum fault-detection rates of different test cases so as to define “fastness” in different testing scenarios. That is, since the number of test cases detected at different time should have different impact on measuring the performance (fastness) of a prioritization technique, different weights should be assigned to the fault-detection rates of different test cases. In particular, WGFD is defined in Formula (4), where n refers to the number of test cases in the test suite, r(i) refers to the fault-detection rate of test case i, and w(i) refers to the assigned weight to the fault-detection rate of test case i.

$\begin{array}{l}\hfill \text{WGFD}=\sum _{i=1}^{n}w(i)*r(i)\end{array}$

5.5 HMFD

According Formula (1), the APFD measure increases as the size of the test suite increases. In other words, APFD is affected by the size of a given test suite. To relieve this issue of APFD, Zhai et al. [99] proposed a new measurement to measure how quickly a prioritized test suite can detect faults, which is independent from the size of a given test suite. The new measurement is called the harmonic mean of the rate of fault detection (HMFD). In particular, HMFD is defined as Formula (5), where TF_j refers to the first test case in the prioritized test suite that detects the ith fault, and m is the number of faults detected by the test suite. Note that low HMFD values mean better performance of test-case prioritization.

$\begin{array}{l}\hfill \text{HMFD}=\frac{m}{\sum _{j=1}^m\frac{1}{T{F}_j}}\end{array}$

5.6 NAPFD and RAPFD

In practice, there may be various constraints in test-case prioritization. Due to the existence of practical constraints in test-case prioritization, not all of the faults can be detected by a given test suite. Moreover, we may not execute the same number of test cases. Walcott et al. [188] proposed to assign a penalty to the missing faults so as to solve the first problem. In addition, Qu et al. [189] proposed normalized APFD (abbreviated as NAPFD) to measure the performance of test-case prioritization in order to solve the two problems. In particular, NAPFD is defined as Formula (6), where p refers to the value that is calculated by dividing the number of faults detected by the prioritized test suite by the number of faults detected by the full test suite. To further improve these measurements, Wang and Chen [190] proposed the relative average percent of faults detected (RAPFD) by considering the given testing resource constraint, which determines how many test cases could be run. Furthermore, Do and Rothermel [191, 192] further proposed many improved cost–benefit models for assessing regression testing methodologies (including test-case prioritization). In particular, these models incorporate context factors (e.g., the costs of some essential testing activities such as test setup and obsolete test identification) and lifecycle factors (e.g., the costs and benefits for techniques across system lifetimes).

$\begin{array}{l}\hfill \text{NAPFD}=p-\frac{\sum _{j=1}^{m}T{F}_j}{nm}+\frac{p}{2n}\end{array}$

6.1 Time Constraint

The mostly studied constraint in test-case prioritization is the time constraint, also called time budget [188]. Ideally, all the test cases in the prioritized test suite are expected to be executed during the process of software testing, so as to avoid fault-detection capability loss of the test suite. However, under the practical environment of software testing, the allowed testing time may not be quite sufficient, which causes that the prioritized test suite may not be totally executed. For example, in some companies, software testing is just allowed in night [188, 194], and thus if the time of executing the whole test suite is more than one night, some prioritized test cases will not be executed. Besides, new software development processes, e.g., extreme programming, also advocate a short testing cycle. Therefore, on this occasion, the time constraint is quite necessary to be considered when prioritizing test cases.

To make test-case prioritization more effective given the allowed testing time, various approaches have been proposed to select only a subset of test cases and schedule their execution order rather than all the test cases. Walcott et al. [188] proposed time-aware test-case prioritization. More specifically, they used a genetic algorithm to prioritize test cases in order to achieve two goals. The first goal is to ensure that the prioritized test cases can be executed within the given testing time. The second goal is to make the prioritized test cases achieve the largest fault-detection capability. To achieve the same goals, Alspaugh et al. [195] proposed to use 0/1 knapsack solvers to prioritize test cases, including greedy, dynamic programming, and the core algorithms. Zhang et al. [82] identified that time-aware test-case prioritization implied to select a subset of test cases from the test suite for prioritization. Therefore, they proposed to combine test-case selection and test-case prioritization to achieve the goals of time-aware test-case prioritization. More specifically, they first used integer linear programming [196] to select a subset of test cases that can achieve the maximum test coverage within the time budget, and then applied traditional test-case prioritization techniques to schedule the execution order of the selected test cases. Note that, in this way, the traditional total technique and the traditional additional technique are both adapted to be time-aware total technique and time-aware additional technique. Later on, Suri et al. [197] also applied ant colony optimization to prioritize test cases in the time constraint environment.

Based on the existing research [188, 191], considering the time constraint in test-case prioritization may influence the costs and benefits of test-case prioritization techniques. Do et al. [198] conducted a series of experiments to investigate such influence. Their experimental results demonstrated that the time constraint indeed has a significant influence on the cost-effectiveness of test-case prioritization techniques. Furthermore, You et al. [199] conducted an empirical study to investigate whether the time cost of each test case influences the effectiveness of time-aware test-case prioritization. Their experimental results showed that the effectiveness of the prioritization techniques considering the time cost of each test case has no significant difference with that of the prioritization techniques omitting the time cost of each test case. That is, it tends to be not worth considering the time cost of each test case for time-aware test-case prioritization. In addition, Marijan [38] proposed a framework for optimal test-case prioritization in the time constraint environment by integrating three different perspectives, including business perspective, performance perspective, and test design perspective. More specifically, from a business perspective, failure impact is regarded as an important factor influencing test effectiveness; from a performance perspective, test execution time is regarded as an obvious factor of test effectiveness; from a technical perspective, both failure frequency and cross-functionality are regarded as important factors of test effectiveness. In particular, failure frequency refers to a measure of how often test cases detect failures, and cross-functionality refers to a measure of how much the functionality of the system under test is covered by a test case.

6.2 Fault Severity

Another widely studied constraint in test-case prioritization is fault severity. The fault severity reflects the costs or resources required if a fault persists in and influences the users/organization/developers. The existing test-case prioritization is based on the assumption that the severity of all the faults are considered equally. However, the assumption may not hold in practice, and thus the fault severity is also a practical constraint for test-case prioritization.

Elbaum et al. [33] firstly considered the fault severity constraint when measuring the effectiveness of test-case prioritization techniques. Park et al. [200] proposed to prioritize test cases by considering fault severity. In particular, they estimate the current fault severity using history information. Actually, their approach has an assumption, i.e., test costs and fault severities are not largely changed from one version to a later version. Malishevsky et al. [201] adapted traditional test-case prioritization (e.g., the total technique and the additional technique) to cost-cognizant test-case prioritization by considering the fault severity constraint and the time cost of each test case. Huang et al. [108] also proposed a history-based cost-cognizant test-case prioritization. More specifically, their approach collected the historical records from the latest regression testing and then used a genetic algorithm to schedule the most effective execution order of test cases.

6.3 Other Constraints

Besides, resource (e.g., hardware resource) is also a constraint in test-case prioritization. Kim and Porter [193] proposed a test-case prioritization based on history information by considering the resource constraint and time constraint. That is, they assigned a selection probability for each test case based on history information, and selected a test case to run based on these probabilities until testing time is exhausted. More specifically, their utilized history information contains the execution history of each test case, the corresponding fault detection, and/or the covered program entities. Wang et al. [88] proposed a resource-aware multiobjective optimization solution to produce an optimal execution order of test cases by considering the resource constraint and the time constraint. In the multiobjective optimization solution, they defined a fitness function based on four cost-effectiveness measures, including (1) minimizing the time for executing prioritized test cases and allocating relevant test resources; (2) maximizing the number of test cases to be executed; (3) maximizing the usage of available test resources; and (4) maximizing fault-detection achieved by prioritized test cases.

Furthermore, there are some other constraints, e.g., testing requirement priorities and the request quotas of web service. To prioritize test cases by considering testing requirement priorities, Zhang et al. [127] proposed to utilize test history information to evaluate the priorities of test cases so as to prioritize test cases based on them. Here various types of code elements can be regarded as testing requirements, e.g., statements, basic blocks, methods; or features and attributions of system; or faults in system. About the constraint of the request quotas of web service (e.g., the upper limit of the number of requests that a user can send to a Web Service during a certain time range), Hou et al. [121] proposed quota-constrained test-case prioritization for service-centric systems by maximize testing requirement coverage. More specifically, they first divided the testing time into time slots, and then selected and prioritized test cases for each slot by using integer linear programming.

7.1 General Test-Case Prioritization

Given a program P and its corresponding test suite T, general test-case prioritization [68–70, 84, 202] computes test execution order valid for a number of subsequent modified revisions of P. Therefore, they are usually based on general program/test information shared by various revisions, e.g., the set of program elements covered by each test.

For example, if test t₁ covers more program elements than t₂ on one program revision, the same may still hold for later program revisions. Therefore, traditional test-case prioritization techniques based on coverage information, e.g., the total/additional [84, 157], adaptive-random-testing-based [177], and search-based techniques [72], can all be directly utilized for general test-case prioritization.

When prioritizing using coverage information obtained from historical revisions, software changes and test additions could make test-case prioritization techniques ineffective since coverage information can be obsolete (due to software changes) or absent (for newly added tests) during the software evolution. To study the impacts of software changes and test additions for general test-case prioritization, Lu et al. [68] recently performed a study on real-world evolving GitHub projects. The study results demonstrate that software changes do not impact general test-case prioritization much, whereas test additions, which incur tests without coverage information, may significantly impact the effectiveness of general test-case prioritization. The study provides practical guidelines for determining the intervals of applying general test-case prioritization—general test-case prioritization should be reapplied whenever there are nontrivial number of added tests.

7.2 Version-Specific Test-Case Prioritization

Given a program P and its corresponding test suite T, version-specific test-case prioritization [66, 95, 146, 186] computes optimal test execution orderings specifically for P′, the next revision of P. Version-specific test-case prioritization is performed after changes have been made to P and prior to regression testing of P′. The prioritized test suite may be more effective for testing P′ than that computed by general test-case prioritization, but may be inferior on average on a succession of subsequent releases of P.

In the literature, researchers have also applied traditional coverage-based test-case prioritization techniques to the version-specific scenario. Furthermore, since regression faults are mainly due to software changes, researchers have also proposed various version-specific test-case prioritization techniques [66, 95, 146, 186] based on the detailed change information during software revision for more effective test-case prioritization. For example, Srivastava and Thiagarajan [66] analyzed the binary-level basic block changes to execute tests covering more changes earlier for faster regression fault detection. Korel et al. [146] analyzed the system models and computed model-level modifications for precise version-specific test-case prioritization. Lou et al. [95] presented a mutation-based version-specific test-case prioritization technique, which simulates faults occurred in software evolution by mutants on the change and prioritizes test cases based on their killing information on these simulation faults. Recently, Saha et al. [186] transformed the version-specific test-case prioritization problem into an information retrieval problem by treating source-code level changes as queries and test-case source code as documents. Then, the tests with more textual similarities with software changes are executed earlier to detect regression bugs faster.

8.1 Studies on Traditional Dynamic Prioritization

Due to the dominant position of traditional dynamic test-case prioritization techniques, the vast majority of studies explore various factors around these techniques.

Rothermel et al. [84] empirically compared various dynamic test-case prioritization techniques (including coverage-based and mutation-based techniques) against unordered or randomized test suites on a suite of C programs. Later on, Elbaum et al. [33] further studied the impacts of fault severities and test execution time on test-case prioritization. Elbaum et al. [157] also investigated the impacts of program versions, program types, and different coverage granularities on test-case prioritization on C programs. Do et al. [203] performed the first study of test-case prioritization on JUnit tests for Java programs. The study demonstrated the effectiveness of dynamic test-case prioritization on Java programs besides C programs, and also revealed divergent behaviors of test-case prioritization on Java and C programs. Do et al. [198] also investigated the effect of time constraints on the cost-effectiveness of test-case prioritization, as well as demonstrating the validity of using mutation faults for test-case prioritization experiments [156, 204]. Recently, Lu et al. [68] investigated the impacts of real-world software evolution on test-case prioritization and found that code changes do not impact the effectiveness of test-case prioritization much while test additions can significantly lower the effectiveness of traditional dynamic test-case prioritization.

In terms of effectiveness, various studies have confirmed that the traditional additional [84] and search-based [72] test-case prioritization techniques represent the state of the art [68, 72, 174, 177].

8.2 Comparison With Traditional Dynamic Techniques

Besides the traditional dynamic test-case prioritization techniques, researchers have also proposed various other test-case prioritization techniques. In the next, we present two recent but important studies comparing traditional dynamic test-case prioritization with other static or black-box techniques.

9.1 Existing Issues

In this section, we discuss the existing issues in test-case prioritization through three aspects—criteria, measurements, and empirical studies.

9.2 Other Challenging Problems

Besides these issues in the current work, test-case prioritization, test-case prioritization also suffers from other challenging problems.

Acknowledgments

This work is supported in part by NSF Grant No. CCF-1566589, UT Dallas faculty start-up fund, Google Faculty Research Award, Samsung GRO Award, and generous supports from Huawei, the National Key Research and Development Program 2016YFB1000801, and the National Natural Science Foundation of China under Grant No. 61522201.