C程序中的內存泄漏機制分析與檢測方法設計*

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

(1.南京航空航天大學計算機科學與技術學院， 江蘇 南京 211106; 2.南京航空航天大學高安全系統的軟件開發與驗證技術工業和信息化部重點實驗室,江蘇 南京 211106)

1 引言

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

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

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

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

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

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

為了在查找精度和效率上達到平衡，本文針對廣泛應用于內存泄漏的SVFA技術缺乏路徑敏感的問題，通過結合控制流信息引入路徑敏感性，來提高檢測準確性。本文提出了一種基于指針分析構建路徑敏感的值流約束檢測內存泄漏的方法，簡稱PACV(Pointer Analysis and Control-flow Value Guard)研究方法。

2 內存泄漏機制分析

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

從程序執行的角度，在任何程序執行路徑中，在分配點(source)創建的每個對象最終必須至少到達一個釋放點(sink)。

2.1 場景分析

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

場景1內存管理關鍵字或函數使用不當。

從2018年1月至2019年4月，CVE中就有3條相關漏洞信息，由于程序結構復雜、人員疏忽導致使用了錯誤的釋放方法。內存分配和釋放是相互匹配出現的，成對使用這些關鍵字或函數是內存動態分配使用的基本原則，調用了內存分配函數卻沒有調用釋放函數會導致泄漏。此場景屬于最基本的場景，針對這種類型的內存泄漏檢測也相對簡單，通常是在函數入口處初始化指針內存的分配情況，在函數出口處對比函數內的分配和釋放操作來判定是否存在已經分配內存的指針沒有被釋放的情況[17]。

場景2程序邏輯缺陷。

雖然程序中分配和釋放函數成對出現，并未出現錯配或者漏配的情況，但由于程序本來的一些缺陷，仍會導致內存泄漏。函數在程序入口處分配了內存，但在最后釋放之前，分支語句內的代碼提前返回發生異常，那么就引發了內存泄漏。若函數里的邏輯非常復雜，或者異常情況不是必現，那么查找內存泄漏點則更加困難。

場景3指針重新賦值。

指針變量p和np分別被分配了5字節的內存。如果程序需要執行賦值語句p=np，指針變量p被np指針重新賦值，導致p之前所指向的內存位置變成了孤立的內存。因為沒有指向該內存的引用，它無法進行釋放，從而導致5字節的內存泄漏。

場景4錯誤的內存釋放。

假設有一個指針變量p，它指向一個5字節的內存位置。該內存位置的第2字節又指向某個新的動態分配的5字節的內存位置。如果通過調用free來釋放了最初的內存塊，則新分配的內存變成了孤立的內存，導致了內存泄漏。

場景5返回值的錯誤處理。

某些函數會返回對動態分配的內存的引用，主函數中調用f函數，但未處理該內存位置的返回地址導致f函數所分配的5字節的內存塊丟失，造成內存泄漏。

2.2 原因分析

根據上述場景分析可知，內存泄漏與指針及其關聯內存操作相關，因此根本原因分析應從內存塊與指針的生命周期展開。內存塊的生命周期可用3種方式表示：

(1)引用：當沒有對內存塊的引用時，堆內存塊的生命周期結束。

(2)可達性：無法再從程序變量進行訪問，堆內存塊的生命周期結束。

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

其中，可達性在控制流分析中更為直觀，若內存塊的生命周期結束而指針不可達，則程序中發生內存泄漏。除了內存塊生命周期外，還需分析指針的生命周期。圖2表示C程序中指向堆內存的指針p的生命周期，顯示了指針p從被聲明到被釋放的全部過程。實線箭頭表示程序中正確執行的順序，虛線箭頭表示可能導致指針p引用的內存塊上發生泄漏的所有情況。例如，虛線箭頭5表示指針p在分配內存塊前未被初始化，虛線箭頭6表示指針p在被訪問之前未被分配內存塊，虛線箭頭7表示指針p釋放內存塊之前未被分配內存塊。由此可見，若程序或運行時系統在堆內存塊的生命周期結束時沒有指針回收其內存，會造成內存泄漏。

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

因此，檢測內存泄漏本質上是分析相應內存塊的生命周期在控制流圖的每個分支中結束時是否釋放了內存指針。

3 PACV檢測分析

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

3.1 基于指針分析的值流構建

指針分析[18]通過解析變量的讀寫信息，分析出變量在程序運行時可能指向的對象集合，得到被分析程序在運行時指針的指向信息[19]。

