面向跨架構惡意軟件的函數相似性檢測和衍變分析

王曉磊， 楊 林， 馬琳茹， 穆 源， 施江勇， 宋焱淼

(1.61660部隊，北京 100093；2.軍事科學院 系統工程研究院，北京 100141；3.國防科技大學 計算機學院，湖南 長沙 410073)

眾所周知，惡意軟件一直在衍變以增加新功能、提升隱蔽性，從而產生一系列不同版本的樣本，這些樣本在功能上并非都是獨一無二的。例如，同一個物聯網惡意軟件樣本往往針對不同體系架構(x86，mips，arm等)編譯出不同的可執行文件[1-2]。

惡意軟件衍變分析主要研究惡意樣本之間的演化關聯關系，對于惡意軟件分析和取證具有重要的應用價值。給定一個惡意軟件的樣本集合，衍變分析要解決的一個重要問題是獲取這些樣本之間的偏序關系，這里的偏序關系是指兩個先后出現的樣本之間存在繼承或演化關系?；谘茏兎治?，安全人員可以了解惡意軟件的發展趨勢，判斷不同的惡意代碼是否源自同一套惡意代碼或是否由同一個作者、團隊編寫[3]。同時，針對某一特定惡意軟件家族的衍變分析還可以提取出此家族的核心特征(基因)，便于后續的分類以及樣本溯源等工作。

目前研究人員提出了許多惡意軟件衍變分析方法，主要原理是兩個代碼高度相似甚至相同的樣本很有可能是同一家族版本[4-10]。然而目前衍變分析中所用的代碼相似分析技術存在缺陷，極大地限制了惡意軟件衍變分析應用的準確性和拓展性。主要是：

(1) 相似性分析的時間開銷較高。例如，BinHunt系統[11]基于控制流圖進行比較并使用符號執行來進行語義相似性分析，盡管該方法提升了比較的準確性，但其方法時空復雜度很高，需要消耗大量時間。文獻[5]的研究表明，使用BinHunt分析兩個惡意程序版本需要30 min至1 h。

(2) 相似性分析的準確度不高。例如，文獻[6]從代碼中提取了12類特征，包括匯編代碼的n-gram特征、靜態程序塊統計特征和動態執行指令的統計特征，然后借助Jaccard距離來分析代碼之間的相似性。該方法時間開銷不高，但是相似性分析的漏報率很高，導致最終的惡意軟件衍變分析準確度只有不到72%。文獻[5]中使用的基于小質數乘積的方法也面臨著高漏報率、準確度不高的問題。

(3) 難以應對跨架構(平臺)的惡意軟件。盡管提出的許多方法嘗試從準確性、高效性等不同方面提升惡意軟件衍變分析的效果，但是這些方法都未充分考慮跨架構惡意軟件的場景。而隨著跨架構惡意軟件尤其是IoT惡意軟件的日益增加，其攻擊目標往往針對多個不同架構的設備，已有的大部分代碼相似性分析方法都不能有效解決相同代碼跨架構編譯的問題，難以在此類情況下準確地進行惡意軟件的衍變分析。

針對當前惡意軟件衍變分析存在的缺陷，本文提出了一種新的函數相似性檢測方法，以進一步提升跨架構惡意軟件衍變分析的準確性和拓展性。

1 研究動機和相關背景知識

1.1 研究動機

前面提到，研究人員已經提出了大量代碼相似性方法用于分析惡意樣本之間的衍變關系，具有代表性的是文獻[5]提出的一種基于質數相乘的SPP-NOP函數哈希方法。具體來說，就是根據指令助記符，為不同的指令分配一個小的質數，然后將某個函數內包括的所有指令對應的質數相乘，其結果作為該函數的哈希值，這樣不同樣本之間相同的哈希值數量就可以作為度量它們之間函數相似性的依據。此方法以函數作為相似性比較的基本粒度，雖然具有很高的相似性比較效率，但是基于質數相乘的哈希方法準確度較低。除此之外，為了進一步驗證SPP-NOP哈希方法是否能夠有效分析跨架構樣本的函數相似性，將獲取的一款名為Lightaidra的公開物聯網惡意軟件源代碼(其中包含49個函數)，編譯成面向不同架構(x86_32，mips，mipsel，arm，ppc)的二進制文件，然后使用SPP哈希方法來分析這些不同架構二進制文件之間的函數相似性，具體結果如圖1所示。其中每個小格表示不同架構之間的相同函數的個數，越大表示相似度越高?？梢园l現，除了mips和mipsel架構之間函數相似度很高外，SPP哈希方法很難捕捉到其他架構樣本之間的函數相似性，因此也就難以用于分析它們之間的衍變關系。和SPP函數哈希方法一樣，其他很多方法也都存在此缺陷。

