基于圖拓?fù)涮卣鞯膼阂廛浖葱苑治黾夹g(shù)研究

黎奇，劉嘉勇，賈鵬，劉露平

（四川大學(xué)電子信息學(xué)院，成都 610065）

0 引言

隨著計(jì)算機(jī)技術(shù)的發(fā)展，惡意軟件越來越危害著網(wǎng)絡(luò)安全。Symantec 2017年發(fā)布的威脅報(bào)告顯示，惡意軟件不僅數(shù)量快速增長，而且呈現(xiàn)出變種越來越多、結(jié)構(gòu)越來越復(fù)雜的特點(diǎn)[1]。由于變種和多態(tài)技術(shù)的普及、自動(dòng)混淆工具的出現(xiàn)，惡意軟件的指令通過重排序及等效序列替換，改變了樣本原有的特征，從而達(dá)到規(guī)避殺毒軟件查殺的目的。惡意樣本的多樣變種為分析惡意軟件帶來了很大的挑戰(zhàn)[2]。

惡意軟件同源性分析根據(jù)樣本的家族屬性可以對未知樣本進(jìn)行分類識(shí)別。在過去的研究工作中，惡意樣本同源性分析通常是將樣本視為字節(jié)序列提取樣本的家族特征[3,6]，基于字節(jié)序列進(jìn)行分類的方法忽視了程序的控制流程圖和函數(shù)調(diào)用圖的結(jié)構(gòu)信息對分類結(jié)果的影響，有著天然的缺陷[6]。大多數(shù)惡意軟件都是由高級編程語言編寫而成，源代碼的微小變化會(huì)引起二進(jìn)制代碼的顯著改變，并且字節(jié)序列的改變并不能反映出樣本功能或結(jié)構(gòu)的改變。

傳統(tǒng)基于圖分析惡意樣本同源性的核心思想是比較不同樣本函數(shù)調(diào)用圖之間圖形的相似性[7]。早期方法是計(jì)算圖之間的編輯距離，Kinable J和Kostakis O[5][5]等人通過此方法測量圖形間相似性。通過計(jì)算圖編輯距離比較圖形相似性的優(yōu)點(diǎn)在于可以定義自己的成本函數(shù)，但該方法的時(shí)間復(fù)雜度隨圖節(jié)點(diǎn)數(shù)量的增加呈指數(shù)增長。為此，Hu X、Chiueh T C和Kang G S[6]使用匈牙利（Hungarian）算法對傳統(tǒng)基于圖編輯距離測量圖相似度的思路做了改進(jìn)，從而在立方階O（n3）的時(shí)間復(fù)雜度中計(jì)算出兩個(gè)圖的相似度。此外，Xu M、Wu L和Qi S[7]等人通過對圖所擁有邊的數(shù)量進(jìn)行標(biāo)準(zhǔn)化來度量圖的相似性。Shohei H和Hisashi K[8]用圖中每個(gè)頂點(diǎn)的鄰域哈希值替換節(jié)點(diǎn)的初始標(biāo)簽后，通過計(jì)算兩個(gè)圖頂點(diǎn)標(biāo)簽集的交集比率，比較兩個(gè)函數(shù)調(diào)用圖的相似度。

與以往僅通過比較惡意樣本函數(shù)調(diào)用圖的結(jié)構(gòu)進(jìn)行樣本同源性研究不同，Jang J W和Woo J[10]等人在2015年提出基于網(wǎng)絡(luò)分析的惡意軟件分類方法中，驗(yàn)證了函數(shù)調(diào)用圖的特征（如度中心性、網(wǎng)絡(luò)密度）可有效區(qū)分正常軟件和惡意軟件，其分類準(zhǔn)確率達(dá)到96%，但該研究沒有用網(wǎng)絡(luò)分析方法對惡意樣本進(jìn)行家族間的分類。

1 基于圖拓?fù)涮卣鞯耐葱苑诸惙椒?/h2>

惡意軟件在執(zhí)行過程中會(huì)調(diào)用很多函數(shù)[4]，同一個(gè)家族軟件的函數(shù)調(diào)用圖有相似的結(jié)構(gòu)信息，本文假設(shè)函數(shù)調(diào)用圖的拓?fù)涮卣骺梢赃M(jìn)行惡意軟件家族分類，基于此，提出基于圖拓?fù)涮卣鞯膼阂廛浖葱苑治龅姆椒?，并進(jìn)行分類實(shí)驗(yàn)。

本文首先生成軟件的函數(shù)調(diào)用圖，根據(jù)函數(shù)調(diào)用圖提取出圖的拓?fù)涮卣骷巴獠亢瘮?shù)名，最后使用機(jī)器學(xué)習(xí)分類算法根據(jù)函數(shù)調(diào)用圖提取出的相關(guān)特征進(jìn)行同源性分類，并進(jìn)行分類評估。惡意軟件同源性分類框架如圖1所示。

