基于抽象內存模型的內存相關漏洞檢測方法

許 健，陳平華，熊建斌

1.廣東工業大學 計算機學院，廣州 510006

2.廣東技術師范大學 自動化學院，廣州 510665

與內存相關的漏洞包括Memory Leak（內存泄露）[1]、Double Free（重復釋放內存）[2]和Use After Free（讀寫釋放后的內存）[3]，這三種漏洞都與動態內存的使用息息相關。內存泄漏是程序運行過程中資源泄漏的一種形式，指的是分配給程序的一部分堆內存直到程序結束才釋放，通常發生在程序執行不適當的內存分配、操作和釋放時。內存泄漏會導致內存耗盡[4]、程序崩潰[5]、系統故障、信息泄漏[6]等嚴重問題。指針使得程序員能夠靈活操作內存，是C語言強大的一個重要特征，但這也使得程序員在使用C語言編寫程序時，很容易錯誤地將內存安全缺陷引入到C程序中，而且這些缺陷很難發現、定位和修復[7]。重復釋放內存指在程序運行過程中，某一塊已分配的動態內存被釋放兩次，這會造成內存管理中數據結構的錯誤，從而導致系統出現未知的風險[8]。讀寫釋放后的內存指的是釋放非空指針指向的動態內存后，但沒有把指針置為空，在后續代碼中又使用該指針讀寫其指向的內存，這將會導致指針訪問或修改未知的數據，有可能影響程序的運行和導致不可預測的結果。

目前對于內存相關漏洞檢測的研究大多專注于指針的數據流分析和內存相關漏洞特征的形式化描述，而忽略了運行時內存的狀態變化和特征。而在對于運行時內存狀態的研究中，則存在著缺乏內存相關漏洞特征的形式化描述以及內存相關漏洞特征描述不全面的問題，例如，對漏洞特征沒有形式化定義或只描述了內存泄露的運行時內存狀態特征。

文獻[9-11]認為造成重復釋放內存和讀寫釋放后的內存兩種內存漏洞的主要原因是懸浮指針的使用。Caballero等[2]指出，重復釋放內存和讀寫釋放后的內存漏洞產生的一個重要特征是，此類漏洞的發生是由于創建和使用了懸浮指針；因此，該研究的認為根源是懸浮指針的創建而不是懸浮指針的使用，但是并沒有考慮內存狀態等任何信息，檢測誤報率普遍較高。Yamaguchi等[12]研究內存泄漏的特點，結合抽象語法樹、控制流圖以及程序流程圖，基于圖遍歷，利用漏洞特征進行漏洞檢測，該方法也只考慮了指針的創建和指針的使用，分析指針的數據流。王濤等[13]定義軟件漏洞的特征，包括初始漏洞節點集、狀態空間、漏洞語法規則集、判定前后條件，設計了一個基于漏洞可執行路徑集的軟件漏洞靜態檢測框架，利用定義的漏洞語法規則求解漏洞可執行路徑集上的漏洞相關節點集，但是文中可執行路徑集是與指針的聲明和定義息息相關的，并未考慮內存的運行時狀態，會存在一定的漏洞漏報。Liu等[7]為內存泄漏漏洞的語義特征定義形式化描述方法，并基于形式化特征定義語法檢測規則，但他們的方法只能形式化地描述內存泄漏特征。Han等[14]研究釋放后訪問內存漏洞的特性是程序中分配內存、釋放內存和使用釋放的內存，這三種操作依次出現，然后選擇關鍵路徑，檢查關鍵路徑上是否存在釋放后訪問內存的漏洞特征。然而，他們的研究中所描述的漏洞特征和對關鍵路徑的選擇算法并沒有深入形式化和講述，沒有考慮運行時內存的狀態，從而導致關鍵路徑的選擇存在一定的錯誤以及漏洞的誤報和漏報。Hu等[8]提出MRVDAVF模型，將有關于內存的漏洞具體形式化，同時構建指針相關的控制流圖，重點對指針的聲明和指針的操作進行分析，文中提到的可執行路徑重點關心指針的數據流信息，并沒有考慮運行時內存狀態且分析程序所有執行路徑，也會產生漏洞的誤報和漏報。Zhang[15]提出一種陣列模型，可以直觀地將內存看作一個大陣列。在這個模型中，數組元素的索引表示變量的內存地址。該方法簡單直觀，但不涉及復雜數據結構的描述，如指針和結構體。Dong[16]提出一個完善的抽象內存模型，基于區域的符號三元組模型，它可以描述內存中數據結構的形態信息和C程序中內存對象的存儲狀態，但并沒有對內存相關的漏洞特征進行形式化表示以及忽略內存的偏移量信息。Dong等[17]在文獻[16]的基礎上提出一個改進的抽象內存模型，加入內存的偏移量信息，并基于改進的抽象內存模型，對內存泄露漏洞進行檢測，但他們的方法只能形式化描述內存泄漏漏洞的特征。

