朱亞偉,左志強(qiáng),王林章,李宣東

(計(jì)算機(jī)軟件新技術(shù)國家重點(diǎn)實(shí)驗(yàn)室(南京大學(xué)),江蘇 南京 210023)

內(nèi)存泄漏會嚴(yán)重降低軟件的性能,甚至造成軟件在運(yùn)行時(shí)崩潰.在C語言中,內(nèi)存的分配與釋放都是人為控制的,隨著計(jì)算機(jī)軟件的規(guī)模和復(fù)雜度的不斷增加,人為的疏忽極易導(dǎo)致內(nèi)存泄漏.由于C語言在計(jì)算機(jī)領(lǐng)域的廣泛應(yīng)用,C程序中的內(nèi)存泄漏問題不可忽視.目前,內(nèi)存泄漏的檢測方法主要是靜態(tài)分析與動態(tài)檢測.

· 動態(tài)檢測方法[1-4]需要執(zhí)行程序,在程序運(yùn)行的過程中對內(nèi)存的分配、使用以及釋放進(jìn)行動態(tài)跟蹤.由于動態(tài)檢測能夠針對當(dāng)次的運(yùn)行結(jié)果得到一個(gè)明確的結(jié)論,因此動態(tài)檢測相對靜態(tài)分析,其結(jié)果更加準(zhǔn)確.但是動態(tài)檢測的準(zhǔn)確性受限于測試用例,無法分析程序執(zhí)行中不可達(dá)位置的錯(cuò)誤.目前,成熟的內(nèi)存泄漏動態(tài)檢測工具有Purify[5]、Valgrind[6]等,都存在內(nèi)存開銷較高和可擴(kuò)展性較差的問題.

· 靜態(tài)分析是在不實(shí)際運(yùn)行程序的情況下對程序代碼及其結(jié)構(gòu)進(jìn)行分析.針對C語言的內(nèi)存泄漏靜態(tài)分析方法主要通過分析內(nèi)存的分配點(diǎn)以及從內(nèi)存分配點(diǎn)開始的不同路徑,在相應(yīng)的路徑中查找與內(nèi)存分配點(diǎn)對應(yīng)的內(nèi)存釋放點(diǎn),驗(yàn)證是否所有路徑都存在正確的內(nèi)存釋放.目前,有許多內(nèi)存泄漏的靜態(tài)分析工作[7-12],也有一些成熟的靜態(tài)分析工具,如Fortify[13]、Coverity[14]、Klocwork[15],這些工具在工業(yè)界的軟件開發(fā)中應(yīng)用廣泛.靜態(tài)分析方法又可根據(jù)流敏感、上下文敏感以及域敏感等進(jìn)行分類,實(shí)現(xiàn)這些靜態(tài)分析方法可以在一定程度上提高內(nèi)存泄漏檢測的準(zhǔn)確率,但會極大降低檢測效率.

內(nèi)存泄漏的靜態(tài)分析目前主要缺點(diǎn)是:當(dāng)內(nèi)存泄漏中存在一些特殊案例時(shí),會降低靜態(tài)分析的準(zhǔn)確性,導(dǎo)致內(nèi)存泄漏的檢測出現(xiàn)誤報(bào)或者漏報(bào).其主要原因在于:

(1) 對分支條件缺少分析,無法識別不可達(dá)路徑;對全局變量和指針的重定向未做細(xì)致分析;忽略指針偏移問題.可以通過流敏感、上下文敏感等靜態(tài)分析方法在一定程度上解決以上問題,但會造成檢測效率大幅降低.

(2) 動態(tài)數(shù)組的分配問題、鏈表的分配釋放不匹配問題、循環(huán)或遞歸中指針分析的準(zhǔn)確性問題(限制循環(huán)或遞歸的展開次數(shù))會導(dǎo)致指針分析不準(zhǔn)確.流敏感、上下文敏感等目前已有的靜態(tài)分析方法無法解決上述問題.

針對靜態(tài)分析的上述不足,本文利用機(jī)器學(xué)習(xí)算法以提高內(nèi)存泄漏靜態(tài)分析的準(zhǔn)確性,獲得更加準(zhǔn)確的內(nèi)存泄漏檢測結(jié)果.本文利用已有的內(nèi)存泄漏案例,即含有標(biāo)簽為虛假內(nèi)存泄漏和真實(shí)內(nèi)存泄漏的兩類數(shù)據(jù)集,通過使用機(jī)器學(xué)習(xí)算法進(jìn)行訓(xùn)練,構(gòu)建內(nèi)存泄漏分類器以分析程序特征與內(nèi)存泄漏的相關(guān)性.

本文的主要貢獻(xiàn)在于:

(1) 本文提出一種C程序內(nèi)存泄漏智能化檢測方法,該方法基于靜態(tài)分析提取內(nèi)存泄漏相關(guān)特征,能夠提高內(nèi)存泄漏檢測的準(zhǔn)確性,減少誤報(bào)和漏報(bào).

(2) 我們實(shí)現(xiàn)了內(nèi)存泄漏的智能化檢測工具 I_Mem.該工具使用多種機(jī)器學(xué)習(xí)算法構(gòu)建內(nèi)存泄漏檢測模型,并基于靜態(tài)分析提取內(nèi)存泄漏相關(guān)特征,能夠提高內(nèi)存泄漏檢測的準(zhǔn)確性.

(3) 我們在LLVM-4.0.0上實(shí)現(xiàn)了I_Mem,并利用4個(gè)開源的C程序(2KLOC)進(jìn)行實(shí)驗(yàn)評估.I_Mem總共發(fā)現(xiàn)了114個(gè)內(nèi)存泄漏,漏報(bào)為4個(gè),誤報(bào)為13個(gè),準(zhǔn)確率為85.6%.

