本文于 2007 年投稿于 ACM-SIGPLAN 會議¹。

概述

指針在代碼編寫過程中可能出現(xiàn)以下兩種問題：

1. 存在一條執(zhí)行路徑，指針未成功釋放（內(nèi)存泄漏），如下面代碼中注釋部分所表明的：

   int foo()
   {
       int *p = malloc(4 * sizeof(int));
       if (p == NULL)
           return -1;
       int *q = malloc(4 * sizeof(int));
       if (q == NULL)
           return -1; // 注意這里，q為NULL時p一定不為NULL，但是函數(shù)直接返回，導(dǎo)致p所指向的區(qū)域未釋放
       // some code to execute
       free(p);
       free(q);
       return 0;
   }
   

2. 存在一條執(zhí)行路徑，指針被重復(fù)釋放（未定義行為），如 free 一個空指針。

   	int *p = (int *)malloc(4 * sizeof(int));
   	int *q = p;
   	free(q);
   	q = p;
   	free(q);
   

最笨拙的方法是枚舉每一條可能的路徑，依次判斷。但是這顯然是不切實際的。因而本文的主要工作是提出一個能夠發(fā)現(xiàn)未釋放指針或重復(fù)釋放指針的高效算法，并進(jìn)行了代碼實現(xiàn)，提示編寫者具體可能的錯誤原因。即給定一個程序，找到其中可能存在的這種問題。

首先進(jìn)行控制流圖（Condition-Flow Graph，CFG）的約定：

1. 賦值（運算節(jié)點）：$e=e^{\prime }$。
2. 函數(shù)調(diào)用：$e=f(p_1,p_2,?,p_m)$。
3. 返回：$\text{return}e$。
4. 分支節(jié)點：${\text{switch}}_e(c_1,n_1;c_2,n_2;?;c_k,n_k;n_t)$。即一個節(jié)點根據(jù)表達(dá)式 $e$ 的值不同可以有 $k+1$ 個分支跳轉(zhuǎn)地址，分別記作 I n = { n 1 , n 2 , ? ? , n k , n t } I_n=\{n_1,n_2,\cdots,n_k,n_t\} In?={n1?,n2?,?,nk?,nt?}，最后一個為默認(rèn)跳轉(zhuǎn)地址。

此外，本文將問題進(jìn)行了規(guī)約：定義 $\mathrm{source}?\mathrm{sink}[n,m]$ 問題為從 $\mathrm{src}$ 會流入到 $[n,m]$ 個 $\mathrm{sink}$ 的條件可滿足性問題。對于未釋放，則是 $\mathrm{source}?\mathrm{sink}[0,0]$ 問題，而多次釋放則是 $\mathrm{source}?\mathrm{sink}[2,\infty ]$ 問題，而合法性判斷是 $\mathrm{source}?\mathrm{sink}[1,1]$ 問題。

算法流程

整體算法流程圖如下所示：

1. 利用編譯器前端搭建 CFG。
2. 到達(dá)定值點分析
3. 值流圖構(gòu)建
4. 無條件可達(dá)性分析，即不考慮具體控制流圖上條件進(jìn)行的分析
5. 條件可達(dá)性分析，即考慮控制流圖上條件進(jìn)行的分析。

在實現(xiàn)該算法的同時還需要調(diào)用：

1. 指針區(qū)域分析，即分析流圖中每個指針?biāo)赶虻膬?nèi)存區(qū)域。
2. 條件分析。
3. SAT（可滿足性問題）解決器，即給定一組條件約束，返回一組可滿足所有條件的初始值或報告無解。下文會將本論文中提出的問題規(guī)約到可滿足性問題。

到達(dá)-定值分析（Reaching-Definition Analysis）