指針數據流分析的方法重點關注程序中指針的數據流向。在檢測內存相關漏洞中，指針數據流分析主要包括分析指針的聲明和定義、申請內存、釋放內存、使用指針訪問內存這幾種情況，重點關注指針變量本身的信息。但忽略了程序中分配和釋放的內存塊大小、指針指向的內存塊信息以及動態分配的連續內存塊和數組這一類順序存儲結構（一組地址連續的存儲單元組成的存儲數據的結構）的重要屬性——偏移量（即指針指向順序存儲結構的位置與順序存儲結構基址的距離）。因此指針數據流分析不能全面且正確地分析程序運行時內存狀態，這將會導致較高的誤報率和漏報率。

為解決指針數據流分析檢測內存相關漏洞所存在的問題，本文提出抽象內存模型，將程序運行過程中變量所操作的內存映射為抽象內存區域。抽象內存模型有效地將各種類型變量的信息以及所對應內存區域的信息結合起來，同時關注變量的信息以及內存區域的屬性特征并且將偏移量信息融合進來。然后基于抽象內存模型形式化內存相關漏洞特征，最后基于內存相關漏洞的特征提出內存相關漏洞檢測框架。

本文工作的主要貢獻有以下三個方面：

（1）結合代碼中數據與運行時內存狀態之間的關系，提出抽象內存模型，從對指針數據流的關心轉化到數據以及運行時內存狀態的關心，該模型將不同類型的變量映射到抽象內存模型五元組，五元組不僅關注各種類型變量的信息和變量所對應內存區域的信息，而且包含內存區域的偏移量信息。同時很方便地分析代碼控制流圖中的可行路徑，從而使得基于抽象內存模型的內存相關漏洞檢測框架更準確地檢測出與內存相關的漏洞，降低漏洞檢測的誤報率和漏報率。

（2）目前內存相關漏洞靜態檢測的方法缺乏漏洞特征的形式化描述以及漏洞特征描述不全面，本文基于抽象內存模型對與內存相關的三種漏洞類型進行分析，對內存相關漏洞的特征進行形式化表示。

（3）基于抽象內存模型和內存相關漏洞的特征，提出內存相關漏洞檢測框架，其中包括可行路徑求解算法以及檢測內存相關漏洞的算法。

1 相關定義

內存相關漏洞產生的主要原因是在程序執行過程中內存狀態的變化，因此只關注指針數據流的方法不能很好并且直觀地分析程序中是否存在內存相關漏洞。另一方面，內存狀態變化的原因可能是由指針或者其他變量引起的，為了建立變量與所操作內存區域之間的關系，同時關注變量的信息和所操作內存區域的信息并且引入內存區域的偏移量信息，本文提出抽象內存模型，將變量在程序運行過程中所操作的內存區域映射為抽象內存區域，用五元組定義抽象內存模型。

定義1（抽象內存模型五元組）抽象內存模型描述不同類型的變量和抽象內存區域之間的關系以及變量和抽象內存區域的信息。定義五元組q=＜Var,Type,Region,Domain,LineNum＞，Var指的是變量的名稱，Type表示變量的類型，Region是與變量相關的抽象內存區域，每一塊不同的抽象內存區域以唯一編號表示，按照r1,r2,…,r k順序編號。Domain表示值域，該值在不同類型變量中所表示的含義有所區別，LineNum表示代碼行號。變量與其對應抽象內存模型五元組之間的對應關系為q=map(Var)，表示將變量Var映射至抽象內存模型五元組q。

考慮C程序中的一個變量Var，根據變量Var的類型不同，其對應的五元組定義有所不同，r x表示某抽象內存區域。

（1）若Var是基本類型，如果Var的值是未知的，則其對應的五元組表示為＜Var,ptv,r x,[-inf,inf],LineNum＞；如果Var的值域是已知的，則表示為：

＜Var,ptv,r x,[y1,y2]?[y3,y4]?…?[yk,yk+1],LineNum＞(k≥1)

ptv表示“基本類型”（primitive type variable）。

（2）若Var是數組類型，則其對應的五元組表示為A=＜Var,array,r x,Domain,LineNum＞，對于每個d i∈Domain，d i=＜index,qi＞，index表示數組的索引，是抽象內存區域的偏移量信息，qi表示數組中元素的五元組信息，其中(d i.qi.r i)?(A.r x)表示Var數組中元素的抽象內存區域在Var數組的抽象內存區域內。

（3）若Var是結構體類型，則其對應的五元組表示S=＜Var,struct,r x,Domain,LineNum＞，對于每個d i∈Domain，d i=＜index,qi＞，index表示結構體中成員變量的位置，是抽象內存區域的偏移量信息，qi表示結構體中成員變量對應的五元組信息，其中(d i.qi.r i)?(S.r x)表示結構體S中成員變量的抽象內存區域在結構體S的抽象內存區域內。

