跟蹤機(jī)制引導(dǎo)的C程序內(nèi)存錯(cuò)誤自動(dòng)修復(fù)

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

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

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

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

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

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

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

本文做出了以下貢獻(xiàn)：

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

（2）提出基于全局指針的跟蹤機(jī)制?；谌毕輬?bào)告分析結(jié)果，插入全局指針跟蹤發(fā)生錯(cuò)誤的分配內(nèi)存，跟蹤分配內(nèi)存的訪問偏移信息。然后基于全局指針生成補(bǔ)丁，避免分配內(nèi)存被錯(cuò)誤或部分釋放。

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

1 相關(guān)工作

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

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

2 作用域樹

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

void*Probe_FileName_Number

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

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

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

3.2 缺陷過濾

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

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

4.1 缺陷報(bào)告

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

表1 缺陷報(bào)告Table 1 Defect report

4.2 跟蹤機(jī)制

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

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

圖4 程序?qū)嵗捌浜?jiǎn)化的控制流圖Fig.4 Example of program and its corresponding simplified control flow graph

4.3 修復(fù)位置定位

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

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

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

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

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

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

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

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

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

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

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

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

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

5 實(shí)驗(yàn)設(shè)計(jì)與結(jié)果分析

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

5.1 數(shù)據(jù)集基準(zhǔn)

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

表3 DTSFix和MemFix修復(fù)內(nèi)存錯(cuò)誤的對(duì)比結(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對(duì)開源C程序的內(nèi)存泄露的完整修復(fù)結(jié)果Table 5 DTSFix complete repair results of memory leakage of open-source C programs

5.2 實(shí)驗(yàn)設(shè)計(jì)實(shí)現(xiàn)

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

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

5.3 實(shí)驗(yàn)結(jié)果與結(jié)果分析

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

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

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

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

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

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

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

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

為了確保補(bǔ)丁的安全性，修復(fù)工具Saver 對(duì)誤報(bào)沒有進(jìn)行修復(fù)，因?yàn)樵诓灰脲e(cuò)誤的情況下修改已經(jīng)正確的程序，這比將不正確的程序轉(zhuǎn)換為正確的程序更具挑戰(zhàn)性。值得注意的是，DTSFix為誤報(bào)生成補(bǔ)丁，經(jīng)過人工驗(yàn)證，插入的補(bǔ)丁沒有引入新的錯(cuò)誤。這是因?yàn)樵诠收隙ㄎ粫r(shí)，確保插入位置之后不存在對(duì)泄漏內(nèi)存的數(shù)據(jù)關(guān)系依賴，生成的補(bǔ)丁含有條件判斷，不會(huì)引入DF。

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

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

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

6 總結(jié)

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