張 靜，黃志球,2，沈國(guó)華,2，喻垚慎，艾 磊

(1.南京航空航天大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院， 江蘇 南京 211106; 2.南京航空航天大學(xué)高安全系統(tǒng)的軟件開(kāi)發(fā)與驗(yàn)證技術(shù)工業(yè)和信息化部重點(diǎn)實(shí)驗(yàn)室,江蘇 南京 211106)

1 引言

內(nèi)存泄漏[1]是程序運(yùn)行時(shí)資源泄漏的一種形式，通常在程序執(zhí)行不適當(dāng)?shù)膬?nèi)存分配和釋放操作時(shí)發(fā)生，是指由于疏忽或錯(cuò)誤造成程序未能釋放已經(jīng)不再使用的內(nèi)存，導(dǎo)致潛在的安全隱患。每個(gè)物理系統(tǒng)都有一個(gè)較大的內(nèi)存量，如果內(nèi)存泄漏沒(méi)有被及時(shí)終止，會(huì)造成難以估計(jì)的損失，如內(nèi)存耗盡[2]、程序崩潰[3]、系統(tǒng)故障、信息泄漏[4]等。例如，2017年的Cloudflare解析器bug導(dǎo)致內(nèi)存泄漏事件中，泄漏的內(nèi)存包含了隱私信息，其中很明顯有一個(gè)是用于在Cloudflare機(jī)器之間進(jìn)行安全連接的私鑰，且這些隱私信息還會(huì)被搜索引擎緩存。2月13日到2月18日期間，通過(guò)Cloudflare的每3 300 000個(gè)HTTP請(qǐng)求中約有1個(gè)可能導(dǎo)致內(nèi)存泄漏(約為請(qǐng)求的0.000 03%)。因此，針對(duì)內(nèi)存泄漏檢測(cè)的研究一直是一個(gè)熱門(mén)的課題[5,6]。

C語(yǔ)言常用于編寫(xiě)安全關(guān)鍵軟件，然而其中存在的內(nèi)存泄漏缺陷一直難以被檢測(cè)。在支持自動(dòng)垃圾回收的語(yǔ)言(如Java)中，程序顯式地申請(qǐng)內(nèi)存，但不需要顯式地釋放。但是，C語(yǔ)言由于缺乏垃圾自動(dòng)回收機(jī)制，導(dǎo)致發(fā)生內(nèi)存泄漏的概率要比Java、C#等大得多，一旦發(fā)生問(wèn)題，后果也更為嚴(yán)重，一般的軟件測(cè)試方法無(wú)法及時(shí)發(fā)現(xiàn)程序中可能存在的內(nèi)存泄漏。堆[7]是操作系統(tǒng)所維護(hù)的一塊特殊內(nèi)存，用于程序的內(nèi)存動(dòng)態(tài)分配。C語(yǔ)言使用malloc從堆上分配內(nèi)存，使用free釋放已分配的對(duì)應(yīng)內(nèi)存。通過(guò)分析程序源碼可知，程序員經(jīng)常使用指針變量直接或者間接地對(duì)內(nèi)存單元進(jìn)行操作，使得這些動(dòng)態(tài)內(nèi)存單元之間存在著復(fù)雜的指向關(guān)系，例如，某個(gè)內(nèi)存單元可能被多個(gè)指針變量或其他內(nèi)存單元引用[8]。隨著軟件規(guī)模的增加，指向關(guān)系更為復(fù)雜，申請(qǐng)和釋放操作可能不在一個(gè)函數(shù)內(nèi)，所以檢測(cè)C程序中已經(jīng)申請(qǐng)的內(nèi)存單元最終是否被釋放非常復(fù)雜。目前檢測(cè)內(nèi)存泄漏的方法主要分為動(dòng)態(tài)測(cè)試和靜態(tài)分析。

動(dòng)態(tài)測(cè)試是在程序執(zhí)行的過(guò)程中，根據(jù)內(nèi)存的實(shí)際變化來(lái)判斷是否發(fā)生泄漏，實(shí)時(shí)動(dòng)態(tài)檢測(cè)，記錄程序動(dòng)態(tài)分配的內(nèi)存資源和釋放信息，檢測(cè)的泄漏點(diǎn)精確，不存在太多誤報(bào)的情況?，F(xiàn)有的動(dòng)態(tài)測(cè)試工具例如Purify[9]和Valgrind[10]，自動(dòng)化程度高且定位準(zhǔn)確。但是，動(dòng)態(tài)測(cè)試存在局限性，首先是難以保證代碼覆蓋的全面性，有的內(nèi)存泄漏不易觸發(fā)，容易發(fā)生漏報(bào)的情況，因此需要依賴(lài)高質(zhì)量的測(cè)試用例[8]；其次動(dòng)態(tài)測(cè)試的代價(jià)比較大，對(duì)硬件的要求高；最后，由于動(dòng)態(tài)測(cè)試發(fā)生在軟件開(kāi)發(fā)后期，此時(shí)發(fā)現(xiàn)缺陷和修改缺陷的成本更高。

靜態(tài)分析技術(shù)是軟件開(kāi)發(fā)中十分有效的質(zhì)量控制方式之一，其分析工具具有靈活的使用方法，根據(jù)檢測(cè)技術(shù)原理，用戶(hù)可以定制最佳的檢測(cè)方案。作為一種檢測(cè)效率高、安全性高的軟件程序檢測(cè)方法，靜態(tài)分析技術(shù)受到越來(lái)越多的軟件開(kāi)發(fā)人員的重視。靜態(tài)分析的主要對(duì)象是源程序，其中含有大量設(shè)計(jì)信息、邏輯信息，同時(shí)也含有程序異常的信息。通過(guò)掃描源程序，可以從中提取方法調(diào)用關(guān)系、各模塊間數(shù)據(jù)交互關(guān)系等設(shè)計(jì)信息，檢測(cè)程序的控制流和數(shù)據(jù)流結(jié)構(gòu)，從邏輯的角度對(duì)程序進(jìn)行分析，更全面地檢測(cè)出程序中存在的內(nèi)存泄漏，因此靜態(tài)分析是檢測(cè)內(nèi)存泄漏必不可少的一種檢測(cè)方式。

