LLVM中靜態(tài)程序信息的過(guò)程間分析方法

莫培弘，衷璐潔

(首都師范大學(xué) 信息工程學(xué)院，北京 100048)

0 引 言

現(xiàn)代軟件系統(tǒng)的復(fù)雜性越來(lái)越突出，程序的規(guī)模也越來(lái)越大，難以直觀地了解程序的編碼邏輯結(jié)構(gòu)。過(guò)程間信息以及過(guò)程內(nèi)信息能夠反映軟件系統(tǒng)中的程序編碼邏輯，在對(duì)程序的理解和分析、軟件的測(cè)試、調(diào)試和維護(hù)、編譯優(yōu)化、錯(cuò)誤定位、bug查找、過(guò)程間數(shù)據(jù)流分析、回溯測(cè)試等軟件工程領(lǐng)域中都有應(yīng)用[1-3]，完整的過(guò)程間信息和過(guò)程內(nèi)信息更好地輔助程序驗(yàn)證和程序調(diào)試[4,5]，提高程序分析的質(zhì)量，增強(qiáng)對(duì)程序的理解。

程序分析方法分為動(dòng)態(tài)分析方法和靜態(tài)分析方法。其中，靜態(tài)分析方法不需要運(yùn)行待分析的程序就能獲取程序可能執(zhí)行的狀態(tài)，有利于對(duì)程序進(jìn)行自動(dòng)化和快速分析。在大型項(xiàng)目中存在大量的過(guò)程間信息和復(fù)雜的過(guò)程內(nèi)信息，通過(guò)靜態(tài)分析可以快速地獲取過(guò)程間信息和過(guò)程內(nèi)信息。精確的過(guò)程內(nèi)信息更好地提高靜態(tài)分析的精度[6,7]。函數(shù)指針指向信息的準(zhǔn)確獲取對(duì)過(guò)程間信息分析的精度有著重要的作用[8,9]。完整的過(guò)程內(nèi)信息和精確的過(guò)程間信息有助于代碼閱讀和分析人員在閱讀和分析大工程或者開(kāi)源代碼時(shí)快速地了解程序的過(guò)程內(nèi)結(jié)構(gòu)和過(guò)程間的層次結(jié)構(gòu)。

1 相關(guān)工作

1.1 有關(guān)研究

目前，對(duì)程序靜態(tài)分析工作的研究比較活躍。針對(duì)過(guò)程間信息提取的問(wèn)題，牟等[10]在函數(shù)調(diào)用路徑的基礎(chǔ)上獲取測(cè)試用例優(yōu)先級(jí)排序的問(wèn)題，通過(guò)獲取函數(shù)調(diào)用的路徑，并利用調(diào)整算法實(shí)現(xiàn)動(dòng)態(tài)調(diào)整測(cè)試用例的優(yōu)先級(jí)排序。孫等[11]針對(duì)操作系統(tǒng)內(nèi)核等大型軟件的函數(shù)調(diào)用問(wèn)題，通過(guò)RTL工具對(duì)源碼生成的中間信息提取函數(shù)調(diào)用信息，生成函數(shù)調(diào)用圖。王等[12]針對(duì)多語(yǔ)言函數(shù)調(diào)用圖的構(gòu)建工具重用率低和實(shí)現(xiàn)復(fù)雜的問(wèn)題，通過(guò)GNU編譯器集合(GCC)的插件在GCC中間表示層上提取函數(shù)調(diào)用關(guān)系并轉(zhuǎn)化成圖形描述語(yǔ)言，獲取函數(shù)調(diào)用圖。

1.2 現(xiàn)有工具

現(xiàn)有的過(guò)程間分析工具存在函數(shù)調(diào)用信息提取不夠準(zhǔn)確和處理庫(kù)函數(shù)調(diào)用信息不夠完善的問(wèn)題。

Source Insight[13]是一個(gè)項(xiàng)目向?qū)У某绦蚓庉嬈骱痛a瀏覽器，具有對(duì)引用樹(shù)(reference tree)，類(lèi)繼承圖(class inheritance diagram)和調(diào)用樹(shù)(call trees)等程序分析信息的可視化支持，并可以生成函數(shù)調(diào)用圖。

CodeViz[14]是一個(gè)C源碼靜態(tài)分析工具，針對(duì)C程序生成可視化的函數(shù)調(diào)用圖，通過(guò)給GCC打補(bǔ)丁，在編譯源文件時(shí)dump出函數(shù)調(diào)用信息，再通過(guò)Perl腳本提取函數(shù)調(diào)用信息。

Cflow[15]是一個(gè)C源碼程序靜態(tài)分析工具，它可以產(chǎn)生前向和反向的兩種函數(shù)調(diào)用圖，直接對(duì)源碼進(jìn)行分析，生成一個(gè)C程序的函數(shù)調(diào)用信息的外部引用集合。