編譯原理中經(jīng)典的數(shù)據(jù)流分析方法。下文中用 $pdom(x,n,m)$ 來描述變量 $x$ 能不能從 CFG 上流圖節(jié)點 $n$ 值不發(fā)生改變的到節(jié)點 $m$。論文中的 $S$ 僅為一個記憶化的集合，不做具體參數(shù)使用。$pdom$ 的計算使用逆向數(shù)據(jù)流分析方法：
$$pdom(x,n,m)=?\begin{array}{l}true,m=n\\ false,\text{n?沒有出邊（返回節(jié)點）}\\ {?}_{i\in I_n}pdom(x,i,m){\wedge }^{?}define(x,i),\text{其他情況}\end{array}$$
其中 $define(x,i)$ 表示 $i$ 節(jié)點沒有進(jìn)行對變量 $x$ 的賦值操作。

構(gòu)建值流圖（Value-Flow Graph）

在構(gòu)建值流圖之前首先需要介紹 free 函數(shù)的工作原理或特性。它釋放傳入?yún)?shù)給定的指針?biāo)赶虻膮^(qū)域，也就是說它是針對內(nèi)存區(qū)域而非指針的。例如下面的兩個例子：

1. 下面代碼中 p1 和 p2 指針?biāo)赶虻膮^(qū)域都被釋放了。

			int *p1 = malloc(4 * sizeof(int)), *p2 = malloc(6 * sizeof(int));
          	int *q = p1;
          	free(q);
          	q = p2;
          	free(q);

2. 下面代碼中 p 指針指向區(qū)域并未完全釋放——p 指針?biāo)赶虻膮^(qū)域仍有一個 int 大小的空間未釋放。

			int *p = malloc(4 * sizeof(int));
          	int *q = p + 1;
          	free(q);

基于以上兩個特性，構(gòu)建如下的節(jié)點：

1. 賦值（運算）節(jié)點。針對 CFG 上每個形如 $x=y$ 形式的賦值語句都對應(yīng)一個 VFG 的節(jié)點。

2. 內(nèi)存區(qū)域節(jié)點。由于 free 是針對區(qū)域而非指針型變量，因而需要用一個單獨的節(jié)點描述它是否有被釋放的途徑。該部分節(jié)點用 $n_r$ 表示，可以使用這篇論文²中的方法快速描述代碼中每個指針可能對應(yīng)的內(nèi)存區(qū)域集合。

   這里還需要注意的是，由于指針存在加減法操作，因而這里需要額外使用一個偏移量來去衡量該內(nèi)存地址的具體使用情況。

3. 釋放節(jié)點。每個 free 函數(shù)調(diào)用的節(jié)點都對應(yīng)一個 VFG 上的匯（sink）點。

4. 函數(shù)調(diào)用實參節(jié)點。由于進(jìn)行函數(shù)調(diào)用，可以視為進(jìn)行一次變量的值使用，記為 $x_{@}n$。

5. 函數(shù)調(diào)用形參節(jié)點。在被調(diào)用函數(shù)（callee）中該函數(shù)作為新變量使用，同時它對應(yīng)于調(diào)用函數(shù)（caller）的一個變量。為避免函數(shù)多次調(diào)用導(dǎo)致邊關(guān)系混亂，因而新建一個形參節(jié)點以解決圖過于混亂的問題，記為 $[p]$。

6. 函數(shù)返回節(jié)點。函數(shù)的返回值可能在 caller 中作為一個新變量繼續(xù)存在，并涉及后續(xù)賦值和計算。

遍歷 CFG，按如下規(guī)則建圖（假設(shè)當(dāng)前節(jié)點為 $n$）：