與動(dòng)態(tài)檢測(cè)相比，靜態(tài)分析能夠遍歷程序中的每個(gè)分支，覆蓋到程序源碼中所有可能路徑，從而找出潛在的缺陷。Maxwell等[11]提出了基于圖的內(nèi)存泄漏檢測(cè)方法，用圖對(duì)動(dòng)態(tài)內(nèi)存建模，將堆內(nèi)存進(jìn)行圖化，然后挖掘圖中的信息，針對(duì)C/C++程序中基于指針和動(dòng)態(tài)內(nèi)存的數(shù)據(jù)結(jié)構(gòu)進(jìn)行有效的缺陷檢測(cè)。斯坦福大學(xué)的Heine等[12]介紹了基于流敏感和上下文敏感檢測(cè)算法的靜態(tài)分析工具，每個(gè)對(duì)象有且只有一個(gè)所有權(quán)指針，對(duì)所有權(quán)約束進(jìn)行求解并將其不一致性判定為潛在的內(nèi)存泄漏，Xie等[13]提出了一種上下文敏感和路徑敏感的算法，通過(guò)顯式內(nèi)存管理來(lái)檢測(cè)程序中的內(nèi)存泄漏，使用布爾約束表達(dá)分析。Fastcheck[14]是一個(gè)常用靜態(tài)分析工具，其檢測(cè)思想是基于保護(hù)值流分析，通過(guò)跟蹤內(nèi)存空間分配點(diǎn)到釋放點(diǎn)的流向，判斷所有的路徑是否有且只有一個(gè)源-聚對(duì)。該方法是基于統(tǒng)一的指向別名分析，使用等價(jià)類(lèi)方法將內(nèi)存劃分成不相交的區(qū)域。

基于上述分析，C程序的內(nèi)存泄漏靜態(tài)分析研究是具有重要現(xiàn)實(shí)意義的。盡管靜態(tài)分析已經(jīng)取得了一定的研究進(jìn)展，但現(xiàn)有的檢測(cè)方法仍存在不足的地方。隨著代碼規(guī)模的增長(zhǎng)，實(shí)用的內(nèi)存檢測(cè)方法需要可擴(kuò)展性，在保證檢測(cè)效率的同時(shí)也需要保證檢測(cè)的準(zhǔn)確性。然而現(xiàn)有的方法大都受限于準(zhǔn)確性和可擴(kuò)展性，例如稀疏值流分析SVFA(Sparse Value-Flow Analysis)[15]是目前內(nèi)存泄漏檢測(cè)相對(duì)準(zhǔn)確且高效的技術(shù)，但是，由于缺乏路徑敏感性，還是不可避免地會(huì)引入誤報(bào)。但是，通過(guò)遍歷控制流圖同時(shí)使用路徑敏感分析來(lái)實(shí)現(xiàn)高精度檢測(cè)的方法，其可擴(kuò)展性容易受限，尤其是分析代碼規(guī)模大的程序時(shí)代價(jià)太高。

為了在查找精度和效率上達(dá)到平衡，本文針對(duì)廣泛應(yīng)用于內(nèi)存泄漏的SVFA技術(shù)缺乏路徑敏感的問(wèn)題，通過(guò)結(jié)合控制流信息引入路徑敏感性，來(lái)提高檢測(cè)準(zhǔn)確性。本文提出了一種基于指針?lè)治鰳?gòu)建路徑敏感的值流約束檢測(cè)內(nèi)存泄漏的方法，簡(jiǎn)稱(chēng)PACV(Pointer Analysis and Control-flow Value Guard)研究方法。

2 內(nèi)存泄漏機(jī)制分析

從動(dòng)態(tài)內(nèi)存管理的角度，可將一個(gè)C程序內(nèi)存空間抽象為2個(gè)空間：工作空間和自由空間。程序運(yùn)行過(guò)程中,自由空間中有可供申請(qǐng)的動(dòng)態(tài)內(nèi)存，工作空間可以申請(qǐng)其中的內(nèi)存塊，通過(guò)全局?jǐn)?shù)據(jù)區(qū)、棧區(qū)和常量區(qū)的指針變量進(jìn)行索引。這2個(gè)空間之間有2種內(nèi)存遷移的方向：(1)自由空間到工作空間：通過(guò)內(nèi)存分配函數(shù)將內(nèi)存塊從自由空間遷移到工作空間中；(2)工作空間到自由空間：通過(guò)內(nèi)存釋放函數(shù)將內(nèi)存塊釋放到自由空間中。在動(dòng)態(tài)空間中，若存在己分配的內(nèi)存塊沒(méi)有釋放卻失去了訪問(wèn)路徑，則無(wú)法再去訪問(wèn)它們，這些內(nèi)存塊就是被泄漏的。如圖1所示，m5釋放回到自由空間中，m1和m8為泄漏內(nèi)存。

從程序執(zhí)行的角度，在任何程序執(zhí)行路徑中，在分配點(diǎn)(source)創(chuàng)建的每個(gè)對(duì)象最終必須至少到達(dá)一個(gè)釋放點(diǎn)(sink)。

2.1 場(chǎng)景分析

通過(guò)分析2018年1月至今CVE(Common Vulnerabilities and Exposure)[16]中公布的63條內(nèi)存泄漏相關(guān)漏洞信息，可將其分為5種常見(jiàn)場(chǎng)景。

場(chǎng)景1內(nèi)存管理關(guān)鍵字或函數(shù)使用不當(dāng)。

從2018年1月至2019年4月，CVE中就有3條相關(guān)漏洞信息，由于程序結(jié)構(gòu)復(fù)雜、人員疏忽導(dǎo)致使用了錯(cuò)誤的釋放方法。內(nèi)存分配和釋放是相互匹配出現(xiàn)的，成對(duì)使用這些關(guān)鍵字或函數(shù)是內(nèi)存動(dòng)態(tài)分配使用的基本原則，調(diào)用了內(nèi)存分配函數(shù)卻沒(méi)有調(diào)用釋放函數(shù)會(huì)導(dǎo)致泄漏。此場(chǎng)景屬于最基本的場(chǎng)景，針對(duì)這種類(lèi)型的內(nèi)存泄漏檢測(cè)也相對(duì)簡(jiǎn)單，通常是在函數(shù)入口處初始化指針內(nèi)存的分配情況，在函數(shù)出口處對(duì)比函數(shù)內(nèi)的分配和釋放操作來(lái)判定是否存在已經(jīng)分配內(nèi)存的指針沒(méi)有被釋放的情況[17]。

