二進制代碼相似分析綜述 - 網安 - 專業的網絡安全產業、社區、知識平臺

工作來源

ACM Computing Surveys 2022

工作背景

二進制代碼相似判斷有著廣泛的用途，如 Bug 搜索、惡意軟件聚類、惡意軟件檢測、惡意軟件譜系跟蹤、補丁生成、跨程序版本移植信息和軟件剽竊檢測等應用場景。其常見的八種應用如下所示：

但判斷二進制代碼相似性是很有挑戰的，不僅是函數名、變量名和數據結構等在編譯過程中丟失了大量的程序語義。當使用不同的編譯器、更改編譯器優化選項以及選擇不同的目標操作系統和 CPU 架構時，生成的二進制代碼都可能會發生顯著變化。

編譯過程

標準的編譯過程將程序源代碼作為輸入，選定編譯器、優化級別和體系架構等進行編譯，生成目標文件再鏈接成二進制程序。如下所示：

可以在編譯過程中增強對抗，比如應用混淆。混淆的方法多種多樣，大類可分為源代碼轉換和二進制轉換兩類。

加殼就是典型的二進制轉換方式，且很多惡意軟件已經開始使用自定義殼。
通過相同的源代碼生成語義等效的不同二進制程序的方式很多，修改編譯器的優化級別或者更換編譯器都可以達到目的。與此同時，為不同架構編譯的程序由于使用不同的指令集，生成的二進制代碼可能完全不同。

歷史發展

二進制代碼相似源于比較程序不同版本間的差異。由于重新編譯時會產生大量非源碼更改導致的程序改變，例如重新編譯時可能會改變的寄存器分配。

二進制代碼相似判斷工作首次出現在 1999 年。名為 EXEDIFF 的工具為 DEC Alpha 生成補丁，比較指令序列。名為 BMAT 的工具為 DLL 文件對其配置信息，比較基本塊與函數。

接下來的十年中，相繼出現了 7 種二進制代碼相似判斷工作，這些工作從語法相似提升到語義相似、擴大應用范圍到惡意軟件等。

2004 年，Thomas Dullien 首次提出構造函數調用圖基于圖進行二進制代碼相似判斷，以應對編譯器優化中的函數指令重排。后續的工作基于此又引入了基本塊的匹配，使用 Some Primes Product 哈希來識別相似的基本塊。這兩項研究也是 IDA 的 BINDIFF 插件的基礎。
2005 年，Kruegel 將相似功能的指令分為 14 類，據此為過程間控制流圖（Inter-procedural Control-flow Graph，ICFG）進行著色，以此對抗部分混淆手段（垃圾指令、指令重排、指令替換等），利用該方法檢測惡意軟件多態變種。
2008 年，Gao 設計的 BINHUNT 工具使用符號執行和約束求解器檢查基本塊的功能是否相似。
2009 年，Xin 設計的 SMIT 工具檢索惡意軟件的調用圖并使用圖編輯距離查找相似的惡意軟件。
在最近的十年間，出現了52種二進制代碼相似判斷的工作。
2015 年，Pewny 提出的 MULTI-MH 是第一個跨架構的二進制代碼搜索工具。
2016 年，Lageman 設計了一個神經網絡來判斷兩個函數是否是從相同的源代碼編譯的。

工作設計

二進制代碼相似判斷方案的三個主要區別在于：（1）比較的類型（相同、相似、等效）、（2）比較的粒度（指令、基本塊、函數）、（3）比較的數量（一對一、一對多、多對多）。

比較的類型

檢查相同很容易，但檢查相似很難。使用相同的編譯參數（相同的編譯器版本、相同的優化級別、相同的目標平臺）兩次編譯相同的程序源代碼都可能會產生兩個具有不同文件哈希的可執行文件。因為兩次編譯的文件中包含不同的元數據，例如編譯時間戳等。例如，mov %eax,$0 和 xor %eax,%eax 在語義上是等效的 x86 指令，都是將寄存器 EAX 的值設置為零。