（4）若Var是指針類型，表示為＜Var,pointer,r x,iBytes,LineNum＞，iBytes表示偏移量，單位為字節，r x表示Var指向的抽象內存區域，則五元組表示Var指向抽象內存區域r x中的第iBytes個字節。指針類型的五元組信息中存在指針與其操作內存區域的偏移量信息。指針可能指向空地址，用“null”表示空地址對應的抽象內存區域；也可能指向野地址，用“wild”表示野地址對應的抽象內存區域。指針數據流信息只包含指針類型變量的信息，而抽象內存模型中指針類型所對應的五元組包含了指針和指向內存狀態信息，以及它們之間的關系和偏移量信息。

指針變量可以指向順序存儲結構的某個偏移位置，指針數據流分析不能確定指針變量相對于順序存儲結構基址的具體偏移量。在抽象內存模型中，增加指針運算以更好地支持順序存儲結構。指針算術操作可以統一為地址表達式操作，地址表達式操作的形式多種多樣，這些變體可以分為以下幾類（offset是表示偏移量的整數類型，p表示指針類型變量）：

基于上述三類指針運算，本文定義指針運算，每一類指針運算可能會改變左值指針指向的抽象內存區域，也可能導致該左值指針變量所對應的五元組狀態發生轉移。

定義2（指針運算）設offset為偏移量，iBytes為offset對應偏移的字節數，p為指針變量名稱，a為指針變量名稱，Array為數組名稱，Array.length為數組的長度，指針運算的轉移規則如表1所示。每一類指針運算都會產生兩種結果，一種結果為發生指針越界錯誤，即指針經過運算后不再指向原先的抽象內存區域，而是指向未知區域；另一種結果為得到正確的指針運算后的結果，即指針指向已知的抽象內存區域，且指向該抽象內存區域的偏移范圍內。

表1 指針類型變量運算五元組狀態轉移規則Table 1 Quintuple state transition rules of arithmetic operations on pointer type variables

對于抽象內存區域Region，當程序中申請的內存為堆內存時，其對應的抽象內存區域用三元組r=＜Size,FreeTimes,PointCnt＞表示，Size表示申請的堆內存的大小，單位為字節，FreeTime表示該堆內存被釋放的次數，PointCnt表示指向該堆內存的指針數量。對于所有動態申請的堆內存，形成一個集合RegionList存放所有動態申請的堆內存對應的抽象內存區域，當程序中申請的內存為非堆內存時，用一元組r=＜Size＞表示。

以圖1代碼為例，在第3行，用抽象內存模型五元組＜data,pointer,wild,[0,0],3＞表示指針data，因為聲明的指針變量data沒有定義指向內存中的某個地址，是一個野指針，所以將抽象內存區域設置為“wild”。在第4行，用抽象內存模型五元組＜data,pointer,null,[0,0],4＞表示指針data，null表示指針data指向空。在第5行，用抽象內存模型五元組＜a,ptv,r1,[0,0],5＞表示基本變量a，其中r1=＜4＞。第6行用五元組＜b,ptv,r2,[1,1],6＞表示基本變量b，其中r2=＜4＞。第9行用抽象內存模型五元組＜data,pointer,r3,[0,0],9＞表示指針data指向抽象內存區域r3且偏移量為0字節，其中r3=＜32,0,1＞表示指針data指向的抽象內存區域r3此刻的狀態，RegionList={r3}。第10行用五元組＜p,pointer,r3,[24,24],10＞表示指針p指向抽象內存區域r3且偏移量為24字節，其中r3=＜32,0,2＞表示此刻r3的狀態，抽象內存區域r3狀態如圖2所示。

圖1 代碼片段例子Fig.1 Code snippet example

圖2 抽象內存區域r 3Fig.2 Abstract memory region r 3

指針數據流分析只關注指針的數據流向，而內存相關漏洞產生的主要原因是程序執行過程中內存狀態發生了改變，因此本文提出的內存相關漏洞檢測框架對程序執行路徑過程中的內存狀態進行分析，因此定義控制流圖表示程序的執行路徑。

定義3（控制流圖）對于代碼的控制流圖CFG=(N,E,Entry,Exit)[18-19]，N是節點n的集合，節點即為源代碼中的語句，E是控制流邊e的集合，控制流邊即為控制流信息表示節點ni經過控制流邊ei到達節點nj,ni為nj的直接前驅，記為ni=Prev(nj),nj為ni的直接后繼，記為nj=Succ(ni)。

對于代碼所對應的控制流圖，由于條件選擇語句的存在，控制流程圖中并不是每一條路徑都是可行的，因此，定義不可行路徑，并且在分析運行時內存狀態時忽略不可行路徑，降低漏洞的誤報率。

2 內存相關漏洞特征形式化

2.1 內存泄露相關定義

內存泄漏（CWE-401）[1]指的是分配給程序的一部分堆內存直到程序結束才釋放，從而導致程序的內存占用隨著運行時間的增加而減少。內存泄漏可能最終導致程序運行緩慢，甚至導致計算機系統崩潰。內存泄露有以下三種情況。

（1）申請的堆內存沒有被釋放。基于抽象內存模型，特征形式化定義為：