場(chǎng)景2程序邏輯缺陷。

雖然程序中分配和釋放函數(shù)成對(duì)出現(xiàn)，并未出現(xiàn)錯(cuò)配或者漏配的情況，但由于程序本來(lái)的一些缺陷，仍會(huì)導(dǎo)致內(nèi)存泄漏。函數(shù)在程序入口處分配了內(nèi)存，但在最后釋放之前，分支語(yǔ)句內(nèi)的代碼提前返回發(fā)生異常，那么就引發(fā)了內(nèi)存泄漏。若函數(shù)里的邏輯非常復(fù)雜，或者異常情況不是必現(xiàn)，那么查找內(nèi)存泄漏點(diǎn)則更加困難。

場(chǎng)景3指針重新賦值。

指針變量p和np分別被分配了5字節(jié)的內(nèi)存。如果程序需要執(zhí)行賦值語(yǔ)句p=np，指針變量p被np指針重新賦值，導(dǎo)致p之前所指向的內(nèi)存位置變成了孤立的內(nèi)存。因?yàn)闆](méi)有指向該內(nèi)存的引用，它無(wú)法進(jìn)行釋放，從而導(dǎo)致5字節(jié)的內(nèi)存泄漏。

場(chǎng)景4錯(cuò)誤的內(nèi)存釋放。

假設(shè)有一個(gè)指針變量p，它指向一個(gè)5字節(jié)的內(nèi)存位置。該內(nèi)存位置的第2字節(jié)又指向某個(gè)新的動(dòng)態(tài)分配的5字節(jié)的內(nèi)存位置。如果通過(guò)調(diào)用free來(lái)釋放了最初的內(nèi)存塊，則新分配的內(nèi)存變成了孤立的內(nèi)存，導(dǎo)致了內(nèi)存泄漏。

場(chǎng)景5返回值的錯(cuò)誤處理。

某些函數(shù)會(huì)返回對(duì)動(dòng)態(tài)分配的內(nèi)存的引用，主函數(shù)中調(diào)用f函數(shù)，但未處理該內(nèi)存位置的返回地址導(dǎo)致f函數(shù)所分配的5字節(jié)的內(nèi)存塊丟失，造成內(nèi)存泄漏。

2.2 原因分析

根據(jù)上述場(chǎng)景分析可知，內(nèi)存泄漏與指針及其關(guān)聯(lián)內(nèi)存操作相關(guān)，因此根本原因分析應(yīng)從內(nèi)存塊與指針的生命周期展開(kāi)。內(nèi)存塊的生命周期可用3種方式表示：

(1)引用：當(dāng)沒(méi)有對(duì)內(nèi)存塊的引用時(shí)，堆內(nèi)存塊的生命周期結(jié)束。

(2)可達(dá)性：無(wú)法再?gòu)某绦蜃兞窟M(jìn)行訪問(wèn)，堆內(nèi)存塊的生命周期結(jié)束。

(3)活躍度：在最后一次訪問(wèn)該內(nèi)存塊之后，堆內(nèi)存塊的生命周期結(jié)束。

其中，可達(dá)性在控制流分析中更為直觀，若內(nèi)存塊的生命周期結(jié)束而指針不可達(dá)，則程序中發(fā)生內(nèi)存泄漏。除了內(nèi)存塊生命周期外，還需分析指針的生命周期。圖2表示C程序中指向堆內(nèi)存的指針p的生命周期，顯示了指針p從被聲明到被釋放的全部過(guò)程。實(shí)線箭頭表示程序中正確執(zhí)行的順序，虛線箭頭表示可能導(dǎo)致指針p引用的內(nèi)存塊上發(fā)生泄漏的所有情況。例如，虛線箭頭5表示指針p在分配內(nèi)存塊前未被初始化，虛線箭頭6表示指針p在被訪問(wèn)之前未被分配內(nèi)存塊，虛線箭頭7表示指針p釋放內(nèi)存塊之前未被分配內(nèi)存塊。由此可見(jiàn)，若程序或運(yùn)行時(shí)系統(tǒng)在堆內(nèi)存塊的生命周期結(jié)束時(shí)沒(méi)有指針回收其內(nèi)存，會(huì)造成內(nèi)存泄漏。

Figure 2 Pointer liveness圖2 指針生命周期

因此，檢測(cè)內(nèi)存泄漏本質(zhì)上是分析相應(yīng)內(nèi)存塊的生命周期在控制流圖的每個(gè)分支中結(jié)束時(shí)是否釋放了內(nèi)存指針。

3 PACV檢測(cè)分析

本節(jié)提出PACV用于檢測(cè)C程序的內(nèi)存泄漏，工作流程分為2個(gè)階段：路徑敏感的值流信息構(gòu)建與基于值流約束的泄漏檢測(cè)。首先基于指向信息構(gòu)建值流，然后利用值流約束檢測(cè)內(nèi)存泄漏，最后通過(guò)程序中分配位置和釋放位置的指針以及內(nèi)存塊的生命周期信息對(duì)泄漏對(duì)象進(jìn)行驗(yàn)證。

3.1 基于指針?lè)治龅闹盗鳂?gòu)建

指針?lè)治鯷18]通過(guò)解析變量的讀寫(xiě)信息，分析出變量在程序運(yùn)行時(shí)可能指向的對(duì)象集合，得到被分析程序在運(yùn)行時(shí)指針的指向信息[19]。

本小節(jié)將程序抽象為一組函數(shù)Fun、一組變量V和一組語(yǔ)句S，據(jù)此對(duì)C程序進(jìn)行抽象模型描述，如下所示：

s∷u=v|u=malloc(n)|u=*v|*u=v|

free(u)|s;s|if(Cond) thenselses′

該模型代表了C語(yǔ)言中內(nèi)存操作的最簡(jiǎn)語(yǔ)句，其中語(yǔ)句s包含了賦值語(yǔ)句(u=v,u=*v,*u=v)、內(nèi)存分配語(yǔ)句(u=mallco(n))、內(nèi)存釋放語(yǔ)句(free(u))，其中內(nèi)存分配語(yǔ)句malloc(n)表示一般情況。

