浅论成本控制与财务管理目标课件

静态代码分析梁广泰2011-05-25静态代码分析梁广泰提纲动机程序静态分析（概念+实例）程序缺陷分析（科研工作）提纲动机动机云平台特点应用程序直接部署在云端服务器上，存在安全隐患直接操作破坏服务器文件系统存在安全漏洞时，可提供黑客入口资源共享，动态分配单个应用的性能低下，会侵占其他应用的资源解决方案之一：在部署应用程序之前，对其进行静态代码分析：是否存在违禁调用？（非法文件访问）是否存在低效代码？（未借助StringBuilder对String进行大量拼接）是否存在安全漏洞？（SQL注入，跨站攻击，拒绝服务）是否存在恶意病毒？……动机云平台特点提纲动机程序静态分析（概念+实例）程序缺陷分析（科研工作）提纲动机静态代码分析定义：程序静态分析是在不执行程序的情况下对其进行分析的技术，简称为静态分析。对比：程序动态分析：需要实际执行程序程序理解：静态分析这一术语一般用来形容自动化工具的分析，而人工分析则往往叫做程序理解用途：程序翻译/编译（编译器），程序优化重构，软件缺陷检测等过程：大多数情况下，静态分析的输入都是源程序代码或者中间码（如Javabytecode），只有极少数情况会使用目标代码；以特定形式输出分析结果静态代码分析定义：静态代码分析BasicBlocksControlFlowGraphDataflowAnalysisLiveVariableAnalysisReachingDefinitionAnalysisLatticeTheory静态代码分析BasicBlocksBasicBlocksAbasicblockisamaximalsequenceofconsecutivethree-addressinstructionswiththefollowingproperties:Theflowofcontrolcanonlyenterthebasicblockthruthe1stinstr.Controlwillleavetheblockwithouthaltingorbranching,exceptpossiblyatthelastinstr.Basicblocksbecomethenodesofaflowgraph,withedgesindicatingtheorder.BasicBlocksAbasicblockisaEABCDFBasicBlockExampleLeadersi=1j=1t1=10*it2=t1+jt3=8*t2t4=t3-88a[t4]=0.0j=j+1ifj<=10goto(3)i=i+1ifi<=10goto(2)i=1t5=i-1t6=88*t5a[t6]=1.0i=i+1ifi<=10goto(13)BasicBlocksEABCDFBasicBlockExampleLeadeControl-FlowGraphsControl-flowgraph:Node:aninstructionorsequenceofinstructions(abasicblock)Twoinstructionsi,jinsamebasicblock

iffexecutionofiguaranteesexecutionofjDirectededge:potential

flowofcontrolDistinguishedstartnodeEntry&ExitFirst&lastinstructioninprogramControl-FlowGraphsControl-floControl-FlowEdgesBasicblocks=nodesEdges:AdddirectededgebetweenB1andB2if:BranchfromlaststatementofB1tofirststatementofB2(B2isaleader),orB2immediatelyfollowsB1inprogramorderandB1doesnotendwithunconditionalbranch(goto)DefinitionofpredecessorandsuccessorB1isapredecessorofB2B2isasuccessorofB1Control-FlowEdgesBasicblocksCFGExampleCFGExample静态代码分析BasicBlocksControlFlowGraphDataflowAnalysisLiveVariableAnalysisReachingDefinitionAnalysisLatticeTheory静态代码分析BasicBlocksDataflowAnalysisCompile-TimeReasoningAboutRun-TimeValuesofVariablesorExpressionsAtDifferentProgramPointsWhichassignmentstatementsproducedvalueofvariableatthispoint?Whichvariablescontainvaluesthatarenolongerusedafterthisprogrampoint?Whatistherangeofpossiblevaluesofvariableatthisprogrampoint?……DataflowAnalysisCompile-TimeProgramPointsOneprogrampointbeforeeachnodeOneprogrampointaftereachnodeJoinpoint–pointwithmultiplepredecessorsSplitpoint–pointwithmultiplesuccessorsProgramPointsOneprogrampoinLiveVariableAnalysisAvariablevisliveatpointpifvisusedalongsomepathstartingatp,andnodefinitionofvalongthepathbeforetheuse.Whenisavariablevdeadatpointp?Nouseofvonanypathfromptoexitnode,orIfallpathsfrompredefinevbeforeusingv.LiveVariableAnalysisAvariabWhatUseisLivenessInformation?Registerallocation.Ifavariableisdead,canreassignitsregisterDeadcodeelimination.Eliminateassignmentstovariablesnotreadlater.Butmustnoteliminatelastassignmenttovariable(suchasinstancevariable)visibleoutsideCFG.Caneliminateotherdeadassignments.HandlebymakingallexternallyvisiblevariablesliveonexitfromCFGWhatUseisLivenessInformatiConceptualIdeaofAnalysisstartfromexitandgobackwardsinCFGComputelivenessinformationfromendtobeginningofbasicblocksConceptualIdeaofAnalysisstaLivenessExamplea=x+y;t=a;c=a+x;x==0b=t+z;

c=y+1;11001001110000Assumea,b,cvisibleoutsidemethodSoareliveonexitAssumex,y,z,tnotvisibleRepresentLivenessUsingBitVectororderisabcxyzt1100111100011111001000101110abcxyztabcxyztabcxyztLivenessExamplea=x+y;1100FormalizingAnalysisEachbasicblockhasIN-setofvariablesliveatstartofblockOUT-setofvariablesliveatendofblockUSE-setofvariableswithupwardsexposedusesinblock(usepriortodefinition)DEF-setofvariablesdefinedinblockpriortouseUSE[x=z;x=x+1;]={z}(xnotinUSE)DEF[x=z;x=x+1;y=1;]={x,y}CompilerscanseachbasicblocktoderiveUSEandDEFsetsFormalizingAnalysisEachbasicAlgorithmforallnodesninN-{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};AlgorithmforallnodesninN静态代码分析–概念BasicBlocksControlFlowGraphDataflowAnalysisLiveVariableAnalysisReachingDefinitionAnalysisLatticeTheory静态代码分析–概念BasicBlocksReachingDefinitionsConceptofdefinitionandusea=x+yisadefinitionofaisauseofxandyAdefinitionreachesauseifvaluewrittenbydefinition

maybereadbyuseReachingDefinitionsConceptofReachingDefinitionss=0;a=4;i=0;k==0b=1;b=2;i<ns=s+a*b;i=i+1;returnsReachingDefinitionss=0;bReachingDefinitionsandConstantPropagationIsauseofavariableaconstant?CheckallreachingdefinitionsIfallassignvariabletosameconstantThenuseisinfactaconstantCanreplacevariablewithconstantReachingDefinitionsandConstIsaConstantins=s+a*b?s=0;a=4;i=0;k==0b=1;b=2;i<ns=s+a*b;i=i+1;returnsYes!Onallreachingdefinitionsa=4

IsaConstantins=s+a*b?sConstantPropagationTransforms=0;a=4;i=0;k==0b=1;b=2;i<ns=s+4*b;i=i+1;returnsYes!Onallreachingdefinitionsa=4

ConstantPropagationTransformComputingReachingDefinitionsComputewithsetsofdefinitionsrepresentsetsusingbitvectorseachdefinitionhasapositioninbitvectorAteachbasicblock,computedefinitionsthatreachstartofblockdefinitionsthatreachendofblockDocomputationbysimulatingexecutionofprogramuntilreachfixedpointComputingReachingDefinitions

1:s=0;2:a=4;3:i=0;k==04:b=1;5:b=2;0000000111000011100001111100111110011111001111111111111111111111234567123456712345671234567123456712345671110000111100011101001111100010111111111001111111i<n1111111returns6:s=s+a*b;7:i=i+1;