圖1 基于SPP-NOP的跨架構函數相似性混淆矩陣

針對上述跨架構代碼相似性分析問題，本文提出了一種基于Weifeiler-Leman圖同構測試的跨架構函數相似性檢測新方法WLHash。作為比較，圖2顯示了新方法WLHash檢測跨架構Lightaidra代碼相似性的結果?？梢钥闯?，所提方法極大地提升了不同架構之間的代碼相似度，為后續更加準確地分析樣本或文件之間的衍變關系，奠定了堅實基礎。

圖2 基于WLHash的跨架構函數相似性混淆矩陣

1.2 相關背景知識

為了進一步提升代碼相似性檢測的準確度，目前主流方法是先將函數轉化為控制流圖(CFG)的形式，其中每個節點表示程序塊，然后再進一步刻畫該函數的語義和結構信息，最終通過圖匹配來完成代碼相似性檢測。但是圖匹配的比較開銷比較大，這些方法在進行代碼相似性分析時效率低下。為此，本文提出了一種相似性比較方法，結合了局部敏感哈希(locality sensitive Hash, LSH)和Weifeiler-Leman圖同構測試?；舅悸肥歉鶕绦驂K包含的指令，借助LSH將控制流圖進行有效的哈希編碼，然后基于哈希編碼進行相似性度量，進而提升代碼相似性分析的準確性和效率。

1.2.1 局部敏感哈希

局部敏感哈希其主要思想是，如果兩個高維空間中的點距離很近，那么設計一種LSH哈希函數計算這兩個點的哈希值，使得它們哈希值一樣的概率很大；若兩點之間的距離較遠，則它們哈希值相同的概率會很小。LSH常見的實現算法是隨機投影法，其思想是隨機生成一些超平面，對空間進行分割，并根據與每個超平面的相對位置對每個輸入進行編碼，最終的編碼即為LSH哈希值。通過隨機投影，兩個高度相似的輸入對于不同的超平面大概率會有相同的相對位置，即最終落在同一空間分區，因此得到的LSH哈希值也一樣。實際應用中，通過計算每個輸入的LSH哈希值，當給定一個輸入，可以快速檢索其他相似輸入。

1.2.2 Weifeiler-Leman圖同構測試

基于控制流圖的代碼相似性分析涉及比較兩個圖是否同構的問題。兩圖同構指的是圖中對應節點的特征信息(attribute)和結構信息(structure)都相同。圖同構問題是一個NP-hard的問題，目前為止還沒有多項式算法能夠解決，而Weisfeiler-Leman圖同構測試算法(以下簡稱WL算法)是一個能夠適用于大多數情況的多項式解決算法。

WL算法同時考慮了圖中的節點特征(attribute)和結構(structure)信息，節點的特征常常用特定標簽表示，而結構信息指節點之間的拓撲連接關系。WL主要是通過聚合鄰居節點的標簽label，然后通過哈希函數得到節點新的標簽，不斷重復直到每個節點的標簽穩定不變。

下面參照文獻[12]來簡單說明WL算法流程，如圖3所示。

圖3 WL的一輪迭代過程

WL算法實現步驟如下：

(1) 根據節點的特征信息，為其賦予標簽。

(2) 對鄰居節點標簽信息進行聚合，每個節點將獲得一個帶標簽的字符串，該字符串以逗號分隔為兩部分，第一部分是該節點上一輪迭代的標簽，第二部分是該節點的鄰居節點標簽按默認升序排序后連接形成的(例如對于節點5，其鄰居節點為2,3,4，所以其結果為“5,234”)。

(3) 標簽壓縮，為了能夠生成一個一一對應的字典，將每個節點的字符串哈希處理后得到節點的新標簽。

(4) 重標記，將哈希處理過的標簽重新賦給相應的節點，從而完成一輪迭代。

2 衍變分析系統

以函數作為衍變關系推斷的基本粒度，提出一種新的函數相似性比較方法，并基于此進行衍變分析，整體架構如圖4所示。

圖4 衍變分析整體架構

