interestjqueryeach

DeterminacyinStaticAnalysisforjQueryEsbenAndreasenAndersMllerAarhusUniversity{esbena,amoeller}@cs.
au.
dkAbstractStaticanalysisforJavaScriptcanpotentiallyhelpprogram-mersnderrorsearlyduringdevelopment.
Althoughmuchprogresshasbeenmadeonanalysistechniques,amajorob-stacleistheprevalenceoflibraries,inparticularjQuery,whichapplyprogrammingpatternsthathavedetrimentalconsequencesontheanalysisprecisionandperformance.
Previousworkondynamicdeterminacyanalysishasdemonstratedhowinformationaboutprogramexpressionsthatalwaysresolvetoaxedvalueinsomecallcontextmayleadtosignicantscalabilityimprovementsofstaticanaly-sisforsuchcode.
WepresentastaticdataowanalysisforJavaScriptthatinfersandexploitsdeterminacyinformationon-the-y,toenableanalysisofsomeofthemostcomplexpartsofjQuery.
Theanalysiscombinesselectivecontextandpathsensitivity,constantpropagation,andbranchpruning,basedonasystematicinvestigationofthemaincausesofanalysisimprecisionwhenusingamorebasicanalysis.
ThetechniquesareimplementedintheTAJSanalysistoolandevaluatedonacollectionofsmallprogramsthatusejQuery.
Ourresultsshowthattheproposedanalysistech-niquesboostbothprecisionandperformance,specicallyforinferringtypeinformationandcallgraphs.
CategoriesandSubjectDescriptorsD.
2.
4[SoftwareEn-gineering]]:Software/ProgramVericationGeneralTermsLanguages,Algorithms,VericationKeywordsJavaScript,programanalysis1.
IntroductionJavaScriptprogrammersneedbettertoolstohelpdetecter-rorsearlyduringdevelopment,transformcodeforrefac-toringoroptimization,andunderstandexistingcodebases.
Permissiontomakedigitalorhardcopiesofallorpartofthisworkforpersonalorclassroomuseisgrantedwithoutfeeprovidedthatcopiesarenotmadeordistributedforprotorcommercialadvantageandthatcopiesbearthisnoticeandthefullcitationontherstpage.
Copyrightsforcomponentsofthisworkownedbyothersthantheauthor(s)mustbehonored.
Abstractingwithcreditispermitted.
Tocopyotherwise,orrepublish,topostonserversortoredistributetolists,requirespriorspecicpermissionand/orafee.
Requestpermissionsfrompermissions@acm.
org.
OOPSLA'14,October19–21,2014,Portland,OR,USA.
Copyrightisheldbytheowner/author(s).
PublicationrightslicensedtoACM.
ACM978-1-4503-2585-1/14/10.
.
.
$15.
00.
http://dx.
doi.
org/10.
1145/2660193.
26602141jQuery.
each("ajaxStartajaxStop.
.
.
ajaxSend".
split(""),2function(i,o){3jQuery.
fn[o]=function(f){4returnthis.
on(o,f);5};6});Figure1.
Asmallexampleofcode(abbreviatedwith".
.
.
")fromjQuery-1.
8.
0thatcauseschallengesforstaticanalysis.
Staticanalysismaybeafruitfulfoundationforsuchtools.
However,thedynamiclanguagefeaturesofJavaScriptarechallengingtoreasonaboutwithstaticanalysis,andtheprevalentuseoflibrariesisamajorobstacleforfurtherprogress.
MostJavaScriptwebapplicationstodayuselibrariestoprovideconvenientfunctionalityontopofthebasicbrowserAPI,andtheselibrariesgenerallyexploitthedynamiclan-guagefeaturesintensely.
Moreover,thelibrarycodeformanywebsitesisanorderofmagnitudelargerthantheap-plicationcodeitself.
Asurveyhasshownthat58%ofthetop10millionwebsitesusethejQuerylibrary,andithasamarketshareamongJavaScriptlibrariesof93.
4%[35].
ThismeansthatpracticalstaticanalysistoolsforJavaScriptwebapplicationsmustbeabletocopewithjQuery.
SincejQueryevolvesandnewversionsappearregularly,andthousandsofpluginsexist,writinganalysis-specicmodelsofthelibrary,forexampleasdetailedannotationsofthelibraryinterface,isnotaviableoption.
Instead,weneedtoimprovethestaticanalysistechniquestobecomeabletoreasonpreciselyandefcientlyabouttheprogrammingpatternsthatareusedinthelibrarycode.
Asanexample,considerwhatisrequiredforastaticanal-ysistoreasonaboutthesmallsnippetofjQuerylibrarycodeshowninFigure1.
Thiscodeconvertsastringintoanarray["ajaxStart","ajaxStop"ajaxSend"]andtheniteratesoverthisarrayusingthejQuery.
eachlibraryfunction,assigningafunctiontoapropertyoftheobjectjQuery.
fn,whichjQueryapplicationsuseasprototypeob-jectforHTMLnodesets.
Intherstiteration,forexam-ple,jQuery.
fn.
ajaxStartissettoafunctionthatpassesacallbackftothis.
on("ajaxStart",f).
Iftheanaly-sisdoesnothavepreciseinformationaboutthevalueofointheassignmentjQuery.
fn[o]orattheinnerexpres-1//Multifunctionalmethodtogetandsetvaluesofacollection2//Thevalue/scanoptionallybeexecutedifit'safunction3access:function(elems,fn,key,value,chainable,emptyGet,pass){4varexec,bulk=key==null,i=0,length=elems.
length;5//Setsmanyvalues6if(key&&typeofkey==="object"){7for(iinkey){8jQuery.
access(elems,fn,i,key[i],1,emptyGet,value);9}10chainable=1;11//Setsonevalue12}elseif(value!
==undefined){13//Optionally,functionvaluesgetexecutedifexecistrue14exec=pass===undefined&&jQuery.
isFunction(value);15if(bulk){16//Bulkoperationsonlyiteratewhenexecutingfunctionvalues17if(exec){18exec=fn;19fn=function(elem,key,value){20returnexec.
call(jQuery(elem),value);21};22//Otherwisetheyrunagainsttheentireset23}else{24fn.
call(elems,value);25fn=null;26}27}28if(fn){29for(;i[r1,r2]and[r1,r2,r3]:representunaryandbinaryoperators,wheretheresultisstoredinr2orr3,respectivelyFigure3.
ThemaininstructionsinTAJSowgraphs.
Thesub-latticesAbsentandAttrindicatewhethertheprop-ertymaybeabsent,and,ifpresent,whatattributes(Read-Only,DontDelete,DontEnum)itmayhave,andModtrackswhetherthepropertyhasbeenmodiedwithinthecurrentfunction(see[15]fordetails).
Eachabstractobjectalsocar-riesascopechain,representedasanitelistofsetsofobjectaddresses.
ValuesaremodeledbytheproductlatticeValuewithacomponentforeachkindofvalue:undefined,null,booleans,numbers,strings,andreferencestoobjects.
Foreachkindofprimitivevalue,thecorrespondinglatticeischosenastheconstantpropagationlattice[36],withrep-resentinganypossiblevalueand⊥representingthesituationwherethevaluecannothavethattype.
TheNumandStringlattices,modelingnumbersandstrings,haveadditionallat-ticeelementsforrepresentingunknownarrayindexvalues.
TheStringlatticefurthermorehasspeciallatticeelementsthatgroupstringswithacommonprex[18].
NotethatTAJSmodelsprogramvariablesaspropertiesofactivationobjects,directlycorrespondingtotheECMAScriptspecication[6].
Thetransferfunctionsfortheowgraphnodesmodeltheeffectsoftheinstructions,includingtypecoercions.
N:owgraphnodesR:registersC:contextsL:objectaddressesP:propertynamesAnalysisLattice=(C*N→State)*CallGraphCallGraph=P(C*N*C*N)State=(L→Obj)*Registers*ExecutionContextRegisters=R→ValueExecutionContext=ScopeChain*P(L)*P(L)ScopeChain=P(L)Obj=(P→Value*Absent*Attr*Mod)*ScopeChainValue=Undef*Null*Bool*Num*String*P(L)Figure4.
BasicabstractdomainsusedbyTAJS.
Initsmostbasicmode,TAJSusesallocationsiteabstrac-tionwhereobjectsaredistinguishedonlybytheirallocationsite,thatis,L=N.
Thedefaultbehavior,however,addsrecencyabstraction[3]todistinguishthemostrecentlyallo-catedobjectfromolderonesoriginatingfromthesameallo-cationsite,therebyenablingstrongupdatesformanywriteoperations.
Sinceasingleprimitiveinstructionmaycreatemultiplenewobjects,forexampleatcallinstructions,TAJSfurtherdistinguishesbetweenobjectsofdifferentkinds,forexample,activationobjectsandargumentsobjects.
TAJSemploysabasicformofpathsensitivitybypruningcertaininfeasibledataowatbranches[1].
Forexample,ataconditionalstatementif(x)S1elseS2,theanalysismayassumethatxisnotfalse,undefined,oranyother"falsy"valueattheentryofS1andconverselyatS2.
Insituationswherepruninginfeasiblevaluesleadsto⊥Value(forexample,ifxisconstant)theentireabstractstatecanbereducedto⊥State,therebyconcludingthatthecorrespondingbranchisunreachableinthegivencallcontext.
Thedefaultsettingforcontextsensitivityisbasedontheideaofobjectsensitivity[26],usingC=P(L),wherecallcontextsaredistinguishedbytheabstractvalueofthis(butonlyforfunctionsthatcontainthis).
OtheranalysistechniquesusedbyTAJSincludelazypropagation[16],abstractgarbagecollection[25],modi-edags[15],modelingoftheHTMLDOMandbrowserAPI[17],andon-the-yeliminationofevalcalls[18],butthosetechniquesarenotessentialtounderstandtheexten-sionsweconsiderinthispaper.
4.
IntegratingDeterminacyinStaticAnalysisTheconceptofdeterminacytsnaturallyintostaticanaly-sis,asknownfromcontextsensitiveconstantpropagationforprimitivevaluesandsingle-targetresolutionforobjectsinmanyexistinganalyzers.
Adeterminacyfactinstaticanal-ysisisthensimplyadataowfactthatanabstractvalueintheabstractstateatagivenowgraphnodeandcontextisasingle,concretevalue,suchas,astringconstantorafunc-tionobject.
Thus,constantpropagationisinitselfasimpleformofdeterminacyanalysis,whichTAJSalreadyexploitsatdynamicpropertyaccess(bytreatingx[y]asx.
pifyisknowntobeaconstantstringp)andatconditionals(byprun-inginfeasibleow,asmentionedintheprevioussection).
Thisraisestwoquestions:(1)ItispossibletoextendTAJStoinfermoredeterminacyinformation(2)CanweexploitthatadditionalinformationtoimproveanalysisofjQueryOurstartingpointisananalysisthatsuffersfromfatalimprecisionandextremememoryandtimeconsump-tionwhengivenatrivialJavaScriptapplicationthatloadsjQueryanddoesnothingelse.
Wenowpresentsomesim-pletechniquesthathavehelpedusrevealthemaincausesofimprecisionorredundantworkintheanalysis,tosuggestopportunitiesforinferringandexploitingmoredeterminacyinformation.
First,weinterruptthedataowxpointsolverafteranumberofiterations,e.
g.
10000nodetransferfunctionexe-cutions.
Sincethexpointhasnotbeenreached,thecurrentabstractstatesaregenerallynotasoundapproximationofthepossibleprogrambehavior,however,theycanstillbeusefulforidentifyinglikelyspuriousdataow.
Wedeneaheuris-ticmeasureofsuspiciousnessontheabstractvaluesandthecallgraph:Anabstractvalueissuspiciousifithasmanydifferenttypes,wherewecategorizetypesasnumbers,strings,booleans,functions,arrays,nativeobjects,DOMobjects,andotherobjects.
Acallgraphissuspiciousatagivencallsiteandcallcontextifthatpairhasalargenumberofcallees.
Wehavefoundthatahighdegreeofsuspiciousnessoftenindicatesahighamountofspuriousdataow,somanuallyinspectingthemostsuspiciouscasesoftenprovidesvalu-ableinsightsaboutthecausesofimprecisionandpotentialsolutions.
Usingadeltadebuggingtool,suchasJSDelta2,withasuspiciousnessthresholdaspredicatehelpsndingsmallerprogramsthatexhibitthebottlenecksofinterest.
Anadditionaleffectivetechniquetoreducethecomplexityofthetaskistoapplyasimpleformofprogramslicingbyre-movingthefunctionsandconditionalbranchesinthejQuerycodethatarenotusedbythegivenapplicationatruntime.
Basedonsuchaninvestigationofimprecisionwhenat-temptingtoanalyzeprogramsthatusejQuery,wepropose2https://github.
com/wala/jsdeltathreeanalysisimprovementsrelatedtocontextandpathsen-sitivity:parametersensitivityasavariantofobjectsensitiv-ity,loopspecializationtoimproveprecisionofforloopsandfor-inloops,andcontextsensitiveheapabstractionforselectedallocationsites.
Eachimprovementcanbeex-pressedandimplementedasamanageableextensionoftheanalysisframeworkdescribedinSection3.
Specically,theabstractdomainsonlyrequiremodicationsofCandL.
5.
ParameterSensitivityAsindicatedbytheexamplesinFigures1and2,itiscriti-calthatcertainlibraryfunctionsareanalyzedcontextsen-sitively.
Objectsensitivityisnotsufcient,sincethisisnotusedbymanyofthefunctions.
Analternative,suchas1-CFA[32],whichincludesthecallsiteinthecontext,isalsoinsufcient,sincemanyofthelibraryfunctions,includ-ingeachandaccessfromourexamples,involvemulti-plelayersofnestedcalls.
Althoughthemoregeneraltech-niquek-CFA(or,thecallstringtechnique[31])mayhelp,ourstudyofimprecision,asdiscussedinSection4,suggeststhatweinsteadfocusontheabstractvaluesofselectedfunc-tionparameters.
Forexample,whatmattersforacalltotheclosureinline2inFigure1isnotthelocationofthecallsitebutthevaluesofitstwoparameters.
Forthisreason,wesug-gestanotionofparametersensitivity,whichcanbeseenasavariantofobjectsensitivitythatiseasilyincorporatedintotheexistingTAJSanalysisframework.
Thebasicconceptofparametersensitivityisnotnew–similartechniqueshavebeenusedinpointeranalysis[21]andtypeinference[27]–butithasnotbeeninvestigatedbeforehowitworksforJavaScriptlibrariesandwhenandhowitshouldbeapplied.
Theideainselectiveparametersensitivityisthatcertainfunctionsshouldbeanalyzedcontextsensitivelydependingontheabstractvaluesoftheirparametersatthecallsites.
IfweletAdenotethesetofallfunctionparameters(identiedbytheirpositioninthelistofactualparameters)wenowextendthenotionofcontextsfromC=P(L)to:C=P(L)*(AValue)Theinterpretationofacontext(t,a)∈Cisthattrepresentsthevalueofthis,asinSection3,theextracomponentaspeciesanabstractvalueforselectedparametersinAforthecurrentfunction.
Theanalysistransferfunctionsrequiremodicationsonlyforcallandconstruct:whencreatingacontext(t,a)∈C,thetcomponentiscreatedasbefore,andtheacomponentisfoundbyreadingtheabstractvaluesoftheselectedactualparametersinthecurrentabstractstate.
Withthisinfrastructureinplace,thequestionthatremainsishowtodecidewhichparameterstoselectwhenconstruct-ingthenewcontexts.
Selectingallparameterswilllikelybetoocostlyandresultinanexplosioninthenumberofcon-texts;selectingnoneisequivalenttoomittingtheanalysisextension.
BasedontheapproachexplainedinSection4weproposethefollowingsimpleheuristicthatperformsthese-lectionon-the-y,duringthestaticanalysis:Whenatransferfunctioncreatesanewcontext(t,a)atsomecallsite,weselectthoseparametersforinclu-sioninawhoseabstractvalueisaconcretestring(i.
e.
,aknownstringintheStringlattice)orasingleobjectaddress(i.
e.
,exactlyoneobjectallocationsite).
AccordingtothestructureofthedomainAnalysisLattice,thisextensionallowsustohavemultipleabstractstatesataprogrampoint,irrespectiveofthis.
Asanexample,iftheaccessfunctionfromFigure2iscalledtwice,ateachplacewithafunctionliteralasthesecondparameter(namedfn),thenthebodyoftheaccessfunctionwilleffectivelybeanalyzedtwice,whichpreventsthetwofunctionliteralsfrombeingmixedtogether.
Inthisway,theanalysisknowspreciselywhatfnreferstoineachcontext.
Thisincreasesprecisionatallcallstofninsideaccess,anditalsoworkssmoothlyinline8wherefnispassedasaparameterinarecursivecall.
RegardingtheexamplefromFigure1,theuseofparame-tersensitivitywillallowtheanalysistodistinguishbetweenthedifferentvaluesofoinline3.
However,moreprecisionimprovementsareneededtohandletheentireexamplesatis-factorily,whichwereturntoinSection7.
NoticehowTAJS'sconstantpropagationandcontextsen-sitiveinterproceduralanalysistwelltogether.
Allthefunc-tionsthatappearinFigure1maybeinvokedwithmanydifferentparametervalues,butourselectiveuseofparame-tersensitivityensuresthatthecentralparametersoftenhaveconstantvaluesineachcontext.
Inotherwords,thestaticanalysisinfersdeterminacyinformationthatisqualiedbyabstractcontexts,notbyconcretecallstacksasindynamicdeterminacyanalysis.
Otherstaticanalysisalgorithmsper-formcontextsensitiveconstantpropagation[28].
Inourset-ting,itisimportantthattheconstantpropagationincludesfoldingatoperators,forexample==and===inFigure2,andatnativeECMAScriptfunctions,forexamplesplitinFigure1,whichwediscussinSection8.
Astheextensionwithparametersensitivitymakestheanalysislatticeinnite-height(sincetheValuelatticethatwenowuseinChasinnitewidth),someformofwideningisneededtoensuretermination.
Wesimplyselectathresh-old,forexample100,specifyingthemaximumnumberofabstractstatesatanyprogrampoint.
Ifthislimitisexceeded,parametersensitivityisdisabledforthefunctionsinques-tion.
However,thisismostlyatheoreticalconcern:ifthenumberofabstractstatesgrowslarge,theanalysiswilllikelybeimpreciseandnotterminateanywaywithinareasonabletimebudget.
Theworst-casecomplexityoftheanalysisin-creasesdramaticallybythisextension.
Theinterestingques-tioniswhetherthiscomplexityoutweighstheincreasedpre-cision,whichwestudyexperimentallyinSection9.
1each:function(obj,callback,args){2varname,i=0,length=obj.
length,3isObj=length===undefined||jQuery.
isFunction(obj);4if(args){5if(isObj){6for(nameinobj){7if(callback.
apply(obj[name],args)===false){8break;9}}10}else{11for(;iapply(obj[i++],args)===false){13break;14}15}16}17//Aspecial,fast,caseforthemostcommonuseofeach18}else{19if(isObj){20for(nameinobj){21if(callback.
call(obj[name],name,obj[name])===false){22break;23}24}25}else{26for(;icall(obj[i],i,obj[i+false){28break;29}30}31}32}33returnobj;34}Figure5.
ThejQueryeachfunction.
6.
LoopSpecializationSomecentrallibraryfunctions,includingtheeachfunction(calledinline1inFigure1andshowninFigure5)andalsotheaccessfunction(Figure2)iteratethrougharrays,andwesometimesobserveacriticallossofprecision,intheformofanunknowndynamicpropertyread,iftheanalysisdoesnotdistinguishbetweentheindividualiterations.
Forexam-ple,intheforloopstartinginline26inFigure5itisimpor-tantthatthepossiblevaluesofiarenotmixedtogether.
Thecallbackisinvokedwithobj[i]astheparameter,soimpre-cisionofiwillpropagateto,forexample,finline4inFig-ure1.
ThismakestheanalysisunabletodistinguishbetweenthedifferentfunctionsinjQuery.
fn.
OneconsequenceofthisisthatsubsequentcallstojQuery.
fn.
eachwillpro-ducedataowtothefunctiononline3inFigure1,whichwillregisterthecallbackparameterasaneventhandler,ulti-matelyresultinginaproliferationofspuriousdataow.
6.
1SpecializationofforLoopsOursolutionistoperformasimplekindofloopunrollingduringtheanalysis.
Wedothisby,again,extendingthenotionofcontexts,addingyetanothercomponenttoC:CBValue)Here,Bisthesetoflocalvariablenamesoccurringintheprogram,andcorrespondstotheformerdenitionofCinSection5.
Theinterpretationofacontextb)∈Cisthatbdescribesthevaluesofselectedlocalvariables.
No-ticethatthenotionof"context"nownotonlycharacterizesinformationfromcallsites,butalsointraproceduralinfor-mation.
Whenevertheanalysisxpointsolverpropagatesabstractstatesintraprocedurally,thecontextsnowchangewhentheabstractvaluesofthevariablesinbchange.
Thisis,fortunately,easytoaccommodateintheTAJSimplemen-tation.
Similartoourapproachtoparametersensitivity,thequestioniswhichlocalvariablestoselectwhenconstructingb.
Weagainproposeasimpleheuristicthatdecideson-the-y:Whenacontextb)iscreated,weselectthoselo-calvariablesforinclusioninbwhoseabstractvalueisaconcreteinteger(asrepresentedintheNumlattice)inthecurrentabstractstate.
However,weincludeonlyvariablesthatappearsyntacticallyintheconditionandinthebodyofanon-nestedforloopinthecurrentfunction,andareinvolvedinadynamicpropertyreadoperation(i.
e.
asasub-expressionofe2ine1[e2]).
ApplyingthistechniquetotheeachfunctioninFigure5,theanalysiswillselectthelocalvariableiforspecializationandeffectivelyunrolltheforloops,creatinganewcon-textforeveryloopiteration.
Thiscanbeviewedasaformofpathsensitivity[4].
Observehowthisanalysisextensionimprovestheinferenceofdeterminacyinformation,espe-ciallywhencombinedwiththeparametersensitivitytech-niquefromSection5.
Theanalysisexploitsthisinformation,forexampletopreciselymodelwhichparametervaluesarepassedtothecallbackinline27.
Someformofwideningisobviouslyneededtoensuretermination,asinSection5.
Asapragmaticsolution,wechoosetorestrictthiscontextspecializationtoasmallrangeofnumericvalues,0to50.
Similartothediscussionabouttheincreasedtheoreticalworst-casecomplexityofaddingparametersensitivity,ourexperimentsinSection9showwhethertheextracomplexitycausedbythisadditionalex-tensionpaysoff.
6.
2Specializationoffor-inLoopsWenowconsiderthefor-inloops,whichcanoftenalsobenetfromcontextspecializationastheyplayacentralroleinmanylibraryfunctions,includingaccess(Figure2),each(Figure5),andextend(Figure6).
Theextendfunc-tionplaysacentralroleinjQueryforpopulatingitscoreobjects,butitisalsooftenusedinapplicationcodetocopypropertiesfromoneobjecttoanother.
Therstpart(lines2–23)inspecttheargumentsobjecttodeterminewhichofthemanypossiblewaysitisbeingused.
Inparticular,thissetstargettotheobjectbeingcopiedto,andibecomestheindexoftherstparametercontainingasourceobject.
Theoutermostforloop(lines24–49)theniteratesthroughthesourceobjects,andtheinnermostfor-inloop(lines28–49)iteratesthoughtheirproperties,copyingthemtothetargetobject.
Thedeepvariabledetermineswhethertouseshallowordeepcopying.
Noticeagainhowinterproceduralconstantpropagationisexploited:callstoextendtypicallypassin1jQuery.
extend=jQuery.
fn.
extend=function(){2varoptions,name,src,copy,copyIsArray,clone,3target=arguments[0]||{},4i=1,5length=arguments.
length,6deep=false;7//Handleadeepcopysituation8if(typeoftarget==="boolean"){9deep=target;10target=arguments[1]||{};11//skipthebooleanandthetarget12i=2;13}14//Handlecasewhentargetisastringorsomething15//(possibleindeepcopy)16if(typeoftarget!
=="object"&&!
jQuery.
isFunction(target)){17target={};18}19//extendjQueryitselfifonlyoneargumentispassed20if(length===i){21target=this;22--i;23}24for(;i=null){27//Extendthebaseobject28for(nameinoptions){29src=target[name];30copy=options[name];31//Preventnever-endingloop32if(target===copy){33continue;34}35//Recurseifwe'remergingplainobjectsorarrays36if(deep&©&&(jQuery.
isPlainObject(copy)||37(copyIsArray=jQuery.
isArray(copy)))){38if(copyIsArray){39copyIsArray=false;40clone=src&&jQuery.
isArray(src)src:[];41}else{42clone=src&&jQuery.
isPlainObject(src)src:{};43}44//Nevermoveoriginalobjects,clonethem45target[name]=jQuery.
extend(deep,clone,copy);46//Don'tbringinundefinedvalues47}elseif(copy!
==undefined){48target[name]=copy;49}}}}50//Returnthemodifiedobject51returntarget;52};Figure6.
ThejQueryextendfunction.
literalobjects,whicharethenkeptseparatebytheanalysisduetotheuseofparametersensitivity.
TAJSrepresentsfor-inloopsusingfourspecialkindsofowgraphinstructionsasillustratedinFigure7.
Intu-itively,begin-for-in[r1,r2]createsaniteratorr2foriteratingthroughthepropertiesoftheobjectpointedtobyr1,has-next-property[r2,r3]setsr3totrueorfalsedependingonwhetherr2hasreachedtheendornot,next-property[r2,r4]picksthenextpropertyfromr2andstoresitsnameinr4,andend-for-inrepresentstheendoftheloopbody.
Weuser1,r2,r3,r4∈Rastemporaryregisters,asdiscussedinSection3.
TheiterationorderisimplementationdependentaccordingtotheECMAScriptspecication,sotoremainconservativeTAJSmustmodelallpossibleorders.
Theor-dinarybehaviorofTAJSistoletr2representtheleastupperboundofthepropertynamesofr1(includingnulltorep-resentend-of-list),setr3toany-boolean,andsetr4equaltor2,correspondingtonondeterministicallypickingapropertyFigure7.
Representationoffor-inloopsinTAJSowgraphs.
nameineachiteration.
Althoughsound,thisisevidentlytooimpreciseforjQuery.
Thismotivatestheadditionofavariantofthecontextspe-cializationmechanismthatweintroducedaboveforordinaryforloops,nowconsideringselectedregistersinsteadofpro-gramvariablesusinganadditionalcomponentinC:CRValue)Wenowmodifythetransferfunctionsofthefourspecialin-structionsasfollows.
First,thetransferfunctionofbegin-for-inwillattempttosplitthecurrentcontextintoaspecial-izedcontextforeachpropertynameinther1object,suchthatr2inthecorrespondingabstractstatethatispropagatedtohas-next-propertyisaxedstringrepresentingexactlyoneofthepropertynames.
Again,anon-the-yheuristicde-cideswhethertoperformthisspecializationornot:Thetransferfunctionofbegin-for-inwillsplitthecurrentcontextifthesetofpropertynamesofr1canbedeterminedpreciselyinthecurrentabstractstate.
(Otherwise,itwillusetheordinarybehavior,asexplainedabove,asafallback.
)Forinstance,ifthecurrentabstractstatehasr1={7}forsomeabstractaddress7∈Landtheabstractobjectat7hasthepropertynames{p1,p2}inthatabstractstatethenthecurrentcontextd)∈Cissplitintotwospecializedversions,d[r2→p1])andd[r2→p2]),thatarepropagatedalongwiththecorrespondinglyspecializedabstractstatestothehas-next-propertyinstruction.
Theanalysisisthenreadytoanalyzetheloopbodytwice,onceforeachpropertyname.
Whenthetransferfunctionforhas-next-propertyre-ceivessuchaspecializedabstractstatewherethevalueofr2isaxedstringpandnottheend-of-listmarkernull,itwillimmediatelypasstheabstractstatetothenext-propertyinstruction,whichthenassignsptor4.
Theonlynontrivialcaseisthetransferfunctionforend-for-in,whichisrespon-sibleformergingthechangesmadetotheabstractstatesbytheloopbody.
Simplytakingtheleastupperboundoftheabstractstatesisasound,butoverlyconservativesolu-tion,sinceitwilleffectivelyincludetheinfeasibleexecutionthatskipstheloopbodyentirely.
Instead,weexploitthefactthatTAJSalreadykeepstrackofwhichpartsoftheabstractstateshavebeenmodiedsincetheentryofthecurrentfunc-tion(cf.
theModsub-latticeinFigure4;seealso[15,16]).
Bytreatingeveryhas-next-propertyinstructionasapseudo-functionentry,thisdirectlygivesustheheaplocationsthathavebeenmodiedbytheloopbody.
Themergedabstractstatecreatedbyend-for-inisthendenedastheleastup-perboundofthespecializedabstractstates,exceptthatweletmodiedpartsinonestateoverwritenon-modiedpartsfromanotherstate.
Tosoundlymodelthenondeterminis-ticiterationorder,wemakesuretheeffectsofoneiterationarevisiblebytheothersbypropagatingthemergedabstractstatenotonlytothesuccessornodeoftheloopbutalsobacktothespecializedcontextsatthehas-next-propertynode.
Asaresult,theanalysissoundlycapturesallpossibledataow,withoutmixingtogetherthepropertynames.
Forexample,theextendfunctionfromFigure6isusedforbootstrappingthejQuerylibrarywithseveralcallsoftheformjQuery.
extend({p1:v1,.
.
.
,pn:vn})thatcopythegivenobjectpropertiestothejQueryobjectitself.
Ouranalysistechniquehandlessuchpatternswithhighprecision.
6.
3ConnectionstoOtherAnalysisTechniquesTheformofcontextspecializationatfor-inloopspre-sentedinSection6.
2isreminiscentofthecorrelationtrack-ingtechniquebySridharanetal.
[33]inWALA'sowinsen-sitivepointeranalysis.
Theprimarymotivatingexamplecon-sideredbySridharanetal.
isasimpleversionoftheextendfunctionfromjQuery.
Thekeyideaincorrelationtrackingistoidentifycorrelateddynamicpropertyaccesses,suchascopy=options[name]andtarget[name]=copyinFigure6(lines30and48),extracttheblockofcodecon-tainingtheaccessesintoanewfunction,andthenanalyzethatfunctioncontextsensitively.
Themaindifferencesbe-tweencorrelationtrackingandourfor-inspecializationtechniquearethatourapproachworksforowsensitiveanalysisandwithoutexplicitlytrackingcorrelatedread/writepairsorextractingfunctions.
Moreover,ourapproachdoesnotrequiremanualmodicationsofjQuery'sextendfunc-tion,unlikeWALA.
Wehaveseenintheprecedingsectionshowtheincreasedcontextsensitivityandloopspecializationcanboostconstantpropagation.
ThisinturngivesmorepowertothebasicformofpathsensitivitythatTAJSusesatbranchesasdescribedinSection3.
Consider,forexample,thebranchesinlines8,20,and20inFigure6foracalljQuery.
extend({p1:v1,.
.
.
,pn:vn})withparametersensitivityenabled.
Withthatcontext,theanalysiswillinferthatthethreebranchconditionswilldenitelyevaluatetofalse,false,andtrue,respectively.
Inotherwords,theanalysisautomati-callyprunesbranchesthatareinfeasibleinthespeciccon-texts,therebyeliminatingaconsiderablesourceofspuri-ousdataow.
Inthisway,ourcombinationofstaticanaly-sistechniquescanalsobeviewedasanalternativetothedynamicdeterminacyanalysisdiscussedinSection2:weeffectivelyinferdeterminacyinformationduringthestaticanalysisratherthanrequiringaseparatedynamicanalysis.
ThenotionoftyperenementbyKashyapetal.
[20]isbasedonthesameideathatTAJSusesatbranchconditionstorestrictdataow,asmentionedinSection3,althoughKashyapetal.
suggestmorekindsofbranchconditionsthanTAJScurrentlysupports.
Interestingly,weobserveonlynegligibleimprovementsoftheanalysisresultsforjQuerybyusingthistechnique,sinceitisoftendominatedbytheuseofcontextsensitiveconstantpropagationandpruningofinfeasiblebranches.
7.
ContextSensitiveHeapAbstractionOurinvestigationofanalysisimprecision,asdescribedinSection4,suggeststhatcontextsensitiveheapabstrac-tion[21]mayalsobenecessary.
Figure1againmotivatestheneed:ifanalyzingaprogramthatuses,forexample,jQuery.
fn.
ajaxStartorjQuery.
fn.
ajaxSend,itisimportantthatthesefunctionsarekeptseparateintheab-straction.
Parametersensitivityisnotsufcient,becausethefunctionsareclosureswithfreevariablesthatareboundinenclosingactivationobjects.
Weincorporateavariantofcontextsensitiveheapab-stractionbyextendingthedenitionofabstractaddressesfromL=Nto:L=N*(AValue)*(BValue)*(RValue)(AsmentionedinSection3,tosimplifythepresentationwehereignoretheothercomponentsofLthatareusedforrecencyabstractionandobjectkinds.
)Thismeansthatobjectsarenownotonlydistinguishedbytheirallocationsite,butalsobyavaluationofselectedprogramvariablesandregisters.
Similartoourotheranalysisextensions,thereisawiderangeofpossibilitiesforselectingwhenandhowtoapplythistechnique.
Motivatedbyourstudyofanalysisimprecision,wesuggestusingtheextracomponentsofLinfoursituationsindifferenttransferfunctions:1.
Whenadeclare-functioninstructionwithsourcelocationninsomecontext(t,a,b,d)∈Ccreatesanewfunctionobject,itsabstractaddressisselectedas(n,a,b,d)∈L;thatis,thecontextsensitivityvaluationsa,b,anddaretakendirectlyfromthecurrentcontext.
Thiscauses,e.
g.
,jQuery.
fn.
ajaxStartorjQuery.
fn.
ajaxStoptohavedistinctabstractvaluesafterthecodeinFigure1hasbeenexecuted.
2.
Whenacallorconstructinstructioncreatesanewac-tivationobjectandanewargumentsobject,theabstractaddressesoftheseobjectsobtaintheircontextsensitivityvaluationdirectlyfromthenewlycreatedcalleecontext.
ThisallowstheanalysistodistinguishthescopechainsofthefunctionobjectsforjQuery.
fn.
ajaxStartandjQuery.
fn.
ajaxStop.
Thereby,whenthefunctionsjQuery.
fn.
ajaxStartorjQuery.
fn.
ajaxStoparelaterinvoked,thevalueofoinline4inFigure1willbeboundpreciselyto"ajaxStart"or"ajaxStop",re-spectively,withoutmixingtogetherthedifferentvalues.
3.
Wrapperobjectscreatedintypecoercionsaretreatedcontextsensitivelyinthesamewayasfunctionobjects,asexplainedabove,exceptthatweonlyusetheparametersensitivitycomponent.
Asamotivatingexample,jQuerypassesprimitivestringvaluesviathecallfunctionineach(line27inFigure5)intothisinthecallbackwherebytheyarecoercedintostringwrapperobjects.
4.
Foreveryobjectliteral{p:v,.
.
.
}thatisinafor-inlooporsyntacticallycontainsafunctionparameterthatispresentintheparametersensitivitycomponent(Sec-tion5)ofthecurrentcontext,theabstractaddressoftheobjectwillbecontextsensitiveinthesamewayaswrap-perobjects.
Thisisuseful,forexample,whenjQuerycre-atesitsinnerHeightmethodusingnestedcallstoeachandanobjectliteraloftheform{padding:"inner"+name,.
.
.
}.
Forallotherobjects,theheapabstractionremainscontextinsensitive.
TheexperimentsinSection9showtheeffectofthisanalysisextensionontheprecisionandperformance.
8.
ModelingStandardLibraryFunctionsTheoriginalversionofTAJSmodelstheJavaScriptstandardlibraryfunctionswithafocusontypeinformation,whichisthenaturalchoicewhendevelopingastatictypeanal-ysis[15].
Asanexample,String.
prototype.
splitismodeledascreatinganarrayofunknownstrings.
Amoreprecisemodelis,however,neededwhenanalyzingline1inFigure1andsimilarusesofsplitthroughoutjQuery.
Weobserveasimilarsituationwithregularexpressions,whichareusedfrequentlyinjQuery.
Forinstance,jQuerycontainstheexpressiondataTypeExpression.
toLowerCase().
split(core_rspace)whichTAJSreachesforanabstractstatewherethevalueofdataTypeExpressionisthestring"jsonjsonp"andcore_rspaceistheregularexpression/\s+/.
Thosevaluesoriginatefromotherfunctions,andouruseofcontextsen-sitiveinterproceduralconstantpropagationisnecessarytoinferthatthevaluesareconstantsthatforaspeciccontext.
Oursolutionis,notsurprisingly,tostrengthenthemodelsofthestandardlibraryfunctionstoobtainfullprecisionincaseswheretheirinputconsistsofconstantprimitivevaluesintheabstractstateatthecallsite.
Asaconsequence,callswithdeterminateinputwillreturndeterminateoutput.
WeachievethisbyinvokinganexternalJavaScriptinterpreter.
3Anothercriticalsourceofimprecisionistheuseofobjectpropertynamesthatconsistofrandomsub-strings.
SuchpropertynamesareusedbyjQueryandotherlibrariestoattachlibrarydatatonon-libraryobjects.
ThefollowingtwoexpressionsfromjQueryshowhowsuchpropertynamesaretypicallycomputed(theactualcodevariesslightlybetweenthedifferentversionsofthelibrary):3http://www.
mozilla.
org/rhino/"jQuery"+(jQuery.
fn.
jquery+Math.
random()).
replace(/\D/g,"")("sizcache"+Math.
random()).
replace(Theresultingstringsareusedaskeysindynamicpropertyaccesses.
Iftheanalysismodelsthesestringsconservativelyas"anystring"(i.
e.
,thetopelementoftheStringlattice),thenitwillmixtogetherthelibrarydataandalltheotherpropertiesoftheinvolvedobjects.
OursolutionistoaugmenttheValuelatticewithaboundednumberkof"randomnumbersorstrings"andaug-menttheStatelatticewithacounterfrom0tok.
Thetrans-ferfunctionforMath.
randomthenpicksthenextrandom-valueelementandincrementsthecounteriflessthank.
NotethatthecorrectnessofjQueryreliesontheassumptionthattherandomlygeneratedpropertynamesdonotclashwithanyotherproperties.
Ifthatassumptionholdsforamillionwebsites,wecanuseittoo:inallcomparisons,wecanas-sumethattheserandomvaluesaredifferentfromallotherstringsandnumbers,inparticular,objectpropertynames.
Similarly,weassumethatoperations,suchasthe+opera-tororthebuilt-inreplacefunction,producerandomvalueswhengivenrandomvaluesasinput.
Sincetheserandomstringsarealwayscreatedinthelibraryinitializationphase,itsufcestosettheboundktoalownumber,e.
g.
,10.
9.
ExperimentalEvaluationOurmainresearchquestionis:DotheanalysistechniquessuggestedinSections5–8improvetheanalysisefcacyTheextensionsincreasethetheoreticalworst-casecomplex-ityoftheanalysis,soitisnotobviouswhethertheyimproveordegradetheresultsoftheanalysis.
Morespecically,foreachoftheextensions,doesthetheoreticallyincreasedpre-cisioncausemoreprogramstobeanalyzable,orconversely,doestheincreasedcomplexitymanifestitselfanddiminishtheincreasedprecisionIncaseswheretheanalysissuc-ceedswithinareasonabletimebound,howpreciseisitAndconversely,incaseswhereitfails,isthecauserelatedtoouranalysisextensions,orcanthosecasessuggestdirectionsforfutureworkinimprovingtheanalysisfurtherToevaluatethesuggestedanalysistechniquesandanswerthesequestionswehaveimplementedtheminTAJSandcol-lectedfourgroupsofbenchmarkprograms:(A)Therstgroupcontains12programsthateachloadadifferentver-sionofjQueryfrom1.
0.
0to1.
11.
0anddoesnothingelse.
4(B)Thesecondgroupconsistsof71programsfromajQuerytutorial5thatloadjQuery1.
10.
06andperformafewsimpleoperationsusingthelibrary,therebyexercisingthedifferentcategoriesoffunctionalityinjQuery.
(C)Tobeabletoex-plorethedifferentpartsofjQueryinisolationweusethe4jQueryversion2.
xisdifferentfrom1.
xinthatcompatibilitysupportforolderbrowsershasbeenremoved,however,itusesES5gettersandsetters,whicharenotyetfullysupportedbyTAJS.
5http://www.
jquery-tutorial.
net/6jQuery1.
10.
0wasthenewestversionwhenthisworkwasinitiated.
jQueryLOCload-LOCowgraphversionnodes1.
0.
098126169251.
1.
0112529078781.
2.
01484289111901.
3.
02124632162821.
4.
02828725216301.
5.
03583910268821.
6.
03896969290781.
7.
040821108304431.
8.
040741158300931.
9.
041211162308611.
10.
041411192312341.
11.
04311121832927Table1.
ThemainversionsofjQuery,showingthenumberofsourcelinesthatcontainexecutablecode,thenumberoflinescontainingcodethatisexecutedbyloadingthelibraryinChrome,andthenumberofprimitiveinstructionsintheTAJSowgraph.
71programsfromthejQuerytutorialagain,butnowusingslicedversionsofjQuery1.
10.
0.
Thatis,eachprogramingroupCusesitsownslicedversionofjQuerywhereallpartsthatareunreachableaccordingtoadynamicexecutionintheChromebrowserhavebeenremoved.
(D)Finally,tomea-suretheimpactoftheanalysismodicationsonnon-jQuerycode,weinclude69programsfromtheGoogleOctanesuite,theSunSpidersuite,the10KEventApartChallenge,andChromeExperimentsthathavebeenusedinpreviousworkonTAJS.
ThejQuerybenchmarksingroupsA,B,andCareevi-dentlyfarfromfullscalewebapplications,butasdiscussedinSection2justloadingjQuerycausesmajorcomplicationsforexistinganalysistools.
Somecharacteristicsofthedif-ferentversionsofjQueryareshowninTable1.
Inparticular,thenumbersinthetableshowthatsubstantialpartsofthelibraryareinvolvedintheloadingprocess.
Ourimplementationandallbenchmarksareavailableonline.
7Allexperimentsareperformedona2.
9GHzPCrunningaJVMwith2GBRAM.
WerstrunTAJSonthebenchmarkprogramsfromgroupsA,B,andCin7differentanalysiscongurations.
Therstisthemodiedanalysiswithalltricksenabled:branchpruning(Section3),parametersensitivity(Section5),loopspecializationforordinaryloops(Section6.
1),loopspecializationforfor-inloops(Section6.
2),contextsensitiveheapabstraction(Section7),andimprovedmodelingofthestandardlibrary(Section8).
7http://brics.
dk/TAJS/jquery.
htmlProgramsSuccessA1211B7127C7148total15486Table2.
AnalysissuccessforthethreegroupsofjQuerybenchmarks,withallanalysisfeaturesenabled.
Eachoftheremainingsixcongurationsdisablesasingleoftheseanalysisfeatures.
Weclassifyananalysisexecutionassuccessfulifitreachesaxpointwithinoneminute.
Thecongurationwithallfeaturesenabledresultsinsuc-cessfulanalysisin86cases.
ThenumbersforeachofthethreegroupsofbenchmarksareshowninTable2.
ThisisasubstantialimprovementcomparedtoWALA,whichisun-abletoanalyzebeyondtherst3versionsofthe12programsingroupA,asmentionedinSection2.
Moreover,foralltheremainingcongurationswendthatalmostnoneofthe154benchmarkprogramscanbeanalyzedsuccessfully.
Inotherwords,alltheanalysisfeaturesmustbeenabledtoobtainsuccessfulanalysis.
Thisobservationconrmsthattheindi-vidualanalysistechniquessupporteachother,asdiscussedinSection6.
3.
Inthecaseswheretheanalysissucceeds,theanalysistimeisbetween1and24seconds,withanaverageof6.
5seconds.
Increasingthetime-outbyafactor10allowsonlythreeadditionalcasestosucceed,whichconrmsthattheanalysisprecisionismoreimportantthanthetimebound.
TomeasuretheanalysisprecisionweinvestigatehowwellTAJSperformstypeanalysis,inferscallgraphs,anddetectsdeadcodeforthe86successfulexecutionsinthecongurationwhereallfeaturesareenabled:1.
Foreveryreachableread-variableandread-propertyin-structionwecountthenumberofpossibletypesthattheresultingvaluemayhaveineachabstractstate(usingthesamecategoriesoftypesasinSection4).
Accordingtotheanalysis,99%ofthevalueshaveauniquetype.
Astheanalysisisconservativethisisalowerbound.
Also,theanalysisndsthattheaveragenumberoftypesforeachoftheinstructionsis1.
006,wheretherealnumbermustbeatleast1.
2.
Weinspecttheabstractvaluesofallpropertiesoftheob-jectsjQueryandjQuery.
fnattheexitoftheprogram.
Thosepropertiesdenethepublicinterfaceofthelibrary,soitisimportantthattheanalysisiscapableofkeepingtheindividualfunctionsapart,whichischallengingsincetheyarecreateddynamicallywhenthelibraryisloaded.
Wendthat99%ofthevaluesthatcontainfunctionsareresolveduniquelybytheanalysis.
3.
Wemeasureforeachcallandconstructinstructionineachreachablecallcontextthenumberofpossiblecallees.
(Duetotheuseofhigher-orderfunctions,wechoosetomeasurethispercontextinsteadofconsideringallpossiblecalleesforagivencall.
)Asaresult,99%haveauniquecalleeaccordingtotheanalysis.
4.
ForeachbenchmarkprogramingroupAandB,wecountthelinesofdeadcodereportedbyTAJSrelativetotheactualdeadcodeasobservedbyexhaustivelyexecutingtheprogramsusingtheChromebrowser.
Onaverage,TAJSnds98%oftheactualdeadcode.
Theseresultsshowthattheanalysishashighprecisioninthecaseswhereitreachesaxpointbeforethetime-out.
Aconcernaboutthebenchmarkprogramsthatarenotan-alyzedsuccessfullyisthatthecausecouldinprinciplebeexplosionsinthenumberofcontextsorabstractaddressesresultingfromtheincreasedworst-casecomplexitywiththeanalysisextensions.
Totestthis,wealsomeasuretheanal-ysisprecisionusingthesamemetricsasabove,onabstractstatesobtainedafterthe1minutetime-out.
Theresultingab-stractstatesarethenunder-approximationsofthexpoints,buttheycanstillbeusefulformeasuringprecision(asdis-cussedinSection4).
Asaresultweseeineachofthefailingcasesthatthecauseisnotanoverwhelmingnumberofcon-textsorabstractaddresses,butimprecisionintheindividualabstractstates.
Thefollowingnumbersareforthebench-marksingroupC,whichonlycontainreachablecodeandaretherebyeasiertocompare:Theaveragenumberofcontextsandabstractaddressesrelativetothenumberoffunctionsis9.
84and25.
8,re-spectively,forthe48successfulcases.
Thecorrespondingnumbersforthe23unsuccessfulcasesatthetime-outarenotmuchhigher:14.
7and31.
5.
Therelativenumberofread-propertyinstructionsthatyieldabstractvalueswithmultiplepossibletypes(mea-suredasinSection4)is13timeshigherfortheunsuc-cessfulcasesthanforthesuccessfulcases.
AlthoughtheproposedanalysistechniquesareobviouslynotsufcienttohandleallaspectsofjQuery,thisindicatesthatthetechniquesarenecessaryconstituentsinjQuerystaticanalysistools.
Toinvestigatethisfurther,wealsoruntheanalysisonthe69benchmarksingroupDthatdonotusejQuery.
EachofthosebenchmarksisanalyzablewiththeoriginalTAJS.
En-ablingallthenewfeaturesexceptloopspecializationforor-dinaryloops(Section6.
1)improvesnotonlyprecisionbut,surprisingly,alsotheanalysistime.
Inotherwords,weob-servethattheincreasedanalysiscomplexitydoesnotde-gradetheperformanceonprogramsthatdonotneedthenewfeatures.
Theloopspecializationtechniquesometimesunrollsloopsunnecessarily,whichcausesamodestslow-downforsomebenchmarks,suggestingthatadjustmentsoftheheuristicsinSection6.
1maybebenecial.
ApossiblethreattovalidityofourresultsisthatthebenchmarksingroupsA,B,andCarenotindependentofeachother:thedifferentversionsofjQuerynaturallysharesomecode,andgroupCisdirectlyconstructedfromgroupBbyremovingunreachablecodetobeabletoexploretherelevantpartsofthelibrary.
Nevertheless,theseexperimentsdemonstratetheeffectoftheanalysistechniquesandcanbehelpfulforidentifyingopportunitiesforfuturework.
Anotherpotentialconcernisthatwehavenoproofofsoundness,althoughthisisnodifferentfromallexistingworkonstaticanalysisforJavaScriptwebapplications.
(TAJShasknownsoundnessbugs,butthoseweareawareofdonotaffectourconclusions.
)InadditiontotheexistingtestsuiteinTAJSwehaveuseditsabilitytodetectdeadcodeasasimplesoundnesscheck:Iftheanalysisreachesaxpointwheresomecodeisreportedasdead,theanalysisisunsoundifthatcodeisreachedinaconcreteexecutioninabrowser.
ThistechniquehascaughtafewsubtlebugsinthemodelingoftheDOMcomparedwithhowmodernbrowserswork.
Wehaveperformedapreliminaryinvestigationoftheun-successfulcases(i.
e.
thosewheretheanalysisdidnottermi-natewithinoneminute),usingthemethodologyfromSec-tion4.
Typicallyintheunsuccessfulcases,unknowndy-namicpropertyreads(x[y]withanunknowny)leadtomuchspuriousdataowandconsequentlymanyspuriouscalledges,asexempliedinSections1and6.
Wehaveiden-tiedsomeofthemajorcausesoftheseunknowndynamicpropertyreads,whichsuggeststhefollowingthreeareaswhereadditionalanalysisprecisionmaybeneededforsuc-cessfulanalysisofmorebenchmarks.
(1)TheloopunrollingheuristicinSection6.
1shouldunrollmoreloopsthatulti-matelyinuencedynamicpropertyreads.
Anexampleofthisisalargeloopthatiteratesoverdeterminatestrings,parsesthemasCSSselectorstrings,andstorestheparseresultsasstringsthatarelaterusedaskeysindynamicpropertyaccesses.
(2)Thecontrolsensitivityforoverloadedfunc-tionsshouldbeincreased.
OtherwiseallthepropertiesoftheglobalobjectwillbereadinadynamicpropertyreadforsomeusesofjQuery.
Increasedprecisionfortypepredicatefunctions,suchasisFunction,islikelytohelpwiththis.
(3)DOMelementsandeventsshouldbetreatedwithmoreprecision,assomeDOMobjectpropertyvaluesareusedaskeysindynamicpropertyreadsandfordecidingwhichover-loadedfunctionvariantstouse.
AnimprovedanalysiscouldthenavoidqueryingDOMelementsusingunknowndynamicpropertyreadsinplaceswheretheanalysisshouldquerythenumericpropertiesofaninternalcacheobjectinstead.
OurresultsarebasedonsmalljQueryapplicationsonly,sofurtherstudiesarerequiredtodeterminehowindetermi-nacyintheapplicationcodeaffectsanalysisofthelibrary.
AlthoughsomeJavaScriptprogramswillsurelyremainbe-yondreachofsoundstaticanalysis,weconjecturethatmanyreal-worldjQueryapplicationscanbeanalyzedeffectivelybyreningthetechniquespresentedinthispaper.
10.
ConclusionPreviousworkonstaticanalysisforJavaScriptwebapplica-tionshasshownthatjQueryandrelatedlibrariesareremark-ablydifculttoanalyzeefciently,yetthereisasubstantialpotentialincreatingeffectiveanalysistoolsforsuchcode.
Thiscould,forexample,leadtobetterIDEsupportortoolsthatcanperformoptimizationsorhelpprogrammersdetecttype-relatederrorsduringdevelopment.
Wehaveshownhowdeterminacyinformationcanbein-ferredandexploitedbyastaticanalysistoenableanalysisofasignicantlylargerpartofthejQuerycodebasethanpre-vioustoolshaveaccomplished.
Mostimportantly,wehavedemonstratedthedecisiveeffectofcombiningselectivecon-textsensitivitywithconstantpropagationandbranchprun-ing.
Eachofthetechniquesweapplyincreasesanalysispre-cision,yettheconsequentincreasedtheoreticalworst-casecomplexitydoesnotmanifestinpracticeinourexperiments.
Althoughmuchworkremainstobedone,theseresultssuggestthathigh-precisiondataowanalysisisapromis-ingapproachtostaticanalysisofreal-worldJavaScriptcode.
Ourinvestigationoftheremainingchallengespointstowardmoreprecisetreatmentofloops,overloadedfunctions,andDOMobjectsaspotentialtopicsoffuturework.
Manyvari-ationsoftheheuristicsproposedinSections5–7canbecon-ceived,whichmaybeworthwhiletoexplorefurther.
AcknowledgmentsThisworkwassupportedbyGoogle,IBM,andtheDanishResearchCouncilforTechnologyandProduction.
References[1]F.
AllenandJ.
Cocke.
Acatalogueofoptimizingtransforma-tions.
InDesignandOptimizationofCompilers,pages1–30.
Prentice-Hall,1971.
[2]C.
Anderson,P.
Giannini,andS.
Drossopoulou.
TowardstypeinferenceforJavaScript.
InProc.
19thEuropeanConferenceonObject-OrientedProgramming,July2005.
[3]G.
BalakrishnanandT.
W.
Reps.
Recency-abstractionforheap-allocatedstorage.
InProc.
13thInternationalStaticAnalysisSymposium,August2006.
[4]T.
BallandS.
K.
Rajamani.
Bebop:apath-sensitiveinterpro-ceduraldataowengine.
InProc.
ACMSIGPLAN-SIGSOFTWorkshoponProgramAnalysisForSoftwareToolsandEngi-neering,June2001.
[5]R.
Chugh,J.
A.
Meister,R.
Jhala,andS.
Lerner.
Stagedin-formationowforJavaScript.
InProc.
30thACMSIGPLANConferenceonProgrammingLanguageDesignandImple-mentation,June2009.
[6]ECMA.
ECMAScriptLanguageSpecication,3rdedition,2000.
ECMA-262.
[7]A.
FeldthausandA.
Mller.
Semi-automaticrenamerefactor-ingforJavaScript.
InProc.
28thACMSIGPLANConferenceonObject-OrientedProgramming,Systems,Languages,andApplications,October2013.
[8]A.
Feldthaus,T.
Millstein,A.
Mller,M.
Schfer,andF.
Tip.
Tool-supportedrefactoringforJavaScript.
InProc.
26thACMSIGPLANConferenceonObject-OrientedProgramming,Sys-tems,Languages,andApplications,October2011.
[9]A.
Feldthaus,M.
Schfer,M.
Sridharan,J.
Dolby,andF.
Tip.
EfcientconstructionofapproximatecallgraphsforJavaScriptIDEservices.
InProc.
35thInternationalConfer-enceonSoftwareEngineering,May2013.
[10]S.
GuarnieriandV.
B.
Livshits.
Gatekeeper:MostlystaticenforcementofsecurityandreliabilitypoliciesforJavaScriptcode.
InProc.
18thUSENIXSecuritySymposium,August2009.
[11]S.
Guarnieri,M.
Pistoia,O.
Tripp,J.
Dolby,S.
Teilhet,andR.
Berg.
SavingtheworldwidewebfromvulnerableJavaScript.
InProc.
20thInternationalSymposiumonSoft-wareTestingandAnalysis.
ACM,July2011.
[12]A.
Guha,S.
Krishnamurthi,andT.
Jim.
UsingstaticanalysisforAjaxintrusiondetection.
InProc.
18thInternationalConferenceonWorldWideWeb.
ACM,May2009.
[13]B.
HackettandS.
Guo.
FastandprecisehybridtypeinferenceforJavaScript.
InProc.
ACMSIGPLANConferenceonPro-grammingLanguageDesignandImplementation,June2012.
[14]D.
JangandK.
-M.
Choe.
Points-toanalysisforJavaScript.
InProc.
24thAnnualACMSymposiumonAppliedComputing,ProgrammingLanguageTrack,March2009.
[15]S.
H.
Jensen,A.
Mller,andP.
Thiemann.
TypeanalysisforJavaScript.
InProc.
16thInternationalStaticAnalysisSymposium,August2009.
[16]S.
H.
Jensen,A.
Mller,andP.
Thiemann.
Interproceduralanalysiswithlazypropagation.
InProc.
17thInternationalStaticAnalysisSymposium,September2010.
[17]S.
H.
Jensen,M.
Madsen,andA.
Mller.
ModelingtheHTMLDOMandbrowserAPIinstaticanalysisofJavaScriptwebapplications.
InProc.
EuropeanSoftwareEngineeringConference/ACMSIGSOFTSymposiumontheFoundationsofSoftwareEngineering,September2011.
[18]S.
H.
Jensen,P.
A.
Jonsson,andA.
Mller.
Remedyingtheevalthatmendo.
InProc.
21stInternationalSymposiumonSoftwareTestingandAnalysis,July2012.
[19]J.
B.
KamandJ.
D.
Ullman.
Monotonedataowanalysisframeworks.
ActaInformatica,7:305–317,1977.
Springer.
[20]V.
Kashyap,J.
Sarracino,J.
Wagner,B.
Wiedermann,andB.
Hardekopf.
TyperenementforstaticanalysisofJavaScript.
InProc.
9thSymposiumonDynamicLanguages,October2013.
[21]G.
KastrinisandY.
Smaragdakis.
Hybridcontext-sensitivityforpoints-toanalysis.
InACMSIGPLANConferenceonProgrammingLanguageDesignandImplementation,June2013.
[22]B.
S.
Lerner,L.
Elberty,J.
Li,andS.
Krishnamurthi.
Com-biningformandfunction:StatictypesforJQueryprograms.
InProc.
27thEuropeanConferenceonObject-OrientedPro-gramming,July2013.
[23]F.
LogozzoandH.
Venter.
RATA:Rapidatomictypeanaly-sisbyabstractinterpretation-applicationtoJavaScriptopti-mization.
InProc.
19thInternationalConferenceonCompilerConstruction,March2010.
[24]M.
Madsen,B.
Livshits,andM.
Fanning.
Practicalstaticanal-ysisofJavaScriptapplicationsinthepresenceofframeworksandlibraries.
InProc.
EuropeanSoftwareEngineeringCon-ference/ACMSIGSOFTSymposiumontheFoundationsofSoftwareEngineering,August2013.
[25]M.
MightandO.
Shivers.
ImprovingowanalysesviaΓCFA:abstractgarbagecollectionandcounting.
InProc.
11thACMSIGPLANInternationalConferenceonFunctionalProgram-ming,September2006.
[26]A.
Milanova,A.
Rountev,andB.
G.
Ryder.
Parameterizedob-jectsensitivityforpoints-toanalysisforJava.
ACMTransac-tionsonSoftwareEngineeringandMethodology,14(1),2005.
[27]J.
PlevyakandA.
A.
Chien.
Preciseconcretetypeinferenceforobject-orientedlanguages.
InProc.
9thAnnualConferenceonObject-OrientedProgrammingSystems,Languages,andApplications,October1994.
[28]T.
W.
Reps,S.
Schwoon,S.
Jha,andD.
Melski.
Weightedpushdownsystemsandtheirapplicationtointerproceduraldataowanalysis.
ScienceofComputerProgramming,58(1-2):206–263,2005.
[29]M.
Schfer,M.
Sridharan,J.
Dolby,andF.
Tip.
Dynamicdeterminacyanalysis.
InProc.
ACMSIGPLANConferenceonProgrammingLanguageDesignandImplementation,June2013.
[30]M.
ShapiroandS.
Horwitz.
Theeffectsoftheprecisionofpointeranalysis.
InProc.
4thInternationalSymposiumonStaticAnalysis,September1997.
[31]M.
SharirandA.
Pnueli.
Twoapproachestointerproceduraldataowanalysis.
InProgramFlowAnalysis:TheoryandApplications,pages189–233.
Prentice-Hall,1981.
[32]O.
Shivers.
Control-FlowAnalysisofHigher-OrderLan-guages.
PhDthesis,CarnegieMellonUniversity,1991.
[33]M.
Sridharan,J.
Dolby,S.
Chandra,M.
Schfer,andF.
Tip.
Correlationtrackingforpoints-toanalysisofJavaScript.
InProc.
26thEuropeanConferenceonObject-OrientedPro-gramming,June2012.
[34]P.
Thiemann.
TowardsatypesystemforanalyzingJavaScriptprograms.
InProc.
ProgrammingLanguagesandSystems,14thEuropeanSymposiumonProgramming,April2005.
[35]W3Techs.
UsageofJavaScriptlibrariesforwebsites,2014.
http://w3techs.
com/technologies/overview/javascript_library/all.
[36]M.
N.
WegmanandF.
K.
Zadeck.
Constantpropagationwithconditionalbranches.
ACMTransactionsonProgrammingLanguagesandSystems,12(2):181–210,1991.
[37]S.
WeiandB.
G.
Ryder.
PracticalblendedtaintanalysisforJavaScript.
InProc.
22ndInternationalSymposiumonSoftwareTestingandAnalysis,July2013.
[38]B.
Yankovetal.
TypeScripttypedenitionforjQuery,2014.
https://github.
com/borisyankov/DefinitelyTyped/blob/master/jquery/jquery.
d.
ts.
[39]Y.
Zheng,T.
Bao,andX.
Zhang.
Staticallylocatingwebapplicationbugscausedbyasynchronouscalls.
InProc.
20thInternationalConferenceonWorldWideWeb,March/April2011.