CallTree[16]是一個(gè)C源碼靜態(tài)調(diào)用樹(shù)生成器，通過(guò)分析C源碼，提取函數(shù)調(diào)用信息。

但是上述文獻(xiàn)[10-12]中均不能獲取函數(shù)指針指向的信息，存在函數(shù)調(diào)用信息獲取不夠完善的問(wèn)題；Source Insight和CodeViz不能獲取函數(shù)指針指向的信息；CallTree不能獲取函數(shù)指針指向的真實(shí)信息；CodeViz、CallTree以及Cflow不能完善地處理庫(kù)函數(shù)調(diào)用信息。綜上，在現(xiàn)有過(guò)程間信息獲取的工作中存在的主要問(wèn)題有以下兩點(diǎn)：

(1)存在不能獲取函數(shù)指針指向的真實(shí)信息；

(2)存在不能完善地處理庫(kù)函數(shù)的調(diào)用信息。

2 LLVM編譯框架

2.1 LLVM

LLVM(low level virtual machine)是一個(gè)被廣泛使用的開(kāi)源編譯器框架，它基于靜態(tài)單賦值(static single assignment，SSA)的編譯策略，能同時(shí)支持靜態(tài)和動(dòng)態(tài)的任意編程語(yǔ)言的編譯目標(biāo)。LLVM有著豐富的工具鏈和用戶(hù)可自由定義的LLVM Pass等，是一個(gè)模塊化、可重復(fù)使用的編譯器和工具技術(shù)的集合。它由不同的子項(xiàng)目組成，許多項(xiàng)目已經(jīng)在各種商業(yè)和開(kāi)源項(xiàng)目中得到廣泛應(yīng)用，并被應(yīng)用于學(xué)術(shù)研究[17,18]。

2.2 LLVM IR

IR是LLVM的中間表示(intermediate representation，IR)，是LLVM編譯框架的一個(gè)重要組成部分。IR中包含豐富的程序分析信息[19]，由模塊、全局變量、函數(shù)以及連接類(lèi)型等信息組成。其中，這些程序信息中包含過(guò)程內(nèi)信息和過(guò)程間信息。

LLVM自定義了一組獨(dú)特的指令模式，并為用戶(hù)提供了大量的API接口和可復(fù)用的庫(kù)，通過(guò)編寫(xiě)LLVM Pass可以為用戶(hù)從IR中獲取程序分析信息帶來(lái)方便。針對(duì)上述函數(shù)指針指向信息獲取不夠準(zhǔn)確和庫(kù)函數(shù)調(diào)用信息處理不完善的問(wèn)題，提出一種LLVM中靜態(tài)程序信息的過(guò)程間分析方法(control-flow inter-procedural call-graph，CFICG)。

LLVM IR文件由LLVM指令組成，本文獲取過(guò)程內(nèi)信息和過(guò)程間信息，需要對(duì)ret、br、switch，call，store以及l(fā)oad等LLVM指令等進(jìn)行解析，進(jìn)而提取本文需要的靜態(tài)程序分析信息。表1是代表性的LLVM指令，如終結(jié)指令：通過(guò)獲取br指令，可以獲取當(dāng)前基本塊的后繼信息；通過(guò)switch指令獲取基本塊的分支信息，解決控制流的分支問(wèn)題。

表1 代表性LLVM指令

3 以過(guò)程內(nèi)信息和過(guò)程間信息的提取為分析示例

LLVM IR文件中包含指針、數(shù)據(jù)流、過(guò)程內(nèi)以及過(guò)程間等的信息。通過(guò)提取本文需要的過(guò)程內(nèi)和過(guò)程間的信息，獲取CFICG信息。CFICG表示為

CFICG=,Node>

其中，cf表示過(guò)程內(nèi)信息，N表示基本塊，E表示基本塊之間的流向，Node表示過(guò)程間信息。

3.1 過(guò)程內(nèi)信息提取的分析

關(guān)于過(guò)程內(nèi)信息的提取，每一個(gè)函數(shù)都由一個(gè)或若干個(gè)基本塊組成，一個(gè)基本塊又由一條或者若干條語(yǔ)句組成，在LLVM IR中以switch、ret、br等終結(jié)指令區(qū)分過(guò)程內(nèi)基本塊的信息，如圖1所示。

圖1 過(guò)程內(nèi)信息分析

以上述圖1(a)中的main函數(shù)為例進(jìn)行說(shuō)明(Li中，L表示行，i表示第幾行)。main函數(shù)有4個(gè)基本塊，分別如圖1(a)中4個(gè)實(shí)線方框所示；main函數(shù)中有兩條過(guò)程內(nèi)路徑，分別是L7->L9->L14和L7->L11,L12->L14。