本文第1節(jié)主要介紹背景知識.第2節(jié)介紹C程序內(nèi)存泄漏智能化檢測方法,包括方法的基本框架、內(nèi)存泄漏模型的構(gòu)建、特征提取與缺陷檢測.第3節(jié)對本文實(shí)現(xiàn)的工具I_Mem進(jìn)行實(shí)驗(yàn)和評估.第4節(jié)主要介紹相關(guān)工作,包括內(nèi)存泄露的靜態(tài)分析方法、內(nèi)存泄露的動態(tài)檢測技術(shù)和基于機(jī)器學(xué)習(xí)的缺陷檢測.第 5節(jié)進(jìn)行總結(jié)和展望.

1 背 景

針對內(nèi)存泄漏的程序靜態(tài)分析需要在獲取所有內(nèi)存分配點(diǎn)后,關(guān)注內(nèi)存的定義、使用及釋放.此外,C語言中由于函數(shù)可以返回指針,內(nèi)存泄漏檢測需要對調(diào)用點(diǎn)作分析.因此,Saber[8,9]關(guān)注C程序中的6種語句,見表1.在表1中,p和q是變量,v表示變量或者堆對象,F是函數(shù).

Table 1 Six types of statements表1 6種語句類型

Saber中使用的靜態(tài)分析方法是 Full-Sparse Value-Flow Analysis,通過構(gòu)建 SVFG來檢測內(nèi)存泄漏.其中,VFG(value flow graph)[7,16]表示的是句法上的語義等價(jià),它關(guān)注變量的定義、使用,能夠表示程序中變量的價(jià)值流向.VFG不同于CFG(control flow graph)和DFG(data flow graph),CFG表示的是控制程序邏輯執(zhí)行的先后順序,一個(gè)程序的CFG被用來確定對變量的一次賦值可能傳播到程序中的哪些位置;DFG是在CFG基礎(chǔ)上實(shí)現(xiàn)的,它描述的是程序運(yùn)行過程中數(shù)據(jù)的流轉(zhuǎn)方式及其行為狀態(tài).在 VFG中,每一個(gè)節(jié)點(diǎn)表示變量的定義,每條邊表示變量的def-use關(guān)系.Saber針對VFG進(jìn)行改進(jìn)構(gòu)建了SVFG.SVFG的構(gòu)建主要分為3個(gè)步驟.

(1) 預(yù)分析:根據(jù)內(nèi)存分配相關(guān)的API(如malloc)確定內(nèi)存位置.使用域敏感、調(diào)用點(diǎn)敏感、流和上文不敏感的安德森指針分析獲取C程序的指針信息.

(2) 全稀疏SSA(static single assigment):在SSA形式中,每個(gè)被使用的變量都有唯一的定義,這可以確保精確地def-use關(guān)系鏈.針對所有內(nèi)存位置,構(gòu)造每個(gè)函數(shù)的SSA形式.關(guān)注內(nèi)存位置的間接訪問,如load,store以及函數(shù)調(diào)用操作.用程序內(nèi)流敏感的指針分析對預(yù)分析的指針信息進(jìn)一步稀疏提高指針分析的準(zhǔn)確性.

(3) SVFG:基于全稀疏 SSA,獲取程序內(nèi)所有內(nèi)存位置的 def-use關(guān)系鏈和 value-flow,并構(gòu)建 SVFG.每個(gè)def-use邊會有一個(gè)”警衛(wèi)”來獲取分支條件.

2 C程序內(nèi)存泄漏智能化檢測方法

本節(jié)我們主要介紹 C程序內(nèi)存泄漏智能化檢測方法的基本框架.本方法是在內(nèi)存泄漏靜態(tài)分析的基礎(chǔ)上進(jìn)行改進(jìn),利用機(jī)器學(xué)習(xí)技術(shù)提高了內(nèi)存泄漏靜態(tài)分析的準(zhǔn)確性.圖1是C程序內(nèi)存泄漏智能化檢測方法的主要框架.

Fig.1 Framework of our work圖1 本文的工作框架

該方法主要可分為兩個(gè)步驟——模型構(gòu)建階段以及特征提取與缺陷檢測階段.

(1) 模型構(gòu)建階段

? 首先,根據(jù)已有的內(nèi)存泄漏構(gòu)建訓(xùn)練集,構(gòu)建訓(xùn)練機(jī)分為兩步:第 1步,構(gòu)建包含真正內(nèi)存泄漏與虛假內(nèi)存泄漏的數(shù)據(jù)集;第2步,從兩個(gè)數(shù)據(jù)集中分別提取內(nèi)存泄漏特征;

? 然后,將訓(xùn)練集輸入機(jī)器學(xué)習(xí)的分類器進(jìn)行訓(xùn)練,并應(yīng)用交叉驗(yàn)證對分類器進(jìn)行評估;

? 隨后,修改分類器類型及參數(shù),選取分類效果最好的作為內(nèi)存泄漏檢測模型.

(2) 特征提取與缺陷檢測階段

? 首先,利用靜態(tài)分析方法分析源程序,獲取所有的內(nèi)存位置(內(nèi)存分配點(diǎn)o),并構(gòu)建從o開始的SVFG,提取SVFG中每條路徑對應(yīng)的內(nèi)存泄漏特征并構(gòu)成數(shù)據(jù)集;

? 根據(jù)內(nèi)存泄漏特征,我們可將數(shù)據(jù)集分成兩部分:一部分可根據(jù)規(guī)則直接判斷是否為內(nèi)存泄漏,另一部分需要輸入到內(nèi)存泄漏檢測模型中進(jìn)行判斷;

? 最后,將內(nèi)存泄露檢測結(jié)果與靜態(tài)分析階段的分配點(diǎn)的信息相結(jié)合,得到漏洞報(bào)告.