證明兩個任意程序在功能上等價是一個不可能問題，類似停機問題。

相似可以從語法、結構和語義上進行判斷：

語法相似比較代碼。語法相似的計算成本最低，但魯棒性差，無法應對寄存器重新分配、指令序列重排、等效指令替換等情況。
結構相似比較圖（如控制流圖、函數調用圖等）。結構相似能夠應對語法轉換，但無法應對代碼結構的轉換（內聯函數或刪除未使用的函數參數）。
語義相似比較功能（系統調用/API）。語義相似的魯棒性最好，但計算代價也最大。

比較的粒度

常見的粒度是基本塊、函數和整個程序。具體來說，還區分為輸入片段的粒度和比較方法的粒度。

如上所示，細粒度的相似不能用于推斷粗粒度的等效或相同，但反之可以。例如函數的所有基本塊都相似，并不能說明函數的功能是相同或等效的。

比較的數量

比較方法中可分為:

一對一（OO），一對一方法大多是為了發現修改的內容。
一對多（OM），一對多方法大多是為了檢索與目標相似的片段。
多對多（MM），多對多方法大多是用于聚類任務。

工作準備

首先排除掉需要源代碼的工作、需要操作字節碼的工作、需要調用系統 API 的工作、需要將二進制代碼視為沒有結構的字節序列的工作。

閱讀過去 20 年的 14 個會議（IEEE S&P、ACM CCS、USENIX Security、NDSS、ACSAC、RAID、ESORICS、ASIACCS、DIMVA、ICSE 、FSE、ISSTA、ASE 和 MSR）的一百多篇論文，整理了以下 61 個工作。

在 61 個工作中，36 個至少對一個程序進行了定量評估。

技術平臺

下表顯示了各個工作使用的靜態分析和動態分析工具、實現的編程語言、支持的目標程序架構和操作系統等信息：

最受歡迎的靜態分析工具是 IDA，各個工作主要用它來進行反匯編和構建控制流圖。最受歡迎的動態分析工具是 PIN，其次是 TEMU 和 ANUBIS。還有其他一些優秀的分析工具，如下所示：

最受歡迎的編程語言是 Python，多達 20 個工作都采用了它，其次是有 14 個工作都采用的 C++。這種趨勢也與 IDA 被廣泛采用有關，IDA 支持 C++ 和 Python 兩個接口。
在二進制代碼分析中使用 IR 的優點在于重用建立在 IR 之上的分析模塊更容易。比如支持一個新的架構只需要增加一個新的前端就可以翻譯成 IR，但是分析代碼是可以復用的。有 15 個工作使用 IR，并且大多數工作都使用底層平臺提供的 IR。在 15 個使用 IR 的工作中，5 個工作使用 BITBLAZE 提供的 VINE，另外 5 個工作使用 VALGRIND 提供的 VEX，另外 2 個工作使用 LLVM-IR。其余 3 個工作使用的是 SAGE III、METASM 和 REIL。而令人驚訝的是，16 個跨架構匹配的工作中只有 6 個工作使用了 IR，其余工作都是為每個架構實現了單獨的分析模塊，這些模塊通常輸出通用格式的特征向量。
支持架構最多的是 x86/x86-64（59 個工作），其次是 ARM（16 個工作）和 MIPS（10 個工作）。
在這 42 個使用 IDA 的工作中，大多數只分析了 x86/x86-64，盡管 IDA 實際上支持很多其他架構。
支持操作系統最多的是 Linux（41 個工作），其次是 Windows（35 個工作），只有 4 個工作支持 MacOS。
其中只有 12 個工作是開源的（BINSLAYER、TRACY、QSM2015、ESH、GENIUS、KAM1N0、GEMINI、ASM2VEC、VULSEEKER、RLZ2019、INNEREYE、SAFE），其中 4 個工作（ESH、GENIUS、RLZ2019、INNEREYE）發布了源碼和機器學習模型。

數據方法

各工作的實驗評估如下所示：

數據集

