基于PAT樹的符號執(zhí)行工具的設(shè)計與實現(xiàn)

1、分 類 號 學(xué) 號2005612100139 學(xué)校代碼 10487 密 級 碩士學(xué)位論文基于PAT樹的符號執(zhí)行工具的設(shè)計與實現(xiàn)學(xué)位申請人： 黃 晉學(xué)科專業(yè)： 計算機(jī)軟件與理論指導(dǎo)教師： 盧 炎 生 教 授答辯日期: 2007年6月2日4A Thesis Submitted in Partial Fulfillment of the Requirements for the Degree of Master of EngineeringA Symbolic Execution Tool based on Program Analysis TreeCandidate :Huang JinMajor

2、 :Computer Software and TheorySupervisor :Prof. Lu YanshengHuazhong University of Science and TechnologyWuhan 430074, P. R. ChinaJun., 2007獨創(chuàng)性聲明本人聲明所呈交的學(xué)位論文是我個人在導(dǎo)師指導(dǎo)下進(jìn)行的研究工作及取得的研究成果。盡我所知，除文中已經(jīng)標(biāo)明引用的內(nèi)容外，本論文不包含任何其他個人或集體已經(jīng)發(fā)表或撰寫過的研究成果。對本文的研究做出貢獻(xiàn)的個人和集體，均已在文中以明確方式標(biāo)明。本人完全意識到，本聲明的法律結(jié)果由本人承擔(dān)。 學(xué)位論文作者簽名： 日期：2007

3、年 月 日學(xué)位論文版權(quán)使用授權(quán)書本學(xué)位論文作者完全了解學(xué)校有關(guān)保留、使用學(xué)位論文的規(guī)定，即：學(xué)校有權(quán)保留并向國家有關(guān)部門或機(jī)構(gòu)送交論文的復(fù)印件和電子版，允許論文被查閱和借閱。本人授權(quán)華中科技大學(xué)可以將本學(xué)位論文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫進(jìn)行檢索，可以采用影印、縮印或掃描等復(fù)制手段保存和匯編本學(xué)位論文。本論文屬于 保密 ，在_年解密后適用本授權(quán)書。不保密。（請在以上方框內(nèi)打“”）學(xué)位論文作者簽名： 指導(dǎo)教師簽名：日期：2007 年 月 日 日期：2007年 月 日華中科技大學(xué)碩士學(xué)位論文摘 要隨著軟件產(chǎn)業(yè)的不斷發(fā)展，程序的規(guī)模越來越大，完全依靠手工進(jìn)行測試的難度越來越大，這就需要一些輔助測試

4、的自動化測試工具。自動化測試工具能夠自動地分析項目的源程序，自動地生成測試用例，并且達(dá)到一定的程序測試覆蓋率，大大提高軟件的可靠性和正確性，并且節(jié)約大量的人力和時間。符號執(zhí)行使用抽象的符號表示程序中變量的值，來模擬程序的執(zhí)行。符號執(zhí)行的研究對于軟件測試中測試用例的產(chǎn)生方法和程序證明理論研究，以及軟件工程中逆向工程的研究都有重要的意義。因此，無論在軟件工程的理論研究，還是在軟件測試自動化的工程實踐中，符號執(zhí)行都有進(jìn)一步研究的價值。目前國內(nèi)外對符號執(zhí)行進(jìn)行了較深入的研究，并且已經(jīng)開發(fā)出了一些工具。但是符號執(zhí)行的一些問題尚待解決，而且國內(nèi)外缺乏針對Java的符號執(zhí)行工具。對數(shù)組的處理和模塊調(diào)用的處理

5、，仍舊是Java語言符號執(zhí)行研究的難點。此外，Java語言是一種面向?qū)ο蟮恼Z言，其面向?qū)ο蟮膹?fù)雜特性也增加了其符號執(zhí)行研究的難度?；诔绦蜢o態(tài)分析樹PAT(Program Analysis Tree)樹的符號執(zhí)行方法是一種自動化的程序靜態(tài)分析方法。該方法通過分析Java源程序建立PAT樹。程序靜態(tài)分析樹能夠?qū)ava程序進(jìn)行形式化的描述。基于程序靜態(tài)分析樹的遍歷方法是一種基于Java程序的邏輯結(jié)構(gòu)的算法。此外，符號執(zhí)行系統(tǒng)的程序基本結(jié)構(gòu)處理策略、符號計算方法和方法調(diào)用也是研究的重點，針對數(shù)組這個符號執(zhí)行的難點也進(jìn)行了相關(guān)的研究。最后，通過一個針對Java程序的符號執(zhí)行工具JSE(Java Sy

6、mbolic Executor)分析表明了基于PAT樹的符號執(zhí)行在實踐中的可行性。關(guān)鍵字： 自動化測試，程序靜態(tài)分析，符號執(zhí)行，程序靜態(tài)分析樹AbstractWith the rapid development of software industry, programs are becoming larger and much more complex than ever before. During the development of software, it is too difficult to test all the programs manually, so automatic

7、ally testing tools are necessary to analysis programs. If the tools can analysis programs automatically, even generate test data automatically with high coverage of programs, the reliability of software will be improved dramatically and considerable resource will be saved. Symbolic execution simulat

8、es execution of programs with symbols instead of real values. Symbolic execution is a useful method for program testing and reverse engineering.Many people have done a lot of research on symbolic execution. Some symbolic execution tools have been developed. Still there are some problems of symbolic

9、execution need to be solved. First of all, no symbolic execution system of Java program has been developed. Secondly, solutions for array and module call are still difficulties of Java symbolic execution. Finally, the complexity of Java increases the difficulty of the symbolic execution implement.Th

10、e symbolic execution based on PAT(program analysis tree) is an automatic program static analysis method, which can analysis the Java program. Also, a visiting method is designed for PAT. Moreover, some researches on symbolic execution have been done. At the end of this thesis, a symbolic execution t

11、ool called JSE (Java Symbolic Executor) is developed. Key words: Automatically Testing, Static Analysis, Symbolic Execution, Program Analysis Tree目 錄 緒 論 )JSE)技術(shù))技術(shù))481 緒論本章首先介紹了軟件測試中符號執(zhí)行系統(tǒng)的研究背景、意義和主要研究內(nèi)容，概述了符號執(zhí)行系統(tǒng)的任務(wù)、設(shè)計原則和實現(xiàn)難點，然后列舉了迄今為止具有代表性的系統(tǒng)和框架，以及它們的優(yōu)缺點，接著指出了本文的研究重點：程序符號執(zhí)行系統(tǒng)設(shè)計與實現(xiàn)。最后指出其存在的不足，并提出了