通常，指針?lè)治雒枋鲆韵?個(gè)集合中的元素之間的關(guān)系：

(1)語(yǔ)句集合S，主要包含指針變量的集合。其中Snull表示指針變量為NULL，該指針變量指向未被分配的內(nèi)存塊。

(2)內(nèi)存位置集合M，它代表了由賦值語(yǔ)句生成的對(duì)象。

(3)指針映射集合T，在分析程序語(yǔ)句的過(guò)程中動(dòng)態(tài)生成，反映了程序中的指針和內(nèi)存地址之間的映射關(guān)系[20]。

(4)指針域的集合F。變量v通過(guò)指針域構(gòu)成指向關(guān)系，表現(xiàn)為被指向的內(nèi)存結(jié)點(diǎn)的地址存儲(chǔ)在指向的內(nèi)存結(jié)點(diǎn)中[8]。

根據(jù)集合元素之間的分析結(jié)果，描述程序中賦值語(yǔ)句產(chǎn)生的變量和對(duì)象之間的指向關(guān)系，如圖3所示。

(1)圖中結(jié)點(diǎn)包括指針結(jié)點(diǎn)x和y，內(nèi)存對(duì)象結(jié)點(diǎn)o1和o2，以對(duì)象生成語(yǔ)句所在行號(hào)命名。

(2)t1表示從指針變量結(jié)點(diǎn)到內(nèi)存對(duì)象結(jié)點(diǎn)o1的映射，表示在運(yùn)行時(shí)可能訪問(wèn)內(nèi)存對(duì)象結(jié)點(diǎn)o1。

(3)由x=y的賦值語(yǔ)句，從內(nèi)存對(duì)象結(jié)點(diǎn)o1到o2的邊，表示o1的指針域可能指向o2[21]。

Figure 3 Point-to graph圖3 指向圖

若存在指針變量z指向內(nèi)存對(duì)象結(jié)點(diǎn)o，且有賦值語(yǔ)句t=z，則z與內(nèi)存對(duì)象結(jié)點(diǎn)o存在間接指向訪問(wèn)關(guān)系。直接指向關(guān)系和間接指向關(guān)系共同組成程序中完整的指向關(guān)系。通過(guò)計(jì)算指向集合的傳遞閉包，可以獲得完整的指向關(guān)系集合。

對(duì)于間接指向關(guān)系的處理，PACV使用可擴(kuò)展的全局指針別名分析來(lái)確定哪些指針變量可能彼此別名，別名信息用抽象內(nèi)存位置的命名空間表示。為獲得更高的精度，根據(jù)其訪問(wèn)路徑確定位置。根據(jù)指針?lè)治隹梢垣@得每個(gè)變量v的指向集ps(v)，每個(gè)指向目標(biāo)都是抽象棧位置(本地或全局變量)或抽象堆對(duì)象。

由于內(nèi)存泄漏檢測(cè)與指針?lè)治雒芮邢嚓P(guān)，因此，現(xiàn)有的許多內(nèi)存泄漏研究將其檢測(cè)方法構(gòu)造為特殊的指針?lè)治?。本文將指針?lè)治鲎鳛楠?dú)立的一部分，以便以后可以重用不同的指針?lè)治鏊惴ǎ岣叻治鲂省?/p>

Table 1 Variables Def-Use information

定義1過(guò)程內(nèi)Def-Use關(guān)系：RIntra(l,l′,v),表示過(guò)程內(nèi)控制流路徑P上v從l到l′的Def-Use關(guān)系，其中v是程序中的變量，在這之間沒(méi)有進(jìn)行重新定義，即:

?/l″∈P:l″∈Defv

定義2過(guò)程間Def-Use關(guān)系：RIntra(l,l′,func(v)),表示過(guò)程間控制流路徑P上v從l到l′的Def-Use關(guān)系,其中l(wèi)與l′在2個(gè)不同方法內(nèi)，在這之間沒(méi)有進(jìn)行重新定義，即:

?/l″∈P:l″∈Deffunc(v)

根據(jù)上文C程序的抽象模型描述，表1列出從語(yǔ)句中提取的變量Def-Use信息。對(duì)于NULL、COPY語(yǔ)句，可以直接讀取其Def-Use信息。對(duì)于LOAD或STORE語(yǔ)句，必須考慮間接訪問(wèn)對(duì)象的Def-Use信息。其中，ps(v)表示從需求驅(qū)動(dòng)的上下文相關(guān)指針?lè)治霁@得的變量v的指向集；對(duì)于方法調(diào)用CALL、METHOD和RET，可以直接獲得變量v的Def-Use信息。

基于指針?lè)治鲋械闹赶蛐畔?gòu)建值流信息，捕獲程序間引用和程序變量的修改副作用，使用別名集合對(duì)每個(gè)LOAD、STORE、CALL語(yǔ)句的間接Def-Use進(jìn)行注釋?zhuān)總€(gè)別名集合代表一組可以間接訪問(wèn)的抽象內(nèi)存對(duì)象。

SVFA是一種廣泛用于內(nèi)存泄漏檢測(cè)的值流分析方法，它沿?cái)?shù)據(jù)依賴(lài)關(guān)系跟蹤VFG而不是CFG，可以跳過(guò)無(wú)關(guān)的程序語(yǔ)句以實(shí)現(xiàn)可擴(kuò)展性。但是，由于缺少必要的控制流信息，SVFA方法缺乏路徑敏感性，導(dǎo)致檢測(cè)結(jié)果誤報(bào)率高，不夠準(zhǔn)確。本文在VFG上結(jié)合必要的控制流信息，不僅對(duì)變量的Def進(jìn)行編碼，還對(duì)相關(guān)的堆對(duì)象的Use進(jìn)行編碼，同一個(gè)內(nèi)存對(duì)象的Use位置根據(jù)控制流進(jìn)行排序，從而檢查內(nèi)存泄漏。同時(shí)，通過(guò)創(chuàng)建終結(jié)結(jié)點(diǎn)模擬對(duì)象的生命周期，表明不再引用p指向的堆對(duì)象。其中數(shù)據(jù)依賴(lài)關(guān)系記為：p@lm→p@ln，表示p指向的內(nèi)存分配對(duì)象可以在語(yǔ)句ln處釋放(li表示第i行的語(yǔ)句)，也可以理解為值流邊。最終達(dá)到對(duì)程序變量的整個(gè)生命周期進(jìn)行建模的效果，將擴(kuò)展之后的SVFA(Sparse Value Flow)對(duì)應(yīng)值流圖記為擴(kuò)展值流圖E-SVFG(Extend SVFG)，仍然沿用稀疏值流圖SVFG的稀疏性質(zhì)，跳過(guò)不相關(guān)語(yǔ)句。