圖1 惡意軟件同源性分類框架

1. 1 拓?fù)涮卣魈崛〖斑^濾

在提取出惡意軟件的函數(shù)調(diào)用圖后，通過把函數(shù)視為節(jié)點(diǎn)，函數(shù)間的調(diào)用關(guān)系視為有向邊后，抽象函數(shù)調(diào)用圖為一個(gè)網(wǎng)絡(luò)。本文生成的網(wǎng)絡(luò)數(shù)據(jù)文本格式如下所示：

其中，directed項(xiàng)為true表示生成的是有向圖；nodes項(xiàng)中以數(shù)字0～n標(biāo)記并表示函數(shù)調(diào)用圖中函數(shù)的名稱；links項(xiàng)中每對{source:n,target:k},k∈[0,n]表示一對函數(shù)調(diào)用關(guān)系，其中source表示調(diào)用函數(shù)，target表示被調(diào)用函數(shù)。

1. 2 函數(shù)調(diào)用圖提取

函數(shù)調(diào)用圖G是一個(gè)由函數(shù)集合V和函數(shù)間關(guān)系集合E組成的有向圖，如圖2所示。函數(shù)調(diào)用圖的數(shù)學(xué)表達(dá)式為：G=(V,E)。

圖2 函數(shù)調(diào)用圖

函數(shù)調(diào)用圖中頂點(diǎn)有兩類函數(shù)構(gòu)成：

（1）本地函數(shù)，程序設(shè)計(jì)者定義的函數(shù)；

（2）外部函數(shù)，系統(tǒng)函數(shù)或庫函數(shù)。

由于在不同的二進(jìn)制文件中，即使兩個(gè)本地函數(shù)功能相同，在靜態(tài)分析過程中，也很難識(shí)別出來。靜態(tài)分析工具一般以sub_開頭的隨機(jī)符號命名本地函數(shù)[11]，因此，本文沒有把本地函數(shù)名作為同源性惡意樣本的分類依據(jù)。

對于外部函數(shù)，本文通過解析樣本PE頭中的導(dǎo)入地址（IAT）表找到外部函數(shù)名稱，對于外部函數(shù)中的靜態(tài)鏈接庫函數(shù)，使用了Fast Library Identification and Recognition Technology（FLITERT）識(shí)別出它們的原始名稱[12]。同一家族的惡意樣本很大概率會(huì)調(diào)用相同的外部函數(shù)。因此，本文把樣本函數(shù)調(diào)用圖的外部函數(shù)名如：ExitProcess、MessageBoxA作為惡意軟件同源性分類一個(gè)單獨(dú)的特征向量。

當(dāng)所有函數(shù)被識(shí)別出來后，根據(jù)提取出來的函數(shù)調(diào)用關(guān)系添加頂點(diǎn)之間的有向邊，生成最終的函數(shù)調(diào)用圖。

（1）拓?fù)涮卣魈崛?/p>

網(wǎng)絡(luò)分析離不開對網(wǎng)絡(luò)拓?fù)涮卣鞯挠?jì)算，本文用NetworkX[13]雜網(wǎng)絡(luò)分析工具中已有的算法對每個(gè)惡意軟件對應(yīng)的網(wǎng)絡(luò)進(jìn)行特征提取。在網(wǎng)絡(luò)分析工具中，計(jì)算網(wǎng)絡(luò)結(jié)構(gòu)的拓?fù)涮卣靼ń菩?、擬合性、中心性等42大類，每類拓?fù)涮卣鞫加幸恍┳犹卣饔糜谘芯空叻治鼍W(wǎng)絡(luò)結(jié)構(gòu)。

網(wǎng)絡(luò)的單一特征并不能很好地分類惡意軟件家族，不同家族的同一網(wǎng)絡(luò)特征值可能相同，同一家族的同一網(wǎng)絡(luò)特征值并不完全相同[10]。在這里，本文提取出了網(wǎng)絡(luò)48個(gè)子特征供后面篩選，表1中列出了選取的部分特征。

表1 部分復(fù)雜網(wǎng)絡(luò)特征

（2）拓?fù)涮卣鬟x擇