12、改進(jìn)的方案。1.1 研究背景隨著信息技術(shù)的飛速發(fā)展，軟件產(chǎn)品應(yīng)用到了人類社會生活中的各個領(lǐng)域，但是各種軟件故障也對社會帶來了極大的經(jīng)濟(jì)損失，甚至產(chǎn)生了一定的破壞作用。特別是對于安全關(guān)鍵系統(tǒng)(Safety Critical System，如民航訂票系統(tǒng)、銀行結(jié)算系統(tǒng)、自動飛行控制軟件、軍事防御和核電站安全控制系統(tǒng)等) 對系統(tǒng)安全性有特殊的要求，而且軟件系統(tǒng)本身復(fù)雜度高。針對這種需求，以軟件測試為中心的質(zhì)量保障技術(shù)在軟件生產(chǎn)中得到了迅速的發(fā)展和應(yīng)用，軟件測試成為發(fā)現(xiàn)軟件故障，保證軟件質(zhì)量，提高軟件可靠性的主要手段。有數(shù)據(jù)表明，軟件測試在軟件開發(fā)中所占用的時間和資源一般在40%至70%。隨著軟件技術(shù)

13、不斷發(fā)展，現(xiàn)代軟件系統(tǒng)發(fā)展極其迅速，這就對軟件測試技術(shù)提出了更高的要求。軟件測試技術(shù)的進(jìn)步能夠極大的減少軟件工程中投入的時間，人力和物力，因此對軟件測試技術(shù)的研究顯得尤其重要。IEEE把軟件測試定義為：從無限大的執(zhí)行域中恰當(dāng)?shù)剡x取一組有限測試用例，對照程序已經(jīng)定義的預(yù)期行為，動態(tài)地檢驗程序的行為。實際上，軟件測試是軟件過程的一個核心工作流，貫穿于整個軟件開發(fā)過程始末。軟件測試過程包含了測試計劃的制定、測試大綱的編寫、測試用例的設(shè)計與生成、測試的實施、測試結(jié)果與問題的分析和報告、以及軟件測試的管理等工作。軟件測試有兩個基本要求，一是要驗證程序符合規(guī)約的要求；二是要證明此驗證過程是可信的。前者強(qiáng)調(diào)

14、軟件測試是一個軟件驗證工程，涵蓋軟件開發(fā)的各個方面，包括從需求說明到概要設(shè)計、詳細(xì)設(shè)計乃至編程和執(zhí)行的所有階段。具體來說軟件測試需要檢查系統(tǒng)的執(zhí)行是否正確，包括三個方面：功能方面程序必須能夠完成約定的功能，例如實時性要求；輸入和輸出方面要求程序?qū)o定的輸入須有正確的輸出，包括例外情況；對外界的影響方面同具體的環(huán)境有關(guān)，例如程序內(nèi)存管理、文件管理，以及對其它應(yīng)用程序的執(zhí)行干擾等。對于后者，測試需要一個充分性準(zhǔn)則，表明到什么程度測試可以終止并取得可信的結(jié)果。程序規(guī)約(Specification)是測試的基礎(chǔ)。規(guī)約一般在程序編寫之前就己經(jīng)明確并規(guī)定了程序應(yīng)該做什么。測試是在規(guī)則的指導(dǎo)下選擇一系列測試

15、用例，并在執(zhí)行測試用例時觀察程序行為是否符合規(guī)約的要求。不是所有的程序規(guī)約和結(jié)構(gòu)都必須被測試用例所覆蓋，因此需要一個程序的正確性定義和測試的充分性驗證準(zhǔn)則。軟件測試技術(shù)可以分為靜態(tài)測試和動態(tài)測試1。靜態(tài)測試是不執(zhí)行程序代碼而尋找程序代碼中可能存在的缺陷或評估程序代碼的過程。動態(tài)測試通過在抽樣測試數(shù)據(jù)上運行程序來檢驗程序的動態(tài)行為和運行結(jié)果以發(fā)現(xiàn)缺陷。測試也分為結(jié)構(gòu)性測試(又稱白盒測試)、功能性測試(黑盒測試)、以及程序與規(guī)約相結(jié)合的測試(灰盒測試)。白盒測試包括控制流測試和數(shù)據(jù)流測試兩類主要技術(shù)以及域測試、符號執(zhí)行(Symbolic Execution)、程序插樁和變異測試等其它技術(shù)。黑盒測試

16、又包括：等價類劃分、因果圖、判定表、邊值分析、組合覆蓋測試和狀態(tài)測試等。灰盒測試綜合考慮軟件的規(guī)范和程序的內(nèi)部結(jié)構(gòu)來生成測試數(shù)據(jù)。靜態(tài)測試中大量使用程序靜態(tài)分析技術(shù)2。程序靜態(tài)分析技術(shù)是指不編譯運行待測試程序，而是通過對程序源代碼進(jìn)行分析以發(fā)現(xiàn)其中的錯誤。程序靜態(tài)分析的目標(biāo)不是證明程序完全正確，而是作為動態(tài)測試的補充，在程序運行前盡可能多的發(fā)現(xiàn)其中隱含的錯誤，提高程序的可靠性和健壯性3。事實上在很多相當(dāng)成熟的系統(tǒng)中包含著錯誤，只憑測試人員手工很難找到這些錯誤，而通過靜態(tài)測試發(fā)現(xiàn)了現(xiàn)存系統(tǒng)的很多錯誤46。程序靜態(tài)分析的方法主要有以下幾種：(1) 符號執(zhí)行7,8。符號執(zhí)行的基本思想是，用抽象的符號

17、表示程序中變量的值，來模擬程序的執(zhí)行。該方法很好的克服了其他測試技術(shù)中不能確定程序中變量的值的問題。符號執(zhí)行常常使用于對路徑敏感的程序分析中。符號執(zhí)行結(jié)合約束求解方法理論上可以精確地靜態(tài)模擬程序的執(zhí)行，因此約束求解工具的接受能力決定了分析程序和發(fā)現(xiàn)錯誤的能力。(2) 定理證明9。自動定理證明是基于語意的程序分析特別是程序驗證中常用到的技術(shù)。但是采用消解原理的定理證明器一般并不適合于程序分析，通常使用各種判定過程來判斷公式是否為定理。(3) 類型推導(dǎo)。類型推導(dǎo)指的是由機(jī)器自動地推導(dǎo)出程序中變量和函數(shù)的類型，它的思想是將程序中的數(shù)據(jù)劃分成不同的集合，再利用類型理論中的算法進(jìn)行分析。類型推導(dǎo)適用于控

