基于gcc抽象語法樹文本的c源程序語義分析方法研究

1、碩士學(xué)位論文基于 GCC 抽象語法樹文本的 C 源程序語義分析方法研究RESEARCH ON SEMANTIC ANALYSISOF C PROGRAM BASED ON GCC ABSTRACTSYNTAX TREE TEXT封戰(zhàn)勝2009 年 6 月國內(nèi)圖書分類號：TP311.5國際圖書分類號：681學(xué)校代碼：10213密級：公開碩士學(xué)位論文基于 GCC 抽象語法樹文本的 C 源程序語義分析方法研究碩 士 研 究 生：封戰(zhàn)勝導(dǎo)師：蘇小紅教授申 請 學(xué) 位：工學(xué)碩士學(xué)科：計(jì)算機(jī)科學(xué)與技術(shù)所 在 單 位：計(jì)算機(jī)科學(xué)與技術(shù)答 辯 日 期： 2009 年 6 月授予學(xué)位單位：哈爾濱工業(yè)大學(xué)Clas

2、sified Index: TP311.5U.D.C:681Dissertation for the Master Degree in EngineeringRESEARCH ON SEMANTIC ANALUSISOF C PROGRAM BASED ON GCC ABSTRACTSYNTAX TREE TEXTCandidate：Supervisor：Academic Degree Applied for：Speciality：Affiliation：Date of Defence：Feng ZhanshengProf.Su XiaohongMaster of EngineeringCom

3、puter Science and TechnologySchool of Computer Scinence andTechnologyJune, 2009Degree-Conferring-Institution： Harbin Institute of Technology哈爾濱工業(yè)大學(xué)工學(xué)碩士學(xué)位論文摘要本文致力于完成 C 語言源程序的系統(tǒng)依賴圖的構(gòu)造，系統(tǒng)依賴圖是靜態(tài)分析工具的基礎(chǔ)，在逆向工程中具有重要意義。系統(tǒng)依賴圖的構(gòu)造可以歸結(jié)為控制流分析和數(shù)據(jù)流分析，控制流分析主要是求取語句間的控制依賴關(guān)系，可以歸結(jié)為父親-孩子關(guān)系的求解。數(shù)據(jù)流分析主要是求取語句間的數(shù)據(jù)依賴關(guān)系，可以歸結(jié)為到

4、達(dá)-定值信息的求解。本文提出了一種基于 GCC 抽象語法樹文本的構(gòu)造系統(tǒng)依賴圖的新方法，首先，對 GCC 抽象語法樹進(jìn)行了深入的研究，統(tǒng)計(jì)出 GCC 抽象語法樹中各個(gè)符號的含義，為后續(xù)研究奠定了基礎(chǔ)。其次，對 GCC 抽象語法樹文本進(jìn)行了標(biāo)準(zhǔn)化及消除文本中與控制流分析和數(shù)據(jù)流分析無關(guān)的冗余信息。再次，用面向?qū)ο蟮乃枷雭磉M(jìn)行靜態(tài)信息提取。最后，在構(gòu)造系統(tǒng)依賴圖時(shí)，本文沒有采用傳統(tǒng)構(gòu)造系統(tǒng)依賴圖的流程，而是首先建立了控制依賴圖，其次在控制依賴圖的基礎(chǔ)上構(gòu)建控制流圖，再次在控制流圖的基礎(chǔ)上構(gòu)建數(shù)據(jù)流圖。同時(shí)本文給出了各個(gè)步驟的具體算法描述，其中包含了自己的算法及對以往算法的改進(jìn)。為了提高數(shù)據(jù)流的精度

5、，介紹了一些提高數(shù)據(jù)流精度的方法，比如指針分析、變量別名分析等等。另外，本文在設(shè)計(jì)系統(tǒng)時(shí)，也對每個(gè)過程的相關(guān)信息進(jìn)行了統(tǒng)計(jì)，為用戶查詢模塊奠定了基礎(chǔ)。本文最后一章給出了系統(tǒng)的詳細(xì)設(shè)計(jì)，并對源程序進(jìn)行了測試，驗(yàn)證了算法的可行性，通過與以往研究的對比，說明了該方法的優(yōu)越性。關(guān)鍵詞：GCC 抽象語法樹；控制流分析；數(shù)據(jù)流分析；控制流圖；系統(tǒng)依賴圖I哈爾濱工業(yè)大學(xué)工學(xué)碩士學(xué)位論文AbstractIn this paper, system dependence graph on the C programming language isconstructed, which is the basis of

