跟蹤機制引導的C程序內存錯誤自動修復

董玉坤，位欣欣，孫玉雪，唐道龍

中國石油大學（華東）計算機科學與技術學院，山東 青島 266580

程序缺陷是軟件開發及維護工作中難以避免的副產品，可引起軟件故障甚至是系統崩潰[1]。如何盡早的檢測并修復程序缺陷一直是研究人員關注的重點。學術界已就缺陷定位、缺陷檢測進行了大量工作[2-6]，但對檢測出的缺陷進行人工修復依然耗費大量人力物力[7]。程序自動修復[8-12]基于給定的錯誤程序自動生成修復補丁，進而修復程序缺陷。其修復過程中產生的補丁可以直接用于修復程序，也能夠幫助開發人員改進代碼，在一定程度上為開發人員縮短修復時間。然而不同類型程序缺陷的產生原因及引發后果不盡相同，利用統一的自動修復框架或方法進行缺陷修復，每類缺陷修復成功率低，同時容易引入新的錯誤。因此研究針對特定類型缺陷的程序自動修復方法尤為重要。

C 程序中的內存錯誤，如內存泄漏（memory leak，ML）、釋放后使用（use-after-free，UAF）和雙重釋放（double-free，DF），在C 程序中非常普遍，但很難修正。例如內存泄漏便是C 程序動態內存分配及釋放方面常見的程序缺陷[13-14]。通常情況下，內存泄漏不會產生可直接觀察的錯誤狀態，而是逐漸積累，造成系統內存的浪費并可能引發系統安全威脅，持續運行下可造成軟件崩潰[15]。盡管研究人員已提出多種方法進行程序中內存錯誤修復，但存在著明顯的缺點。首先，有些方法將缺陷檢測與缺陷修復分為兩個割裂的過程，缺陷檢測的過程信息與結果信息在缺陷修復時未被充分利用，導致缺陷修復時敏感路徑分析精度降低，耗費時間長或者可擴展性低。其次，有些方法可以保證擴展性，應用到大型項目，但是可能在修復的過程中引入新的錯誤[16]。最后，有些工具為了保證安全修復缺陷，選擇性的執行路徑敏感分析，雖然可以保證可擴展性，但造成缺陷報告中的缺陷被遺漏。

本文提出了一種內存錯誤自動修復方法，結合已被過濾的缺陷報告信息，不管缺陷報告中的內存錯誤是真正的錯誤還是誤報（false positive，FP），在保證安全的前提下，對缺陷報告中的錯誤進行全部、盡早的修復。為了實現安全修復，本文提出了一種基于全局指針的跟蹤機制，跟蹤與動態內存分配過程和函數調用有關的分配表達式，確保正確釋放分配內存；同時利用構造的作用域樹，提出一種新的故障定位技術，只有在確信缺陷得到修復而不違反其他安全條件時才插入補丁。該方法在保證可擴展性的同時，實現對報告中的全部錯誤的修復；對于某些未釋放的內存，在其作用結束點及時釋放，實現盡早修復，避免內存空間的浪費。

結合內存錯誤的檢測與修復，在DTSC[17]的基礎上實現了原型工具DTSFix，DTSC（deefect testing system for C）是面向缺陷軟件測試系統——DTS 的重要組成部分之一，主要用于針對C 程序的面向缺陷測試。DTSFix是DTSC在檢測缺陷的基礎上，研究缺陷自動修復的拓展功能，處理過程如圖1 所示。在DTSC 中加入作用域樹，然后對源程序進行第一次缺陷檢測，輸出缺陷報告（defect report，DR）。DR 包括缺陷發生文件、分配位置、分配表達式和可能發生內存錯誤的行，從而指導缺陷檢測以及后續的缺陷修復[18]。依賴缺陷報告以及檢測過程中的函數摘要（function summary，FS）[17]信息，試圖插入一個全局指針作為探針，以追蹤缺陷報告中發生錯誤的分配內存，即本文提出的跟蹤機制。跟蹤機制完成后，著重對DR中的缺陷進行第二次檢測，過濾DR中的部分誤報，為后續自動修復減少干擾，并再次輸出缺陷報告DR′。基于缺陷報告DR′，針對不同的內存錯誤，依賴全局指針生成相應的補丁；作用域樹中的每個樹結點存儲變量屬性信息，通過遍歷指向分配內存區域的變量的作用分布，計算分配內存最后的作用結點，定位故障的修復位置。