2.1 模型構(gòu)建階段

針對內(nèi)存泄漏的靜態(tài)分析中存在的不足,我們提取了 16個(gè)內(nèi)存泄漏特征.本文根據(jù)從內(nèi)存分配點(diǎn)開始的SVFG提取內(nèi)存泄漏特征,每一個(gè)內(nèi)存分配點(diǎn)對應(yīng)一個(gè)內(nèi)存泄漏特征.提取的內(nèi)存泄漏特征信息(內(nèi)存分配點(diǎn)o,內(nèi)存釋放點(diǎn)指針p)包括3類:類型信息、分支信息、釋放信息.類型信息包括數(shù)組(判斷o是否為數(shù)組元素)、結(jié)構(gòu)體(判斷o是否為結(jié)構(gòu)體元素)、鏈表(判斷o是否為鏈表元素),分支信息包括循環(huán)分配(o是否在循環(huán)內(nèi)部分配)、循環(huán)釋放(p是否在循環(huán)內(nèi)部釋放)、循環(huán)匹配(循環(huán)分配與釋放次數(shù)是否一致)、同一循環(huán)(分配與釋放是否在同一循環(huán)內(nèi))、鏈表匹配(鏈表的分配與釋放次數(shù)是否一致)、分支條件(若當(dāng)前分支中不存在對o的釋放,則判斷分支條件是否為真),釋放信息包括函數(shù)間距(從o出發(fā)的SVFG最多經(jīng)過的函數(shù)數(shù)量)、釋放之前為空(p釋放之前是否為空指針)、p指向?qū)ο髷?shù)目(釋放p時(shí),p指向的對象數(shù)目)、別名數(shù)目(釋放p時(shí),指向o的指針數(shù)目)、指針偏移量(釋放p時(shí),p與o的偏移量)、全局指針(判斷在SVFG中有全局變量指向o)、釋放(指針p是否釋放).特征見表2.

Table 2 Features of memory leak表2 內(nèi)存泄漏特征

本文針對內(nèi)存泄漏共提取16個(gè)特征,其中,部分特征與內(nèi)存泄漏靜態(tài)分析的不足存在如下的對應(yīng)關(guān)系.

(1) 針對內(nèi)存泄漏有關(guān)的數(shù)組、鏈表、循環(huán)或遞歸問題,我們使用特征1、特征3～特征8進(jìn)行判斷.

(2) 特征9用于對分支條件進(jìn)行判斷,特征11、特征12、特征15用于判定全局變量以及指針重定向問題,指針偏移量問題使用特征14進(jìn)行判斷.

(3) 其余特征用于對內(nèi)存泄漏的一些復(fù)雜情況進(jìn)行輔助判斷.

確定內(nèi)存泄漏相關(guān)特征后,我們需針對各種內(nèi)存泄漏構(gòu)建訓(xùn)練集.我們使用的是開源的C程序源碼(包括一些大型程序和小程序),在原程序中,我們會插入各種內(nèi)存泄漏以構(gòu)建盡量豐富的訓(xùn)練集,然后從中區(qū)分真正的與虛假的內(nèi)存泄漏.在人工對訓(xùn)練數(shù)據(jù)進(jìn)行標(biāo)記時(shí),我們發(fā)現(xiàn)如下規(guī)律.

(1) 特征15、特征16都為假(即在SVFG中,不存在全局變量指向內(nèi)存分配點(diǎn),也不存在內(nèi)存釋放點(diǎn)),通常是真正內(nèi)存泄漏.

(2) 特征11為真(即p釋放之前為空指針)、或者特征12大于1(即p指向的對象數(shù)目超過1)、或者特征14不為0(存在指針偏移)、或者特征16為假(即未進(jìn)行內(nèi)存釋放),通常是真正內(nèi)存泄漏.

在對訓(xùn)練數(shù)據(jù)進(jìn)行人工標(biāo)記后,我們獲取每個(gè)訓(xùn)練樣本的內(nèi)存泄漏特征,并將這些作為訓(xùn)練集輸入分類器進(jìn)行模型構(gòu)建.現(xiàn)階段主流的機(jī)器學(xué)習(xí)算法有 SVM、決策樹、樸素貝葉斯分類、隱馬爾可夫、隨機(jī)森林、循環(huán)神經(jīng)網(wǎng)絡(luò)、長短期記憶(LSTM)與卷積神經(jīng)網(wǎng)絡(luò)等.本文采用 3種機(jī)器學(xué)習(xí)算法:SVM[17]、隨機(jī)森林(RF)[18]和決策樹[19].下面介紹3種算法的優(yōu)缺點(diǎn).

(1) 決策樹是指 C4.5算法,優(yōu)點(diǎn)是產(chǎn)生的分類規(guī)則易于理解,訓(xùn)練時(shí)間復(fù)雜度較低,準(zhǔn)確率較高;缺點(diǎn)是針對連續(xù)屬性值的特征時(shí)計(jì)算效率低,且容易過擬合.

(2) 隨機(jī)森林的優(yōu)點(diǎn)是訓(xùn)練速度快,易并行化,能夠處理高維度的數(shù)據(jù),適合做多分類問題;缺點(diǎn)是在處理噪音較大的數(shù)據(jù)集上容易過擬合,過于隨機(jī)導(dǎo)致無法控制模型內(nèi)部運(yùn)行.

(3) SVM可以通過計(jì)算數(shù)學(xué)函數(shù)將訓(xùn)練數(shù)據(jù)分開,這些函數(shù)被稱為核函數(shù).常用的核函數(shù)有4種:線性、多項(xiàng)式、徑向基核函數(shù)(RBF)和 Sigmoid函數(shù).根據(jù)文獻(xiàn)[20,21],使用 RBF核函數(shù)將每個(gè)特征向量映射到高維空間,這樣可以防止過擬合.缺點(diǎn)是對大規(guī)模訓(xùn)練樣本難以實(shí)施,解決多分類問題存在困難.