6、 static analysis tool and plays an important role in thereverse engineering. The construction of system dependence graph can be attributed tothe control flow analysis and data flow analysis. The control dependence relationshipamong statements is obtained by control flow analysis, which can be attrib

7、uted to obtainthe father-child relationship. The data dependence relationship among statements isobtained by data flow analysis, which can be attributed to obtain the global informationabout how a program defines, changes and uses data values.The method that how to construct the system dependence gr

8、aph based on theabstract syntax tree text is put forward. Firstly, the abstract syntax tree is studied, and themeaning of symbols in abstract syntax tree is obtained, which lays a good foundation forthe following study. Secondly, the abstract syntax tree text is standardized and theredundant informa

9、tion unrelated to the control flow analysis and data flow analysis iseliminated. Thirdly, the object-oriented thinking is introduced to extract the staticinformation. Finally, the traditional process is not followed when constructing the systemdependence graph. Control flow graph is constructed base

10、d on control dependence graphand data flow graph is constructed based on control flow graph. Also, the description ofspecific algorithm on every step is given, which includes our own algorithm and theimproved algorithm. In order to improve the accuracy of the data flow analysis, somemethods are intr

11、oduced, such as pointer analysis, alias analysis and so on. In addition, therelevant statistical information for each process is obtained, which lays a goodfoundation for the users query module.In the final chapter of this paper, the detailed design is given, and some examplesare tested to verify th

12、e feasibility of our algorithm. In addition, by contrast with theprevious studies, the result shows the superiority of this method.Keywords: GCC abstract syntax tree, control flow analysis, data flow analysis, controlflow graph, system dependence graphII哈爾濱工業(yè)大學(xué)工學(xué)碩士學(xué)位論文目錄摘要 . IAbstract . II第 1 章 緒論 .

13、 11.1 課題研究的背景與意義 . 11.2 基于程序語義分析方法的靜態(tài)分析工具國內(nèi)外研究現(xiàn)狀 . 21.2.1 程序缺陷檢測工具國內(nèi)外研究綜述 . 21.2.2 程序切片工具國內(nèi)外研究綜述 . 41.3 課題研究的主要內(nèi)容及章節(jié)安排 . 5第 2 章 課題相關(guān)的理論基礎(chǔ) . 72.1 GCC文本抽象語法樹 . 72.1.1 GCC抽象語法樹結(jié)構(gòu) . 72.1.2 GCC抽象語法樹分類及常見符號含義 . 82.2 控制流圖 . 82.2.1 控制流圖概述 . 82.2.2 語句的控制流圖描述 . 92.3 系統(tǒng)依賴圖SDG . 122.4 面向?qū)ο笙到y(tǒng)依賴圖及分層切片模型 . 132.5 標(biāo)

14、準(zhǔn)模板庫STL . 162.6 本章小結(jié) . 17第 3 章 程序靜態(tài)信息提取研究 . 183.1 抽象語法樹文本標(biāo)準(zhǔn)化 . 183.1.1 抽象語法樹文本標(biāo)準(zhǔn)化的原因 . 183.1.2 標(biāo)準(zhǔn)化抽象語法樹文本算法描述 . 183.2 消除抽象語法樹文本中的冗余信息 . 183.2.1 消除AST文本中冗余信息的原因. 183.2.2 消除AST文本中冗余信息算法描述. 193.3 基于面向?qū)ο蠹夹g(shù)的源程序靜態(tài)信息提取 . 203.3.1 采用面向?qū)ο蠹夹g(shù)的原因 . 203.3.2 對源程序設(shè)計(jì)語言的分類 . 213.3.3 類之間的調(diào)用關(guān)系 . 213.4 本章小結(jié) . 21第 4 章 程序

