基于程序雙維度特征的惡意程序相似性分析

任益辰，肖 達

1.北京郵電大學 網絡空間安全學院，北京100876

2.移動互聯網安全技術國家工程實驗室，北京100876

隨著互聯網技術和計算機技術的發展，網絡空間中的軟件數量呈爆炸式增長。據微軟官網報道，2018 年Windows 10擁有超過3 500萬應用程序，超過1.75億個軟件版本[1]。網絡空間中的軟件泛濫給了惡意程序可趁之機，惡意程序將自身隱藏在眾多的軟件應用中，給網絡空間安全帶來了嚴重威脅。據《2019年上半年我國互聯網網絡安全態勢》報告顯示，僅2019 年上半年，國家互聯網應急中心就捕獲了3 200萬個惡意程序樣本[2]；據瑞星發布的《2018 年中國網絡安全報告》顯示，2018 年瑞星“云安全”系統共截獲病毒樣本總量7 786萬個[3]，可見惡意軟件相關態勢依然十分嚴峻。惡意軟件檢測始終是網絡空間安全中的關鍵課題之一。

目前，互聯網上各種代碼資源越來越多，軟件復用技術也日益成熟，開發人員能夠快速地在原有軟件基礎上開發出新的軟件，從而大大縮短軟件開發周期，大幅降低軟件開發成本，也大大降低了軟件開發門檻[4-5]。尤其是在惡意軟件開發領域，在已有代碼基礎上進行二次開發或對已有代碼進行集成已變得十分普遍，惡意軟件開發者往往使用復用的手段完成惡意代碼的快速更新和開發。因此，可以通過比較未知軟件與已知惡意軟件的相似性來對惡意軟件進行檢測，同時也可以通過相似性檢測對軟件進行溯源和家族分類[6]。惡意軟件開發者為了躲避安全軟件檢測、對抗殺軟，往往通過混淆、加殼、自壓縮等操作改變惡意軟件特征。因此，僅通過特征碼、散列值、軟件指紋等信息難以識別變形后的惡意軟件與原有惡意軟件的相似性，需要綜合考慮惡意軟件的的各種特征來進行相似性[7]。

本文針對Windows平臺的惡意軟件，在匯編層面提取軟件動態指令流信息，并基于離線基本塊序列構造軟件控制流圖，從軟件代碼語義特征和結構特征兩個維度對軟件進行相似性分析。動態提取軟件特征能夠有效避免加殼、混淆等軟件變形技術的影響，提取匯編層面的信息使檢測不受軟件開發語言的限制，從兩個維度進行檢測，既考慮到軟件的語義特征又考慮到軟件的結構特征，能夠對軟件進行較為全面的分析。

1 相關工作

隨著軟件技術的發展，軟件復用技術給軟件開發帶來極大便利，同時也帶來了盜版軟件泛濫，惡意軟件開發門檻降低，惡意軟件泛濫的問題。

最初，軟件相似性或同源性的檢測分析技術主要用于軟件版權保護，解決軟件版權糾紛問題，后來應用范圍逐步擴展到惡意軟件同源性分析、漏洞挖掘等安全領域[8-19]。

軟件相似指的是定義為軟件實質相似，即軟件思想在表達形式上的相似。軟件的表達形式指的是軟件思想在技術上的實現，最初包括模塊結構、模塊組織、編碼等，后來研究中又加入了數據結構、控制流圖等[20-21]。

根據分析手段的不同，可以將分析方法劃分為靜態分析和動態分析兩種[21]。靜態分析方法通過直接分析二進制文件數據提取軟件靜態信息來對軟件相似性進行檢測。在研究的早期階段多使用軟件的一些功能特征、外部特征來研究，例如軟件大小、軟件工作流程等[22]。在之后的研究中，研究人員還使用了靜態指令頻率、字符串集合、控制流等特征[9]。靜態分析不需要執行軟件，僅通過讀取二進制文件就可以進行分析，具有較高的分析速度和安全性，但靜態分析方法無法分析經過混淆、加殼等變形技術處理過的軟件，需要與軟件反混淆、脫殼等技術相配合。

