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

中國石油大學(xué)（華東）計算機科學(xué)與技術(shù)學(xué)院，山東 青島 266580

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

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

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

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

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

本文做出了以下貢獻：

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

（2）提出基于全局指針的跟蹤機制?；谌毕輬蟾娣治鼋Y(jié)果，插入全局指針跟蹤發(fā)生錯誤的分配內(nèi)存，跟蹤分配內(nèi)存的訪問偏移信息。然后基于全局指針生成補丁，避免分配內(nèi)存被錯誤或部分釋放。

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

1 相關(guān)工作

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

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

2 作用域樹

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

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

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

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

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

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

連接SFS類型結(jié)點s與MS類型結(jié)點：

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

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

3 內(nèi)存錯誤檢測

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

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

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

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

3.1 基于全局指針跟蹤分配內(nèi)存

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

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

其中，EV為一個二元組集合，封裝的是受副作用影響的外部表達式（可計算為全局指針或?qū)崊⒅羔樀谋磉_式）及其抽象取值。RE為一個二元組集合，封裝的是函數(shù)返回表達式及其抽象取值，若外部變量及函數(shù)返回值均指向動態(tài)分配內(nèi)存時，則Domain 為指向內(nèi)存單元的抽象地址。

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

其中exp是整型參數(shù)，F(xiàn)unMalloc()指代自定義內(nèi)存分配函數(shù)。

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

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

void*Probe_FileName_Number

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

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

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

3.2 缺陷過濾

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

4 基于跟蹤機制的內(nèi)存泄漏自動修復(fù)

4.1 缺陷報告

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

表1 缺陷報告Table 1 Defect report

4.2 跟蹤機制

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

如圖4 為包含全局指針的程序?qū)嵗捌浜喕目刂屏鲌D。其中圖4（a）是一個代碼片段，存在一個全局指針指向動態(tài)分配內(nèi)存。圖4（b）中m為L3 行分配內(nèi)存的地址，m+1 表示動態(tài)分配內(nèi)存地址m后的單元，可以看出在函數(shù)f未對全局指針p進行偏移、賦值等操作的情況下，全局指針p可跟蹤m直至作用域結(jié)束。正是全局指針的可跟蹤機制使得只需在程序合適位置執(zhí)行釋放操作，避免內(nèi)存部分釋放。

圖4 程序?qū)嵗捌浜喕目刂屏鲌DFig.4 Example of program and its corresponding simplified control flow graph

4.3 修復(fù)位置定位

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

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

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

修復(fù)位置已經(jīng)定位到F層，然后定位修復(fù)位置所在結(jié)點：

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

圖5 圖3示例程序?qū)?yīng)的作用域樹Fig.5 Scope tree corresponding to sample program in Fig.3

4.4 內(nèi)存錯誤自動修復(fù)

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

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

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

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

圖6 圖3示例程序的修復(fù)結(jié)果Fig.6 Repair results of Fig.3 sample program

同時，在對跨文件的內(nèi)存的動態(tài)分配存在類似處理方法，即在調(diào)用內(nèi)存分配函數(shù)文件中確定動態(tài)分配內(nèi)存的分配行，并利用全局指針進行狀態(tài)跟蹤，直至作用域結(jié)束完成釋放。

5 實驗設(shè)計與結(jié)果分析

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

5.1 數(shù)據(jù)集基準

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

表3 DTSFix和MemFix修復(fù)內(nèi)存錯誤的對比結(jié)果Table 3 Comparison results of DTSFix and MemFix fixing memory error

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

表5 DTSFix對開源C程序的內(nèi)存泄露的完整修復(fù)結(jié)果Table 5 DTSFix complete repair results of memory leakage of open-source C programs

5.2 實驗設(shè)計實現(xiàn)

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

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

5.3 實驗結(jié)果與結(jié)果分析

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

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

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

同時，在修復(fù)工作進行前，對DR′的準確性沒有進行人工判斷。換句話說，在不清除誤報的情況下，對錯誤報告中的所有內(nèi)存錯誤記錄進行統(tǒng)一的缺陷修復(fù)處理。對誤報的修復(fù)并不影響程序的執(zhí)行路徑，仍然可以保證其正確性。如圖8 所示，圖（a）是沒有缺陷的一個程序?qū)嵗凑`報），圖（b）是對圖（a）的修復(fù)。經(jīng)過人工判定，插入的修復(fù)補丁對源程序沒有任何副作用。

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

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

缺陷修復(fù)率=修復(fù)缺陷數(shù)量/缺陷待修復(fù)數(shù)量

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

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

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

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

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

6 總結(jié)

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