支持多程序語言的靜態(tài)信息提取方法

逄 龍，王甜甜，蘇小紅，馬培軍

(哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，150001哈爾濱，hitpanglong@163.com)

代碼靜態(tài)分析已經(jīng)廣泛應(yīng)用于程序理解、軟件缺陷檢測、程序驗(yàn)證等方面.靜態(tài)信息提取是代碼靜態(tài)分析的基礎(chǔ)，是將代碼文本轉(zhuǎn)換為可分析處理的中間邏輯表示結(jié)構(gòu)的過程，其所支持解析的程序語言種類、生成的中間表示的表達(dá)能力都極大影響靜態(tài)代碼分析的應(yīng)用范圍.當(dāng)前主要采用的方法為:1)Yacc類語法生成解析器［1-2］.該方法語言適應(yīng)能力強(qiáng)，但后續(xù)語法的消歧和調(diào)試開銷大，中間表示結(jié)果單一;2)專用前端解析，如CIL，Clang等［3-4］，文檔完整，但支持語言單一，需其他預(yù)處理工具支持，中間表示單一;3)對編譯器擴(kuò)展［5-6］，應(yīng)用便捷，但對編譯器內(nèi)部已有功能重用率低，執(zhí)行效率不高;4)解析編譯器中間調(diào)試文件，重構(gòu)中間表示［7-10］，支持多種語言，但實(shí)現(xiàn)復(fù)雜，后續(xù)測試開銷大.

為了支持多語言解析，并提供統(tǒng)一且具備不同表達(dá)能力的中間表示，滿足健壯性和穩(wěn)定性的要求，通過在代碼級別改造開源GCC編譯器來實(shí)現(xiàn)靜態(tài)信息的提取.該編譯器應(yīng)用廣泛、成熟可靠，所以在此基礎(chǔ)上改造可以降低后續(xù)分析程序的復(fù)雜度，但這種方法的主要難點(diǎn)是代碼規(guī)模較大、整體復(fù)雜、文檔不完整、代碼的設(shè)計(jì)目標(biāo)與靜態(tài)分析的目標(biāo)不同，因而需要針對靜態(tài)分析的目標(biāo)在代碼級別對其進(jìn)行修改.本文首先對靜態(tài)信息所依賴的GCC源代碼內(nèi)部運(yùn)行過程和相關(guān)機(jī)制進(jìn)行分析，然后針對類型和函數(shù)聲明定義、函數(shù)體內(nèi)語句遍歷和中間表示訪問等靜態(tài)信息，在GCC編譯器的不同階段提出了運(yùn)行改入點(diǎn)和內(nèi)部輔助函數(shù)相結(jié)合的提取方法，并給出整體的修改、應(yīng)用流程，最后通過提取典型靜態(tài)信息的對比實(shí)驗(yàn)，表明該方法提高了執(zhí)行效率，增強(qiáng)了靜態(tài)信息提取的可靠性.

1 與靜態(tài)信息提取相關(guān)的GCC源代碼分析

GCC-4.3.0編譯器整體結(jié)構(gòu)如圖1所示.整體劃分為3層:前端解析源代碼、中端負(fù)責(zé)機(jī)器無關(guān)的優(yōu)化和后端負(fù)責(zé)目標(biāo)機(jī)器相關(guān)的優(yōu)化和變換.源代碼在前端生成原始中間表示后，通過后續(xù)的層間流轉(zhuǎn)、層內(nèi)變換和處理，最終生成目標(biāo)代碼.本文主要針對與靜態(tài)信息提取相關(guān)的前端、中端和涉及的中間表示進(jìn)行分析.

圖1 GCC編譯器結(jié)構(gòu)框圖

1.1 整體流程