18、制流無關(guān)的分析，能夠處理大規(guī)模的程序。(4) 基于規(guī)則的檢查。在面向不同應(yīng)用的程序中，存在不同的編程規(guī)則。基于規(guī)則的檢查使用規(guī)則處理器，將規(guī)則轉(zhuǎn)換成內(nèi)部表示，將其應(yīng)用于程序分析?；谝?guī)則的分析方法的優(yōu)點是能夠針對不同的系統(tǒng)采用不同的規(guī)則進(jìn)行分析。缺點是受到規(guī)則描述機(jī)制的局限。(5) 模型檢測。模型檢測是一種驗證有限狀態(tài)并發(fā)系統(tǒng)的方法。它是基于有限狀態(tài)系統(tǒng)構(gòu)造和有向圖等抽象模型的。它的難點在于如何避免狀態(tài)空間的爆炸。以上幾種方法之間有一定的聯(lián)系。類型推導(dǎo)和模型檢測都是對程序的抽象。符號執(zhí)行和類型推導(dǎo)都有程序產(chǎn)生約束，只是約束的形式不同：符號執(zhí)行的約束形式是布爾表達(dá)式以及線性等式和不等式；類型推導(dǎo)

19、的約束形式是集合關(guān)系表達(dá)式。上面這些方法形式各異，各有相關(guān)的分析工具1014，分別實現(xiàn)了各自的理論的將價值。采用新型的編程語言和開發(fā)方式，可以極大的提高軟件系統(tǒng)的開發(fā)效率，同時也能明顯減少錯誤的引入。Java語言是當(dāng)今一種主流的軟件系統(tǒng)開發(fā)語言，具有較高的可靠性。Java使用早期問題檢查機(jī)制和運行時檢查機(jī)制，并且Java的語言模型避免了拙劣的指針和內(nèi)存分配錯誤導(dǎo)致的內(nèi)存泄漏錯誤。其次，Java被設(shè)計用于網(wǎng)絡(luò)/分布式環(huán)境，具有一定的安全機(jī)制，比如禁止運行時堆棧溢出，禁止破壞運行空間外內(nèi)存等。但是Java語言仍舊無法避免程序設(shè)計錯誤等原因帶來的軟件錯誤，例如邏輯錯誤。因此，有必要對Java語言軟件

20、測試技術(shù)進(jìn)行一定的研究。1.2 符號執(zhí)行系統(tǒng)的意義符號執(zhí)行15 (symbolic execution)的思想早已提出。符號執(zhí)行的基本思想是：用抽象的符號表示程序中變量的值，來模擬程序的執(zhí)行。該方法很好地克服了在靜態(tài)測試時不能確定程序中變量的值的問題。符號執(zhí)行常常在對路徑敏感的程序分析16,17中使用。對符號執(zhí)行的研究也有很多。通常意義下的程序執(zhí)行是給出具體的輸入數(shù)據(jù)使得程序能夠沿著某一特定路徑執(zhí)行并輸出與之對應(yīng)的具體結(jié)果。然而符號執(zhí)行的目的在于分析程序中變量之間的約束關(guān)系，不需要指定具體的輸入數(shù)據(jù)，將變量作為代數(shù)中的抽象符號處理，結(jié)合程序的約束條件進(jìn)行推理，結(jié)果是輸出一些描述變量間關(guān)系的表達(dá)

21、式。在符號執(zhí)行的過程中，控制流圖中的分支導(dǎo)致了對于變量的不同的約束條件，而這些約束條件就描述了相應(yīng)路徑的測試數(shù)據(jù)間的約束關(guān)系。符號執(zhí)行的研究無論是對軟件工程本身的研究，還是對實際工程中測試技術(shù)的發(fā)展，都有比較重要的意義18,19。首先，符號執(zhí)行和約束求解方法的研究產(chǎn)生了基于符號執(zhí)行和約束求解的測試用例產(chǎn)生標(biāo)準(zhǔn)和方法20。其次，符號執(zhí)行方法的研究中對于從代碼還原狀態(tài)圖的研究對軟件工程中的逆向工程有較大的促進(jìn)作用。此外，對于軟件測試的程序證明(program proving)理論的研究也有重要的意義21。具體來說符號執(zhí)行的應(yīng)用主要有以下幾個方面：1. 產(chǎn)生測試用例符號執(zhí)行最重要的一個應(yīng)用就是可以自

22、動生成測試用例2224。符號執(zhí)行輸入符號值和路徑選擇，然后符號執(zhí)行程序的選定路徑，得到符號執(zhí)行的結(jié)果以及路徑選擇條件集合。對于軟件測試來說，可以使用真實值代替符號輸入，那么所選用的真實值就是一組測試數(shù)據(jù)。其中，真實值產(chǎn)生的依據(jù)就是符號執(zhí)行程序某路徑的路徑選擇條件。因此，我們在軟件測試中，可以利用符號執(zhí)行，設(shè)計一些自動生成工具，遍歷符號的執(zhí)行路徑，根據(jù)不同路徑的選擇條件，自動的產(chǎn)生測試用例，而且使用這種產(chǎn)生測試用例的方法，測試的覆蓋率很高25。2. 程序證明最著名的程序證明26方法是由Floyd提出基于斷言機(jī)制的“誘導(dǎo)斷言確認(rèn)法”。該方法將斷言設(shè)置在程序模塊的開始和結(jié)尾，那么判斷一個模塊或者一段

23、程序正確與否的標(biāo)準(zhǔn)就是模塊開始處的斷言必須要保證模塊結(jié)束處斷言的正確性，否則程序模塊出現(xiàn)錯誤。例如在某個程序中要求變量A滿足A4且A10，那么我們將斷言插入程序中。在符號執(zhí)行過程中，我們可以將路徑執(zhí)行條件加入程序的斷言中去。當(dāng)一個斷言中包含路徑選擇條件的程序符號執(zhí)行時，如果路徑選擇條件與斷言一致，那么可以發(fā)現(xiàn)程序該路徑是可達(dá)的。反之，如果路徑選擇條件與斷言矛盾，可以很容易的發(fā)現(xiàn)路徑是不可達(dá)的。3. 符號調(diào)試符號執(zhí)行本身可以模擬程序的執(zhí)行過程，因此符號執(zhí)行可以用于程序的調(diào)試7技術(shù)。通常意義上的程序跟蹤調(diào)試只能跟蹤顯示程序運行過程中變量的當(dāng)前真實值。但是一個基于符號執(zhí)行的調(diào)試工具能夠跟蹤顯示變量的

24、符號表達(dá)式，這樣變量的意義就更加明顯。1.3 符號執(zhí)行系統(tǒng)的研究現(xiàn)狀對于符號執(zhí)行的研究，目前不僅已經(jīng)有了一定的理論成果2729，而且還針對各種語言開發(fā)出了許多的工具3032。本節(jié)主要介紹幾個有代表性的系統(tǒng)，并針對各個系統(tǒng)進(jìn)行相應(yīng)的評價。 交互符號執(zhí)行系統(tǒng)EFFIGYEFFIGY是一個由IBM Thomas J. Watson Research Center的James C. King等人研發(fā)的符號執(zhí)行系統(tǒng)，針對程序的調(diào)試和測試的交互性符號執(zhí)行器(Interactive Symbolic Executor)，能處理PL/I型語言的程序。EFFIGY是第一個使用符號執(zhí)行的系統(tǒng)。它利用符號執(zhí)行的特性