衍變分析主要包括兩個階段。階段1中提出了一種新的函數哈希算法WLHash，負責計算每個函數的哈希，并進行存儲；階段2則基于前期獲取的函數哈希進行衍變分析推斷。在階段1中，初始輸入為所有待分析樣本和它們包含的函數，然后針對每個函數進行一系列操作，包括程序塊向量化、LSH哈希和WL圖同構測試，并獲取最終的函數哈希。在階段2中則充分利用階段1獲取的函數哈希，進行衍變關系推斷，基本思路是根據一個待分析樣本中包含的函數，逐個查找與該函數相似的其他樣本中的函數，從而獲得它們之間的衍變關系。如圖4所示，某個樣本中包含一個函數ft，通過查詢前期存儲的函數哈希，找到了與ft相似的函數f1，從而可以獲得該樣本與其他樣本之間的關系。這里有兩點需要額外說明，一是函數哈希計算過程中，兩個高度相似的函數，它們最終的哈希值是相同的；二是在函數哈希計算中，除了存儲函數與哈希的對應關系外，還存儲了函數與樣本之間的包含關系，便于后期衍變關系推斷使用。

2.1 階段1：函數哈希計算WLHash

提取每個函數的控制流圖(CFG)來作為哈希計算的依據，其中控制流圖的節點表示函數中的程序塊，而邊則表示程序塊之間的跳轉關系。為了更為準確地進行函數相似性比較，在計算函數哈希的過程中同時考慮程序塊的語法特征和控制流圖的結構特征。具體來說，就是通過對程序塊中指令的進行正則化處理，得到程序塊的向量化表示；在此基礎上，使用局部敏感哈希來獲取每個程序塊的標簽，從而可以將原始控制流圖轉化為一個節點帶有標簽的圖，并最終經過WL圖同構測試來獲取最終的函數哈希。

2.1.1 程序塊向量化

面向不同架構編譯的相同源代碼會輸出不同的二進制代碼，這些代碼雖然語義上是等效的，但語法上往往差異很大。這種由跨架構編譯帶來的差異化因素主要包括：指令助記符、地址屬性、寄存器使用、指令排序等。為此，程序塊的向量化表示主要是為了消除這些可變因素，使得盡可能準確地度量兩個程序塊之間的相似性。

如圖5所示，最左側表示原始程序塊包含的代碼。為了消除跨架構編譯帶來的差異因素，中間的正則化(normalization)按指令助記符類型(stack，jump等)以及操作數類型(reg，mem等)對原始指令進行抽象簡化，最右側簡化后，忽略指令順序，統計不同指令抽象的數量，并轉化為最終的向量化表示。本文采用的正則化將指令助記符分為6類，而操作數類型分為4類，這樣一個指令助記符加上兩個操作數的可能組合為96，因此每個程序塊最終表示成一個96維的向量。

圖5 程序塊向量化表示

2.1.2 LSH哈希

LSH哈希的任務就是為相似的向量分配相同的標簽，即為每個程序塊分配標簽。和許多LSH方案一樣，本文也使用隨機投影對空間進行劃分，然后根據針對每個超平面的相對位置對每個輸入進行二進制編碼。如果產生兩個超平面，則可將空間分為4個分區，分別編碼為00,01,10和11。而相似的輸入落在同一空間分區的概率更高，因為它們更可能與超平面具有相同的相對位置，這樣相似的輸入就很可能有相同的編碼。例如，按照上面的分區，兩個高度相似的輸入同時落在了10分區，則可轉化為十進制的2，即兩個輸入最終的LSH哈希為2。這樣通過上述計算，就可以得到每個程序塊對應的LSH哈希，并作為其節點標簽。本文實際選擇使用96個超平面，數量與每個程序塊的向量維度相同。大多數LSH每次產生的超平面都是隨機的，導致最終計算結果并不唯一，為了解決這個問題，本文保存了首次隨機產生的超平面，后續一直使用這個超平面[13]。

2.1.3 WL圖同構測試

經過上述兩個步驟，可以將函數的控制流圖轉化為一個節點帶標簽的圖，接下來采用WL圖同構測試來將此帶標簽的圖轉化為一個哈希，這樣可以對大量的函數控制流圖進行預先計算，然后進行大規模比較和搜索。函數哈希核心思想是基于函數的控制流圖，通過一系列的鄰居節點標簽聚合和節點重新標記來進行。

具體計算過程如表1所示。第1行是針對圖中的每個節點，WL圖同構測試收集節點的每個鄰居標簽信息(算法第4～6行)，并將它們排序成一個有序列表(第7行)，然后對節點的原始標簽和其有序的鄰居節點標簽進行哈希操作(第8行)，作為節點的新標簽。最后，經過若干輪鄰居節點標簽聚合和重新標記(第10行)，可以最終得到圖中所有節點的最新標簽(第11行)。最后，對排序后的節點最終標簽進行合并和哈希操作(第12、13行)來計算圖哈希，作為對應函數的哈希。這里有一點需要強調的是，實際研究發現WL圖同構測試多輪迭代操作并未大幅提升后續相似性比較的準確性，但卻導致巨大的計算開銷，因此僅使用1輪迭代來計算圖哈希。