1. 賦值語句 $y=x$、釋放節(jié)點 $free(x)$、返回節(jié)點 $return(x)$：將所有 $x$ 的定值點集合 $n_x$ 建立一條邊連到 $n$ 節(jié)點。
2. $y=f(x_1,x_2,?,x_m)$：對于每個函數(shù)實參 $x_i$，首先將 $x_i$ 的定值點集合連接一條邊到對應(yīng)的實參節(jié)點（$n_{x_i}\to {x_i}_{@}n$），然后每個實參節(jié)點連接到形參節(jié)點 ${x_i}_{@}n\to p_i$，最后將 callee 函數(shù)的返回節(jié)點 $n_{\mathrm{ret}}^f$ 連接到當(dāng)前函數(shù)調(diào)用節(jié)點（該語句可以視為一種特殊類型的賦值語句）$n_{\mathrm{ret}}^f\to n$。
3. 對于賦值變量中 $x$ 或 $y$ 不是一個有效節(jié)點的（如 malloc 函數(shù)返回的堆區(qū)域指針），調(diào)用內(nèi)存區(qū)域查詢函數(shù)返回對應(yīng)的內(nèi)存區(qū)域節(jié)點。

無條件可達(dá)性分析（Unguarded Reachability Detection）

該步驟中忽略了程序流圖中的條件，即認(rèn)為所有的邊都是可走到的，在這種情況下先簡單分析是否每個 malloc 函數(shù)都有至少一個 free 與之對應(yīng)。

1. 枚舉一個起始點 $src$，首先找到 VFG 順向流圖中可到達(dá)節(jié)點集合 $F_{src}$
2. 找到 $F_{src}$ 中所有的 free 語句對應(yīng)節(jié)點，記為 $K$。
3. 分類討論：
   1. 如果 $K$ 為空，則該 malloc 語句無對應(yīng) free 語句，直接報告內(nèi)存泄漏。
   2. 如果從該 $src$ 節(jié)點可以到達(dá)一個內(nèi)存區(qū)域節(jié)點，則說明該代碼片段中存在全局變量，暫時不繼續(xù)分析該代碼的內(nèi)存泄漏問題，直接退出。
   3. 找到能從 $src$ 到并且能到達(dá) $K$ 的集合 $R$，并將 $R$ 集合傳遞到下一步繼續(xù)分析。

條件可達(dá)性分析（Guarded Reachability Detection）

預(yù)處理

首先在 CFG 上進(jìn)行條件分析?？紤]每個分支節(jié)點 $n$ 需要滿足其分支出口唯一，即對于分支節(jié)點 $n$：${\text{switch}}_e(c_1,n_1;c_2,n_2;c_k,n_k;n_t)$，需要滿足：
C n = [ ? i ( e = c i ) n ] ∧ [ ? i ≠ j ( e = c i ) n ∧ ( e = c j ) n ￣ ] C_n=\left [\bigvee_{i}(e=c_i)_n\right] \wedge \left[\bigwedge_{i \ne j} \overline{(e=c_i)_n \wedge (e=c_j)_n}\right] Cn?=[i??(e=ci?)n?]∧ ?i=j??(e=ci?)n?∧(e=cj?)n?? ?
即存在一條出路，且不存在一個條件同時滿足兩條出路。

定義函數(shù) $cg(x,n,m)$（下簡寫成 $cguard(n\to m)$，其中程序點 $n$ 為形如 $x=e$ 的賦值語句）表示變量 $x$ 從程序點 $n$ 到 $m$ 需要滿足的輸入條件集合，有如下遞推：

其中$I_{n,x,E}$ 表示滿足后續(xù)節(jié)點不是形如 $define(n_i,x)$ 且 $?n,n_i?$ 不在 $E$ 中的后續(xù)節(jié)點集合 { n i } \{n_i\} {ni?}。$cond(n,n_i,E)$ 函數(shù)表示從 $n$ 節(jié)點走到 $n_i$ 節(jié)點所需要滿足的條件，并且要求 $n$ 節(jié)點后續(xù)不能有 $E$ 中的邊：

這里 $(e=c_i{)}_n$ 表示在程序分支判斷點 $n$ 處進(jìn)行條件判斷 $e=c_i$。