基于靜態分析方法的局限性和虛擬技術的發展，目前大多使用動態分析方法或動靜結合的分析方法。動態分析方法通過在沙箱、虛擬機等環境中運行軟件，通過動態插樁、污點跟蹤等技術獲取軟件運行過程中的信息來對軟件相似性進行檢測[22]。按照獲取信息的內容可以將其劃分為軟件產生的數據和軟件執行的代碼兩種，其中數據包括堆棧數據、函數參數、變量數據等，代碼包括API 調用、系統函數調用等，按照信息組合形式可以分為集合型、序列型、樹或圖型。動態分析方法基于軟件運行的實際數據對軟件相似性進行分析，能夠有效地對抗代碼混淆、軟件加殼等軟件變形技術。由于動態分析方法需要執行二進制程序，而執行程序尤其是惡意程序會存在一定的風險，因此需要在安全環境下進行分析。

2 特征提取與分析

本文使用控制流圖來描述程序的結構特征，用基本塊集合描述程序的語義特征，基于這兩種特征的綜合相似度對惡意程序進行相似性分析。首先提取程序動態指令流信息，構建程序動態執行的基本塊集合和控制流圖，分別計算基本塊集合相似度和控制流圖相似度，從程序代碼和程序結構兩個角度對程序相似性進行衡量。

2.1 基于沙箱的動態指令流提取

為規避運行未知軟件對分析系統造成不利影響的風險，本文使用PinFWSand Box[23]無感知沙箱提取軟件動態信息。PinFWSand Box 無感知沙箱通過動態插樁技術對軟件系統調用、模塊加載及指令流進行監控，并且能夠回滾惡意行為，有效地保護分析主機的安全性。

PinFWSand Box 是基于Pin 平臺的Pintools 工具開發的一款沙箱。Pin[24]是Intel公司開發的一個二進制程序動態分析平臺，支持IA-32、x86-64 和MIC 指令集架構，支持Linux、Windows 和MacOS 系統。Pin 相當于一個即時（Just in Time，JIT）編譯器，能夠在二進制程序的任意位置插入代碼并執行，能夠替換原有程序代碼，能夠記錄系統調用、程序線程活動等情況，能夠檢測進程樹，模擬API（Application Programming Interface）調用[25]，具有指令級、基本塊級、函數級三種插樁粒度。Pintools工具是動態插樁平臺Pin的擴展工具。Pin平臺為用戶提供了豐富的API接口，允許用戶開發動態鏈接庫（Dynamic Link Library）形式的插件，從而使用戶可以自定義插入代碼的內容和位置，進而提取出自己感興趣的信息。這些插件被稱為Pintools。

軟件動態指令流數據量十分龐大，一個1 KB 的程序就可能要執行幾十萬調指令，直接對每條指令進行插樁會大大影響程序運行速度，大大降低分析效率，并且難以存儲。因此，本文對PinFWSand Box 中的Pintools工具進行了調整，以基本塊為單位提取軟件動態指令流，并且采用基本塊索引庫的方式對基本塊執行序列進行存儲。

程序順序執行的一段匯編語句序列，該序列是單入口單出口的，程序執行過程中僅從入口進入這段序列，僅從出口退出這段序列，則這段序列就稱為基本塊。程序執行一旦進入某個基本塊，就一定會執行該基本塊中所有指令直到退出該基本塊。如果直接記錄基本塊執行序列，仍然需要較大的存儲空間，因此采用基本塊索引庫的方式進行存儲，將基本塊與執行序列分別存儲。在存儲基本塊時相同的基本塊僅記錄一次，為每個基本塊分配唯一的編號，基本塊執行序列中使用編號來代替基本塊，從而大大降低存儲空間?；緣K粒度的軟件動態指令流數據獲取算法步驟如下：

步驟1 程序準備執行一個基本塊，觸發基本塊插樁函數；

