莫培弘，衷璐潔

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

0 引 言

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

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

1 相關(guān)工作

1.1 有關(guān)研究

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

1.2 現(xiàn)有工具

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

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

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

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

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

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

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

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

2 LLVM編譯框架

2.1 LLVM

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

2.2 LLVM IR

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

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

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

表1 代表性LLVM指令

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

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

CFICG=,Node>

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

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

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

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

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

圖1(b)為圖1(a)對應(yīng)的LLVM IR，源碼中的基本塊語句轉(zhuǎn)化成LLVM中的指令，如圖1中虛線箭頭對應(yīng)的方框，在圖1(b)中實(shí)線方框前的虛線方框即為當(dāng)前基本塊的名稱，圖1(b)中main函數(shù)分別有entry，if.then，if.else和if.end這4個(gè)基本塊，其過程內(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ù)和名稱，一個(gè)label指令對應(yīng)一個(gè)后繼基本塊，entry基本塊的br指令中存在兩個(gè)label指令，即存在兩個(gè)后繼的基本塊。通過準(zhǔn)確地獲取過程內(nèi)信息并組成與源碼對應(yīng)的過程內(nèi)信息，解決過程內(nèi)信息的復(fù)雜性與多樣性地問題。

圖2 基本塊信息獲取

3.2 過程間信息提取的分析

函數(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之間有一條路徑。

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

圖3 過程間信息分析

圖3(a)中假設(shè)EditFunc函數(shù)與FileFunc函數(shù)已事先定義好，由函數(shù)指針*funcptr1，*funcptr2和4個(gè)非函數(shù)指針的函數(shù)FileFunc，EditFunc，foo和main組成，圖中實(shí)線箭頭表示函數(shù)調(diào)用的過程，虛線箭頭表示函數(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 指令，對圖3(b)中main的過程間信息分析，存在兩條調(diào)用路徑，即圖中細(xì)虛線箭頭表示的調(diào)用路徑和細(xì)實(shí)線箭頭表示的調(diào)用路徑。細(xì)虛線箭頭調(diào)用信息表示為圖4(a)所示，main通過call指令調(diào)用foo函數(shù)，foo通過call調(diào)用 FileFunc函數(shù)。

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

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

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

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

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

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

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

圖5 main的CFICG信息

4 過程間分析方法(CFICG)

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

圖6 CFICG框架

4.1 算法描述

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

CFICG的算法描述如下：

CFICG的算法描述

輸入：IR

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

getProInfo(IR)

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

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

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

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

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

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

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

輸入：IR

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

getIntra(IR)

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

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

(3) if unconditional_branch(br) then

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

(5) else

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

(7) end if

(8)end for

4.3 過程間信息提取的算法描述

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

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

從LLVM指令中獲取call指令，并通過call指令獲取直接函數(shù)調(diào)用信息，對獲取的函數(shù)進(jìn)行庫函數(shù)和非庫函數(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; //獲取非庫函數(shù)調(diào)用信息

(8) end if

(9) end for

(10) end for

(11) end for

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

通過解析call指令和call的函數(shù)，若不是函數(shù)指針則不做進(jìn)一步分析，直接獲取調(diào)用的函數(shù)信息；若是函數(shù)指針則進(jìn)一步分析，通過函數(shù)參數(shù)傳遞的個(gè)數(shù)和函數(shù)傳遞的實(shí)參獲取函數(shù)指針指向的信息；若是存在store和load指令則進(jìn)行指針分析，獲取調(diào)用的函數(shù)信息，然后通過對函數(shù)的形參和實(shí)參分析，獲取函數(shù)指針指向的真實(shí)信息；當(dāng)一個(gè)函數(shù)調(diào)用分析完后定值-引用(def-use)分析下一個(gè)被調(diào)用的函數(shù)，再繼續(xù)重復(fù)上述的執(zhí)行過程，直到所有的函數(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的重要部分在對函數(shù)指針指向信息的分析和對過程間信息的def-use分析[20,21]上。在分析函數(shù)指針調(diào)用信息的部分，通過分析確定函數(shù)指針，再通過函數(shù)指針傳遞的實(shí)參與形參確定函數(shù)調(diào)用信息指向的真實(shí)函數(shù)；def-use分析，通過函數(shù)的定值，再由函數(shù)調(diào)用來確定哪個(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}。

針對過程間信息的處理，首先根據(jù)函數(shù)的定值，然后通過確定main函數(shù)調(diào)用時(shí)引用了哪個(gè)函數(shù)，再判斷引用的函數(shù)是否為函數(shù)指針；如果是，則獲取函數(shù)指針變量的信息，通過分析函數(shù)指針的實(shí)參(稱為定值)被哪個(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ù)開始分析.

(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++程序的過程內(nèi)信息和過程間信息，首先通過與現(xiàn)有工具Source Insight、CallTree以及Cflow的對比來驗(yàn)證本方法過程間信息的提取精度；再通過開源碼進(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；開發(fā)工具：Sublime Text 3，vim；編程語言：C/C++，python。

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

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

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

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

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

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

圖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對應(yīng)源程序的第1個(gè)case，并調(diào)用add(函數(shù)指針add_ptr指向add)，sw_bb2對應(yīng)源程序的第2個(gè)case，并調(diào)用mul(函數(shù)指針mul_ptr指向mul)，sw_bb3對應(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ì)過程間分析方法(CFICG)和現(xiàn)有工具對圖7的C源碼獲取程序中實(shí)際被調(diào)用函數(shù)與實(shí)驗(yàn)獲取被調(diào)用函數(shù)的個(gè)數(shù)進(jìn)行對比，統(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é)果見表2。

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

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

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

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

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

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

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

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

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

6 結(jié)束語

本文針對C/C++靜態(tài)程序分析，提出一種在LLVM平臺下靜態(tài)程序信息的過程間分析方法(CFICG)，通過對過程內(nèi)信息和過程間信息的提取，解決了過程間信息獲取中函數(shù)指針指向信息不夠準(zhǔn)確的問題以及庫函數(shù)調(diào)用信息處理不完善的問題。實(shí)驗(yàn)結(jié)果表明，本文提出的靜態(tài)程序分析方法(CFICG)支持C/C++程序過程內(nèi)和過程間的信息提取，更好地處理庫函數(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).[李舟軍,張俊賢,廖湘科,等.軟件安全漏洞檢測技術(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)用路徑的測試用例優(yōu)先級排序[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).[王亞剛,徐成華.多語言源程序函數(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.