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

任益辰，肖 達(dá)

1.北京郵電大學(xué) 網(wǎng)絡(luò)空間安全學(xué)院，北京100876

2.移動(dòng)互聯(lián)網(wǎng)安全技術(shù)國(guó)家工程實(shí)驗(yàn)室，北京100876

隨著互聯(lián)網(wǎng)技術(shù)和計(jì)算機(jī)技術(shù)的發(fā)展，網(wǎng)絡(luò)空間中的軟件數(shù)量呈爆炸式增長(zhǎng)。據(jù)微軟官網(wǎng)報(bào)道，2018 年Windows 10擁有超過(guò)3 500萬(wàn)應(yīng)用程序，超過(guò)1.75億個(gè)軟件版本[1]。網(wǎng)絡(luò)空間中的軟件泛濫給了惡意程序可趁之機(jī)，惡意程序?qū)⒆陨黼[藏在眾多的軟件應(yīng)用中，給網(wǎng)絡(luò)空間安全帶來(lái)了嚴(yán)重威脅。據(jù)《2019年上半年我國(guó)互聯(lián)網(wǎng)網(wǎng)絡(luò)安全態(tài)勢(shì)》報(bào)告顯示，僅2019 年上半年，國(guó)家互聯(lián)網(wǎng)應(yīng)急中心就捕獲了3 200萬(wàn)個(gè)惡意程序樣本[2]；據(jù)瑞星發(fā)布的《2018 年中國(guó)網(wǎng)絡(luò)安全報(bào)告》顯示，2018 年瑞星“云安全”系統(tǒng)共截獲病毒樣本總量7 786萬(wàn)個(gè)[3]，可見惡意軟件相關(guān)態(tài)勢(shì)依然十分嚴(yán)峻。惡意軟件檢測(cè)始終是網(wǎng)絡(luò)空間安全中的關(guān)鍵課題之一。

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

本文針對(duì)Windows平臺(tái)的惡意軟件，在匯編層面提取軟件動(dòng)態(tài)指令流信息，并基于離線基本塊序列構(gòu)造軟件控制流圖，從軟件代碼語(yǔ)義特征和結(jié)構(gòu)特征兩個(gè)維度對(duì)軟件進(jìn)行相似性分析。動(dòng)態(tài)提取軟件特征能夠有效避免加殼、混淆等軟件變形技術(shù)的影響，提取匯編層面的信息使檢測(cè)不受軟件開發(fā)語(yǔ)言的限制，從兩個(gè)維度進(jìn)行檢測(cè)，既考慮到軟件的語(yǔ)義特征又考慮到軟件的結(jié)構(gòu)特征，能夠?qū)浖M(jìn)行較為全面的分析。

1 相關(guān)工作

隨著軟件技術(shù)的發(fā)展，軟件復(fù)用技術(shù)給軟件開發(fā)帶來(lái)極大便利，同時(shí)也帶來(lái)了盜版軟件泛濫，惡意軟件開發(fā)門檻降低，惡意軟件泛濫的問(wèn)題。

最初，軟件相似性或同源性的檢測(cè)分析技術(shù)主要用于軟件版權(quán)保護(hù)，解決軟件版權(quán)糾紛問(wèn)題，后來(lái)應(yīng)用范圍逐步擴(kuò)展到惡意軟件同源性分析、漏洞挖掘等安全領(lǐng)域[8-19]。

軟件相似指的是定義為軟件實(shí)質(zhì)相似，即軟件思想在表達(dá)形式上的相似。軟件的表達(dá)形式指的是軟件思想在技術(shù)上的實(shí)現(xiàn)，最初包括模塊結(jié)構(gòu)、模塊組織、編碼等，后來(lái)研究中又加入了數(shù)據(jù)結(jié)構(gòu)、控制流圖等[20-21]。

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

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

2 特征提取與分析

本文使用控制流圖來(lái)描述程序的結(jié)構(gòu)特征，用基本塊集合描述程序的語(yǔ)義特征，基于這兩種特征的綜合相似度對(duì)惡意程序進(jìn)行相似性分析。首先提取程序動(dòng)態(tài)指令流信息，構(gòu)建程序動(dòng)態(tài)執(zhí)行的基本塊集合和控制流圖，分別計(jì)算基本塊集合相似度和控制流圖相似度，從程序代碼和程序結(jié)構(gòu)兩個(gè)角度對(duì)程序相似性進(jìn)行衡量。