表1 基于WL圖同構測試的函數哈希算法

以圖3為例，經過1輪WL圖同構測試后，兩圖G和G′的有序節點標簽列表分別為{6-6-8-10-11-13}和{6-7-9-10-12-13}，因此兩圖最終的圖哈希分別為hash(6-6-8-10-11-13)和hash(6-7-9-10-12-13)。

2.2 階段2：建立衍變圖

在計算完所有樣本中函數的圖哈希后，衍變關系推斷的主要目標就是以這些圖哈希和對應樣本為輸入，分析它們之間的衍變關系，并最終生成一個較為完整的衍變圖。其中節點表示樣本，邊表示樣本之間父子繼承關系。根據前期每個函數計算的圖哈希，繼承關系的主要依據是樣本插入衍變圖的先后和它們之間的相似性，相似性度量的標準就是樣本之間相同函數的個數。在軟件開發過程中，常常出現軟件版本的分叉和融合，版本分叉允許開發者在不影響其他版本的基礎上修改和測試新功能，而版本融合則往往是為了結合若干版本的特定功能。如表2中算法所示，衍變圖建立主要包括3個步驟：

(1) 根節點識別。

(2) 建立包含分叉的衍變圖(對應算法中的Lineage_branch函數)，這個階段以選定的根樣本為起始點，根據樣本之間的相似性，不斷地向圖中插入剩余樣本，在這個階段一個父節點可能有多個子節點。

(3) 衍變圖添加交叉邊(對應算法中的Lineage_merge函數)，這個階段判斷某個樣本在功能函數上是否與其他樣本有繼承關系，即一個節點可能有多個父節點，然后向圖中添加對應的交叉邊。

2.2.1 根節點識別

衍變圖在初始時是一棵空樹，如何選擇和插入第一個節點(根節點)至關重要。在軟件工程領域，軟件演化 (software evolution)是指對軟件進行維護和更新的一種行為，它是軟件生命周期中始終存在的變化活動。針對軟件演化，Lehman等[14]提出了8條軟件演化法則，其中第六條的功能持續增加法則聲明在軟件的生命周期中，軟件功能必須持續增加，即程序會隨著時間的推移而增長。受此啟發，在表2算法中第3行，首先從初始樣本集合中選取根節點，依據是它包含的功能函數最少而且到所有其他節點的平均相似度之和最大。

2.2.2 建立包含分叉的衍變圖

在選定了根節點后，接下來需要遍歷所有其他樣本來建立包含分叉的衍變圖，具體流程如表2算法中的函數Lineage_branch所示。對于每一個未插入衍變圖的樣本，首先需要確定它和衍變圖中的哪個節點存在衍變關系，而此過程需要將待插入樣本和衍變圖中已有樣本進行相似性比較(算法第10行)，并將相似性最高的樣本作為待插入樣本的父節點，把待插入樣本作為子節點(第13行)，然后在父、子節點之間建立一條指向邊(第14行)，表示衍變關系。這里，兩個樣本之間的相似性程度是通過度量兩者之間相似函數的個數，具體實現就是兩個樣本之間相同的函數哈希個數越多，相似程度越高。在通過相似性比較不斷插入樣本過程中，表2中算法能夠處理兩種特殊情況：

表2 衍變圖建立算法

(1) 如果有多個已插入樣本和待插入樣本具有相同的函數哈希個數，則進一步通過細粒度的指令類型統計來比較樣本之間的相似性程度，把函數哈希個數相同且指令類型統計更接近的樣本作為最終的相似樣本;

(2) 如果所有已插入樣本與待插入樣本的相似度都不高(算法第11、12行)，則可能與待插入樣本相似的樣本還未插入，因此暫時跳過，先分析其他未插入樣本。

基于函數相似性比較，表2算法中的Lineage_branch函數通過不斷的比較、插入樣本，最終可以得到一個包含多分叉的衍變圖，其中每個子節點至多只有一個父節點，而一個父節點則可能有多個子節點。

2.2.3 衍變圖添加交叉邊