圖1(b)為圖1(a)對(duì)應(yīng)的LLVM IR，源碼中的基本塊語(yǔ)句轉(zhuǎn)化成LLVM中的指令，如圖1中虛線箭頭對(duì)應(yīng)的方框，在圖1(b)中實(shí)線方框前的虛線方框即為當(dāng)前基本塊的名稱(chēng)，圖1(b)中main函數(shù)分別有entry，if.then，if.else和if.end這4個(gè)基本塊，其過(guò)程內(nèi)的路徑分別為entry->if.else->if.end和entry ->if.then ->if.end。

每一個(gè)基本塊由多條LLVM指令組成，并以br，ret等終結(jié)指令劃分基本塊。如圖1(b)中main的entry由{L9，L10，L11，L12}組成，L12中實(shí)線箭頭表示為圖2，entry以br指令結(jié)束一個(gè)基本塊并由label指令指明當(dāng)前基本塊的后繼基本塊的個(gè)數(shù)和名稱(chēng)，一個(gè)label指令對(duì)應(yīng)一個(gè)后繼基本塊，entry基本塊的br指令中存在兩個(gè)label指令，即存在兩個(gè)后繼的基本塊。通過(guò)準(zhǔn)確地獲取過(guò)程內(nèi)信息并組成與源碼對(duì)應(yīng)的過(guò)程內(nèi)信息，解決過(guò)程內(nèi)信息的復(fù)雜性與多樣性地問(wèn)題。

圖2 基本塊信息獲取

3.2 過(guò)程間信息提取的分析

函數(shù)調(diào)用是一個(gè)有向圖，這里先將其表示為CallGraph(V,E)，V表示函數(shù)調(diào)用中所有函數(shù)節(jié)點(diǎn)的集合，E表示節(jié)點(diǎn)之間的邊，并滿足E?V×V。

表示如下：

其中，VE表示函數(shù)調(diào)用之間的關(guān)系集合；functionSet表示函數(shù)的集合；F(a,b)表示函數(shù)a到函數(shù)b之間有一條路徑。

過(guò)程間信息提取需要區(qū)分直接函數(shù)調(diào)用信息和函數(shù)指針指向信息，在LLVM 的指令中直接函數(shù)調(diào)用與函數(shù)指針都以call指令的形式表示[19]，如圖3所示。為區(qū)分直接函數(shù)調(diào)用和函數(shù)指針，需要做進(jìn)一步的分析，即通過(guò)函數(shù)所在的文件、函數(shù)名、參數(shù)類(lèi)型和參數(shù)個(gè)數(shù)并結(jié)合定值-引用(def-use)方法和指針?lè)治龇椒?load和store指令)來(lái)確定函數(shù)指針指向的信息。

圖3 過(guò)程間信息分析

圖3(a)中假設(shè)EditFunc函數(shù)與FileFunc函數(shù)已事先定義好，由函數(shù)指針*funcptr1，*funcptr2和4個(gè)非函數(shù)指針的函數(shù)FileFunc，EditFunc，foo和main組成，圖中實(shí)線箭頭表示函數(shù)調(diào)用的過(guò)程，虛線箭頭表示函數(shù)指針指向的真實(shí)函數(shù)，main函數(shù)的調(diào)用路徑，分別是main->foo->funcptr1和main->funcptr2，這兩條調(diào)用路徑上都有函數(shù)指針。

獲取函數(shù)指針指向的真實(shí)信息需要獲取函數(shù)指針指向的真實(shí)函數(shù)，即funcptr1指向的真實(shí)函數(shù)是FileFunc，funcptr2指向的真實(shí)函數(shù)是EditFunc, 得出main中的兩條真實(shí)函數(shù)調(diào)用路徑，分別為main-> foo->FileFunc和main->EditFunc。

圖3(a)源碼轉(zhuǎn)化成圖3(b)的LLVM 指令，對(duì)圖3(b)中main的過(guò)程間信息分析，存在兩條調(diào)用路徑，即圖中細(xì)虛線箭頭表示的調(diào)用路徑和細(xì)實(shí)線箭頭表示的調(diào)用路徑。細(xì)虛線箭頭調(diào)用信息表示為圖4(a)所示，main通過(guò)call指令調(diào)用foo函數(shù)，foo通過(guò)call調(diào)用 FileFunc函數(shù)。

圖4 main調(diào)用信息的路徑

第二條函數(shù)調(diào)用信息的路徑，即圖中細(xì)實(shí)線箭頭所示，表示為圖4(b)，main函數(shù)通過(guò)call指令調(diào)用“%1”，“%1”的形成過(guò)程，首先，store指令將EditFunc函數(shù)存儲(chǔ)到函數(shù)指針funcptr2中，然后load指令將funcptr2加載到“%1”，最后main函數(shù)通過(guò)call指令調(diào)用“%1”，最終獲取函數(shù)指針指向的真實(shí)函數(shù)EditFunc。