圖1 DTSFix工作框架Fig.1 Working framework of DTSFix

本文做出了以下貢獻：

（1）構建了一個描述變量作用范圍信息的作用域樹。首先將輸入的源程序解析為抽象語法樹（abstract syntax tree，AST），之后基于AST 構造了一個記錄變量在可達語句片段的活性信息的作用域樹，樹結點存儲在此程序片段可能出現的變量集合，研究人員可以利用樹的結點信息搜索分析變量的可達樹結點，并將其應用于定位缺陷修復位置，保證修復缺陷又不會產生副作用。

（2）提出基于全局指針的跟蹤機制。基于缺陷報告分析結果，插入全局指針跟蹤發生錯誤的分配內存，跟蹤分配內存的訪問偏移信息。然后基于全局指針生成補丁，避免分配內存被錯誤或部分釋放。

（3）構建了基于跟蹤機制的內存錯誤自動修復工具DTSFix。增加作用域樹以及跟蹤機制后，提高對內存缺陷的檢測精度，降低缺陷誤報率，完成對內存錯誤的自動修復，實現對大型開源C 程序項目的內存錯誤修復。

1 相關工作

近些年，研究人員已對多種缺陷類型進行通用的自動修復框架及方法設計，主要可歸結為基于搜索的程序修復、基于人工模板的程序修復與基于語義的程序修復。這些方法多基于缺陷定位方法對源代碼語句按照可疑值進行排序，將疑似缺陷的位置依次傳輸給補丁生成算法[19-20]以完成程序修復。基于搜索的修復方法[21-24]利用元啟發式方法、演化算法等優化算法在龐大的搜索空間中反復尋找補丁程序，并通過配套的測試用例集進行補丁正確性驗證。基于語義的程序修復方法[25-28]利用符號執行推導出正確補丁的約束條件，并使用程序合成或約束求解來合成補丁。基于人工模板的程序修復[29-31]，根據開發者或研究人員的經驗預定義一些補丁模板或者補丁生成策略來生成補丁，用于指導修復特定類型的缺陷。此外，除上述方式外，研究人員還關注了其他形式的程序修復方法。文獻[32]提出了CodePhage 算法，該算法可以在被修復應用中定位缺陷，同時從其他應用遷移代碼來消除缺陷。該算法可修復指定缺陷，如整數溢出、緩沖區溢出及零除數等。文獻[33]提出了基于機器學習的Getafix，它可以從以往提交的代碼中找到缺陷修復模式，然后對所有候選補丁進行排序，并推薦最合適的修復補丁。而且，最近幾年由于人工智能領域的迅速發展，一些智能化的新技術也被應用到程序修復領域中[34-36]。

在內存錯誤自動修復方面，文獻[37]基于可靠的靜態分析提出了MemFix，為分配內存未釋放、多次釋放、釋放后再使用3 種內存錯誤類型提供了統一的解決方案，但它的可擴展性低，無法生成條件補丁，不足以分析基準程序。文獻[38]利用指針分析與數據流分析實現了針對C 程序內存泄漏自動修復工具leakFix。該工具可求解釋放操作的安全插入位置，保證修復后程序的正確性，但是可以修復的內存泄漏的類型種類比較少，只能修復一小部分的內存泄漏。文獻[39]針對資源泄漏、內存泄漏和空指針引用3 種類型缺陷實現了FootPatch方法，該方法利用靜態方法檢測和修復指針安全屬性違反問題，通過分離邏輯生成補丁，并對輸出的補丁程序進行形式驗證，但是，FootPatch僅根據給定的錯誤報告檢查補丁的正確性，并不能確保安全，并且可能會引入新的錯誤。文獻[40]針對內存錯誤提出新的技術SAVER，它對主要敏感路徑創建對象流圖，依據對象流圖中各個對象的路徑判斷是否有泄漏，并提出相應模式的補丁。SAVER 對真正的缺陷執行修復，且插入的補丁不會對源程序產生副作用，但是它需要定義程序和錯誤報告作為輸入，選擇性的構建對象流圖，當缺陷涉及自定義分配函數或釋放函數時，SAVER便無法修復錯誤。