網(wǎng)絡(luò)分析依賴的是與研究相關(guān)拓?fù)涮卣鞯挠?jì)算，不是越多特征，越有利于目標(biāo)的分類，反之，多余的特征會(huì)影響分類的正確性[4]。在初次選擇的48個(gè)特征中只有部分特征與惡意樣本家族分類相關(guān)。為了精簡特征集，需要對這些特征進(jìn)行選擇。由于每個(gè)子特征對家族預(yù)測能力不同，特征間也存在相互關(guān)聯(lián)的現(xiàn)象[15]。為了選取出家族預(yù)測能力強(qiáng)且組成的特征集關(guān)聯(lián)性低的單個(gè)特征，本文選擇了過濾器模式的基于關(guān)聯(lián)的特征選擇（CFS）方法進(jìn)行特征篩選[14]，其評估方法為：

其中：Ms為對一個(gè)包含有k個(gè)特征項(xiàng)的特征子集s的評價(jià)；rˉcf為特征與類之間的平均相關(guān)度；rˉff為特征與特征之間的平均相關(guān)度。

本文使用CFS方法對48個(gè)特征過濾后，選出了如下所示的8個(gè)拓?fù)涮卣骷希鳛閻阂鈽颖就葱缘姆诸愐罁?jù)：

（1）傳遞性

傳遞性表示網(wǎng)絡(luò)中連接同一個(gè)節(jié)點(diǎn)的兩個(gè)節(jié)點(diǎn)相互連接的可能性，即網(wǎng)絡(luò)中可能組成三角形的比例，屬于聚類特征。計(jì)算方式如公式（2）所示。

triangles指網(wǎng)絡(luò)中三角形的數(shù)量，triads指有兩條邊有相同頂點(diǎn)的數(shù)量，結(jié)果為浮點(diǎn)數(shù)。

（2）強(qiáng)連通分量數(shù)

有向網(wǎng)絡(luò)強(qiáng)連通分量：在有向網(wǎng)絡(luò)中，如果一對頂點(diǎn) Vi,Vj,Vi≠ Vj間存在 Vi到 Vj及 Vj到 Vi的路徑，則稱兩個(gè)頂點(diǎn)強(qiáng)連通。有向網(wǎng)絡(luò)的極大強(qiáng)連通子圖，稱為強(qiáng)連通分量，屬于組件類特征。

（3）強(qiáng)連通點(diǎn)

強(qiáng)連通點(diǎn)：為強(qiáng)連通分量中的節(jié)點(diǎn)，該特征屬于組件類，把強(qiáng)連通點(diǎn)的標(biāo)號作為一個(gè)特征。

（4）吸引分量的數(shù)量

吸引分量屬于強(qiáng)連通分量，吸引分量具有一旦進(jìn)入，則一直在這個(gè)分量中循環(huán)的屬性，屬于組件類特征。

（5）平均連通度

網(wǎng)絡(luò)的平均連通度是反應(yīng)網(wǎng)絡(luò)可靠性的參數(shù)之一，是經(jīng)典連通度的推廣，屬于連通性特征類，計(jì)算方式如公式（3）所示。

u,v指的是網(wǎng)絡(luò)中的節(jié)點(diǎn)。

（6）簡單循環(huán)長度

簡單循環(huán)是指網(wǎng)絡(luò)中一個(gè)封閉的路徑，此路徑中節(jié)點(diǎn)不會(huì)重復(fù)出現(xiàn)，把FCG生成的網(wǎng)絡(luò)的簡單循環(huán)節(jié)點(diǎn)的長度作為一個(gè)特征，屬于循環(huán)類特征。

（7）流層次結(jié)構(gòu)

度量流層次結(jié)構(gòu)是為了理解網(wǎng)絡(luò)的結(jié)構(gòu)機(jī)制和演化模式出現(xiàn)的，這里為有向網(wǎng)絡(luò)中不參與循環(huán)的邊的比例，該特征屬于距離相關(guān)特征度量類。

（8）密度

網(wǎng)絡(luò)密度，該特征用于測量網(wǎng)絡(luò)屬性，計(jì)算方式如公式（4）所示。

其中n為網(wǎng)絡(luò)節(jié)點(diǎn)的數(shù)量，m為網(wǎng)絡(luò)邊的數(shù)量。

綜上所述，本文使用CFS特征選擇算法，從初始48個(gè)拓?fù)涮卣骷羞x出1個(gè)聚類、3個(gè)組件類、1個(gè)連通性類、1個(gè)循環(huán)類、1個(gè)層結(jié)構(gòu)類和1個(gè)網(wǎng)絡(luò)屬性類特征作為家族同源性分析的依據(jù)。

2 實(shí)驗(yàn)評估

測試環(huán)境為裝有Weka3.8軟件的Windows 64位系統(tǒng)計(jì)算機(jī)，詳細(xì)配置為：CPU型號Intel Core i7 4790@3.60GHz，內(nèi)存 8GB。

2. 1 實(shí)驗(yàn)樣本

