Today’s AgendaQuick ReviewRegression TestingWhat is it?Develop-Test-Release CycleRegression-Test ProcessA Simple ApproachMajor TasksExample (1)Example (2)The RTS Problem (1)The RTS Problem (2)Slide 13Main IdeaObtain Execution TracesCFGExecution TraceTest VectorSyntax TreeSelection StrategyProcedure SelectTestsMainExampleSlide 23MotivationSlide 25Slide 26The Set-Cover ProblemSlide 28A Greedy AlgorithmProcedure CMIMXSlide 31Slide 32Slide 33Residual CoverageProcedure PrTestSlide 36Slide 37SummaryToday’s AgendaQuick ReviewRegression TestingSoftware Testing and Maintenance 1Quick ReviewWhat is regression testing?Software Testing and Maintenance 2Software Testing and Maintenance 3Regression Testing Introduction Test Selection Test Minimization Test Prioritization SummarySoftware Testing and Maintenance 4What is it? Regression testing refers to the portion of the test cycle in which a program is tested to ensure that changes do not affect features that are not supposed to be affected.  Corrective regression testing is triggered by corrections made to the previous version; progressive regression testing is triggered by new features added to the previous version.Software Testing and Maintenance 5Develop-Test-Release CycleVersion 1 Version 21. Develop P 1. Modify P to P’2. Test P 2. Test P’ for new functionality3. Release P 3. Perform regression testing on P’ to ensure that the code carried over from P behaves correctly4. Release P’Software Testing and Maintenance 6Regression-Test Process1. Test revalidation/selection/ minimization/prioitization2. Test setup3. Test execution4. Output comparison5. Fault MitigationSoftware Testing and Maintenance 7A Simple Approach Can we simply re-execute all the tests that are developed for the previous version?Software Testing and Maintenance 8Major Tasks Test revalidation refers to the task of checking which tests for P remain valid for P’. Test selection refers to the identification of tests that traverse the modified portions in P’. Test minimization refers to the removal of tests that are seemingly redundant with respect to some criteria. Test prioritization refers to the task of prioritizing tests based on certain criteria.Software Testing and Maintenance 9Example (1) Consider a web service ZipCode that provides two services:ZtoC: returns a list of cities and the state for a given zip codeZtoA: returns the area code for a given zip code Assume that ZipCode only serves the US initially, and then is modified as follows:ZtoC is modified so that a user must provide a given country, as well as a zip code.ZtoT, a new service, is added that inputs a country and a zip code and return the time-zone.Software Testing and Maintenance 10Example (2) Consider the following two tests used for the original version:t1: <service = ZtoC, zip = 47906>t2: <service = ZtoA, zip = 47906> Can the above two tests be applied to the new version?Software Testing and Maintenance 11The RTS Problem (1)PP’obsoleteToredundantTuregression subsetTrregression testsTrTdnew testsTT’Functionality retained across P and P’Modified and newly added codeSoftware Testing and Maintenance 12The RTS Problem (2) The RTS problem is to find a minimal subset Tr of non-obsolete tests from T such that if P’ passes tests in Tr then it will also pass tests in Tu. Formally, Tr shall satisfy the following property: t  Tr and t’ Tu  Tr, P(t) = P’(t)  P(t’) = P’(t’).Software Testing and Maintenance 13Regression Testing Introduction Test Selection Test Minimization Test Prioritization SummarySoftware Testing and Maintenance 14Main Idea The goal is to identify test cases that traverse the modified portions.  Phase 1: P is executed and the trace is recorded for each test case in Tno = Tu  Tr. Phase 2: Tr is isolated from Tno by a comparison of P and P’ and an analysis of the execution tracesStep 2.1: Construct CFG and syntax treesStep 2.2: Compare CFGs and select testsSoftware Testing and Maintenance 15Obtain Execution Traces1. main () {2. int x, y, p;3. input (x, y);4. if (x < y)5. p = g1(x, y);6. else7. p = g2(x, y);8. endif9. output (p);10. end 11. }1. int g1 (int a, b) {2. int a, b;3. if (a + 1 == b)4. return (a*a);5. else6. return (b*b); 1. int g2 (int a, b) {2. int a, b;3. if (a == (b + 1))4. return (b*b);5. else6. return (a*a); Consider the following test set:t1: <x=1, y=3>t2: <x=2, y=1>t3: <x=1, y=2>Software Testing and Maintenance 16CFGStart123EndStart123EndStart123End41,23,45791,23461,2346fttfmaing1 g2Software Testing and Maintenance 17Execution TraceTest (t) Execution Trace (trace(t))t1 main.Start, main.1, main.2, g1.Start, g1.1, g1.3, g1.End, main.2, main.4, main.Endt2 main.Start, main.1, main.3, g2.Start, g2.1, g2.2, g2.End, main.3, main.4, main.Endt3 main.Start, main.1, main.2, g1.Start, g1.1, g1.2, g1.End, main.2, main.4, main.EndSoftware Testing and Maintenance 18Test VectorTest vector (test(n)) for node nFunction 1 2 3 4main t1, t2, t3 t1, t3 t2 t1, t2, t3g1 t1, t3 t3 t1 -g2 t2 t2 None -Software Testing and Maintenance 19Syntax Tree;input <xy x ymain.1=p callparamparam functionxy zmain.2==+ ba 1g1.1returna a*g1.2 and g2.3returnb b*g1.3 and g2.2Software Testing and Maintenance 20Selection Strategy The CFGs for P and P’ are compared to identify nodes that differ in P and P’.Two nodes are considered equivalent if the corresponding syntax trees are identical.Two syntax trees are considered identical when their roots have the same labels and the same corresponding descendants. Tests that traverse those nodes are selected.Software Testing and Maintenance 21Procedure SelectTestsMainInput: (1) G and G’, including syntax trees; (2) Test vector test(n) for each node n in G and G’; and (3) Set T of non-obsolete testsOutput: A subset T’ of TProcedure SelectTestsMain Step 1: Set T’ = . Unmark all nodes in G and in its child CFGs Step 2: Call procedure SelectTests (G.Start, G’.Start’) Step 3: Return T’ as the desired test setProcedure SelectTests (N, N’) Step 1: Mark node N Step 2: If N and N’ are not equivalent, T’ = T’  test(N) and return, otherwise go to the next step. Step 3: Let S be the set of successor nodes of N Step 4: Repeat the next step for each n  S. 4.1 If n is marked then return else repeat the following steps: