DEPARTMENT：DepartmentofComputerScience&TechnologySPECIALIZATION：ComputerScience&TechnologyUNDERGRADUATE:ZihanLiuMENTOR:LeiNowadays，computertechnologyisbeingappliedinallkindsofindustiesandfieldsmorewidelyanddeeply.Alongwiththistrend，thequalityofsoftwarehasethespecialandimportantfocus，onwhichallthesoftwaredevelpoersandusershaveputeyes.Thedataflowysiswhichisbasedonthestaticysisofsourcecodeisakindofimportanttechniqueusedforsoftwareysis,softwaremaintenanceandsoftwarequalityassurance.Throughdataflowysis,youcanfindandlocatetheanomalies，whichareusuallyassociatedwiththeassignmentanduseofvariantsinThispaperwillintroducesoot，proposedamethodofdataflowysisbasedonsootdataflowframework.Inthisexperiment,theduchainsofprogramisrealized,anddetectexceptionfordef-useofvariable.ThemainworkUnderstandingthestatusofdomesticandforeignprograms,summarizethetoolsandmethodsoftheprogramysis..LearningtounderstandtheSoot.yzingthevariousintermediaterepresentationsofSootanditsbasicobject.Buildingcontrolflowchartbysoot,completeysisofvariabledefinitionoftheusebasedondataflowysisframeworkofsoot.ngCaseysisandresult:Soot；Dataflowysis；Variable'sdef-use目第一章緒 Java程序分析現(xiàn) 控制 數(shù)據(jù) 數(shù)據(jù)流異 工具Soot介 Soot概 Soot中間表示 Soot數(shù)據(jù)結(jié)構(gòu)基 Soot的執(zhí) 第三章基于Soot的程序變量定義使用分 Soot的數(shù)據(jù)流框 分析本 近似的級(jí) 初始狀 FLOW集 控制流 定義使用鏈的................................................................................... 第五章總結(jié)與展 參考文 致 研究背景和意JavaJamesGosling1991SunMicrosystems和健壯性，JavaTIOBEProgrammingCommuity2006，Java終處于開發(fā)語言的前兩位[1]JavaJava服務(wù)器軟件和上有著廣泛的運(yùn)用[2]。然后，由于兩種平臺(tái)的特殊性，它們JavaJavaJava的正確性。根據(jù)在對(duì)Java源程序的分析過程中是否需要編譯運(yùn)行程序的源代代碼是否滿足規(guī)范性、安全性、可靠性、可性等指標(biāo)的分析技術(shù)，隨著編30%~70%的邏輯設(shè)計(jì)錯(cuò)誤和編碼錯(cuò)誤可以通過靜態(tài)測試分析得出。找到程序數(shù)據(jù)流中的異?，F(xiàn)象，包括：無定義變量、連續(xù)使用變量無定義以及變量定義而不，這些都是程序設(shè)計(jì)中常見的錯(cuò)誤，通過數(shù)據(jù)流分析能本文利用soot的數(shù)據(jù)流分析框架，對(duì)案例程序的構(gòu)造進(jìn)行分析，并進(jìn)行數(shù)據(jù)流分析獲得定義使用鏈，找出程序中變量定義的錯(cuò)誤，從而有效的保證Java程序定義使用的正確性。Java程序分析現(xiàn)靜態(tài)測試是指無需運(yùn)行被測代碼，僅通過分析或檢查源程序的語法、結(jié)不匹配，有歧義的嵌套語句，錯(cuò)誤的遞歸，計(jì)算，可能出現(xiàn)的空指針分析的中間表示（InterRepresentation，IR），然后對(duì)中間表示進(jìn)行多FindBugs是由馬里蘭大學(xué)提供的一款開源Java靜態(tài)分析工具。它以Java源代碼編譯之后的class文件為輸出，根據(jù)內(nèi)部給定的代碼規(guī)則來檢測程序中的。FindBugs既可以提供可視化UI界面，同時(shí)也可以作為Eclipse插件FortifySourcecodeysisSuite是一款成軟件源代碼安全掃描、PMD是由DARPA在SourceForge上發(fā)布的開源Java代碼靜態(tài)分析工具。PMDJava的bug，未使用的代碼，重復(fù)的代碼，循環(huán)體創(chuàng)建新對(duì)象等問題的檢驗(yàn)。PMD提供了和多種JavaIDE的集成，例如Eclipse，IDEA，NetBean等。Compaq公司(現(xiàn)在的HP)的SystemReseachCenter研發(fā)的ESC(ExtendedStaticChecking)靜態(tài)分析工具運(yùn)用自動(dòng)定理證明的方法去推斷程序的語義，它可以發(fā)現(xiàn)許多只有在執(zhí)行時(shí)才會(huì)發(fā)生的錯(cuò)誤，例如:空指針解、數(shù)組ESC/Java釋語言(annotationlanguage)往系統(tǒng)中添加設(shè)計(jì)方案(designdecisions，這SableSoot[5][6]。SootJavaclassJimple[7]，Jimple3(CHA，Spark，Paddle，在此基礎(chǔ)上做了許多關(guān)于字節(jié)碼相關(guān)的優(yōu)化。他們的最主要JimpleJimple析方法。然而，Soot項(xiàng)目設(shè)計(jì)的目標(biāo)并不是自動(dòng)檢測程序中的，而只是利JavaclassJava能，所以其支持的靜態(tài)分析方法和精度都十分有限。但是，JimpleSoot本文研究內(nèi)容與章節(jié)安本文引入Soot，著重利用數(shù)據(jù)流對(duì)Java程序進(jìn)行變量定義使用分析，獲得第一章緒論，介紹課題的研究背景、研究意義，介紹Java程序變量使用及據(jù)流異常，Soot數(shù)據(jù)結(jié)構(gòu)、中間表示及數(shù)據(jù)流分析的三種實(shí)現(xiàn)。第三章本章是介紹Java程序變量定義檢測的實(shí)際實(shí)現(xiàn)與分析，包括變量定程序分析技控制控制流分析（Controlflowysis）簡稱CFA，是一種確認(rèn)程式控制流程對(duì)象程式設(shè)計(jì)，CFACFG是一有向圖G(N，E，nentry，nexit).其中，NEn1，n2>|n1，n2∈N且n1n2}；nentrynexit和出口節(jié)點(diǎn)。它具有唯一的起始節(jié)點(diǎn)START和唯一的終止節(jié)點(diǎn)STOP。CFG中的每個(gè)節(jié)點(diǎn)至多只能有兩個(gè)直接后繼。對(duì)于有兩個(gè)直接后繼的節(jié)點(diǎn)v，其出邊具有屬性“T”或“F”，CFGNSTARTNSTOP數(shù)據(jù)個(gè)程序的控制流圖(controlflowgraphCFG)被用來確定對(duì)變量的一次賦值可GaryKildall在NavalPostgraduateSchool講發(fā)明的。數(shù)據(jù)流分析試圖獲得程序中每一點(diǎn)的特定信息。通常，在基本塊(basic向流分析(forwardflowysis)中，一個(gè)塊的結(jié)束狀態(tài)是這個(gè)塊起始狀態(tài)的outb=inb=在這里，inb是塊b的轉(zhuǎn)移函數(shù)。它作用于狀態(tài)，并產(chǎn)生出口狀態(tài)outb連接運(yùn)算符join將塊b的前驅(qū)節(jié)點(diǎn)p∈predb的出口狀態(tài)，產(chǎn)生狀態(tài)b。數(shù)據(jù)流異如誤拼、誤用變量名，刪除語句，不正確的代碼段拷貝。DFA的存在表明程序有的DFA。4種情況。時(shí)，稱該變量在這條語句中被定義。我們用d表示“定義”操作。作用r表示。釋放當(dāng)一個(gè)變量的值不可知時(shí)，稱該變量被釋放。尚未賦初值的變量k空操作上述3種操作以外的操作稱 空操作?？詹僮饔胠表示一個(gè)DFA3dk 意味著在變量的兩次連續(xù)定義之間沒它 因此，依據(jù)r、d、k、lDFA。Soot介Soot概Soot[11][12]McGillSable1996年開始開發(fā)的JavaJava實(shí)現(xiàn)，提供了多種字節(jié)碼分析和變換功Soot提供的上圖是SootSoot的輸入可以是JavaSoot內(nèi)部，通過各個(gè)模塊分工協(xié)作，利用中間表示進(jìn)行相應(yīng)Java虛擬機(jī)的電腦上運(yùn)行。Soot中間表示SootJavaJavaSoot[13]，各個(gè)分Soot（IR)，這樣可以省去一些中間表示過于復(fù)雜不易操作的弊端。期間表示，又叫中間代碼，中間語言，是復(fù)雜性介于源程序以及機(jī)器碼（字節(jié)碼）SootBaf中間表示Baf是Soot內(nèi)部基于堆棧的字節(jié)碼表示，與其他字節(jié)碼相區(qū)別的地方是BafBaf中，有對(duì)應(yīng)SootUnits的指令，所有指令實(shí)現(xiàn)了Inst接口，該接口又實(shí)Unit和SwitchableBafJava字節(jié)碼中，long，integer，short等類型變量相加的指令，在Baf中可以直接簡化為相加指令，不需要過多的去考慮類型問題。Baf最主要用于一些基于字節(jié)碼的優(yōu)化分析和變換，如窺視孔優(yōu)化等等。具體可以利用soot.baf和emal包中的內(nèi)容來實(shí)現(xiàn)Baf。JimpleJimpleJava中簡單類型化的三地址(棧無關(guān))Soot核JimpleSoot中，Jimple表示可以直接或者基于Java源程序代碼來創(chuàng)建(JDK1.4以上)JDK版本1.5JavaJava類文件來生成。Soot中的JimpleJimple轉(zhuǎn)化過程中，通過引入新的局部變jsr指令目的。Jimple表示中，清除了一imple3a200imple15條語句指令。在imple中，每條語句對(duì)應(yīng)與Sootiimple有15種表語句語句是NopSmtdtitySmt和igSmt。用于過程間控制流的語句有fStmt，GooSmt，lwichSm(對(duì)應(yīng)M中l(wèi)wich指令)LoupwichSmt(Moupwih指令)。用于過程內(nèi)控制流的語句有oSmt，umSmturoidSmt。監(jiān)視語句有SooErMoirSmt和EitoiorSmtThwSmt，SmtSmtimpleSR用于分析)imple中間表示的時(shí)候，系統(tǒng)的impleR類型三地址碼每一個(gè)inst每一條stmt200種的inst（指令15種stmt（指令ShimpleShimple可以像Jimple—樣用在某些場合分析中，Shimple中間表示是JimpleSSA的定義和所謂的phi-nodes兩個(gè)不同點(diǎn)外，Shimple幾乎和Jimple是一樣的。Shimple在控制流編碼方面非常清晰，利用Shimple代碼，我們可以很容易的進(jìn)GrimpGrimple是Jimple聚合版本，與Jimple的平面表達(dá)式不同的是它可以為表Java，Grimple的分析，反編譯也可以很好的從Gimple代碼開始。Grimple可以在soot.grimple,ernalSoot數(shù)據(jù)結(jié)構(gòu)基Soot采用的是Java語言編寫的，具有Java程序一切特性，除此以外，其Soot文件程序4）Body據(jù)結(jié)構(gòu)來表示方法的組成語句，例如Jimple中間表示來分析程序的時(shí)候，程序中方法的組成語句就會(huì)用JimpleBodyIR級(jí)別類似。chain[14]：Chain是Soot中最有用的基本數(shù)據(jù)結(jié)構(gòu)。它結(jié)合了List和Set的功能來提供一個(gè)獨(dú)立的元素有序集合的自然描述。為了討論chain數(shù)據(jù)結(jié)構(gòu)的必要性，我們考慮用ListJava方法中描述語句。ArrayList和LinkedList是List的兩個(gè)標(biāo)準(zhǔn)實(shí)現(xiàn)方式，它們兩個(gè)都不合適因?yàn)樗鼈兲峁〆moe（Object，remoe（Object）為了保證add（Object，remoe（Object）contains（Object）方法操作的常數(shù)時(shí)間，Soot定義了Chain數(shù)據(jù)結(jié)構(gòu)來有效收集一個(gè)特定元素的有序集合。Soot默認(rèn)使用HashChainChain，它本質(zhì)上是一個(gè)用Hashmap增加信息的LinkedList。因?yàn)榇_保了元素是獨(dú)立的，Hashmap可以包含一個(gè)從元素到連接的節(jié)點(diǎn)的映射，實(shí)現(xiàn)了Contains和Remove操作的時(shí)間的穩(wěn)定。除了作為Soot方法體信息的很好的描述形式，Chains給編譯器的許多演算析中需要一系列的節(jié)點(diǎn)用來，當(dāng)一個(gè)特定的節(jié)點(diǎn)時(shí)，須加表的容量（線性時(shí)間Contains（）提供一個(gè)可供選擇的節(jié)點(diǎn)信息來（常數(shù)時(shí)間。當(dāng)在迭代器中使用Chains時(shí)，它經(jīng)常會(huì)被修改，通常來說在迭代過程中修改信息十分，因?yàn)樵诋?dāng)前的迭代中會(huì)有很多復(fù)雜的結(jié)果，Soot提供ConcurrentModificationException方法來解決這一問題。snapshotI 函數(shù)將Chain中的內(nèi)容到緩沖區(qū)，并且返回緩沖區(qū)的一個(gè)迭代。這將允許程序員通過靜態(tài)副本迭代器修改Chain。Unit接口：Unit接口是Soot中最基本的接口用來表示指令或者說明。在BAFUnits是PushInst和AddInst等指令的桟基礎(chǔ)，在JIMPLE中Units是AssighStmt和InvokeStmt等指令的三地址代碼說明。2.2.4Soot控制流Soot在packagesoot.toolkits.graph中提供幾種不同的數(shù)據(jù)流圖[15]，在這些圖中提供DirectedGraph接口，定義了可以得到的方法：一個(gè)圖的和出迭代；圖的大?。ü?jié)點(diǎn)的個(gè)數(shù)多少下面描述幾個(gè)節(jié)點(diǎn)是Sootunit的CFG圖的實(shí)現(xiàn)，我們用過程內(nèi)數(shù)據(jù)流來展現(xiàn)。這些CFG圖的基本類是UnitGraphCFG圖的抽象類。有三種圖：BriefUnitGraph，ExceptionalUnitGraph和TraphUnitGraph。Soot命令行執(zhí)行操作：javajavaOptionssoot.MainsootOptions]classnamesoot.Options是Soot接受的配置項(xiàng)，可以通過java.soot.Mainhelp進(jìn)行查閱，最后一項(xiàng)classname（可以是類文件，可以是java文件或其他可以轉(zhuǎn)換成class的文件使用Ecplise使用soot生成不同類型的按照要求安裝好Soot插件后，可以選定需要分析的文件，然后右擊文件，選中選項(xiàng)Soot，然后點(diǎn)擊ProcessAllSourceFilesProcessAllClassFiles，最后點(diǎn)擊運(yùn)行RUNSootOutPut中看到。Soot數(shù)據(jù)流分析設(shè)4決定分析的精度。是may（可能）還是must（必須，具體來說是在merge時(shí)找交集還是并集。式進(jìn)行分析。向分析中，分析過程由被調(diào)用點(diǎn)一次到調(diào)用點(diǎn)，即CFG的出從CFG的點(diǎn)開始。， 的數(shù)據(jù)流框架能處理各種形式的cfg，通過接口soot.toolkits.graph.DirectedGrap實(shí)現(xiàn)。Soot的數(shù)據(jù)流框分析Soot提供三種不同的分析：ForwardFlowysis（向前的流分析）從UnitGraph的entry開始，BackwardFlowysis（向后的流分析）從UnitGraph的exit開始逆向分析，以及ForwardBranchedFlowysis（前向的出現(xiàn)分支的流分析flow流方向其他是一樣的，結(jié)果為兩張映IN集合和從節(jié)點(diǎn)到OUT集合。最后一個(gè)提供了通過不同分支節(jié)點(diǎn)傳遞不同的信息（比如信息流從帶有if（x>0）的節(jié)點(diǎn)流出時(shí)可以是x>0或者x<0IN集合，從節(jié)點(diǎn)到OUT集合以及從節(jié)點(diǎn)到branchOUT集合。在這里我們用BackwardFlowysis分析程序變量 （1）（2） upr（gdoi（；}分析的一個(gè)分析的精度由分析如何施展對(duì)lattice元素的合并來表現(xiàn)。分析可以是may或者must。may分析我們用并集來實(shí)現(xiàn)合并，must則用交集。在流分析中，joining用merge方法實(shí)現(xiàn)，實(shí)驗(yàn)程序是一個(gè)must分析，所以用交集實(shí)現(xiàn)protectvoidmerge（Objectin1，Objectin2，ObjectFlowSetinSet1=（FlowSet）in1，inSet2=（FlowSet）in2，outSet=（FlowSet）out;inSersection（inSet2，outSet}FlowFlow集合，bounded（Bounded-FlowSet接口）和unbounded（FlowSet接口。一個(gè)bounded集合知道所有可能存在的Value而unbounded不能。實(shí)現(xiàn)數(shù)據(jù)流分分析中需要的soot方法為flowThrough。這個(gè)數(shù)據(jù)流分析分為兩部分：1）IN集合移動(dòng)到OUT集合，將節(jié)點(diǎn)kills掉的2）對(duì)節(jié)點(diǎn)產(chǎn)生的OUTprotectedvoidflowThrough（Objectin，Objectnode，Object kill（inSet，u，outSetgen（outSet，u}定義初始狀這一步驟包括了定義節(jié)點(diǎn)和其他節(jié)點(diǎn)lattice元素的內(nèi)容，通過重載以下兩個(gè)類來實(shí)現(xiàn)：entryInitialFlownewInitialFlow。 lurrt} alueArrySparseSet（；}Objectequals方法。Soot元素（表示一些代碼結(jié)構(gòu)）soot.EquivTo接口來實(shí)現(xiàn)，所以如果當(dāng)需要一個(gè)flowset來二元運(yùn)算表達(dá)式，必須用equivTo方FLOW集在soot中，flowsets與個(gè)CFG中的節(jié)點(diǎn)關(guān)聯(lián)。分為有界（Bounded-FlowSet接口）和 （FlowSet接口，有界接口知道全集的取值， FlowSetflowlattices控制流soot.toolkits.graphpackageDirectedGraph和后繼節(jié)點(diǎn)，用于遍歷圖的遍歷器以及吐得大小（節(jié)點(diǎn)個(gè)數(shù)SootUnitsBaseclassUnitGraph，CFGBriefUnitGraph不包含針對(duì)exceptionExceptionalUnitGraph包含exceptionTrapUnitGraph和前者類似。獲取定義使用定義使用鏈（Def-usechain）是由一個(gè)變量（variable）所有的（Def）以及這個(gè)定義可以到達(dá)的所有，不包含中間其他的定義。定義使用定義使用鏈的考慮到變量的定義及其使用為成對(duì)出現(xiàn)，故使用hashmap來定義使用鏈的SmartLocalDefs（UnitGraphg，LiveLocalslive）結(jié)構(gòu)中的getDefsOfAt（Locall，Units）可以獲得一個(gè)局部變量在一個(gè)方法中確getUsesOf（Units）可以獲得一個(gè)局部變量在一個(gè)方法中確定節(jié)點(diǎn)處的使用情getduchainsBodyb=UnitGraphgraph= SimpleLiveLocalss=newSimpleLiveLocals(graph); tor<Unit>gIt=graph.i /*生成du-UnitdefUnit=SmartLocalDefsdes=newSmartLocalDefs(graph,/*局部變量的定義SimpleLocalUsesuses=newSimpleLocalUses(graph,List<UnitValueBoxPair>ul=uses.getUsesOf(defUnit);if(ul!=null&&ul.size()!=0){/*定義在這個(gè)單元有使用intdefLine=HashSet<Integer>useLines=/*存數(shù)使用行if(useLines==useLines=/*所有的使用for(UnitValueBoxPairvbp:ul){Stringuse=}duChains.put(defLine,}}returnduChains;/*返回定義使用鏈}在得到程序的定義使用鏈后，進(jìn)行了活躍變量分析。實(shí)驗(yàn)擴(kuò)展了Soot提供的BackwardFlowysisClass，完成了分析的構(gòu)造函數(shù)并復(fù)寫了數(shù)據(jù)流分析wcopy（FlowSet：FlowSet接口實(shí)現(xiàn)了union（）、intersection（）、isempty（）等方法；ArrayPackedSet和ArraySparseSet是FlowSet的兩種基本實(shí)現(xiàn)：前者set，set。FlowUniverse：這個(gè)class里的對(duì)象是在BoundedFlowSets被創(chuàng)建時(shí)用來確SetsbodyFlowUniverse用ArrayPackedSet表示一個(gè)空的集合用來給定的in'sout（s）（in（s）\kill（s）∪gen（s））out（s）（in（s）∩preserve（s）∪gen（s））這一塊提前計(jì)算出了每個(gè)語句的preserveset。迭代這個(gè)單元的定義表，對(duì)于每個(gè)定義，在kill將kill集合上添加的作為preservegenerateset。useboxes，useboxesgenerateset。generate實(shí)驗(yàn)環(huán)境及配4-1Windows764-SOOT實(shí)驗(yàn)結(jié)果及分案例分1.舉一個(gè)1.舉一個(gè)簡單的例子進(jìn)行分析可以把Jimple也貼后描述怎配置運(yùn)行。最終不是能輸出每個(gè)節(jié)點(diǎn)的def-use嗎。然后寫到表格貼上去。一個(gè)是人工分析進(jìn)行說明比如對(duì)每個(gè)代碼行前面標(biāo)上比如下面：intx=1001inta=x-1第二就說明第一x在第二行中使用。然后具體說明一2.2.之后你可以隨便改文件比如10個(gè)文件然后統(tǒng)計(jì)里面的代碼行數(shù)變量數(shù)，然后def然后use什么的3.3.然后可以就得出的def-use分析一下規(guī)模。比如簡短的程序得到def-use很多說明這個(gè)定義使用變量的普遍性啊什么之類然后說明一下獲取def-use分析的意義之類的手動(dòng)舉例手動(dòng)舉例一個(gè)錯(cuò)誤的例子。然后分析比如第一行intx=100;變?yōu)閤;沒有初始化然后我們獲取def-use集合就可知道前面沒有定義后使用了就存在錯(cuò)誤雖然這種情況java里面會(huì)經(jīng)常報(bào)錯(cuò)。然而面對(duì)多對(duì)象可能就存在 數(shù)據(jù)流分析牽引的話就可能在這方面起大的作用什么的隨便最后總結(jié)下說分析這個(gè)有必什么的案例 main main（String[]{intx=100；inta=x-1；intb=x-2;System.out.println（a*b}JimplepublicpublicclassTestextends{publicstaticvoid{intx,a,temp$0,b,temp$1,temp$3,temp$4;java.io.PrintStreamtemp$2;args:=@parameter0:java.lang.String[];x=100;temp$0=x-1;a=temp$0;temp$1=x-2;b=temp$1;temp$2=<java.lang.System:java.io.PrintStreamout>;temp$3=a*b;temp$4=temp$3-}在test結(jié)果分 83[1]TIOBE，ProgrammingCommunity [2]Oracle.LearnAboutJavaTechnology[EB/OL]. 秦首科.數(shù)據(jù)流上的異常檢測[D].復(fù)旦大學(xué)::ZhengJ,WilliamsL,NagappanN,etal.Onthevalueofstaticysisforfaultdetectioninsoftware[J].SoftwareEngineering,