15、系統(tǒng)依賴圖生成方法研究 . 234.1 生成系統(tǒng)依賴圖的總體流程 . 234.2 預(yù)處理 . 244.2.1 確定語句范圍 . 244.2.2 switch語句標(biāo)準(zhǔn)化. 254.2.3 for語句標(biāo)準(zhǔn)化 . 26III哈爾濱工業(yè)大學(xué)工學(xué)碩士學(xué)位論文4.2.4 函數(shù)調(diào)用語句標(biāo)準(zhǔn)化 . 264.2.5 語句排序 . 284.3 控制依賴分析和控制依賴子圖生成 . 294.3.1 控制依賴子圖 . 294.3.2 跳轉(zhuǎn)語句的處理 . 304.4 控制流圖的生成 . 314.5 數(shù)據(jù)依賴分析和數(shù)據(jù)依賴子圖生成 . 314.5.1 到達(dá)定值信息相關(guān)概念 . 314.5.2 計(jì)算語句的REF、DEF 、G

16、EN和KILL集合 . 334.5.3 計(jì)算語句的IN、OUT集合. 364.5.4 建立數(shù)據(jù)依賴邊 . 374.5.5 計(jì)算過程間的數(shù)據(jù)流 . 374.5.6 指針分析 . 394.5.7 變量別名分析和數(shù)組變量分析 . 434.6 本章小結(jié) . 43第 5 章 系統(tǒng)實(shí)現(xiàn)及測試分析 . 445.1 系統(tǒng)總體設(shè)計(jì)與實(shí)現(xiàn) . 445.2 系統(tǒng)應(yīng)用環(huán)境 . 475.3 系統(tǒng)測試與分析 . 485.3.1 源程序 1 的測試與分析 . 485.3.2 源程序 2 的測試與分析 . 505.3.3 源程序 3 的測試與分析 . 535.3.4 實(shí)驗(yàn)結(jié)果對比分析 . 555.4 本章小結(jié) . 55結(jié)論

17、. 56參考文獻(xiàn) . 58攻讀學(xué)位期間發(fā)表的學(xué)術(shù)論文 . 61哈爾濱工業(yè)大學(xué)碩士學(xué)位論文原創(chuàng)性聲明 . 62哈爾濱工業(yè)大學(xué)碩士學(xué)位論文使用授權(quán)書 . 62致謝 . 63IV哈爾濱工業(yè)大學(xué)工學(xué)碩士學(xué)位論文第 1 章 緒論1.1 課題研究的背景與意義隨著軟件規(guī)模的擴(kuò)大，軟件的可靠性顯得越來越重要，對軟件進(jìn)行測試是保證軟件質(zhì)量的重要環(huán)節(jié)，由于在軟件的開發(fā)后期發(fā)現(xiàn)錯(cuò)誤進(jìn)行修改是早期發(fā)現(xiàn)錯(cuò)誤進(jìn)行修改所需成本的很多倍，因此在動態(tài)測試前對軟件進(jìn)行靜態(tài)測試可以盡早的發(fā)現(xiàn)軟件中的缺陷，提高產(chǎn)品的質(zhì)量，加快開發(fā)速度，減少軟件的開發(fā)成本。靜態(tài)分析主要包括代碼檢查、靜態(tài)結(jié)構(gòu)分析、代碼質(zhì)量度量等等，而軟件維護(hù)、程序分析

18、、逆向工程和轉(zhuǎn)換工具幾乎都依靠靜態(tài)源代碼分析作為基礎(chǔ)。因此，研究促進(jìn)程序理解的軟件工程方法和工具就顯得非常必要，逆向工程正是在這種需要下產(chǎn)生的軟件工程方法。逆向工程著眼于分析軟件并用抽象形式將其表現(xiàn)出來，使其便于理解。逆向工程可用于軟件維護(hù)、再工程、重用以及文檔化等許多用途。理解現(xiàn)有的軟件系統(tǒng)，一般需要靜態(tài)和動態(tài)兩方面的信息。靜態(tài)信息描述軟件在源代碼中的結(jié)構(gòu)，動態(tài)信息描述程序運(yùn)行期間的行為。靜態(tài)和動態(tài)分析的結(jié)果是對軟件組件及組件之間關(guān)系的信息描述。通過從目標(biāo)軟件還原設(shè)計(jì)模式可以幫助開發(fā)人員和維護(hù)人員進(jìn)行程序理解，這種逆向工程方法同樣適用于從高層設(shè)計(jì)信息構(gòu)造軟件，如正向工程。被抽取的靜態(tài)模型可以