在構(gòu)建模型時(shí),需要確定分類器類型及參數(shù),我們使用分類的準(zhǔn)確率作為評估標(biāo)準(zhǔn),然后進(jìn)行迭代確定最優(yōu)的分類器類型及參數(shù),步驟如下.

(1) 首先選定第1個(gè)分類器類型以及參數(shù)并進(jìn)行訓(xùn)練,使用五折交叉驗(yàn)證得到的準(zhǔn)確率作為基線;

(2) 多次修改分類器參數(shù)(根據(jù)分類器類型可自行調(diào)整),記錄五折交叉驗(yàn)證的準(zhǔn)確率超過基線的分類器類型、參數(shù)以及準(zhǔn)確率;

(3) 修改分類器類型,并重復(fù)第(2)步;

(4) 選取準(zhǔn)確率最高的分類器(類型及參數(shù))作為本文內(nèi)存泄漏檢測模型.

2.2 特征提取與缺陷檢測階段

特征提取與缺陷檢測主要分為以下 3個(gè)步驟:程序靜態(tài)分析、特征提取、內(nèi)存泄漏檢測.程序靜態(tài)分析就是第1節(jié)所介紹的Full-Sparse Value-Flow Analysis.

2.2.1 特征提取

本文通過構(gòu)建SVFG并獲取特征,算法1闡述了如何通過SVFG來獲取內(nèi)存泄漏特征,該算法的輸入是內(nèi)存位置(內(nèi)存分配點(diǎn))集合src以及SVFG.基本思想是:分析內(nèi)存分配點(diǎn)的信息獲取內(nèi)存泄漏的部分類型和指針信息,分析內(nèi)存分配點(diǎn)到釋放點(diǎn)的路徑信息獲取內(nèi)存泄漏的其余信息.

· 首先,在第1行～第5行,我們初始化存放特征信息的向量V,然后遍歷內(nèi)存分配點(diǎn)的集合src,并從內(nèi)存分配點(diǎn)開始向前遍歷SVFG,獲取當(dāng)前內(nèi)存分配點(diǎn)的部分類型信息和分支信息(如內(nèi)存分配點(diǎn)是否為數(shù)組或者結(jié)構(gòu)體、內(nèi)存分配點(diǎn)是否在循環(huán)中等)存入V中,記錄經(jīng)過的節(jié)點(diǎn)集合FNode以及內(nèi)存釋放點(diǎn)集合dst,并初始化BNode集合(用于存放內(nèi)存釋放點(diǎn)向后遍歷SVFG經(jīng)過的節(jié)點(diǎn)).

· 然后,在第6行至第11行,遍歷內(nèi)存釋放點(diǎn)集合dst,并從內(nèi)存釋放點(diǎn)開始向后遍歷SVFG,若當(dāng)前節(jié)點(diǎn)出現(xiàn)在FNode中,則將該節(jié)點(diǎn)放入BNode中.

· 最后遍歷FNode與BNode,獲取當(dāng)前內(nèi)存分配點(diǎn)對應(yīng)的特征信息存入V中.

算法1.SVFG遍歷獲取內(nèi)存泄漏特征.

如圖2所示,我們給出了一個(gè)具體示例展示如何從源程序中提取特征.圖2(a)是C程序源碼,圖2(a)左邊為代碼行號.圖2(b)是根據(jù)源碼獲取的特征以及對應(yīng)的屬性值.其中,O1對應(yīng)第16行內(nèi)存分配點(diǎn)的特征信息,O2對應(yīng)第5行內(nèi)存分配點(diǎn)的特征信息,O3根對應(yīng)第6行內(nèi)存分配點(diǎn)的特征信息.根據(jù)圖2(b)可知.

·O1所對應(yīng)的特征1、特征4～特征6、特征9、特征16為TRUE,表明該內(nèi)存位置在循環(huán)中分配與釋放,且分配與釋放次數(shù)一致;特征10的值為3,表示從內(nèi)存分配點(diǎn)到釋放位置經(jīng)過3個(gè)函數(shù).

·O2所對應(yīng)的特征 15、特征 16均為 FALSE,表明該內(nèi)存位置沒有進(jìn)行內(nèi)存釋放,也沒有全局變量指向該內(nèi)存位置.

·O3所對應(yīng)的特征15為TRUE,特征16為FALSE,表明該內(nèi)存位置沒有進(jìn)行內(nèi)存釋放,但存在全局變量指向該內(nèi)存位置.

Fig.2 Example of feature extraction圖2 特征提取示例

2.2.2 內(nèi)存泄漏檢測

獲取所有內(nèi)存泄漏特征的數(shù)據(jù)集后,我們首先根據(jù)判定規(guī)則依次對數(shù)據(jù)集進(jìn)行篩選,判斷結(jié)果主要分為 3類:疑似內(nèi)存泄漏,表示為T;可能非內(nèi)存泄漏,表示為F;無法判斷,表示為N.內(nèi)存泄漏判定規(guī)則如下.

(1) 若特征15、特征16全部為假(即在SVFG中,沒有全局變量指向該內(nèi)存分配點(diǎn),也不存在內(nèi)存釋放語句),則判定結(jié)果為T.

(2) 若特征15為真、特征16為假(即在SVFG中,存在全局變量指向該內(nèi)存分配點(diǎn),不存在內(nèi)存釋放語句),則判定結(jié)果為N.

(3) 對于不滿足第1條規(guī)則且不滿足第2條規(guī)則的數(shù)據(jù),提交給內(nèi)存泄漏檢測模型,得到內(nèi)存泄漏檢測結(jié)果.內(nèi)存泄漏模型中檢測結(jié)果分為兩類:T和F.