25、，用于程序的開發(fā)和測試。該系統(tǒng)具有一定的適應(yīng)性，其最大的特點是具有一定的交互性。符號執(zhí)行可以得到程序路徑的符號結(jié)果，并且在系統(tǒng)中逐行顯示變量的符號值。EFFIGY功能上最大的詬病在于沒有提供一個程序路徑的流程圖，這樣不便于使用者確定路徑的執(zhí)行情況。同時，它沒有提供一個路徑選擇的策略，而必須由使用者制定測試的策略，選則路徑，例如每一次循環(huán)，都要選擇是否繼續(xù)循環(huán)。這樣就加大了使用者的工作量。該系統(tǒng)沒有直接提出模塊調(diào)用的處理方法。對于數(shù)組和指針，該系統(tǒng)也沒有涉及。 功能全面的符號執(zhí)行系統(tǒng)SELECT這個試驗系統(tǒng)主要實現(xiàn)的功能包括：符號執(zhí)行程序遍歷所有可能的程序路徑；簡化符號執(zhí)行結(jié)果；自動產(chǎn)生測試用例

26、；用于程序的符號調(diào)試。SELECT具有一定的判斷程序路徑可達(dá)性的能力。這個系統(tǒng)本身就是設(shè)計用于根據(jù)設(shè)定的算法自動產(chǎn)生路徑選擇策略，從而使得符號執(zhí)行能夠覆蓋程序的每一個分支。隨著符號執(zhí)行的進(jìn)行，每添加一條程序分支，就計算程序分支的路徑選擇條件，進(jìn)而判斷路徑的可達(dá)性。SELECT的分析器能夠處理線性和非線性的不等式，并且根據(jù)結(jié)果產(chǎn)生測試用例。對于存在大量循環(huán)的程序的處理，SELECT使用交互性的策略，根據(jù)使用者的需求設(shè)定循環(huán)的次數(shù)，然后系統(tǒng)自動更新路徑選擇條件和變量的符號表達(dá)式，知道循環(huán)結(jié)束。SELECT使用預(yù)備策略處理模塊調(diào)用。當(dāng)模塊滿足復(fù)用的條件時，即不存在不確定的過程，例如循環(huán)，那么在符號執(zhí)

27、行前單獨處理每一個子模塊，記錄下符號執(zhí)行結(jié)果和路徑選擇條件。當(dāng)子模塊被調(diào)用時，直接使用子模塊的處理結(jié)果。但是這樣會導(dǎo)致程序可選擇路徑的數(shù)量爆炸，影響符號執(zhí)行的運行效率。1.3.3 單元測試引擎CUTECUTE33是近年來出現(xiàn)的一個針對C語言和Java語言的單元測試工具。該工具能夠系統(tǒng)的自動的測試面向過程的C語言（包含指針）和并行的Java程序。CUTE結(jié)合了具體執(zhí)行和符號執(zhí)行的優(yōu)點，避免了隨機(jī)測試的低效性。CUTE通過具體執(zhí)行和符號執(zhí)行相結(jié)合的方式執(zhí)行待測程序。它的符號執(zhí)行的方式區(qū)別傳統(tǒng)的符號執(zhí)行方式，符號執(zhí)行是在程序具體執(zhí)行的基礎(chǔ)上進(jìn)行的。在CUTE的執(zhí)行過程當(dāng)中，收集程序執(zhí)行路徑的路徑選擇

28、條件，在程序某條路徑的結(jié)尾，處理收集到的一組符號約束條件，產(chǎn)生該路徑的測試用例。CUTE的算法首先隨機(jī)產(chǎn)生一個具體的輸入，然后循環(huán)執(zhí)行以下過程：(1) 使用產(chǎn)生的輸入執(zhí)行代碼，同時計算路徑符號約束條件；(2) 如果遇到程序分支，隨機(jī)產(chǎn)生一個具體輸入；(3) 如果當(dāng)前程序分支執(zhí)行完成，那么退回前一個分支節(jié)點，處理路徑的符號約束，計算出執(zhí)行該分支節(jié)點的其他未執(zhí)行路徑的具體輸入值。CUTE采用了深度優(yōu)先遍歷的策略，遍歷了整個程序的分支。更重要的是，算法使用的是具體值來執(zhí)行程序，因此發(fā)現(xiàn)的程序錯誤具有較高的可信度。為了驗證CUTE的正確性，進(jìn)行了相關(guān)的測試實驗。一個是比較流行的用C語言編寫的數(shù)據(jù)結(jié)構(gòu)庫

29、SGLIB，另一個是著名的Sun公司在中被廣泛使用的安全的線程收集框架。使用CUTE對SGLIB進(jìn)行單元測試，在三秒鐘內(nèi)發(fā)現(xiàn)了兩個錯誤。一個錯誤是在一個雙鏈表庫中發(fā)現(xiàn)的，一個非空的鏈表鏈接到了一空鏈表中去了。另一個錯誤是一個死循環(huán)。后來SGLIB的開發(fā)者證實了錯誤的存在。使用JCUTE對安全的線程收集框架進(jìn)行測試，意外的發(fā)現(xiàn)了潛在的多線程之間的競爭，死鎖，不能被捕獲的異常和死循環(huán)。這再一次的證明了CUTE的算法的正確性。現(xiàn)有研究總結(jié)對于符號執(zhí)行研究的難點，國內(nèi)外的許多學(xué)者有了一些初步的研究。國內(nèi)特別是中科院的張健等研究員對于符號執(zhí)行的指針，結(jié)構(gòu)變量，路徑可達(dá)性問題和約束求解問題有一定的研究。具

30、體來說，符號執(zhí)行研究存在的主要難題有以下四個：1. 循環(huán)(loop)的處理如果程序中循環(huán)7的次數(shù)是未知的，或者說是動態(tài)的取決于程序的輸入或者狀態(tài)，那么符號執(zhí)行是無法獲知執(zhí)行的路徑的，會造成符號執(zhí)行處理過程復(fù)雜化。如果循環(huán)次數(shù)太多，那么符號執(zhí)行也是不可行的。因此對于循環(huán)，主要采取交互式的方式，手動設(shè)置循環(huán)次數(shù)上限或者交互式設(shè)置循環(huán)次數(shù)，處理符號執(zhí)行中的循環(huán)執(zhí)行次數(shù)不確定的問題。2. 模塊調(diào)用 (module call)的處理程序中存在著大量的模塊調(diào)用7，如函數(shù)的調(diào)用。但是這樣的調(diào)用會造成符號執(zhí)行處理過程的爆炸34，那么對于符號執(zhí)行也是不可行的。處理符號執(zhí)行中的模塊調(diào)用主要有兩種策略：動態(tài)擴(kuò)展策略

