C程序內存泄漏智能化檢測方法?

朱亞偉,左志強,王林章,李宣東

(計算機軟件新技術國家重點實驗室(南京大學),江蘇 南京 210023)

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

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

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

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

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

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

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

本文的主要貢獻在于:

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

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

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

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

1 背 景

針對內存泄漏的程序靜態(tài)分析需要在獲取所有內存分配點后,關注內存的定義、使用及釋放.此外,C語言中由于函數(shù)可以返回指針,內存泄漏檢測需要對調用點作分析.因此,Saber[8,9]關注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,通過構建 SVFG來檢測內存泄漏.其中,VFG(value flow graph)[7,16]表示的是句法上的語義等價,它關注變量的定義、使用,能夠表示程序中變量的價值流向.VFG不同于CFG(control flow graph)和DFG(data flow graph),CFG表示的是控制程序邏輯執(zhí)行的先后順序,一個程序的CFG被用來確定對變量的一次賦值可能傳播到程序中的哪些位置;DFG是在CFG基礎上實現(xiàn)的,它描述的是程序運行過程中數(shù)據(jù)的流轉方式及其行為狀態(tài).在 VFG中,每一個節(jié)點表示變量的定義,每條邊表示變量的def-use關系.Saber針對VFG進行改進構建了SVFG.SVFG的構建主要分為3個步驟.

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

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

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

2 C程序內存泄漏智能化檢測方法

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

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

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

(1) 模型構建階段

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

? 然后,將訓練集輸入機器學習的分類器進行訓練,并應用交叉驗證對分類器進行評估;

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

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

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

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

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

2.1 模型構建階段

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

Table 2 Features of memory leak表2 內存泄漏特征

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2.1 特征提取

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

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

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

· 最后遍歷FNode與BNode,獲取當前內存分配點對應的特征信息存入V中.

算法1.SVFG遍歷獲取內存泄漏特征.

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

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

·O2所對應的特征 15、特征 16均為 FALSE,表明該內存位置沒有進行內存釋放,也沒有全局變量指向該內存位置.

·O3所對應的特征15為TRUE,特征16為FALSE,表明該內存位置沒有進行內存釋放,但存在全局變量指向該內存位置.

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

2.2.2 內存泄漏檢測

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

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

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

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

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

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

3 工具與評估

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

Fig.3 Framework of I_Mem圖3 I_Mem框架

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

3.1 模型構建階段

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

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

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

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

我們使用五折交叉驗證,在1 728個實例中進行模型訓練與評估,對于SVM、隨機森林和決策樹這3種機器學習算法,我們選取每種機器學習算法在訓練過程中準確率最高的進行展示,見表3.

Table 3 Results of classification表3 分類結果

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

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

我們的實驗分為兩部分.

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

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

實驗對象見表4.

Table 4 Experimental subjects表4 實驗對象

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

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

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

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

Table 5 Experimental results of Siemens表5 Siemens實驗結果

表6為SPEC 2000的實驗結果.總結兩部分實驗,我們可以得到如下結論.

(1) 本文方法在靜態(tài)分析的基礎上利用機器學習算法提高了內存泄漏檢測在特殊案例上的準確性.

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

Table 6 Experimental results of SPEC 2000表6 SPEC 2000實驗結果

3.3 討 論

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

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

4 相關工作

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

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

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

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

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

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

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

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

本文的主要工作是在靜態(tài)分析的基礎上,利用機器學習技術進行內存泄漏檢測,減少了靜態(tài)分析的漏報和誤報,提高了靜態(tài)分析的準確性,尤其在針對內存泄漏的特殊案例時,能夠顯著提高內存泄漏檢測的準確性.

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

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

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

4.3 基于機器學習的缺陷檢測

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

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

5 總結與展望

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

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