上述的兩條函數(shù)調(diào)用路徑中都存在函數(shù)指針信息，獲取準(zhǔn)確的過(guò)程間信息需要做以下分析：

(1)區(qū)分直接函數(shù)調(diào)用信息與函數(shù)指針指向信息；

(2)分析函數(shù)指針指向的信息存在的兩種情況：①只存在call指令形式的函數(shù)指針信息；②存在store、load和call指令的函數(shù)指針信息。

直接函數(shù)調(diào)用和函數(shù)指針都以call指令表示，通過(guò)對(duì)函數(shù)所在的文件、函數(shù)名、參數(shù)類(lèi)型和參數(shù)個(gè)數(shù)等進(jìn)行分析獲取函數(shù)指針指向的信息。針對(duì)函數(shù)指針的第二種情況，需要對(duì)store和load進(jìn)行指針?lè)治?，再?duì)call進(jìn)行指向分析獲取函數(shù)指針指向的信息。

最后，結(jié)合獲取的過(guò)程內(nèi)信息和過(guò)程間信息，組成CFICG信息，如圖5所示。

圖5 main的CFICG信息

4 過(guò)程間分析方法(CFICG)

針對(duì)上述過(guò)程間存在不能獲取函數(shù)指針指向的真實(shí)信息和不能完善地處理庫(kù)函數(shù)調(diào)用信息的問(wèn)題，提出一種在LLVM 中提取靜態(tài)程序信息的過(guò)程間分析方法(CFICG)，其結(jié)構(gòu)框架如圖6所示。首先輸入LLVM IR文件，通過(guò)上述過(guò)程間信息提取的分析方式，編寫(xiě)LLVM Pass提取過(guò)程內(nèi)信息和過(guò)程間信息，形成程序執(zhí)行的所有可能過(guò)程，并解析過(guò)程內(nèi)信息和過(guò)程間信息，最后生成過(guò)程內(nèi)信息和過(guò)程間信息的文本。解決過(guò)程間的函數(shù)指針指向信息不夠準(zhǔn)確和庫(kù)函數(shù)調(diào)用信息處理不完善的問(wèn)題以及過(guò)程內(nèi)信息的復(fù)雜性與多樣性的問(wèn)題。

圖6 CFICG框架

4.1 算法描述

為了獲取過(guò)程內(nèi)信息和過(guò)程間信息，提出在LLVM中靜態(tài)程序信息的過(guò)程間分析方法(CFICG)，CFICG算法表示為getProInfo()，其由3部分組成，分別是過(guò)程內(nèi)信息提取算法(getIntra())，直接函數(shù)調(diào)用信息提取算法(getCusCall())和函數(shù)指針指向信息提取算法(getPtrCall())，它們的具體算法描述分別如下所示。

CFICG的算法描述如下：

CFICG的算法描述

輸入：IR

輸出：過(guò)程內(nèi)信息、過(guò)程間信息

getProInfo(IR)

(1)getIntra(IR)//提取過(guò)程內(nèi)信息算法

(2)getCusCall(IR)//提取直接函數(shù)調(diào)用信息算法

(3)getPtrCall(IR)//提取函數(shù)指針指向信息算法

CFICG算法包括3部分：過(guò)程內(nèi)信息提取算法、直接函數(shù)調(diào)用信息提取算法和函數(shù)指針指向信息提取算法，分別是算法1、算法2和算法3，算法1、算法2和算法3的輸入都是LLVM的IR，輸出分別是過(guò)程內(nèi)信息、直接函數(shù)調(diào)用信息和函數(shù)指針指向信息。

4.2 過(guò)程內(nèi)信息提取的算法描述

首先獲取每一個(gè)函數(shù)的每一個(gè)基本塊，然后獲取每一個(gè)基本塊的終結(jié)指令，再根據(jù)終結(jié)指令確定基本塊的后繼，重復(fù)上述步驟，依次獲取，直到每一個(gè)函數(shù)執(zhí)行完畢。其算法如下：

算法1：過(guò)程內(nèi)信息提取的算法描述

輸入：IR

輸出：過(guò)程內(nèi)信息

getIntra(IR)

(1)forbbin func do //遍歷函數(shù)獲取基本塊

(2)br←branch(bb); //獲取br指令

(3) if unconditional_branch(br) then

(4)sets←successors(bb);//無(wú)后繼的基本塊

(5) else

(6)sets_n←successor(bb);//有后繼的基本塊

(7) end if

(8)end for

4.3 過(guò)程間信息提取的算法描述

本文的過(guò)程間信息分為直接函數(shù)調(diào)用信息和函數(shù)指針指向信息，其中直接函數(shù)調(diào)用信息包括庫(kù)函數(shù)調(diào)用信息和非庫(kù)函數(shù)調(diào)用信息。