2 作用域樹

為獲取變量在生命周期內的作用范圍，或者分析某位置使用的變量應該匹配哪層作用域內的變量聲明，以分析該變量的可能取值，通過構建作用域樹來表示變量在程序中的邏輯關系，描述變量的作用分布。

DTSFix以.c文件為單位進行分析，定義3種作用域以標識變量的作用分布。分別為源文件作用域（source file scope，SFS）、函數作用域（method scope，MS）、局部作用域（local scope，LS）。一個文件只有一個SFS，MS對應著定義的函數，LS 對應著函數體內的一個塊。其中塊有3 種屬性，分別是簡單語句塊LS～、判斷分支塊LS^、循環塊LS*。作用域之間具有包含關系，每個作用域看作一個樹結點，形成一個樹狀數據結構。各作用域的封裝信息以及之間的包含關系為：

對于SFS，封裝外部聲明的變量集合Evar，外部聲明的函數集合Func，.c 文件中的函數集合M，文件名sfs以及文件存儲位置file；一個.c文件中有且僅有一個SFS結點，在SFS結點下含有0個或多個MS孩子結點。其中，Evar 中的每個Evari，封裝此變量的名稱var，定義行Linedef，一個或多個使用行Lineuse；Func中的每個funci，封裝此外部聲明的函數的名稱func，聲明行Linedec；M中的每個mi，封裝此函數的函數名稱func，函數開始行LSstart，函數結束行LSend。

對于MS，封裝形式化參數變量集合Fvar，函數中的語句塊集合Ls，函數的名稱func以及函數開始行LSstart，函數結束行LSend；每個MS 結點下含有1 個或多個LS孩子結點。其中，LS 中的每個Fvari，封裝的此變量的定義行Linedef，也即是函數開始行LSstart；Ls中的每個ls i，封裝此語句塊的類型style，語句塊開始行LSstart，語句塊結束行LSend。

對于LS，封裝局部變量集合Var，語句塊的類型style，語句塊開始行LSstart，語句塊結束行LSend；每個LS結點下含有0個或多個LS孩子結點。若語句塊中存在中斷語句return、break、continue，且中斷語句所在行與語句塊結束行不同時，那么中斷語句所在行也是語句塊結束行，另外，對帶有return 語句的LS 結點做標記。其中，style有3種類型，簡單語句塊LS～是連續的基本語句，循環塊LS*是while或者for循環體，判斷分支塊LS^，是if或者switch…case分支語句。其中LS^具有一些特殊性，每個分支便看作一個作用域，如果存在if，else if，…，else連續分支，第一個分支看作，剩余的看作。

作用域樹各個結點之間的關系利用結點開始行以及結束行來尋找，從而構建一個.c 文件的作用域樹，其中樹結點的孩子結點有左右順序。各個結點連接規則如下所示。

連接SFS類型結點s與MS類型結點：

ms是MS類型結點，schild是s的孩子結點集合，若ms與m的開始行信息一樣，則ms屬于s孩子結點，連接ms與s結點。其中s孩子結點的左右順序由其孩子linestart決定，若?m,m′∈MS,m.linestart＜m′.linestart，則結點m在結點m′左側。

圖2 作用域樹示例Fig.2 Anexample of scope tree

3 內存錯誤檢測