若存在一條可行路徑path，當代碼沿著path執行完畢，在RegionList集合中存在一塊抽象內存區域r i的釋放次數為0，即說明在程序結束之前，存在申請的堆內存沒有被釋放的情況，此時判定代碼存在內存泄露漏洞。

（2）指針的重定義。基于抽象內存模型，特征形式化定義為：

若存在一條可行路徑path，在程序沿著path執行過程中，當控制流到達某節點nk時，所有指向某抽象內存區域r i的指針都已被重定義，不再指向該抽象內存區域r i，說明r i所代表的某塊初始分配的堆內存沒辦法被釋放，從而將會產生內存泄露的問題。

（3）堆內存的申請和釋放大小不匹配。基于抽象內存模型，特征形式化定義為：

若存在一條可行路徑path，在程序沿著path執行過程中，控制流到達某節點nk時，指針Var雖然指向抽象內存區域r i，但不是指向該抽象內存區域r i的首地址，此時若執行free(Var)對Var指向的堆內存進行釋放操作，由于Var不是指向對應堆內存的首地址，會出現堆內存的申請和釋放大小不匹配的問題，從而導致內存泄露漏洞。

2.2 重復釋放內存相關定義

重復釋放內存（CWE-415）[2]是指在運行程序的過程中，某塊堆內存在被釋放一次之后，但是在之后再次被釋放，這會造成堆內存管理中數據結構的錯誤，從而給系統和程序帶來未知的錯誤，基于抽象內存模型，特征形式化定義為：

在可執行路徑path中，在程序沿著path執行過程中，控制流到達某節點nk時，發現在RegionList中存在一塊抽象內存區域r i的釋放內存次數大于1，此時判定代碼存在重復釋放內存的漏洞。

2.3 讀寫釋放后的內存相關定義

讀寫釋放后的內存（CWE-416）[3]是指一個指針在釋放了它指向的堆內存后，指針并沒有被賦為null，如果在程序運行結束之前，再次通過該指針訪問它指向的堆內存，對指向的內容進行讀或寫操作時，將會讀取到未知的值或者修改未知區域的內容，這都將會導致不可預計的嚴重后果，基于抽象內存模型，特征形式化定義為：

某指針類型變量p在節點ni處聲明，其所對應的抽象內存模型五元組為＜p,pointer,r i,[0,0],LineNum＞，在可執行路徑path中的節點nj執行free(p)釋放了p指向的堆內存區域r i后，并沒有把指針p置為null，在節點nk仍然對p指向的這塊堆內存進行讀寫操作，而這塊堆內存是未知的情況，此時判定代碼存在讀寫釋放后的內存的漏洞。

3 內存相關漏洞檢測框架

3.1 整體架構

圖3為本文內存相關漏洞檢測框架圖，首先，對目標源代碼進行詞法分析和語法分析生成對應的抽象語法樹AST；然后構造對應的控制流圖CFG，定義控制流圖CFG的節點信息CFGNode，如圖4所示；其次，基于抽象內存模型，定義內存相關漏洞特征，根據內存泄露漏洞、重復釋放內存漏洞以及讀寫釋放后的內存漏洞的特征相關定義，檢測路徑上的指針狀態以及運行時內存狀態判斷代碼是否存在某種內存相關漏洞；最后生成漏洞報告。

圖3 整體架構Fig.3 Overall framework

圖4 控制流圖CFG節點信息Fig.4 Node information of control flow graph（CFG）

3.2 得到所有可行路徑

控制流圖CFG中的所有路徑由可行路徑以及不可行路徑組成，條件選擇語句是造成不可行路徑的主要原因。如果在控制流圖中某個節點存在條件選擇語句，此時會產生兩條控制流邊，分別表示條件選擇表達式為true或者false的流向情況，但是當該條件選擇表達式的結果能被判定為永遠為false或者永遠為true，那么其中的一條邊必然不可行，而另一條邊是可行的。不可行路徑的存在是誤報和漏報的一個重要原因，因為不可行路徑是永遠不可能被執行的，所以應該忽略對不可行路徑的分析。在控制流圖中加入變量的數值區間域可以有效地檢測出不可達路徑。

3.2.1數值區間域檢測不可行路徑

數值的區間域信息也即為數值的取值范圍，抽象內存模型中基本變量類型所對應五元組中的值域即為該變量的取值范圍。若變量v是基本類型且v的值是未知的，則其對應的五元組＜v,ptv,r x,[-inf,inf],LineNum＞表示變量v的取值范圍為負無窮到正無窮；若變量v是基本類型且取值范圍是已知的，則其對應的五元組＜v,ptv,r x,[y1,y2]?[y3,y4]?…?[yk,yk+1],LineNum＞(k≥1)表示變量v的取值范圍為多個區間的并集。特別地，常數C的取值范圍表示為[C,C]。

程序執行過程中，數值的區間域可能會經過運算而發生改變，本文基于抽象內存模型引入數值區間域運算對程序控制流圖中的變量及表達式的取值范圍進行跟蹤，下面定義基本的區間域運算。給定兩個區間域X=[x s,x e]和Y=[ys,ye]，區間域四則運算定義為：