19、用于保證體系結(jié)構(gòu)嚴(yán)格按照方案進(jìn)行以及獲得軟件當(dāng)前階段的整個(gè)視圖，而動態(tài)模型則可以用于支持調(diào)試，找出錯(cuò)誤代碼，以及理解軟件當(dāng)前行為。源程序靜態(tài)信息提取需要對源程序進(jìn)行編譯，但是不需要運(yùn)行。需要經(jīng)過詞法分析、語法分析的過程，這就要要有針對源程序語言的詞法分析器、語法分析器和相應(yīng)的輸出信息接口。對源程序進(jìn)行靜態(tài)信息提取主要有以下兩種方式：(1)直接編寫針對源程序語言的詞法分析器、語法分析器，對源程序進(jìn)行靜態(tài)分析，得到源程序的靜態(tài)信息；(2)利用開源編譯器GCC(GNU Compiler Collection)或者詞法分析器LEX(Lexical Compiler)和語法分析器YACC(Yet Ano

20、ther Compiler Compiler)或者語言識別工具ANTLR(Another Tool for Language Recognition)1達(dá)到對源程序進(jìn)行信息提取的目的。對于第一種方式，這類靜態(tài)分析器使用語法制導(dǎo)分析源代碼，特點(diǎn)是語法識別準(zhǔn)確，提取的源代碼信息比較準(zhǔn)確，編寫靜態(tài)信息輸出接口也有利于實(shí)現(xiàn)交互，但是由于語言描述比較復(fù)雜，實(shí)現(xiàn)難度比較大。對于第二種方式，YACC生成的編譯器主要是用 C語言寫成的語法分析器 (Parser)，需要與詞法分析器 LEX一起使-1-哈爾濱工業(yè)大學(xué)工學(xué)碩士學(xué)位論文用，再把兩部分產(chǎn)生出來的 C程序一并編譯。語言識別工具ANTLR可以接受文法語言描

21、述，并產(chǎn)生識別這些語言的語句的程序，作為翻譯程序的一部分，可以使用簡單的操作符和動作來參數(shù)化文法，告訴它如何去創(chuàng)建抽象語法樹和如何產(chǎn)生輸出，但是這種工具主要是針對JAVA,C+,C#和Python語言的。如果利用GCC編譯器的話，可以修改GCC編譯器前端的源碼，添加靜態(tài)信息輸出接口，以便輸出源程序的靜態(tài)信息；或者利用其產(chǎn)生的抽象語法樹AST(Abstract Syntax Tree)層或者寄存器存儲轉(zhuǎn)換語言RTL(Register Transfer Language)中間文件，提取源程序的靜態(tài)信息。然而GCC源代碼規(guī)模龐大，結(jié)構(gòu)關(guān)系復(fù)雜，因此直接修改GCC前端的源碼不太現(xiàn)實(shí)。另外，由于RTL文

22、件中含有大量編譯器后端的信息，而這部分信息對源程序結(jié)構(gòu)分析所需提取的信息來說含有大量冗余的信息，并且程序間的結(jié)構(gòu)不清晰。所以，本文給出一種基于GCC的AST中間文件提取源程序靜態(tài)信息的方法。目前解析GCC產(chǎn)生的抽象語法樹文本是一個(gè)相對比較新的研究課題。國內(nèi)外對GCC抽象語法樹解析研究比較晚，最早的文獻(xiàn)是2002年的James F. Power的文章2，AST文本解析方法可分為兩種：一是通過編譯的方法構(gòu)造分析器對抽象語法樹文本進(jìn)行解析3，在分析抽象語法樹結(jié)構(gòu)的基礎(chǔ)上，把文本抽象語法樹當(dāng)作一種特殊的語言來識別，構(gòu)造相應(yīng)的詞法規(guī)則和語法規(guī)則，使用flex和bison工具4生成的解析器能夠有效地對抽象