31、和預(yù)處理策略。前者在對某個模塊符號執(zhí)行時，實時地對某個模塊進(jìn)行符號執(zhí)行，它的優(yōu)點是符號執(zhí)行過程靈活，且存儲空間需求低，但是消耗了一定的執(zhí)行時間。后者在針對某個程序符號執(zhí)行時前，已經(jīng)將所有模塊進(jìn)行了符號執(zhí)行，并將符號執(zhí)行的結(jié)果紀(jì)錄下來，以后在符號執(zhí)行過程中如果需要調(diào)用模塊，只需要調(diào)用該模塊的符號執(zhí)行結(jié)果。它的優(yōu)點是一次執(zhí)行，永久使用。但是它不適用于存在不確定元素，如循環(huán)和數(shù)組的模塊，靈活性差，且對于大型程序，占用大量的存儲空間。3. 數(shù)組(array)的處理對于數(shù)組35，如果程序中出現(xiàn)了下標(biāo)是變量的數(shù)組成員，比如Ai，其中i是一個變量，那么符號執(zhí)行時，對Ai的操作，比如賦值，處理起來就會十分復(fù)雜

32、。對數(shù)組元素的混淆，已經(jīng)提出了一種處理符號執(zhí)行中數(shù)組元素混淆的方法，通過轉(zhuǎn)換存在數(shù)組元素混淆的代碼段，可以被一般的符號執(zhí)行工具識別。此外，中科院軟件所的張健提出了基于形式轉(zhuǎn)換的處理數(shù)組和指針的方法，設(shè)計了工具PAT，實現(xiàn)了對數(shù)組和指針元素的操作。4. 不可達(dá)路徑 (infeasible path)的處理符號執(zhí)行研究中的不可達(dá)路徑問題36,37實際上是基于約束性問題38的。由于程序中存在著大量的不可達(dá)路徑，符號執(zhí)行揭示這些不可達(dá)路徑，從而測試程序分支的正確性。因此，對不可達(dá)路徑的研究也是十分有意義的。目前中科院的張健對此進(jìn)行了一定的研究，給出了分離路徑執(zhí)行條件和針對整形和布爾型的線性條件約束求解

33、的方法，提出了基于程序流圖的搜索算法，并且實現(xiàn)了約束求解工具BoNuS2。1.4 論文的組織結(jié)構(gòu)本文符號執(zhí)行系統(tǒng)的研究與實現(xiàn)分為理論研究和技術(shù)實現(xiàn)這兩個方面。理論研究的主要內(nèi)容包括建立程序靜態(tài)分析的中間表示模型和建立描述符號執(zhí)行的行為模型。符號執(zhí)行系統(tǒng)的技術(shù)實現(xiàn)包括Java程序靜態(tài)分析技術(shù)、符號計算技術(shù)和可視化技術(shù)?；谏鲜鲅芯績?nèi)容，本文各章的內(nèi)容安排如下：第1章概述了符號執(zhí)行系統(tǒng)的研究背景，然后介紹了研究符號執(zhí)行的意義、主要任務(wù)、設(shè)計原則以及實現(xiàn)難點，最后講述未來發(fā)展方向和本論文的研究內(nèi)容。第2章介紹了符號執(zhí)行系統(tǒng)JSE的整體結(jié)構(gòu)，包括其層次結(jié)構(gòu)和各個組成模塊的主要功能，然后描述了符號執(zhí)行的

34、工作流程。第3章主要提出了符號執(zhí)行系統(tǒng)靜態(tài)分析中信息提取的需求，闡釋了JSE的代碼信息提取框架，分析了其對應(yīng)的信息提取策略。JSE的信息提取框架極大優(yōu)化了信息存儲結(jié)構(gòu)，而其對應(yīng)的信息提取策略較好的改進(jìn)了信息提取的方式和效率。第4章主要針對符號執(zhí)行的特點和難點，提出了相應(yīng)的解決策略和算法；同時，針對模塊調(diào)用產(chǎn)生的超大規(guī)模問題，提出了靈活分類機(jī)制，并通過高效的數(shù)據(jù)分類算法和模塊處理算法對其進(jìn)行了實現(xiàn)。第5章系統(tǒng)測試包括功能測試和性能測試。針對JSE的信息提取策略，測試了符號執(zhí)行的信息提取效果，包括多種代碼靜態(tài)信息的顯示，程序變量的符號表達(dá)式的實時更新，程序的路徑可達(dá)性的等。針符號執(zhí)行中處理模塊調(diào)用

35、的不同，在符號執(zhí)行程序效率方面，分別比較了簡單策略和優(yōu)化策略兩種情況下的性能，最終證實了該理論研究的可行性和有效性。第6章對全文進(jìn)行總結(jié)并展望了未來的工作。主要對信息提取策略和符號執(zhí)行優(yōu)化策略進(jìn)行了評價，并初步規(guī)劃了在該研究領(lǐng)域的未來的改進(jìn)方案。最后是致謝和參考文獻(xiàn)。2 符號執(zhí)行系統(tǒng)JSE在分析了現(xiàn)有符號執(zhí)行系統(tǒng)的優(yōu)缺點之后，針對Java語言的特點，設(shè)計了Java語言的符號執(zhí)行系統(tǒng)JSE(Java Symbolic Executor)。本章簡要描述了JSE的系統(tǒng)構(gòu)架、工作流程和用戶實例，說明了該系統(tǒng)在構(gòu)架上具有清晰的層次和良好的可擴(kuò)展性。2.1 符號執(zhí)行系統(tǒng)概述針對Java語言的符號執(zhí)行工具J

36、SE能夠模擬程序執(zhí)行，并且用抽象的符號表示程序中變量的值。該方法可以對Java這種路徑敏感語言使用，并且能夠克服在其他靜態(tài)測試時不能確定程序中變量的值的問題。JSE的實現(xiàn)主要有以下三個方面的意義：(1) 提供一個針對Java語言的程序靜態(tài)分析架構(gòu)。不同于已有的基于某種語言提供斷言機(jī)制的符號執(zhí)行技術(shù)，JSE的研究基礎(chǔ)實質(zhì)上是Java源程序的靜態(tài)分析技術(shù)，類似于程序的編譯技術(shù)。它是一種底層的技術(shù)，通過分析代碼的成分，各種成分之間的關(guān)系，然后產(chǎn)生一個適用于符號執(zhí)行的框架結(jié)構(gòu)，從而進(jìn)行符號執(zhí)行。從這一點上來說，現(xiàn)有的編譯技術(shù)可以給系統(tǒng)設(shè)計以很好的啟發(fā)。(2) 符號調(diào)試方法。符號執(zhí)行本身可以模擬程序的執(zhí)