定義3程序的E-SVFG使用有向圖G=(N,E)表示，其中N是結(jié)點(diǎn)集合，E是邊集合：

(1)o@p∈N表示程序點(diǎn)p處的對(duì)象為o。

(2)當(dāng)o1和o2表示同一對(duì)象且存在從p1到p2的控制流路徑時(shí)，有向邊(o1@p1,o2@p2)∈E。

3.2 基于路徑敏感的值流分析的內(nèi)存泄漏檢測(cè)

將程序的內(nèi)存空間劃分為一組抽象內(nèi)存位置M。抽象內(nèi)存函數(shù)mem:S→M，實(shí)現(xiàn)給定語(yǔ)句到抽象內(nèi)存位置的映射。通過(guò)將所有訪問(wèn)映射到它們的抽象內(nèi)存位置，可以通過(guò)直接訪問(wèn)處理間接訪問(wèn)。此外，由于抽象內(nèi)存位置可以表示多個(gè)物理位置，存儲(chǔ)新值不會(huì)覆蓋舊值，因此對(duì)抽象內(nèi)存位置的新定義被稱(chēng)為弱更新，添加新值而不破壞舊值。用ζ函數(shù)來(lái)表示弱更新。

定義4ζ函數(shù)形式如下所示：

d=ζ(d1,d2)

ζ函數(shù)有2個(gè)操作數(shù)，第1個(gè)操作數(shù)d1表示分配的新值，第2個(gè)操作數(shù)d2表示保留的舊值。由于d2本身可以被賦予ζ函數(shù)，所以可以將所有操作數(shù)向前傳遞追溯，直到ζ函數(shù)找到分配給抽象內(nèi)存位置定義的所有值。

為了對(duì)控制流信息進(jìn)行更具體的描述，給出定義5。

定義5θ函數(shù)形式如下所示：

d=θ(〈p1,d1〉,〈p2,d2〉,…,〈pn,dn〉)

其中,d為變量的定義；pi(i≤i≤n)為謂詞，在多條控制流路徑匯合處，若新的謂詞p成立，則新定義d成立。通過(guò)構(gòu)造控制流的程序表達(dá)，可經(jīng)一處Def達(dá)到某個(gè)變量的多處Use。θ函數(shù)的定義操作數(shù)本身可以是θ。函數(shù)的定義，可以通過(guò)計(jì)算操作數(shù)的傳遞閉包來(lái)找到由θ函數(shù)定義的變量的所有可能值。

為減少誤報(bào)，增加路徑敏感性尤為重要。如表2所示，路徑不敏感分析會(huì)推斷出x可能指向a或者NULL，導(dǎo)致第13行上的*x會(huì)因解引用NULL而發(fā)生ERROR。然而分析程序路徑顯示，只有當(dāng)Cond在第13行成立時(shí)才會(huì)解引用，也就是x只能指向a。

Table 2 Path-sensitive analysis

訪問(wèn)路徑是指解引用和字段訪問(wèn)操作的組合，若訪問(wèn)路徑不包含迭代的解引用或字段訪問(wèn)操作，則簡(jiǎn)單很多。函數(shù)的局部變量、參數(shù)、全局變量作為函數(shù)訪問(wèn)位置。訪問(wèn)位置的內(nèi)容以路徑敏感形式進(jìn)行跟蹤。用直接訪問(wèn)替代間接訪問(wèn)，每個(gè)變量的定義或使用全部用θ函數(shù)表達(dá)，通過(guò)將其映射到抽象內(nèi)存位置來(lái)分析其他所有訪問(wèn)。

根據(jù)表2分析可知，第11行if語(yǔ)句末尾的θ函數(shù)表明：當(dāng)Cond為真，變量x表達(dá)為x0；當(dāng)Cond為假，則為x1。著重分析第13行的間接訪問(wèn)*x，x的有效定義是x2。當(dāng)Cond為真，x2與x0相同，其值為&a，因此*x的有效定義是a,a1；當(dāng)Cond為假，x2由x1給出，其值為NULL，解引用NULL產(chǎn)生錯(cuò)誤。*x的這2個(gè)可能值由2個(gè)新定義t1、t2的θ函數(shù)表示。由此說(shuō)明如何表示間接訪問(wèn)的Def-Use關(guān)系。

給定程序，構(gòu)建其過(guò)程間控制流圖即ICFG(Interprocedural Control Flow Graph)。函數(shù)中的節(jié)點(diǎn)分為調(diào)用節(jié)點(diǎn)和返回節(jié)點(diǎn)，邊分為從調(diào)用節(jié)點(diǎn)到函數(shù)入口節(jié)點(diǎn)的調(diào)用邊以及從函數(shù)的出口節(jié)點(diǎn)到返回節(jié)點(diǎn)的返回邊。為執(zhí)行上下文敏感分析，變量v的pt({ci},v)(其中ci表示變量v的調(diào)用位置)返回結(jié)果為包含ci的函數(shù)調(diào)用序列的變量v的指向集。因此，pt({},vl)給出在所有調(diào)用上下文中第l行的v的指向集。

為執(zhí)行路徑敏感分析，通過(guò)調(diào)用上下文c和路徑保護(hù)ρ來(lái)表示抽象路徑，c指定其調(diào)用序列，ρ收集其分支條件。定義pt({c,ρ},v)，給出在{c,ρ}下的第l行的v的指向集。在函數(shù)f中，每個(gè)分支條件被看作一個(gè)布爾表達(dá)式。對(duì)于一條控制流邊e，ControlGuard(e)是執(zhí)行e的分支條件；對(duì)于一組控制流邊e組成的控制流路徑cp，cp的條件是每條e的分支條件的邏輯合取:

ControlGuard(cp)=

{∧ControlGuard(e)|e∈cp}

從語(yǔ)句l到語(yǔ)句l′的路徑保護(hù)Guard(l,l′)是由所有控制流路徑的路徑條件的邏輯析取：

