1Class 17• Questions/comments• Graders for Problem Set 6 (4); Graders for Problem set 7 (2-3) (solutions for all); will be posted on T-square• Regression testing, Instrumentation• Final project presentations: Dec 1, 3; 4:35-6:45• Assign (see Schedule for links) • Problem Set 7 discuss• ReadingsDiscussiony Mutation analysis and testingy Mutant operatory Mutatey Mutanty Killing mutantsy Mutation adequacyy Equivalent mutantsDiscussiony Regression testingy What is it?y What are scenarios in which it is used?y Test selectiony DejaVu algorithm?y Safety?y Precision?y Fault-revealing test cases?y Modification-revealing test cases?DejaVu Algorithmy Algorithm can be used at various levelsy Branches in CFGy Methods, procedures in programy Classesy UML diagramsy Other representations of program1. Construct representation G for Pif()doBdoAG12TFGeneral Test Selection with DejaVuG can bey low level—e.g., codey higher level—e.g., UML diagrams, state-transition diagrams, architectural diagramsy other information—e.g., CVS repositoryP can bey proceduraly object-orientedy databasey Web-basedy other1. Construct representation G for Pif()doBdoAG12TF2. Associate test cases in T with entities in GXt3Xe2Xe1t2t1TCedgeMGeneral Test Selection with DejaVuGG’Dangerous edge 3. Build G’ and compare G and G’ to find dangerous entitiesdoCdoB12 121. Construct representation G for Pif()doBdoAG12TF2. Associate test cases in T with entities in GXt3Xe2Xe1t2t1TCedgeMGeneral Test Selection with DejaVuGG’Dangerous edge 3. Build G’ and compare G and G’ to find dangerous entitiesdoCdoB12 121. Construct representation G for Pif()doBdoAG12TF2. Associate test cases in T with entities in GXt3Xe2Xe1t2t1TCedgeM4. Select test cases based on dangerous entitiesXt3Xe2Xe1t2t1TCedgeMGeneral Test Selection with DejaVuExecuteProgram PTest SuiteTAdd featuresImprove performanceTTAssessadequacyAssessoutcomeSelect Subset of T to RerunFAugment Tfor untestedadequacy requirementsIdentifyfaultsFModifyPÆP’Select subsetof T to rerunP’ Versionof PProgramPTT-T’T’T’T’Test-Suite Prioritization ProblemP’ Versionof PProgramPTT-T’T’T’T’Test-Suite Prioritization ProblemWhat if•T’ has too many test cases for allotted time?• want to run mostimportant test casesin T’ first?P’ Versionof PProgramPTT-T’T’T’What if•T’ has too many test cases for allotted time?• want to run mostimportant test casesin T’ first?SolutionOrder (prioritize) T’• find faults earlier• get coverage earlier•etc.T’Test-Suite Prioritization ProblemP’ Versionof PProgramPWhat if•T’ has too many test cases for allotted time?• want to run mostimportant test casesin T’ first?SolutionOrder (prioritize) T’• find faults earlier• get coverage earlier•etc.T’t1, t2,…,tnTest-Suite Prioritization ProblemP’ Versionof PProgramPWhat if•T’ has too many test cases for allotted time?• want to run mostimportant test casesin T’ first?SolutionOrder (prioritize) T’• find faults earlier• get coverage earlier•etc.Test-Suite Prioritization ProblemT’t1, t2,…,tnt1, t2,…,tnt1, t3,…,tn. . .t2, t1,…,tn. . .P’ Versionof PProgramPTest-Suite Prioritization ProblemT’t1, t2,…,tnt1, t2,…,tnt1, t3,…,tn. . .t2, t1,…,tn. . .What if•T’ has too many test cases for allotted time?• want to run mostimportant test casesin T’ first?SolutionOrder (prioritize) T’• find faults earlier• get coverage earlier•etc.Exponential:best orderingP’ Versionof PProgramPTest-Suite Prioritization ProblemT’t1, t2,…,tnt1, t2,…,tnt1, t3,…,tn. . .t2, t1,…,tn. . .What if•T’ has too many test cases for allotted time?• want to run mostimportant test casesin T’ first?SolutionOrder (prioritize) T’• find faults earlier• get coverage earlier•etc.Exponential:best orderingHeuristics:good orderingTest-Suite Prioritization ProblemGivenGivenT, a test suite PT, the set of permutations of T (prioritizationsprioritizations)f: PTÆReals (f yields prioritization award valueaward value)ProblemProblemFind T’ in PT such that for all T’’ in PT where T’’ does not equal T’, f(T’) > f(T’’) (i.e., find the best prioritization)y Increase likelihood of revealing faults earlier in regression testingy Increase likelihood of revealing high-risk faults earlier in regression testing y Increase likelihood of revealing regression errors for specific code changesy Increase code coverage earlier in regression testingObjectives for Test-suite Prioritizationy Increase likelihood of revealing faults earlier in regression testingy Increase likelihood of revealing high-risk faults earlier in regression testing y Increase likelihood of revealing regression errors for specific code changesy Increase code coverage earlier in regression testingObjectives for Test-suite PrioritizationPrioritizations We UsedT1 unorderedT2 randomT3 optimalT4 branch-totalT5 branch-additionalT6 FEP-totalT7 FEP-additionalT8 statement-totalT9 statement-additionalPrioritizations We UsedT1 unorderedT2 randomT3 optimalT4 branch-totalT5 branch-additionalT6 FEP-totalT7 FEP-additionalT8 statement-totalT9 statement-additionalFault Exposing Potential (FEP)The fault-exposing potential (FEP) for a statement s in a program P is the probability that, when Pis executed with a test, a fault at s will cause Pto failFault Exposing PotentialVoas developed the PIEPIE model for P and input distribution D as a measure of FEPE -- the probability that s will be executed by d, a random selection from DI -- the probability that the state at s will be changed by dP -- the probability that the modified state will propagate to output (cause a failure)Approximating FEPWe use mutation analysismutation analysis to approximate FEP In mutation analysismutation analysis, we create many versions of a program, each containing one syntactic change and try to “kill” the mutants with the test suiteThe mutation scoremutation score is the percentage of mutants “killed” by the test suiteAverage Percentage of Fault Detection (APFD)y Want to measure how rapidly a prioritized test suite detects faultsy We use a weighted average of the percentage of faults detected over the life of the test suite --average percentage of fault detectionaverage percentage of fault detection (APFD)y We think that higher APFD means a faster (better) fault detection rateExampleFaultTest1 2 3 4 5