衍變圖中，每個子節點最多只有一個父節點。然而，實際情況是一個樣本往往可能和多個樣本有繼承和演化關系。因此，還需在建立的衍變圖中添加額外的交叉邊用以表示衍變關系，表2算法中的Lineage_merge函數描述的就是這個過程。添加交叉邊的具體流程是，對于圖中的某個節點v，首先確定其父節點(算法23行)，及未能從父節點繼承的新增函數(第24行，即該節點自身包含但父節點沒有的函數)?；诠濣cv的新增函數，算法第27行主要任務就是從圖中進一步搜索節點v可能的其他候選父節點，在搜索過程中首先排除節點v現有的父節點和子節點(第25行)，然后從剩余節點中找出可能的父節點。之所以排除節點v的父節點，是因為它已經影響了當前節點，而排除其子節點，則是避免在衍變圖中產生循環。候選父節點的搜索是一個迭代的過程，首先從剩余節點中找出和節點v共有最多新增函數的節點，作為一個候選父節點；然后，將這些發現的共有函數從最開始的新增函數集中刪除，作為搜索下一個候選父節點所需的新增函數集，直至新增函數集大小小于某個閾值(本文設置為5)。最終，根據這些搜索到的候選父節點，在衍變圖中添加它們和當前節點v之間的指向邊(第30行)。

最終經過搜索其他父節點并添加額外交叉邊，衍變圖中某個節點可能存在多個父節點，能夠更加準確地刻畫樣本間的衍變關系。值得注意的是，前面提出的面向函數的圖哈希算法極大地提升了此階段的運算效率，因為基于圖哈希的搜索允許在O(1)的時間內迅速判斷某個新增函數是否包含在某個樣本中。

3 實驗評估

實驗評估主要包括3個部分：(1) 基于已知的正常程序衍變版本，評估提出的衍變分析方法的準確性；(2) 對跨架構的IoT惡意樣本進行衍變分析，并對生成的衍變圖進行統計；(3) 評估所提方法的性能開銷。

3.1 實驗環境與數據集

3.1.1 實驗環境

實驗在一個臺式機上運行，其配置為Intel i5-4460，CPU主頻3.1 GHz，內存16 GB；所有程序均由Python語言編寫，使用IDA pro 7.0對二進制程序進行反編譯；使用MongoDB存儲程序所有的中間輸出(例如函數哈希)。

3.1.2 數據集

由于缺乏可以直接用于評估惡意軟件衍變分析準確性的數據集，故搜集了已知衍變關系的Putty系列程序，如表3所示，共計7個程序，24個版本，每個版本對應一個樣本，總計168個樣本，均為x86架構，從首個版本的發布到最近發布間隔18.5 a。

表3 Putty系列程序

同時也搜集了1 804個跨架構的IoT惡意樣本用于衍變分析，如表4所示，第一列是家族名，其余的列分別是不同架構和所對應的樣本數量。

表4 跨架構IoT惡意樣本

3.2 衍變分析的準確性評估

在進行衍變分析準確性評估之前，首先定義準確性評估標準。衍變圖本身是一個有向圖，通過邊來表示樣本節點之間的衍變關系，其實質是一個嚴格的偏序關系。假如4個樣本a、b、c、d的真實衍變關系為a->b->c->d，將生成的衍變圖與真實衍變關系進行對比，通過搜索偏序不一致的實例來評估其準確性。舉個例子，假如生成的衍變圖中上述4個樣本的衍變關系為a->b->d->c，通過與這個真實的偏序衍變關系進行比較，可以發現存在一個偏序不一致實例，即d->c與c->d不符。本文定義，與真實衍變關系相比，最終生成的衍變圖中存在的偏序不一致性(partial order inconsistency，POI)越少，則其準確性越高。

為了評估衍變分析的準確性，選取了Putty系列程序作為分析對象，這樣做主要是因為它有多個衍變版本，而且衍變路線清晰且已知，便于評估衍變結果的準確度。如表3中提到的，這些Putty系列程序共計24個版本，從開始版本0.52到結束版本0.74，每個版本對應一個樣本。通過衍變分析，最終得到每一個程序對應的有向衍變圖，其中每個節點表示樣本及其版本號，邊的方向揭示了樣本之間的衍變關系，邊的顏色和粗細表示了樣本之間相似的程序，例如圖6是生成的putty程序衍變圖，其中包含24個頂點，41條邊。

圖6 putty衍變圖

圖中較粗的邊是在衍變圖生成過程中由函數Lineage_branch生成，表示衍變的主體路線，而較細的邊則是由函數Lineage_merge生成的交叉邊。從圖中可以看出，較粗的邊清晰地表示了各個樣本之間的主體衍變關系，而較細的交叉邊則在一定程度上反映了樣本之間功能的繼承關聯關系。