2.1 基于沙箱的動(dòng)態(tài)指令流提取

為規(guī)避運(yùn)行未知軟件對(duì)分析系統(tǒng)造成不利影響的風(fēng)險(xiǎn)，本文使用PinFWSand Box[23]無(wú)感知沙箱提取軟件動(dòng)態(tài)信息。PinFWSand Box 無(wú)感知沙箱通過(guò)動(dòng)態(tài)插樁技術(shù)對(duì)軟件系統(tǒng)調(diào)用、模塊加載及指令流進(jìn)行監(jiān)控，并且能夠回滾惡意行為，有效地保護(hù)分析主機(jī)的安全性。

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

軟件動(dòng)態(tài)指令流數(shù)據(jù)量十分龐大，一個(gè)1 KB 的程序就可能要執(zhí)行幾十萬(wàn)調(diào)指令，直接對(duì)每條指令進(jìn)行插樁會(huì)大大影響程序運(yùn)行速度，大大降低分析效率，并且難以存儲(chǔ)。因此，本文對(duì)PinFWSand Box 中的Pintools工具進(jìn)行了調(diào)整，以基本塊為單位提取軟件動(dòng)態(tài)指令流，并且采用基本塊索引庫(kù)的方式對(duì)基本塊執(zhí)行序列進(jìn)行存儲(chǔ)。

程序順序執(zhí)行的一段匯編語(yǔ)句序列，該序列是單入口單出口的，程序執(zhí)行過(guò)程中僅從入口進(jìn)入這段序列，僅從出口退出這段序列，則這段序列就稱為基本塊。程序執(zhí)行一旦進(jìn)入某個(gè)基本塊，就一定會(huì)執(zhí)行該基本塊中所有指令直到退出該基本塊。如果直接記錄基本塊執(zhí)行序列，仍然需要較大的存儲(chǔ)空間，因此采用基本塊索引庫(kù)的方式進(jìn)行存儲(chǔ)，將基本塊與執(zhí)行序列分別存儲(chǔ)。在存儲(chǔ)基本塊時(shí)相同的基本塊僅記錄一次，為每個(gè)基本塊分配唯一的編號(hào)，基本塊執(zhí)行序列中使用編號(hào)來(lái)代替基本塊，從而大大降低存儲(chǔ)空間。基本塊粒度的軟件動(dòng)態(tài)指令流數(shù)據(jù)獲取算法步驟如下：

步驟1 程序準(zhǔn)備執(zhí)行一個(gè)基本塊，觸發(fā)基本塊插樁函數(shù)；

步驟2 在基本塊索引庫(kù)中查詢?cè)摶緣K對(duì)應(yīng)編號(hào)，如果已經(jīng)記錄過(guò)該基本塊，則轉(zhuǎn)到步驟5；

步驟3 為該基本塊分配執(zhí)行編號(hào)；

步驟4 記錄基本塊相關(guān)信息并添加到索引庫(kù)；

步驟5 將基本塊的執(zhí)行編號(hào)添加到基本塊執(zhí)行序列；

步驟6 程序執(zhí)行基本塊；

步驟7 判斷程序是否執(zhí)行完成，否則轉(zhuǎn)到步驟1，是則退出。

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

2.2.1 基本塊集合預(yù)處理

直接提取得到的基本塊集合存在功能無(wú)關(guān)指令噪聲、可重排指令噪聲、指令多樣化等問(wèn)題，會(huì)嚴(yán)重影響相似度計(jì)算結(jié)果，因此需要對(duì)基本塊集合進(jìn)行預(yù)處理。

（1）常用指令篩選

在預(yù)處理的過(guò)程中需要對(duì)指令格式進(jìn)行統(tǒng)一處理。目前缺少能夠統(tǒng)一匯編語(yǔ)言格式的中間語(yǔ)言，如果針對(duì)每個(gè)匯編指令一一進(jìn)行格式規(guī)定，工作量過(guò)大，而且這些指令不都是經(jīng)常使用的指令，沒有全部處理的必要，只需要對(duì)常用的指令格式進(jìn)行格式統(tǒng)一。因此需要篩選出常用指令。

本文從樣本網(wǎng)站獲取1 500 個(gè)二進(jìn)制樣本，提取了這些樣本的動(dòng)態(tài)指令流，并對(duì)其中屬于x86指令集的指令進(jìn)行統(tǒng)計(jì)。統(tǒng)計(jì)的內(nèi)容包括指令符號(hào)、指令在樣本集中出現(xiàn)的次數(shù)、指令在樣本集中出現(xiàn)的頻率、包含指令的樣本占比，最后篩選出最常用的100個(gè)匯編指令。