本文中實(shí)驗(yàn)數(shù)據(jù)均來源于VxHeavens數(shù)據(jù)集，該數(shù)據(jù)集中的樣本均按卡巴斯基命名規(guī)則命名。為了確保實(shí)驗(yàn)數(shù)據(jù)的準(zhǔn)確性，本文使用了VirusTotal網(wǎng)站抽樣驗(yàn)證樣本的家族命名。本次實(shí)驗(yàn)使用Windows平臺(tái)上的10個(gè)惡意樣本家族數(shù)據(jù)進(jìn)行同源性分析，10個(gè)樣本家族分別是：

實(shí)驗(yàn)中使用到每個(gè)家族的樣本數(shù)量如表2所示。

表2 惡意家族樣本

2. 2 測量指標(biāo)

通過判斷預(yù)測值是否很好地與實(shí)際標(biāo)記值相匹配可以評估分類算法的性能。本文用以下通用標(biāo)準(zhǔn)來度量分類方法的有效性：

精確率（Pr）：被預(yù)測為某個(gè)家族的惡意樣本中實(shí)際為該家族的樣本所占比例，計(jì)算公式：

其中TP表示正確分類到某個(gè)家族的數(shù)量，F(xiàn)P表示錯(cuò)誤分類到這個(gè)家族的數(shù)量。

召回率（Rc）：正確預(yù)測為某個(gè)家族數(shù)量和實(shí)際為該家族樣本數(shù)量的比值，計(jì)算公式：

其中TP表示正確分類到某個(gè)家族的數(shù)量，F(xiàn)N表示該家族實(shí)例被錯(cuò)誤分配到其他家族的數(shù)量。

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

本次實(shí)驗(yàn)使用10折交叉驗(yàn)證法，即將實(shí)驗(yàn)樣本分成10分，輪流將其中9分作為訓(xùn)練集，剩余1份作為測試集來評估分類。本次實(shí)驗(yàn)選擇LibSVM、Instance Based 1、RandomForest、BayesNet四種分類算法對樣本進(jìn)行了同源性分析。實(shí)驗(yàn)結(jié)果表明，四種分類算法的參數(shù)設(shè)定改變并沒有有效地提高分類的效果，因此本實(shí)驗(yàn)中的四種分類算法均采用Weka中默認(rèn)的參數(shù)值。各種算法分類結(jié)果如表3所示，表中包含每個(gè)分類算法對家族分類的Pr、Rc值。

表3 實(shí)驗(yàn)結(jié)果

通過表3中Pr、Rc兩類指標(biāo)的比較，可以看出RandomForest分類效果最好，精確率平均值和召回率平均值均為95.6%；Instance Based 1分類算法次之，精確率平均值和召回率平均值均為94.4%；BayesNet分類算法精確率平均值為85.4%，召回率平均值84.1%；LibSVM分類算法精確率平均值僅為77.4%，召回率平均值僅為78.4%。

耗時(shí)方面，因?yàn)镮nstance Based 1分類算法不需要建立模型，速度更快。使用RandomForest分類算法，構(gòu)建模型所需的時(shí)間為6.96秒；BayesNet構(gòu)建模型所需的時(shí)間為7.05秒；LibSVM構(gòu)建模型所需的時(shí)間為1.71秒。

綜合上所述，結(jié)合分類算法精確率、召回率和分類樣本所需建模時(shí)間，RandomForest適用于本次實(shí)驗(yàn)，達(dá)到較準(zhǔn)確的分類效果。

3 結(jié)語

本文在函數(shù)調(diào)用圖基礎(chǔ)上，結(jié)合網(wǎng)絡(luò)理論體系中的網(wǎng)絡(luò)分析方法,提出基于圖拓?fù)涮卣鞯膼阂廛浖葱苑治黾夹g(shù)。通過實(shí)驗(yàn)，RandomForest分類算法取得了精確率95.6%的分類效果，驗(yàn)證了本文提出思路的有效性和可行性。本文的貢獻(xiàn)有以下幾點(diǎn)：

（1）提出了一種基于函數(shù)調(diào)用圖拓?fù)涮卣骱蜋C(jī)器學(xué)習(xí)相結(jié)合的惡意軟件同源性分類方法；

（2）設(shè)計(jì)實(shí)驗(yàn)，驗(yàn)證了本文提出方法的有效性，在本文所使用的樣本集上，惡意軟件同源性分類精確率上達(dá)到了95.6%。

本文的缺陷在于特征提取方法不夠完善，實(shí)驗(yàn)結(jié)果中出現(xiàn)了某個(gè)家族分類效果明顯低于其他家族的現(xiàn)象。在下一步工作中，將優(yōu)化拓?fù)涮卣鬟x擇方法，加大樣本規(guī)模，以得到更好的實(shí)驗(yàn)結(jié)果。