23、語法樹進(jìn)行解析；二是基于XML或是GXL的解析方法5-8，這種解析方法相對多一些，因?yàn)閄ML是一種很通用的信息格式，現(xiàn)有的對XML文檔進(jìn)行解析的工具很多也非常成熟。將文本抽象語法樹轉(zhuǎn)換為XML文檔，再由XML文檔解析器構(gòu)造出具有某種存儲結(jié)構(gòu)的抽象語法樹。1.2 基于程序語義分析方法的靜態(tài)分析工具國內(nèi)外研究現(xiàn)狀1.2.1 程序缺陷檢測工具國內(nèi)外研究綜述靜態(tài)分析工具根據(jù)軟件的結(jié)構(gòu)、內(nèi)容或文檔來評價(jià)軟件系統(tǒng)，而不需要執(zhí)行程序。因此可以較早地發(fā)現(xiàn)程序代碼中的缺陷，這使得后面的軟件開發(fā)階段可以著重分析復(fù)雜功能以及算法的錯(cuò)誤。靜態(tài)分析工具可以在軟件工程人員審查、測試之前查找軟件中的缺陷,也可結(jié)合到整個(gè)軟件

24、開發(fā)過程中。靜態(tài)分析工具可以自動識別特定的軟件缺陷，通常采用的方法是掃描并分析程序的源代碼來查找代碼中特定模式集合。其中最大的優(yōu)點(diǎn)在于：它們不必執(zhí)行目標(biāo)程序就可以推論出可應(yīng)用于所有可能執(zhí)行路徑上的結(jié)果。按照采用的分析技術(shù)的不同可以分為四類：第一類主要是基于字符串匹配技術(shù) 它把注釋、字符、聲明以及函數(shù)調(diào)用都當(dāng)作字符流進(jìn)行匹配，不能理解所掃描的文件，準(zhǔn)確率很低；第二類靜態(tài)分析工具采用了基本的詞法分析方法 它們將源文件預(yù)處理為Token流，然后將-2-哈爾濱工業(yè)大學(xué)工學(xué)碩士學(xué)位論文Token流與庫中的缺陷結(jié)構(gòu)進(jìn)行匹配。盡管詞法分析工具有了很大的進(jìn)步,但它們?nèi)匀粵]有考慮源代碼的語義，不能理解程序的執(zhí)行

25、行為，因此誤檢率仍然很高；第三類靜態(tài)分析工具采用了程序語義分析方法。這些工具通過分析程序的控制流和數(shù)據(jù)流，以及函數(shù)調(diào)用關(guān)系等考慮程序的基本語義。這些工具大多專用于檢查特定的缺陷；第四類靜態(tài)分析工具將數(shù)據(jù)挖掘技術(shù)與程序分析相結(jié)合。不需要預(yù)先定義模式或規(guī)則,而用數(shù)據(jù)挖掘方法挖掘編程模式。例如CPMiner9使用數(shù)據(jù)挖掘技術(shù)識別大型軟件中的拷貝- 粘貼代碼,并檢測與拷貝- 粘貼代碼相關(guān)的軟件缺陷；PRMiner10使用頻繁項(xiàng)集合挖掘來抽取軟件代碼中隱含的編程規(guī)則。下面重點(diǎn)介紹一下基于程序語義分析方法的靜態(tài)分析工具：(1)BOON11 應(yīng)用整數(shù)范圍分析,確定C程序中是否有數(shù)組越界。盡管它能檢測到很多詞

26、法工具檢測不到的缺陷,但沒有考慮語句順序和指針別名,也不能對過程間依賴進(jìn)行建模。(2)CQual12 使用類型驗(yàn)證檢查類型標(biāo)識符,可以檢查C程序中字符串使用缺陷和鎖缺陷,它需要程序員對一些變量進(jìn)行注釋。(3)xg+13 使用模板驅(qū)動的編譯器擴(kuò)展來查找Linux與OpenBSD內(nèi)核的缺陷,可以檢測沒有釋放動態(tài)分配的內(nèi)存、內(nèi)核死鎖等缺陷。(4)MOPS14 采用模型檢查方法,查找與安全屬性相關(guān)的缺陷,如優(yōu)先級管理錯(cuò)誤、文件訪問競爭等。(5)Splint15 用程序員提供的注釋輔助程序分析。可以查找使用未初始化的變量、數(shù)組下標(biāo)越界等缺陷。(6)FindBug16,17 使用缺陷模式檢查器,檢查Jav

