Selecting a Cost-E ective Test Case Prioritization Technique

1 Selecting a Cost-E ective Test case Prioritization TechniqueSebastian Elbaum, Gregg Rothermel,ySatya Kanduri,zAlexey G. Malishevsky,xJanuary 8, 2003 AbstractRegression testing is an expensive testing process used to validate modi ed software and detectwhether new faults have been introduced into previously tested code. To reduce the cost of regressiontesting, software testers may prioritize their test cases so that those which are more important, by somemeasure, are run earlier in the regression testing process. One goal of Prioritization is to increase atest suite's rate of fault detection. Previous empirical studies have shown that several prioritizationtechniques can signi cantly improve rate of fault detection, but these studies have also shown that thee ectiveness of these techniques varies considerably across various attributes of the program, test suites,and modi cations being considered.

2 This variation makes it di cult for a practitioner to choose anappropriate Prioritization Technique for a given testing scenario. To address this problem, we analyzethe fault detection rates that result from applying several di erent Prioritization techniques to severalprograms and modi ed versions. The results of our analyses provide insights into what types of prioriti-zation techniques are and are not appropriate under speci c testing scenarios, and the conditions underwhich they are or are not appropriate. Our analysis approach can also be used by other researchers orpractitioners to determine the Prioritization techniques appropriate to other IntroductionRegression testing is an expensive testing process used to validate modi ed software and detect whether newfaults have been introduced into previously tested case prioritizationtechniques help engineersexecute regression tests in an order that achieves testing objectives earlier in the testing process.

3 One testingobjective involvesrate of fault detection{ a measure of how quickly a test order detects faults. An improvedrate of fault detection can provide earlier feedback on the system under test, enable earlier debugging, andincrease the likelihood that, if testing is prematurely halted, those test cases that o er the greatest faultdetection ability in the available testing time will have been Prioritization techniques have been described in the research literature [5, 6, 8, 19, 23]. Studies[6, 18, 19] have shown that at least some of these techniques can signi cantly increase the rate of faultdetection of test suites in comparison to the rates achieved by unordered or randomly ordered test recently, researchers at Microsoft [21] have applied Prioritization to test suites for several multi-millionline software systems, and found it highly e cient even on such large systems.}

4 Department of Computer Science and Engineering, University of Nebraska { of Computer Science, Oregon State of Computer Science and Engineering, University of Nebraska { of Computer Science, Oregon State early indications of potential are encouraging; however, studies have also shown that the rates offault detection produced by Prioritization techniques can vary signi cantly with several factors related toprogram attributes, change attributes, and test suite characteristics [3, 4]. In several instances, techniqueshave not performed as expected. For example, one might expect that techniques that take into account thelocation of code changes would outperform techniques that simply consider test coverage without takingchanges into account, and this expectation is implicit in the Technique implemented at Microsoft [21].}}

5 Inour empirical studies [6], however, we have often observed results contrary to this expectation. It is possiblethat engineers choosing to prioritize for both coverage and change attributes may actually achieve poorerrates of fault detection than if they prioritized just for coverage, or did not prioritize at generally, to use Prioritization Cost-E ectively, practitioners must be able to assess which prioritiza-tion techniques are likely to be most e ective in their particular testing scenarios, , given their particularprograms, test cases, and modi cations. Toward this end, we might seek an algorithm which, given variousmetrics about programs, modi cations, and test suites, calculates and recommends the Technique most likelyto succeed.

6 The factors a ecting Prioritization success are, however, complex, and interact in complex ways[3]. We do not possess su cient empirical data to allow creation of such a general prediction algorithm, andthe complexities of gathering such data are such that it may be years before it can be available. Moreover,even if we possessed a general prediction algorithm capable of distinguishing between existing prioritizationtechniques, such an algorithm might not extend to additional techniques that may be this paper, therefore, we pursue an alternative approach. Using data obtained from the applicationof several Prioritization techniques to several substantial programs, we compare the performance of severalprioritization techniques in terms of e ectiveness, and show how the results of this comparison can be used,together with cost-bene t threshold information, to select a Technique that is most likely to be Cost-E then show how an analysis strategy based on classi cation trees can be incorporated into this approachand used to improve the likelihood of Selecting the most Cost-E ective results provide insight into the tradeo s between techniques, and the conditions underlying thosetradeo s, relative to the programs, test suites, and modi ed programs that we examine.

7 If these resultsgeneralize to other workloads, they could guide the informed selection of techniques by practitioners. Moregenerally, however, the analysis strategy we use demonstrably improves the Prioritization Technique selectionprocess, and can be used by researchers or practitioners to evaluate techniques in a manner appropriate totheir own testing rest of this article is organized as follows. Section 2 describes the test case Prioritization problem ingreater detail, presents a measure for assessing rate of fault detection and techniques for prioritizing tests ,and summarizes related work. Section 3 presents the details of our study, our results, and our approachesfor Selecting appropriate techniques. Section 4 presents further discussion of our results, and Test case PrioritizationRothermel et al.

8 [19] de ne the test case Prioritization problem and describe several issues relevant to itssolution; this section reviews the portions of that material that are necessary to understand this test case Prioritization problem is de ned as follows:The Test case Prioritization Problem:Given:T, a test suite;PT, the set of permutations ofT; andf, a function fromPTto the : FindT02 PTsuch that (8T00)(T002PT)(T006=T0)[f(T0) f(T00)].Here,PTrepresents the set of all possible prioritizations (orderings) ofT, andfis a function that, appliedto any such ordering, yields anaward valuefor that are many possible goals for Prioritization . In this article, we focus on increasing the likelihood ofrevealing faults earlier in the testing process.

9 This goal can be described, informally, as one of improving atest suite'srate of fault detection. To quantify this goal, [19] introduced a metric,APFD, which measuresthe weighted average of the percentage of faults detected over the life of the suite. APFD values range from0 to 100; higher numbers imply faster (better) fault detection a test suite containingntest cases, and letFbe a set ofmfaults revealed byT. LetTFibe the rst test case in orderingT0ofTwhich reveals faulti. The APFD for test suiteT0is given by the equation:APFD = 1 TF1+TF2+:::+TFmnm+12n(1)For example, consider a program with a test suite of ve test cases,AthroughE, such that the programcontains eight faults detected by those test cases, as shown by the table in Figure Consider two ordersof these test cases, orderT1:A{B{C{D{E, and orderT2:C{E{B{A{D.}}}}}}}}

10 Figures and show thepercentages of faults detected versus the fraction of the test suite used, for these two orders, area inside the inscribed rectangles (dashed boxes) represents the weighted percentage of faults detectedover the corresponding fraction of the test suite. The solid lines connecting the corners of the inscribedrectangles interpolate the gain in the percentage of detected faults. The area under the curve thus representsthe weighted average of the percentage of faults detected over the life of the test suite. Test orderT1 ( ) produces an APFD of 50%, and test orderT2 (Figure ) is a much \faster detecting" test order thanT1, (and in fact, an optimal order) with an APFD of Suite case Order: A B C D EPercent Detected FaultsArea = 50%1 2 3 4 5 6 7 8 9 10x xx x x xx x x x x x x x x x Suite FractionTest case Order: C E B A DPercent Detected FaultsArea = 84%A.