步驟2 在基本塊索引庫中查詢該基本塊對應編號，如果已經記錄過該基本塊，則轉到步驟5；

步驟3 為該基本塊分配執行編號；

步驟4 記錄基本塊相關信息并添加到索引庫；

步驟5 將基本塊的執行編號添加到基本塊執行序列；

步驟6 程序執行基本塊；

步驟7 判斷程序是否執行完成，否則轉到步驟1，是則退出。

2.2 基本塊集合的處理與相似度分析

2.2.1 基本塊集合預處理

直接提取得到的基本塊集合存在功能無關指令噪聲、可重排指令噪聲、指令多樣化等問題，會嚴重影響相似度計算結果，因此需要對基本塊集合進行預處理。

（1）常用指令篩選

在預處理的過程中需要對指令格式進行統一處理。目前缺少能夠統一匯編語言格式的中間語言，如果針對每個匯編指令一一進行格式規定，工作量過大，而且這些指令不都是經常使用的指令，沒有全部處理的必要，只需要對常用的指令格式進行格式統一。因此需要篩選出常用指令。

本文從樣本網站獲取1 500 個二進制樣本，提取了這些樣本的動態指令流，并對其中屬于x86指令集的指令進行統計。統計的內容包括指令符號、指令在樣本集中出現的次數、指令在樣本集中出現的頻率、包含指令的樣本占比，最后篩選出最常用的100個匯編指令。

（2）指令多樣性去除

在匯編語言中有一些語句有相同的功能，例如xor eax，eax 和mov eax，0 都是將eax 寄存器清零本質上沒有區別。為避免這種同義語句給基本塊相似度計算帶來干擾，需要將這些語句進行統一。

（3）指令格式標準化

x86 匯編指令格式多樣，對參數的操作也不盡相同，給相似度計算帶來麻煩，因此需要對指令格式進行標準化。

將指令語句標準化為三部分：一個指令碼、一個返回值、三個參數。指令碼即原來的指令碼，結果存儲變量為用于存儲指令執行結果的變量，參數即原來的參數，個數不夠的用null代替。

除指令格式外，指令參數也要進行標準化。匯編指令可以使用寄存器、棧地址、內存地址作為參數，這些參數的本質都是變量，因此將這些參數進行統一命名，并進行編號。

（4）基本塊簡化

進行上述處理后，能夠得到格式統一的基本塊集合，然后基于DAG 圖（Directed Acyclic Graph，有向無環圖）對基本塊進行簡化，包括刪除無用賦值語句、合并串聯賦值語句等局部優化處理，從而使基本塊語句更加精簡，進一步縮小基本塊集合的規模。

以返回值和參數為頂點，將BBL（Basic Block，基本塊）轉化為DAG圖。頂點劃分為三種：返回值所在頂點為def頂點，初次使用的變量所在頂點為zero頂點，其他頂點為use頂點。

通過判斷頂點的父節點和子節點的個數來判斷該語句是否需要優化，并且通過頂點的合并、刪除來完成優化。如果某個定義頂點無父節點，則說明該頂點定義后未被使用，可以被刪除；如果定義頂點只有一個子節點，則說明該頂點對應的參數或返回值的值與子節點相同，可以將該頂點與子頂點合并。最后，將優化后的DAG圖恢復成BBL的格式。

2.2.2 相似度計算

本文基于指令間的參數依賴提取基本塊的def-use鏈，并基于基本塊的def-use 鏈來計算基本塊間的相似度，從而避免指令可重排問題給相似度計算帶來的干擾。之后，根據基本塊間的相似度構造集合的相似度矩陣來計算集合間的相似度。

（1）基本塊相似度

def-use 鏈是編譯原理中用來描述變量依賴關系的鏈表，在變量作用域內，以變量定義語句為起點，依次綴連變量的使用語句直到變量再次被定義或作用域結束?；緣K的def-use鏈則以一個基本塊作為變量的作用域，以變量定義語句或變量初次出現語句為起點，依次綴連變量使用語句，直到基本塊結束或變量被重定義。