（2）指令多樣性去除

在匯編語(yǔ)言中有一些語(yǔ)句有相同的功能，例如xor eax，eax 和mov eax，0 都是將eax 寄存器清零本質(zhì)上沒有區(qū)別。為避免這種同義語(yǔ)句給基本塊相似度計(jì)算帶來(lái)干擾，需要將這些語(yǔ)句進(jìn)行統(tǒng)一。

（3）指令格式標(biāo)準(zhǔn)化

x86 匯編指令格式多樣，對(duì)參數(shù)的操作也不盡相同，給相似度計(jì)算帶來(lái)麻煩，因此需要對(duì)指令格式進(jìn)行標(biāo)準(zhǔn)化。

將指令語(yǔ)句標(biāo)準(zhǔn)化為三部分：一個(gè)指令碼、一個(gè)返回值、三個(gè)參數(shù)。指令碼即原來(lái)的指令碼，結(jié)果存儲(chǔ)變量為用于存儲(chǔ)指令執(zhí)行結(jié)果的變量，參數(shù)即原來(lái)的參數(shù)，個(gè)數(shù)不夠的用null代替。

除指令格式外，指令參數(shù)也要進(jìn)行標(biāo)準(zhǔn)化。匯編指令可以使用寄存器、棧地址、內(nèi)存地址作為參數(shù)，這些參數(shù)的本質(zhì)都是變量，因此將這些參數(shù)進(jìn)行統(tǒng)一命名，并進(jìn)行編號(hào)。

（4）基本塊簡(jiǎn)化

進(jìn)行上述處理后，能夠得到格式統(tǒng)一的基本塊集合，然后基于DAG 圖（Directed Acyclic Graph，有向無(wú)環(huán)圖）對(duì)基本塊進(jìn)行簡(jiǎn)化，包括刪除無(wú)用賦值語(yǔ)句、合并串聯(lián)賦值語(yǔ)句等局部?jī)?yōu)化處理，從而使基本塊語(yǔ)句更加精簡(jiǎn)，進(jìn)一步縮小基本塊集合的規(guī)模。

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

通過(guò)判斷頂點(diǎn)的父節(jié)點(diǎn)和子節(jié)點(diǎn)的個(gè)數(shù)來(lái)判斷該語(yǔ)句是否需要優(yōu)化，并且通過(guò)頂點(diǎn)的合并、刪除來(lái)完成優(yōu)化。如果某個(gè)定義頂點(diǎn)無(wú)父節(jié)點(diǎn)，則說(shuō)明該頂點(diǎn)定義后未被使用，可以被刪除；如果定義頂點(diǎn)只有一個(gè)子節(jié)點(diǎn)，則說(shuō)明該頂點(diǎn)對(duì)應(yīng)的參數(shù)或返回值的值與子節(jié)點(diǎn)相同，可以將該頂點(diǎn)與子頂點(diǎn)合并。最后，將優(yōu)化后的DAG圖恢復(fù)成BBL的格式。

2.2.2 相似度計(jì)算

本文基于指令間的參數(shù)依賴提取基本塊的def-use鏈，并基于基本塊的def-use 鏈來(lái)計(jì)算基本塊間的相似度，從而避免指令可重排問(wèn)題給相似度計(jì)算帶來(lái)的干擾。之后，根據(jù)基本塊間的相似度構(gòu)造集合的相似度矩陣來(lái)計(jì)算集合間的相似度。

（1）基本塊相似度

def-use 鏈?zhǔn)蔷幾g原理中用來(lái)描述變量依賴關(guān)系的鏈表，在變量作用域內(nèi)，以變量定義語(yǔ)句為起點(diǎn)，依次綴連變量的使用語(yǔ)句直到變量再次被定義或作用域結(jié)束?；緣K的def-use鏈則以一個(gè)基本塊作為變量的作用域，以變量定義語(yǔ)句或變量初次出現(xiàn)語(yǔ)句為起點(diǎn)，依次綴連變量使用語(yǔ)句，直到基本塊結(jié)束或變量被重定義。

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

定義2（基本塊變量集合）將基本塊中除常量外的其余操作數(shù)稱為變量，符號(hào)記為var，將變量var的個(gè)數(shù)記為varnum，將基本塊中變量集合記為var_set，則：

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

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