內存錯誤是程序開發人員在編碼時，由于設計疏忽或考慮不全面導致的。程序調用malloc 等函數動態分配內存空間，調用free等函數釋放分配的內存空間。如果程序開發人員沒有在合適的位置釋放內存或者沒有正確的進行釋放操作，比如在程序執行不了的分支路徑上進行釋放操作，或者在程序執行路徑上遺漏了free操作，將導致內存泄漏。同樣的，如果程序開發人員多次釋放內存對象或者引用已經釋放的內存對象，將會導致DF或者UAF[41]。

一般有兩種檢測內存錯誤的方法，分別是靜態和動態檢測技術。由于內存錯誤的隱蔽性，靜態檢測技術優先于成本較高的動態檢測技術[42]。源程序的靜態缺陷檢測產生了大量的缺陷信息，可以幫助自動程序修復產生補丁，以提高程序修復的準確性[18，43]。

如圖3是一個缺陷程序示例。在程序中，f1 是一個內存分配函數，m、p、q均為局部指針變量，圖3（a）中，在第8 行，f1 函數的返回值賦值給指針變量p，在第9行，當a＞0 時，q=p，然后在第15行釋放內存。但是在第11 行至14 行，當執行else 分支時，再次調用f1函數，返回值賦值給指針變量q，釋放p，這時在第15行，第8 行分配的內存可能發生DF，而在第16 行，在函數結束時，第12行分配的內存可能發生ML。

圖3 缺陷程序示例Fig.3 Example of defect program

3.1 基于全局指針跟蹤分配內存

C 程序中對某一內存的分配與釋放往往存在于不同函數中，同時，函數返回值及受副作用影響的表達式均可對動態分配內存進行操作。本文利用函數摘要的思想對指向分配內存的函數返回值及受副作用影響的表達式進行表示與確定，以保證全局指針可正確跟蹤可能發生錯誤的分配內存。

本文獲取的部分摘要信息如下：

其中，EV為一個二元組集合，封裝的是受副作用影響的外部表達式（可計算為全局指針或實參指針的表達式）及其抽象取值。RE為一個二元組集合，封裝的是函數返回表達式及其抽象取值，若外部變量及函數返回值均指向動態分配內存時，則Domain 為指向內存單元的抽象地址。

定義1（分配表達式（allocation expression，AExp））分配表達式為在程序分配行獲取動態分配內存首地址的表達式，其最終取值為指針。在程序分配行的語法可歸納為：

其中exp是整型參數，FunMalloc()指代自定義內存分配函數。

對于圖3（a）的程序例子，變量p、q均為分配表達式，從函數摘要中得到的函數返回的內存信息[17]如下：

在DTSFix 基于跟蹤機制檢測內存錯誤之前，它事先進行靜態分析，然后輸出一份缺陷報告DR。對于缺陷報告中的每個錯誤，DTSFix 聲明全局指針去跟蹤報告中的分配內存。

void*Probe_FileName_Number

聲明的指針為void*類型，任何類型的指針都可以直接賦值給void指針，而無需進行其他相關的強制類型轉換。請注意，void 指針不指向具體的數據類型，只表示用來指向一個抽象的類型的數據，即近提供一個純地址，而不能指向任何具體的對象，因此，需要避免對void指針進行算術操作。

算法1描述的是跟蹤發生錯誤的分配內存的過程，對于報告中的每條缺陷，首先聲明全局指針，從源程序的AST中檢索出第一個外部聲明結點，映射獲得這個結點對應的代碼段的開始行，即全局指針的插入位置，在全局指針插入之前，獲得源程序P 的符號表，以避免全局指針的命名與程序中的變量之間的沖突；然后進行令全局指針跟蹤這個缺陷的分配內存。依據函數摘要以及作用域樹的分布位置，幫助全局指針精準跟蹤DR中發生錯誤的分配內存，監督分配內存的生命周期。