具體來說，對于生成的衍變圖，準確性評估的方法是通過人工查看每個樣本之間的前后繼承關系，查看得到的衍變圖是否準確遵循了真實版本演化過程。經過人工分析發現，圖6的putty衍變圖中，最終得到了putty-0.68->putty-0.69和putty-0.68->putty-0.70的衍變關系，與真實的衍變關系putty-0.68->putty-0.69 ->putty-0.70相比，偏序不一致性數量為1。在衍變分析過程中，出現偏序不一致性的主要原因是函數相似性計算過程中出現偏差。比如兩個函數本來相似度不高，但是采用某些函數相似性計算方法導致兩者高度相似，從而引入錯誤的衍變關系。

為此，針對搜集的7個Putty系列程序，分別計算了它們的衍變圖，并手工分析了它們的偏序不一致性。同時為了與WLHash函數哈希方法進行對比，在衍變分析過程中，也嘗試采用了文獻[7]中的函數哈希方法SPP-NOP來計算最終的衍變圖。結果如表5所示，其中|V|表示節點數，|E|表示邊數，|C|表示添加的交叉邊數，而|POI|表示偏序不一致數。從表5中可以看出，不論是SPP-NOP哈希，還是WLHash哈希，都會造成最終生成的衍變圖出現一定的偏序不一致性，但是兩者結果還比較接近，基于SPP-NOP的函數哈希方法產生了20個偏序不一致實例，而基于WLHash的方法產生了22個偏序不一致實例。出現偏序不一致性的根本原因是兩個函數哈希方法在計算函數相似時會出現一定的誤報。例如，pscp-0.69中的函數“sub_4337E3”的WLHash函數哈希和pscp-0.54中的函數“sub_4210A6”、“sub_40E958”和“sub_40B4E9”的WLHash函數哈希相同。但實際情況是，pscp-0.69中的函數“sub_4337E3”只和pscp-0.54中的函數“sub_4210A6”相似。與此同時，SPP-NOP的函數哈希方法也會出現一定的誤報，例如putty-0.68中“sub_4210A6”的SPP-NOP函數哈希與putty-0.70中“sub_46419D”和“sub_4969E8”的SPP-NOP函數相同，但實際上，putty-0.68中的“sub_4210A6”函數只與putty-0.70中的“sub_46419D”函數高度相似。

表5 Putty系列程序衍變圖統計結果

3.3 跨架構惡意軟件的衍變分析

按照前面的分析流程，對搜集到的跨架構IoT惡意軟件(表4)也進行了同樣的衍變分析，同樣使用了文獻[7]所提的SPP和WLHash兩種函數哈希方法，并最終生成惡意樣本對應的衍變圖，衍變圖的具體信息如表6所示。

表6 惡意軟件衍變圖統計結果

從表6中的新增交叉邊數|C|可以看出，基于WLHash函數哈希的衍變分析方法識別出更多跨架構樣本之間的衍變關系。以Tsunami家族為例，基于SPP和WLHash的函數哈希所產生的衍變圖分別包括47和58條邊，以及11條和22條交叉邊。接下來以Tsunami的衍變圖進行比較說明，其中圖7是基于SPP函數哈希所生成的衍變圖，而圖8是基于WLHash函數哈希所生成的衍變圖中每個節點名稱使用編號+架構來表示，例如節點0_x86表示0號樣本，其架構為x86。

圖7 基于SPP-NOP的Tsunami衍變圖

圖8 基于WLHash的Tsunami衍變圖

通過對比Tsunami的兩個衍變圖，可以很容易發現WLHash函數哈希能夠捕捉更多跨架構樣本之間的衍變關系，以樣本0_x86為例，在圖7中它是孤立節點，與其他節點沒有衍變關系，而在圖8中則與多個其他架構的樣本具有衍變關系。

除了0號樣本，通過對比發現WLHash函數哈?？梢园l現其他跨架構樣本之間的衍變關系，因此可以有效輔助跨架構場景下的惡意軟件分析。

3.4 WLHash函數哈希的性能開銷

為了評估本文所提出的WLHash函數哈希的計算開銷，對搜集到的1 804樣本進行函數哈希計算，并統計每個樣本的分析時間，時間分布如圖9所示。平均每個樣本的函數分析時間是2.45 s，95%的樣本都能在4.14 s內計算完函數哈希。上述實驗結果表明，WLHash函數具有較低的計算開銷，適用于計算大規模惡意軟件樣本的函數哈希。

圖9 WLHash計算時間CDF分布圖

4 結果分析

4.1 代碼相似性分析