37、行過程，因此符號執(zhí)行可以用于程序的調(diào)試技術(shù)。通常意義上的程序跟蹤調(diào)試只能跟蹤顯示程序運行過程中變量的當(dāng)前真實值。但是一個基于符號執(zhí)行的調(diào)試工具能夠跟蹤顯示變量的符號表達(dá)式，這樣變量的意義就更加明顯。因此，符號執(zhí)行運用于調(diào)試技術(shù)也是很有意義的。(3) 為今后進(jìn)一步的相關(guān)研究奠定堅實的理論和實踐基礎(chǔ)。對于軟件測試，符號執(zhí)行系統(tǒng)的研究可以產(chǎn)生測試用例，并且相對于隨機(jī)測試等其他的方法，產(chǎn)生的測試用例的覆蓋率要高出很多。對于程序證明等理論研究，符號執(zhí)行提供了一個形式化工具，為程序證明提供了強(qiáng)有力的試驗工具。JSE的基礎(chǔ)就是對程序進(jìn)行使用一定的靜態(tài)分析技術(shù)進(jìn)行一定的處理，并通過靈活、可靠的框架將這些數(shù)據(jù)匯

38、聚、結(jié)構(gòu)化并用于符號執(zhí)行。系統(tǒng)能保證正確和全面地提取信息，并且滿足系統(tǒng)高效、可擴(kuò)展性和健壯性的要求。2.2 符號執(zhí)行系統(tǒng)架構(gòu)主體框架結(jié)構(gòu)系統(tǒng)基于Java的訪問者(Visitor)模型，提供了一系列代碼分析功能。系統(tǒng)模塊結(jié)構(gòu)如圖所示。圖中標(biāo)識了JSE的兩個主要邏輯層：靜態(tài)分析層和應(yīng)用層。靜態(tài)分析層主要負(fù)責(zé)Java源程序的預(yù)處理和靜態(tài)分析，生成PAT樹和源程序文本對象；應(yīng)用層主要實現(xiàn)了基于PAT樹的符號執(zhí)行功能，此外還實現(xiàn)了PAT樹和Java源程序文本的可視化功能。各種功能各司其職，互相協(xié)作，保證符號執(zhí)行系統(tǒng)功能完善、結(jié)構(gòu)清晰，并具有良好的可維護(hù)性。圖2.1 JSE系統(tǒng)模塊框架圖靜態(tài)分析層分析源程

39、序，得到程序的一個中間形式程序靜態(tài)分析樹。雖然由源程序直接實現(xiàn)應(yīng)用層的功能是可行的，甚至更高效，但是使用中間形式，可以實現(xiàn)分析程序與符號執(zhí)行應(yīng)用的邏輯獨立性，能夠比較容易的實現(xiàn)面向不同應(yīng)用和不同語言的符號執(zhí)行系統(tǒng)。在不改變符號執(zhí)行前端代碼分析程序的情況下為新的應(yīng)用構(gòu)造一個新的應(yīng)用框架。同樣對于一個新的語言，在不改變已有應(yīng)用框架的情況下，為新的語言構(gòu)造一個分析該語言的分析程序，就可以構(gòu)造出新語言的符號執(zhí)行系統(tǒng)。使用中間形式的主要缺點是：中間形式的生成相比不使用中間形式的應(yīng)用在效率上會有所降低，這是因為中間形式需要再一次的處理才能生成符號執(zhí)行所需目標(biāo)結(jié)構(gòu)。程序的中間形式常見的是樹形表示，如圖所示。

40、樹形表示是一種最常見的表示方式，它最大的優(yōu)點就是能夠反映出程序的自然層次結(jié)構(gòu)，而且能夠滿足應(yīng)用的需求。程序分析樹在程序分析和提取符號執(zhí)行有效信息之間建立了一個清晰的接口。WXYZ圖程序分析樹應(yīng)用層主要實現(xiàn)符號執(zhí)行和可視化這兩個方面的功能，它的實現(xiàn)是基于程序分析樹及其遍歷算法組成的數(shù)據(jù)結(jié)構(gòu)框架的。結(jié)構(gòu)化顯示程序元素的功能主要通過遍歷程序分析樹，提取出相關(guān)的信息，然后通過圖形用戶接口顯示。符號執(zhí)行功能首先提取符號執(zhí)行有效信息，然后進(jìn)行相關(guān)的處理。圖描述了符號執(zhí)行JSE的執(zhí)行模型。圖2.3 原型系統(tǒng)JSE執(zhí)行模型系統(tǒng)模塊設(shè)計符號執(zhí)行系統(tǒng)JSE的主要任務(wù)是符號執(zhí)行Java源程序，并實現(xiàn)可視化功能。下面

41、對設(shè)計的模塊作總體性的介紹：1. 靜態(tài)分析模塊在原型系統(tǒng)中，采用開源項目eclipse的JDT(Java Development Tool)對Java源程序進(jìn)行靜態(tài)分析，靜態(tài)分析的主要功能包括詞法分析和改進(jìn)的語法分析。詞法分析是將Java慣用的詞法如關(guān)鍵字、專用符號、注釋、標(biāo)識符、數(shù)字等終結(jié)符劃分出來作為語法分析的輸入；語法分析的任務(wù)是對詞法分析的結(jié)果進(jìn)行語義分析，產(chǎn)生抽象語法樹。進(jìn)一步地產(chǎn)生類結(jié)構(gòu)信息表、函數(shù)、語句列表等。語法分析是識別程序結(jié)構(gòu)的過程，通常采用遞歸下降法，具體做法是將語法規(guī)則的每一項都寫成一個處理函數(shù)，分析過程中采用向前看一個語言單元，判斷所處的狀態(tài)并調(diào)用相應(yīng)的處理函數(shù)。JS

42、E的語法分析經(jīng)過改進(jìn)，加入了針對符號執(zhí)行系統(tǒng)的PAT樹語法，并在抽象語法樹的基礎(chǔ)上，使用Java的合成模式，生成了針對符號執(zhí)行的程序靜態(tài)分析樹。此外，靜態(tài)分析模塊還使用JDT生成的文本對象，實現(xiàn)了對代碼文本副本的輔助操作功能。2. 符號執(zhí)行模塊符號執(zhí)行模塊是應(yīng)用層的主要功能模塊，也是原型系統(tǒng)的核心模塊。符號執(zhí)行模塊的輸入是PAT樹，核心方法是PAT樹的遍歷方法，輸出的符號執(zhí)行結(jié)果。符號執(zhí)行的主要流程是：首先遍歷根據(jù)程序生成PAT樹，生成變量列表；然后使用路徑控制模塊控制模擬程序執(zhí)行的執(zhí)行路徑，每當(dāng)遇到分支時，與用戶進(jìn)行交互，根據(jù)用戶的選擇從而選擇執(zhí)行的路徑，并且記錄路徑選擇條件；每當(dāng)執(zhí)行到需要