大多數工作都使用自定義數據集，有 18 個工作都采用的通用數據集是 Corutils。
使用的兩個公開固件是 ReadyNAS 和 DD-WRT。
超過一半的工作評估的樣本數量都小于 100 個，7 個工作小于 1000 個，8 個工作小于 1 萬個，只有 8 個工作評估了超過 1 萬個樣本。
在 61 個工作中有 37 個工作只評估了良性程序，8 個工作只評估了惡意軟件，16 個工作對二者都進行了評估。特別的，在評估惡意軟件的 24 個工作中，只有 5 個（SMIT、BEAGLE、MUTANTXS、CXZ2014、BINSIM）工作額外處理了加殼的樣本。
對于處理函數的這些工作來說，最大的數據集來自GENIUS，它評估了從 8126 個固件中提取的 4.2 億個函數，其余工作均不超過五千萬。

評估方法

對方法的評估集中在魯棒性、準確性、可比性和性能上：

魯棒性：通過不同編譯器、不同編譯選項等方式來評估是否具備魯棒性。早期工作一般都沒有評估魯棒性，但后期工作都很重視。
準確性：大多數工作都使用基本事實對準確性進行定量評估，也有一小部分工作通過案例研究進行準確性評估。
可比性：比較很難，因為大多數工作的程序都不是公開可用的，數據集也是自定義的。但最近的工作越來越傾向于對外開放代碼和數據集。評價指標其實也難以進行衡量和比較。
性能：測量運行時性能很常見，有 49 個工作都完成了。

工作評估

比較類型

輸入比較

有 21 個工作是一對一、有 30 個工作是一對多、有 10 個是多對多。

可以通過一對一的方法擴展到一對多和多對多，但如果只是簡單應用在大量樣本上會遇到效率問題。提高匹配效率的一般做法就是從每個輸入中提取特征向量，使用特征向量間的相似度來代表樣本間的相似度。在特征向量的特征子集上添加索引，也可以減少比對次數。

比較方法

相似性比較有 42 個工作、等價性比較有 5 個工作、相同性比較有 2 個工作。

粒度

所有工作共有八個粒度：指令、指令集合、基本塊、基本塊集合、函數、函數集合、Trace、整個程序。

最常見的輸入粒度是函數（26 個工作），其次是整個程序（25 個工作）。
最常見的比較粒度是函數（30 個工作），其次是基本塊（20 個工作）。

語法相似

通過比較指令序列來判斷相似性。序列中的指令在虛擬地址空間中是連續的，并且屬于同一個函數。序列中的指令可以首先被規范化，例如僅保留操作碼或將操作數規范化等。

指令序列可以是固定或可變長度的。固定大小的序列是通過在指令流上滑動窗口獲得的，例如 n-gram、nperms 等。比較指令序列的方法主要是計算哈希、Embedding 和 Alignment：

6 個工作（BMAT、DR2005、SWPQS2006、SMIT、BINCLONE、SPAIN）使用哈希從可變長度指令序列中計算固定長度哈希。
5 個工作（IDEA、MBC、MUANTX-S、EXPOS′E、KAM1N0）通過 n-gram 序列生成 Embedding。
3 個工作（EXEDIFF、TRACY、BINSEQUENCE）使用 Alignment 通過在任一序列中插入 gap 來對齊兩個序列以生成它們之間的映射，解釋插入、刪除和修改的指令。

結構相似

常見方式是通過圖結構判斷結構相似性，最常見的圖是控制流圖（CFG）、過程間控制流圖（ICFG）和函數調用圖（CG）。在 CFG 和 ICFG 中，節點是基本塊，邊表示控制流跳轉。在 CG 中，節點是函數，邊表示調用關系。判斷圖相似的子圖同構是一個 NP 完全問題，其他方法如最大公共子圖同構也是一個 NP 完全問題，比較時需要減少比對的圖的數量和大小才能提高效率。

有 27 個工作采用了結構相似性判斷。其中，14 個工作只使用了 CFG、4 個工作只使用了 ICFG、2 個工作只使用了 CG。

語義相似