根據(jù)判定規(guī)則(1)和規(guī)則(2):若在SVFG中沒有全局變量指向該內(nèi)存分配點(diǎn),也不存在內(nèi)存釋放語句,則可直接判斷為疑似內(nèi)存泄漏;若在SVFG中存在全局變量指向該內(nèi)存分配點(diǎn),但不存在內(nèi)存釋放語句,由于全局變量可能在任何地方釋放,我們不做判斷,視為警報(bào).因此根據(jù)規(guī)則(1)和規(guī)則(2),我們可直接判斷數(shù)據(jù)對應(yīng)的分類結(jié)果,無需使用內(nèi)存泄漏檢測模型.根據(jù)第3條規(guī)則,圖2(b)中O1所對應(yīng)的特征應(yīng)該輸入內(nèi)存泄漏檢測模型.根據(jù)第1條規(guī)則,圖2(b)中O2所對應(yīng)特征的判定結(jié)果為疑似內(nèi)存泄漏.根據(jù)第2條規(guī)則,圖2(b)中O3所對應(yīng)的特征則無法判斷是否發(fā)生內(nèi)存泄露.

提取數(shù)據(jù)集中判定結(jié)果為疑似內(nèi)存泄漏的分配點(diǎn),并結(jié)合內(nèi)存位置信息給出漏洞報(bào)告.報(bào)告中標(biāo)明疑似內(nèi)存泄漏,并給出每個(gè)泄漏點(diǎn)的文件名、行號以及分配語句.

3 工具與評估

我們基于LLVM編譯器(版本4.0.0)實(shí)現(xiàn)我們的C程序內(nèi)存泄漏智能化檢測工具I_Mem,工具框架如圖3所示.我們的智能化檢測工具I_Mem主要分為3個(gè)模塊:內(nèi)存泄漏檢測模型、特征提取和內(nèi)存泄漏檢測.分別于第2.1節(jié)、第2.2.1節(jié)和第2.2.2節(jié)對應(yīng).

Fig.3 Framework of I_Mem圖3 I_Mem框架

在實(shí)驗(yàn)中,每個(gè)C程序的源文件都由Clang編譯成LLVM bitcode文件格式,再由LLVM Gold Plugin進(jìn)行合并,生成整個(gè)程序的bc文件.在模型構(gòu)建階段,我們使用的SVM分類器是libSVM[22],隨機(jī)機(jī)森林和決策樹使用的是機(jī)器學(xué)習(xí)工具 weka[23].我們的實(shí)驗(yàn)分為兩部分:一是在模型構(gòu)建階段對我們的模型進(jìn)行評估;二是在特征提取與缺陷檢測階段對內(nèi)存泄漏的檢測結(jié)果進(jìn)行評估.

3.1 模型構(gòu)建階段

我們從開源的 C程序中提取真正的與虛假的內(nèi)存泄漏實(shí)例來構(gòu)建機(jī)器學(xué)習(xí)分類器,我們提取內(nèi)存泄漏示例的開源C程序主要有icecast-2.3.1,cluster-3.0,droplet-3.0,wine-0.9.24以及SPEC 2000中的ammp,equak,然后,通過以下步驟獲取真正的與虛假的內(nèi)存泄漏.

(1) 關(guān)注源碼中所有的內(nèi)存分配點(diǎn),通過添加或者注釋內(nèi)存釋放點(diǎn)來獲取真正的與虛假的內(nèi)存泄漏.

(2) 仿照已經(jīng)獲取的內(nèi)存泄漏實(shí)例,在源碼中插入各種內(nèi)存泄漏以構(gòu)建豐富的訓(xùn)練集,盡量滿足各個(gè)特征的屬性.

通過以上兩個(gè)步驟,我們可以獲取大量的內(nèi)存泄漏實(shí)例用于機(jī)器學(xué)習(xí)分類器的構(gòu)建.模型構(gòu)建階段總過獲取了1 728個(gè)內(nèi)存泄漏實(shí)例(396個(gè)虛假內(nèi)存泄漏,1 332個(gè)真正內(nèi)存泄漏).構(gòu)建模型中,我們采用五折交叉驗(yàn)證來確定準(zhǔn)確率最高的分類器類型和參數(shù).準(zhǔn)確率是正確分類的樣本數(shù)與總樣本數(shù)之比.

我們使用五折交叉驗(yàn)證,在1 728個(gè)實(shí)例中進(jìn)行模型訓(xùn)練與評估,對于SVM、隨機(jī)森林和決策樹這3種機(jī)器學(xué)習(xí)算法,我們選取每種機(jī)器學(xué)習(xí)算法在訓(xùn)練過程中準(zhǔn)確率最高的進(jìn)行展示,見表3.

Table 3 Results of classification表3 分類結(jié)果

如表3所示,SVM的分類準(zhǔn)確率為97.7%,隨機(jī)森林與決策樹的準(zhǔn)確率99.6%.因?yàn)闆Q策樹容易出現(xiàn)過擬合現(xiàn)象,因此我們選取隨機(jī)森林作為我們內(nèi)存泄漏檢測模型.實(shí)驗(yàn)結(jié)果表明,我們構(gòu)建的隨機(jī)森林模型在對真實(shí)與虛假的內(nèi)存泄漏進(jìn)行分類時(shí)是有效的.

3.2 特征提取與缺陷檢測階段

我們的實(shí)驗(yàn)分為兩部分.

· 第1部分的實(shí)驗(yàn)數(shù)據(jù)來自基準(zhǔn)程序Siemens[24].共有4個(gè)程序,這些實(shí)驗(yàn)對象的規(guī)模都比較小,存在的內(nèi)存泄漏不多,因此,我們在源碼中手工植入內(nèi)存泄漏,特別是植入與數(shù)組、循環(huán)、鏈表等有關(guān)的內(nèi)存泄漏,以驗(yàn)證內(nèi)存泄漏模型在檢測各種類型內(nèi)存泄漏時(shí)的有效性.