43、符號執(zhí)行的語句時，就對相應(yīng)的變量進(jìn)行符號計算，然后更新變量列表，將符號計算結(jié)果輸入變量列表。符號執(zhí)行模塊包括四個子模塊：(1) PAT樹遍歷功能模塊。針對基于Java的合成模式構(gòu)造的PAT樹，采用訪問者模式設(shè)計PAT樹的遍歷功能。該遍歷功能能夠遍歷Java語言的各種語法結(jié)構(gòu)，如類文件、包聲明、import聲明、類聲明、類結(jié)構(gòu)體、變量聲明、類的方法、if結(jié)構(gòu)、while結(jié)構(gòu)、賦值語句和中綴表達(dá)式等結(jié)構(gòu)。(2) 變量列表相關(guān)功能模塊。變量列表主要內(nèi)容包括變量名和變量的符號值。首先，遍歷PAT樹，初始化符號執(zhí)行的變量列表，變量的符號值初始化為變量名；在符號計算過程中，每次計算到一個變量就在變量列表中

44、查找相應(yīng)的變量；每次符號計算完成后，查找需更新變量，更新相關(guān)變量。(3) 符號計算模塊。符號計算模塊是該原型系統(tǒng)的核心模塊之一，該模塊實現(xiàn)了中綴表達(dá)式中變量值的符號替換。當(dāng)符號執(zhí)行系統(tǒng)處理賦值語句的中綴表達(dá)時，系統(tǒng)根據(jù)PAT樹遍歷方法遍歷中綴表達(dá)式，每次遍歷到一個變量，查找變量列表，用變量的符號值替換變量，最后就得到了符號計算的結(jié)果。(4) 路徑控制模塊。路徑控制模塊也是該原型系統(tǒng)的核心模塊之一，該模塊實現(xiàn)了在符號執(zhí)行系統(tǒng)模擬程序執(zhí)行過程中選擇執(zhí)行路徑的功能。Java程序中存在分支結(jié)構(gòu)和循環(huán)結(jié)構(gòu)，因此程序執(zhí)行路徑不是簡單的順序結(jié)構(gòu)。當(dāng)符號執(zhí)行分支結(jié)構(gòu)時，使用PAT樹的相應(yīng)的遍歷方法，符號執(zhí)行系

45、統(tǒng)提示用戶輸入執(zhí)行分支選擇，然后系統(tǒng)根據(jù)輸入執(zhí)行用戶選擇的路徑。同樣，當(dāng)符號執(zhí)行循環(huán)結(jié)構(gòu)時，使用PAT樹處理循環(huán)的遍歷方法，符號執(zhí)行系統(tǒng)提示輸入執(zhí)行次數(shù)，用戶輸入后系統(tǒng)根據(jù)輸入次數(shù)循環(huán)執(zhí)行相應(yīng)的語句。3. 可視化模塊可視化模塊屬于原型系統(tǒng)的應(yīng)用層。可視化模塊分為三個子模塊：源程序文本顯示模塊、PAT樹可視化模塊和符號執(zhí)行結(jié)果可視化模塊。(1) 源程序文本可視化模塊：使用已生成的文本對象和文本控件，可視化源程序，并實現(xiàn)代碼高亮和代碼定位等功能；(2) PAT樹可視化模塊：根據(jù)已生成的PAT樹和PAT樹的遍歷方法，使用樹狀控件，實現(xiàn)一個可視化的樹型結(jié)構(gòu)；(3) 符號執(zhí)行結(jié)果可視化模塊：符號執(zhí)行結(jié)果

46、包括變量的符號值和路徑選擇條件，可以使用文本控件，實現(xiàn)符號執(zhí)行結(jié)果的可視化。2.3 小結(jié)本章主要介紹了JSE的體系結(jié)構(gòu)和工作流程。為了使符號執(zhí)行系統(tǒng)具有良好的健壯性和可維護(hù)性，JSE采用了分層的構(gòu)架。系統(tǒng)的四個功能模塊（文件管理模塊、程序靜態(tài)分析模塊、可視化組件、符號執(zhí)行組件）分布在三個邏輯層（基礎(chǔ)層、中間層和應(yīng)用層）中。在描述了符號執(zhí)行系統(tǒng)基礎(chǔ)構(gòu)架之后，介紹了各模塊的調(diào)用關(guān)系。最后，從用戶的角度介紹了JSE中程序靜態(tài)分析和符號執(zhí)行的工作流程，以及如何完成各種不同的功能。通過此章的介紹可以看出，該系統(tǒng)在結(jié)構(gòu)上遵循了符號執(zhí)行系統(tǒng)可擴(kuò)展性和健壯性的設(shè)計原則。不過要真正進(jìn)行較好的符號執(zhí)行，還需要各個

47、模塊的細(xì)節(jié)設(shè)計和實現(xiàn)。其中程序信息的有效組織和符號執(zhí)行的機(jī)制是JSE的重點和難點。3 Java程序靜態(tài)分析技術(shù)程序靜態(tài)分析39是符號執(zhí)行的基礎(chǔ)，也是一個實現(xiàn)的難點。程序靜態(tài)分析的主要功能包括構(gòu)造程序靜態(tài)分析樹和實現(xiàn)程序靜態(tài)分析樹的遍歷這兩個部分。本章主要集中研究與符號執(zhí)行緊密聯(lián)系的程序靜態(tài)分析的要點，具體來說就是如何構(gòu)造一種與程序?qū)?yīng)的數(shù)據(jù)結(jié)構(gòu)，如何設(shè)計針對這個數(shù)據(jù)結(jié)構(gòu)的靈活高效的遍歷方法。而程序靜態(tài)分析樹的實現(xiàn)借鑒了現(xiàn)有的編譯技術(shù)，因此它的實現(xiàn)只作必要的介紹。程序靜態(tài)分析從根本上說，Java源代碼只是一些普通的文本文件。對一個Java 源代碼文件進(jìn)行編輯最直觀的方法，就是采用文本掃描工具。然

48、而在實際運用中，它有很大的局限性，如圖中的代碼。/Example 類package example ;public class Exampleint foo = 1;public int getFoo( )return foo; public int getFoo(int foo) return foo + this. Foo; 圖示例Java代碼在對以上代碼做解釋時，就會發(fā)現(xiàn)一個單純的掃描程序很難區(qū)分方法getFoo（）中的foo 與getFoo（int foo）方法中傳入的實例變量foo。類似的，也很難區(qū)分同一個getFoo（int foo）方法中實例變量foo 與本地引用this. fo

49、o 所表示的不同含義。程序靜態(tài)分析樹能準(zhǔn)確、形象地描述了程序的邏輯機(jī)構(gòu)，具有較強(qiáng)的描述能力。在這個例子中，它會考慮“foo”引用的上下文，將不同方法體中“foo”引用表示成程序靜態(tài)分析樹中不同的節(jié)點，易于客戶端識別它們。如果采用程序靜態(tài)分析樹PAT(Program Analysis Tree)作為中間表示形式，對程序進(jìn)行靜態(tài)分析后的輸出，是依據(jù)某種文法生成的在內(nèi)存中具有統(tǒng)一結(jié)構(gòu)的程序靜態(tài)分析樹，從而能很好地實現(xiàn)軟件復(fù)用。并且針對Java 源代碼的編輯操作（例如在Example 類中對本地引用foo 的重命名操作）只需要遍歷這一個由對象構(gòu)成的樹型層次結(jié)構(gòu)，因此使用程序靜態(tài)分析樹也非常的方便。程序

