contributingphpecho

NAVEX:PreciseandScalableExploitGenerationforDynamicWebApplicationsAbeerAlhuzali,RigelGjomemo,BirhanuEshete,andV.
N.
Venkatakrishnan,UniversityofIllinoisatChicagohttps://www.
usenix.
org/conference/usenixsecurity18/presentation/alhuzaliThispaperisincludedintheProceedingsofthe27thUSENIXSecuritySymposium.
August15–17,2018Baltimore,MD,USAISBN978-1-939133-04-5NAVEX:PreciseandScalableExploitGenerationforDynamicWebApplicationsAbeerAlhuzali,RigelGjomemo,BirhanuEshete,andV.
N.
VenkatakrishnanUniversityofIllinoisatChicago{aalhuz2,rgjome1,eshete5,venkat}@uic.
eduAbstractModernmulti-tierwebapplicationsarecomposedofsev-eraldynamicfeatures,whichmaketheirvulnerabilityanalysischallengingfromapurelystaticanalysisper-spective.
Wedescribeanapproachthatovercomesthechallengesposedbythedynamicnatureofwebapplica-tions.
Ourapproachcombinesdynamicanalysisthatisguidedbystaticanalysistechniquesinordertoautomat-icallyidentifyvulnerabilitiesandbuildworkingexploits.
OurapproachisimplementedandevaluatedinNAVEX,atoolthatcanscaletheprocessofautomaticvulnerabilityanalysisandexploitgenerationtolargeapplicationsandtomultipleclassesofvulnerabilities.
Inourexperiments,wewereabletouseNAVEXoveracodebaseof3.
2mil-lionlinesofPHPcode,andconstruct204exploitsinthecodethatwasanalyzed.
1IntroductionModernwebapplicationsaretypicallydesignedasmulti-tierapplications(i.
e.
,client,server,anddatabase).
Theyincludemanydynamicfeatures,whichgeneratecontent"onthey"basedonuserinteractionandotherinputs.
Suchdynamismhelpstheusabilityaswellastherespon-sivenessoftheapplicationtotheuser.
Thesefeatures,however,increasethecomplexityofwebapplicationsandraisethedifcultybarofanalyzingtheirsecurity.
Currently,severalapproachesexistforanalyzingthesecurityofmodernwebapplicationssuchas[9,15,18,29].
TheseapproachesuseaseriesofanalysistechniquestoidentifyvulnerabilitiessuchasSQLInjection(SQLI)andCross-SiteScripting(XSS).
However,adrawbackoftheseapproachesisthattheygeneratefalsealarms,thereforerequiremanualeffortstocheckwhethereachoneofthereportedvulnerabilitiesisindeedexploitable.
Otherapproachestakeafurtherstepandtrytoincludemethodsforautomaticallyverifyingthatvulnerabilitiesaretruebygeneratingconcreteexploits[7,25,27,32].
However,theseapproachesuselargelystaticanalysismethods.
Whilestaticanalysismethodscanprovidegoodcoverageofanapplication,theyoftensacricepre-cisionduetotechnicalchallengesrelatedtohandlingcomplexprogramartifacts,whichisoneofthemainrea-sonsforgeneratingfalsepositives.
Inparticular,staticanalysisischallenginginthecontextofthedynamicfea-turesofwebapplications,wherecontent(e.
g.
,forms,links,JavaScriptcode)isoftengeneratedonthey,andthecodeisexecutedatdifferenttiers,whoseeffectsaredifculttomodelstatically.
Inthispaper,ourmaincontributionisapreciseap-proachforvulnerabilityanalysisofmulti-tierwebappli-cationswithdynamicfeatures.
Ratherthanfollowingastrictlystaticanalysisstrategy,ourapproachcombinesdynamicanalysisofwebapplicationswithstaticanaly-sistoautomaticallyidentifyvulnerabilitiesandgenerateconcreteexploitsasproofofthosevulnerabilities.
Thecombinationofdynamicandstaticanalysisprovidessev-eralbenets.
First,thedynamicexecutioncomponentgreatlyreducesthecomplexityfacedbythestaticanal-ysisbyrevealingrun-timeartifacts,whichdonotneedtobemodeledstatically.
Ontheotherhand,thestaticanalysiscomponentguidesitsdynamiccounterpartinmaximizingthecoverageoftheapplicationbyanalyzingapplicationpathsandprovidinginputstoexercisethosepaths.
Second,ourapproachscalestoverylargeapplica-tions(e.
g.
,965KLOC),surpassingsignicantlythestateoftheart.
Themainreasonfortheincreasedscalabilityistheabilityofthedynamicexecutioncomponenttoreducethecomplexityfacedbythestaticanalysiscomponent.
Anadditionalgoalofourapproachisthatofenablingautomaticexploitgenerationfordifferentclassesofvul-nerabilitieswithminimalanalysissetupoverhead.
Toachievethisgoal,ourapproachwasdesignedwithsev-eralanalysistemplatesandanattackdictionarythatisusedtoinstantiateeachtemplate.
Thereexistotherstaticapproachesthattrytoachievesuchgeneralityforidenti-fyingvulnerabilities[9,15].
However,ourapproachex-tends[9]by(a)applyingprecisedynamicanalysistech-niquesand(b)automaticallygeneratingexploitsfortheUSENIXAssociation27thUSENIXSecuritySymposium377identiedvulnerabilities.
OurapproachisimplementedinatoolcalledNAVEX.
NAVEX'soperationsaredividedintotwosteps.
Intherststep,wecreateamodelofthebehaviorofindividualmodulesofawebapplicationusingsymbolicexecution.
Toaddressthescalabilitychallenge,weprioritizeonlythosemodulesthatcontainpotentiallyvulnerablesinkswhereanattacker'may'besuccessfulininjectingmali-ciousvaluesorinexploitingothertypesofvulnerabili-ties,andanalyzethemfurtherinthesuccessivesearch.
Inthesecondstep,weconstructtheactualexploits.
Thisrequiresmodelingthewholeapplicationanddis-coveringasequenceofHTTPrequeststhattakeanappli-cationtoexecuteavulnerablesink.
Toaddressthescala-bilitychallengeinthisphase,weperformdynamicanal-ysisofadeployedapplicationanduseawebcrawlerandaconcolicexecutionerontheserver-sidetouncoverpos-sibleHTTPnavigationpathsthatmayleadtheattackertothevulnerablesink.
Tomaximizethecoverageofthecodeduringdynamicanalysis,thecrawlerandconcolicexecutionerareaidedbyaconstraintsolver,whichgen-eratesthe(exploit)sequenceofHTTPinputs.
OurcontributionsinNAVEXincludeanexploitgen-erationframeworkthatcaneasilyscaletolargeappli-cationsandmanyclassesofvulnerabilitiesandanovelmethodthatcombinesdynamicexecutionandstaticanalysistoaddressscalabilityissuesaffectingpreviousworks,mainlyduetothedynamicfeaturesofwebappli-cations.
WeevaluateNAVEXon26applicationshavingatotalof3.
2MSLOCand22.
7KPHPles.
NAVEXwasabletoanalyzetheapplicationsandgenerated204exploits,inlittleunder6.
5hours.
Oftheseexploits,195arerelatedtoSQLIandXSS,while9arerelatedtologicvulnera-bilities,suchasExecutionAfterRedirect(EAR)vulner-abilities.
WenotethatNAVEXistherstreportedworkintheliteraturetoconstructexploitsforEARvulnerabil-ities.
Thispaperisorganizedasfollows.
Section2discussesarunningexampletohighlightchallengesandprovidesanoverviewofNAVEX,ArchitecturalandalgorithmicdetailsofNAVEXarediscussedinSection3.
Section4containsdetailsabouttheimplementation,Section5describestheevaluationofNAVEX,andSection6dis-cussestherelatedwork.
Finally,Section7containstheconclusions.
2ChallengesandApproachOverviewInthissection,weusearunningexampletohighlightthechallengesaddressedinthispaper.
WethenpresentanoverviewofNAVEX.
2.
1RunningExampleListings1-3presentasimplebookborrowingwebap-plication,whichwillbeusedthroughoutthispapertoillustrateourapproach.
BookscanbeselectedthroughthewebforminselectBooks.
phpmodule(lines23-38inListing1).
SelectBooks.
phpvalidatessomeoftheuserinputusingJavaScript(lines31-36).
Theuserin-putisfurthervalidatedandsanitizedbyserver-sidecode(lines4-12).
Next,themodulequeriesthedatabasetocheckthebookavailability(line17).
Basedonthequeryresults,$SESSION['ISBN']isinitializedandanHTTPlinktohold.
phpisprintedonthebrowser.
1HoldtheBook";21}22>//client-sidecodestarts23"onsubmit="validate()">24//drop-downlist25IntrotoCS26IntrotoMath.
.
272829303132functionvalidate(){//validatesformuponsubmission33varedition=document.
getElementsByName("edition");34if(edition.
valueListing1:selectBooks.
php,ndbookstoborrow.
Hold.
php(Listing2)performsadditionalchecksand,iftheyaresatised,anHTTPlinkguidestheusertothenextstep(line7).
Whenthelinkisclickedthesuperglobal$GET['step']issetandthemodulecheckout.
phpisthereforeincludedbyhold.
phpandexecuted.
Checkout.
phpcompletestheborrowingpro-cessbyprovidingalink(line19)totheuserforconr-mation.
Thelinksetstwosuperglobals($GET['step']and$GET['msg']),whichwillbecheckedbythemod-ule(line6).
Finally,aconrmationfunction(line13)is37827thUSENIXSecuritySymposiumUSENIXAssociationcalledtonotifytheuserthatthebookwassuccessfullyreserved.
1Checkout";8if(isset($_GET['step'GET['step']=="checkout")9include_once("checkout.
php");10}11>Listing2:hold.
php,holdbooksforpickup.
1sql_fetchrow($result);10$msg=$_GET['msg'];11confirm($name,$msg);12}13functionconfirm($name,$msg){14if(isset($name)&&isset($msg))15echo$name.
"youare".
$msg;//XSSvulnerability16}17>//client-sidecodestarts1819DONE20Listing3:checkout.
php,checkoutfunctionality.
Theexamplecontainssensitivesinksthatarevul-nerabletoinjectionandlogicattacks.
Forexample,thequeryinlisting1(line17)isvulnerabletoSQLIthroughthevariable$publisher,whichisnotprop-erlysanitizedbeforereachingthesink.
Inparticular,thestrreplacefunction(line13)doesapoorjobofsan-itizing$publisher,sinceanSQLIattacknotinvolvingdoublequotesmaystillbeused.
Additionally,theechocallinListing3isvulnerabletoXSSastheuserinput$msgisnotsanitized.
Finally,thesinkatListing1line3isvulnerabletoanExecutionAfterRedirect(EAR)logicattackbecausetheexecutionaftertheheadercall(redi-rectstheexecutiontoanotherPHPmodule)doesnothaltsincethereisnocalltoanexecutionterminationfunctionafterward.
Consequently,thefollowingstatementswillbeexecutedregardlessofthecheckatline2.
Theprob-lemisfurtherexacerbatedbythefactthatthosestate-mentscontainavulnerableSQLquery.
AnattackermaythusbeabletorunaSQLIexploitwithoutneedingtologinrst.
2.
2ChallengesAsillustratedbytheexample,typicalwebapplicationshaveclient-sidelogicthatconsistsofforms,links,andJavaScriptcode,whichmaybedynamicallygeneratedbytheserver-sidecode,aswellasacomplexserver-sidelogicthatfrequentlyinteractswiththeclient-sideandwiththedatabasebackend.
Therefore,buildinganexploitgenerationframeworkthatuncoversawiderangeofdifferenttypesofexploitsfordynamicwebapplica-tionsisnon-trivial.
Specically,weidentifythefollow-ingchallenges:Sinkreachability.
Inwebapplications,sometasks/-functionalitiesrequireaseriesofsteps,andtherearede-pendenciesthatexistbetweenthesetasks.
Thesestepsareusuallyaccomplishedusingdifferentmoduleswherethestateoftheapplication,maintainedthroughtheuseofglobalconstructs(e.
g.
,$GET[]inPHP),isupdatedtoreectthecompletion/failureofastep.
Ifasensi-tivesinkislocateddeepintheseinterrelatedmodules,thechallengeistoautomaticallygenerateanexploitthatnavigatesthroughthecomplexdependenciesamongap-plicationmoduleswhilesatisfyingconstraintsrequiredateachjunctioninthenavigation.
Forinstance,asuccess-fulexploitforthevulnerableechoinListing3,mustcon-sidernavigationandconstraintsatisfactionthroughthemodulesselectBooks.
php,hold.
php,index.
php(notshownintheexample),andcheckout.
php.
Morebroadly,wemusttakeintoaccountseveralfac-tors.
First,dataowpathsfromsourcestosensitivesinksmustbeidentied.
Next,possibledatasanitiza-tionsalongthosepathsmustbeanalyzed.
However,san-itizationsareavailableinmanyavors,includingbuilt-insanitizations(e.
g.
,htmlspecialchars()),implicitsanitizations(e.
g.
,castoperatorsasshownintherun-ningexample),customsanitizations(e.
g.
,customuseofstrreplace()),andsanitizationsinducedbydatabaseconstraints(e.
g.
,NOTNULLconstraints).
Thepracticalchallengehereistopreciselyidentifywhensuchsani-tizationsaresufcientlyrobusttoeliminateallpossiblerisks.
Dynamicfeatures.
Anautomaticexploitgenerationap-proachthatisentirelybasedonstaticaspectsofawebapplicationispronetomisscertainrealexploits.
Asmentionedbefore,modernwebapplicationsoftencon-tainfeaturesthatarerevealedonlywhentheapplicationisexecuted.
Thesefeaturesoftenincludedynamicallygeneratedformsandlinksthatmaydrivethenavigationoftheapplicationtovulnerablesinks.
Unlesstheap-plicationisdeployedandexecuted,itischallengingforastaticanalysisapproachtoinfersuchartifacts,whichmaycontainusefulconstraintsforexploitpaths.
Forin-stance,line23ofListing1,wheretheactionoftheformissetbytheresultofrunningtheembeddedPHPcode.
Topreciselyinferthevalueofthataction,astaticanalyzerhastobeabletohandlethePHPsemanticsofthatcodeportion.
Othersituations(notshownintheex-ample)includedynamicallygeneratedcontentincludingJavaScriptgeneratedcontent.
Itis,therefore,necessaryUSENIXAssociation27thUSENIXSecuritySymposium379toincorporatedynamicanalysisaspartoftheexploitgenerationframeworktomaketheseruntimeartifactsex-plicit.
Anadditionalchallengewithdynamicexecutionismaximizingthecoverageofanapplication.
Scalability.
Generatingexecutableexploitsthatspanmultiplemodulesandtraverseexecutionpathsinsideeachmoduleforlargeandcomplexmodernwebapplica-tionsischallenging.
Constructingexploitsrequiresan-alyzingtheapplicationasawhole,includingitsclient-side,server-sideanddatabasebackend.
Todealwiththischallenge,theexploitgenerationapproachmustbede-signedwithcarefulconsiderationsforpruningunfeasi-bleexploitpaths.
Todemonstratetheneedforascal-ableapproach,let'sconsiderourrunningexample.
Forthissimpleapplication,toconstructanexploitforthevulnerablesinkinListing3,wehavetoprocessato-talof44executionpathsinthe3modules(i.
e.
,32pathsinselectBooks.
php,4inhold.
php,and8incheckout.
php)tondcandidateexploitablepathstothesink.
Anotherscalabilitychallengeweneedtotackleisrelatedtothegoalofgeneratingexploitsformultipleclassesofvulnerabilities.
Toaddressthischallenge,weneedtosupportabstractionandanalysisofmulti-pleclassesofvulnerabilitiesefciently,astogenerateasmanydifferenttypesofexploitsaspossible.
2.
3ApproachOverviewOurgoalistobuildaprecise,scalable,andefcientexploitgenerationframeworkthattakesintoaccountthedynamicfeaturesofwebapplicationsandthenaviga-tionalcomplexitiesthatstemfromdependenciesamongtheclient-side,server-sideanddatabasebackend.
OurapproachisimplementedinasystemcalledNAVEX,asshowninFigure1.
Toaddressthescala-bilitychallenges,ourapproachisdividedintotwosteps:(I)vulnerablesinkidenticationand(II)concreteexploitgeneration.
Giventheapplicationsourcecode,therststepiden-tiesvulnerablesinksintheapplicationandthecorre-spondingmodules.
Thisphaseanalyzeseachmoduleseparatelyandiscrucialforprioritizingonlythosemod-ulesthathavevulnerabilities;thussignicantlyreduc-ingthesearchspaceandcontributingtoscalability.
Toaddressthesinkreachabilitychallenge,NAVEXbuildsapreciserepresentationofthesemanticsofbuilt-insaniti-zationroutines.
Inaddition,forcustomsanitizations,itbuildsamodelusingsymbolicconstraints.
Thesecon-straintsareusedbyaconstraintsolver,whichdeterminesifthesanitizationsaresufcientlyrobust.
Thesecondstepisresponsibleforgeneratingconcreteexploits.
Themainprobleminautomaticallygeneratingconcreteexploitsisthatofidentifyingapplication-widenavigationpathsthat,startingfrompublic-facingpages,drivetheexecutiontothevulnerablesinksidentiedinFigure1:ThearchitectureofNAVEX.
therststepthroughaseriesofHTTPrequests.
TheoutputofthedynamicexecutionisaNavigationGraphthatrepresentsthenavigationstructureofthewebappli-cation.
Finally,foreverymodulecontainingavulnera-blesink,asidentiedintherststep,NAVEXusesthisnavigationgraphtondthepathsfrompublicmodulestothatmodulealongwhichtheexploitcanbeexecuted.
ThedynamicfeatureschallengeisaddressedinNAVEXbycombiningdynamicanalysisandsymbolicexecutionofapplications.
Tomaximizethecoverageofanapplica-tion,NAVEXrepeatsthedynamicexecutionmanytimes,eachtimewithdifferentinputsgeneratedbyaconstraintsolverinawaythatmaximizespathcoverageintheap-plication.
Ateachexecution,NAVEXcollectstheinfor-mationnecessarytoderivetheapplication'snavigationstructure.
3ArchitectureandAlgorithms3.
1VulnerableSinkIdenticationToidentifythevulnerablesinks,NAVEXanalyseseachmoduleseparately.
Animplicitgoalofthisstepistoexcludefromthefollowingstepthosemodulesthatdonotcontainvulnerablesinks.
Inparticular,asdepictedinFigure2,NAVEXrstbuildsagraphmodelofeachmodule'scode,thenitdiscoversthepathsthatcontaindataowsbetweensourcesandsinks.
Finally,itusessymbolicexecutiontogenerateamodeloftheexecutionasaformulaandconstraintsolvingtodeterminewhichofthosepathsarepotentiallyexploitable.
Eachofthesecomponentsisdescribednext.
3.
1.
1AttackDictionaryToaddressthechallengeofdiscoveringmultipleclassesofvulnerabilities,NAVEXwasdesignedtobeeasilyex-tensibletoawiderangeofvulnerabilities,suchasSQLI,XSSaswellaslogicvulnerabilitiessuchasEAR[18]andcommandinjection.
Akeyobservationisthatsev-eraltypesofvulnerabilitiesareessentiallysimilar.
Forinstance,SQLIandXSSbothdependontheowofma-liciousdatafromsourcestosinksandinjectionofma-liciousdatainthosesinks.
Themaindifferenceisthenatureofthesinkandtheattackpayload.
Thissimilar-ity,inturn,canbeleveragedtobuildanalysistemplatesthatcanbeinstantiatedwithminimalchangestodiscoverdifferentclassesofvulnerabilities.
Tothisend,NAVEXbuildsanAttackDictionary,whichisusedtoinstantiateanalysistemplatestargetingeachclassofvulnerability.
Inparticular,itcontainsattackspecications,asfollows:38027thUSENIXSecuritySymposiumUSENIXAssociationFigure2:VulnerableSinksIdentication(StepI)Components.
Sinks.
Theseareinstructionsthatexecutethemaliciouscontentofanattack.
Forinstance,echoandprintPHPfunctionsaresinksforXSSattacks.
Sanitizations.
TheseincludeanextensivelistofPHPsanitizations,includingbuilt-insanitizationfunctionsandoperators,whichmayimplicitlysanitizeaninput(e.
g.
,castoperators).
Whileextensive,thislistisnotexhaustive,andthereforeitmaymissfunctions.
How-ever,thesemanticsofknowncustomsanitizationfunc-tions(e.
g.
,strreplace)arecapturedbyNAVEXusingconstraintsolving.
TraversalType.
Itspeciesthetypeoftraversalthatisneededonthegraph(thegraphrepresentationwillbedescribedshortly).
Wecurrentlysupportforwardandbackwardtraversalsbetweensourcesandsinks.
Speci-cally,injectionvulnerabilitiestypicallyneedabackwardtraversal,whilevulnerabilitiessuchasEARneedafor-wardone.
AttackStrings.
Theattackstringsarespecicationsofthepossible(malicious)valuesthatcanappearatasink.
Whilenotexhaustive,thelistofattackstringsusedbyNAVEXisveryextensive.
Itcontains45attackpatternscollectedfromcheatsheets(e.
g.
,[6]),andsecurityre-ports.
Currently,theattackdictionarycontainsentriesforSQLI,XSS,leinclusion,commandinjection,codeex-ecution,andEAR.
3.
1.
2GraphConstructionThisstepbuildsagraphmodeltorepresentthepossi-bleexecutionpaths,whicharelatersymbolicallyexe-cuted,inaPHPmodule.
Specically,ourgraphmodelisbasedonCodePropertyGraphs(CPGs)[9,33],whichcombineabstractsyntaxtrees(AST),controlowgraphs(CFG),callgraph,anddatadependencegraphs(DDG)underauniquerepresentationtodiscovervulnerabilities,whicharemodeledasgraphqueries.
Inparticular,givenasourceandasinkinstruction,CPGscanbeusedtonddatadependencypathsbetweentheirvariables.
However,ournalgoalisnotmerelythatofndingvulnerablepathsbutalsothatofgeneratingconcreteex-ploits.
Tothisend,weextendCPGswithsanitizationanddatabaseconstrainttags.
ThesetagsareattributesaddedtotheCPGsandareusedtopruneoutalargenumberofpotentiallyunexploitablepathsandindirectlyaddressingthechallengeofpathexplosion.
SanitizationTags.
Asanitizationtagstoresinformationaboutthesanitizationstatusofeachvariableinanode,ifany.
Thepossiblevaluesofthetagareunsan-X,san-XwhereXrepresentsthespecicvulnerability.
Forin-stance,san-sqlandunsan-sqlrepresentpresence(ornon-presence)ofSQLIsanitization,respectively.
Thevaluesofthesanitizationtagsareinferredandaddedtothegraphduringitsconstruction.
Inparticular,asanodeisaddedtotheCPG,thecorrespondingnode'sASTisanalyzedtodetecteventualsanitizations.
Thisanalysisisguidedbythesanitizationspatternscontainedintheattackdictionaryforeachtypeofvulnerability.
Whenamatchamongthesanitizationpatternsisfoundforavariableinanode,thecorrespondingsan-Xvalueissetforthatvariable.
Note,weaddsanitizationtagsthatresolvethesanitizationstatusofdifferenttypesofPHPstatementssuchasassignment,cast,binary,unarystatements,built-infunctions,etc.
TodemonstratehowNAVEXassignssanitizationtags,letusconsiderthestatementatline9inListing1.
NAVEXstartsbyinspectingtheASTof$edition=(int)$POST['edition']toassignanappropriatetagto$POST['edition']rst.
Then,itpropagatesthesan-itizationstatusto$edition.
Inthiscase,theassignedtagto$POST['edition']issan-allbecausethecasttointegeroperatorsanitizesitforallvulnerabilitiesinourattackdictionary.
Consequently,thevariable$editionwillhavethesamevalueinitssanitizationtag.
DatabaseConstraintTags.
Databasesmayoftenen-forceadditionalconstraintsonthedatathatowtothedatabasetables.
Forinstance,thecolumnsofadatabasetablemayimplicitlysanitizecertaininputs,basedonthecolumn'sdatatype(e.
g.
,enumorinteger).
Weenhancecodepropertygraphstocapturedatabaseconstraints.
Inparticular,foreachwebapplication,NAVEXparsesitsschematocollecttablenames,theircolumnsnames,datatypes,andvalueconstraints(e.
g.
,NOTNULL).
DuringtheCPGconstruction,NAVEXaddsatagcalledDBtotherootnodeofeachapplication.
Thistagcontainsthecollectedinformationfromtheschema,anditisutilizedlaterduringthegraphtraversalandexploitgeneration(Sections3.
1.
3and3.
1.
4).
USENIXAssociation27thUSENIXSecuritySymposium3813.
1.
3GraphTraversalThegoalofthisstepistodiscovervulnerablepathsfromsourcestosensitivesinksbyinspectingtheenhancedCPG.
BackwardTraversal.
Anexampleofabackwardtraver-salfordiscoveringvulnerablepathsforinjectionvulner-abilitiesisshowninAlgorithm1.
Thealgorithmstartsbysearchingthegraphforcallstosensitivesinksspeciedintheattackdictionary(line4).
Foreachnoderepresentingasink,itfollowsback-wardthedatadependencyedgesforallvariablesusedinthatsinkusingthefunctionAnalyzeNode(line8).
ThisfunctioncallsFollowBackwardDDEdge(line18)tondalldatadependencypathsfromasinknodetoeitherasourceorafunctionargument(ifthesinkisinsideafunction).
Ifapathendsatafunctionargu-ment,AnalyzeNodeiscalledrecursivelyoverthenodesrepresentingthecallsitesofthatfunction(line15).
ThefunctionFollowBackwardDDEdgeidentiesintra-proceduralpathsbetweensourcesandsinksandusesthesanitizationandDBtagstoeliminatesanitizedpaths.
Fi-nally,getPathsTo(line24)ndsalltraversedandun-sanitizedpathsinthegraphleadingtosourcenodes.
Asanexample,considerthevulnerablesinkechotoXSS(line15)inListing3.
Startingfromthissink,thealgorithmfollowsalldatadependencyedgesbackwardswhilecheckingthesanitizationtagsof$nameand$msg.
Sincetheyarebothunsanitized,NAVEXstorestheintra-proceduralpathsofthevariablesandfollowsthedatade-pendencyedgesinthecallerfunctionuntilitreachesthesourceof$msg(line10).
Note,$nameisnotauserinput(holdsvaluesfromthedatabase)andthereforethealgo-rithmonlyreturnstheinter-pathsof$msgasvulnerablepathstoXSS.
TheFilterSanNodesfunctionusesthesanitizationandDBtagstopruneoutunpromisingpathsforexploitgeneration.
Inparticular,DBtagsareutilizedduringthesearchforSQLIvulnerability.
Foreachwritequery,NAVEXparsesthequeryusingaSQLparsertondnec-essaryinformationsuchastableandcolumnsnames.
Then,itmatchestheextractedinformationwiththeDBtagtoderiveconstraintsfromthecolumnsdatatypesandvalueconstraints(Fdb).
Theseconstraintsareusedinconjunctionwiththepathconstraints(Fpath)inthenextstep(Section3.
1.
4).
ForwardTraversal.
Asanotherexample,todetectEARvulnerabilities,NAVEXperformsaforwardgraphtraver-salfromsourcestosinkswherethesourcesareredirec-tioninstructions(e.
g.
,header)andthesinksaretermi-nationinstructions(e.
g.
,die).
Inparticular,wedistin-guishbetweentwotypesofEARvulnerabilities,namelybenignwherethecodebetweensourcesandsinksdoesnotcontainsensitiveoperations(e.
g.
,SQLqueries)andmaliciousEARwherethatcodecontainsthem[18].
Algorithm1InjectionVulnerabilityPathDiscovery1:Input:sources,sinks2:output:VulnerablePaths3:4:sinkNodes=FINDSINKNODE(sinks)5:forallsn∈sinkNodesdo6:VulnerablePaths=ANALYZENODE(sn)7:returnVulnerablePaths8:functionANALYZENODE(node)9:VulnerablePaths←[]10:paths=FOLLOWBACKWARDDDEDGE(sn)11:forallpath∈pathsdo12:ifpathhasasourcethen13:VulnerablePaths←path14:else15:callPaths=ANALYZENODE(callNode)16:VulnerablePaths←path+callPaths17:returnVulnerablePaths18:functionFOLLOWBACKWARDDDEDGE(node)19:IntraPaths←[]20:whilenodeisnotasource∧nodeisnotafunc.
argu-mentdo21:IncNodes=GETINCOMINGDDNODE(node)22:UnsanNodes=FILTERSANNODES(IncNodes)23:node←unsanNodes24:IntraPaths=GETPATHSTO(node)25:returnIntraPathsTheoutputofthisstepisasetofpathsthatarepoten-tiallyvulnerable.
Thissetofpathsissentininputtothenextstep.
3.
1.
4ExploitStringGenerationThelaststepofthestaticanalysisisthegenerationofexploitstringsoverthevulnerablepathsdiscovereddur-inggraphtraversal.
Inthisstep,eachvulnerablepathismodeledasalogicalformulaFpath.
Inaddition,theconstraintsderivedfromtheDBtagsFdbareaddedtotheformula.
Itisnextaugmentedwithadditionalcon-straintsoverthevariablesatthesinksFattack,whichrep-resentvaluesthatcanleadtoanattack.
ThesevaluesareretrievedfromtheAttackDictionarybasedonthetypeofvulnerabilityunderconsideration.
Theaugmentedformula(i.
e.
,Fpath∧Fdb∧Fattack)isnextsenttoasolver,whichprovidesasolution(ifitex-ists)overthevaluesoftheinputvariables,thatisanex-ploitstring.
Thissolutioncontainsthevaluesofthein-putvariables,which,afterthepathandsanitizationsex-ecutions,causetheattackstringtoappearatthesink.
However,evenifasolutionexists,therelatedexploitisnotnecessarilyfeasible.
Todetermineitsfeasibility,NAVEXneedstouncoverthesequenceofHTTPrequeststhatmustbesenttotheapplicationtoexecutetheattackdescribedbytheexploitstrings.
Thisstepisexposedintherestofthissection.
38227thUSENIXSecuritySymposiumUSENIXAssociation3.
2ConcreteExploitGenerationTogeneratetheconcreteexploits,NAVEXexecutesseveralstepsasdepictedinFigure3.
First,adynamicex-ecutionstepcreatesanavigationgraphthatcapturesthepossiblesequencesinwhichapplicationmodulescanbeexecuted.
Next,thenavigationgraphisusedtodiscoverexecutionpathstoonlythosemodulesthatcontainthevulnerablesinksuncoveredbythevulnerablesinkiden-ticationstep.
Finally,thenalexploitsaregenerated.
Wedescribeeachofthesestepsnext.
3.
2.
1DynamicExecutionThisstepisresponsibleforbuildinganapplication-widenavigationgraph,whichrepresentspossiblesequencesofmoduleexecutionstogetherwithassociatedconstraints.
Previousresearch[7]hasrecognizedtheimportanceofbuildingsuchagraph.
However,akeydifferencewiththatworkistheapproachinwhichthegraphisgener-ated.
Inparticular,theapproachof[7]usesstaticanaly-sistodiscoverlinksandformsanddoesnotdealwiththedynamicfeaturesofwebapplications,whosesemanticsarechallengingtobecapturedstatically.
Incontrast,NAVEXusesadynamicexecutionap-proach.
Itexecutesthewebapplicationthroughacrawlersothatasignicantportionofthosedynamicfeaturesbe-comeconcreteanddonotneedtobesymbolicallyeval-uated.
However,acommonchallengewhenperformingthedynamicanalysisismaximizingthecoverageoftheapplication.
Toaddressthischallenge,NAVEXusescon-straintsolvingandconcolicexecutiontogeneratealargenumberofforminputsthataidthecrawlerinmaximizingthecoverageoftheapplication.
Crawler.
Thecrawlerisresponsibleforuncoveringthenavigationstructureoftheapplications.
Foreachap-plication,thecrawlerisinitiatedwithaseedURLandwhenevernecessary,validlogincredentials.
Whilemostapplicationshavetwotypesofroles(administratorandregularuser),tomaximizethecrawlingcoverage,thecrawlerdoestheauthenticationforeachrole-typeintheapplication.
StartingfromtheseedURL,thecrawlerextractsHTMLlinks,forms,andJavaScriptcode.
ThelinksarestoredandusedasthenextURLstocrawl.
Forformsubmissions,thecrawlerneedstoconstructvaluesthatcomplywiththeformrestrictions(e.
g.
,lengthofin-put)andsatisfyeventualJavaScriptvalidations.
Havingamechanismthatautomaticallygeneratesvalidformin-putsgreatlyimprovesthecrawlingcoverageofwebap-plicationssincewebformsarecommonconstructsthatinuencethenavigationstructure.
Toaddressthisproblem,ourcrawlerextractstheforms'inputelds,buttons,andactionandmethodat-tributes(i.
e.
,GETorPOST)usinganHTMLparserandgeneratesasetofconstraintsovertheformvaluesim-pliedbytheformattributes.
Inaddition,todealwithJavaScriptcodethatvalidatesforminputs,thecrawlerleveragesthetechniquesusedin[12].
Specically,theJavaScriptcodeisextractedandanalyzedusingconcrete-symbolicexecution.
Thecodeisrstexecutedconcretelyandwhentheexecutionreachesaconditionalstatementthathassymbolicvariables,theexecutionforks.
Then,theexecutionresumesconcretely.
Aftertheexecutionstopsforalltheforks,asetofconstraintsthatrepre-senteachexecutionpaththatreturnstrueisgenerated.
NAVEXcombinestheformHTMLconstraintsFhtmlandtheJavaScriptconstraintsFjstoproducethenalformconstraintsFform.
Asanexample,theconstraintsfortheforminourrunningexample(Listing1)are:Fhtml:(bookname=="IntrotoCSbyauthor1"∨bookname=="IntrotoMathbyauthor2")Fjs:edition>0Fform:Fhtml∧FjsFinally,theformulafformissenttothesolvertondasolution.
NAVEXusesthesolverso-lution,formmethod,andactioneldstois-sueanewHTTPrequesttotheapplication(i.
e.
,http:.
.
.
/selectBooks.
phpaction=borrowPOST[bookname=IntrotoCSbyauthor1,edition=2]).
AddressingServer-sideConstraints.
Server-sidecodeoftenintroducesadditionalconstraintsonthevaluesoftheinputvariables,whichcaninuencethenavigationstructureofanapplication.
Mostcommonly,thesein-cludeconstraintsoverthevaluessubmittedviaforms.
Forinstance,inListing1,theserver-sidecodeintro-ducesanadditionalcheckoverthestringlengthof$publisher,whichisnotpresentintheJavaScriptval-idation.
Typically,whentheserverconstraintsaresatised,theexecutionproceedsandthestateoftheapplicationischanged,whileintheoppositecase,theapplicationre-jectstheforminputsandthestateoftheapplicationdoesnotchange.
Therefore,tomaximizethecoverageoftheapplication,thecrawlermustbeabletogenerateforminputsthatareacceptedbytheapplication.
Whileautomaticallygeneratingforminputsthatarerejectediseasier,generatinginputsthatareacceptedismorechallenging.
Todealwiththischallenge,weuti-lizeanexecution-tracingengineontheserver-sidecode.
NAVEXusestheproducedtraceinformationtodeterminewhetherarequestissuccessfulbycheckingiftheappli-cationis(i)changingitsstate(i.
e.
,creatinganewses-sion,settinganewvariableandsuperglobalvalues,etc.
)and(ii)performingsensitiveoperationssuchasqueryingthedatabase.
Whenarequestisnotsuccessful,NAVEXutilizesthetraceinformationtoperformaconcolicexecution.
Inparticular,itrstretrievestheexecutedstatementsin-cludingtheconditionalstatements.
Then,thecollectedUSENIXAssociation27thUSENIXSecuritySymposium383Figure3:ConcreteExploitGeneration(StepII)Components.
conditionalstatementsaretransformedautomaticallytosolverspecicationsandnegatedtouncovernewexecu-tionpaths.
Thenewlycreatedspecicationsarethensenttothesolvertogeneratenewforminputs.
Thisprocessiscontinuouslyrepeateduntiltheformsubmissionissuc-cessful.
Asanexample,theaboveinferenceconstructsthefollowingconstraintsthatyieldtoasuccessfulformsubmission(bookname=="introtoCSbyauthor1"∨bookname=="introtoMathbyauthor2")∧length(publisher)0Finally,foreachacceptedform,NAVEXstoresthefullHTTPrequestthatledtothesuccessfulsubmission.
3.
2.
2NavigationGraphTheNavigationGraphproducedbythedynamicexe-cutionsteprepresentstheapplications'navigationbe-havior.
ItisadirectedgraphG=(N,E)whereeachnoden∈NrepresentsanHTTPrequestandeachedgee=(ni,nj)∈Erepresentsanavigationfromnitonj,whichcanbeoftypelinkorform.
Inparticular,forev-eryedgee=(ni,nj)∈Enirepresentsthepagefromwhichtherequestwasoriginated.
Eachnodeinthegraphhasthefollowingpropertiesid,URL,role,andformparamsfornodesrepresentinganHTTPrequestgeneratedbyaformsubmission.
Theidpropertystoresauniqueidentierofthenode,theURLpropertyistheURLintheHTTPrequest,whichiscomposedofthemodulenameandHTTPparametersoftherequest,andtherolepropertyholdsthelogincredentialsusedasin-puttothecrawlerasillustratedinFigure4.
Itisimpor-tanttonotethatthenavigationgraphcancontainmultiplenodesassociatedwiththesamePHPmodule.
Inpartic-ular,ifaPHPmodulecanacceptdifferentcombinationsofinputvariables,eachsuchcombinationisrepresentedbyacorrespondingnodeintheNG.
ApartialinstanceofanNG,relatedtoourrunningex-ampleisshowninFigure4.
Asanexample,onepossi-bleformsubmission,withforminputvaluesgeneratedbythesolver,isrepresentedbytheedgebetweennodes2and3,whiletheotheredgesrepresentlinknaviga-tion.
Notethathold.
phpisassociatedwithtwodifferentnodes(id-s5and6),eachhavingadifferentcombinationofinputvariables(i.
e.
,HTTPparameters).
Thisrepre-sentationwillbecrucialinthenextstepwhenexploringpathstotheexploitablemodules.
3.
2.
3FinalExploitGenerationTogeneratethenalconcreteexploits,NAVEXutilizestheNGalongwiththevulnerablesinksidentiedbythetechniquesintroducedinSection3.
1.
OnechallengethatNAVEXmustsolveinthisstepisthatofcombiningtheresultsproducedbythestepofvulnerablesinkidentica-tionwiththeNavigationGraph.
Inparticular,whenmod-ulescontainingvulnerablesinksareincludedbyothermodulesusingPHPinclusion,theformerdoesnotap-pearintheNG,becausethereisnoexplicitnavigationtothem.
Forinstance,themodulecheckout.
phpdoesnotappearintheNGinFigure4.
Toexecutethesevulner-ablemodules,theexecutionmustinvoketheincludingmodules.
Toaddressthisissue,NAVEXexecutesapreprocess-inginclusionresolutionstep,whichcreatesaninclusionmapthatstorestheleinclusionrelationships.
ThemapisconstructedbyperformingatraversalthatsearchestheenhancedCPGfornodesthatrepresentcallstoleinclu-sionPHPfunctions(e.
g.
,require,include,etc).
Oncetheinclusionresolutionstepiscompleted,NAVEXusestheNGandtheproducedinclusionmaptosearchpathsontheNGfrompublicmodulestotheex-ploitablemodules(ortheirincludingparents).
Itisim-portanttonotethatthepreviousidenticationofvulner-ablesinksthat'may'beexploitablegreatlyreducesthecostofsuchsearchandincreasesthelikelihoodofnd-ingexecutableexploits.
ThesearchmethodissummarizedinAlgorithm2.
Therstinputtothesearchisthesetofpairs{(module,exploit)}fromStepIofNAVEX.
Modulerep-resentsthevulnerablemodule,andexploitrepresentstheassignmentsofmaliciousvaluestoinputsgeneratedbythesolver.
ThenextinputistheInclusionMapandtheSeedURLs,whichrepresentthepubliclyaccessiblemodules.
Foreachvulnerablemodule,usingtheinclu-sionmapandtheparametersintheexploit,thealgo-rithmrstndspossibledestinationnodes,whichwillbethetargetsofthegraphsearch(line5).
Thesenodes(DestURLs)representeitherthevulnerablemoduleoritsparents(ifaparentPHPmoduleincludesthevulnerablemodule).
GetDestURLsreturnsonlythosenodesoftheNG,whoseparameternamesmatchtheparameternamesappearinginthecorrespondingexploit.
Thefunc-tionExpSearchrstidentiesthenodeswhoseURLmatchesoneoftheSeedURLs(i.
e.
,matchestheURL38427thUSENIXSecuritySymposiumUSENIXAssociationFigure4:Thenavigationgraph(NG)ofourrunningexample.
Algorithm2GeneratingConcreteExploits1:Input:ModulesAndExploits={(module,exploit)},InclusionMap,SeedURLs2:output:ConcreteexploitsforVulnModule3:4:forallvm∈ModulesAndExploitsdo5:DestURLs=GETDESTURLS(vm,InclusionMap)6:Exploit=EXPSEARCH(SeedURLs,DestURLs,vm)7:AllExploits←Exploit8:returnAllExploits9:10:functionEXPSEARCH(SeedURLs,DestURLs,vm)11:SrcNodes=FINDSRCNODES(SeedURLs)12:forallsn∈SrcNodesdo13:paths=GETPATHSTO(sn,DestURLs)14:forallpath∈pathsdo15:exploit=REPLACEVULNPARAMS(path,vm)16:ConcreteExploits←exploit17:returnConcreteExploitsproperty)(line11).
ThetraversalthenexplorestheNGforeachoftheretrievedSrcNodestondpathsbetweenthesourcenodeandtheDestURLs(line13).
Finally,foreachfoundpath,itreplacesthevaluesoftheHTTPpa-rametersinthelastedgewiththemaliciousvaluesgen-eratedbythesolver.
Applyingthealgorithmtoourrun-ningexample,yieldstoconsideringhttp://localhost/App/selectBooks.
phpasaSeedURL,andthenodewithid6inFigure4asDestURL,becausethatnodematchesthevulnerablemodule,whosecorresponding(XSS)exploitcontainsanassignmentofamaliciousvaluetotheHTTPvariablemsg.
Sincetheexploitstringformsgisalert("XSS");(generatedbythesolverandstoredinexploit),GetPathsToexploresthefollowingnavigationpathsbetweentheSeedURLandDestURL:(1)nodesof[id=2,id=3,id=4,id=5]and(2)nodesof[id=2,id=3,id=4,id=5,id=6].
However,itreturnsonlytherstnavigationpathbecausetheURLofnode5doesnotcontaintheHTTPparametermsg.
Finally,ReplaceVulnParamsfunctionreplacesthevalueofthemsgwiththemaliciousvalueoftheexploit.
Asaresult,NAVEXgeneratesthefollowingsetofHTTPrequestsasaconcreteexploitforthevulnerablesink(line15)atListing3:1.
http://localhost/App/index.
php2.
http://localhost/App/selectBooks.
phpwithPOSTparams:[bookname=introtoCSbyauthor1,edition=2,publisher=aaaaaaa]3.
http://localhost/App/selectBooks.
phpaction=borrow4.
http://localhost/App/hold.
php5.
http://localhost/App/hold.
phpstep=checkout6.
http://localhost/App/hold.
phpstep=checkout&msg=alert("XSS");Ascanbenoted,asaresultofourdynamicexecutionandofthenavigationgraphdesignwherenodesrepre-sentHTTPrequests,thechallengingproblemofndingsequencesofHTTPrequeststhatexecuteanexploitistransformedintoasimplegraphsearchproblem,whichisefcient.
4ImplementationTheimplementationofNAVEXisbasedonseveralexist-ingtools,mostofwhichwereextendedtodealwithourproblem.
ForStepIofourapproach,thePHPextension[9]ofcodepropertygraphs[33]wasenhancedwithaddi-tionaltagstoenableprecisetainttrackinganddatabaseconstraintsreasoning.
TheenhancedCPGisthenim-portedtotheNeo4j[4]graphdatabase,anopensourcegraphplatformtocreateandquerygraphdatabases.
Thegraphtraversals,suchasalgorithm1,arewritteninGremlin[1].
Neo4jandGremlinarealsousedinStepIItobuildandsearchthenavigationgraph.
Forconstraintssolving,weleveragedZ3solver[17]anditsextensionZ3-str[35].
Inparticular,whengraphtraversalsreportavulnerablepathtoasink,NAVEXan-alyzesthereturnedpathanditsnodes.
Basedoneachnodetype,aThree-AddressCode(TAC)formulathatrepresentsthenodeiscreatedautomatically.
TheTACFormulaconsistsofrightoperand(rightOp),operator,andleftoperand(leftOp),nodetype,anduniquenodeid.
Then,NAVEXstartsanalyzingeachTACformulaac-cordingtoitstype.
Basedoftheoperator,leftOp,andrightOp,NAVEXgenerates:(1)appropriateZ3variabledeclarations,(2)asetofassertionsthatreplicatethese-manticsofthePHPoperatorinZ3specication,and(3)anassertionthatassignsappropriateattackstringsfromourattackdictionarytoeachsinkvariableintheformula.
NAVEXsupportsassignment,unary,binary,conditional,built-infunction,andcaststatementtypes.
TheTACfor-mulaanalysisandZ3translationenginecodeareapprox-USENIXAssociation27thUSENIXSecuritySymposium385imately3600JavaLOC.
ForStepII,weextendedcrawler4j[2]byaddingsup-portforcollectingformsandJavaScriptcode,extract-ingconstraintsfromtheforms,andgeneratingZ3asser-tions.
TodealwithJavaScript,weusedanextensionoftheNarcissusJavaScriptengine[3],whichaddstheabil-itytoevaluateJavaScriptcodesymbolically.
Then,con-straintsextractedfromJavaScriptrelatedtoforminputsaretransformedandcombinedwiththeformconstraintsandsolvedbyZ3.
Togenerateserver-sideexecutiontraces,weleveragedXdebug[5],anopensourcedebuggerforPHPcode.
NotethatXdebug,likeanydebuggingtool,imposesper-formanceissuessuchasHTTPresponsesdelaysduetotracegeneration.
Therefore,tomaintainacceptableper-formance,NAVEXinvokesXdebugandanalyzestracesondemand.
Broadly,thetechniquesimplementedinNAVEXcanbeusedtogenerateexploitsfornon-PHPwebapplica-tions.
Atanimplementationlevel,NAVEXisapplicabletootherserver-sidelanguagesifthetargetsourcecodeisrepresentedasCPGs,modelsofthetargetlanguagefea-tures(i.
e.
,built-infunctions,operators,etc.
)assolverspecicationsareavailable,andsuitableserver-sideexe-cutiontracingtoolisused.
NAVEXisanopen-sourcesoftwareavailableathttps://github.
com/aalhuz/navex5EvaluationDataset.
WeevaluatedNAVEXon26real-worldPHPap-plicationswithacombinedcodebaseof3.
2MSLOCand22.
7KPHPlesasshowninTable1.
Ourcriteriaforse-lectingtheapplicationsinclude:(i)evaluationonthelat-estversionsofpopular,complexandlargePHPapplica-tionssuchasJoomla,HotCRP,andWordPress,and(ii)comparisonofNAVEXonthesametestapplica-tionsusedbystate-of-the-artworkinexploitgenera-tion(e.
g.
,Chainsaw[7])andvulnerabilityanalysis(e.
g.
,RIPS[15],[16]).
Setup.
NAVEXwasdeployedonUbuntu12.
04LTSVMwith2-coresof2.
4GHzeachand40GBRAM.
WerstgeneratedtheenhancedCPGandusedittondex-ploitablepathsforallthe26applications.
Then,wede-ployedtheapplicationsthathaveexploitablepaths.
Thedeploymentprocessincludes:installingeachapplicationonaserver,creatinglogincredentialsforeachrole,andpopulatingtheapplicationdatabasewithinitialdatabynavigatingtheapplicationandsubmittingformswhennecessary.
Wetakeasnapshotofeachapplication'sdatabaseanduseitaftereachcrawlingtorestoretheorig-inalstateofthedatabase.
Notethatduetospecicde-ploymentinstructionsforeachapplication,wecouldnotleverageautomationtoincludemoreapplicationstoeval-uate.
Givenampletimeformanualdeployment,NAVEXApplication(version)PHPFilesPHPSLOCmyBloggie(2.
1.
4)569090ScarfBeta19978DNscript601322WeBid(0.
5.
4)30065302Eve(1.
0)8905SchoolMate(1.
5.
4)6315375geccbblite(0.
1)11323FAQforge(1.
3.
2)171676WebChess(0.
9)295219WordPress(4.
7.
4)699181257HotCRP(2.
100)14557717HotCRP(2.
60)4314870Zen-Cart(1.
5.
5)1010109896OpenConf(6.
71)13421108osCommerce(2.
3.
4)68463613osCommerce(2.
3.
3)54149378Drupal(8.
3.
2)8626585094Gallery(3.
0.
9)51039218Joomla(3.
7.
0)2764302701LimeSurvey(3.
1.
1)3217965164Collabtive(3.
1)836172564Elgg(2.
3.
5)3201215870CPG(1.
5.
46)359305245MediaWiki(1.
30.
0)3680537913phpBB(2.
0.
23)7429164phpBB(3.
0.
11)387158756Table1:Subjectapplicationsofourevaluation.
AST,CFG,PDG,andsanitizationandDBtagsgeneration1hr25mGraphdatabasesize4.
15GiBTotal#nodes24,418,552Total#edges56,060,195Table2:StatisticsontheenhancedCPGgeneration.
canbeusedtoanalyzeandgenerateexploitsforhundredsorthousandsofapplications.
Summaryofresults.
NAVEXconstructedatotalof204exploits,ofwhich195areoninjection,and9areonlogicvulnerabilities.
Thesanitization-tags-enhancedCPGre-ducedfalsepositives(FPs)by87%onaverage.
Thein-clusionofclient-sidecodeanalysisforbuildingthenavi-gationgraphenhancedtheprecisionofexploitgenerationby54%onaverage.
Ontheevaluationset,NAVEXwasabletodrilldownasdeepas6HTTPrequeststostitchtogetherexploits.
Enhancedcodepropertygraphstatistics.
Foralltheapplicationsundertest,Table2showstheenhancedCPGconstructiontimeandsize.
Note,theenhancedgraphrepresentsthesourcecodeofallthe26applicationsun-dertest,indicatingthelowruntimeoverheadofNAVEX.
Navigationgraphstatistics.
Table3summarizesthetotaltimetogenerateconcreteexploitsinStepIIofNAVEX.
TheapplicationlistinthetablerepresentstheapplicationsforwhichNAVEXfoundexploitablepaths.
Therefore,ifanapplicationdidnothaveanyexploitablepath,NAVEXwillnotmodelitsnavigationbehavior.
Thenumberofrolesreectsthenumberofallaccounttypes(privileges)foreachapplication.
TheNGhasapproxi-mately59Knodesand1Medges.
5.
1ExploitsSQLIExploits.
NAVEXexaminedcallsto38627thUSENIXSecuritySymposiumUSENIXAssociationApplicationTotalCrawling,FormsSpec.
Generation,SolvingTime&NGBuildingTime#ofRolesmyBloggie2m2SchoolMate05WebChess1m36sec2Eve1m5sec1geccbblite57sec1Scarf1m44sec2FAQforge47sec1WeBid9m29sec2DNscript51sec1phpBB22m14sec2HotCRP(2.
60)30m13sec4osCommerce(2.
3.
3)2hr6m32sec2CPG24m40sec2MediaWiki15m30sec1LimeSurvey46sec2osCommerce(2.
3.
4)2hr19m1sec2OpenConf2m1sec2Gallery35m51sec2Collabtive24m2sec3Totaltime6hr27m18secGraphdatabasesize104.
44MiBTable3:StatisticsontheNavigationgraphgeneration.
mssqlquery,mysqlquery,mysqliquery,andsqlitequeryassinksforSQLIvulnerability.
Itreportedatotalof155SQLIexploitablesinkswitharunningtimeof37mand45sec.
Fromthese,itgenerated105concreteSQLIexploitsin7mand76secassummarizedinTable4.
NAVEXgeneratedSQLIexploitsforallapplicationsthathaveSQLIexploitablesinks(seeds)exceptforSchoolMate.
InSchoolMate,thecrawlerrecoveredonlythreeHTTPrequests.
Thisapplicationhas5differ-entroles,andforeachrole,ourcrawlerwasabletologinsuccessfully.
However,eachtimethecrawlersendsanHTTPrequestafterthelogin,theapplicationredi-rectstheexecutiontotheloginpage,whichmeansthattheapplicationdoesnotproperlymaintainusersessions.
Therefore,thecrawlerdidnotproceed,andthecover-agewaslow.
ThisfaultyapplicationwaschoseninourevaluationmainlytocomparetheresultsofNAVEXwithotherrelatedworkthatincludeditintheirtestapplica-tions.
Thereportedexploitablesinks,nevertheless,areconrmedtobetruepositives(TPs).
SelectedSQLIExploit.
OneoftheapplicationsforwhichNAVEXgeneratedalargenumberofSQLIexploitsisWeBid.
Listing4showsanexploitablesinklocatedintheuserinterface.
Anauthenticatedusercancheckotherusers'messages(line3),consequently,themessageswillbeaggedasread(line6).
ThegeneratedexploitforbothsinksisinListing5.
1$messageid=$_GET['id'];//nosanitization2//1stvul.
query3$sql="SELECT*FROM'".
$DBPrefix.
"messages'WHERE'id'='$messageid'";4.
.
.
.
5//2ndvul.
query6$sql="UPDATE'".
$DBPrefix.
"messages'SET'read'='1'WHERE'id'='$messageid'";Listing4:SimpliedcodeforSQLIvulnerabilityinWeBid.
ApplicationSQLIExp.
SinksTPsFPsSQLIExploitsmyBloggie2222022Scarf0000DNscript1101WeBid4040040Eve5505SchoolMate505000geccbblite4404FAQforge1414014WebChess1313013osCommerce(2.
3.
3)1101phpBB(2.
0.
23)5505Total1551550105Table4:SummaryofthegeneratedSQLIexploitablesinksandexploits.
ApplicationXSSExp.
SinksTPsFPsXSSexploitsmyBloggie2202Scarf1101DNscript1101WeBid12848Eve2202SchoolMate111100FAQforge7707WebChess1414014HotCRP(2.
60)5505osCommerce(2.
3.
4)5505osCommerce(2.
3.
3)4645142CPG111100MediaWiki1101phpBB(2.
0.
23)151502Total133128590Table5:SummaryofthegeneratedXSSseedsandexploits.
1http://localhost/WeBid/user_login.
phpPOST[username=user,password=pass,action=login]2http://localhost/WeBid/index.
php3http://localhost/WeBid/user_menu.
php4http://localhost/WeBid/yourmessages.
phpid=1'OR'1'='1Listing5:SQLIexploitgeneratedforthesinksinListing4.
XSSExploits.
NAVEXexaminedcallstoechoandprintPHPfunctionsassinksforXSSvulnerability.
Itfoundatotalof133XSSexploitablesinks,5ofwhicharefalsepositives,in1hand49m.
Itsuccessfullygener-ated90XSSexploitsforthe133sinksin40mand12secasshowninTable5.
Forallexploitablesinks,NAVEXgeneratedXSSexploitsexceptforSchoolMate,duetothereportedproblem.
Note,weconsideranexploitazero-dayiftheexploitinanactiveapplicationwasnotreportedbeforeandhasasignicanteffect,whichisnotthecaseforthevulnera-bilityinMediaWikiforinstance.
SelectedXSSExploit.
ForosCommerce2.
3.
4,NAVEXgenerated5XSSexploits.
Inthefollowing,wedemon-strateoneoftheseexploits,whichillustratesthepreci-sionofouranalysisincapturingtheeffectofcustomandbuilt-insanitizationfunctionsalongdifferentpathstosinks.
Listing6showsthevulnerablesink(echo)whereuserinput$HTTPGETVARS['page']passesthrough3differentfunctionsanditisnallyprocessedbyeitherhtmlspecialcharsorstrtrPHPfunc-USENIXAssociation27thUSENIXSecuritySymposium387tions.
NAVEXdidnotreportthepathsgoingthroughhtmlspecialcharsasexploitablebecauseitisasuf-cientXSSsanitizationfunction.
Ontheotherhand,itreportedthepathsthatincludestrtr,whichisnotatypicalsanitizationfunctionforXSS,asvulnerable.
Inthisexample,strtrreplacesdoublequoteswith"whichisnotsufcienttopreventXSS.
NAVEXinferredthesemanticsofthisfunction(throughitsmodelingofmanyPHPfunctionsassolverspecications)andusedthesolvertondanXSSattackstringthatdoesnotin-cludedoublequotesfromourXSSattackdictionary.
Ad-ditionally,tobreakouttheoutersinglequotes,theattackstringshouldhaveasinglequote('HTMLentity)encoded(%26%2339%3B).
Asaresult,thesolverselected%26%2339%3B-alert(1)-%26%2339%3Basama-licioususerinputthatsatisesthepathconstraints.
Listing7showstheexploitconstructedautomaticallyforthisvulnerability.
1echo''"'));13.
.
.
}14//3rdfunction15functiontep_parse_input_field_data($data,$parse){16returnstrtr(trim($data),$parse);}Listing6:SimpliedcodeforXSSvulnerabilityinosCommerce2.
3.
4.
1http://localhost/oscommerce-2.
3.
4/catalog/admin/login.
phpaction=processPOST[username=admin@test.
com,password=pass]2http://localhost/oscommerce-2.
3.
4/catalog/admin/index.
php3http://localhost/oscommerce-2.
3.
4/catalog/admin/reviews.
php4http://localhost/oscommerce-2.
3.
4/catalog/admin/reviews.
phppage=%26%2339%3B-alert(1)-%26%2339%3BListing7:AnXSSexploitgeneratedforListing6.
EARExploits.
NAVEXexaminedatotalof246callstoheaderfunction(EARsource)in17mand17sec.
Itfound19benignEARand3maliciousEARvulnerabili-ties.
Itsuccessfullygenerated9exploitsforthe22EARvulnerabilitiescombinedassummarizedinTable6.
NotethatinthecaseofEAR,anexploitisasequenceofHTTPrequestscausesthecodeaftertheredirectionfunctiontoexecute.
CodeExecutionExploits.
NAVEXexaminedallcallstoApplicationBenignEARSinksMaliciousEARSinksFPsEARExploitsmyBloggie7000WeBid0101Eve1001HotCRP(2.
100)1001HotCRP(2.
60)1001OpenConf4011osCommerce(2.
3.
4)0101osCommerce(2.
3.
3)0101Gallery2000Joomla0010LimeSurvey1000Collabtive1001MediaWiki1011Total19339Table6:SummaryofthegeneratedEARseedsandexploits.
thePHPfunctioneval,atotalof98callsinourdataset,in21mand20sec.
Allthecallsarenotvulnerable,andtherefore,NAVEXdidreportanyexploitablecodeexecutionsinks,andnoexploitsweregenerated.
CommandInjectionExploits.
NAVEXexaminedallcallstoexec,expectpopen,passthru,pcntlexec,popen,procopen,shellexec,system,mail,andbacktickoperator,atotalof350calls,in22mand32sec.
NAVEXdidnotndanyvulnerablesinks.
FileInclusionExploits.
NAVEXexaminedatotalof8063callstoinclude,includeonce,require,andrequireoncein27mand58sec.
Itmarked1sinkasexploitableinWeBid.
However,anexploitcouldnotbegeneratedbecausetheunsanitizedlename(userin-put)isprexedandpostxedwithsomeconstantstrings,whichcannotbeoverwrittenbyamaliciousinput.
5.
2MeasurementsPerformanceandscalability.
Figure5showstheper-formanceofNAVEXmeasuredbythetotaltimetondexploitablesinksandtogenerateexploitspervulnerabil-itytype.
Note,foreachvulnerabilitytype,thebluebarshowsthetotaltimeoftheanalysisofStepI,forallap-plicationsundertest.
Theorangebar,ontheotherhand,recordsthetotaltimespentbyStepII,fortheapplica-tionsthathaveexploitablesinks.
Dynamicanalysiscoverage.
WeconsiderthenumberofstaticallyidentiedvulnerabilitiesbyStepIasabaselinetoassessthecoverageofStepII.
NAVEXsuccessfullyconstructed105exploitsfor155SQLIsinks,90exploitsfor128XSSsinks,and9exploitsfor19EARvulnerabilities.
Overall,thetotalcoverageofStepIIis68%incomparisonwiththetotalvulnerablesinksforallapplications.
Effectofsanitizationtagsoncodepropertygraphs.
Figure6showstheeffectofenhancingtheCPGwithsan-itizationandDBtagsonthetotalnumberofvulnerablesinks.
Theorangebarshowsthetotalnumberofvulner-ablesinkswiththeenhancements,showingreductionsinfalsepositives.
Overall,thenumberofreportedvulner-38827thUSENIXSecuritySymposiumUSENIXAssociationFigure5:PerformanceofNAVEXforeachvulnerabilitytype.
Note,zerovaluesrefertotheabsenceofexploits.
Figure6:Theeffectofsanitization-tag-enhancedCPGinre-ducingfalsepositivesinvulnerablesinknding.
ForSQLI,thenumbersshowthe#ofsinksusingsanitizationandDBproper-ties.
ablesinksforeachvulnerabilitytypeisreduced,onanaverage,by87%duetoenhancementsimplementedonCPGstosignicantlycut-downfalsepositives.
Effectofclient-sidecodeanalysis.
Oneofthecontri-butionsofourworkistheprecisehandlingofclient-sidecodeduringtheNGconstruction.
Formsarecommonartifactsinmodernwebapplications.
Inourdataset,wecountedthefrequencyofusingformstoreceivedatafromusers.
Wefoundoutthatthenumberofuniqueformsinallapplicationsrangesfrom3(asingeccbblite)to186(asinWeBid)withanaverageof45form/application.
Additionally,Figure7validatesourclaimthatinordertoimprovethecoverageandconse-quentlygeneratemoreexploitsindeployedapplications,wemustsupportinputgenerationandconstraintsextrac-tionfromformsandJavaScriptcode.
ItcanbeseenfromFigure7thatNAVEX'sprecisionsignicantlyincreases.
Additionally,wemeasuredthemaximumlengthofallnavigationpathsleadingtoallexploitablesinks.
ForSQLIandEARexploits,wefoundthatthemaximumex-ploitlengthis5whereasforXSSis6.
5.
3ComparisonwithRelatedWorkWecomparetheresultsofNAVEXwithotherrelatedworksbasedonthefollowing:(1)commonsubjectappli-cations(andsameversionnumbers),(2)commonvulner-abilitytypes,and(3)knowledgeofhowtheresultsoftherelatedworkarecounted.
SeveralrelatedworkmetthosecriteriasuchasCRAXweb[22],RIPS[15],[16],[31],Ardilla[25],andChainsaw[7].
However,sinceChainsaw[7],themostrecentrelatedwork,providedadetailedcomparisonbetweentheirworkand[22],[31],Figure7:Theenhancementonexploitgenerationprecisionduetoclient-sidecodeanalysis.
and[25],wecompareNAVEXwithChainsaw,RIPS,and[16].
Vulnerabilitydetection.
InTable7,wecompareRIPS,Chainsaw,and[16]withNAVEXintermsoftheto-talnumberofthereportedSQLIandXSSvulnerabili-ties.
ComparedtoChainsaw,NAVEXfoundthesamenumberofXSSandSQLIvulnerabilitiesinscarfandEve,nevertheless,itreportedmorevulnerablesinksformyBloggie.
Inaddition,NAVEXfound71vulnerablesinksinHotCRP,osCommerce,andphpBBbecauseitcanhandleobject-orientedPHPcode,whichisnotavail-ableinChainsaw.
ComparedtoRIPS,NAVEXfound19morevulnerablesinksforphpBB,osCommerce,andmyBloggie.
Itmissed2vulnerablesinksinHotCRPduetomissingedgesinthecodepropertygraphthatrepre-sentdynamicfunctioncalls.
Exploitgeneration.
SinceChainsawsupportsgen-eratingexploitsforXSSandSQLI,wecompareittoNAVEXwithrespecttothetotalnumberofthegener-atedSQLIandXSSexploitsaswellassomeperformancemeasurements(seeTable8).
NAVEXconstructed19moreexploitsinWeBid,myBloggie,geccbblite,WebChess,andFAQforge,andachievedthesameforEve,scarf,andDNscript.
ForSchoolMate,NAVEXdidnotgenerateexploitsduetoissuesrelatedtomain-taininguserssessions(asdiscussedearlier).
SinceinChainsawtheexploitgenerationisdonestatically,itwasabletogenerateexploitsforthisapplication.
NAVEXsignicantlyoutperformedChainsawintermsofefciency.
Chainsawgeneratedtheexploitsin112minwhileNAVEXtook25minand2sec.
Inad-dition,wecontrastthetotaltimetobuildandsearchthenavigationgraphinNAVEX(18m26sec)withthetotaltimetoconstructandsearchtheRenedWorkowGraph(RWFG)(1day13h21m)inChainsaw.
ThisindicatesthatthetechniquesusedinNAVEXimprovedtheexploitgenerationefciencywithoutlosingprecision.
5.
4LimitationsandDiscussionUnsupportedfeatures.
Certainfeaturesofwebapplica-tionsarenotyetsupportedandthereforelimitourcover-age.
Forexample,formsthathaveinputsoftypefilerequiretheusertoselectanduploadanactuallefromUSENIXAssociation27thUSENIXSecuritySymposium389ApplicationRIPS[15][16]Chainsaw[7]NAVEXmyBloggie21SQLI(5)2224Scarf-SQLI(1)11Eve--77HotCRP(2.
60)7--5osCommerce(2.
3.
3)42--46phpBB(2.
0.
23)8(SQLI)--20Table7:Comparisononthenumberofidentied(SQLI+XSS)vulnerablesinks.
ApplicationChainsaw[7]NAVEXEve77SchoolMate540WebChess2527FAQforge821geccbblite34myBloggie2224Scarf11DNscript22WeBid4748Totalexploitgenerationtime112m25m2secTotalNGconstruction&solvingtime1day13h21m18m26secTable8:Comparisononthenumberofgenerated(SQLI+XSS)exploits.
thelocalsystem.
Inagiventestsetting,thiscanbemadetoworkwithoursolver,buttomakethisworkacrossallplatformsrequiresmoreengineeringeffort.
Anotheris-sueisofderivingTACformulasfromgraphnodesauto-matically.
Itisachallengingprocessthatinvolvesan-alyzingeachASTnodeandsupportingdifferentnodestructuresforeachnodetype.
Forexample,theleft-handsideofanassignmentstatementinPHPcanbeasim-plevariable,aconstant,afunctioncall,nestedfunctioncalls,etc.
Wehavecarefullyconsideredthesecases,andNAVEXhasthesupportformostsuchnodetypesandstructures,yetthereareafewinstancesstillunderde-velopment.
Inourdataset,NAVEXincorrectlyaggedonly5sinksasXSSexploitableinosCommerce2.
3.
3andWeBid.
InPHP,staticallyhandlingdynamiccallstofunctionsischallenging.
NAVEXutilizesCPGs,whichdonothavefullsupportforresolvingdynamicfunctioncalls.
However,thisdidnothaveabigimpactontheresultsreportedbyNAVEX.
Forinstance,therewere3falsepositivesreportedforEARvulnerabilityinJoomla,OpenConf,andMediaWiki.
6RelatedWorkExploitgenerationforwebapplications.
Exploitgen-erationhasseenalotofinterestinbinaryapplica-tion[8,14,21].
Forwebapplications,theclosestworktoNAVEXisChainsaw[7],asystemthatusespurelystaticanalysistobuildconcreteexploits.
NAVEXdiffersfromChainsawin2aspects:(i)itperformsacombinationofdynamicandstaticanalyses,whichenablesittobetterscaletolargeapplicationsandtondmoreexploits,(ii)itsupportsndingexploitsformultipleclassesofvulner-abilities.
AdditionalrelatedworksincludeArdilla[25],whichusesconcolicexecutionandtainttrackingtocon-structSQLIandXSSattackvectors;CRAXweb[22],whichemploysconcreteandsymbolicexecutionsup-portedbyaconstraintsolvertogenerateSQLIandXSSexploits.
QED[27]generatesrst-orderSQLIandXSSattacksusingstaticanalysisandmodelcheckingforJavawebapplications.
[32]generatesinputsthatexposeSQLIvulnerabilitiesusingconcolicexecutionofPHPapplica-tions.
EKHunter[19]combinesstaticanalysisandcon-straintsolvingtondexploitsinfor-crimewebappli-cations.
WAPTEC[13]andNoTamper[12]generateexploitsforparameter-tamperingvulnerabilities.
Theseworks,however,arelimitedtosinglePHPmodulesanddonotconsiderwhole-applicationpaths.
Modelingwithcodepropertygraphs.
Yamaguchietal.
[33]introducedthenotionofCPGsforvulnerabilitymodelinganddiscoveryinCprograms.
Inafollow-upwork[9],theyappliedCPGsforvulnerabilitydiscoveryonPHPapplications.
WhileourworkusestheexibilityandefciencythatCPGsoffer,ourproblemgoesastepfurthertogenerateactualexecutableexploits.
Asacon-sequence,weenhanceCPGswithadditionalattributes.
Vulnerabilityanalysis.
Thereisalargebodyofre-searchthatstudiedserver-sidevulnerabilitydetection.
Broadly,therearestaticanalysisapproaches(suchas[11,15,16,18,23,24,26,29–31,34]),dynamicanalysisapproaches(e.
g.
,[20,28]),andhybridapproaches(suchas[10]).
AlthoughNAVEXemployssomeoftheseanal-ysistechniquestondvulnerabilities,theaimofNAVEXisdifferentfromtheseworksasitconstructsexploitsfortheidentiedvulnerabilities.
OurnavigationmodelingisinspiredbyMiMoSA[11],whichisasystemthatndsdataandworkowvulnerabilitiesbyanalyzingmodulesofwebapplications.
NAVEXadvancestheanalysisbycombiningstaticanddynamicanalysestoconstructcon-creteexploitsforlargewebapplications.
7ConclusionsInthispaper,wepresentNAVEX,anautomaticexploitgenerationsystemthattakesintoaccountthedynamicfeaturesandthenavigationalcomplexitiesofmodernwebapplications.
Onourdataset,NAVEXconstructedatotalof204exploits,ofwhich195areontaint-stylevulnerabilities,and9areonlogicvulnerabilities.
WedemonstratedthatNAVEXsignicantlyoutperformspriorworkontheprecision,efciency,andscalabilityofexploitgeneration.
AcknowledgmentsWethankCurtThiemeforhissupportwiththeap-plications'deployment.
WealsothankAdamDoupeandtheanonymousreviewersfortheirfeedback.
ThismaterialissupportedinpartbyNSFunderGrantNos.
CNS-1514472,DGE-1069311andbyDARPAunderanAFOSRcontractFA8650-15-C-7561.
39027thUSENIXSecuritySymposiumUSENIXAssociationReferences[1]Apachetinkerpop.
https://tinkerpop.
apache.
org/gremlin.
html,2018.
Accessed:2018-05-1.
[2]crawler4j.
https://github.
com/yasserg/crawler4j,2018.
Accessed:2018-05-1.
[3]Narcissus.
https://github.
com/mozilla/narcissus/,2018.
Ac-cessed:2018-05-1.
[4]Theneo4jgraphplatformthe#1platformforconnecteddata.
https://neo4j.
com/,2018.
Accessed:2018-05-1.
[5]Xdebug-debuggerandprolertoolforphp.
https://xdebug.
org/,2018.
Accessed:2018-05-1.
[6]Xsslterevasioncheatsheet.
https://www.
owasp.
org/index.
php/XSSFilterEvasionCheatSheet,2018.
Accessed:2018-05-1.
[7]ALHUZALI,A.
,ESHETE,B.
,GJOMEMO,R.
,ANDVENKATAKRISHNAN,V.
Chainsaw:Chainedautomatedworkow-basedexploitgeneration.
InProceedingsofthe2016ACMSIGSACConferenceonComputerandCommunicationsSecurity(CCS)(2016),ACM,pp.
641–652.
[8]AVGERINOS,T.
,CHA,S.
K.
,HAO,B.
L.
T.
,ANDBRUM-LEY,D.
AEG:AutomaticExploitGeneration.
InNDSS(2011),vol.
11,pp.
59–66.
[9]BACKES,M.
,RIECK,K.
,SKORUPPA,M.
,STOCK,B.
,ANDYAMAGUCHI,F.
Efcientandexiblediscoveryofphpappli-cationvulnerabilities.
InSecurityandPrivacy(EuroS&P),2017IEEEEuropeanSymposiumon(2017),IEEE,pp.
334–349.
[10]BALZAROTTI,D.
,COVA,M.
,FELMETSGER,V.
,JOVANOVIC,N.
,KIRDA,E.
,KRUEGEL,C.
,ANDVIGNA,G.
Saner:Com-posingstaticanddynamicanalysistovalidatesanitizationinwebapplications.
In2008IEEESymposiumonSecurityandPrivacy(sp2008)(2008),pp.
387–401.
[11]BALZAROTTI,D.
,COVA,M.
,FELMETSGER,V.
V.
,ANDVI-GNA,G.
Multi-moduleVulnerabilityAnalysisofWeb-basedAp-plications.
Inthe14thACMConferenceonComputerandCom-municationsSecurity(CCS)(2007),pp.
25–35.
[12]BISHT,P.
,HINRICHS,T.
,SKRUPSKY,N.
,BOBROWICZ,R.
,ANDVENKATAKRISHNAN,V.
Notamper:automaticblackboxdetectionofparametertamperingopportunitiesinwebapplica-tions.
InProceedingsofthe17thACMconferenceonComputerandcommunicationssecurity(2010),ACM,pp.
607–618.
[13]BISHT,P.
,HINRICHS,T.
,SKRUPSKY,N.
,ANDVENKATAKR-ISHNAN,V.
WAPTEC:WhiteboxAnalysisofWebApplicationsforParameterTamperingExploitConstruction.
Inthe18thACMconferenceonComputerandcommunicationssecurity(2011),pp.
575–586.
[14]BRUMLEY,D.
,POOSANKAM,P.
,SONG,D.
,ANDZHENG,J.
AutomaticPatch-BasedExploitGenerationisPossible:Tech-niquesandImplications.
InSecurityandPrivacy,2008.
SP2008.
IEEESymposiumon(2008),pp.
143–157.
[15]DAHSE,J.
,ANDHOLZ,T.
SimulationofBuilt-inPHPFeaturesforPreciseStaticCodeAnalysis.
InSymposiumonNetworkandDistributedSystemSecurity(NDSS)(2014).
[16]DAHSE,J.
,ANDHOLZ,T.
StaticDetectionofSecond-OrderVulnerabilitiesinWebApplications.
In23rdUSENIXSecuritySymposium(USENIXSecurity)(2014),pp.
989–1003.
[17]DEMOURA,L.
,ANDBJRNER,N.
Z3:Anefcientsmtsolver.
InToolsandAlgorithmsfortheConstructionandAnalysisofSys-tems.
Springer,2008,pp.
337–340.
[18]DOUPE,A.
,BOE,B.
,KRUEGEL,C.
,ANDVIGNA,G.
Feartheear:discoveringandmitigatingexecutionafterredirectvulnera-bilities.
InProceedingsofthe18thACMconferenceonComputerandcommunicationssecurity(2011),ACM,pp.
251–262.
[19]ESHETE,B.
,ALHUZALI,A.
,MONSHIZADEH,M.
,PORRAS,P.
A.
,VENKATAKRISHNAN,V.
N.
,ANDYEGNESWARAN,V.
EKHunter:ACounter-OffensiveToolkitforExploitKitInltra-tion.
In22ndAnnualNetworkandDistributedSystemSecuritySymposium,NDSS(2015).
[20]HALDAR,V.
,CHANDRA,D.
,ANDFRANZ,M.
Dynamictaintpropagationforjava.
In21stAnnualComputerSecurityApplica-tionsConference(ACSAC)(2005),pp.
9–pp.
[21]HU,H.
,CHUA,Z.
L.
,ADRIAN,S.
,SAXENA,P.
,ANDLIANG,Z.
AutomaticGenerationofData-OrientedExploits.
In24thUSENIXSecuritySymposium(USENIXSecurity15)(2015),USENIXAssociation,pp.
177–192.
[22]HUANG,S.
,LU,H.
,LEONG,W.
,ANDLIU,H.
CRAXweb:AutomaticWebApplicationTestingandAttackGeneration.
InIEEE7thInternationalConferenceonSoftwareSecurityandRe-liability,SERE(2013),pp.
208–217.
[23]HUANG,Y.
-W.
,YU,F.
,HANG,C.
,TSAI,C.
-H.
,LEE,D.
-T.
,ANDKUO,S.
-Y.
Securingwebapplicationcodebystaticanal-ysisandruntimeprotection.
InProceedingsofthe13thinterna-tionalconferenceonWorldWideWeb(2004),ACM,pp.
40–52.
[24]JOVANOVIC,N.
,KRUEGEL,C.
,ANDKIRDA,E.
Pixy:AStaticAnalysistoolforDetectingWebApplicationVulnerabilities.
InSecurityandPrivacy,2006IEEESymposiumon(2006),pp.
6–pp.
[25]KIEYZUN,A.
,GUO,P.
J.
,JAYARAMAN,K.
,ANDERNST,M.
D.
AutomaticCreationofSQLInjectionandCross-SiteScriptingAttacks.
InIEEE31stInternationalConferenceonSoft-wareEngineering(ICSE)(2009),pp.
199–209.
[26]LIVSHITS,V.
B.
,ANDLAM,M.
S.
FindingSecurityVulnerabil-itiesinJavaApplicationswithStaticAnalysis.
In14thUSENIXSecuritySymposium(Baltimore,Maryland,USA,2005).
[27]MARTIN,M.
,ANDLAM,M.
S.
Automaticgenerationofxssandsqlinjectionattackswithgoal-directedmodelchecking.
InPro-ceedingsofthe17thconferenceonSecuritysymposium(2008),pp.
31–43.
[28]NGUYEN-TUONG,A.
,GUARNIERI,S.
,GREENE,D.
,SHIRLEY,J.
,ANDEVANS,D.
Automaticallyhardeningwebapplicationsusingprecisetainting.
InIFIPInternationalInfor-mationSecurityConference(2005),Springer,pp.
295–307.
[29]SAMUEL,M.
,SAXENA,P.
,ANDSONG,D.
Context-sensitiveauto-sanitizationinwebtemplatinglanguagesusingtypequali-ers.
InProceedingsofthe18thACMconferenceonComputerandcommunicationssecurity(2011),pp.
587–600.
[30]SAXENA,P.
,MOLNAR,D.
,ANDLIVSHITS,B.
Scriptgard:au-tomaticcontext-sensitivesanitizationforlarge-scalelegacywebapplications.
InProceedingsofthe18thACMconferenceonComputerandcommunicationssecurity(2011),pp.
601–614.
[31]WASSERMANN,G.
,ANDSU,Z.
Soundandpreciseanalysisofwebapplicationsforinjectionvulnerabilities.
InACMSigplanNotices(2007),vol.
42,ACM,pp.
32–41.
[32]WASSERMANN,G.
,YU,D.
,CHANDER,A.
,DHURJATI,D.
,INAMURA,H.
,ANDSU,Z.
Dynamictestinputgenerationforwebapplications.
InProceedingsofthe2008internationalsym-posiumonSoftwaretestingandanalysis(2008),pp.
249–260.
[33]YAMAGUCHI,F.
,GOLDE,N.
,ARP,D.
,ANDRIECK,K.
Mod-elinganddiscoveringvulnerabilitieswithcodepropertygraphs.
InSecurityandPrivacy(SP),2014IEEESymposiumon(2014),IEEE,pp.
590–604.
[34]YU,F.
,ALKHALAF,M.
,ANDBULTAN,T.
Stranger:Anautomata-basedstringanalysistoolforphp.
InInternationalCon-ferenceonToolsandAlgorithmsfortheConstructionandAnaly-sisofSystems(2010),pp.
154–157.
USENIXAssociation27thUSENIXSecuritySymposium391[35]ZHENG,Y.
,ZHANG,X.
,ANDGANESH,V.
Z3-str:AZ3-basedStringSolverforWebApplicationAnalysis.
InProceedingsofthe20139thJointMeetingonFoundationsofSoftwareEngineer-ing(2013),pp.
114–124.
39227thUSENIXSecuritySymposiumUSENIXAssociation