1:s=0;4:b=1;5:b=2;0FormalizingReachingDefinitionsEachbasicblockhasIN-setofdefinitionsthatreachbeginningofblockOUT-setofdefinitionsthatreachendofblockGEN-setofdefinitionsgeneratedinblockKILL-setofdefinitionskilledinblockGEN[s=s+a*b;i=i+1;]=0000011KILL[s=s+a*b;i=i+1;]=1010000CompilerscanseachbasicblocktoderiveGENandKILLsetsFormalizingReachingDefinitioExampleExampleForwardsvs.backwardsAforwardsanalysisisonethatforeachprogrampointcomputesinformationaboutthepastbehavior.Examplesofthisareavailableexpressionsandreachingdefinitions.Calculation:predecessorsofCFGnodes.Abackwardsanalysisisonethatforeachprogrampointcomputesinformationaboutthefuturebehavior.Examplesofthisarelivenessandverybusyexpressions.Calculation:successorsofCFGnodes.Forwardsvs.backwardsAforwarMayvs.MustAmayanalysisisonethatdescribesinformationthatmaypossiblybetrueand,thus,computesanupperapproximation.Examplesofthisarelivenessandreachingdefinitions.Calculation:unionoperator.Amustanalysisisonethatdescribesinformationthatmustdefinitelybetrueand,thus,computesalowerapproximation.Examplesofthisareavailableexpressionsandverybusyexpressions.Calculation:intersectionoperator.Mayvs.MustAmayanalysisis静态代码分析–概念BasicBlocksControlFlowGraphDataflowAnalysisLiveVariableAnalysisReachingDefinitionAnalysisLatticeTheory静态代码分析–概念BasicBlocksBasicIdeaInformationaboutprogramrepresentedusingvaluesfromalgebraicstructurecalledlatticeAnalysisproduceslatticevalueforeachprogrampointTwoflavorsofanalysisForwarddataflowanalysisBackwarddataflowanalysisBasicIdeaInformationaboutprPartialOrdersSetPPartialordersuchthatx,y,zPxx (reflexive)xyandyximpliesxy (asymmetric)xyandyzimpliesxz (transitive)CanusepartialordertodefineUpperandlowerboundsLeastupperboundGreatestlowerboundPartialOrdersSetPUpperBoundsIfSPthenxPisanupperboundofSifyS.yxxPistheleastupperboundofSifxisanupperboundofS,andxyforallupperboundsyofS-join,leastupperbound(lub),supremum,supSistheleastupperboundofSxyistheleastupperboundof{x,y}UpperBoundsIfSPthenLower