50、靜態(tài)分析樹對于面向?qū)ο蟮南到y(tǒng)，有些源代碼的語法成分是我們不關(guān)心的，而有些是我們要重點關(guān)注的，因此在對Java 源代碼的語法分析過程中沒有必要去生成一棵完整的抽象語法樹。在抽象語法樹中去掉那些不必要的信息，從而可獲得更有效的源程序中間表示，這種經(jīng)變換后的語法樹就是程序靜態(tài)分析樹。要建立一個程序靜態(tài)分析樹，必須以程序靜態(tài)分析樹的文法為前提。文法是決定怎樣將語言的元素組合起來的規(guī)則的集合。給定一個編程語言Java 之后，就可以根據(jù)Java 語言的特點定義出程序靜態(tài)分析樹的文法。Java語言有多種結(jié)構(gòu)，限于篇幅，主要文法示例如下：文法1. CompilationUni t= ( PackageDecl

51、aration ) ? ( ImportDeclaration ) * ( TypeDeclaration ) * ；文法2. PackageDeclaration = “package” Name “;” ；文法3. ImportDeclaration =“import”Name(“.”“*”)?“;”；文法4. TypeDeclaration = ( ClassDeclaration | InterfaceDeclaration | “;” ) ；文法5. IfStatement = “if”“(“Expression”)”Statement (“else”Statement)?；文法6.

52、 WhileStatement = “while” “ ( “Expression” ) ” Statement。其中：CompilationUnit：一個編譯單元，對應(yīng)一個類文件；PackageDeclaration：包聲明；ImportDeclaration：一個引用聲明；TypeDeclaration：類型聲明，即聲明主體；ClassDeclaration：類聲明，即類的主體；InterfaceDeclaration：接口主體，即接口主體；IfStatement：if機(jī)構(gòu)主體；WhileStatement：while結(jié)構(gòu)主體；Expression：表達(dá)式；Statement：語句。PAT

53、樹的構(gòu)造1. 程序靜態(tài)分析樹的結(jié)點程序分析樹的每一個節(jié)點是一個類的對象，代表一個類型的語句. 基于Java 語言的程序靜態(tài)分析樹文法中包含了86 條文法規(guī)則，規(guī)則的左部出現(xiàn)的符號稱為非終結(jié)符號，對應(yīng)為程序靜態(tài)分析樹的復(fù)合節(jié)點；規(guī)則中不屬于非終結(jié)符號集合的符號稱為終結(jié)符號，對應(yīng)的是樹葉節(jié)點，因此在我們設(shè)計的解釋器中，節(jié)點類包含了這86 條規(guī)則對應(yīng)的基本類，主要的類圖示意如圖3.2所示。圖3.2結(jié)點類繼承關(guān)系圖CompilationUnit等基本類都繼承于ASTNode類， ASTNode類定義了setParent( )和addChild( )等基本操作。2. 程序靜態(tài)分析樹的構(gòu)造在構(gòu)造程序靜態(tài)分

54、析樹的過程中，使用了已有的詞法分析和語法分析工具JDT，構(gòu)造PAT樹則采用了Java合成(Composite)模式40。合成模式利用整體和部分的關(guān)系將對象組織到樹結(jié)構(gòu)中，使得客戶端把一個個單獨的成分對象和由它們復(fù)合而成的對象同等對待。設(shè)計采用的程序靜態(tài)分析樹樹是一個有向樹結(jié)構(gòu)，一個節(jié)點對象既持有對所有子對象的引用，又持有對其父對象的引用。其構(gòu)造的過程在后面有詳細(xì)的描述。在程序分析樹的構(gòu)造過程中，涉及到解釋器(Interpreter)模式。通常方法是設(shè)計一個解釋器，客戶端可以使用這個解釋器來解釋Java 源代碼。解釋器在掃描Java 源代碼的過程中，通過匹配從而去創(chuàng)建一個個節(jié)點類對應(yīng)的對象。其工

55、作流程如圖3.3所示。圖3.3 PAT樹的構(gòu)造方法詞法分析器的任務(wù)是從左至右逐個字符地對源程序進(jìn)行掃描，產(chǎn)生一個個的單詞符號。單詞符號是一個程序語言的基本，包括：關(guān)鍵字、標(biāo)識符、常數(shù)運算符、界符等，掃描操作返回值是一個整型變量，用于判斷哪一個節(jié)點類對象需要創(chuàng)建。語法分析是解釋過程的核心部分，它的任務(wù)是在詞法分析識別出單詞符號串的基礎(chǔ)上，建立一棵與輸入串相匹配的語法分析樹。每個節(jié)點類都對應(yīng)一個調(diào)用方法，用于創(chuàng)建這個節(jié)點類的對象。例如：根節(jié)點類CompilationUnit 對應(yīng)了方法CompilationUnit( )， 類PackageDeclaration對應(yīng)了方法PackageDeclar

56、ation( )。這些方法之間的互相調(diào)用，依據(jù)PAT樹的文法規(guī)則來予以確認(rèn)。如圖，給出一個Java類Test，它只有一個方法main( )，并且根據(jù)這個程序構(gòu)造對應(yīng)的PAT樹。這個程序計算兩個整數(shù)的商和余數(shù)。其中m是被除數(shù)，n是除數(shù)，r是余數(shù)，q是商。下面針對main()為例來闡述程序靜態(tài)分析樹的創(chuàng)建過程。解釋器的掃描過程是從第一行第一列開始，從上往下從左至右進(jìn)行掃描的。如何將子樹的節(jié)點依據(jù)父子關(guān)系連成一個子樹？本文采用“自下而上”語法分析方法，即從語法樹的末端開始，步步向上“歸約” ，直至根節(jié)點。自下而上分析法是一種“移進(jìn)、歸約”法。這種方法是利用一個寄存節(jié)點的先進(jìn)后出棧，首先把某個分枝的末

57、端節(jié)點進(jìn)棧，當(dāng)棧頂形成某個產(chǎn)生式的一個候選式時，把棧頂?shù)倪@一部分歸約成該文法規(guī)則的左部符號。package test;public class Testvoid main(int m, int n) int q=0, r=m; while(r=n) r=r-n; q=q+1; 圖 main()函數(shù)代碼文法CompilationUnit = ( PackageDeclaration ) ? ( ImportDeclaration ) * ( TypeDeclaration ) * 表明CompilationUnit 對象是根節(jié)點。文法規(guī)則的右部說明了CompilationUnit 節(jié)點可能有三個子節(jié)點： PackageDe