27、a程序中的缺陷,如空指針異常、死鎖、線程問題等。(7)PREfix18 基于程序調(diào)用圖進(jìn)行分析,通過分析程序中很多路徑,跟蹤變量和內(nèi)存狀態(tài),查找C與C+程序中常見的動態(tài)錯(cuò)誤。PREfast是PRE2fix工具的一個(gè)”fast”版本,有些PREfast的分析基于C/C+程序的抽象模式匹配來查找簡單的編程錯(cuò)誤。PREfast/PREfix可以用于檢測未初始化的變量、空指針脫引用、使用未初始化的內(nèi)存、重復(fù)釋放資源等缺陷。(8)SLAM19 將程序抽象成布爾程序,并研究它的可達(dá)狀態(tài)。如果布爾程序到達(dá)了一個(gè)錯(cuò)誤狀態(tài)。則可能是一個(gè)不可行的路徑,在這種情況下,重新分析布爾程序。SLAM被用于查找Window

28、s驅(qū)動程序中缺陷。(9)Flexelint (www. gimpel. com /html/products.htm) 檢查C/C+源代碼中的錯(cuò)誤、不一致性、不可移植的常量以及冗余代碼等。(10)Reasonings Illuma (www. reasoning. com) 可以查找C/C+應(yīng)用中的缺陷。代-3-哈爾濱工業(yè)大學(xué)工學(xué)碩士學(xué)位論文碼發(fā)送到Rea2soning，Reasoning執(zhí)行靜態(tài)分析,消除虛假報(bào)警并生成報(bào)告。Illuma識別可導(dǎo)致應(yīng)用程序崩潰的可靠性缺陷,包括空指針脫引用、數(shù)組訪問越界、內(nèi)存泄露、錯(cuò)誤的再分配以及未初始化的變量。(11)Klocwork () 有 兩 個(gè) 靜

29、態(tài) 分 析 工 具 ， 即 inForce 與GateKeeper。inForce分析工具執(zhí)行源代碼靜態(tài)分析來識別潛在的缺陷和安全漏洞。Gate2Keeper分析工具分析了源代碼體系結(jié)構(gòu)的優(yōu)點(diǎn)與缺點(diǎn)并評價(jià)代碼質(zhì)量、缺陷和維護(hù)開銷。缺陷類型包括模塊間的關(guān)系、代碼聚合、高風(fēng)險(xiǎn)的代碼文件與函數(shù)的邏輯錯(cuò)誤等。(12)CodeSurfer20 計(jì)算很多種程序的語義表示,如調(diào)用圖和依賴圖,來輔助軟件審查。整個(gè)程序的指針分析確保了指針別名分析的表示是準(zhǔn)確的。在依賴圖上進(jìn)行查詢使得審查者能夠回答程序的語義問題。通過對程序進(jìn)行模型檢查,可以查找軟件缺陷。但它的缺點(diǎn)是創(chuàng)建依賴圖的開銷太大,不適合應(yīng)用于大型程序。(

30、13)PGRelief21 是南京大學(xué)與日本富士通公司合作開發(fā)的自動靜態(tài)分析系統(tǒng)。通過靜態(tài)分析用C/C+語言編寫的源程序及頭文件,尋找程序的潛在缺陷,并統(tǒng)計(jì)程序的復(fù)雜度和規(guī)模。分析的缺陷包括潛在的邏輯錯(cuò)誤(信賴性缺陷)、設(shè)計(jì)艱澀以至妨礙程序理解的缺陷(維護(hù)性缺陷)、因?yàn)榫幾g器的不同而可能有不同解釋的缺陷(移植性缺陷)、有可能增加程序目標(biāo)代碼規(guī)模和執(zhí)行步驟的缺陷(效率性缺陷)等。對程序語義分析方法進(jìn)行研究的還有我國的合肥工業(yè)大學(xué)22、西安電子科技大學(xué)23-25等。1.2.2 程序切片工具國內(nèi)外研究綜述程序切片是由M.Weiser 1979年在他的博士論文26中優(yōu)先建立起來的一種程序分析技術(shù)，19