· 第2部分?jǐn)?shù)據(jù)來源于原生SPEC 2000[25],我們選取了3個(gè)程序,以驗(yàn)證內(nèi)存泄漏模型在檢測大規(guī)模程序時(shí)的有效性.

實(shí)驗(yàn)對象見表4.

Table 4 Experimental subjects表4 實(shí)驗(yàn)對象

我們的方法是在 SVFG的基礎(chǔ)上提取內(nèi)存泄漏特征,并利用機(jī)器學(xué)習(xí)技術(shù)進(jìn)行內(nèi)存泄漏檢測,因此,我們選取Saber來比較本文方法和靜態(tài)分析方法的效果.Saber通過構(gòu)建源碼的SVFG來判斷內(nèi)存泄漏.在表5中展示了本文方法與Saber在Siemens程序上的對比實(shí)驗(yàn)結(jié)果.

根據(jù)表5中的結(jié)果,我們可以得到如下結(jié)論.

(1) 兩種內(nèi)存泄漏檢測方法的漏報(bào)數(shù)目都比較低;

(2) 針對內(nèi)存泄漏的一些特殊案例,如內(nèi)存泄漏的分配、使用或者釋放出現(xiàn)了循環(huán)、遞歸、鏈表等情況時(shí),Saber誤報(bào)較多,例如print_tokens程序中的34個(gè)內(nèi)存分配點(diǎn),Saber的誤報(bào)是10個(gè),本文只有5個(gè).

Table 5 Experimental results of Siemens表5 Siemens實(shí)驗(yàn)結(jié)果

表6為SPEC 2000的實(shí)驗(yàn)結(jié)果.總結(jié)兩部分實(shí)驗(yàn),我們可以得到如下結(jié)論.

(1) 本文方法在靜態(tài)分析的基礎(chǔ)上利用機(jī)器學(xué)習(xí)算法提高了內(nèi)存泄漏檢測在特殊案例上的準(zhǔn)確性.

(2) 本文的內(nèi)存泄漏模型在檢測大規(guī)模程序時(shí)是有效的.

Table 6 Experimental results of SPEC 2000表6 SPEC 2000實(shí)驗(yàn)結(jié)果

3.3 討 論

內(nèi)存泄漏靜態(tài)分析方法的缺點(diǎn)在于大規(guī)模程序誤報(bào)多,需要人工確認(rèn).本文利用機(jī)器學(xué)習(xí)方法獲取已有的知識經(jīng)驗(yàn),幫助提高內(nèi)存泄漏靜態(tài)分析的準(zhǔn)確性.在選取內(nèi)存泄漏特征時(shí),我們研究內(nèi)存泄漏機(jī)理,調(diào)研內(nèi)存泄漏檢測方法,從而確定內(nèi)存泄漏相關(guān)特征,并構(gòu)建內(nèi)存泄漏檢測模型.實(shí)驗(yàn)結(jié)果表明,本文方法確實(shí)有助于提高內(nèi)存泄漏檢測的準(zhǔn)確率.在模型構(gòu)建階段,我們對構(gòu)建的內(nèi)存泄漏檢測模型進(jìn)行五折交叉驗(yàn)證,交叉驗(yàn)證結(jié)果準(zhǔn)確率高達(dá) 95%以上.實(shí)驗(yàn)結(jié)果表明,我們構(gòu)建的內(nèi)存泄漏檢測模型在對真實(shí)與虛假的內(nèi)存泄漏進(jìn)行檢測時(shí)是有效的.在特征提取與缺陷檢測階段,在Siemens的實(shí)驗(yàn)數(shù)據(jù)上,我們的方法與Saber進(jìn)行對比實(shí)驗(yàn),Saber的平均準(zhǔn)確率只有69.5%,我們的方法準(zhǔn)確率高達(dá)88.1%;在SPEC 2000的實(shí)驗(yàn)數(shù)據(jù)上,總共184內(nèi)存分配點(diǎn),Saber的誤報(bào)為11個(gè),我們的誤報(bào)只有2個(gè).

綜上所述,我們的實(shí)驗(yàn)結(jié)果表明,C程序內(nèi)存泄漏智能化檢測方法在針對數(shù)組、循環(huán)等相關(guān)的內(nèi)存泄漏時(shí)能夠得到更加準(zhǔn)確的檢測結(jié)果.在靜態(tài)分析的基礎(chǔ)上,利用機(jī)器學(xué)習(xí)算法,使得內(nèi)存泄漏檢測結(jié)果更加準(zhǔn)確.此外,實(shí)驗(yàn)中存在一些不足需要注意:目前,我們只針對 C語言內(nèi)存泄漏進(jìn)行檢測,并不支持 C++;實(shí)驗(yàn)中,我們所選取的是簡單的基準(zhǔn)程序,并在源碼中插入一些內(nèi)存泄漏特殊案例,并不保證該方法對內(nèi)存泄漏其他特殊案例檢測都具有較高的準(zhǔn)確率.但是我們相信,實(shí)驗(yàn)的結(jié)果確實(shí)表明了本文的方法在檢測內(nèi)存泄漏上的可行性及準(zhǔn)確性.

4 相關(guān)工作

在本節(jié)中,我們主要通過以下3個(gè)方面來介紹和討論相關(guān)工作:(1) 內(nèi)存泄漏的靜態(tài)分析;(2) 內(nèi)存泄漏的動態(tài)檢測;(3) 基于機(jī)器學(xué)習(xí)的缺陷檢測.

4.1 內(nèi)存泄漏的靜態(tài)分析