在控制流圖中，當遇到條件選擇語句時，對條件選擇語句中的條件表達式進行分析，根據條件表達式相關變量所對應的五元組中的值域信息分析條件表達式的返回值是否一直是false或者true，排除不可行路徑。另一方面，相關變量的五元組信息在程序執行過程中隨時會發生變化，此時必須獲得條件表達式相關變量所對應的最新五元組信息。對每個變量使用一個該變量專屬的棧結構來保存該變量所對應的最新五元組信息，棧中有且只有一個元素，該元素表示變量最新的五元組信息，隨著程序的執行，在控制流圖某一節點，若變量的五元組信息與該變量專屬棧棧頂的五元組信息不同，則把棧中舊的五元組信息彈出，然后把新的變量對應五元組信息壓入該變量的專屬棧中。

在圖5代碼第4行（圖6控制流圖的節點n2）變量a的數值區間域為[0，0]，其所對應的五元組為＜a,ptv,r1,[0,0],4＞，變量a專屬棧中的內容如圖7所示。

圖5 代碼片段例子Fig.5 Code snippet example

圖6 圖5代碼對應的控制流圖Fig.6 Control flow diagram corresponding to code in Fig.5

圖7 到達圖6控制流圖節點n2時的變量a專屬棧內容Fig.7 Exclusive stack content of variable a when reaching node n2 of control flow graph in Fig.6

在圖5代碼的第5行（圖6控制流圖的節點n3）變量b的數值區間域為[0，0]，其所對應的五元組為＜b,ptv,r2,[0,0],5＞，變量b的專屬棧中的內容如圖8所示。

圖8 到達圖6控制流圖節點n3時的變量b專屬棧內容Fig.8 Exclusive stack content of variable b when reaching node n3 of control flow graph in Fig.6

在圖5代碼的第6行（圖6控制流圖的節點n4），變量b專屬棧棧頂五元組＜b,ptv,r2,[0,0],6＞的值域[0，0]和[1，1]區間域進行加法運算，得到區間域結果為[1，1]，所以此時變量b所對應的五元組為＜b,ptv,r2,[1,1],6＞，與變量b的專屬棧棧頂五元組信息不同，因此先從變量b的專屬棧中彈出舊的五元組信息，然后將變量b新的五元組信息壓入變量b的專屬棧中，變量b的專屬棧中的內容變為如圖9所示。

圖9 到達圖6控制流圖節點n4時的變量b專屬棧內容Fig.9 Exclusive stack content of variable b when reaching node n4 of control flow graph in Fig.6

本文主要針對條件表達式中只存在關系運算符的情況進行分析研究，關系運算符主要有以下六種：==（等于）、!=（不等于）、＞（大于）、＜（小于）、≥（大于或等于）和≤（小于或等于）。假設有兩個基本類型變量a和b，當控制流圖到達某一選擇語句時，獲取a和b各自的專屬棧棧頂的最新五元組信息，變量a所對應的最新五元組為aq=＜a,ptv,r i,Domain,LineNum＞，變量b所對應的最新五元組為bq=＜b,ptv,r j,Domain,LineNum＞。表2為a和b通過六種比較運算符的運算結果一直是false或true的情況分析。

表2 六種比較運算符運算結果一直是false或true的情況Table 2 Result of six comparison operators is always false or true

當圖5代碼執行到第7行（圖6控制流圖的節點n5），分別取得此時變量a的專屬棧和變量b的專屬棧，并得到各自棧頂的五元組信息＜a,ptv,r1,[0,0],4＞（圖7）以及＜b,ptv,r2,[1,1],6＞（圖9）。由表2可知，b的區間域總是大于a的區間域。所以第7行的條件表達式結果必為true，而第11行的條件表達式結果必為false。所以，在控制流圖中，n5→e6n7是不可行子路徑，n7→e7n8也為不可行子路徑。

圖10為基于抽象內存模型，利用數值區間域以及表2規則對控制流圖中的不可行路徑進行分析。

圖10 不可行路徑分析Fig.10 Analysis of infeasible path

3.2.2所有可行路徑求解算法

在代碼控制流圖CFG上，按照算法1，從CFG根節點開始，采用深度優先遍歷，基于抽象內存模型，利用數值區間域及表2規則，排除不可行路徑，得到所有可行路徑。

算法1根據數值區間域檢測得到所有可行路徑

輸入：CFG

輸出：所有可行的路徑

說明：isReach(node,nextNode)：當節點node是條件選擇語句，利用數值區間域檢測節點node是否可達節點nextNode，其中nextNode=Succ(node)，true表示可達，false表示不可達。

可行路徑求解算法的輸入是代碼的控制流圖CFG，輸出的結果是所有的可行路徑。算法1的1～3行分別定義臨時的路徑變量path、存放所有可行路徑的變量feasiblePath以及CFG的根節點root；7～11行是深度優先遍歷的遞歸出口，當遍歷到CFG的出口節點時，一條可行路徑生成并加入到feasiblePath中；13行表示臨時存儲到達控制流圖當前節點node時的所有專屬棧，以便遞歸返回時供isReach(node,nextNode)判斷節點可達性使用。14～22行是對每個節點的后繼節點集循環一遍，如果當前節點可達某后繼節點，則把該節點信息加入到path中，然后繼續以后繼節點進行深度優先遍歷。

