基于圖拓撲特征的惡意軟件同源性分析技術(shù)研究

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

（四川大學電子信息學院，成都 610065）

0 引言

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

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

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

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

1 基于圖拓撲特征的同源性分類方法

惡意軟件在執(zhí)行過程中會調(diào)用很多函數(shù)[4]，同一個家族軟件的函數(shù)調(diào)用圖有相似的結(jié)構(gòu)信息，本文假設(shè)函數(shù)調(diào)用圖的拓撲特征可以進行惡意軟件家族分類，基于此，提出基于圖拓撲特征的惡意軟件同源性分析的方法，并進行分類實驗。

本文首先生成軟件的函數(shù)調(diào)用圖，根據(jù)函數(shù)調(diào)用圖提取出圖的拓撲特征及外部函數(shù)名，最后使用機器學習分類算法根據(jù)函數(shù)調(diào)用圖提取出的相關(guān)特征進行同源性分類，并進行分類評估。惡意軟件同源性分類框架如圖1所示。

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

1. 1 拓撲特征提取及過濾

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

其中，directed項為true表示生成的是有向圖；nodes項中以數(shù)字0～n標記并表示函數(shù)調(diào)用圖中函數(shù)的名稱；links項中每對{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是一個由函數(shù)集合V和函數(shù)間關(guān)系集合E組成的有向圖，如圖2所示。函數(shù)調(diào)用圖的數(shù)學表達式為：G=(V,E)。

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

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

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

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

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

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

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

（1）拓撲特征提取

網(wǎng)絡(luò)分析離不開對網(wǎng)絡(luò)拓撲特征的計算，本文用NetworkX[13]雜網(wǎng)絡(luò)分析工具中已有的算法對每個惡意軟件對應(yīng)的網(wǎng)絡(luò)進行特征提取。在網(wǎng)絡(luò)分析工具中，計算網(wǎng)絡(luò)結(jié)構(gòu)的拓撲特征包括近似性、擬合性、中心性等42大類，每類拓撲特征都有一些子特征用于研究者分析網(wǎng)絡(luò)結(jié)構(gòu)。

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

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

（2）拓撲特征選擇

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

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

本文使用CFS方法對48個特征過濾后，選出了如下所示的8個拓撲特征集合，作為惡意樣本同源性的分類依據(jù)：

（1）傳遞性

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

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

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

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

（3）強連通點

強連通點：為強連通分量中的節(jié)點，該特征屬于組件類，把強連通點的標號作為一個特征。

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

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

（5）平均連通度

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

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

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

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

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

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

（8）密度

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

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

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

2 實驗評估

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

2. 1 實驗樣本

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

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

表2 惡意家族樣本

2. 2 測量指標

通過判斷預測值是否很好地與實際標記值相匹配可以評估分類算法的性能。本文用以下通用標準來度量分類方法的有效性：

精確率（Pr）：被預測為某個家族的惡意樣本中實際為該家族的樣本所占比例，計算公式：

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

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

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

2. 3 實驗結(jié)果與分析

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

表3 實驗結(jié)果

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

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

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

3 結(jié)語

本文在函數(shù)調(diào)用圖基礎(chǔ)上，結(jié)合網(wǎng)絡(luò)理論體系中的網(wǎng)絡(luò)分析方法,提出基于圖拓撲特征的惡意軟件同源性分析技術(shù)。通過實驗，RandomForest分類算法取得了精確率95.6%的分類效果，驗證了本文提出思路的有效性和可行性。本文的貢獻有以下幾點：

（1）提出了一種基于函數(shù)調(diào)用圖拓撲特征和機器學習相結(jié)合的惡意軟件同源性分類方法；

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

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