4.3.1 直接函數(shù)調(diào)用信息提取的算法描述

從LLVM指令中獲取call指令，并通過(guò)call指令獲取直接函數(shù)調(diào)用信息，對(duì)獲取的函數(shù)進(jìn)行庫(kù)函數(shù)和非庫(kù)函數(shù)的區(qū)分，最后得到直接函數(shù)調(diào)用信息。其算法如下：

算法2：直接函數(shù)調(diào)用信息提取的算法描述

輸入：IR

輸出：直接函數(shù)調(diào)用信息

getCusCall(IR)

(1)forfuncin mod do //遍歷模塊獲取函數(shù)

(2) forbbin func do //遍歷函數(shù)獲取基本塊

(3) foriin basicbk do //遍歷基本塊獲取指令

(4)setinstrc←i;

(5) if(call←instrc) //獲取call指令

(6)setfunct←call; //獲取函數(shù)調(diào)用信息

(7)setfunct←funct; //獲取非庫(kù)函數(shù)調(diào)用信息

(8) end if

(9) end for

(10) end for

(11) end for

4.3.2 函數(shù)指針指向信息提取的算法描述

通過(guò)解析call指令和call的函數(shù)，若不是函數(shù)指針則不做進(jìn)一步分析，直接獲取調(diào)用的函數(shù)信息；若是函數(shù)指針則進(jìn)一步分析，通過(guò)函數(shù)參數(shù)傳遞的個(gè)數(shù)和函數(shù)傳遞的實(shí)參獲取函數(shù)指針指向的信息；若是存在store和load指令則進(jìn)行指針?lè)治?，獲取調(diào)用的函數(shù)信息，然后通過(guò)對(duì)函數(shù)的形參和實(shí)參分析，獲取函數(shù)指針指向的真實(shí)信息；當(dāng)一個(gè)函數(shù)調(diào)用分析完后定值-引用(def-use)分析下一個(gè)被調(diào)用的函數(shù)，再繼續(xù)重復(fù)上述的執(zhí)行過(guò)程，直到所有的函數(shù)都分析完畢為止。其算法描述如下：

算法3：函數(shù)指針信息提取的算法描述

輸入：IR

輸出：函數(shù)指針的指向信息

getPtrCall(IR)

(1)forbbin func do

(2) foriin basicbk do

(3)cur_inst=i;

(4) if(!call←cur_inst)

(5)setfunc←call;//獲取函數(shù)調(diào)用信息

(6) else

(7)setnum←getNumArg;//參數(shù)個(gè)數(shù)

(8)setAgrOperand←num;//實(shí)參

(9) end if

(11)setfunc←store;//獲取函數(shù)調(diào)用信息

(12)setfunc←load;//獲取函數(shù)調(diào)用信息

(13) end if

(14) forargin func do //遍歷函數(shù)獲取參數(shù)

(15) if(arg==ArgOperand)//獲取形參

(16)setfunct←call;//函數(shù)指針信息

(17) end if

(18) end for

(19) getFuncChain();//函數(shù)調(diào)用鏈信息獲取

(20) end for

(21)end for

算法3的重要部分在對(duì)函數(shù)指針指向信息的分析和對(duì)過(guò)程間信息的def-use分析[20,21]上。在分析函數(shù)指針調(diào)用信息的部分，通過(guò)分析確定函數(shù)指針，再通過(guò)函數(shù)指針傳遞的實(shí)參與形參確定函數(shù)調(diào)用信息指向的真實(shí)函數(shù)；def-use分析，通過(guò)函數(shù)的定值，再由函數(shù)調(diào)用來(lái)確定哪個(gè)函數(shù)被哪個(gè)函數(shù)引用。其表示形式如下：

(1)def(func2)={func1|函數(shù)func1定值了函數(shù)func2}

表示函數(shù)func2的定值函數(shù)集def(func2)由定值函數(shù)func2的所有函數(shù)組成。

(2)use(func2)={func1|函數(shù)func1引用了函數(shù)func2}

函數(shù)func2的引用函數(shù)集use(func2)由引用函數(shù)func2的所有函數(shù)組成。

(3)use(func2)={func1|函數(shù)func1引用了函數(shù)func2}

函數(shù)func2的定值-引用函數(shù)集def-use(func2)由定值函數(shù)func2的所有引用的函數(shù)組成。

如：main=foo1->foo2->foo3->foo4；

則：def-use(main)={foo1，foo2，foo3，foo4}。