isReach(node,nextNode)利用數值區間域分析控制流圖中當節點node是條件選擇語句時是否可達節點nextNode（節點nextNode是節點node的直接后繼節點）。此時只要得到與節點node相關的變量以及它們各自專屬棧中的棧頂五元組信息，利用表2規則，若節點node的條件表達式的結果一直是false或者一直是true，則根據node到nextNode的邊信息是true或者false判斷是否可達；相反，則肯定可達。該算法的時間復雜度為O(1)。

可行路徑求解算法對控制流圖的每個節點和邊只遍歷一次，且isReach(node,nextNode)時間復雜度為O(1)，因此總時間復雜度為O(n+e)，其中n為控制流圖中的節點數，e代表控制流圖中的邊數。

3.3 檢測內存相關漏洞算法

算法2為檢測內存相關漏洞的算法，主要任務是在所有可行路徑上，依照基于抽象內存模型中提出的內存泄露漏洞、重復釋放內存漏洞以及讀寫釋放后的內存漏洞相關特征形式化定義，分析路徑上的節點的指針狀態以及運行時內存狀態，以檢測出相應的內存相關的漏洞。

算法2得到可能存在的與內存相關的漏洞

算法2的輸入是所有可行路徑，輸出是可能存在的與內存相關的漏洞。算法2中第1行的errors集合是存放檢測出來的內存相關漏洞。第6～8行表示如果當前節點是分配動態內存的節點，則生成對應的抽象內存區域r加入到RegionList集合中。第9～23行表示如果當前節點是涉及到指針運算的節點，遍歷每一個相關指針p，11行表示先根據指針p對應的專屬棧得到離當前節點最近的關于指針p對應的五元組信息old Q，然后按照抽象內存模型中的指針運算規則運算，如果運算結果存在指針越界的情況，則把“指針越界錯誤”加入到errors集合中；如果指針p沒有越界，則根據五元組old Q得到其之前指向的抽象內存區域，如果指向該內存區域的指針的數量減少了，則說明當前節點的指針運算使得指針p不再指向該內存區域，當指向該內存區域的指針的數量為0時，則把“指針重定義所導致的內存泄露”加入到errors集合中。第24～37行表示如果當前節點是涉及指針p釋放動態內存的節點，則根據指針p對應的專屬棧得到離當前節點最近的關于指針p對應的五元組信息old Q，如果指針p不是指向動態內存首地址，則把“堆內存的申請和釋放大小不匹配導致的內存泄露”加入到errors集合中；否則，判斷p指向的抽象內存區域的釋放次數是否為1，如果為1，則把“重復釋放內存”加入到errors集合中。第38～44行表示如果當前節點是使用指針p讀寫指向內存的節點，則根據指針p對應的專屬棧得到離當前節點最近的關于指針p對應的五元組信息old Q，如果p指向的抽象內存已經在之前被釋放過了，則把“讀寫釋放后的內存”加入到errors中。第45～52行表示如果當前節點是CFG的出口節點時，此時遍歷RegionList集合中的抽象內存區域，如果發現某一抽象內存區域的釋放次數為0，則把“申請的堆內存沒有被釋放”加入到errors中。

檢測內存相關漏洞算法通過遍歷每一條可行路徑上的節點信息，平均時間復雜度為O(m×n)，其中m表示可行路徑的條數，n表示平均每條可行路徑上的節點數。

4 實驗

本文從C/CPP的Juliet Test Suite[20]中選取CWE-401 Memory Leak、CWE-415 Double Free和CWE-416 Use After Free三種與內存相關的漏洞類型的測試數據集，將本文提出的內存相關漏洞檢測框架與另外四種漏洞檢測工具/框架（Flawfinder[21]、Cppcheck[22]、Splint[23]和MRVDAVF[8]）在該數據集進行實驗。表3為三種類型數據集經預處理之后的具體信息。

表3 測試數據集具體信息Table 3 Specific information of test data set

設測試數據集的總漏洞數為TVN，模型（工具）檢測出來的漏洞數為TRN，檢測出來屬于測試數據集的漏洞類型的漏洞數量為TTP，檢測出來不屬于測試數據集的漏洞類型的漏洞數量為TFN，則有TRN=TTP+TNF。公式（1）為漏報率FNR，公式（2）為漏洞誤報率FPR。