在動態分配內存語句之后都插入跟蹤語句，避免調用分配函數后，內存返回值沒有指向，導致地址丟失。如果分配內存在當前分配函數中沒有使用，且存在返回值或受副作用影響的外部表達式在另一個函數，則聲明新的全局指針跟蹤返回值或受副作用影響的外部表達式。在圖3（b）中，DTSFix 首先依次分析缺陷報告中的每個缺陷信息，例如針對在第15行的缺陷，p可能發生DF，聲明相應的全局指針Probe_f2_1。然后找到錯誤內存的分配行L8，全局指針指向分配行的分配表達式p，以便跟蹤其生命周期。

3.2 缺陷過濾

插入全局指針，實現對缺陷報告中全部錯誤內存的跟蹤。然后，DTSFix 利用函數調用關系和數據流分析來確定程序中全局指針的抽象存儲狀態。最后，對全局指針的狀態分析，檢測是否存在缺陷。當缺陷檢測完成后，可能發生內存錯誤的分配內存的相關信息將被記錄，輸出過濾的缺陷檢測報告DR′。

4 基于跟蹤機制的內存泄漏自動修復

4.1 缺陷報告

DTSFix第二次對源程序執行缺陷檢測并輸出DR′，報告包括可能發生內存泄漏的程序文件、內存分配行、分配表達式，以及泄漏發生行等，與DR相比，添加了全局指針列。DR′如表1所示。

表1 缺陷報告Table 1 Defect report

4.2 跟蹤機制

C 程序中往往通過分配表達式靈活訪問動態分配的連續內存，其中涉及的訪問操作、指針偏移、函數調用等可能導致動態分配內存的地址信息丟失，引起內存泄漏。全局指針在指向未發生變化的情況下，可在整個源程序內跟蹤動態分配內存，對可能丟失的動態分配內存地址進行記錄，以彌補指向丟失。

如圖4 為包含全局指針的程序實例及其簡化的控制流圖。其中圖4（a）是一個代碼片段，存在一個全局指針指向動態分配內存。圖4（b）中m為L3 行分配內存的地址，m+1 表示動態分配內存地址m后的單元，可以看出在函數f未對全局指針p進行偏移、賦值等操作的情況下，全局指針p可跟蹤m直至作用域結束。正是全局指針的可跟蹤機制使得只需在程序合適位置執行釋放操作，避免內存部分釋放。

圖4 程序實例及其簡化的控制流圖Fig.4 Example of program and its corresponding simplified control flow graph

4.3 修復位置定位

在以M0為根結點的子樹中，若O分布在多個return結點lsreturn，則l可能會有多個，l定位在各個沒有釋放語句的lsreturn出口前。

在以M0為根結點的子樹中，若存在1 個或0 個return結點，O作用分布的LS結點的最低層，統稱C層，C層結點的父結點所在層，即P層，P層結點的父親結點所在層為2P層，依次類推。

其中，(m-1)PLi是O在(m-1)P層作用分布的LS結點或者低一層O作用分布的LS 結點的父結點，k是與r沒有關系，可能是1或者大于1。

修復位置已經定位到F層，然后定位修復位置所在結點：

在函數結點M是遞歸的情況下，如果O出現過的LS 結點只有一個MS 類型父結點M，則O可以在M中定位修復位置;否則，對O的修復必須定位在M及其子結點之外的其他結點，以確保安全修復。

圖5 圖3示例程序對應的作用域樹Fig.5 Scope tree corresponding to sample program in Fig.3

4.4 內存錯誤自動修復

本文中DTSFix通過對C程序執行添加語句的操作以生成補丁代碼段。該過程可歸結為函數F={FML,FDF,FUAF}的求解過程，分別表示為未釋放、多次釋放、釋放后使用。

其中，FML=fix(p,lML)，lML是計算得到的泄漏內存的修復位置，表示在lML處分配內存作用域將結束的釋放操作，該操作使得根據全局指針p正確釋放分配內存；FDF=fix(p,lDF)，lDF是DR′中的DF發生行之前，表示在lDF處對全局指針p取值判斷是否非空，然后插入操作以修復雙重釋放泄漏；FUAF與FML類似，刪除錯誤發生行的free語句，通過計算分配內存最后的作用分布位置lUAF。通過對函數P的正確求解即獲得錯誤程序的修復補丁。基于跟蹤機制生成補丁和修復缺陷的過程如算法2所示。