編譯器GCC開始執(zhí)行后，針對編譯對象的不同程序語言，調(diào)用對應(yīng)語言前端解析，將該編程語言源代碼文本解釋為與語言相關(guān)的抽象語法樹形式的中間表示.經(jīng)前端genericize函數(shù)去除語言相關(guān)性的節(jié)點(diǎn)，轉(zhuǎn)換為Generic形式或直接為Gimple形式，輸入中端進(jìn)行優(yōu)化處理.中端優(yōu)化包括與目標(biāo)機(jī)器無關(guān)的過程間和過程內(nèi)優(yōu)化.調(diào)用圖管理器負(fù)責(zé)維護(hù)中間表示的過程間調(diào)用結(jié)構(gòu)邏輯關(guān)系，用以管理過程間優(yōu)化處理的中間結(jié)果，遍管理器負(fù)責(zé)維護(hù)編譯器內(nèi)對中間表示進(jìn)行優(yōu)化處理的各步驟定義、依賴關(guān)系和調(diào)用順序，用以指導(dǎo)優(yōu)化處理次序.

1.2 中間表示

GCC內(nèi)部中間表示是各層間流轉(zhuǎn)和層內(nèi)處理對象的重要數(shù)據(jù)結(jié)構(gòu)，根據(jù)不同處理階段轉(zhuǎn)換為特定形式，同時也是靜態(tài)信息提取的直接來源，所蘊(yùn)含靜態(tài)信息的質(zhì)量和結(jié)構(gòu)組織的復(fù)雜性決定著靜態(tài)信息提取方法的質(zhì)量和效率.GCC前端和中端主要采用抽象語法樹、Generic、Gimple和SSA這4種形式中間表示.

抽象語法樹是經(jīng)過解析源代碼文本后得到與之直接對應(yīng)的邏輯結(jié)構(gòu)，與語言相關(guān).Generic形式是對抽象語法樹的簡化，統(tǒng)一語句結(jié)構(gòu)，去除語言的相關(guān)性，包含副作用(Side Effect).Gimple形式是在Generic形式的基礎(chǔ)上限制每條語句的操作數(shù)＜3的一種約簡，簡化了復(fù)雜表達(dá)式結(jié)構(gòu)，引入中間臨時變量.SSA形式是在Gimple基礎(chǔ)上增加數(shù)據(jù)流信息的一種中間表示，在每次賦值時，對左邊變量都增加序號加以辨別，而且后續(xù)讀取該變量的表達(dá)式直接指向該變量序號的定義處.SSA和Gimple均適合作為靜態(tài)信息提取的中間表示.

1.3 遍(Pass)

在GCC優(yōu)化中，對編譯單元(函數(shù)或文件)的一次遍歷處理，稱為遍(Pass).GCC“遍管理器”是對遍定義、組織和執(zhí)行而實(shí)施管理的一組機(jī)制.根據(jù)靜態(tài)信息種類，提取過程可抽象為遍，通過在合適的步驟后對合適的中間表示遍歷來實(shí)現(xiàn)，這樣可以重用GCC內(nèi)部已經(jīng)提供的通用功能和信息，如冗余代碼去除、控制流圖、數(shù)據(jù)依賴等.GCC通過遍來關(guān)聯(lián)中端和后端內(nèi)具體的優(yōu)化處理步驟，遍的機(jī)制分為3個部分:遍的定義、遍的組織和遍的執(zhí)行.

2 靜態(tài)信息提取

在分析與靜態(tài)信息提取相關(guān)的GCC內(nèi)部代碼組織機(jī)制的基礎(chǔ)上，根據(jù)信息來源，給出確切的改入點(diǎn)，結(jié)合內(nèi)部輔助函數(shù)從獲得的中間表示中提取所需信息.核心思想是在GCC運(yùn)行過程中，在合適的位置得到合適的中間表示，使用合適的方法提取靜態(tài)信息.

2.1 改入點(diǎn)

改入點(diǎn)是修改GCC源代碼的位置，因?yàn)椴煌娜朦c(diǎn)會獲得不同中間表示，如圖2所示.

1)遍改入點(diǎn).通過GCC內(nèi)部遍機(jī)制，以遍歷函數(shù)體內(nèi)語句方式來提取靜態(tài)信息.因?yàn)楸楣芾砥魈幱诰幾g器中端和后端部分，獲得語言無關(guān)的中間表示，所以遍改入點(diǎn)可直接應(yīng)用于編譯器所支持語言.根據(jù)所需提取靜態(tài)信息種類和GCC已定義遍所提供的不同中間表示，在適當(dāng)類型的遍中適當(dāng)順序位置處加入自定義遍.在圖2中0處 init-optimization-passes，初始化遍組織關(guān)系:低級化遍(all-lowering-passes)、過程遍(all-ipa-passes)和所有遍(all-passes).