將基本塊語(yǔ)義內(nèi)容轉(zhuǎn)化為基本塊變量個(gè)數(shù)、常量個(gè)數(shù)、def-use鏈集合、常量集合四部分，并通過(guò)這四部分相似度的結(jié)合計(jì)算出基本塊相似度。

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

同樣，對(duì)于基本塊B，將其轉(zhuǎn)化為{varnumb,connumb,cha_setchanumb,con_setconnumb}。

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

其中simvar用varnum之間的距離來(lái)計(jì)算，simcon用connum之間的距離來(lái)計(jì)算，公式如下：

simcha_set用兩個(gè)BBL的cha_set的Jaccard系數(shù)來(lái)計(jì)算，simcon_set用兩個(gè)BBL 的con_set的Jaccard 系數(shù)來(lái)計(jì)算。其中，Jaccard系數(shù)定義為兩個(gè)集合交集大小與并集大小的比值。對(duì)于集合S1和S2，其Jaccard系數(shù)計(jì)算公式如下：

比對(duì)A和B的cha_set，相同chain的個(gè)數(shù)記為Nsamechain，不同chain的個(gè)數(shù)記為Ndiffchain，則：

比對(duì)A和B的con_set，相同con的個(gè)數(shù)記為Nsamecon，不同con的個(gè)數(shù)記為Ndiffcon，則：

（2）基本塊集合相似度

定義5（基本塊集合）將基本塊記為BBL，將基本塊個(gè)數(shù)記為BBLnum，將基本塊集合記為BBLSet，則對(duì)于程序P，其基本塊集合表示為：

定義6（基本塊集合相似度矩陣）計(jì)算兩個(gè)基本塊結(jié)合中任意兩個(gè)基本塊之間的相似度，并按照基本塊順序進(jìn)行排列，構(gòu)成相似度矩陣，記為SimMatrix。

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

使用KM 算法計(jì)算出s11,…,sBBLnumPBBLnumQ中最大的相似度匹配值。KM 算法是求最大權(quán)匹配的經(jīng)典算法，能夠獲得結(jié)果最大化的情況下兩組集合最優(yōu)匹配順序。則兩個(gè)BBL集合的相似度公式為：

2.3 控制流圖的生成與相似度計(jì)算

控制流圖（Control Flow Graph，CFG）是Frances E Allen 于1970 年提出的一種抽象數(shù)據(jù)結(jié)構(gòu)[18]，是對(duì)程序控制流圖的簡(jiǎn)化，用于描述程序代碼結(jié)構(gòu)。圖1所示是程序中最基本的三種結(jié)構(gòu)：順序結(jié)構(gòu)、分支結(jié)構(gòu)、循環(huán)結(jié)構(gòu)。

圖1 程序基本結(jié)構(gòu)

基本塊集合僅包含了程序動(dòng)態(tài)指令流的組成，未包含程序的代碼結(jié)構(gòu)信息，因此引入控制流圖相似度，從而使程序相似性的衡量更為全面和準(zhǔn)確。

本文基于NetworkX模塊來(lái)實(shí)現(xiàn)控制流圖的生成和相似度計(jì)算。

2.3.1 控制流圖的生成

本文基于基本塊執(zhí)行序列來(lái)生成基本塊級(jí)別的控制流圖，在使用PinFWSand沙箱提取程序動(dòng)態(tài)指令流的同時(shí)記錄基本塊執(zhí)行序列。在記錄基本塊時(shí)采用了基本塊索引庫(kù)的方式，為每一個(gè)基本塊設(shè)置一個(gè)唯一的編號(hào)，在執(zhí)行序列中使用編號(hào)表示基本塊?；緣K內(nèi)容記錄在基本塊索引庫(kù)中，基本塊執(zhí)行序列記錄在基本塊執(zhí)行序列文件中。

如圖2 所示，這是某個(gè)基本塊索引庫(kù)的一部分，包含5個(gè)基本塊，編號(hào)分別為1、2、3、4、5，這5個(gè)基本塊在執(zhí)行序列文件中對(duì)應(yīng)的執(zhí)行序列為123435。

圖2 基本塊集合與執(zhí)行序列示例