31、84年，M.Weiser在IEEE Transations on Software Engineering上進(jìn)一步闡述了程序切片技術(shù)的思想27。程序切片技術(shù)在軟件分析、理解、調(diào)試、測試、度量、軟件質(zhì)量保證、逆向工程等許多方面有著廣泛的應(yīng)用。在軟件調(diào)試過程中，定位程序中存在的錯(cuò)誤是一項(xiàng)困難的工作，程序切片可以幫助程序員很容易地進(jìn)行錯(cuò)誤定位。軟件維護(hù)是軟件生命周期的重要組成部分，其個(gè)占整個(gè)系統(tǒng)費(fèi)用的一半及以上。軟件維護(hù)的主要挑戰(zhàn)來自對現(xiàn)實(shí)對現(xiàn)有系統(tǒng)的理解和確保修改系統(tǒng)不會引發(fā)新的錯(cuò)誤，分解切片捕獲與程序中某個(gè)變量在所有計(jì)算位置的值的相關(guān)的程序信息，將對程序的修改引起的影響控制在一定的范圍內(nèi)。當(dāng)軟件

32、系統(tǒng)修改后，為了保證系統(tǒng)的正確性以及修改不會帶來副作用，需要對其進(jìn)行重新測試，即回歸測試。只有那些受影響的代碼需要重新測試，通過程序切片技術(shù)可以避免完全重新測試。實(shí)際上，程序切片的應(yīng)用非常廣泛，在軟件開發(fā)的各個(gè)階段都可以發(fā)揮程序切片的巨大作-4-哈爾濱工業(yè)大學(xué)工學(xué)碩士學(xué)位論文用。在程序分析中引入基于系統(tǒng)依賴圖和圖形可達(dá)性的程序切片方法，可以降低程序分析的復(fù)雜度?？刂埔蕾囆畔⒔y(tǒng)計(jì)謂詞語句(條件語句和循環(huán)語句)對程序行為的影響，數(shù)據(jù)依賴信息統(tǒng)計(jì)數(shù)據(jù)交互行為對程序行為的影響。程序切片就是使用SDG的控制依賴信息和數(shù)據(jù)依賴信息來搜集在語義上影響一條語句的所有語句的集合。目前，實(shí)用的程序切片工具和環(huán)境很

33、多，按照切片對象的程序設(shè)計(jì)語言的不同可以分為以下幾類：(1)支持C語言的PST Wisconsion程序切片工具Version1.1是一個(gè)支持對C程序操作操作的軟件系統(tǒng)。它包括后向切片、前向切片和消片三種功能，它們能幫助用戶獲得對一個(gè)程序正在做什么和如何做的理解。ChopShop是由Carnegie Mellon大學(xué)的計(jì)算機(jī)科學(xué)學(xué)院最初開發(fā)的一種逆向工程工具，可以用來幫助程序員理解不熟悉的C代碼，它接受完全的ANSI，以文本和圖形兩種形式產(chǎn)生程序切片，并進(jìn)行化名分析、處理所有的語言特性，它是第一個(gè)為過程提供數(shù)據(jù)抽象機(jī)制的程序切片工具。Chinsu是Florida大學(xué)計(jì)算機(jī)和信息科學(xué)系開發(fā)，受到

34、軟件工程研究中心(SERC)基金資助的一個(gè)集成了許多工具的程序切片環(huán)境，可以在軟件工程的許多活動中，主要是維護(hù)活動過程中期輔助作用。Unravel是一個(gè)原型程序切片工具，可以用來使用程序切片靜態(tài)的估計(jì)ANSI C源代碼。(2)支持Ada語言的PST PSS/Ada系統(tǒng)是由楊洪等人設(shè)計(jì)的一個(gè)Ada程序的靜態(tài)切片生成原型系統(tǒng)，它是一個(gè)Ada軟件測試、排錯(cuò)、分析、理解和維護(hù)工具，在Ada程序的并行性檢查、波動性分析、復(fù)雜性度量等方面也提供一定范圍的支持。(3)支持Java語言的PST Indus是美國勘薩州州立大學(xué)的V.P.Ranganath小組開發(fā)一個(gè)比較完整的Java程序切片工具。(4)其他PS