這里加入 $E$ 集合（已遍歷的邊集合）作為參數(shù)是方便代碼實現(xiàn)上的，由于流圖中可能有環(huán)存在，因而不能重復(fù)遍歷同一條邊，通過在狀態(tài)中多維護一個 $E$ 集合可以有效防止重復(fù)遍歷到同一條邊。在 $cond$ 中，顯然要進(jìn)入循環(huán)然后退出該循環(huán)需要同時滿足在循環(huán)的出口判斷中 $e=c_i$ 和 $e\ne c_i$，這顯然是永假的。因而這里加入了邊的限制條件以防止上述情況的出現(xiàn)。

當(dāng)然這里會存在一個小漏洞就是僅判斷了循環(huán)入口點的條件，只有當(dāng)循環(huán)未執(zhí)行的時候才判斷了出口點的條件。這里會對未釋放問題的判定產(chǎn)生一定的影響，但是對多重釋放不會。

接下來就是考慮利用這些條件在 VFG 上進(jìn)行條件判斷。同樣定義 $vguard(n,m)=vg(n,m)$ 函數(shù)表示從 VFG 圖上 $n$ 節(jié)點走到 $m$ 的約束條件集合，有：
v g ( n , m , E ) = { t r u e , n = m ? n → n ′ ∈ E c g u a r d ( n → n ′ ) ∪ v g ( n ′ , m , E ∪ { n → n ′ } ) , 其他情況 vg(n,m,E)= \begin{cases} true,n=m\\ \bigvee_{n \to n' \in E} cguard(n \to n') \cup vg(n',m,E \cup \{n \to n'\}),\texttt{其他情況} \end{cases} vg(n,m,E)={true,n=m?n→n′∈E?cguard(n→n′)∪vg(n′,m,E∪{n→n′}),其他情況?
和在 CFG 上的情況類似，這里只需要在 VFG 圖上再加入 CFG 上的信息即可。

分析過程

考慮對于一個確定的 $src$ 節(jié)點和所有該指針的釋放操作匯點 $K$，在 2.3 節(jié)中闡述的 $R$ 集合上進(jìn)行分析。定義 $G_k=vguard(src,k)$，$C$ 為 $R$ 上所有的分支節(jié)點需要滿足的 $C_n$ 的與集合。此時就滿足了一個 SAT 問題的框架：

1. 如果此處存在一組初值指派滿足 $\overline{{\vee }_{k\in K}{G}_k}\wedge C$，則表明存在某種初值指派，使得從該 $src$ 語句無法走到任何一個匯點，即發(fā)生了內(nèi)存泄漏。
2. 如果存在一組初值指派，滿足 $?i\ne j,G_i\wedge G_j\wedge C$，則表明某組初值指派可以到達(dá)兩個不同的 free 語句，進(jìn)行多次釋放操作，因而發(fā)生未定義行為（Undefined Behavior）。

可以注意到上述的操作時間復(fù)雜度是比較高的，特別是對于有大量 malloc 語句存在的時候。因而本文中僅對操作數(shù)不超過閾值 $30$ 的代碼進(jìn)行分析。

實驗結(jié)果

本文同時實現(xiàn)了代碼，將所有的錯誤種類分成以下幾類：

1. 從未釋放。又分為：a）指針作為局部變量在 main 函數(shù)或其他函數(shù)未釋放；b）指針作為全局變量或存在于數(shù)組等結(jié)構(gòu)中未釋放。
2. 釋放。又分為：a）一切條件下都能釋放；b）某些情況下能釋放，有些情況未釋放。
3. 不能判定，認(rèn)為釋放了。這種情況通常因為分析語句過多導(dǎo)致超過閾值停止分析。

下表是該方法在進(jìn)行 SPEC2000 程序檢測時的測試數(shù)據(jù)。

本文相較于當(dāng)時的內(nèi)存檢測軟件在性能和誤判率上有一定提升。

本文最后也就實際代碼編寫中發(fā)生的內(nèi)存泄露情況進(jìn)行了一定的分析。

到了這里，關(guān)于Practical Memory Leak Detection using Guarded Value-Flow Analysis 論文閱讀的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！