表4為Flawfinder、Cppcheck、Splint、MRVDAVF和本文模型在三個數據集上的檢測結果對比。Flawfinder、Cppcheck和Splint是三款開源的代碼靜態檢測分析工具，MRVDAVF是針對內存相關漏洞提出的檢測模型，這些檢測工具或者方法都重點關注指針的數據流并分析程序中所有執行路徑。與Flawfinder、Cppcheck、Splint和MRVDAVF相比，本文檢測方法在Memory Leak和User After Free在Double Free這三種與內存相關的漏洞檢測中具有更低的誤報率和漏報率，說明本文提出的基于抽象內存模型的檢測框架的有效性和可行性。因為本文的檢測方法完全模擬了運行時內存的狀態，并描述了涉及指針運算的操作，同時包含變量的信息、內存區域的信息以及忽略程序中不可行路徑，確保更加精確的內存相關漏洞的檢測。其中存在一定的誤報率和漏報率的原因是缺乏對代碼中循環結構的分析以及條件選擇語句中其他未知復雜表達式的處理。

表4 五種檢測工具（模型）對三個測試數據集的檢測結果Table 4 Test results of five test tools（models）on three test data sets

圖11為不含有漏洞的代碼片段，圖12、圖13和圖14代碼片段均含有內存泄漏的漏洞，圖15代碼片段含有重復釋放內存的漏洞，圖16代碼片段含有讀寫釋放后的內存的漏洞。通過實驗發現，分析程序中所有路徑的檢測模型或工具對圖11的代碼進行靜態檢測時會誤報內存泄露漏洞；重點關注指針數據流的模型或工具能夠正確檢測出圖12和圖13代碼含有內存泄漏的漏洞，但不能檢測出圖14代碼含有內存泄漏的漏洞；同時也不能檢測出圖15代碼含有重復釋放內存的漏洞；以及不能檢測出圖16代碼含有讀寫釋放后的內存的漏洞。而本文提出的方法能夠正確檢測圖11～圖16的代碼。

圖12 內存泄漏例子（沒釋放動態內存）Fig.12 Memory leak example（dynamic memory is not freed）

圖13 內存泄漏例子（指針重定向）Fig.13 Memory leak example（pointer redirection）

圖14 內存泄漏例子（動態內存釋放不全）Fig.14 Memory leak example（dynamic memory is not fully freed）

圖15 代碼片段例子（重復釋放內存）Fig.15 Code snippet example（double free）

圖16 代碼片段例子（讀寫釋放后的內存）Fig.16 Code snippet example（use after free）

圖11代碼是一個無漏洞的例子，但當使用Flawfinder、Cppcheck、Splint、MRVDAVF這類關注指針數據流并分析程序中所有執行路徑的檢測工具或方法檢測圖11代碼時，會得到內存泄露的檢測結果。因為若關注指針data的數據流并分析程序中所有執行路徑時，指針data在第9行申請了一塊堆內存，但是并沒有在11～14行的if語句塊中執行free(data)操作釋放data指向的堆內存，從而報告程序存在內存泄露的漏洞。但實際上11～14行的if語句塊中的代碼是永遠都執行不到，只會執行15～18行else語句塊中的代碼，else語句塊中有free(data)語句，所以實際上該段代碼是不存在內存泄露漏洞的。本文基于抽象內存模型提出使用數值區間域解決該類問題，根據控制流圖的節點遍歷，當遍歷到控制流圖的控制語句節點時，得到a和b兩個變量各自對應的專屬棧，根據專屬棧可得到a和b兩個變量的最新五元組信息，也即得到a和b的數值區間域，以分析路徑的可達性與不可達性，忽略不可行路徑，避免漏洞誤報。

圖12代碼是一個由于申請的堆內存沒有被釋放而導致內存泄漏的例子，當使用Flawfinder、Cppcheck、Splint、MRVDAVF這類關注指針數據流的檢測工具或方法檢測圖12代碼時，能夠報告存在內存泄漏的檢測結果，因為若關心指針data的數據流，發現到程序結束之前都沒有執行free(data)釋放指針data所指向的堆內存，此時可判定代碼存在由申請的堆內存沒有被釋放導致的內存泄露漏洞。本文提出的基于抽象內存模型的檢測方法重點關注已分配堆內存的狀態，同樣也能報告存在內存泄漏的檢測結果，因為在程序結束之前，通過遍歷程序執行過程中分配的所有堆內存對應的抽象內存區域，發現存在某抽象內存區域中釋放次數FreeTimes的值為0，此時同樣可判定代碼存在由申請的堆內存沒有被釋放導致的內存泄露漏洞。

圖13代碼是一個由于指針的重定義而導致內存泄漏的例子，當使用Flawfinder、Cppcheck、Splint、MRVDAVF這類關注指針數據流的檢測工具或方法檢測圖13代碼時，能夠報告存在內存泄漏的檢測結果，因為若關心指針data的數據流，代碼中第3行聲明指針data指向某塊堆內存，而在第5行對指針進行了重定義，指向另一塊堆內存，導致之前指向的堆內存沒法被釋放。本文提出的基于抽象內存模型的檢測方法重點關注運行時堆內存狀態，記錄代碼中第3行以及第5行中申請的兩塊堆內存的具體信息，在執行代碼第5行之后發現第3行申請的堆內存所對應的抽象內存區域中指針指向數PointCnt的值為0，證明此時沒有指針指向代碼第3行申請的堆內存，此時同樣可判定代碼存在由指針重定義導致的內存泄露漏洞。