35、T CodeSurfer是以一種新的方式來分析、理解和瀏覽源代碼，它是一個(gè)具有突破性的軟件開發(fā)和維護(hù)工具，工程師用來瀏覽和理解源代碼中詳細(xì)的依賴關(guān)系。它提供了一種相對比較便利的訪問程序深層結(jié)構(gòu)的方法，即通過全局程序分析發(fā)現(xiàn)語義特性和關(guān)系。1.3 課題研究的主要內(nèi)容及章節(jié)安排論文中主要涉及到的理論方面的研究有：(1)分析源程序調(diào)用GCC編譯器生成的抽象語法樹文本的結(jié)構(gòu)。(2)消除抽象語法樹文本中的有助于編譯的細(xì)節(jié)信息，提取出與源程序結(jié)構(gòu)相關(guān)的信息。(3)如何結(jié)合面向?qū)ο笏枷氚殉绦蛟O(shè)計(jì)語言正確分類，涵蓋程序設(shè)計(jì)語言中的所-5-哈爾濱工業(yè)大學(xué)工學(xué)碩士學(xué)位論文有語句，表達(dá)式及變量，保證信息提取的完整性

36、。(4)如何建立標(biāo)準(zhǔn)的控制依賴圖，正確的表示語句之間的控制依賴關(guān)系。(5)如何建立標(biāo)準(zhǔn)的數(shù)據(jù)流圖，正確的表示語句之間的數(shù)據(jù)依賴關(guān)系。(6)如何保證源程序結(jié)構(gòu)信息輸出的規(guī)范性。(7)是否能在系統(tǒng)依賴圖的基礎(chǔ)上擴(kuò)展來表示C+面向?qū)ο笳Z言。(8)該研究的主要應(yīng)用。本文共分為5個(gè)部分：第1章主要介紹了課題研究背景和意義，介紹了基于GCC抽象語法樹文本解析源程序的國內(nèi)外現(xiàn)狀，并介紹了基于程序語義分析方法的程序缺陷檢測工具和程序切片工具在國內(nèi)外的研究現(xiàn)狀。第2章主要介紹了和課題相關(guān)的一些理論基礎(chǔ)，GCC抽象語法樹結(jié)構(gòu)、控制流圖等等，并延伸了SDG，介紹了面向?qū)ο蟮南到y(tǒng)依賴圖OOSDG。第3章主要介紹了基于

37、GCC抽象語法樹文本的源程序靜態(tài)信息提取方法。第4章主要介紹了基于GCC抽象語法樹解析的程序系統(tǒng)依賴圖生成方法。第5章主要介紹了系統(tǒng)的詳細(xì)設(shè)計(jì)和測試結(jié)果分析。-6-哈爾濱工業(yè)大學(xué)工學(xué)碩士學(xué)位論文第 2 章 課題相關(guān)的理論基礎(chǔ)2.1 GCC 文本抽象語法樹2.1.1 GCC 抽象語法樹結(jié)構(gòu)GCC編譯系統(tǒng)是由美國自由軟件基金會(Free Software Foundation)開發(fā)，可以編譯多種程序設(shè)計(jì)語言，支持多平臺編譯的編譯程序集合，是Linux/Unix下最穩(wěn)定和成熟的編譯器。GCC編譯系統(tǒng)主要由三部分組成：與程序設(shè)計(jì)語言相關(guān)的前端、與程序設(shè)計(jì)語言無關(guān)的后端和與機(jī)器相關(guān)的機(jī)器描述部分。為了支

38、持多平臺編譯，GCC前端需要一種中間表示，能夠向上支撐多種程序設(shè)計(jì)語言到中間代碼的映射，向下支持跨平臺代碼轉(zhuǎn)換并且適合在多種平臺下進(jìn)行優(yōu)化。為此GCC編譯系統(tǒng)使用兩個(gè)層次的中間表示，分別為抽象語法樹AST層和寄存器轉(zhuǎn)移語言RTL層。抽象語法樹作為一種通用的中間表示，不僅包含各種語言共有的語法結(jié)構(gòu)，某些特定類型的樹結(jié)點(diǎn)還可以表示一些語言特有的語法結(jié)構(gòu)。抽象語法樹易于轉(zhuǎn)換成寄存器轉(zhuǎn)移語言，而寄存器轉(zhuǎn)移語言適合在不同平臺下進(jìn)行優(yōu)化，這使得GCC的兩層中間表示具有良好的通用性。AST是程序的一種中間表示形式。GCC編譯系統(tǒng)以程序的過程為單位生成抽象語法樹，抽象語法樹與過程一一對應(yīng)。AST能夠包含整個(gè)編譯單元的完整表示，比較直觀的表示出源程序