如圖6顯示了圖3的內存錯誤的自動修復情況。在圖6中，根據表2的信息，由p指向的分配內存可能在第15 行發生DF。因此，修復補丁被插入到第15 行之前。此外，q可能出現ML，通過分析文件作用域樹之后，發現泄漏的內存的最外層作用點是L16前，所以在此處插入補丁釋放分配內存。

表2 圖3實例的檢測結果Table 2 Detection results of example in Fig.3

圖6 圖3示例程序的修復結果Fig.6 Repair results of Fig.3 sample program

同時，在對跨文件的內存的動態分配存在類似處理方法，即在調用內存分配函數文件中確定動態分配內存的分配行，并利用全局指針進行狀態跟蹤，直至作用域結束完成釋放。

5 實驗設計與結果分析

本章對DTSFix 進行了實驗評估，主要目的是：（1）評估DTSFix在第二次缺陷檢測之后，過濾報告中誤報的效果；（2）評估它在實踐中修復內存錯誤的有效性，主要觀察它對ML、DF、UAF 缺陷類型的修復效果，以及針對誤報，插入補丁后對源程序的影響。本文還將DTSFix 與現有的修復內存錯誤技術MemFix、Saver進行比較。所有的實驗都是在一臺裝有Intel Core i5-8500和16 GB內存的主機上進行的。

5.1 數據集基準

本文用兩個基準集評估了DTSFix：一組是從流行的開源C語言庫中抽象出來的模型程序[37]和一組開源C程序[40]。第一個基準集是由MemFix 創建的，從5 個開源存儲庫構建的總共100個模型程序，平均每個程序代碼行大概有200行，最大的代碼行是440行。其中，一個程序只包含一個錯誤，每個程序都盡量保留了程序的原始特性，以便在模型程序中與錯誤相關的部分保持完整，雖然模型程序與原始程序相比較小，但修正其中的錯誤并不容易。表3橫軸和表4第一列顯示了從開源存儲庫構建的模型程序的結果，目的是評估修復工具針對內存釋放錯誤的修復效果。第二個基準集是開源的C程序，由從GitHub 收集的5 個基準構成，分別是flex、WavPack、Swoole、Snort和p11-kit，如表4、表5第一列所示。這5個程序也被Saver工具應用，用于評估Saver關于內存錯誤的修復效果。DTSFix 與Saver 利用此數據集對比修復內存泄漏的效果，同時列出并分析DTSFix對此數據集中內存泄露的修復效果和時間，以充分例證本文方法的有效性。

表3 DTSFix和MemFix修復內存錯誤的對比結果Table 3 Comparison results of DTSFix and MemFix fixing memory error

表4 DTSFix和Saver基于開源C程序的內存泄漏修復效果Table 4 Repair effects of DTSFix and Saver on memory leak based on open-source C programs

表5 DTSFix對開源C程序的內存泄露的完整修復結果Table 5 DTSFix complete repair results of memory leakage of open-source C programs

5.2 實驗設計實現

本文的實驗驗證是基于DTSC 檢測系統的進一步研究，并實現了原型工具DTSFix，重點是真正地實現修復內存錯誤的目標，而不是優化其檢測功能。本文對基準進行缺陷檢測，獲得含有錯誤內存信息的DR。然后在源程序中插入全局指針來追蹤報告的分配內存，執行缺陷過濾。最后，基于缺陷類別來確定修復補丁模式。利用作用域樹計算修復位置，插入合適的修復補丁。在這個過程中，DTSFix檢測和修復是一體化的，可以直接在修復過程中使用缺陷檢測的過程信息和結果信息。DR 中的缺陷信息幫助在原程序中插入全局指針，而在檢測過程構建的作用域樹用于尋找補丁插入位置，對源程序插入的全局指針用于缺陷檢測和補丁生成。