定義1（基本塊常量集合）將基本塊中匯編指令操作數中的立即數稱為基本塊常量，符號記為con，將常量con的個數記為connum，將基本塊中常量集合符號記為con_set，則：

定義2（基本塊變量集合）將基本塊中除常量外的其余操作數稱為變量，符號記為var，將變量var的個數記為varnum，將基本塊中變量集合記為var_set，則：

定義3（def-use 鏈集合）將基本塊中的def-use鏈記為chain，個數記為chanum，def-chain鏈集合記為cha_set，則

定義4（相似度）集合或數值之間相似的程度，數值范圍在0～1，符號記為sim?；緣K之間相似度記為simbbl，變量相似度記為simvar，常量相似度記為simcon，常量集合相似度記為simcon_set，def-chain鏈集合相似度記為simcha_set。

將基本塊語義內容轉化為基本塊變量個數、常量個數、def-use鏈集合、常量集合四部分，并通過這四部分相似度的結合計算出基本塊相似度。

對于基本塊A，將其相關信息轉化為{varnuma,connuma,cha_setchanuma,con_setconnuma}，其中基本塊A的def-use鏈集合可以表示為：

同樣，對于基本塊B，將其轉化為{varnumb,connumb,cha_setchanumb,con_setconnumb}。

基本塊A與基本塊B相似度計算公式如下：

其中simvar用varnum之間的距離來計算，simcon用connum之間的距離來計算，公式如下：

simcha_set用兩個BBL的cha_set的Jaccard系數來計算，simcon_set用兩個BBL 的con_set的Jaccard 系數來計算。其中，Jaccard系數定義為兩個集合交集大小與并集大小的比值。對于集合S1和S2，其Jaccard系數計算公式如下：

比對A和B的cha_set，相同chain的個數記為Nsamechain，不同chain的個數記為Ndiffchain，則：

比對A和B的con_set，相同con的個數記為Nsamecon，不同con的個數記為Ndiffcon，則：

（2）基本塊集合相似度

定義5（基本塊集合）將基本塊記為BBL，將基本塊個數記為BBLnum，將基本塊集合記為BBLSet，則對于程序P，其基本塊集合表示為：

定義6（基本塊集合相似度矩陣）計算兩個基本塊結合中任意兩個基本塊之間的相似度，并按照基本塊順序進行排列，構成相似度矩陣，記為SimMatrix。

將程序P和Q任意兩個BBL之間的相似度簡記為sij=simBBL(BBLi,BBLj)，其中i∈NBBLnumP,j∈NBBLnumQ。則P 和Q 的基本塊集合相似度矩陣表示為：

使用KM 算法計算出s11,…,sBBLnumPBBLnumQ中最大的相似度匹配值。KM 算法是求最大權匹配的經典算法，能夠獲得結果最大化的情況下兩組集合最優匹配順序。則兩個BBL集合的相似度公式為：

2.3 控制流圖的生成與相似度計算

控制流圖（Control Flow Graph，CFG）是Frances E Allen 于1970 年提出的一種抽象數據結構[18]，是對程序控制流圖的簡化，用于描述程序代碼結構。圖1所示是程序中最基本的三種結構：順序結構、分支結構、循環結構。

圖1 程序基本結構

基本塊集合僅包含了程序動態指令流的組成，未包含程序的代碼結構信息，因此引入控制流圖相似度，從而使程序相似性的衡量更為全面和準確。

本文基于NetworkX模塊來實現控制流圖的生成和相似度計算。

2.3.1 控制流圖的生成

本文基于基本塊執行序列來生成基本塊級別的控制流圖，在使用PinFWSand沙箱提取程序動態指令流的同時記錄基本塊執行序列。在記錄基本塊時采用了基本塊索引庫的方式，為每一個基本塊設置一個唯一的編號，在執行序列中使用編號表示基本塊?；緣K內容記錄在基本塊索引庫中，基本塊執行序列記錄在基本塊執行序列文件中。

