Transcription
Program-basedMutation TestingCS 3250Software Testing[Ammann and Offutt, “Introduction to Software Testing,” Ch. 9.2]Spring 2022 – University of Virginia Praphamontripong1
Applying Syntax-Based Testing toPrograms Test requirements are derived from the syntax of softwareartifacts Syntax-based criteria originated with programs and havebeen used mostly with program source code BNF criteria are most commonly used to test compilers Use BNF criteria to generate programs to test all languagefeatures that compilers must process Mutation testing criteria are most commonly used for unittesting and integration testingSpring 2022 – University of Virginia Praphamontripong2
Instantiating Grammar-BasedTestingGrammar-Based TestingProgram-basedGrammarStringmutation Programmutation Valid strings Mutants arenot tests Must killmutants n Test howclassesinteract Valid strings Mutants arenot testsStringmutationGrammar FSMs Modelchecking Valid strings Traces aretests Must killmutants Includes OO InputvalidationtestingStringmutation Input validationtesting XML and others Invalid strings No groundstrings Mutants aretests XML andothers Valid andinvalid stringsSpring 2022 – University of VirginiaInput-Based Valid strings Praphamontripong3
revisitMutation Testing A process of changing the software artifact based on welldefined rules Mutation operators: Rules that specify syntacticvariations of strings generated from a grammar Rules are defined on syntactic descriptionsGrammars We perform mutation analysis when we want to makesystematic changes, resulting in variations of a validstringMutants: Result of one application ofa mutation operator We can mutate the syntax or objects developed from thesyntaxGrammarGround strings(Strings in the grammar)Spring 2022 – University of Virginia Praphamontripong4
Mutation Testing (Source Code) Inject changes into programs Strongest testing criterion Effective criterion for designing and evaluating tests Applied to C, C , Java, JavaScript, Java EE, PHP,Angular, SQL, Android, spreadsheet, policy, Premise:If the software has a fault, there usually are some mutantsthat can only be killed by a test that also detects that fault.Kill:The test makes the output of the original program differentfrom the output of the mutantSpring 2022 – University of Virginia Praphamontripong5
Mutation TestingFind last index of zeroEffectivetestsOriginalProgramint lastZero (int[] x) {for (int i x.length-1; i 0; i--) {if (x[i] 0)return i;i 0}return -1;}Input: x {1, 1, 2};Output original: -1Output mutant: -1IneffectiveIneffectivetestsSpring 2022 – University of VirginiaInput: x {0, 1, 2};Output original: 0Output mutant: -1Killed!Test x {0, 1, 2};Very effective at exploring theboundary case[Thanks to Professor Lin Deng, Towson University] Praphamontripong6
Mutation TestingA mutant is killed if there is a testcase for which the test results aredifferent from the original programSubjectprogramsKilling mutants à expose faultsRun tests onsubject programApplymutationoperatorsmutantsMust bevalid strings(compilable)Spring 2022 – University of eresult?yesRecordkilledmutantsRun tests onmutantsMutants are not tests, but used to find tests#test requirements # mutants Praphamontripong7
Mutation TestingSubjectprogramsA mutant is killed if there is a testcase for which the test results aredifferent from the original programMutation operators Rules that specify how to modify the code (mutate) Well designed operators result in powerful testsKilling mutants à expose faultsRun tests atorsmutantsMust bevalid strings(compilable)Spring 2022 – University of Virginiado one of two tasksKilling Mimic typical programmer mistakesmutant Encourage common test heuristicsGeneratetestsnoDistinguishableto result?yesWe use mutation testing Help testers design high quality tests EvaluatetheRun testsonquality of existing testsRecordkilledmutantsmutants# "# %& ' ()** ,Mutation scores # &-&. /#)0%* & "# %& 'Mutants are not tests, butused to find tests#test requirements # mutants Praphamontripong8
Killing MutantsGiven a mutant m Î M for a ground string program P and atest t, t is said to kill m if and only if the output of t on P isdifferent from the output of t on m. The quality of tests depends on mutation operators Different operators must be defined for different goals(and possibly for different programming languages) Testers add tests until all mutants have been killed A mutant is killed if there is a test case for which the testresults are different from the original programKilling mutants exposing faultsSpring 2022 – University of Virginia Praphamontripong9
Categories of Mutants Dead mutant A test case has killed it The fault that a dead mutant represents will be detected by thesame test that killed it Uncompilable mutant Syntactically illegal Should not be generated or should be immediately discarded Trivial mutant Almost every test can kill it (Functionally) equivalent mutant No test can kill it (same behavior or output as original, for allinputs) Infeasible test requirementsSpring 2022 – University of Virginia Praphamontripong10
Example: Program MutationOriginal methodA fault is introducedby mutating the codeMutantSpring 2022 – University of Virginia Praphamontripong11
Example: Program Mutation i 1 is a mutation of i 0 The code obtained bychanging i 0 to i 1 is calleda mutant of numZero A test kills the mutant if themutant yields differentoutputs from the originalcode Consider t1 {1, 0, 0} Original returns 2, mutant returns 2, the mutant is not killed Consider t2 {0, 1, 0} Original returns 2, mutant returns 1, the mutant is killedSpring 2022 – University of Virginia Praphamontripong12
Example 2Originalmethodmutant1Each mutated statement represents a separate programmutant2Spring 2022 – University of Virginia Praphamontripongmutant313
Example 2Consider the following tests t1 min(0, 0)mutant1 t2 min(0, 1) t3 min(1, 0)Which mutants will be killed bywhich tests?mutant2Spring 2022 – University of Virginia Praphamontripongmutant314
Example 2xymin m1m2m3t1000000t2010100t3100100mutant1 t1 kills none of the mutants t2 kills m1 t3 kills m1mutant2mutant3EquivalentmutantSpring 2022 – University of Virginia Praphamontripong15
Example 3With embedded mutantsReplace operatorOriginal methodMutant 4: force thetester to createtests that causeevery variable andexpression to havethe value of zeroSpring 2022 – University of Virginia1Immediate runtimefailure . If reached2Replace one variablewith another34Immediate runtimefailure if y 0, elsedoes nothing Praphamontripong16
Mutation CoverageMutation Coverage (MC): For each m Î M, TR containsexactly one requirement, to kill m. The RIPR model Reachability: the test causes the faulty (mutated) statement to bereached Infection: the test causes the faulty statement to result in anincorrect state Propagation: the incorrect state propagates to incorrect output Revealability: the tester must observe part of the incorrect output The RIPR model leads to two variants of mutation coverage:Strong mutation and Weak mutationSpring 2022 – University of Virginia Praphamontripong17
1. Strong Mutation CoverageStrong Mutation Coverage (SMC): For each m Î M, TRcontains exactly one requirement, to strongly kill m. Require RIPROutput of runninga test set on theoriginal programSpring 2022 – University of Virginia PraphamontripongOutput of runninga test set on amutant18
2. Weak Mutation CoverageWeak Mutation Coverage (WMC): For each m Î M, TRcontains exactly one requirement, to weakly kill m. Require RI-R Check internal state immediately after execution of the mutatedstatement If the state is incorrect, the mutant is killed A few mutants can be killed under weak mutation but not understrong mutation (no propagation) Incorrect state does not always propagate to the outputTest sets that weakly kill all mutants also strongly kill mostmutantsSpring 2022 – University of Virginia Praphamontripong19
Example (Mutant 1)Consider mutant 1Reachability: true123Infection: x yPropagation: (y x) falseFull test specification:true Ù (x y) Ù ((y x) false) (x y) Ù (y x)4 (y x)Test case value:(x 3, y 5) strongly kill, weakly kill mutant 1(x 5, y 3) weakly kill, but not strongly killSpring 2022 – University of Virginia Praphamontripong20
Example (Mutant 3)Consider mutant 3Reachability: trueInfection: (y x) ! (y v)1However, the previousstatement was v x23Substitute the infectioncondition, we get(y x) ! (y x)4“Logical contradiction”No input can kill this mutant “Equivalent mutant”Spring 2022 – University of Virginia Praphamontripong21
Designing Mutation OperatorsMutation Operators do one of two tasks: Mimic typical programmer mistakes Encourage common test heuristicsWhat are some of the common mistakes you may have made when writing programs?Spring 2022 – University of Virginia Praphamontripong22
Designing Mutation Operators (cont.)Mutation Operators do one of two tasks: Mimic typical programmer mistakes Encourage common test heuristicsResearchers design many operators, then experimentally Select the most useful operators Remove the redundant operatorsEffective Mutation Operators If tests that are created specifically to kill mutants created by acollection of mutation operators O {o1, o2, } also killmutants created by all remaining mutation operators with veryhigh probability, then O defines an effective set of mutationoperatorsSpring 2022 – University of Virginia Praphamontripong23
5forJavaMuJava operatorsExample:twoExample:Each arithmetic expression (andsubexpression) is modified by the functions1. ABS –– AbsoluteValue Insertion:MutationOperatorsabs(),and failOnZero().1.ABSnegAbs(),–– AbsoluteValue Insertion:MutationOpsfor Java ProgramsEach arithmetic expression (and subexpression) is modified by the functions2. AOR –– Arithmetic Operator Replacement:abs(), negAbs(), and failOnZero().Each occurrence of one of the arithmetic operators , ,*, , and % is2.AOR by––eachArithmeticOperatorreplacedof the otheroperators.Replacement:In addition, each is replaced by thespecial mutation operators leftOp, and rightOp.Each occurrence of one of the arithmetic operators , ,*, , and % isreplaced by each of the other operators. In addition, each is replaced by the3. ROR –– aop RelationalOperatorReplacement:leftOp(xy) xrightOp(x aop y) yExample:special mutation operators leftOp, and rightOp.Each occurrence of one of the relational operators ( , , , , , ) is replacedby ROReach of––theother operatorsand by Replacement:falseOp and trueOp.3.RelationalOperator1Each occurrence of2one of the relational operators ( , , , , , ) is replacedby each of the other3 operators and by falseOp and trueOp.Introduction to Software Testing (Ch 5) Ammann & Offutt4trueOp(x aop y) truefalseOp(x aop y) falseIntroduction to Software Testing (Ch 5) Ammann & Offutt[note: from slides[http://cs.gmu.edu/ offutt/mujava/mutopsMethod.pdf]by Amman & Offutt]Spring 2022 – University of Virginia Praphamontripong24
special mutation operators leftOp, and rightOp.Each occurrence of one of the arithmetic operators , ,*, , and % isreplaced by each of the other operators. In addition, each is replaced by the3. ROR –– aop RelationalReplacement:leftOp(xy) OperatorxrightOp(x aop y) yspecial mutation operators leftOp, and rightOp.Each occurrence of one of the relational operators ( , , , , , ) is replacedby ROReach of––theother operatorsand by Replacement:falseOp and trueOp.3.RelationalOperatorExample:Mutation Ops for Java ProgramsEach occurrence of one of the relational operators ( , , , , , ) is replacedby each of the other operators and by falseOp and trueOp.Introduction to Software Testing (Ch 5) Ammann & OffutttrueOp(x aop y) trueIntroductionto Software Testing (Ch 5)Example:falseOp(x aop y) false Ammann & Offutt[note: from slides by Amman & Offutt]512345[http://cs.gmu.edu/ offutt/mujava/mutopsMethod.pdf]Spring 2022 – University of Virginia Praphamontripong25
Example:Mutation Ops for Java ProgramSDL – Statement DeletionSDL deletes each executable statement by commenting them out. Itdoes not delete declarations.GeneralstatementdeletionSpring 2022 – University of Virginia[http://cs.gmu.edu/ offutt/mujava/mutopsMethod.pdf] Praphamontripong26
Example:Mutation Ops for Web AppsFOB – FailOnBackfailOnBack.js html body body onload “manipulatehistory()” script src “failOnBack.js” /script /html function manipulatehistory(){var currentpage window.document.toString();var currenturl window.location.href;var pageData window.document.toString();URL CURL CURL FURL PURL PURL 2URL 2URL 1URL 1// add a dummy url right before the current urlhistory.replaceState( pageData, “dummyurl”, “failonback.html” );history.pushState( currentpage,“currenturl”, currenturl);browserhistory}// update the page contentwindow.addEventListener( ‘popstate’, function(event) {window.location.reload(); });[https://eric.ed.gov/?id ED578113]Spring 2022 – University of Virginia Praphamontripong27
Example:Mutation Ops for Web AppsWSCR – Scopereplacement html jsp:useBean id id1 scope “page” class class1 / jsp:useBean id id1 scope “session” class class1 / /html WSIR – Sessioninitialization replacementPublic class logout extends HttpServlet{public void doGet( . ){session request.getSession(true);session request.getSession(false);.} }WSAD – SessionsetAttribute deletionPublic class logout extends HttpServlet{public void doGet( . ){session.setAttribute(attr1 , value1 );// session.setAttribute(attr1 , value1 );.} }[https://eric.ed.gov/?id ED578113]Spring 2022 – University of Virginia Praphamontripong28
Example:Mutation Ops for Android Apps OnClick Event Replacement (ECR) Replaces event handlers with other compatible handlermPrepUp.setOnClickListener (new OnClickListener() {publicv)v){ epTime(); } (); }decrementPrepTime});mPrepDown.setOnClickListener (new OnClickListener() {public void onClick (View v) {decrementPrepTime (); }}); OnTouch Event Replacement (ETR) Replaces OnTouch events, similar to ECR[https://cs.gmu.edu/ pring 2022 – University of Virginia Praphamontripong29
Mutation Testing in Practice Strongest test criterion but very difficult expensive to apply Subsumes other criteria by including specific mutation operators First-order mutation due to Competent programmers andcoupling effectDo fewer Selective mutation operatorsRemoving redundancyDo smarterAutomation Weak mutation Distributed execution Mutant generation Mutant executionDo faster SchemataSpring 2022 – University of Virginia Praphamontripong30
Summary Mutation is very effective – the “gold standard” of testing Used to evaluate other criteria Applied to various software artifacts, languages, frameworkswith different implementation and specific definition of mutationoperators Most expensive # test requirements # mutants Very difficult to apply by hand – need automation To improve the test process, use selective mutation operatorsSpring 2022 – University of Virginia Praphamontripong31
Instantiating Grammar-Based Testing Grammar-Based Testing Program-based Integration Model-Based Input-Based Compiler testing Valid and invalid strings Grammar Program mutation Valid strings Mutants are not tests Must kill mutants String mutation Input validation testing XML and others Valid strings Grammar Input .