Guard(l,l′)={∨

ControlGuard(cp)|cp∈Path(l,l′)}

其中Path(l,l′)表示從l到l′的控制流路徑集。

由此，根據(jù)上述定義收集從入口main()到某條語(yǔ)句的路徑保護(hù)Guard(l,l′)。由于路徑條件可能出現(xiàn)矛盾的情況，用true與false表示可行與不可行路徑。

根據(jù)計(jì)算值流邊上的保護(hù)信息，以捕獲程序中值流發(fā)生的路徑條件，用于推斷所有路徑上的釋放點(diǎn)的可達(dá)性。設(shè)定在內(nèi)存分配結(jié)點(diǎn)創(chuàng)建的對(duì)象為src，在內(nèi)存釋放結(jié)點(diǎn)創(chuàng)建的對(duì)象為sink，編碼路徑之后，開(kāi)始分析可達(dá)性。

部分路徑分析：Fsrc為前向切片，由VFG中src可以到達(dá)的結(jié)點(diǎn)組成，Ssrc為Fsrc到達(dá)的釋放結(jié)點(diǎn)集合，若Ssrc為空，則src肯定發(fā)生泄漏，因?yàn)榇朔N情況下，不會(huì)沿某些控制流路徑到達(dá)sink(釋放結(jié)點(diǎn))。如果src沿著一些控制流路徑到達(dá)全局變量，則泄漏檢測(cè)終止，認(rèn)為src沒(méi)有泄漏。

路徑分析：Bsrc為一個(gè)后向切片，包含src到Ssrc中的sink的路徑上的節(jié)點(diǎn)。然后執(zhí)行全路徑分析來(lái)檢查一個(gè)src在每條控制流上至少可達(dá)Ssrc中的一個(gè)sink，如果src在某些控制流路徑上無(wú)法到達(dá)Ssrc中的sink，則發(fā)出泄漏警告，這是一種條件性泄漏，只有在某些路徑條件下才會(huì)觸發(fā)。

根據(jù)控制流路徑保護(hù)信息，解決全路徑可達(dá)性問(wèn)題，vfPath(src,sink)是VFG中從src到sink的所有值流路徑集，對(duì)于每條值流路徑VP∈vfPath(src,sink)，Guard(VP)編碼在程序中從src到sink的控制流路徑集。此外，為降低分析難度，遞歸與循環(huán)均展開(kāi)一次。因此，有以下定義：

HasFree(src)={∨Guard(VP)|

VP∈vfPath(src,sink),sink∈Ssrc}

如果HasFree(src)≠true，則發(fā)出泄漏警告，表示src沿著HasFree中的控制流路徑發(fā)生泄漏。此外，在分配點(diǎn)之后插入對(duì)Add()的調(diào)用，以跟蹤內(nèi)存中的所有已分配對(duì)象。在從相應(yīng)的分配結(jié)點(diǎn)可到達(dá)的每個(gè)釋放結(jié)點(diǎn)之后插入對(duì)Delete()的調(diào)用，以刪除釋放的對(duì)象。首先，程序的VFG非常逼近變量的Def-Use關(guān)系，路徑分析可靠性大大提高；其次，Add()和Delete()維護(hù)有效的內(nèi)存地址，記錄其生命期，對(duì)于產(chǎn)生的內(nèi)存泄漏進(jìn)行驗(yàn)證，剔除部分誤報(bào)。鑒于以上2個(gè)原因，得出的分析結(jié)果更為準(zhǔn)確。

根據(jù)上文所提方法設(shè)計(jì)的算法主要包括wlMod和Check_MemeoryLeak 2個(gè)算法，如算法1和算法2所示。

算法1wlMod算法

input：the C program。

output：Wstore Def-Use chain in statements。

1 whilef∈FCGis not empty

2W=?;

3 foreachs∈Succ(n) inCFGf

4switch(s){

5 case assignment statements:e0=e1:

6Mods=ζ(e0,graph(s));

7 case call statements:e=p():

8Mods=ζ(e,graph(s));

9 }

10 foreach producrepr

11Mod(pr)=∪s∈stm(pr)Mod(s);

12W=W∪{pr};

13 endfor

14 endwhile

算法1首先通過(guò)worklist設(shè)計(jì)迭代算法wlMod，進(jìn)行后向分析。從程序CFG入口處的第1個(gè)變量定義處，即第1個(gè)指針賦值語(yǔ)句處生成初始化信息，將信息向后傳播。其中，F(xiàn)CG表示程序過(guò)程調(diào)用圖，f為程序過(guò)程調(diào)用圖中的函數(shù)，CFGf表示為每個(gè)函數(shù)生成的CFG，Succ(n)表示 CFG上語(yǔ)句n的所有后繼語(yǔ)句。從FCG中自頂向下選擇函數(shù)，為CFGf中每個(gè)程序點(diǎn)生成初始內(nèi)存信息。

算法2Check_MemoryLeak算法

input： statementS,HasFree(src)。

output：reportMemoryLeak。

1 begin

2 foreachs∈S

3switch(s){

4 cases:e0=e1:

5 for(go throughdleft)

6 if(dleft→mem)

7DeleteTA(dleft→mem);

8 if(dright→mem)

9 for(go throughdleft)

10 AddTA(dleft→mem),TB(dleft);

11 if(malloc(n)):

12 for(go throughdleft)

13 AddTA(dleft→mem),TB(dleft);

14 cases:free(u):

15 for(go throughdleft)

16 DeleteTA(dleft→mem),TB(dleft);}

17 end for

18 if(TAdidn′t includesrc(dleft→mem)&&

19TBincludesrc(dleft))

20 reportMemoryLeak_Error;

21 end