針對(duì)過(guò)程間信息的處理，首先根據(jù)函數(shù)的定值，然后通過(guò)確定main函數(shù)調(diào)用時(shí)引用了哪個(gè)函數(shù)，再判斷引用的函數(shù)是否為函數(shù)指針；如果是，則獲取函數(shù)指針變量的信息，通過(guò)分析函數(shù)指針的實(shí)參(稱(chēng)為定值)被哪個(gè)函數(shù)指針指向的函數(shù)引用了，最終獲取函數(shù)指針指向的真實(shí)函數(shù)信息。即獲取函數(shù)調(diào)用的定值-引用算法表示為getFuncChain()。

getFuncChain()算法描述的流程具體如下：

算法4：函數(shù)調(diào)用鏈算法的描述

輸入：IR中的函數(shù)

輸出：函數(shù)調(diào)用鏈

getFuncChain(func1,func2){

(1)從main函數(shù)的func1函數(shù)開(kāi)始分析.

(2)分析函數(shù)列表中的每一個(gè)函數(shù)fun;

(3) if(fun是函數(shù)變量)

(4) 則def(fun),use(fun)中的函數(shù),def(func)|函數(shù)變量func∈use(fun)中的函數(shù)是func2中函數(shù).

(5) else if((f為函數(shù)自變量|f∈def(fun)或f∈(def(def(fun)…)或f∈use(fun))

(6) 則def(fun),use(fun)中的函數(shù)是func2中的函數(shù).

(7) getFuncChain(func11,func22)遞歸獲取下一個(gè)引用的函數(shù).

(8) 生成函數(shù)調(diào)用鏈.

(9) }

5 實(shí)驗(yàn)結(jié)果與分析

本文在LLVM下靜態(tài)分析提取C/C++程序的過(guò)程內(nèi)信息和過(guò)程間信息，首先通過(guò)與現(xiàn)有工具Source Insight、CallTree以及Cflow的對(duì)比來(lái)驗(yàn)證本方法過(guò)程間信息的提取精度；再通過(guò)開(kāi)源碼進(jìn)行實(shí)驗(yàn)驗(yàn)證本方法的實(shí)用性。

5.1 實(shí)驗(yàn)環(huán)境

本文的實(shí)驗(yàn)環(huán)境為，硬件環(huán)境：Intel(R) Core(TM) i7-4790 CPU @ 3.60GHz，3GB內(nèi)存；軟件環(huán)境：Ubuntu 15.04，LLVM 3.7.0；開(kāi)發(fā)工具：Sublime Text 3，vim；編程語(yǔ)言：C/C++，python。

5.2 實(shí)驗(yàn)驗(yàn)證

本文的實(shí)驗(yàn)驗(yàn)證主要從兩方面進(jìn)行驗(yàn)證：

(1)驗(yàn)證本文提出的過(guò)程間分析方法對(duì)過(guò)程間信息提取的精度;

(2)驗(yàn)證本文提出的過(guò)程間分析方法的實(shí)用性。

5.2.1 驗(yàn)證CFICG提取過(guò)程間信息的精度

圖7(a)中函數(shù)add_ptr、mul_ptr以及test1_all為函數(shù)指針，本文利用graphviz[22]工具繪制函數(shù)調(diào)用圖，圖7(b)是過(guò)程間分析方法(CFICG)與現(xiàn)有分析工具的對(duì)比結(jié)果。根據(jù)圖7的實(shí)驗(yàn)結(jié)果可知，Source Insight可以獲取直接函數(shù)調(diào)用信息，不能獲取函數(shù)指針指向的信息；CallTree可以獲取函數(shù)調(diào)用信息，無(wú)法獲取函數(shù)指針指向的真實(shí)信息；Cflow可以獲取函數(shù)指針指向的真實(shí)信息，不能解析、區(qū)分非庫(kù)函數(shù)調(diào)用與庫(kù)函數(shù)調(diào)用的信息(如scanf函數(shù))；本文提出的過(guò)程間分析方法獲取了函數(shù)指針指向的真實(shí)信息以及識(shí)別和區(qū)分非庫(kù)函數(shù)和庫(kù)函數(shù)調(diào)用的信息并可以直觀地觀察在哪個(gè)基本塊內(nèi)發(fā)生了函數(shù)調(diào)用，如圖7(b)的實(shí)驗(yàn)結(jié)果對(duì)比。

圖7(b)中CFICG的函數(shù)add、mul、test1和test2都只有1個(gè)基本塊entry；all有4個(gè)基本塊分別是entry、if_then、if_else以及if_end，在if_then內(nèi)調(diào)用了test1(函數(shù)指針test1_all指向test1)，在if_else內(nèi)調(diào)用了test2；函數(shù)main有5個(gè)基本塊分別為entry、sw_bb、sw_bb2、sw_bb3以及sw_epilog，即sw_bb對(duì)應(yīng)源程序的第1個(gè)case，并調(diào)用add(函數(shù)指針add_ptr指向add)，sw_bb2對(duì)應(yīng)源程序的第2個(gè)case，并調(diào)用mul(函數(shù)指針mul_ptr指向mul)，sw_bb3對(duì)應(yīng)源程序的第3個(gè)case，并調(diào)用了all，再以一個(gè)sw_epilog作為最后1個(gè)基本塊結(jié)束整個(gè)函數(shù)。

圖7 CFICG與現(xiàn)有工具實(shí)驗(yàn)結(jié)果

表2用于統(tǒng)計(jì)過(guò)程間分析方法(CFICG)和現(xiàn)有工具對(duì)圖7的C源碼獲取程序中實(shí)際被調(diào)用函數(shù)與實(shí)驗(yàn)獲取被調(diào)用函數(shù)的個(gè)數(shù)進(jìn)行對(duì)比，統(tǒng)計(jì)出圖8的函數(shù)調(diào)用信息提取的覆蓋率((覆蓋率=(實(shí)驗(yàn)獲取被調(diào)用函數(shù)個(gè)數(shù)/程序中實(shí)際被調(diào)用函數(shù)個(gè)數(shù))×100%))，表2中reCal表示程序中實(shí)際被調(diào)用函數(shù)個(gè)數(shù)，ExO表示實(shí)驗(yàn)獲取被調(diào)用函數(shù)個(gè)數(shù)，IdCo表示函數(shù)調(diào)用提取的覆蓋率，統(tǒng)計(jì)結(jié)果見(jiàn)表2。

表2 圖7中示例代碼函數(shù)調(diào)用信息的統(tǒng)計(jì)結(jié)果

圖8 函數(shù)調(diào)用信息獲取的覆蓋率

5.2.2 驗(yàn)證CFICG的實(shí)用性

通過(guò)測(cè)試開(kāi)源碼，來(lái)驗(yàn)證本文提出的過(guò)程間分析方法(CFICG)的實(shí)用性。實(shí)驗(yàn)結(jié)果見(jiàn)表3。

由于處理源碼的規(guī)模較大，為了體現(xiàn)過(guò)程間分析方法(CFICG)的檢測(cè)速度，進(jìn)行了時(shí)間開(kāi)銷(xiāo)的統(tǒng)計(jì)。如圖9所示。

同時(shí)，以aget開(kāi)源碼為示例給出實(shí)驗(yàn)結(jié)果的圖示，并放大一小部分以便了解，如圖10所示。

實(shí)驗(yàn)結(jié)果表明，本文提出的過(guò)程間分析方法(CFICG)提取了過(guò)程內(nèi)信息的路徑流向，在過(guò)程間信息提取中函數(shù)指針指向信息提取更為精確和庫(kù)函數(shù)調(diào)用信息處理更為完善，并且能結(jié)合過(guò)程內(nèi)信息分析出函數(shù)調(diào)用信息發(fā)生在哪個(gè)基本塊內(nèi)，比上述工具更準(zhǔn)確地體現(xiàn)出函數(shù)調(diào)用發(fā)生的位置。更精確地獲取函數(shù)指針指向的真實(shí)信息和更完善地處理庫(kù)函數(shù)調(diào)用的信息，提高了靜態(tài)程序分析過(guò)程間的精度；對(duì)開(kāi)源碼進(jìn)行了實(shí)驗(yàn)，驗(yàn)證本文提出的方法的實(shí)用性并且在時(shí)間開(kāi)銷(xiāo)上也不是很大；同時(shí)，有助于代碼閱讀和程序分析人員更清晰、更好地理解程序結(jié)構(gòu)以及程序的設(shè)計(jì)流程。

表3 源碼實(shí)驗(yàn)結(jié)果

圖9 開(kāi)源碼獲取函數(shù)信息的時(shí)間開(kāi)銷(xiāo)

6 結(jié)束語(yǔ)

本文針對(duì)C/C++靜態(tài)程序分析，提出一種在LLVM平臺(tái)下靜態(tài)程序信息的過(guò)程間分析方法(CFICG)，通過(guò)對(duì)過(guò)程內(nèi)信息和過(guò)程間信息的提取，解決了過(guò)程間信息獲取中函數(shù)指針指向信息不夠準(zhǔn)確的問(wèn)題以及庫(kù)函數(shù)調(diào)用信息處理不完善的問(wèn)題。實(shí)驗(yàn)結(jié)果表明，本文提出的靜態(tài)程序分析方法(CFICG)支持C/C++程序過(guò)程內(nèi)和過(guò)程間的信息提取，更好地處理庫(kù)函數(shù)調(diào)用信息并更為準(zhǔn)確地獲取函數(shù)指針指向的真實(shí)信息，并且具有實(shí)用性。

圖10 aget實(shí)驗(yàn)結(jié)果

參考文獻(xiàn)：

[1]Ohmann P,Liblit B.Lightweight control-flow instrumentation and postmortem analysis in support of debugging[C]//IEEE/ACM 28th International Conference on Automated Software Engineering,2013:378-388.

[2]ZONG Fangfang,HUANG Hongyun,DING Zuohua.Software fault location based on double-times-locating strategy[J].Journal of Software,2016,27(8):1993-2007(in Chinese).[宗芳芳,黃鴻云,丁佐華.基于二次定位策略的軟件故障定位[J].軟件學(xué)報(bào),2016,27(8):1993-2007.]

[3]LI Zhoujun,ZHANG Junxian,LIAO Xiangke,et al.Survey of software vulnerability detection techniques[J].Chinese Journal of Computers,2015,38(4):717-732(in Chinese).[李舟軍,張俊賢,廖湘科,等.軟件安全漏洞檢測(cè)技術(shù)[J].計(jì)算機(jī)學(xué)報(bào),2015,38(4):717-732.]

[4]Fittkau F,Finke S,Hasselbring W,et al.Comparing trace visualizations for program comprehension through controlled experiments[C]//IEEE 23rd International Conference on Program Comprehension,2015:266-276.

[5]Sui Y,Xue J.SVF:Interprocedural static value-flow analysis in LLVM[C]//Proceedings of the 25th International Confe-rence on Compiler Construction.New York:ACM,2016:265-266.

[6]Tice C,Roeder T,Collingbourne P,et al.Enforcing forwar-dedge control-flow integrity in GCC & LLVM[C]//23rd USENIX Security Symposium,2014:941-955.

[7]Niu B,Tan G.Modular control-flow integrity[J].ACM SIGPLAN Notices,2014,49(6):577-587.

[8]Wang P,Yang J,Tan L,et al.Generating precise dependencies for large software[C]//4th International Workshop on Managing Technical Debt.IEEE,2013:47-50.

[9]Padhye R,Khedker U P.Interprocedural data flow analysis in soot using value contexts[C]//Proceedings of the 2nd ACM SIGPLAN International Workshop on State of the Art in Java Program Analysis,2013:31-36.

[10]MOU Yongmin,LI Huili.Test case prioritization based on function calling paths[J].Computer Engineering,2014,40(7):242-246(in Chinese).[牟永敏,李慧麗.基于函數(shù)調(diào)用路徑的測(cè)試用例優(yōu)先級(jí)排序[J].計(jì)算機(jī)工程,2014,40(7):242-246.]

[11]SUN Weizhen,DU Xiangyan,XIANG Yong,et al.CG-RTL:A RTL-based function call graph generator[J].Journal of Chinese Computer Systems,2014,35(3):555-559(in Chinese).[孫衛(wèi)真,杜香燕,向勇,等.基于RTL的函數(shù)調(diào)用圖生成工具CG-RTL[J].小型微型計(jì)算機(jī)系統(tǒng),2014,35(3):555-559.]

[12]WANG Yagang,XU Chenghua.Construction of function calls relationship graph for multi-language source code[J].Journal of Xi’an University of Posts and Telecommunications,2013,18(6):75-79(in Chinese).[王亞剛,徐成華.多語(yǔ)言源程序函數(shù)調(diào)用關(guān)系圖的生成方法[J].西安郵電大學(xué)學(xué)報(bào),2013,18(6):75-79.]

[13]Source Dynamics Inc:Source insight version 3.5[EB/OL].[2016-06-07].https://www.sourceinsight.com/doc/v3/ManualTOC.htm.

[14]Petersenna:CodeViz:A CallGraph visualiser [EB/OL].[2015-07-23].https://github.com/petersenna/codeviz.

[15]Ruda:GNU cflow[EB/OL].[2015-10-23].http://rudix.org/packages/cflow.html.

[16]Czaber:callTree[EB/OL].[2016-07-26].https://sourceforge.net/projects/calltree/.

[17]LLVM Team.The LLVM compiler infrastructure[EB/OL].[2017-03-13].http://llvm.org/.

[18]Lopes B C,Auler R.Getting started with LLVM core libra-ries[M].Birmingham:Packt Publishing Ltd,2014:219-284.

[19]LLVM Team.LLVM language reference manual[EB/OL].[2015-09-01].http://releases.llvm.org/3.7.0/docs/LangRef.html.

[20]Wei F,Roy S,Ou X.Amandroid:A precise and general inter-component data flow analysis framework for security vetting of android apps[C]//Proceedings of the ACM SIGSAC Conference on Computer and Communications Security.New York:ACM,2014:1329-1341.

[21]Jin W,Cohen C,Gennari J,et al.Recovering c++ objects from binaries using inter-procedural data-flow analysis[C]//Proceedings of ACM SIGPLAN on Program Protection and Reverse Engineering Workshop.New York:ACM,2014:1.

[22]John Ellson:Graph visualization tools[EB/OL].[2017-01-04].https://github.com/ellson/graphviz/releases.