圖14代碼是一個由于堆內存的申請和釋放大小不匹配而導致內存泄露的例子，但當使用Flawfinder、Cppcheck、Splint、MRVDAVF這類關注指針數據流的檢測工具或方法檢測圖14代碼時，會得到不存在內存泄漏漏洞的檢測結果。因為若只關心指針data的數據流，忽略指針運算以及指針對指向堆內存的偏移量信息，程序中會在第5行執行free(data)語句釋放指針data指向的堆內存，所以報告不存在內存泄露漏洞。而本文提出的基于抽象內存模型的檢測方法關注指針對于順序存儲結構的偏移量信息，根據指針對該堆內存的偏移量信息和堆內存的釋放信息，在代碼第5行執行free(data)時發現指針data并非指向堆內存的首地址，因此在代碼第3行成功分配的內存塊沒有被完全釋放，此時判定代碼存在由堆內存的申請和釋放大小不匹配導致的內存泄露漏洞，避免了內存泄漏漏洞的漏報。

圖15代碼是一個存在重復釋放內存的例子，但當使用Flawfinder、Cppcheck、Splint、MRVDAVF這類關注指針數據流的檢測工具檢測圖15代碼時，會得到不存在重復釋放內存漏洞的檢測結果。因為若只關心指針data的數據流，程序中會執行free(data)語句釋放指針data指向的內存，同理，若關心指針p的數據流，程序中也會執行free(p)語句釋放指針p指向的內存，完全沒有考慮指針指向內存的狀態信息。而本文提出的基于抽象內存模型的檢測方法重點關注運行時堆內存狀態以及指針狀態，發現指針data和指針p都指向同一塊堆內存，在執行代碼第5行free(data)時，將指針data指向的堆內存所對應的抽象內存區域中釋放次數FreeTimes的值置為1，而在執行代碼第6行free(p)時，指針p指向的堆內存所對應的抽象內存區域中釋放次數FreeTimes的值為1，此時判定代碼存在重復釋放內存的漏洞，避免了漏洞漏報。

圖16代碼是一個存在讀寫釋放后的內存的例子，但當使用Flawfinder、Cppcheck、Splint、MRVDAVF這類關注指針數據流的檢測工具檢測圖16代碼時，檢測不出代碼中含有讀寫釋放后的內存的漏洞。因為若只關心指針data的數據流，在代碼中第7行指針data仍然指向一片有效合法的內存，并沒有考慮所指向內存的狀態信息，所以可以通過*data訪問該合法內存的內容，導致讀寫釋放后的內存的漏洞漏報。而本文提出的基于抽象內存模型的檢測方法重點關注運行時堆內存狀態以及指針狀態，代碼中第3行聲明指針data指向一塊堆內存，在執行代碼第7行free(data)時，將指針data指向的堆內存所對應的抽象內存區域中釋放次數FreeTimes的值置為1，在代碼第8行使用*data訪問指針data指向的堆內存，發現指針data指向的堆內存所對應的抽象內存區域中釋放次數FreeTimes的值為1，此時判定代碼存在讀寫釋放后的內存的漏洞，避免了漏洞誤報。

上述的實驗結果表明，在代碼中存在不可行路徑、指針偏移、動態內存狀態變更這幾種情況，基于指針數據流和分析程序所有路徑的檢測方法會出現誤報和漏報的問題。而本文提出的基于抽象模型的檢測方法關注變量的信息、所操作內存區域的信息、兩者之間的關系以及內存區域的偏移量信息，可以在上述的幾種情況下得到正確的檢測結果，大大降低與內存相關漏洞檢測的誤報率和漏報率。

5 結束語

內存泄露、重復釋放內存和讀寫釋放后的內存這三種漏洞都具有某些特征，對漏洞特征的研究將促進對漏洞預防和檢測的研究。本文提出的基于抽象內存模型的內存相關漏洞檢測框架重點關注運行時內存狀態與指針的狀態，對內存相關漏洞進行檢測。首先，本文對抽象內存模型進行形式化定義，并形式化描述內存相關漏洞特征；然后，基于抽象內存模型以及內存相關漏洞特征，提出內存相關漏洞檢測框架，包含可行路徑求解算法以及檢測內存相關漏洞算法；最后，為了檢驗本文提出的檢測框架的有效性和可行性，與其他四種漏洞檢測工具或模型（Flawfinder、Cppcheck、Splint和MRVDAVF）進行了對比實驗。與Flawfinder、Cppcheck、Splint和MRVDAVF相比，本文提出的框架對于內存泄露、重復釋放內存和讀寫釋放后的內存的檢測能力更強，漏洞漏報率和誤報率均降低。實驗結果表明，本文提出的檢測方法是可行和有效的。

基于該研究的后續工作主要分為兩個方面：

（1）研究條件選擇語句中更加復雜的表達式和未知情況下的處理，如其他類型變量以及地址比較等。

（2）研究循環語句以及多線程情況下的可行路徑求解過程。