一共有 26 個計算語義相似度的工作，大部分在基本塊的粒度上捕獲語義，捕獲語義的三種基本方法是：指令分類、輸入輸出對、符號公式。

特征相似

有 28 個工作將二進制代碼表示為一個向量或者一組特征，確保相似的二進制代碼具有相似的特征向量，特征可以是布爾型、數值型或類別型。衡量特征相似通常使用 Jaccard 系數、位向量的點積以及數字向量的歐幾里得或余弦距離。

最近 Embedding 很火熱，有助于降低特征維度并增加特征向量的密度。下圖是兩種特征提取方式：

特別的，近五年來機器學習在該領域也得到了廣泛應用，可用于無監督相似聚類/分類等任務。

哈希

主要有三類哈希可用：密碼學哈希、局部敏感哈希和可執行文件哈希。共有 11 個工作使用了局部敏感哈希，其中 7 個都使用了 MinHash（BINHASH、MULTIMH、GENIUS、BINSEQUENCE、BINSHAPE、CACOMPARE、BINSIGN）。其他局部敏感哈希如 ssdeep、tlsh 等，所有的工作都沒有使用，有研究表明這些局部敏感哈希作用于整個程序的相似性效果會比部分內容的相似性更好，這可能和工作的預期目標不太相符。

架構

不同體系結構的代碼語法可能有很大不同，因為它們可能使用具有不同指令助記符、寄存器組和默認調用約定的單獨指令集。所有 16 個跨架構比較的工作都是在 2015 年以后提出的，主要有兩條技術路線：7 個工作選擇將二進制代碼提升為與體系結構無關的中間表示（IR），另外 9 個工作為每個架構設計獨立的模塊提取特征再判斷相似性。

分析類型

可以使用靜態分析、動態分析或兩者結合的方式進行分析。有 51 個工作只使用靜態分析，有 4 個工作只使用動態分析，有 6 個工作將二者結合使用。此外，也有工作使用污點分析與符號執行。

二進制代碼相似中的動態分析普遍用于惡意軟件脫殼（SMIT、BEAGLE、MUANTX-S、CXZ2014、BINSIM）、Trace 粒度跟蹤（BINSIM、KS2017）以及收集語義相似性的運行時值（BLEX、 BINSIM、IMF-SIM）。

規范化

在 33 個工作中使用了指令規范化，共有三種：操作數移除（9 個工作）、操作數規范化（17 個工作）、助記符歸一化（3 個工作）。

另一種規范化是刪除不影響語義的、編譯器添加的用于加載程序的函數、無法訪問的僵尸代碼等部分代碼。

工作思考

作者提出了以下幾點的思考，覺得可能是未來發展方向的突破點：

小塊二進制代碼。許多工作都忽略相對較小的二進制代碼，因為這些小塊二進制代碼會影響相似性的判斷，進一步結合上下文有可能對解決該問題有幫助。
源碼到二進制的相似性。可以用該方法確認某些二進制程序中是否存在開源代碼中的已知漏洞。
數據相似性。其實，程序同時包含代碼和數據，數據可能存儲在復雜的數據結構中。也許可以結合類型推斷來判斷數據結構的相似性。
語義關系。語義相似性的另一個路徑是識別具有相關函數的二進制代碼，例如加密或網絡通信函數。這是更有挑戰性的，因為功能相關的代碼可能沒有相同的語義。
可擴展性。程序、樣本、固件數量越來越多，二進制代碼相似性判斷的方案需要能夠具備極好的可擴展性，才能較好地應對數據爆炸。
混淆。混淆代碼的二進制代碼相似性仍然存在許多挑戰。例如 Themida 和 VMProtect 等基于虛擬化的加殼程序，就很難以處理。
方法比較。構建基準數據集和相同實驗條件下的獨立驗證是非常重要的。

二進制代碼相似分析有著廣泛的應用場景，但實際上現有的工作在解決實際問題時遇到了各種各樣的問題，仍然有待后人去開發研究效果更好的方案。對該方向感興趣的，可以進一步閱讀文章中提到的這些工作。