如圖2 所示，這是某個基本塊索引庫的一部分，包含5個基本塊，編號分別為1、2、3、4、5，這5個基本塊在執行序列文件中對應的執行序列為123435。

圖2 基本塊集合與執行序列示例

根據基本塊執行序列文件中的編號序列來生成控制流圖。將所有的編號作為圖的節點，將編號的相鄰關系作為邊，邊的方向由先出現的編號指向它后面的編號，以邊重復出現的次數作為邊的權重。用符號G表示生成的控制流圖，G(V,E)表示包含節點集合V和有向帶權邊集合E的控制流圖。

例如，基本塊執行的編號序列為123435，則將1、2、3、4、5 作為控制流圖的頂點，將執行序列中的5 種相鄰關系作為連接頂點的有向邊，分別為（1，2）（2，3）（3，4）（4，3）（3，5），每條邊均只出現一次，因此邊的權重均為1。由此，生成了帶有循環結構控制流圖，如圖3所示。

圖3 基本塊序列轉控制流圖示例

2.3.2 相似度計算

圖的相似度計算是一個非常復雜的問題，在實際應用過程中常常根據實際情況對圖進行專門的處理，從而降低復雜度，提高計算效率。對于程序的動態控制流圖來說，最關鍵的部分是其中的分支結構、循環結構，這兩種結構包含了程序運行中的控制轉移信息。而順序結構對于控制流圖來說是不重要的，而且在控制流圖中大量存在，因此對控制流圖中順序結構的部分進行合并能夠有效縮小圖的規模，且不影響圖的相似度計算。

通過檢查頂點及其相鄰頂點的出度和入度來識別垂直結構。如果一個頂點的入度大于1 或出度大于1，則該頂點在一個分支結構上，需要保留，例如圖3 中的頂點3。由這種頂點指向的的頂點也需要保留，例如圖3中的頂點4和頂點5，其余頂點可以合并。

例如，對于圖3 中的示例，頂點123 之間是垂直結構，頂點345 之間是循環結構，則由123435 序列可以簡化為3435。簡化示意圖如圖4所示。

圖4 控制流圖簡化示例

控制流圖順序結構合并算法偽代碼如下所示：

input：控制流圖節點集合V

控制流圖邊集合E

output：控制流圖節點集合V′

控制流圖節點集合E′

for v in V ：

get edge set e of v in E

if v out-degree＜2 and v in-degree＜2：

get (v′,v) in e

if v′ out-degree＞=2：

continue

get (v,v′)

add edge (v′,v′′) to E

del (v′,v) in E

del (v,v′) in E

del v in V

根據實驗結果，經順序結構合并處理，V和E的規模都下降到了原來的20%以內。

將兩個控制流圖的相似度定義為兩個控制流圖公共子圖規模與原圖規模的比值?；赩F2 算法[26]來獲取G1與G2的公共子圖，偽代碼如下所示：

input：控制流圖G1

控制流圖G2

output：公共子圖集合commonGraphSet

while G1not empty and G2not empty:

generate subgraph subG1of G1

while subG1subgraph isomorphism to G2：

while not used node n in G1：

if n not in subG1and connected to subG1and in G1：

add n to subG1

break

else:

add subG1to common Graph Set

goto next

get next node n

next：

del subG1in G1

del subG1in G2

根據以上步驟可以獲得G1與G2的公共子圖集合，該集合能夠最大范圍的覆蓋G1和G2的公共部分，記為common Graph(G1,G2)。

將圖的相似度記為simGraph，則simGraph(G1,G2)表示G1與G2的的相似度。

定義7（圖的規模）將圖G的規模定義為圖中節點與邊的總數，記為Scale(G)。

則G1與G2的相似度計算公式為：