DTSFix 的修復原則上是安全的。第2 章實現的作用域樹和第3.1 節實現的基于全局指針跟蹤分配內存，目的便是找到安全釋放位置以及將動態分配的內存地址正確釋放。請注意，DTSFix 不準確（不完整）的靜態分析或預分析可能會導致較低的修復率，但不會損害程序的安全性。在故障定位時，搜索的補丁插入位置是發生錯誤的分配內存最末尾的活性位置，且在此位置之后，沒有對此內存區域的引用，保證插入補丁后不會對源程序產生威脅。另外，基于全局指針生成的補丁包含斷言，因此避免補丁插入程序后部分修復缺陷或者引入新的錯誤。

5.3 實驗結果與結果分析

如圖7 顯示了DTSFi 兩次檢測抽象模型程序的結果。其中柱狀圖的橫軸是基準集的5 個項目（Binutils、Git、OpenSSH、OpenSSL 和Tmux），每個項目分別含有20個程序；縱軸是工具報告的缺陷檢測數量；FP表示第一次檢測項目中報告的誤報數量，FP′表示第二次檢測報告的誤報數量；ML、DF、UAF分別表示第一次缺陷檢測報告的各種缺陷數量，ML′、DF′、UAF′分別表示第二次缺陷檢測報告的各種缺陷數量。

如圖7 所示，5 個程序上第一次執行缺陷檢測后，DR總共報告了155個缺陷，為了評估DTSFix，手動分類檢測結果，將缺陷分為49 個缺陷和106 個誤報。工具（自動地）對第一次缺陷檢測過程信息處理，在待測程序中插入全局指針跟蹤DR中指出的分配內存，然后第二次執行缺陷檢測，DR′總共報告了90個缺陷。手動分類后發現，其中各個項目的減少的誤報個數分別是Binutils（9 個）、Git（13 個）、OpenSSH（8 個）、OpenSSL（12 個）和Tmux（23 個）。程序中插入的全局指針跟蹤內存對象的訪問操作、指針偏移、函數調用等，記錄內存對象的動態變化信息，幫助缺陷檢測更準確地分析錯誤分配內存在程序點的狀態，從而減少誤報。同時也發現兩次檢測結果中，報告中的真實缺陷數量沒有改變，在兩次檢測結果中，對各個項目檢測到的真實缺陷數分別是Binutils（9個）、Git（7個）、OpenSSH（13個）、OpenSSL（11個）和Tmux（9個）。

表3 顯示了DTSFix 和MemFix 修復模型程序的結果。#Pgm 表示缺陷數，表格第2、3、4 列表示DTSFix 與MemFix 相比，分別修復內存錯誤的數量。與MemFix相比，DTSFix能夠修復其中的49%（49/100）。對于內存泄漏（ML），DTSFix平均成功修復了56%（28/50）。對于雙重釋放（DF）和釋放后使用（UAF），DTSFix 能夠修復54.2%（13/24）和30.8%（8/26）。對于Tmux程序中的DF和UAF，MemFix 未能修復它們，而本工具對此突破了零修復率。這是因為當代碼中隱含地存在隱式釋放語句時，MemFix不能修復在這些程序中發現的錯誤（例如UAF）。DTSFix 修復缺陷的數量與其缺陷檢測的結果有直接關系，它可以保證DR′報告的真實缺陷全部安全修復。

同時，在修復工作進行前，對DR′的準確性沒有進行人工判斷。換句話說，在不清除誤報的情況下，對錯誤報告中的所有內存錯誤記錄進行統一的缺陷修復處理。對誤報的修復并不影響程序的執行路徑，仍然可以保證其正確性。如圖8 所示，圖（a）是沒有缺陷的一個程序實例（即誤報），圖（b）是對圖（a）的修復。經過人工判定，插入的修復補丁對源程序沒有任何副作用。

圖8 修復誤報對程序的影響Fig.8 Impact of fixing false positives on program