圖2 GCC 中語言前端和統(tǒng)一中端調(diào)用圖

為獲得Gimple形式中間表示，在低級化遍中的pass-build-cfg遍后增加自定義遍.為獲得數(shù)據(jù)流相關(guān)的中間表示，在過程間遍中的pass-earlywarn-uninitialized遍后增加改入點(diǎn).其中:passbuild-cfg遍已經(jīng)建立了過程內(nèi)控制流圖和基本塊，通過遍歷程序基本塊間關(guān)系和塊內(nèi)語句可獲得初步的Gimple格式的統(tǒng)一中間表示;pass-remove-useless-stmts遍去除無用冗余的語句;passearly-warn-uninitialized遍檢測使用未初始化變量情況;pass-build-ssa遍建立了SSA的中間表示，通過遍歷定義-使用鏈獲得數(shù)據(jù)流相關(guān)信息.

調(diào)用改入點(diǎn)是GCC調(diào)用內(nèi)部遍的位置，可根據(jù)需要調(diào)整具體調(diào)用次序.在圖2中，獲取Gimple的自定義遍從屬于低級化遍，在5處調(diào)用.獲取SSA的自定義遍從屬于過程間遍的第2層子遍pass-early-local-passes，在6處和8處調(diào)用.所有遍在7處調(diào)用.

2)解析相關(guān)改入點(diǎn).通過GCC前端解析提取語言相關(guān)靜態(tài)信息.

復(fù)合類型改入點(diǎn)為獲得結(jié)構(gòu)體、聯(lián)合體和類的類型定義相關(guān)靜態(tài)信息.在聲明與函數(shù)定義翻譯單元加入改入點(diǎn).在C語言前端的c-parserstruct-or-union-specifier函數(shù)內(nèi)1 979行處增加改入點(diǎn)，該處獲得的是解析出的類型定義，如圖2中2所示.在C++語言前端(cp/Class.c)的finish-struct-1函數(shù)返回前增加改入點(diǎn)，以獲得類定義中的域相關(guān)靜態(tài)信息.

標(biāo)識符改入點(diǎn)為獲得全局變量相關(guān)靜態(tài)信息.GCC的標(biāo)識(Identity，ID)為3類:位置標(biāo)簽、復(fù)合類型名和和其他ID.ID通過struct c-binding與具體中間表示關(guān)聯(lián)，以作用域(struct c-scope類型)為集合通過鏈表方式存儲.在關(guān)聯(lián)函數(shù)bind內(nèi)加入改入點(diǎn)，如圖2中3所示.

原始中間表示改入點(diǎn)為獲得抽象語法樹等靜態(tài)信息.GCC通過lang-hooks類型定義各語言解析、后端處理等入口函數(shù).C語言中，在c-genericize函數(shù)中，加入改入點(diǎn)，如圖2中4所示，獲得原始抽象語法樹中間表示.C++語言中，在cp/ decl.c的finish-function中調(diào)用cp-genericize函數(shù)前增加改入點(diǎn)，獲得原始抽象語法樹中間表示.

3)輔助改入點(diǎn).為后續(xù)分析處理傳遞提取的靜態(tài)信息，在翻譯單元編譯開始前和結(jié)束后進(jìn)行必要的初始化和終結(jié)工作，在調(diào)用語言類函數(shù)指針前和之后增加改入點(diǎn)，如圖2中1和9處所示.此處可以負(fù)責(zé)處理文件描述符、過程間通訊和數(shù)據(jù)庫操作等與外界交換信息的建立與消解，還可以設(shè)置初始化環(huán)境等.

2.2 輔助函數(shù)

輔助函數(shù)是在特定改入點(diǎn)獲得對應(yīng)中間表示后，根據(jù)靜態(tài)信息種類和GCC代碼內(nèi)部組織機(jī)制，來提取所需靜態(tài)信息的具體方法.

