搜索
ACMTransactionsonSoftwareEngineeringandMethodology(toappear)AnEmpiricalStudyofRegressionTestSelectionTechniquesToddL.GravesMaryJeanHarroldyJung-MinKimzAdamPorterxGreggRothermel{AbstractRegressiontestingistheprocessofvalidatingmodi edsoftwaretodetectwhethernewerrorshavebeenintroducedintopreviouslytestedcode,andprovidecon dencethatmodi cationsarecorrect.Sinceregressiontestingisanexpensiveprocess,researchershaveproposedregressiontestselectiontechniquesasawaytoreducesomeofthisexpense.Thesetechniquesattempttoreducecostsbyselectingandrunningonlyasubsetofthetestcasesinaprogram'sexistingtestsuite.Althoughtherehavebeensomeanalyticalandempiricalevaluationsofindividualtechniques,toourknowledgeonlyonecomparativestudy,focusingononeaspectoftwoofthesetechniques,hasbeenreportedintheliterature.Weconductedanexperimenttoexaminetherelativecostsandbene tsofseveralregressiontestselectiontechniques.Theexperimentexamined vetechniquesforreusingtestcases,focusingontheirrelativeabilitiestoreduceregressiontestinge ortanduncoverfaultsinmodi edprograms.Ourresultshighlightseveraldi erencesbetweenthetechniques,andexposeessentialtradeo sthatshouldbeconsideredwhenchoosingatechniqueforpracticalapplication.1INTRODUCTIONAsdevelopersmaintainasoftwaresystem,theyperiodicallyregressiontestit,hopingto nderrorscausedbytheirchanges,andprovidecon dencethattheirmodi cationsarecorrect.Tosupportthisprocess,developersoftencreateaninitialtestsuite,andthenreuseitforregressiontesting.Thesimplestregressiontestingstrategy,retestall,rerunseverytestcaseintheinitialtestsuite.Thisapproach,however,canbeprohibitivelyexpensive{rerunningalltestcasesinthetestsuitemayrequireanunacceptableamountoftime.Analternativeapproach,regressiontestselection,rerunsonlyasubsetoftheinitialtestsuite.Ofcourse,thisapproachisimperfectaswell{regressiontestselectiontechniquescanhavesubstantialcosts,andcandiscardtestcasesthatcouldrevealfaults,possiblyreducingfaultdetectione ectiveness.Thistradeo betweenthetimerequiredtoselectandruntestcasesandthefaultdetectionabilityofthetestcasesthatareruniscentraltoregressiontestselection.Becausetherearemanywaysinwhichtoapproachthistradeo ,avarietyoftestselectiontechniqueshavebeenproposed(e.g.,[1,4,7,8,12,15,20]).Althoughtherehavebeensomeanalyticalandempiricalevaluationsofindividualtechniques[4,18,20,21],toourknowledgeonlyonecomparativestudy,focusingononeaspectoftwoofthesetechniques,hasbeenreportedintheliterature[16].Wehypothesizethatdi erentregressiontestselectiontechniquescreatedi erenttradeo sbetweenthecostsofselectingandexecutingtestcases,andtheneedtoachievesucientfaultdetectionability.Becausetherehavebeenfewcontrolledexperimentstoquantifythesetradeo s,weconductedsuchastudy.Ourresultsindicatethatthechoiceofregressiontestselectionalgorithmsigni cantlya ectstheNationalInstituteofStatisticalSciences,andSoftwareProductionResearchDepartment,BellLaboratories,1000E.War-renvilleRd.,Naperville,IL60566,graves@bell-labs.com.yDepartmentofComputerandInformationScience,OhioStateUniversity,harrold@cis.ohio-state.edu.zDepartmentofComputerScience,UniversityofMarylandatCollegePark,jmkim@cs.umd.edu.xDepartmentofComputerScience,UniversityofMarylandatCollegePark,aporter@cs.umd.edu.{DepartmentofComputerScience,OregonStateUniversity,grother@cs.orst.edu.cost-e ectivenessofregressiontesting.Belowwereviewtherelevantliterature,describethetestselectiontechniquesweexamined,andpresentourexperimentaldesign,analysis,andconclusions.2REGRESSIONTESTINGSUMMARYANDLITERA-TUREREVIEW2.1RegressionTestingLetPbeaprocedureorprogram,letP0beamodi edversionofP,andletTbeatestsuiteforP.Atypicalregressiontestproceedsasfollows:1.SelectT0T,asetoftestcasestoexecuteonP0.2.TestP0withT0,establishingP0'scorrectnesswithrespecttoT0.3.Ifnecessary,createT00,asetofnewfunctionalorstructuraltestcasesforP0.4.TestP0withT00,establishingP0'scorrectnesswithrespecttoT00.5.CreateT000,anewtestsuiteandtestexecutionpro leforP0,fromT,T0,andT00.Eachofthesestepsinvolveimportantproblems.Step1involvestheregressiontestselectionproblem:theproblemofselectingasubsetT0ofTwithwhichtotestP0.Step3addressesthecoverageidenti cationproblem:theproblemofidentifyingportionsofP0oritsspeci cationthatrequireadditionaltesting.Steps2and4addressthetestsuiteexecutionproblem:theproblemofecientlyexecutingtestsuitesandcheckingtestresultsforcorrectness.Step5addressesthetestsuitemaintenanceproblem:theproblemofupdatingandstoringtestinformation.Althougheachoftheseproblemsissigni cant,werestrictourattentiontotheregressiontestselectionproblem.Notethatregressiontestselectionisapplicablebothincaseswherethespeci cationshavenotchanged,andwheretheyhavechanged.Inthelattercase,itisnecessarytoidentifythetestcasesinTthatareobsoleteforP0priortoperformingtestselection.(TestcasetisobsoleteforprogramP0ifandonlyiftspeci esaninputtoP0thatisinvalidforP0,ortspeci esaninvalidinput-outputrelationforP0.)Havingidenti edthesetestcasesandremovedthemfromT,regressiontestselectioncanbeperformedontheremainingtestcases.Notefurtherthattheidenti cationofobsoletetestcasesisnecessaryif