對于Saver和DTSFix生成的每個補丁，手動檢查補丁是否正確修復了目標缺陷。對于修復真實缺陷的補丁，如果它完整地修復內存泄漏（例如，在缺陷的所有執行路徑上都保證釋放了內存），并且沒有引入新的錯誤，將定義這個補丁是正確的（√T）。如果生成的補丁引入了一個新的錯誤，將其視為不安全的（×T，×F）。工具的修復率計算公式為：

缺陷修復率=修復缺陷數量/缺陷待修復數量

實驗結果如表4 所示。缺陷檢測階段已經實現作用域樹的構建以及對泄露內存的跟蹤，因此修復階段執行故障定位和補丁生成并不會耗費太多時間。Infer∩DR′報告有69 個缺陷待修復，對于其中的49 個真正缺陷，DTSFix為其生成了補丁，這些缺陷被完全正確地修復，修復率為71%（49/69）。Infer報告有107個缺陷待修復，其中有68 個真正缺陷，Saver 只完全正確地修復45個缺陷，修復率為42%（45/107）。DTSFix這種高修復率的一個關鍵因素是基于插入的全局指針生成補丁，對泄漏內存進行全程的跟蹤。

為了確保補丁的安全性，修復工具Saver 對誤報沒有進行修復，因為在不引入錯誤的情況下修改已經正確的程序，這比將不正確的程序轉換為正確的程序更具挑戰性。值得注意的是，DTSFix為誤報生成補丁，經過人工驗證，插入的補丁沒有引入新的錯誤。這是因為在故障定位時，確保插入位置之后不存在對泄漏內存的數據關系依賴，生成的補丁含有條件判斷，不會引入DF。

表5 顯示了DTSFix 檢測以及修復5 個開源程序內存泄露的結果。#√表示工具在分析缺陷報告DR′的基礎上，對缺陷的修復數量。#ALoc表示修復過程中插入補丁后，源程序新增的代碼行。分析DR′發現，工具在檢測開源程序中的DF和UAF結果很少，幾乎沒有檢測到錯誤，而只是為基準測試產生誤報。人工檢查DR′后，只在P11-kit 程序中檢測到1 個UAF，其余開源程序中并沒有檢測到，因此，表5 只展示了工具對開源程序中內存泄漏的檢測與修復結果。

從表5可以看出，工具在檢測階段花費時間占整個過程的58%～84%（TDefect/（TDefect+TFix），TDefect是檢測階段花費的時間，TFix是修復階段花費的時間），主要是因為構建作用域樹以及實現跟蹤機制都是在檢測階段實現的，生成補丁以及定位修復位置依賴前期工作，所以花費時間占比少。工具在沒有引入新錯誤的情況下，總共正確修正了58個錯誤（修復率為59.8%）。而且，從表4和表5可以發現，工具修復缺陷的數量與其檢測到的真實缺陷數量相同，工具可以修復全部DR′中的真實內存錯誤，同時不會給原程序引入新的錯誤。

在實驗評估中，本文使用了兩個開源數據集，但它們可能不具有代表性，或者不足以客觀地評估錯誤修復工具的性能。本文的評估重點是DTSFix修復內存錯誤的情況，然而，修復只是原型檢測工具的擴展應用，依賴檢測過程產生的信息，目前還沒有應用到其他工具上，對于修復方法的復用性未來還有很多工作要做。

6 總結

本文研究了由動態分配內存錯誤釋放或未釋放而引起的內存錯誤，提出了跟蹤機制的自動修復方法，并實現了修復工具DTSFix。該工具實現檢測與修復過程一體化，不必借助額外工具進行檢測或者中間語言轉換，保留處理過程細節，更大化地利用處理過程的反饋信息。實驗結果表明，所提出的修復算法可以有效地修復C程序中的內存錯誤；另外，由DTSFix生成的補丁能夠消除目標錯誤而不引入新的錯誤。在未來的工作中，將努力降低靜態分析結果的誤報率，提高修復位置的準確性。