1)位集合操作.數(shù)據(jù)流分析經(jīng)常使用集合操作，GCC內(nèi)部實(shí)現(xiàn)了集合相關(guān)操作運(yùn)算的抽象數(shù)據(jù)類型sbitmap，定義包含在Sbitmap.h內(nèi);提供基于位內(nèi)部表示和相關(guān)操作，初始化與可變長度調(diào)整:sbitmap-alloc、sbitmap-resize;集合運(yùn)算操作: sbitmap-difference、sbitmap-not;向量位集操作: sbitmap-vector-alloc;位集合設(shè)置內(nèi)聯(lián)函數(shù):SETBIT、sbitmap-iter-init等.

2)輔助信息遍歷.輔助信息包括控制流圖和數(shù)據(jù)流信息.低級化遍中建立控制流圖，在所有遍生成的SSA中間表示蘊(yùn)含數(shù)據(jù)流信息.struct basic-block-def和struct edge-def定義了基本塊和邊.以ENTRY-BLOCK-PTR宏獲得入口基本塊開始，以FOR-EACH-BB宏基本塊間流轉(zhuǎn)，實(shí)現(xiàn)基本塊遍歷.在基本塊內(nèi)，bsi-start獲得塊內(nèi)首語句，bsi-next獲得下一條語句和bsi-end-p判定塊內(nèi)語句結(jié)束與否來實(shí)現(xiàn)基本塊內(nèi)語句遍歷. walk-use-def-chains函數(shù)遍歷數(shù)據(jù)流信息.

圖3 修改GCC源代碼提取靜態(tài)信息過程圖

3)表達(dá)式遍歷.遍歷表達(dá)式中的操作數(shù)來提取變量訪問.walk-tree函數(shù)遍歷抽象語法樹表達(dá)式;walk-stmts函數(shù)遍歷Gimple形式表達(dá)式，提供了賦值表達(dá)式中區(qū)別左邊和右邊表達(dá)式的標(biāo)志.FOR-EACH-SSA-TREE-OPERAND配合類型標(biāo)志位組合遍歷SSA操作數(shù).

4)中間表示節(jié)點(diǎn)訪問.抽象數(shù)據(jù)類型tree統(tǒng)一表達(dá)各種中間表示，提供了對應(yīng)訪問函數(shù). TREE-CODE宏獲得節(jié)點(diǎn)種類;TREE-OPERAND獲得節(jié)點(diǎn)下指定操作數(shù);針對COMPONENT-REF類型節(jié)點(diǎn)，DECL-CONTEXT獲得其域變量所屬類型;TYPE-NAME獲得變量的類型節(jié)點(diǎn); DECL-NAME獲得類型節(jié)點(diǎn)名稱，如在C語言中typedef定義的類型名稱;IDENTIFIER-POINTER獲得具體ID字符串;TYPE-FIELDS獲得結(jié)構(gòu)體或聯(lián)合體內(nèi)域的列表.

2.3 其他相關(guān)修改

在特定修改點(diǎn)利用輔助函數(shù)獲取了所需的靜態(tài)信息后，需要通過修改配置文件實(shí)現(xiàn)與GCC的整合.修改GCC源代碼提取靜態(tài)信息的整體過程如圖3所示.

1)控制選項(xiàng)配置修改.是外部調(diào)用GCC可設(shè)置的參數(shù)，通過添加與控制靜態(tài)信息提取相關(guān)選項(xiàng)來控制是否運(yùn)行.為便于控制，利用增加common.opt文件中選項(xiàng)定義記錄的方式來控制是否運(yùn)行靜態(tài)信息提取.

2)工程配置修改.將自定義的文件通過編譯、鏈接整合到GCC.首先增加生成該源代碼文件的目標(biāo)文件的依賴關(guān)系，然后將此目標(biāo)文件加入OBJS-common所依賴列表中實(shí)現(xiàn)整合.

3 結(jié)果與分析