內(nèi)存泄漏通常是由于人為的對程序中動態(tài)內(nèi)存的管理不當(dāng)造成的,內(nèi)存泄漏會導(dǎo)致內(nèi)存空間被消耗,且在程序運(yùn)行期間無法回收和重新利用.內(nèi)存泄漏十分隱蔽,在程序運(yùn)行初期不易被發(fā)現(xiàn);但是對于長期運(yùn)行的程序,特別是服務(wù)器,影響十分顯著,它會降低程序性能,甚至導(dǎo)致程序在運(yùn)行時(shí)崩潰.特別是在 C語言中,內(nèi)存的分配與釋放都是人為控制的,內(nèi)存釋放這一步驟極容易被忽略,從而導(dǎo)致內(nèi)存泄漏.

靜態(tài)分析主要是根據(jù)特定的錯(cuò)誤模式來查找內(nèi)存泄漏,或者建立內(nèi)存狀態(tài)模型來進(jìn)行內(nèi)存泄漏檢測.Cherem 等人[7]通過構(gòu)建數(shù)據(jù)流圖進(jìn)行數(shù)據(jù)流分析,分析數(shù)值從內(nèi)存分配點(diǎn)到內(nèi)存釋放點(diǎn)的路徑中是否正確傳播來檢測內(nèi)存泄露.Saber通過構(gòu)建C程序的SVFG檢測內(nèi)存泄漏.Orlovich等人[10]首先假設(shè)內(nèi)存泄漏存在,然后進(jìn)行反向數(shù)據(jù)流分析,驗(yàn)證該假設(shè)是否成立.RL_Detector[11]基于控制流圖(CFG)進(jìn)行數(shù)據(jù)流分析,利用靜態(tài)符號執(zhí)行對于每個(gè)資源(包括內(nèi)存泄露)收集所有路徑約束,通過路徑約束計(jì)算數(shù)據(jù)流條件并檢測資源泄露.Heine等人[12]開發(fā)了一個(gè)描述指針隸屬關(guān)系的模型,在該模型中,每個(gè)內(nèi)存對象只能被1個(gè)擁有指針指向,因此該指針是唯一的且具有傳遞性,基于此對程序生成一種約束,用來檢測內(nèi)存泄漏.Cai等人[26]提出了基于上下文無關(guān)文法可達(dá)性的由調(diào)用上下文向引用上下文自動轉(zhuǎn)換的方法,用于輔助內(nèi)存泄漏動態(tài)檢測方法,從而提供對象引用路徑等更豐富的報(bào)告信息,也為將來擴(kuò)展我們方法中內(nèi)存泄漏特征提供參考.

內(nèi)存泄漏靜態(tài)分析的優(yōu)點(diǎn)是能夠自動化運(yùn)行,檢測速度快;缺點(diǎn)是誤報(bào)較多.目前,也有一些工作是在靜態(tài)分析的基礎(chǔ)上對內(nèi)存泄漏進(jìn)行修復(fù).內(nèi)存泄漏修復(fù)需要首先定位內(nèi)存泄漏位置,因此,內(nèi)存泄漏修復(fù)的準(zhǔn)確性首先取決于內(nèi)存定位的準(zhǔn)確性,其次是插入釋放語句的準(zhǔn)確性.目前,主要的內(nèi)存泄漏修復(fù)工作有:

· Leakfix[27]基于指針分析和數(shù)據(jù)流分析,判斷內(nèi)存泄露位置并進(jìn)行內(nèi)存泄漏的修復(fù).Leakfix能夠保證為一個(gè)內(nèi)存泄露生成多個(gè)修復(fù)程序,但不能保證生成的修復(fù)程序完全解決了該內(nèi)存泄漏.

· AutoFix[28]是根據(jù)已有的靜態(tài)分析警報(bào),通過指針分析構(gòu)建 VFG,再根據(jù)活性分析判斷內(nèi)存泄漏位置,進(jìn)行內(nèi)存泄漏的修復(fù).Autofix通過代碼插樁進(jìn)行內(nèi)存泄漏的修復(fù),并在一個(gè)沙箱中運(yùn)行程序進(jìn)行檢查,確保修復(fù)的安全性.

內(nèi)存泄漏的修復(fù)首先需要確保內(nèi)存泄漏檢測的準(zhǔn)確性,不能對誤報(bào)進(jìn)行修復(fù);其次,內(nèi)存泄漏修復(fù)需要保證修復(fù)的正確性.Leakfix在修復(fù)之后需要使用內(nèi)存泄漏檢測工具進(jìn)行檢測,AutoFix則是自動的在修復(fù)之后運(yùn)行程序進(jìn)行安全性檢查.因此,內(nèi)存泄漏的修復(fù)受限于規(guī)模,如何提高內(nèi)存泄漏修復(fù)的可擴(kuò)展性以及準(zhǔn)確性依然是一個(gè)難題.

本文的主要工作是在靜態(tài)分析的基礎(chǔ)上,利用機(jī)器學(xué)習(xí)技術(shù)進(jìn)行內(nèi)存泄漏檢測,減少了靜態(tài)分析的漏報(bào)和誤報(bào),提高了靜態(tài)分析的準(zhǔn)確性,尤其在針對內(nèi)存泄漏的特殊案例時(shí),能夠顯著提高內(nèi)存泄漏檢測的準(zhǔn)確性.

4.2 內(nèi)存泄漏的動態(tài)檢測