作為程序分析領域的一個經典問題，代碼相似性分析常常指的是在無法獲得源碼的情況下分析二進制函數的相似性，在安全和知識產權保護等領域中有重要應用，例如惡意軟件分析，漏洞檢測，版權糾紛等。截至目前，研究人員已經提出了大量代碼相似性分析方法[15-27]。文獻[28]對現有代碼相似性分析工作進行了分類，根據提取的程序特征粒度，將已有方法分為4類：基于指令特征的方法、基于程序基本塊特征的方法、基于程序函數特征的方法和基于整個程序特征的方法；根據相似性的類別，又可分為語法相似性、語義相似性和結構相似性3類。

作為較早的代碼相似性比較方法，模糊哈希技術通過計算代碼的哈希值來識別相似的惡意軟件變種。比如最具有代表性的模糊哈希技術SSdeep[29]，已被VirusTotal作為所有提交的惡意軟件樣本的文件屬性之一。盡管SSdeep和大多數現有的模糊哈希工具提供了一定的代碼相似性分析能力，但其魯棒性較差，代碼中的微小改動就會導致哈希變動，使得相似性程度大幅下降。

為了提升代碼相似性比較的準確性，目前主流的方法是基于函數的控制流圖來進行相似性分析，這樣就能同時考慮代碼的結構和語義信息?；诳刂屏鲌D的相似性分析設計圖同構分析問題是一個NP-Hard問題，因此研究人員提出了各種方法通過利用控制流圖中的一些特征(例如有界度)來近似逼近控制流圖的相似性。(1)最小權二部圖匹配。Hu等[30]提出了一種基于編輯距離的圖同構算法，原理是通過建立兩個圖中不同節點映射成本的成本矩陣，并使用匈牙利算法[31]找到節點之間的最優映射，從而使總成本(即編輯距離)最小化。根據鄰居節點的相似性，文獻[32]迭代地建立兩個CFG節點之間的相似矩陣，并同樣采用匈牙利算法來尋找兩個圖中節點之間的匹配，使得得到的相似性數值最高。(2)最大公共子圖匹配。文獻[33]設計了一個回溯搜索算法來得到兩個圖的最大公共子圖。該思想已被用于設計高效的CFG相似度比較算法，并被用于二進制語義差異分析[11]和二進制代碼搜索[34]場景中。在給定最大公共子圖輸出的情況下，圖的相似度得分為公共子圖節點的最大值除以兩個圖之間的所有節點的數目。(3)K-子圖匹配。Kruegel等[35]設計了一種基于K階子圖(包含K個節點)挖掘的算法。他們為圖中的每個節點生成一個生成樹，使得每個節點的出度小于或等于2，然后通過考慮根節點下K-1個節點的所有可能分配，從生成樹中遞歸地生成K階子圖。然后對每個K階子圖進行規范化處理，并通過連接其鄰接矩陣的每一行提取出指紋。(4)基于仿真的圖相似。文獻[36]使用標記的轉移系統對控制流圖進行建模，給定兩個控制流圖，它們遞歸地從入口節點開始匹配最相似的出口節點，并求出匹配節點和邊的相似度，然后用遞推公式定義兩個控制流圖的總體相似性。盡管圖匹配等方法在一定程度上提升了基于控制流圖的代碼相似性分析的準確性和效率，但是仍無法較好處理跨架構的代碼。

為了能夠進行跨平臺架構的代碼相似性分析，不同于傳統的圖匹配方法，近幾年來研究人員提出了全新的代碼相似性分析方法。例如，文獻[37]提出基于中間表示的代碼相似性分析方法，基本原理是首先將匯編代碼轉換為中間表示(IR)代碼來解決語法差異，然后再基于中間表示來分析代碼相似性。然而，現有的IR語言/平臺僅限于處理少數架構(即mips、arm、x86)，難以處理包含了多種不同架構的惡意軟件數據集。另外有研究者提出將圖嵌入技術應用于代碼相似性分析。例如，文獻[24]首先對控制流圖中的每個塊進行屬性標記，然后借助神經網絡進行圖嵌入，將轉化后的控制流圖轉化為數字向量，實現了跨平臺的代碼相似性比較，取得了較好的精度和效率。文獻[38]則提出了一種新的基于自然語言處理的二進制函數相似性分析方法，二進制程序經過反匯編之后則為一條條匯編指令，主要思路是將一條匯編指令當作一個單詞(word)而將一個程序塊視為一個語句(sentence)，通過訓練神經網絡挖掘出其中的語義表示，從而將本來代碼相似比較問題轉換為自然語言相似比較問題。除了上述方法，還有一些其他類似的基于圖神經網絡和圖嵌入等深度學習算法的跨架構代碼相似性分析方法[17-18,24,27]，但這些方法的可拓展性和效率還有待提高，第一，訓練過程需要大量標簽代碼數據；第二，圖嵌入的運行開銷會隨著代碼量的增加而增加。例如對于基于自然語言處理的文獻[24]來說，訓練數據集的大小十分重要，幾十萬條匯編指令的文本大小也不過幾十MB，這對于模型訓練來說是否足夠是個問題，訓練數據集小的一個重要后果就是在實際情況下表現可能會很差。

