This paper presents EXE, an effective bug-finding tool that automatically generates inputs that crash real code. Instead of running code on manually or randomly constructed input, EXE runs it on symbolic input initially allowed to be “anything.” As check
EXE:AutomaticallyGeneratingInputsofDeath
CristianCadar,VijayGanesh,PeterM.Pawlowski,DavidL.Dill,DawsonR.Engler
ComputerSystemsLaboratory
StanfordUniversityStanford,CA94305,U.S.A
{cristic,vganesh,piotrek,dill,engler}@cs.stanford.eduABSTRACT
ThispaperpresentsEXE,ane ectivebug- ndingtoolthatautomaticallygeneratesinputsthatcrashrealcode.Insteadofrunningcodeonmanuallyorrandomlyconstructedinput,EXErunsitonsymbolicinputinitiallyallowedtobe“any-thing.”Ascheckedcoderuns,EXEtrackstheconstraintsoneachsymbolic(i.e.,input-derived)memorylocation.Ifastatementusesasymbolicvalue,EXEdoesnotrunit,butinsteadaddsitasaninput-constraint;allotherstatementsrunasusual.Ifcodeconditionallychecksasymbolicex-pression,EXEforksexecution,constrainingtheexpressiontobetrueonthetruebranchandfalseontheother.Be-causeEXEreasonsaboutallpossiblevaluesonapath,ithasmuchmorepowerthanatraditionalruntimetool:(1)itcanforceexecutiondownanyfeasibleprogrampathand(2)atdangerousoperations(e.g.,apointerdereference),itdetectsifthecurrentpathconstraintsallowanyvaluethatcausesabug.Whenapathterminatesorhitsabug,EXEautomaticallygeneratesatestcasebysolvingthecurrentpathconstraintsto ndconcretevaluesusingitsownco-designedconstraintsolver,STP.BecauseEXE’sconstraintshavenoapproximations,feedingthisconcreteinputtoanuninstrumentedversionofthecheckedcodewillcauseittofollowthesamepathandhitthesamebug(assumingdeter-ministiccode).
EXEworkswellonrealcode, ndingbugsalongwithinputsthattriggerthemin:theBSDandLinuxpacket lterimplementations,theudhcpdDHCPserver,thepcreregularexpressionlibrary,andthreeLinux lesystems.
CategoriesandSubjectDescriptors
D.2.5[SoftwareEngineering]:TestingandDebugging—Testingtools,Symbolicexecution
GeneralTerms
Reliability,Languages
Keywords
Bug nding,testcasegeneration,constraintsolving,sym-bolicexecution,dynamicanalysis,attackgeneration.
Permissiontomakedigitalorhardcopiesofallorpartofthisworkforpersonalorclassroomuseisgrantedwithoutfeeprovidedthatcopiesarenotmadeordistributedforpro torcommercialadvantageandthatcopiesbearthisnoticeandthefullcitationonthe rstpage.Tocopyotherwise,torepublish,topostonserversortoredistributetolists,requirespriorspeci cpermissionand/orafee.
CCS’06,October30–November3,2006,Alexandria,Virginia,USA.Copyright2006ACM1-59593-518-5/06/0010...$5.00.
1.INTRODUCTION
Attacker-exposedcodeisoftenatangledmessofdeeply-nestedconditionals,labyrinthinecallchains,hugeamountsofcode,andfrequent,abusiveuseofcastingandpointeroperations.Forsafety,thiscodemustexhaustivelyvetin-putreceiveddirectlyfrompotentialattackers(suchassys-temcallparameters,networkpackets,evendatafromUSBsticks).However,attemptingtoguardagainstallpossibleattacksaddssigni cantcodecomplexityandrequiresaware-nessofsubtleissuessuchasarithmeticandbu erover owconditions,whichthehistoricalrecordunequivocallyshowsprogrammersreasonaboutpoorly.
Currently,programmerscheckforsucherrorsusingacom-binationofcodereview,manualandrandomtesting,dy-namictools,andstaticanalysis.Whilehelpful,thesetech-niqueshavesigni cantweaknesses.Thecodefeaturesde-scribedabovemakemanualinspectionevenmorechalleng-ingthanusual.Thenumberofpossibilitiesmakesman-ualtestingfarfromexhaustive,andevenlesssowhencom-poundedbyprogrammer’slimitedabilitytoreasonaboutallthesepossibilities.Whilerandom“fuzz”testing[35]often ndsinterestingcornercaseerrors,evenasingleequalityconditionalcanderailit:satisfyinga32-bitequalityinabranchconditionrequirescorrectlyguessingonevalueoutoffourbillionpossibilities.Correctlygettingasequenceofsuchconditionsishopeless.Dynamictoolsrequiretestcasestodrivethem,andthushavethesamecoverageproblemsasbothrandomandmanualtesting.Finally,whilestaticanalysisbene tsfromfullpathcoverage,thefactthatitinspectsratherthanexecutescodemeansthatitreasonspoorlyaboutbugsthatdependonaccuratevalueinforma-tion(theexactvalueofanindexorsizeofanobject),point-ers,andheaplayout,amongmanyothers.
ThispaperdescribesEXE(“EXecutiongeneratedExe-cutions”),anunusualbute ectivebug- ndingtoolbuilttodeeplycheckrealcode.ThemaininsightbehindEXEisthatcodecanautomaticallygenerateitsown(potentiallyhighlycomplex)testcases.Insteadofrunningcodeonmanuallyorrandomlyconstructedinput,EXErunsitonsymbolicin-putthatisinitiallyallowedtobe“anything.”Ascheckedcoderuns,ifittriestooperateonsymbolic(i.e.,input-derived)expressions,EXEreplacestheoperationwithitscorrespondinginput-constraint;itrunsallotheroperationsasusual.Whencodeconditionallychecksasymbolicex-pression,EXEforksexecution,constrainingtheexpressiontobetrueonthetruebranchandfalseontheother.Whenapathterminatesorhitsabug,EXEautomaticallygeneratesatestcasethatwillrunthispathbysolvingthepath’scon-
automatically generating inputs of software bug CH ... Chi na) Abstract: U tilizing sof t w ar e...death [ C ] / / P ro ceedings of t he 13...
Generating and Real-Time Rendering of Clouds Petr Man? Czech Technical University in Prague Czech Republic Abstract This paper presents a method for ...
Automatically Generating Loop Invariants Using Quanti?er Elimination?? –Preliminary Report– Deepak Kapur Abstract. An approach for automatically generating ...
Vox Populi a Tool for Automatically Generating Video Documentaries ABSTRACT Vox Populi is a system that automatically generates video documentaries. Our ...
Automatically Generating User Interfaces For Ubiquitous Applications Abstract. ...Supple takes three inputs: a functional interface speci?cation, a device ...
Automatically Generating User Interfaces For Ubiquitous Applications Abstract. ...Supple takes three inputs: a functional interface speci?cation, a device ...
热门文档