為了驗(yàn)證本文所提出方法的有效性、效率和健壯性，在2.6 GHz主頻CPU、2 GB內(nèi)存和Ubuntu 9.10操作系統(tǒng)的測試環(huán)境下，分別按本文方法和CIL方法，提取結(jié)構(gòu)體域變量讀、寫和函數(shù)訪問等靜態(tài)信息，應(yīng)用于5個開源軟件進(jìn)行測試，測試結(jié)果如表1所示.其中通過UCC統(tǒng)計(jì)代碼規(guī)模，Linux系統(tǒng)指令time統(tǒng)計(jì)運(yùn)行時間.

表1 實(shí)驗(yàn)結(jié)果對比表

如表1所示，由于本文方法是在GCC源碼級上修改，所以繼承了GCC特點(diǎn)，在支持語言、耗時和錯誤數(shù)方面優(yōu)于CIL方法.CIL方法由于對擴(kuò)展語法支持不完備而發(fā)生的錯誤有:openssh中對64位整數(shù)常量不能識別;gtk中可變參數(shù)無法定義別名屬性.由于GCC對Java擴(kuò)展庫實(shí)現(xiàn)不完整，導(dǎo)致本文方法提取tomcat時部分依賴于此的文件無法編譯，但可以利用Open Java對應(yīng)庫文件替換予以解決.本文方法在處理Java語言時，較C語言耗時較大，主要由于前端頻繁啟動虛擬機(jī)造成的，通過改進(jìn)前端工作方式降低耗時.CIL方法由于對編譯器參數(shù)處理不完善，導(dǎo)致分析gtk項(xiàng)目時，無法自動完成需手工干預(yù)，易用性方面弱于本文方法.

4 結(jié)論

1)一次實(shí)現(xiàn)后可支持多語言前端，可直接應(yīng)用于C/C++/Java等主流編程語言.

2)通過增加參數(shù)選項(xiàng)，按項(xiàng)目配置文件自動執(zhí)行靜態(tài)信息提取.

3)重用了GCC內(nèi)前端和中端組織機(jī)制，避免了重復(fù)實(shí)現(xiàn)，保證了效率、健壯性和穩(wěn)定性.

［1］TERENCE P.The Definitive ANTLR Reference:Building Domain-Specific Languages［M］.Raleigh，Dallas: Pragmatic Bookshelf，2007.

［2］SCOTT M，GEORGE N.Elkhound:A fast，practical glr parser generator［C］//Proceedings of the 13thInternational Conference on Compiler Construction.Barcelona: EATCS，EASST，EAPLS，ACM，2004:325-336.

［3］GEORGE C N，SCOTT M，SHREE P R，et al.CIL:Intermediate language and tools for analysis and transformation of C programs［C］//Proceedings of the 11thInternational Conference on Compiler Construction.Grenoble: EATCS，EASST，EAPLS，ACM，2002:213-228.

［4］CHRIS L，VIKRAM A.LLVM:A compilation framework for lifelong program analysis＆transformation［C］// Proceedings of the international symposium on Code generation and optimization.PaloAlto:ACM，2004:75-92.

［5］SEAN C，DANIEL J D，EREZ Z.Extending GCC with modular gimple optimizations［C］//Proceedings of GCC Developers’Summit.Ottawa:Linux Symposium，2007: 31-37.

［6］TARAS G，DAVID M.Using GCC instead of grep and sed［C］//Proceedings of GCC Developers’Summit.Ottawa:Linux Symposium，2008:21-32.

［7］李鑫，王甜甜，蘇小紅，等.消除GCC抽象語法樹文本中冗余信息的算法研究［J］.計(jì)算機(jī)科學(xué)，2008，35(10):170-172.

［8］KRAFT A，MALLOY A，POWER F.A tool chain for reverse engineering C++applications［J］.Science of Computer Programming，2007，69(13):3-13.

［9］GSCHWIND T，PINZGER M，GALL H.TUAnalyzeranalyzing templates in C++code［C］//Proceedings of the 11thWorking Conference on Reverse Engineering. Delft:IEEE，2004:48-57.

［10］ANTONIOL G，DIPENTA M，MASONE G，et al. Compiler hacking for source code analysis［J］.Software Quality Journal，2004，12(4):383-06.