频谱缺陷定位中挑战与解决方案

SeekingforthePotofGoldattheEndoftheProgramSpectrumRainbow---频谱缺陷定位中挑战与解决方案ThelegendTheleprechaunsreburiedthegoldinpotsdeepundergroundallovertheisland.Whenrainbowsappear,theyalwaysendataspotwheresomeleprechaun'spotofgoldisburiedAutomatedFaultLocalizationDebuggingishardforhumans:weincreasinglyhavetoworkonandwithlargecodebasewrittenbyothers.Debuggingishardformachines:automatedrepairtechniquesrelyheavilyonautomatedfaultlocalisation.ProgramSpectrumandFaultLocalizationProgramspectrum:run-timeprofileAssociatedwitheachtestingresultGranularity:statements,branches,etc.Coverageinformation:binary(executionslice),executiontrace,etc.Testingresultforthetestcases:ProgramSpectrumandFaultLocalizationSince2001…ProgramSpectrumandFaultLocalizationJaccard……TarantulaOchiaiNaishCBIProgramSpectrumandFaultLocalizationJaccard……TarantulaOchiaiNaishCBIOK,itisanoldstory,but…Whichisthebest?定义：任意两个公式之间的关系FormulaR1isbetterthanformulaR2(R1→R2)R1R2ifforanyprogram,faultystatement,testsuiteandconsistenttie-breakingscheme,E1≤E2FormulaR1isequivalenttoformulaR2(R1↔R2)R1↔R2

ifforanyprogram,faultystatement,testsuiteandconsistenttie-breakingscheme,E1=E2TheoreticalFramework–Basis

TheoreticalFramework–BasisSBSFSA只与R的定义有关

TheoreticalFramework–BasisSB1SF1SA1SB2SF2SA2Assumeconsistenttie-breaking

TheoreticalFramework–BasisSB2SF2SA2SB1SF1SA1定理4：给定两个公式,如果其对应的程序语句子集存在反例使得相对应的子集间无确定包含关系，则R1

--\>R2，且R2

--\>R1TheoreticalFramework–Basis给定一定范围的公式集合，可以为其建立性能层次关系---例如基于35个公式的实例分析TheoreticalFramework–BasisER1M2AMPLEER3ER2OchiaiKulczynski2Wong3ER5GP2GP3GP196组等价公式StrictlybetterCover了过去20年的实验结论论文X.Xie(*),T.Y.Chen,F.-C.Kuo,B.W.Xu,ATheoreticalAnalysisofTheRiskEvaluationFormulasforSpectrum-BasedFaultLocalization,ACMTransactiononSoftwareEngineeringandMethodology,2013,Vol.22,No.4,pp.31:1-31:40.TheoreticalFramework–BasisHowtogeneralizedtheanalysis?Restricted,repeatedanalysis,sortofboring,seemstobeendless…Implication:给定任何一个公式，总能够找到它在给定公式集中的性能层次定位定义：Limitedmaximality---AriskevaluationformulaR1fromasubsetofformulas,S⊂F,issaidtobeamaximalformulaofS

ifforanyelementR2∈S,R2→R1impliesR2↔R1.定义：Maximality---AriskevaluationformulaR1fromasubsetofformulas,SissaidtobeamaximalformulainF,

ifforanydistinctformulaR2∈FsuchthatR2→R1impliesR2↔R1TheoreticalFramework–Generalization有限集无限集频谱坐标系：TheoreticalFramework–Generalization

给定P&TS(执行信息)，每个点上将会附结>=0个程序语句,这些语句所获得的risk值就是其所附结点的risk值；不同执行信息决定了每个点上所附结语句的密度

频谱坐标系中的FaultyBorder：wecallthesequentialpoints<(F,0),(F,1),…,(F,ep),…,(F,P)>为FaultyBorder，记为ETheoreticalFramework–GeneralizationFaultyBorder作用：singlefaultsf一定附结于FaultyBorder的某个点上，因为ef=FTheoreticalFramework–Generalization附在哪个点取决于sf的ep值-neverknowduetoinevitablecoincidentalcorrectness(不确定性1）而sf的ranking又取决于R对于sf所附结点所赋予的risk在所有faultyborder上点risk值的排名(不确定性2)每次都能排在top很难！

TheoreticalFramework–Generalization

TheoreticalFramework–GeneralizationER1M2AMPLEER3ER2OchiaiKulczynski2Wong3ER5GP2GP3GP19

TheoreticalFramework–Generalization

定理：ThereisnoformulathatisgreatestagainstthesetofallformulasF

GreatestFormula:ariskevaluationformulaRissaidtobeagreatestformulainFifforanydistinctformulaR’inF,itholdsthatRR’TheoreticalFramework–Generalization结论TheoreticalFramework–Generalization……………………MaximalMaximalMaximalUR为空，PR不同UR不为空，PR相同AssignUR点为最小值PR不变Generalizationisdone论文发表S.Yoo(*),X.Xie(*),F-C.Kuo,T.Y.Chen,M.Harman,HumanCompetitivenessofGeneticProgramminginSpectrum-BasedFaultLocalisation:TheoreticalandEmpiricalAnalysis,ACMTransactionsonSoftwareEngineeringandMethodology,2017,26(1),pp.4:1-4:30.TheoreticalFramework–GeneralizationSBFLinPracticeHuman-centricdisciplineHumanbeingsgetinvolvedineachactivitySBFLinPracticeConcludedobservationsSBFLinMoocTestonlyhelpstoimprove“completionrate”in“top-rankingcases”SBFLinMoocTestisNOThelpinginreducingtimecostTimecostsignificantlyincreaseswithinaccurateSBFLresultsFinallyreachaparticularareaandfixthebug.First,considercasewithoutSBFLAfirstcodescanFollowedbyseveralroundsofnavigationalongthroughallthecodelinessequentiallySBFLinPracticeNow,let’sconsiderSBFLAfirstcodescan,i.e.askimoftheentireorpartofthecodebeforeinspectingthetopDuringFollow-upbrowsing,i.e.allnavigationafter“firstscan”,programmersswitchbetweenthetopandothers.UntiltheyidentifythebugandfixitSBFLinPracticeSBFLinPracticeConcludedobservationsFirstscanispreservedinSBFLSBFLmayresultininsufficientfirstcodescan---couldbeharmfultotheefficiencyCarefulscanleadstobettercodecomprehension---inevitabletoefficientdebuggingSBFLleadstomorerevisitandlongertimetospendonsf,inordertodetectitAutomaticdebugging:highlightasuspiciousareafordevtofocusonAsquicklyaspossibleAssmallaspossibleSBFLinPractice!missagoodglobalunderstanding;!moretimetocompensate!Generallyunrealistic!Browsingcontextisindispensable论文发表X.Xie,Z.Liu,S.Song,Z.Chen,J.XuanandB.W.Xu,RevisitofAutomaticDebuggingviaHumanFocus-tracking,InternationalConferenceonSoftwareEngineering(ICSE),2016,pp.808-819SBFLinPracticeThelegendThereisnopotofgoldattheendoftherainbow……Walkthroughtherainbow,youwillhavenothingbuttherainbowNoendofthepoint,noultimatesolution沿途的风景也能胜过彼岸Wefounda``prac