算法2從程序入口處開(kāi)始，處理變量的Def-Use關(guān)系，為編碼路徑做基礎(chǔ)，分析布爾表達(dá)式的正確性，識(shí)別可能存在泄漏的路徑。為提高檢測(cè)的準(zhǔn)確性，對(duì)內(nèi)存塊進(jìn)行生命周期監(jiān)測(cè)。上文定義的指針映射集T，是在分析程序語(yǔ)句的過(guò)程中動(dòng)態(tài)生成的，它反映了程序中的指針和內(nèi)存地址之間的映射關(guān)系。為了對(duì)分配的動(dòng)態(tài)內(nèi)存塊以及其與指針的關(guān)系進(jìn)行跟蹤，算法2將指針映射集分為2個(gè)部分：(1)指針與分配的動(dòng)態(tài)內(nèi)存塊的映射TA，多個(gè)指針可指向同一塊動(dòng)態(tài)內(nèi)存。(2)分配的動(dòng)態(tài)內(nèi)存塊與指針集合的映射TB，存放所有指向動(dòng)態(tài)內(nèi)存塊的指針[23]；同時(shí)也分為2個(gè)操作：Add()和Delete()，分別對(duì)應(yīng)內(nèi)存塊和指針的插入和刪除，其中dleft,dright是語(yǔ)句的左操作數(shù)和右操作數(shù)。遍歷程序CFG的每條路徑進(jìn)行檢測(cè)，針對(duì)不同的結(jié)點(diǎn)進(jìn)行不同的處理。主要分為2種語(yǔ)句處理：(1)賦值語(yǔ)句：如p1=p2=p，可能有多個(gè)左操作數(shù)，那么，算法進(jìn)行遍歷，查找其在TA中是否有記錄，若有則刪除。然后判斷dright的類(lèi)型：①指針：查找dleft在TA中是否有記錄，若沒(méi)有則處理結(jié)束；若有根據(jù)對(duì)應(yīng)的內(nèi)存塊M，在TA中添加dleft→M，在TB中的M對(duì)應(yīng)的指針集合中添加dleft。②內(nèi)存分配函數(shù)：生成內(nèi)存塊M，在TA中添加dleft→M，在TB中添加M。(2)處理內(nèi)存釋放函數(shù)：根據(jù)dleft刪除TA和TB中有關(guān)M的所有記錄。最后根據(jù)檢測(cè)出的警報(bào)信息，驗(yàn)證TA和TB是否為內(nèi)存泄漏錯(cuò)誤。

Figure 4 Class diagram of implementation圖4 實(shí)現(xiàn)類(lèi)圖

4 實(shí)驗(yàn)分析

本節(jié)根據(jù)PACV研究框架以及實(shí)現(xiàn)算法，對(duì)實(shí)際程序中出現(xiàn)的內(nèi)存泄漏進(jìn)行分析。原型工具的設(shè)計(jì)思想如下：首先將源程序通過(guò)抽象語(yǔ)法樹(shù)AST(Abstract Syntax Tree)轉(zhuǎn)化為中間語(yǔ)言程序，在中間語(yǔ)言程序上提取指針別名信息和控制流信息，在此基礎(chǔ)上構(gòu)建路徑敏感的值流信息，利用值流約束檢測(cè)內(nèi)存泄漏。

為了滿(mǎn)足檢測(cè)需求和具體方法實(shí)現(xiàn)設(shè)計(jì)的目標(biāo)和原則，從功能和執(zhí)行邏輯上，將原型工具分為2個(gè)模塊：代碼預(yù)處理模塊和內(nèi)存泄漏檢測(cè)模塊。應(yīng)用SVFG、CFG分析技術(shù)定制的算法。源程序經(jīng)過(guò)編譯前端處理后獲得AST，然后生成中間語(yǔ)言程序，獲取變量的Def-Use鏈，結(jié)合必要控制流信息進(jìn)行內(nèi)存泄漏路徑約束檢測(cè)。圖4是原型工具實(shí)現(xiàn)類(lèi)圖。

程序的源文件首先由CLANG前端使用 “-O0”編譯，然后使用LLVM Gold鏈接，以生成整個(gè)程序bc文件。基于開(kāi)源工具SVF[24]計(jì)算Def-Use鏈，增加路徑敏感性分析；路徑保護(hù)使用二進(jìn)制決策圖編碼；路徑可行性由Z3求解器檢查。實(shí)驗(yàn)結(jié)果通過(guò)2個(gè)問(wèn)題來(lái)證明PACV在檢測(cè)實(shí)際程序中的內(nèi)存泄漏時(shí)是有效且精確的：

問(wèn)題1在檢測(cè)現(xiàn)有的內(nèi)存泄漏錯(cuò)誤時(shí)是否有效？

問(wèn)題2PACV在大型程序中不增加時(shí)耗的情況下是否仍能有效查找漏洞？

4.1 案例分析

本小節(jié)使用基于路徑敏感的值流分析的內(nèi)存泄漏檢測(cè)方法檢測(cè)圖5中案例程序中存在2處泄漏的原因。此案例程序改編自發(fā)生在wine中的真實(shí)場(chǎng)景(wine是實(shí)驗(yàn)中用到的一個(gè)應(yīng)用程序)。在圖5a中，main函數(shù)中的for循環(huán)中調(diào)用了allocM，每次調(diào)用都會(huì)創(chuàng)建1個(gè)由2個(gè)對(duì)象組成的單字符緩沖區(qū)：L13的o，L14的o′。存在2種情況：如果緩沖區(qū)包含的字符是‘noleak’，則打印該字符，然后釋放o和o′；如果緩沖區(qū)包含的字符不是‘noleak’，則o和o′都會(huì)泄漏。

(1)指針?lè)治?。獲得指針別名信息：

ps(o)={o′}

ps(input)=ps(q)=ps(q)={o}

(2)值流構(gòu)建。引入R表示{o}，其中o是在L13創(chuàng)建的抽象堆對(duì)象。根據(jù)指針?lè)治鼋Y(jié)果，R與*input，*p和*q彼此之間別名。對(duì)程序中LOAD、STORE、CALL和RETURN語(yǔ)句進(jìn)行分析，獲取程序變量之間的Def-Use關(guān)系。例如，根據(jù)表1定義，l13屬于STORE語(yǔ)句,描述為定義R，l4和l19的LOAD語(yǔ)句使用R(對(duì)其讀取)，l3的CALL語(yǔ)句在allocM中重定義R(對(duì)其修改)，l9的CALL語(yǔ)句在freeM中使用R(對(duì)其讀取)，最后R被隱式返回給main函數(shù)，在l16添加返回信息。如圖5b所示，該圖通過(guò)分配o和o′捕獲Def-Use信息和值流。