本小節將程序抽象為一組函數Fun、一組變量V和一組語句S，據此對C程序進行抽象模型描述，如下所示：

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

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

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

通常，指針分析描述以下4個集合中的元素之間的關系：

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

(2)內存位置集合M，它代表了由賦值語句生成的對象。

(3)指針映射集合T，在分析程序語句的過程中動態生成，反映了程序中的指針和內存地址之間的映射關系[20]。

(4)指針域的集合F。變量v通過指針域構成指向關系，表現為被指向的內存結點的地址存儲在指向的內存結點中[8]。

根據集合元素之間的分析結果，描述程序中賦值語句產生的變量和對象之間的指向關系，如圖3所示。

(1)圖中結點包括指針結點x和y，內存對象結點o1和o2，以對象生成語句所在行號命名。

(2)t1表示從指針變量結點到內存對象結點o1的映射，表示在運行時可能訪問內存對象結點o1。

(3)由x=y的賦值語句，從內存對象結點o1到o2的邊，表示o1的指針域可能指向o2[21]。

Figure 3 Point-to graph圖3 指向圖

若存在指針變量z指向內存對象結點o，且有賦值語句t=z，則z與內存對象結點o存在間接指向訪問關系。直接指向關系和間接指向關系共同組成程序中完整的指向關系。通過計算指向集合的傳遞閉包，可以獲得完整的指向關系集合。

對于間接指向關系的處理，PACV使用可擴展的全局指針別名分析來確定哪些指針變量可能彼此別名，別名信息用抽象內存位置的命名空間表示。為獲得更高的精度，根據其訪問路徑確定位置。根據指針分析可以獲得每個變量v的指向集ps(v)，每個指向目標都是抽象棧位置(本地或全局變量)或抽象堆對象。

由于內存泄漏檢測與指針分析密切相關，因此，現有的許多內存泄漏研究將其檢測方法構造為特殊的指針分析。本文將指針分析作為獨立的一部分，以便以后可以重用不同的指針分析算法，提高分析效率。

Table 1 Variables Def-Use information

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

?/l″∈P:l″∈Defv

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

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

根據上文C程序的抽象模型描述，表1列出從語句中提取的變量Def-Use信息。對于NULL、COPY語句，可以直接讀取其Def-Use信息。對于LOAD或STORE語句，必須考慮間接訪問對象的Def-Use信息。其中，ps(v)表示從需求驅動的上下文相關指針分析獲得的變量v的指向集；對于方法調用CALL、METHOD和RET，可以直接獲得變量v的Def-Use信息。

基于指針分析中的指向信息構建值流信息，捕獲程序間引用和程序變量的修改副作用，使用別名集合對每個LOAD、STORE、CALL語句的間接Def-Use進行注釋，每個別名集合代表一組可以間接訪問的抽象內存對象。

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

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

(1)o@p∈N表示程序點p處的對象為o。

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

3.2 基于路徑敏感的值流分析的內存泄漏檢測

將程序的內存空間劃分為一組抽象內存位置M。抽象內存函數mem:S→M，實現給定語句到抽象內存位置的映射。通過將所有訪問映射到它們的抽象內存位置，可以通過直接訪問處理間接訪問。此外，由于抽象內存位置可以表示多個物理位置，存儲新值不會覆蓋舊值，因此對抽象內存位置的新定義被稱為弱更新，添加新值而不破壞舊值。用ζ函數來表示弱更新。

定義4ζ函數形式如下所示：

d=ζ(d1,d2)

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

為了對控制流信息進行更具體的描述，給出定義5。

定義5θ函數形式如下所示：

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

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

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

Table 2 Path-sensitive analysis

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

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

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

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

ControlGuard(cp)=

{∧ControlGuard(e)|e∈cp}

從語句l到語句l′的路徑保護Guard(l,l′)是由所有控制流路徑的路徑條件的邏輯析?。?/p>