根據(jù)基本塊執(zhí)行序列文件中的編號(hào)序列來(lái)生成控制流圖。將所有的編號(hào)作為圖的節(jié)點(diǎn)，將編號(hào)的相鄰關(guān)系作為邊，邊的方向由先出現(xiàn)的編號(hào)指向它后面的編號(hào)，以邊重復(fù)出現(xiàn)的次數(shù)作為邊的權(quán)重。用符號(hào)G表示生成的控制流圖，G(V,E)表示包含節(jié)點(diǎn)集合V和有向帶權(quán)邊集合E的控制流圖。

例如，基本塊執(zhí)行的編號(hào)序列為123435，則將1、2、3、4、5 作為控制流圖的頂點(diǎn)，將執(zhí)行序列中的5 種相鄰關(guān)系作為連接頂點(diǎn)的有向邊，分別為（1，2）（2，3）（3，4）（4，3）（3，5），每條邊均只出現(xiàn)一次，因此邊的權(quán)重均為1。由此，生成了帶有循環(huán)結(jié)構(gòu)控制流圖，如圖3所示。

圖3 基本塊序列轉(zhuǎn)控制流圖示例

2.3.2 相似度計(jì)算

圖的相似度計(jì)算是一個(gè)非常復(fù)雜的問(wèn)題，在實(shí)際應(yīng)用過(guò)程中常常根據(jù)實(shí)際情況對(duì)圖進(jìn)行專門的處理，從而降低復(fù)雜度，提高計(jì)算效率。對(duì)于程序的動(dòng)態(tài)控制流圖來(lái)說(shuō)，最關(guān)鍵的部分是其中的分支結(jié)構(gòu)、循環(huán)結(jié)構(gòu)，這兩種結(jié)構(gòu)包含了程序運(yùn)行中的控制轉(zhuǎn)移信息。而順序結(jié)構(gòu)對(duì)于控制流圖來(lái)說(shuō)是不重要的，而且在控制流圖中大量存在，因此對(duì)控制流圖中順序結(jié)構(gòu)的部分進(jìn)行合并能夠有效縮小圖的規(guī)模，且不影響圖的相似度計(jì)算。

通過(guò)檢查頂點(diǎn)及其相鄰頂點(diǎn)的出度和入度來(lái)識(shí)別垂直結(jié)構(gòu)。如果一個(gè)頂點(diǎn)的入度大于1 或出度大于1，則該頂點(diǎn)在一個(gè)分支結(jié)構(gòu)上，需要保留，例如圖3 中的頂點(diǎn)3。由這種頂點(diǎn)指向的的頂點(diǎn)也需要保留，例如圖3中的頂點(diǎn)4和頂點(diǎn)5，其余頂點(diǎn)可以合并。

例如，對(duì)于圖3 中的示例，頂點(diǎn)123 之間是垂直結(jié)構(gòu)，頂點(diǎn)345 之間是循環(huán)結(jié)構(gòu)，則由123435 序列可以簡(jiǎn)化為3435。簡(jiǎn)化示意圖如圖4所示。

圖4 控制流圖簡(jiǎn)化示例

控制流圖順序結(jié)構(gòu)合并算法偽代碼如下所示：

input：控制流圖節(jié)點(diǎn)集合V

控制流圖邊集合E

output：控制流圖節(jié)點(diǎn)集合V′

控制流圖節(jié)點(diǎn)集合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

根據(jù)實(shí)驗(yàn)結(jié)果，經(jīng)順序結(jié)構(gòu)合并處理，V和E的規(guī)模都下降到了原來(lái)的20%以內(nèi)。

將兩個(gè)控制流圖的相似度定義為兩個(gè)控制流圖公共子圖規(guī)模與原圖規(guī)模的比值。基于VF2 算法[26]來(lái)獲取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

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

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

定義7（圖的規(guī)模）將圖G的規(guī)模定義為圖中節(jié)點(diǎn)與邊的總數(shù)，記為Scale(G)。

則G1與G2的相似度計(jì)算公式為：

例如，對(duì)于圖5中的兩個(gè)控制流圖A和B，A中頂點(diǎn)3、4、5組成的圖與B中頂點(diǎn)1、2、3組成的子圖同構(gòu)，則A與B的公共子圖規(guī)模為6。圖A的規(guī)模為6，圖B的規(guī)模為10，則兩個(gè)圖的相似度為0.75。

圖5 控制流圖相似度計(jì)算示例

2.4 基于二維特征整合的相似度計(jì)算