(3)泄漏檢測(cè)?；诼窂矫舾械闹盗?，每個(gè)分配位置根據(jù)VFG的可達(dá)性判斷o和o′是否泄漏。每條Def-Use邊都含有其路徑保護(hù)信息，在程序ICFG上捕獲Def-Use之間的分支條件，所有路徑保護(hù)信息按需生成，如圖5c所示。當(dāng)o和o′沿if分支,則到達(dá)釋放點(diǎn)，當(dāng)o和o′沿else分支,則2個(gè)對(duì)象發(fā)生泄漏，如圖5d所示。

a 程序案例

b 值流構(gòu)建

c值流信息約束

d 泄漏路徑識(shí)別

4.2 程序集分析

為回答針對(duì)實(shí)驗(yàn)評(píng)估提出的2個(gè)問(wèn)題，被測(cè)程序的選取分為2個(gè)部分：第1部分是對(duì)經(jīng)典的堆操作程序進(jìn)行分析，包括鏈表和樹(shù)操作程序，覆蓋了第2節(jié)所列舉的全部?jī)?nèi)存泄漏場(chǎng)景，如表3所示。表3中的前5個(gè)程序來(lái)自文獻(xiàn)[25]的不同類(lèi)型的鏈表程序，分別是創(chuàng)建一定長(zhǎng)度的鏈表、在鏈表中有序地插入一個(gè)元素、刪除元素、判斷鏈表中是否含有某個(gè)元素和鏈表逆置，后2個(gè)程序是文獻(xiàn)[26]中的樹(shù)操作程序。第2部分是選取表4中列出的14個(gè)SPEC2000C程序，將實(shí)驗(yàn)效果與CLANG中一個(gè)靜態(tài)分析器(符號(hào)執(zhí)行)和FASTCHECK(SVFA)進(jìn)行比較，選取這2個(gè)工具是因?yàn)樗鼈児_(kāi)可用，使用率高且趨于成熟。評(píng)估時(shí)考慮2個(gè)標(biāo)準(zhǔn)：(1)效率，即分析時(shí)間；(2)準(zhǔn)確率，即低誤報(bào)檢測(cè)內(nèi)存泄漏的能力。

Table 3 Typical program analysis

由表3和表4的分析結(jié)果可知，PACV實(shí)現(xiàn)了之前所述的設(shè)計(jì)目標(biāo)。表3顯示在鏈表插入程序中，含有1個(gè)誤報(bào)，說(shuō)明PACV在檢測(cè)現(xiàn)有的典型錯(cuò)誤案例時(shí)還是非常有效的。表4顯示 PACV在119個(gè)泄漏警告中檢測(cè)到85個(gè)故障，F(xiàn)ASTCHECK在165個(gè)警告中檢測(cè)到90個(gè)故障，CLANG在47個(gè)泄漏警告中檢測(cè)到40個(gè)故障，相比其他2個(gè)工具要少得多?？偟膩?lái)說(shuō)，PACV速度比FASTCHECK慢，但誤報(bào)率低約28%，更加精確；CLANG的誤報(bào)率低，但CLANG是過(guò)程內(nèi)的這一局限性，即單獨(dú)分析函數(shù)而不考慮其調(diào)用函數(shù)和被調(diào)用函數(shù)，外部信息被假設(shè)為未知信息，無(wú)法分析在被調(diào)用函數(shù)中創(chuàng)建的對(duì)象，從而導(dǎo)致CLANG漏掉許多錯(cuò)誤。對(duì)比其他2個(gè)工具可知，PACV在保證一定速度的同時(shí)仍能保證一定的精確性。

作為靜態(tài)分析方法，PACV仍然受限于誤報(bào)和漏報(bào)2大固有缺陷。誤報(bào)的發(fā)生有以下原因：某些不可行的路徑無(wú)法識(shí)別，分析時(shí)限制循環(huán)迭代次數(shù)以及保守分析內(nèi)存塊的別名信息存在不準(zhǔn)確性。漏報(bào)的發(fā)生有以下原因：對(duì)數(shù)組別名訪問(wèn)的不健全建模，分析循環(huán)或遞歸的前n項(xiàng)有限次展開(kāi)和對(duì)堆建模不精確性。此外，和許多方法一樣，PACV處理指針別名分析時(shí)不完全準(zhǔn)確。

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

C語(yǔ)言作為安全關(guān)鍵軟件的主要實(shí)現(xiàn)語(yǔ)言，執(zhí)行效率高，使用范圍廣，然而在廣泛應(yīng)用的同時(shí)，存在的安全問(wèn)題也不容忽視。通過(guò)大量實(shí)際項(xiàng)目分析得知，C程序出現(xiàn)最多的安全問(wèn)題就是與內(nèi)存相關(guān)的缺陷問(wèn)題，其中內(nèi)存泄漏就是一種常見(jiàn)的缺陷形式。內(nèi)存泄漏缺陷具有很高的隱蔽性和危害性，會(huì)造成難以估計(jì)的損失。

針對(duì)廣泛應(yīng)用于內(nèi)存泄漏的SVFA分析技術(shù)缺乏路徑敏感的問(wèn)題，本文提出基于路徑敏感的值流分析的內(nèi)存泄漏檢測(cè)方法PACV。在中間代碼上提取指針別名信息與控制流信息，基于指針別名信息構(gòu)建值流信息，由于SVFA技術(shù)缺乏路徑敏感性，因此在值流信息上結(jié)合控制流信息引入路徑敏感性。最后根據(jù)路徑敏感的值流約束檢測(cè)程序是否含有內(nèi)存泄漏，在程序分配結(jié)點(diǎn)和釋放結(jié)點(diǎn)增加Add()和Delete()2個(gè)函數(shù)維護(hù)有效的內(nèi)存地址，記錄其生命期，對(duì)產(chǎn)生的內(nèi)存泄漏進(jìn)行驗(yàn)證。本文方法與現(xiàn)有的研究工作相比，提高了內(nèi)存泄漏檢測(cè)結(jié)果的準(zhǔn)確性，具有一定的意義。

Table 4 Comparision with other tools(T:True Alarms;F:False Positves)

基于本文現(xiàn)有工作，今后在以下方面進(jìn)行進(jìn)一步的研究，包括：結(jié)合更加完備的指針別名算法，提升路徑分析的計(jì)算精度，加強(qiáng)誤報(bào)情況的約減計(jì)算。