Guard(l,l′)={∨

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

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

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

根據計算值流邊上的保護信息，以捕獲程序中值流發生的路徑條件，用于推斷所有路徑上的釋放點的可達性。設定在內存分配結點創建的對象為src，在內存釋放結點創建的對象為sink，編碼路徑之后，開始分析可達性。

部分路徑分析：Fsrc為前向切片，由VFG中src可以到達的結點組成，Ssrc為Fsrc到達的釋放結點集合，若Ssrc為空，則src肯定發生泄漏，因為此種情況下，不會沿某些控制流路徑到達sink(釋放結點)。如果src沿著一些控制流路徑到達全局變量，則泄漏檢測終止，認為src沒有泄漏。

路徑分析：Bsrc為一個后向切片，包含src到Ssrc中的sink的路徑上的節點。然后執行全路徑分析來檢查一個src在每條控制流上至少可達Ssrc中的一個sink，如果src在某些控制流路徑上無法到達Ssrc中的sink，則發出泄漏警告，這是一種條件性泄漏，只有在某些路徑條件下才會觸發。

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

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

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

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

根據上文所提方法設計的算法主要包括wlMod和Check_MemeoryLeak 2個算法，如算法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首先通過worklist設計迭代算法wlMod，進行后向分析。從程序CFG入口處的第1個變量定義處，即第1個指針賦值語句處生成初始化信息，將信息向后傳播。其中，FCG表示程序過程調用圖，f為程序過程調用圖中的函數，CFGf表示為每個函數生成的CFG，Succ(n)表示 CFG上語句n的所有后繼語句。從FCG中自頂向下選擇函數，為CFGf中每個程序點生成初始內存信息。

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

Figure 4 Class diagram of implementation圖4 實現類圖

4 實驗分析

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

為了滿足檢測需求和具體方法實現設計的目標和原則，從功能和執行邏輯上，將原型工具分為2個模塊：代碼預處理模塊和內存泄漏檢測模塊。應用SVFG、CFG分析技術定制的算法。源程序經過編譯前端處理后獲得AST，然后生成中間語言程序，獲取變量的Def-Use鏈，結合必要控制流信息進行內存泄漏路徑約束檢測。圖4是原型工具實現類圖。

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

問題1在檢測現有的內存泄漏錯誤時是否有效？

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

4.1 案例分析

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

(1)指針分析。獲得指針別名信息：

ps(o)={o′}

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

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

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

a 程序案例

b 值流構建

c值流信息約束

d 泄漏路徑識別

4.2 程序集分析

為回答針對實驗評估提出的2個問題，被測程序的選取分為2個部分：第1部分是對經典的堆操作程序進行分析，包括鏈表和樹操作程序，覆蓋了第2節所列舉的全部內存泄漏場景，如表3所示。表3中的前5個程序來自文獻[25]的不同類型的鏈表程序，分別是創建一定長度的鏈表、在鏈表中有序地插入一個元素、刪除元素、判斷鏈表中是否含有某個元素和鏈表逆置，后2個程序是文獻[26]中的樹操作程序。第2部分是選取表4中列出的14個SPEC2000C程序，將實驗效果與CLANG中一個靜態分析器(符號執行)和FASTCHECK(SVFA)進行比較，選取這2個工具是因為它們公開可用，使用率高且趨于成熟。評估時考慮2個標準：(1)效率，即分析時間；(2)準確率，即低誤報檢測內存泄漏的能力。

Table 3 Typical program analysis

由表3和表4的分析結果可知，PACV實現了之前所述的設計目標。表3顯示在鏈表插入程序中，含有1個誤報，說明PACV在檢測現有的典型錯誤案例時還是非常有效的。表4顯示 PACV在119個泄漏警告中檢測到85個故障，FASTCHECK在165個警告中檢測到90個故障，CLANG在47個泄漏警告中檢測到40個故障，相比其他2個工具要少得多?？偟膩碚f，PACV速度比FASTCHECK慢，但誤報率低約28%，更加精確；CLANG的誤報率低，但CLANG是過程內的這一局限性，即單獨分析函數而不考慮其調用函數和被調用函數，外部信息被假設為未知信息，無法分析在被調用函數中創建的對象，從而導致CLANG漏掉許多錯誤。對比其他2個工具可知，PACV在保證一定速度的同時仍能保證一定的精確性。

作為靜態分析方法，PACV仍然受限于誤報和漏報2大固有缺陷。誤報的發生有以下原因：某些不可行的路徑無法識別，分析時限制循環迭代次數以及保守分析內存塊的別名信息存在不準確性。漏報的發生有以下原因：對數組別名訪問的不健全建模，分析循環或遞歸的前n項有限次展開和對堆建模不精確性。此外，和許多方法一樣，PACV處理指針別名分析時不完全準確。

5 結束語

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

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

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

基于本文現有工作，今后在以下方面進行進一步的研究，包括：結合更加完備的指針別名算法，提升路徑分析的計算精度，加強誤報情況的約減計算。