静态代码分析

静态代码分析梁广泰2011-05-25提纲动机程序静态分析（概念+实例）程序缺陷分析（科研工作）动机云平台特点应用程序直接部署在云端服务器上，存在安全隐患•直接操作破坏服务器文件系统•存在安全漏洞时，可提供黑客入口资源共享，动态分配•单个应用的性能低下，会侵占其他应用的资源解决方案之一：在部署应用程序之前，对其进行静态代码分析：•是否存在违禁调用？（非法文件访问）•是否存在低效代码？（未借助StringBuilder对String进行大量拼接）•是否存在安全漏洞？（SQL注入，跨站攻击，拒绝服务）•是否存在恶意病毒？•……提纲动机程序静态分析（概念+实例）程序缺陷分析（科研工作）静态代码分析定义：程序静态分析是在不执行程序的情况下对其进行分析的技术，简称为静态分析。对比：程序动态分析：需要实际执行程序程序理解：静态分析这一术语一般用来形容自动化工具的分析，而人工分析则往往叫做程序理解用途：程序翻译/编译（编译器），程序优化重构，软件缺陷检测等过程：大多数情况下，静态分析的输入都是源程序代码或者中间码（如Javabytecode），只有极少数情况会使用目标代码；以特定形式输出分析结果静态代码分析BasicBlocksControlFlowGraphDataflowAnalysisLiveVariableAnalysisReachingDefinitionAnalysisLatticeTheoryBasicBlocksAbasicblockisamaximalsequenceofconsecutivethree-addressinstructionswiththefollowingproperties:Theflowofcontrolcanonlyenterthebasicblockthruthe1stinstr.Controlwillleavetheblockwithouthaltingorbranching,exceptpossiblyatthelastinstr.Basicblocksbecomethenodesofaflowgraph,withedgesindicatingtheorder.EABCDFBasicBlockExampleLeaders1.i=12.j=13.t1=10*i4.t2=t1+j5.t3=8*t26.t4=t3-887.a[t4]=0.08.j=j+19.ifj=10goto(3)10.i=i+111.ifi=10goto(2)12.i=113.t5=i-114.t6=88*t515.a[t6]=1.016.i=i+117.ifi=10goto(13)BasicBlocksControl-FlowGraphsControl-flowgraph:Node:aninstructionorsequenceofinstructions(abasicblock)•Twoinstructionsi,jinsamebasicblockiffexecutionofiguaranteesexecutionofjDirectededge:potentialflowofcontrolDistinguishedstartnodeEntry&Exit•First&lastinstructioninprogramControl-FlowEdgesBasicblocks=nodesEdges:AdddirectededgebetweenB1andB2if:•BranchfromlaststatementofB1tofirststatementofB2(B2isaleader),or•B2immediatelyfollowsB1inprogramorderandB1doesnotendwithunconditionalbranch(goto)Definitionofpredecessorandsuccessor•B1isapredecessorofB2•B2isasuccessorofB1CFGExample静态代码分析BasicBlocksControlFlowGraphDataflowAnalysisLiveVariableAnalysisReachingDefinitionAnalysisLatticeTheoryDataflowAnalysisCompile-TimeReasoningAboutRun-TimeValuesofVariablesorExpressionsAtDifferentProgramPointsWhichassignmentstatementsproducedvalueofvariableatthispoint?Whichvariablescontainvaluesthatarenolongerusedafterthisprogrampoint?Whatistherangeofpossiblevaluesofvariableatthisprogrampoint?……ProgramPointsOneprogrampointbeforeeachnodeOneprogrampointaftereachnodeJoinpoint–pointwithmultiplepredecessorsSplitpoint–pointwithmultiplesuccessorsLiveVariableAnalysisAvariablevisliveatpointpifvisusedalongsomepathstartingatp,andnodefinitionofvalongthepathbeforetheuse.Whenisavariablevdeadatpointp?Nouseofvonanypathfromptoexitnode,orIfallpathsfrompredefinevbeforeusingv.WhatUseisLivenessInformation?Registerallocation.Ifavariableisdead,canreassignitsregisterDeadcodeelimination.Eliminateassignmentstovariablesnotreadlater.Butmustnoteliminatelastassignmenttovariable(suchasinstancevariable)visibleoutsideCFG.Caneliminateotherdeadassignments.HandlebymakingallexternallyvisiblevariablesliveonexitfromCFGConceptualIdeaofAnalysisstartfromexitandgobackwardsinCFGComputelivenessinformationfromendtobeginningofbasicblocksLivenessExamplea=x+y;t=a;c=a+x;x==0b=t+z;c=y+1;11001001110000Assumea,b,cvisibleoutsidemethodSoareliveonexitAssumex,y,z,tnotvisibleRepresentLivenessUsingBitVectororderisabcxyzt1100111100011111001000101110abcxyztabcxyztabcxyztFormalizingAnalysisEachbasicblockhasIN-setofvariablesliveatstartofblockOUT-setofvariablesliveatendofblockUSE-setofvariableswithupwardsexposedusesinblock(usepriortodefinition)DEF-setofvariablesdefinedinblockpriortouseUSE[x=z;x=x+1;]={z}(xnotinUSE)DEF[x=z;x=x+1;y=1;]={x,y}CompilerscanseachbasicblocktoderiveUSEandDEFsetsAlgorithmforallnodesninN-{Exit}IN[n]=emptyset;OUT[Exit]=emptyset;IN[Exit]=use[Exit];Changed=N-{Exit};while(Changed!=emptyset)chooseanodeninChanged;Changed=Changed-{n};OUT[n]=emptyset;forallnodessinsuccessors(n)OUT[n]=OUT[n]UIN[p];IN[n]=use[n]U(out[n]-def[n]);if(IN[n]changed)forallnodespinpredecessors(n)Changed=ChangedU{p};静态代码分析–概念BasicBlocksControlFlowGraphDataflowAnalysisLiveVariableAnalysisReachingDefinitionAnalysisLatticeTheoryReachingDefinitionsConceptofdefinitionandusea=x+yisadefinitionofaisauseofxandyAdefinitionreachesauseifvaluewrittenbydefinitionmaybereadbyuseReachingDefinitionss=0;a=4;i=0;k==0b=1;b=2;ins=s+a*b;i=i+1;returnsReachingDefinitionsandConstantPropagationIsauseofavariableaconstant?CheckallreachingdefinitionsIfallassignvariabletosameconstantThenuseisinfactaconstantCanreplacevariablewithconstantIsaConstantins=s+a*b?s=0;a=4;i=0;k==0b=1;b=2;ins=s+a*b;i=i+1;returnsYes!Onallreachingdefinitionsa=4ConstantPropagationTransforms=0;a=4;i=0;k==0b=1;b=2;ins=s+4*b;i=i+1;returnsYes!Onallreachingdefinitionsa=4ComputingReachingDefinitionsComputewithsetsofdefinitionsrepresentsetsusingbitvectorseachdefinitionhasapositioninbitvectorAteachbasicblock,computedefinitionsthatreachstartofblockdefinitionsthatreachendofblockDocomputationbysimulatingexecutionofprogramuntilreachfixedpoint1:s=0;2:a=4;3:i=0;k==04:b=1;5:b=2;0000000111000011100001111100111110011111001111111111111111111111234567123456712345671234567123456712345671110000111100