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

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

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

0 引言

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

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

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

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

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

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

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

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

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

在提取出惡意軟件的函數調用圖后，通過把函數視為節點，函數間的調用關系視為有向邊后，抽象函數調用圖為一個網絡。本文生成的網絡數據文本格式如下所示：

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

1. 2 函數調用圖提取

函數調用圖G是一個由函數集合V和函數間關系集合E組成的有向圖，如圖2所示。函數調用圖的數學表達式為：G=(V,E)。

圖2 函數調用圖

函數調用圖中頂點有兩類函數構成：

（1）本地函數，程序設計者定義的函數；

（2）外部函數，系統函數或庫函數。

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

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

當所有函數被識別出來后，根據提取出來的函數調用關系添加頂點之間的有向邊，生成最終的函數調用圖。

（1）拓撲特征提取

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

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

表1 部分復雜網絡特征

（2）拓撲特征選擇

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

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

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

（1）傳遞性

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

triangles指網絡中三角形的數量，triads指有兩條邊有相同頂點的數量，結果為浮點數。

（2）強連通分量數

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

（3）強連通點

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

（4）吸引分量的數量

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

（5）平均連通度

網絡的平均連通度是反應網絡可靠性的參數之一，是經典連通度的推廣，屬于連通性特征類，計算方式如公式（3）所示。

u,v指的是網絡中的節點。

（6）簡單循環長度

簡單循環是指網絡中一個封閉的路徑，此路徑中節點不會重復出現，把FCG生成的網絡的簡單循環節點的長度作為一個特征，屬于循環類特征。

（7）流層次結構

度量流層次結構是為了理解網絡的結構機制和演化模式出現的，這里為有向網絡中不參與循環的邊的比例，該特征屬于距離相關特征度量類。

（8）密度

網絡密度，該特征用于測量網絡屬性，計算方式如公式（4）所示。

其中n為網絡節點的數量，m為網絡邊的數量。

綜上所述，本文使用CFS特征選擇算法，從初始48個拓撲特征集中選出1個聚類、3個組件類、1個連通性類、1個循環類、1個層結構類和1個網絡屬性類特征作為家族同源性分析的依據。

2 實驗評估

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

2. 1 實驗樣本

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

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

表2 惡意家族樣本

2. 2 測量指標

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

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

其中TP表示正確分類到某個家族的數量，FP表示錯誤分類到這個家族的數量。

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

其中TP表示正確分類到某個家族的數量，FN表示該家族實例被錯誤分配到其他家族的數量。

2. 3 實驗結果與分析

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

表3 實驗結果

通過表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分類算法，構建模型所需的時間為6.96秒；BayesNet構建模型所需的時間為7.05秒；LibSVM構建模型所需的時間為1.71秒。

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

3 結語

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

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

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

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