基本塊集合可以表征程序語(yǔ)義特征，控制流圖可以表征程序結(jié)構(gòu)特征，將這兩種特征結(jié)合，從語(yǔ)義和結(jié)構(gòu)兩種維度來(lái)計(jì)算程序之間的相似度，能夠使相似度計(jì)算結(jié)果更為準(zhǔn)確、更可信。

定義8（程序相似度）將兩個(gè)程序之間的相似度定義為兩個(gè)程序動(dòng)態(tài)基本塊集合相似度與動(dòng)態(tài)控制流圖相似度的線性組合，記為simPro。

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

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

3 實(shí)驗(yàn)評(píng)估

本文對(duì)提出的方法進(jìn)行了可行性實(shí)驗(yàn)和可靠性實(shí)驗(yàn)，從可行性、可靠性兩方面對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行評(píng)估。

實(shí)驗(yàn)在搭載有VM虛擬機(jī)的服務(wù)器上進(jìn)行，實(shí)驗(yàn)環(huán)境包括Win7操作系統(tǒng)、pin工具和python環(huán)境。詳細(xì)實(shí)驗(yàn)環(huán)境如表1所示。

表1 實(shí)驗(yàn)環(huán)境

3.1 可行性實(shí)驗(yàn)

可行性實(shí)驗(yàn)用于測(cè)試本方法能否正確識(shí)別程序的相似性。本文從惡意程序分析網(wǎng)站獲取了7 組惡意程序，共120 個(gè)樣本進(jìn)行可行性測(cè)試實(shí)驗(yàn)，同組程序都是相同惡意程序的變種，程序組別與樣本個(gè)數(shù)如表2所示。

表2 實(shí)驗(yàn)樣本列表

計(jì)算每個(gè)程序與自身的相似度，均為1.0。

對(duì)同組程序兩兩之間進(jìn)行相似度檢測(cè)，實(shí)驗(yàn)結(jié)果統(tǒng)計(jì)如圖6所示。

同組程序之間的相似度計(jì)算結(jié)果中約有99%大于0.8，說(shuō)明本方法能夠有效識(shí)別相似的惡意程序。

對(duì)不同組程序兩兩之間進(jìn)行相似度檢測(cè)，每組程序之間的平均相似度統(tǒng)計(jì)結(jié)果如表3所示。

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

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

不同組程序之間的相似度平均值在0.4 以內(nèi)，說(shuō)明本方法能夠區(qū)分相似性較小的惡意程序。

由實(shí)驗(yàn)結(jié)果得知，本文方法既能識(shí)別相似性較大的程序又能區(qū)分相似性較小的程序，說(shuō)明本方法在惡意程序的相似性分析上是可行的。

多次重復(fù)上述實(shí)驗(yàn)，得到相同的實(shí)驗(yàn)結(jié)果。由此可見，本文方法是穩(wěn)定可行的。

3.2 可靠性實(shí)驗(yàn)

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

表4 加殼后程序與原程序相似度部分?jǐn)?shù)據(jù)

對(duì)相似度取值范圍進(jìn)行統(tǒng)計(jì)，結(jié)果如圖7、8所示。

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

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

從圖7 和圖8 的實(shí)驗(yàn)結(jié)果中可以看出，加殼變形后的程序中有大約83%與原程序的相似度達(dá)到0.9 以上，約94%達(dá)到0.8 以上，說(shuō)明本文方法能夠有效地對(duì)抗程序加殼變形手段，是可靠的。

4 結(jié)語(yǔ)

本文提出一種基于控制流圖和指令基本塊的惡意軟件相似度分析方法，首先使用PinFWSand 沙箱建立程序指令流快照，并使用索引庫(kù)的方式進(jìn)行存儲(chǔ)，然后對(duì)獲取的指令流信息進(jìn)行預(yù)處理，去除基本塊集合和控制流圖的干擾噪聲，最后綜合程序基本塊集合和控制流圖的相似度得出程序間的相似度。本文方法從程序結(jié)構(gòu)和代碼語(yǔ)義兩個(gè)方面綜合考慮程序的相似度，對(duì)程序相似度的衡量更全面更準(zhǔn)確，能夠有效的識(shí)別同源的惡意軟件，并且能夠?qū)託さ溶浖冃问侄斡休^好的抗干擾效果。本文未對(duì)這兩種相似度進(jìn)行加權(quán)計(jì)算，在下一步的工作中需要對(duì)兩者在軟件相似中的權(quán)重進(jìn)行研究。