內(nèi)存泄漏的動態(tài)檢測方法需要運(yùn)行源代碼,在程序運(yùn)行過程中對內(nèi)存分配、使用以及釋放進(jìn)行動態(tài)跟蹤.LeakPoint[1]基于污點(diǎn)傳播的思想監(jiān)控內(nèi)存對象的狀態(tài),追蹤內(nèi)存最后的使用位置以及失去引用的位置.DOUBLETAKE[2]將程序執(zhí)行拆分為多個(gè)塊,在每個(gè)塊運(yùn)行開始之前保存程序狀態(tài),在該塊之行結(jié)束之后檢查程序狀態(tài),判斷內(nèi)存是否發(fā)生錯(cuò)誤.Sniper[3]利用處理器的監(jiān)視單元(PMU)進(jìn)行指令采樣,來跟蹤對于堆內(nèi)存的訪問指令,然后通過離線模擬器分析指令計(jì)算堆對象的陳舊度,并重新執(zhí)行相關(guān)指令,捕獲程序執(zhí)行期間的內(nèi)存泄漏.Omega[4]主要采用指針計(jì)數(shù)的思想記錄內(nèi)存對象的引用計(jì)數(shù).

動態(tài)檢測相對于靜態(tài)分析更加準(zhǔn)確,但是動態(tài)檢測無法分析程序執(zhí)行中不可達(dá)位置的錯(cuò)誤.動態(tài)檢測最大的缺點(diǎn)是效率低,耗時(shí)長.目前,代碼規(guī)模和復(fù)雜度日漸增加,內(nèi)存泄漏的動態(tài)檢測效率遠(yuǎn)遠(yuǎn)無法滿足工業(yè)界的需求,并且隨著靜態(tài)分析技術(shù)的發(fā)展,內(nèi)存泄漏靜態(tài)分析結(jié)果的準(zhǔn)確率逐漸提高,靜態(tài)分析的使用更加廣泛.因此,本文的方法是基于靜態(tài)分析,利用規(guī)則和機(jī)器學(xué)習(xí)技術(shù)進(jìn)行內(nèi)存泄漏檢測,具有高效率和高可靠性.

4.3 基于機(jī)器學(xué)習(xí)的缺陷檢測

目前,機(jī)器學(xué)習(xí)技術(shù)已被廣泛運(yùn)用于程序分析中以檢測程序缺陷.Alatwi等人[29]實(shí)現(xiàn)了一種檢測安卓應(yīng)用程序是否屬于惡意軟件的方法,其主要思想是將 apk反匯編為源碼,然后利用靜態(tài)分析方法提取代碼代征,并選取可用于模型預(yù)測的最佳特征組合,構(gòu)建 SVM 分類器進(jìn)行檢測.Tac[20]主要利用機(jī)器學(xué)習(xí)算法來消除 typestate和指針分析的差距,它從源碼中提取35個(gè)特征,并訓(xùn)練SVM分類器以檢測Use-After-Free.Nagano等人[30]對執(zhí)行文件進(jìn)行靜態(tài)分析,然后利用機(jī)器學(xué)習(xí)的分類算法及自然語言處理技術(shù)來識別惡意軟件.Grieco等人[31]從二進(jìn)制文件中提取程序靜態(tài)特征,從程序執(zhí)行中提取動態(tài)特征,然后利用機(jī)器學(xué)習(xí)技術(shù)訓(xùn)練模型來檢測內(nèi)存沖突.

本文的主要工作是通過靜態(tài)分析提取內(nèi)存泄漏特征,然后利用規(guī)則和機(jī)器學(xué)習(xí)模型檢測內(nèi)存泄漏.我們關(guān)注的重點(diǎn)是內(nèi)存泄漏的特殊案例,因此在檢測內(nèi)存泄漏上準(zhǔn)確性更高.

5 總結(jié)與展望

本文提出了一種 C程序內(nèi)存泄漏智能化檢測方法,首先構(gòu)建機(jī)器學(xué)習(xí)模型,然后在內(nèi)存泄漏靜態(tài)分析的基礎(chǔ)上提取內(nèi)存泄漏特征,并利用規(guī)則和機(jī)器學(xué)習(xí)模型進(jìn)行內(nèi)存泄漏的檢測.實(shí)驗(yàn)結(jié)果表明,我們構(gòu)建的內(nèi)存泄漏檢測模型在對真實(shí)與虛假的內(nèi)存泄漏進(jìn)行檢測時(shí)是有效的.相對于目前的內(nèi)存泄漏靜態(tài)分析方法,本文方法在針對數(shù)組、循環(huán)等相關(guān)的內(nèi)存泄漏時(shí)檢測結(jié)果更加準(zhǔn)確.

在本文方法的實(shí)驗(yàn)中,我們也遇到了一些問題和挑戰(zhàn),這也是我們未來的研究方向:(1) 目前,本文在特征選取與缺陷檢測階段選取的實(shí)驗(yàn)數(shù)據(jù)為簡單程序且人為插入了各種內(nèi)存泄漏,下一步需要選取一些開源的大型程序進(jìn)行實(shí)驗(yàn);(2) 本文目前關(guān)注的重點(diǎn)是C語言中與循環(huán)、結(jié)構(gòu)體、數(shù)組以及鏈表有關(guān)的內(nèi)存泄漏,可以擴(kuò)展至 C++中,關(guān)注類以及各類容器有關(guān)的內(nèi)存泄漏問題;(3) 當(dāng)前的工作可以擴(kuò)展到其他內(nèi)存缺陷中,目前提取的特征適用于構(gòu)建內(nèi)存泄漏的分類器,我們可以提取更多的程序特征,構(gòu)建多種內(nèi)存缺陷檢測的分類器;(4) 本文目前的靜態(tài)分析方法是對每個(gè)內(nèi)存分配點(diǎn)提取一個(gè)內(nèi)存泄漏特征,我們可以進(jìn)行細(xì)化,對于每個(gè)內(nèi)存分配點(diǎn)的每條路徑提取一個(gè)內(nèi)存泄漏特征,這樣,檢測結(jié)果會更加準(zhǔn)確,檢測報(bào)告會更加詳細(xì).