BoundsIfSPthenxPisalowerboundofSifyS.xyxPisthegreatestlowerboundofSifxisalowerboundofS,andyxforalllowerboundsyofS-meet,greatestlowerbound(glb),infimum,infSisthegreatestlowerboundofSxyisthegreatestlowerboundof{x,y}LowerBoundsIfSPthenCoveringxyifxyandxyxiscoveredbyy(ycoversx)ifxy,andxzyimpliesxzConceptually,ycoversxiftherearenoelementsbetweenxandyCoveringxyifxyandxyExampleP={000,001,010,011,100,101,110,111}(standardBooleanlattice,alsocalledhypercube)xyif(xbitwiseandy)=x111011101110010001000100HasseDiagramIfycoversxLinefromytoxyabovexindiagramExampleP={000,001,010,01LatticesIfxyandxyexistforallx,yP, thenPisalattice.IfSandSexistforallSP, thenPisacompletelattice.AllfinitelatticesarecompleteLatticesIfxyandxyexiLatticesIfxyandxyexistforallx,yP, thenPisalattice.IfSandSexistforallSP, thenPisacompletelattice.AllfinitelatticesarecompleteExampleofalatticethatisnotcompleteIntegersIForanyx,yI,xy=max(x,y),xy=min(x,y)ButIandIdonotexistI{,}isacompletelatticeLatticesIfxyandxyexiLatticeExamplesLatticesNon-latticesLatticeExamplesLatticesSemi-LatticeOnlyoneofthetwobinaryoperations(meetorjoin)existMeet-semilatticeIfxyexistforallx,yPJoin-semilatticeIfxyexistforallx,yPSemi-LatticeOnlyoneofthetwMonotonicFunction&FixedpointLetLbealattice.Afunctionf:L→Lismonotonicif∀x,y∈S:x

y⇒f(x)

f(y)LetAbeaset,f:A→Aafunction,a∈A. Iff(a)=a,thenaiscalledafixedpointoffonAMonotonicFunction&FixedpoiExistenceofFixedPointsTheheightofalatticeisdefinedtobethelengthofthelongestpathfrom⊥to⊤InacompletelatticeLwithfiniteheight,everymonotonicfunctionf:L→Lhasaunique

leastfixed-point:

ExistenceofFixedPointsThehKnaster-Tarski

FixedPointTheoremSuppose(L,)isacompletelattice,f:LLisamonotonicfunction.ThenthefixedpointmoffcanbedefinedasKnaster-Tarski

FixedPointThCalculatingFixedPointThetimecomplexityofcomputingafixed-pointdependsonthreefactors:Theheightofthelattice,sincethisprovidesaboundfori;Thecostofcomputingf;Thecostoftestingequality.Thecomputationofafixed-pointcanbeillustratedasawalkupthelatticestartingat⊥:CalculatingFixedPointThetimApplicationtoDataflowAnalysisDataflowinformationwillbelatticevaluesTransferfunctionsoperateonlatticevaluesSolutionalgorithmwillgenerateincreasingsequenceofvaluesateachprogrampointAscendingchainconditionwillensureterminationWillusetocombinevaluesatcontrol-flowjoinpointsApplicationtoDataflowAnalysTransferFunctionsTransferfunctionf:PPforeachnodeincontrolflowgraphfmodelseffectofthenodeontheprograminformationTransferFunctionsTransferfunTransferFunctionsEachdataflowanalysisproblemhasasetFoftransferfunctionsf:PPIdentityfunctioniFFmustbeclosedundercomposition: f,gF.thefunctionh=x.f(g(x))FEachfFmustbemonotone: xyimpliesf(x)f(y)SometimesallfFaredistributive: f(xy)=f(x)f(y)DistributivityimpliesmonotonicityTransferFunctionsEachdataflo课程考核方式作业（提交到课程平台/，并演示）+课程报告作业选题：代码注释提取，文档生成代码信息统计：总行数，代码行数，类数量，方法数，方法长度等Latex格式文档自动转成PDF代码在线diffExecutableJar转换成带有特定icon的exe程序代码各类缺陷检测：内存泄漏，空指针异常Testcase自动生成脚本缺陷分析：Javascript，Python，Ruby，PHP……C#代码缺陷分析在线压缩，解压缩，加密，解密……课程考核方式作业（提交到课程平台http://sase.seQuestions?

Thankyou!Questions?

Thankyou!静态代码分析梁广泰2011-05-25静态代码分析梁广泰提纲动机程序静态分析（概念+实例）程序缺陷分析（科研工作）提纲动机动机云平台特点应用程序直接部署在云端服务器上，存在安全隐患直接操作破坏服务器文件系统存在安全漏洞时，可提供黑客入口资源共享，动态分配单个应用的性能低下，会侵占其他应用的资源解决方案之一：在部署应用程序之前，对其进行静态代码分析：是否存在违禁调用？（非法文件访问）是否存在低效代码？（未借助StringBuilder对String进行大量拼接）是否存在安全漏洞？（SQL注入，跨站攻击，拒绝服务）是否存在恶意病毒？……动机云平台特点提纲动机程序静态分析（概念+实例）程序缺陷分析（科研工作）提纲动机静态代码分析定义：程序静态分析是在不执行程序的情况下对其进行分析的技术，简称为静态分析。对比：程序动态分析：需要实际执行程序程序理解：静态分析这一术语一般用来形容自动化工具的分析，而人工分析则往往叫做程序理解用途：程序翻译/编译（编译器），程序优化重构，软件缺陷检测等过程：大多数情况下，静态分析的输入都是源程序代码或者中间码（如Javabytecode），只有极少数情况会使用目标代码；以特定形式输出分析结果静态代码分析定义：静态代码分析BasicBlocksControlFlowGraphDataflowAnalysisLiveVariableAnalysisReachingDefinitionAnalysisLatticeTheory静态代码分析BasicBlocksBasicBlocksAbasicblockisamaximalsequenceofconsecutivethree-addressinstructionswiththefollowingproperties:Theflowofcontrolcanonlyenterthebasicblockthruthe1stinstr.Controlwillleavetheblockwithouthaltingorbranching,exceptpossiblyatthelastinstr.Basicblocksbecomethenodesofaflowgraph,withedgesindicatingtheorder.BasicBlocksAbasicblockisaEABCDFBasicBlockExampleLeadersi=1j=1t1=10*it2=t1+jt3=8*t2t4=t3-88a[t4]=0.0j=j+1ifj<=10goto(3)i=i+1ifi<=10goto(2)i=1t5=i-1t6=88*t5a[t6]=1.0i=i+1ifi<=10goto(13)BasicBlocksEABCDFBasicBlockExampleLeadeControl-FlowGraphsControl-flowgraph:Node:aninstructionorsequenceofinstructions(abasicblock)Twoinstructionsi,jinsamebasicblock

iffexecutionofiguaranteesexecutionofjDirectededge:potential

flowofcontrolDistinguishedstartnodeEntry&ExitFirst&lastinstructioninprogramControl-FlowGraphsControl-floControl-FlowEdgesBasicblocks=nodesEdges:AdddirectededgebetweenB1andB2if:BranchfromlaststatementofB1tofirststatementofB2(B2isaleader),orB2immediatelyfollowsB1inprogramorderandB1doesnotendwithunconditionalbranch(goto)DefinitionofpredecessorandsuccessorB1isapredecessorofB2B2isasuccessorofB1Control-FlowEdgesBasicblocksCFGExampleCFGExample静态代码分析BasicBlocksControlFlowGraphDataflowAnalysisLiveVariableAnalysisReachingDefinitionAnalysisLatticeTheory静态代码分析BasicBlocksDataflowAnalysisCompile-TimeReasoningAboutRun-TimeValuesofVariablesorExpressionsAtDifferentProgramPointsWhichassignmentstatementsproducedvalueofvariableatthispoint?Whichvariablescontainvaluesthatarenolongerusedafterthisprogrampoint?Whatistherangeofpossiblevaluesofvariableatthisprogrampoint?……DataflowAnalysisCompile-TimeProgramPointsOneprogrampointbeforeeachnodeOneprogrampointaftereachnodeJoinpoint–pointwithmultiplepredecessorsSplitpoint–pointwithmultiplesuccessorsProgramPointsOneprogrampoinLiveVariableAnalysisAvariablevisliveatpointpifvisusedalongsomepathstartingatp,andnodefinitionofvalongthepathbeforetheuse.Whenisavariablevdeadatpointp?Nouseofvonanypathfromptoexitnode,orIfallpathsfrompredefinevbeforeusingv.LiveVariableAnalysisAvariabWhatUseisLivenessInformation?Registerallocation.Ifavariableisdead,canreassignitsregisterDeadcodeelimination.Eliminateassignmentstovariablesnotreadlater.Butmustnoteliminatelastassignmenttovariable(suchasinstancevariable)visibleoutsideCFG.Caneliminateotherdeadassignments.HandlebymakingallexternallyvisiblevariablesliveonexitfromCFGWhatUseisLivenessInformatiConceptualIdeaofAnalysisstartfromexitandgobackwardsinCFGComputelivenessinformationfromendtobeginningofbasicblocksConceptualIdeaofAnalysisstaLivenessExamplea=x+y;t=a;c=a+x;x==0b=t+z;

c=y+1;11001001110000Assumea,b,cvisibleoutsidemethodSoareliveonexitAssumex,y,z,tnotvisibleRepresentLivenessUsingBitVectororderisabcxyzt1100111100011111001000101110abcxyztabcxyztabcxyztLivenessExamplea=x+y;1100FormalizingAnalysisEachbasicblockhasIN-setofvariablesliveatstartofblockOUT-setofvariablesliveatendofblockUSE-setofvariableswithupwardsexposedusesinblock(usepriortodefinition)DEF-setofvariablesdefinedinblockpriortouseUSE[x=z;x=x+1;]={z}(xnotinUSE)DEF[x=z;x=x+1;y=1;]={x,y}CompilerscanseachbasicblocktoderiveUSEandDEFsetsFormalizingAnalysisEachbasicAlgorithmforallnodesninN-{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};AlgorithmforallnodesninN静态代码分析–概念BasicBlocksControlFlowGraphDataflowAnalysisLiveVariableAnalysisReachingDefinitionAnalysisLatticeTheory静态代码分析–概念BasicBlocksReachingDefinitionsConceptofdefinitionandusea=x+yisadefinitionofaisauseofxandyAdefinitionreachesauseifvaluewrittenbydefinition

maybereadbyuseReachingDefinitionsConceptofReachingDefinitionss=0;a=4;i=0;k==0b=1;b=2;i<ns=s+a*b;i=i+1;returnsReachingDefinitionss=0;bReachingDefinitionsandConstantPropagationIsauseofavariableaconstant?CheckallreachingdefinitionsIfallassignvariabletosameconstantThenuseisinfactaconstantCanreplacevariablewithconstantReachingDefinitionsandConstIsaConstantins=s+a*b?s=0;a=4;i=0;k==0b=1;b=2;i<ns=s+a*b;i=i+1;returnsYes!Onallreachingdefinitionsa=4

IsaConstantins=s+a*b?sConstantPropagationTransforms=0;a=4;i=0;k==0b=1;b=2;i<ns=s+4*b;i=i+1;returnsYes!Onallreachingdefinitionsa=4

ConstantPropagationTransformComputingReachingDefinitionsComputewithsetsofdefinitionsrepresentsetsusingbitvectorseachdefinitionhasapositioninbitvectorAteachbasicblock,computedefinitionsthatreachstartofblockdefinitionsthatreachendofblockDocomputationbysimulatingexecutionofprogramuntilreachfixedpointComputingReachingDefinitions

1:s=0;2:a=4;3:i=0;k==04:b=1;5:b=2;0000000111000011100001111100111110011111001111111111111111111111234567123456712345671234567123456712345671110000111100011101001111100010111111111001111111i<n1111111returns6:s=s+a*b;7:i=i+1;

1:s=0;4:b=1;5:b=2;0FormalizingReachingDefinitionsEachbasicblockhasIN-setofdefinitionsthatreachbeginningofblockOUT-setofdefinitionsthatreachendofblockGEN-setofdefinitionsgeneratedinblockKILL-setofdefinitionskilledinblockGEN[s=s+a*b;i=i+1;]=0000011KILL[s=s+a*b;i=i+1;]=1010000CompilerscanseachbasicblocktoderiveGENandKILLsetsFormalizingReachingDefinitioExampleExampleForwardsvs.backwardsAforwardsanalysisisonethatforeachprogrampointcomputesinformationaboutthepastbehavior.Examplesofthisareavailableexpressionsandreachingdefinitions.Calculation:predecessorsofCFGnodes.Abackwardsanalysisisonethatforeachprogrampointcomputesinformationaboutthefuturebehavior.Examplesofthisarelivenessandverybusyexpressions.Calculation:successorsofCFGnodes.Forwardsvs.backwardsAforwarMayvs.MustAmayanalysisisonethatdescribesinformationthatmaypossiblybetrueand,thus,computesanupperapproximation.Examplesofthisarelivenessandreachingdefinitions.Calculation:unionoperator.Amustanalysisisonethatdescribesinformationthatmustdefinitelybetrueand,thus,computesalowerapproximation.Examplesofthisareavailableexpressionsandverybusyexpressions.Calculation:intersectionoperator.Mayvs.MustAmayanalysisis静态代码分析–概念BasicBlocksControlFlowGraphDataflowAnalysisLiveVariableAnalysisReachingDefinitionAnalysisLatticeTheory静态代码分析–概念BasicBlocksBasicIdeaInformationaboutprogramrepresentedusingvaluesfromalgebraicstructurecalledlatticeAnalysisproduceslatticevalueforeachprogrampointTwoflavorsofanalysisForwarddataflowanalysisBackwarddataflowanalysisBasicIdeaInformationaboutprPartialOrdersSetPPartialordersuchthatx,y,zPxx (reflexive)xyandyximpliesxy (asymmetric)xyandyzimpliesxz (transitive)CanusepartialordertodefineUpperandlowerboundsLeastupperboundGreatestlowerboundPartialOrdersSetPUpperBoundsIfSPthenxPisanupperboundofSifyS.yxxPistheleastupperboundofSifxisanupperboundofS,andxyforallupperboundsyofS-join,leastupperbound(lub),supremum,supSistheleastupperboundofSxyistheleastupperboundof{x,y}UpperBoundsIfSPthenLower

BoundsIfSPthenxPisalowerboundofSifyS.xyxPisthegreatestlowerboundofSifxisalowerboundofS,andyxforalllowerboundsyofS-meet,greatestlowerbound(glb),infimum,infSisthegreatestlowerboundofSxyisthegreatestlowerboundof{x,y}LowerBoundsIfSPthenCoveringxyifxyandxyxiscoveredbyy(ycoversx)ifxy,andxzyimpliesxzConceptually,ycoversxiftherearenoelementsbetweenxandyCoveringxyifxyandxyExampleP={000,001,010,011,100,101,110,111}(standardBooleanlattice,alsocalledhypercube)xyif(xbitwiseandy)=x111011101110010001000100HasseDiagramIfycoversxLinefromytoxyabovexindiagramExampleP={000,001,010,01LatticesIfxyandxyexistforallx,yP, thenPisalattice.IfSandSexistforallSP, thenPisacompletelattice.AllfinitelatticesarecompleteLatticesIfxyandxyexiLatticesIfxyandxyexistforallx,yP, thenPisalattice.IfSandSexistforallSP, thenPisacompletelattice.AllfinitelatticesarecompleteExampleofalatticethatisnotcompleteIntegersIForanyx,yI,xy=max(x,y),xy=min(x,y)ButIandIdonotexistI{,}isacompletelatticeLatticesIfxyandxyexiLat