例如，對于圖5中的兩個控制流圖A和B，A中頂點3、4、5組成的圖與B中頂點1、2、3組成的子圖同構，則A與B的公共子圖規模為6。圖A的規模為6，圖B的規模為10，則兩個圖的相似度為0.75。

圖5 控制流圖相似度計算示例

2.4 基于二維特征整合的相似度計算

基本塊集合可以表征程序語義特征，控制流圖可以表征程序結構特征，將這兩種特征結合，從語義和結構兩種維度來計算程序之間的相似度，能夠使相似度計算結果更為準確、更可信。

定義8（程序相似度）將兩個程序之間的相似度定義為兩個程序動態基本塊集合相似度與動態控制流圖相似度的線性組合，記為simPro。

對于程序P和Q，其相似度記為simPro(P,Q)，則相似度計算公式為：

其中α為線性系數，值為0.5。若0.8 ≤simPro(P,Q)≤1.0，則判定程序P和Q相似；如果0.0 ≤simPro(P,Q)≤0.4，則判定程序P和Q不相似；否則無法判定程序P和Q是否相似。

3 實驗評估

本文對提出的方法進行了可行性實驗和可靠性實驗，從可行性、可靠性兩方面對實驗結果進行評估。

實驗在搭載有VM虛擬機的服務器上進行，實驗環境包括Win7操作系統、pin工具和python環境。詳細實驗環境如表1所示。

表1 實驗環境

3.1 可行性實驗

可行性實驗用于測試本方法能否正確識別程序的相似性。本文從惡意程序分析網站獲取了7 組惡意程序，共120 個樣本進行可行性測試實驗，同組程序都是相同惡意程序的變種，程序組別與樣本個數如表2所示。

表2 實驗樣本列表

計算每個程序與自身的相似度，均為1.0。

對同組程序兩兩之間進行相似度檢測，實驗結果統計如圖6所示。

同組程序之間的相似度計算結果中約有99%大于0.8，說明本方法能夠有效識別相似的惡意程序。

對不同組程序兩兩之間進行相似度檢測，每組程序之間的平均相似度統計結果如表3所示。

表3 不同組程序間相似度平均值

圖6 同組程序相似度取值范圍分布圖

不同組程序之間的相似度平均值在0.4 以內，說明本方法能夠區分相似性較小的惡意程序。

由實驗結果得知，本文方法既能識別相似性較大的程序又能區分相似性較小的程序，說明本方法在惡意程序的相似性分析上是可行的。

多次重復上述實驗，得到相同的實驗結果。由此可見，本文方法是穩定可行的。

3.2 可靠性實驗

對120個樣本程序進行加殼處理，分別計算其與原程序的相似度，加殼方法選擇了常見的upx、ASPack、PECompact、ASProtect、EXECryptor 這5 種。相似度計算結果如表4所示。

表4 加殼后程序與原程序相似度部分數據

對相似度取值范圍進行統計，結果如圖7、8所示。

圖7 加殼后程序與原程序相似度取值范圍分布柱狀圖

圖8 加殼后程序與原程序相似度取值范圍百分比

從圖7 和圖8 的實驗結果中可以看出，加殼變形后的程序中有大約83%與原程序的相似度達到0.9 以上，約94%達到0.8 以上，說明本文方法能夠有效地對抗程序加殼變形手段，是可靠的。

4 結語

本文提出一種基于控制流圖和指令基本塊的惡意軟件相似度分析方法，首先使用PinFWSand 沙箱建立程序指令流快照，并使用索引庫的方式進行存儲，然后對獲取的指令流信息進行預處理，去除基本塊集合和控制流圖的干擾噪聲，最后綜合程序基本塊集合和控制流圖的相似度得出程序間的相似度。本文方法從程序結構和代碼語義兩個方面綜合考慮程序的相似度，對程序相似度的衡量更全面更準確，能夠有效的識別同源的惡意軟件，并且能夠對加殼等軟件變形手段有較好的抗干擾效果。本文未對這兩種相似度進行加權計算，在下一步的工作中需要對兩者在軟件相似中的權重進行研究。