和上述工作相比，本文所提的方法在分析跨架構代碼的同時也兼顧了準確性和效率，提升了跨架構惡意軟件衍變分析的實用性。

4.2 惡意軟件衍變分析

惡意軟件衍變分析的本質是捕捉其演化過程，正如文獻[3]中總結的，惡意代碼存在兩個方面的演化：功能特性演化和生成方式演化。(1) 從功能特性演化方面來說，與早期相比, 新一代惡意軟件朝著定向性、持續性、隱蔽性和技術先進性等功能特性不斷演化；(2)從生成方式演化方面來說，新的惡意軟件很少從頭開始創建,大多數是采用自動生成工具、第三方庫以及借用現有的惡意軟件代碼生成,許多惡意軟件都是已存在惡意軟件的變體，超過98%的新惡意軟件樣本實際上是來自現有惡意軟件家族的衍生產品(或變體)。惡意代碼經過修改或者自行演化等途徑后,往往會形成數十種甚至更多的變種,使得變體數量迅速增長。通過分析惡意軟件間的衍變關系，可以迅速發現相似變種及其衍變關系，便于安全人員及時發現新型惡意變種及新特性。

針對惡意軟件的衍變分析研究可以追溯到20多年前，Hull等首次對Stoned引導扇區計算機病毒的演化進行了系統的分析。文獻[6]提到，軟件衍生關系推理主要目標是推斷程序之間的時間順序和祖先/后代關系，軟件衍變過程可以最終表示為一個衍變圖。

截至目前，研究人員已經提出了大量惡意軟件衍變分析方法[4-10，39-41]。例如部分文獻采用基于距離的層次聚類方法來分析惡意軟件之間的衍變分析。除了聚類方法外，文獻[42]提出了一種新的圖剪枝算法來建立不同惡意代碼實例之間的繼承關系，該算法主要考慮時間信息和惡意代碼描述中識別的關鍵短語。通過建立惡意代碼之間的繼承關系，可以進一步了解這些年來惡意代碼是如何演變的，特別是不同的惡意代碼實例是如何相互關聯的。文獻[43]則提出在樣本之間跟蹤和識別單個特征(例如，小代碼子集)，然后訓練分類器以正確識別衍變關系。作為兩個比較經典的惡意軟件衍變分析工作文獻[5，6]，文獻[6]從代碼中提取了12類特征，包括匯編代碼的n-gram特征、靜態程序塊統計特征和動態執行指令的統計特征，然后借助Jaccard距離來分析代碼之間的相似性，但是分析開銷和漏報率比較高；而文獻[5]提出使用小質數乘積的方法來分析函數相似性，并進而推斷衍變關系，也存在準確度不高的問題。

與這些工作相比，本文最大的貢獻在于提出了基于WLHash函數哈希的惡意軟件衍變關系推斷，極大地提升了分析準確性和效率，同時也適用于跨架構的惡意軟件衍變分析。

5 結論

本文提出了一種基于WL圖同構測試的函數哈希方法WLHash，用于函數相似性檢測，并對正常應用和跨架構惡意樣本進行了衍變分析，生成了衍變圖。實驗結果表明，與已有的函數哈希方法相比，本文所提的函數哈希方法在保證準確性和分析效率的前提下，能夠刻畫跨架構的函數相似性，從而捕捉到不同架構下樣本之間的衍變關系，能夠輔助安全人員更加準確地分析多架構惡意軟件家族的演化關系，具有很高的實際應用價值。

雖然本文提出了一種較為準確的函數相似性檢測方法，通過衍變分析也能夠找出相鄰兩個樣本之間函數的新增和刪減。但是對于分析人員來說，僅僅知道函數的新增和刪減情況并不能理解樣本之間的功能變化。在接下來的工作中，希望能夠進一步提取函數的語義摘要，從而能夠輔助分析人員迅速把握樣本之間在功能語義上的改變，以及功能新增或功能刪減。