二進(jìn)制代碼相似性搜索研究進(jìn)展

夏 冰，龐建民，周 鑫，單 征

（1.數(shù)學(xué)工程與先進(jìn)計(jì)算國家重點(diǎn)實(shí)驗(yàn)室，鄭州 450001；2.中原工學(xué)院前沿信息技術(shù)研究院，鄭州 450007）

0 引言

隨著物聯(lián)網(wǎng)和工業(yè)互聯(lián)網(wǎng)的快速發(fā)展，無論是智能手機(jī)還是嵌入式設(shè)備，絕大多數(shù)軟件都是以二進(jìn)制代碼形式發(fā)布。為了快速開發(fā)產(chǎn)品，廠商使用開源軟件或通過代碼重用加速產(chǎn)品迭代，為不同操作系統(tǒng)和不同CPU 架構(gòu)，產(chǎn)生眾多可定制化且滿足客戶需求的固件鏡像文件。這種通過開源部署生成的二進(jìn)制固件程序在滿足客戶便利的同時(shí)，一旦固件鏡像文件引用的開源組件或底層系統(tǒng)被發(fā)現(xiàn)存在安全風(fēng)險(xiǎn)，會(huì)帶來巨大安全隱患。如現(xiàn)在仍未消除的OpenSSL（Open-source Secure Sockets Layer）漏洞因破壞性之大、影響范圍之廣，堪稱網(wǎng)絡(luò)安全里程碑事件。出于商業(yè)保護(hù)或其他技術(shù)原因，廠家通常并不對(duì)外提供源代碼。因此，在源代碼無法獲取或者獲取不便這一事實(shí)下，二進(jìn)制代碼分析成為工業(yè)界和學(xué)術(shù)界研究其安全問題的最佳方法，其研究話題和分析技術(shù)持續(xù)高漲。

由于代碼復(fù)用，同樣的代碼會(huì)出現(xiàn)在多個(gè)程序中，甚至出現(xiàn)在同一個(gè)程序的多個(gè)部分。一旦發(fā)現(xiàn)某個(gè)二進(jìn)制代碼存在bug，從眾多代碼中找到被使用的bug 代碼、相同的bug代碼或相似的bug 代碼，從而可大規(guī)模、快速且及時(shí)地發(fā)現(xiàn)bug 風(fēng)險(xiǎn)。這樣一來，采用相似性搜索技術(shù)發(fā)現(xiàn)網(wǎng)絡(luò)安全脆弱性為二進(jìn)制代碼安全分析提供一種新思路，其研究成果廣泛應(yīng)用在bug 搜索、惡意軟件分析檢測(cè)、補(bǔ)丁生成分析和軟件竊取檢測(cè)等方面。

本文首先介紹二進(jìn)制代碼相似性搜索體系架構(gòu)，給出二進(jìn)制代碼涉及的基本概念，詳細(xì)介紹二進(jìn)制代碼相似性搜索流程；其次，從二進(jìn)制代碼的語法、語義和語用相似性搜索角度，總結(jié)對(duì)比分析現(xiàn)有技術(shù)研究現(xiàn)狀；最后，給出二進(jìn)制代碼相似性搜索領(lǐng)域未來發(fā)展方向。

1 二進(jìn)制代碼相似性搜索體系架構(gòu)

1.1 二進(jìn)制代碼

二進(jìn)制代碼是指源代碼經(jīng)過編譯鏈接后，可被CPU 直接執(zhí)行的機(jī)器代碼。從源代碼到目標(biāo)程序大致需要經(jīng)歷編譯過程和鏈接過程。編譯過程主要是將程序源代碼作為輸入，選擇某種編譯器如GCC（GNU Compiler Collection）和優(yōu)化級(jí)別如-O0、-O1、-O2 后，編譯生成目標(biāo)文件。鏈接過程是將多個(gè)目標(biāo)文件鏈接在一起，生成被CPU 如x86、ARM（Advanced RISC Machine）等識(shí)別執(zhí)行的目標(biāo)程序、獨(dú)立可執(zhí)行程序或庫文件。如圖1 所示為源代碼編譯過程。

圖1 源代碼編譯過程Fig.1 Compilation process of program source code

二進(jìn)制代碼可以有不同表現(xiàn)形式，如：用十六進(jìn)制字符串形式表示原始字節(jié)，用IDA Pro（Interactive Disassembler Professional）工具將二進(jìn)制代碼反匯編后得到匯編指令序列，用LLVM（Low Level Virtual Machine）工具將其轉(zhuǎn)化為等價(jià)的中間語言IR（Intermediate Representation），用控制流圖（Control Flow Graph，CFG）表示功能調(diào)用關(guān)系等。本文將以x86 匯編指令為例，不包含文獻(xiàn)［42-43］中討論的類似Java 字節(jié)碼的操作，討論和二進(jìn)制代碼相似性搜索有關(guān)的指令、基本塊、程序流程圖等基本概念。

通常一條匯編指令由一個(gè)助記符或操作碼最多3 個(gè)操作數(shù)組成。操作碼表示指令的機(jī)器行為語義。每個(gè)操作數(shù)可以是一個(gè)參數(shù)（如寄存器、偏移量）或用于尋址的一組參數(shù)。如匯編指令MOV EAX，［ESP+8］，其中MOV 為操作碼，EAX 和［ESP+8］為操作數(shù)，EAX 和ESP 為寄存器，［ESP+8］為寄存器ESP 和偏移量8 共同組成的用于尋址的一組參數(shù)。

二進(jìn)制目標(biāo)文件通過反匯編后會(huì)生成多個(gè)二進(jìn)制函數(shù)。二進(jìn)制函數(shù)通常有若干個(gè)基本塊（Basic Block，BB）組成并在CFG 的作用下完成函數(shù)功能。一個(gè)二進(jìn)制函數(shù)的CFG 可以用一個(gè)二元組（

N

，

E

）描述，其中：

N

是有窮節(jié)點(diǎn)集合，每個(gè)節(jié)點(diǎn)表示函數(shù)內(nèi)一個(gè)基本塊；

E

是邊，表示基本塊之間的連接調(diào)用關(guān)系。

1.2 二進(jìn)制代碼相似性搜索流程

二進(jìn)制代碼相似性搜索通常以攜帶片段屬性（如代碼片段具有高危漏洞風(fēng)險(xiǎn)或惡意代碼調(diào)用風(fēng)險(xiǎn)）的代碼片段作為查詢條件，利用相似性技術(shù)從資源池中返回滿足查詢條件的代碼片段作為輸出。二進(jìn)制代碼相似性搜索是項(xiàng)系統(tǒng)工程，是多種技術(shù)的融合結(jié)果。具體來講二進(jìn)制代碼相似性搜索主要由代碼片段提取、代碼片段比較、資源池組成，如圖2所示。

圖2 二進(jìn)制代碼相似性搜索框架Fig.2 Framework of binary code similarity search

1.2.1 二進(jìn)制代碼片段提取

代碼片段大小和特定應(yīng)用場(chǎng)景有關(guān)，如要搜索的是文件、函數(shù)或者基本塊。這些片段具有某種特征或?qū)傩?，屬性可以是已知也可以是未知。片段可以來自同版本程序，如某個(gè)二進(jìn)制可執(zhí)行程序的兩個(gè)函數(shù)，也可以來自同程序的兩個(gè)版本，或者也可以來自兩個(gè)不同程序。

按照代碼片段提取的粗細(xì)粒度，從細(xì)到粗可以劃分為指令、一組相關(guān)的指令、基本塊、一組相關(guān)的基本塊、函數(shù)、一組相關(guān)的函數(shù)，路徑軌跡和整個(gè)程序。如文獻(xiàn)［44］采用一組相關(guān)的指令

K

-Gram 方案，文獻(xiàn)［8］采用共享某個(gè)屬性的指令Strand 方案。通過設(shè)置切片規(guī)則，提取的指令可以屬于不同的基本塊，甚至不同的函數(shù)。一組相關(guān)的基本塊由共享結(jié)構(gòu)屬性（如數(shù)據(jù)依賴關(guān)系、調(diào)用關(guān)系）的多個(gè)基本塊組成。這組基本塊可以隸屬相同的函數(shù)，也可以屬于不同的函數(shù)。相關(guān)函數(shù)是一個(gè)二進(jìn)制程序的組件，如一個(gè)庫組件、一個(gè)類組件或者一個(gè)模塊組件。路徑軌跡是指一條處理二進(jìn)制程序某個(gè)變量或參數(shù)的執(zhí)行路徑。

代碼片段提取后，通常有兩種方式得到代碼片段比較結(jié)果。一是，用細(xì)粒度比較后的統(tǒng)計(jì)結(jié)果來推導(dǎo)粗粒度比較結(jié)果，如文獻(xiàn)［8］的Strand 用細(xì)粒度的指令去分析粗粒度的基本塊或函數(shù)；二是，用細(xì)粒度特征累加推導(dǎo)粗粒度結(jié)果，如文獻(xiàn)［15］提出的Gemini 方案在基本塊上累加指令的特征，從而在函數(shù)粒度上產(chǎn)生特征向量實(shí)現(xiàn)函數(shù)間比較。

1.2.2 二進(jìn)制代碼片段比較

通常將比較結(jié)果分為相同（Identical）比較、等價(jià)（Equivalent）比較和相似性（Similar）比較。二進(jìn)制代碼相似性搜索關(guān)鍵在于代碼片段比較。

兩個(gè)二進(jìn)制代碼片段相同是指它們具有相同的語法表示。判斷二進(jìn)制片段是否相同最簡單的方式是采用哈希散列技術(shù)，如采用SHA（Secure Hash Algorithm）技術(shù)和MD5（Message Digest algorithm 5）技術(shù)來計(jì)算哈希值，就能夠?qū)崿F(xiàn)每個(gè)片段內(nèi)容是否相同的判斷。然而，這種簡單粗暴的方式對(duì)代碼片段要求特別苛刻，一旦某個(gè)細(xì)微變化都會(huì)產(chǎn)生巨大差異結(jié)果，甚至在原本相同的代碼上產(chǎn)生意想不到的后果。即使源代碼沒有改變，采用相同編譯器對(duì)同一源代碼進(jìn)行前后兩次編譯，產(chǎn)生的二進(jìn)制代碼也會(huì)發(fā)生變化。這是因?yàn)檫@些執(zhí)行文件加入了類似當(dāng)前編譯時(shí)間等實(shí)現(xiàn)自動(dòng)計(jì)算的動(dòng)態(tài)變化信息。

兩個(gè)二進(jìn)制代碼片段等價(jià)是指它們具有相同的語義，即它們具有相同功能或影響。兩個(gè)二進(jìn)制片段語義相等并不關(guān)心二進(jìn)制代碼的語法。盡管兩個(gè)相同的二進(jìn)制代碼片段具有相同的語義，但兩個(gè)不同的二進(jìn)制代碼片段也可能具有相同的語義。如“MOV EAX，0”和“XOR EAX，EAX”是語義相等的兩條x86 指令，功能都是設(shè)置寄存器EAX 的值為0。由于證明兩個(gè)程序是否功能相等是一個(gè)不可判定問題，因此判斷代碼相等需要付出高額代價(jià)。一種比較實(shí)際的方式是通過比較細(xì)粒度的二進(jìn)制代碼片段來實(shí)現(xiàn)等價(jià)判斷。如文獻(xiàn)［12］提出的XMATCH 方案，通過抽取基本塊中的條件表達(dá)式來判斷兩個(gè)基本塊的語義是否等價(jià)。

兩個(gè)二進(jìn)制代碼片段相似是指它們的語法、結(jié)構(gòu)或功能語義是相似的。語法相似性比較的是代碼字面表示。結(jié)構(gòu)相似性是指代碼片段用圖表示后，兩個(gè)圖結(jié)構(gòu)間是相似的，如代碼的CFG 或函數(shù)間調(diào)用圖。由于CFG 的點(diǎn)和邊可以攜帶更多語義信息，因此在某種程度上能捕獲代碼的語法表示和語義表示。語義相似性比較的是代碼功能。一種簡單的語義相似性比較方法是比較程序的交互行為是否相似，或者比較操作系統(tǒng)API（Application Programming Interface）調(diào)用或系統(tǒng)調(diào)用后程序環(huán)境是否相似。但是，兩個(gè)具有相同系統(tǒng)調(diào)用的程序卻可以實(shí)現(xiàn)截然不同的結(jié)果。因此，本文不考慮通過系統(tǒng)調(diào)用或利用操作系統(tǒng)API 和環(huán)境進(jìn)行交互的行為相似性比較這種動(dòng)態(tài)分析方法，而是關(guān)注靜態(tài)分析比較。

小結(jié)一下，二進(jìn)制代碼相同能夠推導(dǎo)出等價(jià)和相似，但是二進(jìn)制代碼相似不能推導(dǎo)出等價(jià)或相同。語義相似性比較對(duì)代碼語法轉(zhuǎn)變和代碼結(jié)構(gòu)變化不敏感，不足之處是如果比較的是較大代碼片段，則會(huì)帶來計(jì)算代價(jià)高的問題。

1.2.3 二進(jìn)制代碼資源池

軟件開發(fā)者依據(jù)客戶需求可以編譯生成符合任何目標(biāo)平臺(tái)架構(gòu)需要的二進(jìn)制程序，從而得到多個(gè)不同架構(gòu)的程序版本。這種情況下產(chǎn)生的二進(jìn)制程序因使用了不同的指令集，語法前后產(chǎn)生巨大變化。軟件開發(fā)者也可以利用混淆轉(zhuǎn)變技術(shù)，為一份相同源代碼產(chǎn)生多樣化的二進(jìn)制程序變種，然而變種后的語義功能卻沒有變化。因此，二進(jìn)制代碼相似性搜索要具有一定的魯棒性，要能夠處理資源池中不同平臺(tái)架構(gòu)的二進(jìn)制程序。

魯棒性是指代碼搜索方案在面臨代碼轉(zhuǎn)換場(chǎng)景時(shí)，如選擇不同編譯器和優(yōu)化選項(xiàng)、不同平臺(tái)架構(gòu)和混淆等，仍然能夠找到相似性的代碼。因此，依據(jù)代碼搜索的魯棒性來建設(shè)資源池，可將資源池中的二進(jìn)制代碼分為單平臺(tái)代碼如x86和跨平臺(tái)代碼如x86、ARM、MIPS（Million Instructions Per Second）。

由于跨平臺(tái)代碼語法差異很大，因此在比較上通常是計(jì)算語義相似性。當(dāng)前跨平臺(tái)解決方案采用兩種技術(shù)來實(shí)現(xiàn)。一是語法分析，先利用中間語言表示技術(shù)，把二進(jìn)制代碼提升到和平臺(tái)無關(guān)的中間語言表示上，然后在中間語言表示上完成相同的語法分析，這樣就實(shí)現(xiàn)了和原來平臺(tái)架構(gòu)無關(guān)，如文獻(xiàn)［10］提出的BinGo 方案和文獻(xiàn)［2］提出的FirmUp 方案。二是特征分析，為每一個(gè)平臺(tái)架構(gòu)設(shè)計(jì)單獨(dú)的模塊獲取特征向量，捕獲二進(jìn)制代碼的語義信息，利用監(jiān)督學(xué)習(xí)機(jī)制在跨平臺(tái)間打上標(biāo)簽，如來自同一份源代碼則表示相似標(biāo)記為1，否則標(biāo)記為0，然后將數(shù)據(jù)喂入模型訓(xùn)練從而得到分析模型，BinDNN 方案、INNEREYE 方案和SAFE 方案。

1.3 代碼轉(zhuǎn)換與相似性搜索

二進(jìn)制代碼相似性搜索本質(zhì)上仍然屬于程序逆向分析和應(yīng)用技術(shù)，因此需要解決高級(jí)語義丟失、編譯轉(zhuǎn)換和代碼混淆帶來的技術(shù)難題。源代碼經(jīng)過編譯處理后，使其原本豐富的程序語義信息丟失，如函數(shù)名、變量名、備注和數(shù)據(jù)結(jié)構(gòu)，從而為分析帶來挑戰(zhàn)性。

編譯轉(zhuǎn)換帶來的代碼變化主要是由于編譯過程使用了不同的編譯器，選擇了不同優(yōu)化選項(xiàng)，為不同操作系統(tǒng)和底層不同CPU 指令集平臺(tái)架構(gòu)生成的二進(jìn)制程序，這些都會(huì)導(dǎo)致二進(jìn)制代碼發(fā)生巨大變化。此外，為保護(hù)知識(shí)產(chǎn)權(quán)或增加程序逆向分析難度，代碼混淆轉(zhuǎn)變既可以發(fā)生在源代碼，也可以發(fā)生在二進(jìn)制代碼中，盡管語義保持不變，但是二進(jìn)制代碼的結(jié)構(gòu)或語法發(fā)生了變化，也給代碼相似性搜索提出挑戰(zhàn)。綜上所述，二進(jìn)制代碼相似性搜索主要面臨源代碼轉(zhuǎn)換和二進(jìn)制代碼轉(zhuǎn)換的挑戰(zhàn)，這二種轉(zhuǎn)換都不改變代碼語義。如圖3 所示為代碼轉(zhuǎn)換過程。

圖3 代碼轉(zhuǎn)換過程Fig.3 Process of code transform

源代碼轉(zhuǎn)換發(fā)生在編譯前，轉(zhuǎn)換前后的輸入和輸出都是源代碼，如將相同的軟件功能分別采用不同高級(jí)語言來實(shí)現(xiàn)。因此，源代碼轉(zhuǎn)換通常不考慮目標(biāo)平臺(tái)，只需要特定的程序語言編寫程序即可。

二進(jìn)制代碼轉(zhuǎn)換發(fā)生在編譯后，轉(zhuǎn)換前后的輸入和輸出都是二進(jìn)制。二進(jìn)制代碼轉(zhuǎn)換與采用的開發(fā)語言無關(guān)，嚴(yán)重依賴目標(biāo)平臺(tái)。二進(jìn)制代碼轉(zhuǎn)換后，代碼前后在語法上差異巨大，對(duì)相似性搜索提出嚴(yán)峻挑戰(zhàn)。

1.4 討論與小結(jié)

二進(jìn)制代碼相似性搜索需要比較兩個(gè)或多個(gè)二進(jìn)制代碼片段。對(duì)兩個(gè)以上片段的比較方法，通常是采取一個(gè)片段和剩余片段的比較，或片段之間彼此比較來實(shí)現(xiàn)。這樣一來，基于比較數(shù)目，二進(jìn)制代碼相似性搜索結(jié)果可分成一對(duì)一類型、一對(duì)多類型、多對(duì)多類型。多數(shù)一對(duì)一類型實(shí)現(xiàn)二進(jìn)制代碼差異進(jìn)化問題，如區(qū)分同一程序的兩個(gè)連續(xù)版本，識(shí)別目標(biāo)版本中增加、刪除、修改的內(nèi)容。多數(shù)一對(duì)多類型實(shí)現(xiàn)的是二進(jìn)制代碼相似性搜索問題。例如搜索一個(gè)查詢片段是否和目標(biāo)片段中相似，然后返回Top

K

個(gè)最相似的目標(biāo)片段。多對(duì)多類型典型應(yīng)用場(chǎng)景是二進(jìn)制代碼片段集群識(shí)別，如惡意代碼聚類分析中，將兩兩比較相似的識(shí)別為同類。

由于語義相似性聚焦在相似的行為影響或功能等價(jià)上，因此可有效應(yīng)對(duì)源代碼轉(zhuǎn)換和二進(jìn)制代碼轉(zhuǎn)換的挑戰(zhàn)。為了系統(tǒng)描述研究現(xiàn)狀，本文將從二進(jìn)制代碼語法、二進(jìn)制代碼語義和二進(jìn)制代碼語用三個(gè)角度介紹。

2 基于語法的二進(jìn)制代碼相似性搜索

基于語法的代碼搜索是指在代碼片段比較的時(shí)候，比較的是代碼字面表示。主要包括基于哈希、指令序列和CFG 的代碼搜索技術(shù)。

2.1 基于哈希的搜索技術(shù)

將哈希技術(shù)應(yīng)用到原始字節(jié)的比較上，可以提高搜索效率，快速區(qū)分是否在細(xì)粒度上發(fā)生代碼復(fù)用。哈希實(shí)現(xiàn)的是相同，而不是相似的輸入。哈希值壓縮后便于存儲(chǔ)和計(jì)算，比較效率高，從而多用于檢索?；诠５乃阉骷夹g(shù)主要包括局部敏感哈希、模糊哈希和可執(zhí)行文件哈希。

2.1.1 局部敏感哈希

局部敏感哈希（Locality-Sensitive Hashing，LSH）思想是相似的輸入產(chǎn)生相似的哈希值。具體來講，將待比較的兩個(gè)代碼原始字節(jié)集合分成了多個(gè)較小子集合，對(duì)每個(gè)子集合中的數(shù)據(jù)施加哈希計(jì)算，最后統(tǒng)計(jì)相同哈希值的數(shù)量。相同數(shù)量越多，相似性越高。

文獻(xiàn)［50］抽取二進(jìn)制文件數(shù)據(jù)段中的ASCII（American Standard Code for Information Interchange）格式字符串、代碼段中的ASCII 格式字符串和數(shù)據(jù)段中的Unicode 字符串，組合得到可讀字符串序列，借助深度學(xué)習(xí)編碼可讀字符串，隨后對(duì)編碼向量施加LSH 計(jì)算從而實(shí)現(xiàn)快速檢索。

Gemini 方案引入屬性控制流程圖（Attributed CFG，ACFG），借助Structure2vec 技術(shù)生成圖嵌入向量，然后利用LSH 計(jì)算每個(gè)嵌入向量的哈希值，并存入到數(shù)據(jù)庫。為了從數(shù)據(jù)庫中搜索識(shí)別一組與查詢函數(shù)相似的二進(jìn)制代碼函數(shù)，只需要哈希計(jì)算查詢函數(shù)嵌入向量，從而實(shí)現(xiàn)函數(shù)的快速搜索。

文獻(xiàn)［51］將SimHASH 哈希技術(shù)應(yīng)用到函數(shù)相似性檢測(cè)中，依據(jù)函數(shù)中代碼塊的SimHASH 值快速發(fā)現(xiàn)相似代碼塊。文獻(xiàn)［52］提出的BinHASH 方案將函數(shù)表示為一組行為特征集合，利用輸入輸出分析獲得基本塊內(nèi)的行為，如內(nèi)存操作行為、寄存器操作行為，然后將這些行為特征施加最小哈希MinHASH 運(yùn)算，從而在大規(guī)模函數(shù)中實(shí)現(xiàn)聚類分析。

文獻(xiàn)［53］提出的Kam1n0 方案認(rèn)為現(xiàn)有哈希技術(shù)不能很好地處理分布不均勻的數(shù)據(jù)，認(rèn)為：基本塊越小，相似性越高；基本塊越大，向量空間呈稀疏分布，相似性越低。因此，在LSH 的基礎(chǔ)上，提出了一種新的自適應(yīng)局部敏感哈希（Adaptive LSH，ALSH）算法，該算法對(duì)于稠密區(qū)域可以得到較少的點(diǎn)，對(duì)于稀疏區(qū)域可以得到較多的點(diǎn)，并證明性能等效近鄰搜索。

2.1.2 模糊哈希

模糊哈希主要原理是依據(jù)分片條件對(duì)文件進(jìn)行分片，使用一個(gè)弱哈希計(jì)算文件局部內(nèi)容，使用一個(gè)強(qiáng)哈希對(duì)文件分片計(jì)算哈希值，并與分片條件一起構(gòu)成一個(gè)模糊哈希結(jié)果，最后使用一個(gè)字符串相似性對(duì)比算法來判斷兩個(gè)模糊哈希值的相似度是多少，從而判斷兩個(gè)文件的相似程度。模糊哈希算法多用于文件級(jí)別的相似性比較。

文獻(xiàn)［54］提出的Ssdeep 方案認(rèn)為同源文件以相同的順序共享相同的位集（sets of bits），因此，通過使用滾動(dòng)方式獲得數(shù)據(jù)的邊界，提出一種上下文觸發(fā)的分段散列（Context-Triggered Piecewise Hashing，CTPH）算法。這種散列可以用來識(shí)別未知輸入和已知文件之間的有序同源序列，當(dāng)文件的部分變化發(fā)生時(shí)，如修改、增加、刪除等操作，使用Ssdeep 均能發(fā)現(xiàn)與源文件的相似關(guān)系。這是因?yàn)槟：２粌H捕捉二進(jìn)制代碼相似性，也捕捉了可執(zhí)行文件中數(shù)據(jù)的相似性。文獻(xiàn)［55］的結(jié)果證實(shí)，模糊哈希能夠識(shí)別具有共同代碼或庫程序之間的相似性。他們發(fā)現(xiàn)即使相同的源代碼在編譯的時(shí)候采用不同編譯優(yōu)化選項(xiàng)，可執(zhí)行文件的數(shù)據(jù)部分仍然相同，這對(duì)數(shù)據(jù)相似性分析引入到二進(jìn)制代碼相似性搜索中具有指導(dǎo)意義。類似的實(shí)現(xiàn)方案還有TLSH（Trend LSH）方案、nextGen-hash 方案和BitShred 方案。

2.1.3 可執(zhí)行文件哈希

可執(zhí)行文件哈希把一個(gè)可執(zhí)行文件作為輸入，在進(jìn)行哈希計(jì)算時(shí)使用的輸入僅僅是可執(zhí)行文件部分內(nèi)容，如導(dǎo)入表或者文件頭，這在惡意軟件變種相似性比較非常有用。變異的惡意文件如果采用簡單的二次加殼，或者混淆變化小，那么文件內(nèi)容很少會(huì)發(fā)生變化，這樣一來，將可執(zhí)行文件哈希用于比較分析惡意文件的多個(gè)變種時(shí)，能產(chǎn)生多個(gè)相同的哈希值。

文獻(xiàn)［59］提出的peHash方案對(duì)一個(gè)PE（Portable Executable）可執(zhí)行文件，選擇在編譯和加殼過程中很少發(fā)生變化的區(qū)域上進(jìn)行哈希計(jì)算，如初始化棧大小、堆大小。文獻(xiàn)［60］提出的ImpHash 方案認(rèn)為加殼變種后功能是一樣的，則認(rèn)為導(dǎo)入表同樣也是一樣，因此在計(jì)算的時(shí)候僅僅對(duì)導(dǎo)入表進(jìn)行哈希計(jì)算。由于惡意代碼在加殼過程中加入一些不相關(guān)可執(zhí)行文件，并重構(gòu)導(dǎo)入表，從而造成錯(cuò)誤率很高。

2.1.4 討論與小結(jié)

哈希技術(shù)能夠感知代碼細(xì)微變化，檢索匹配效率高，不足之處在于錯(cuò)誤率高。從方案名稱、實(shí)現(xiàn)、優(yōu)點(diǎn)、不足四個(gè)角度總結(jié)基于哈希的搜索技術(shù)如表1 所示。

表1 基于哈希的二進(jìn)制代碼相似性搜索方案間比較Tab 1 Comparison of binary code similarity search schemes based on hash

2.2 基于指令序列的搜索技術(shù)

指令序列通常是指函數(shù)中的指令在空間上是按照線性連續(xù)地排列。指令序列在比較時(shí)需要指令歸一化，歸一化主要包括操作碼歸一化和操作數(shù)歸一化。文獻(xiàn)［61］提出的BinClone 方案采用操作數(shù)歸一化，將常量用VAL 符號(hào)代替，內(nèi)存地址用MEM 符號(hào)代替、寄存器用REG 符號(hào)代替。與BinClone 不同的是，文獻(xiàn)［11］提出的BinSequence 方案將常量分為內(nèi)存偏離量和立即數(shù)。文獻(xiàn)［45］采用操作碼符歸一化，將操作碼區(qū)分為邏輯計(jì)算、數(shù)據(jù)傳輸、棧操作、數(shù)學(xué)運(yùn)算、函數(shù)調(diào)用、地址操作等類別。由于指令是代碼搜索最基本的組成單位，因此通常將指令比較的結(jié)果作為相似性搜索的前提。典型的指令比較主要包括

N

-Gram、

N

-Perm、指令哈希和指令對(duì)齊方式。2.2.1

N

-Gram指令序列可定長也可變長。定長指令序列通過運(yùn)用滑動(dòng)窗口大小或步長來實(shí)現(xiàn)?；瑒?dòng)窗口大小也就是指令序列中指令的數(shù)量，步長是指從窗口開始處開始滑動(dòng)的指令個(gè)數(shù)。當(dāng)步長小于滑動(dòng)窗口大小時(shí)，連續(xù)序列重疊。當(dāng)步長為

n

時(shí)，產(chǎn)生的序列稱之為

N

-Gram。例如，給定一個(gè)指令助記符序列｛MOV，SUB，ADD｝，當(dāng)

N

=2 時(shí)，指令助記符序列會(huì)得到｛MOV，SUB｝和｛SUB，ADD｝兩個(gè)指令序列。Rendezvous 方案、Kam1n0 方案以及ILINE 方案在各自的系統(tǒng)中都采用了

N

-Gram 作為相似性比較的方法。2.2.2

N

-Perm

N

-Perm 是指不考慮順序的

N

-Gram 方案，這種方法能夠捕獲序列中的指令重新排序狀況。由于不考慮指令順序，因此一個(gè)

N

-Perm 指令序列會(huì)產(chǎn)生多個(gè)

N

-Gram。如2-Perm 的｛MOV，PUSH｝會(huì)產(chǎn)生2-Gram 的｛MOV，PUSH｝和｛PUSH，MOV｝。文獻(xiàn)［45］表明將

N

-Germ 用于軟件指紋比較時(shí)，

N

取值為4 或5 的時(shí)候，相似性比較的可信度較高。

2.2.3 指令哈希

指令哈希是指從一個(gè)變長的指令序列中得到固定長度個(gè)數(shù)的指令序列后，運(yùn)用哈希計(jì)算，如果兩者之間哈希值一樣，則認(rèn)為序列相似，如SMIT（Symantec Malware Indexing Tree）方案、BinClone方案以 及SPAIN（Security Patch Analysis for bINary）方案。

2.2.4 指令對(duì)齊

TRACY 方案采用指令對(duì)齊方式，從CFG 上抽取連續(xù)的固定個(gè)數(shù)的基本塊形成Trace，對(duì)齊基本塊后對(duì)基本塊內(nèi)部采用指令序列對(duì)齊方式，這樣就可以在兩個(gè)序列之間產(chǎn)生一個(gè)映射。指令對(duì)齊時(shí)候定義一個(gè)相似度分值，指令和空對(duì)齊的時(shí)候定義一個(gè)空分值。如果Trace 間相似度超過閾值

a

，認(rèn)為兩個(gè)Trace 相似，并計(jì)入Trace 相似總數(shù)。接著，計(jì)算所有相似性Trace 匹配結(jié)果的覆蓋率，從而得到一個(gè)覆蓋值。設(shè)置閾值

b

，如果覆蓋值超過閾值

b

，則認(rèn)定兩個(gè)函數(shù)相似。

2.2.5 討論與小結(jié)

指令作為代碼分析最重要的組成部分，在實(shí)現(xiàn)代碼搜索方案中通常是將其作為方案預(yù)處理部分。如指令預(yù)處理后喂入詞向量訓(xùn)練模型從而進(jìn)行后期基本塊或者圖的比較搜索。由于指令優(yōu)化和體系架構(gòu)的差異，指令數(shù)量龐大且變化多通常超出字典范疇，因此需要進(jìn)行歸一化處理。指令歸一化后會(huì)造成指令精確語義的缺失，進(jìn)而會(huì)影響語義比較。如何識(shí)別指令語義細(xì)微差異，并對(duì)其指令序列進(jìn)行精確表示學(xué)習(xí)是代碼分析的一項(xiàng)基礎(chǔ)工作?；谥噶钚蛄械亩M(jìn)制代碼相似性搜索方案間的比較結(jié)果如表2 所示。

表2 基于指令序列的二進(jìn)制代碼相似性搜索方案間比較Tab 2 Comparison of binary code similarity search schemes based on instruction sequence

2.3 基于圖結(jié)構(gòu)的搜索技術(shù)

代碼片段的控制結(jié)構(gòu)可以抽象成圖來表示，二進(jìn)制代碼用圖表示后，代碼相似性計(jì)算問題就轉(zhuǎn)換為圖相似性比較問題。圖結(jié)構(gòu)的穩(wěn)定性，以及圖中節(jié)點(diǎn)和邊都可以攜帶更多的語義信息，使其在搜索效果上具有更強(qiáng)的魯棒性。

二進(jìn)制代碼有三種有向圖表示方式：函數(shù)內(nèi)部CFG、函數(shù)間CFG（Inter-Procedural CFG，ICFG）和程序調(diào)用圖（Call Graph，CG）。由上面分析可知，每個(gè)函數(shù)都有自己的CFG。CFG 和ICFG 節(jié)點(diǎn)是基本塊，邊表示控制流轉(zhuǎn)移如分支或跳轉(zhuǎn)，不同之處在于CFG 節(jié)點(diǎn)位于于同一函數(shù)內(nèi)，ICFG 節(jié)點(diǎn)屬于程序內(nèi)任一函數(shù)。CG 的節(jié)點(diǎn)不是基本塊，而是函數(shù)，邊表示函數(shù)間的調(diào)用者與被調(diào)用者關(guān)系。

三種有向圖的輸入是不同的。CG 或ICFG 以整個(gè)二進(jìn)制程序或文件作為輸入，基于CFG 的方法是以二進(jìn)制函數(shù)作為輸入。多數(shù)方案不在圖上進(jìn)行二次加工。如文獻(xiàn)［62］采用CG 方式，文獻(xiàn)［63］采用CFG 方式，文獻(xiàn)［64］采用ICFG方式。

有些方案賦予圖更多的語義信息。Genius 方案和Gemini 方案融入基本塊的統(tǒng)計(jì)屬性，文獻(xiàn)［23］融入邊的屬性，把CFG 中的邊標(biāo)記為控制流轉(zhuǎn)移類型。SIGMA（Semantic Integrated Graph Matching Approach）方案融入圖的屬性，提出一種包含CFG、CG 和寄存器流程圖的語義集成圖。文獻(xiàn)［66］融合CFG 調(diào)用的內(nèi)聯(lián)函數(shù)和庫函數(shù)，提出執(zhí)行依賴圖（Execution Dependence Graph，EDG）。文獻(xiàn)［67］使用指令依賴關(guān)系圖（Reductive Instruction Dependent Graph，RIDG），認(rèn)為雖然指令的順序發(fā)生了變化，但指令之間的依賴關(guān)系圖卻保持不變。這意味著指令依賴關(guān)系圖具有天然抗指令重排序的特性，因此引入RIDG 實(shí)現(xiàn)一種通用且抗混淆的二進(jìn)制程序相似性分析。

當(dāng)前基于圖結(jié)構(gòu)的搜索技術(shù)主要包括圖相似性比較、路徑相似性比較和圖嵌入向量相似性比較。

2.3.1 圖相似性比較

由于圖同構(gòu)要求圖中所有節(jié)點(diǎn)要相同，比較代價(jià)較高，因此當(dāng)前二進(jìn)制代碼比較通常是采用子最大公共子圖同構(gòu)，即找到兩個(gè)圖中的最大同構(gòu)子圖。為了減少圖比較對(duì)的數(shù)目以及圖大小，文獻(xiàn)［62］對(duì)相同簽名的CFG 和差異較大CFG不進(jìn)行比較，iBinHunt 方案只比較具有相同污點(diǎn)標(biāo)簽的節(jié)點(diǎn)。SMIT 方案和BinSlayer 方案把圖相似度模型歸結(jié)為圖優(yōu)化問題。SMIT 利用制高點(diǎn)樹（Vantage Point Tree，VPT）技術(shù)將搜索問題轉(zhuǎn)換為近鄰搜索，BinSlayer 利用匈牙利算法（Hungarian Algorithm，HA）加快搜索速度。文獻(xiàn)［22］采用子圖匹配的方案，其基本思想是把函數(shù)CFG 圖分割成多個(gè)子圖，為每個(gè)子圖產(chǎn)生一個(gè)指紋，通過統(tǒng)計(jì)子圖指紋匹配數(shù)量來確定兩個(gè)圖之間的相似度。

2.3.2 路徑相似性比較

CoP 方案和BinSequence 方案把函數(shù)相似性轉(zhuǎn)換為路徑相似性比較。CoP 利用符號(hào)執(zhí)行和證明理論，計(jì)算基本塊中的語義等價(jià)最長公共序列，作為路徑上的基本比較元素。BinSequence 為提高搜索速度，采用兩個(gè)過濾器，過濾掉基本塊數(shù)量和函數(shù)指紋差距大的函數(shù)，借助近鄰搜索技術(shù)得到CFG 上的最長執(zhí)行路徑，接著在兩個(gè)函數(shù)之間建立基本塊映射關(guān)系并計(jì)算兩兩之間的相似性度量值。路徑相似性比較優(yōu)勢(shì)在于路徑全覆蓋，通過統(tǒng)計(jì)的方式來獲得度量值。最大的不足在于：如果函數(shù)CFG 頂點(diǎn)過少，則在小片段比較上不具有優(yōu)勢(shì)；如果函數(shù)CFG 過大，在計(jì)算效率上會(huì)受到影響。

2.3.3 圖嵌入向量相似性比較

文獻(xiàn)［15］提出一種基于圖嵌入的相似性解決方案。利用統(tǒng)計(jì)方法得到基本塊的向量表示，將二進(jìn)制函數(shù)的CFG 表示為具有向量值的屬性CFG（ACFG），然后利用Structure2vec實(shí)現(xiàn)圖嵌入，接著將兩個(gè)圖嵌入向量送入孿生神經(jīng)網(wǎng)絡(luò)，從而實(shí)現(xiàn)相似性比較。

VulSeeker方案首先構(gòu)建標(biāo)簽語義流圖（Labeled Semantic Flow Graph，LSFG）；然后提取每個(gè)基本塊的特征向量，利用DNN（Deep Neural Network）模型生成函數(shù)圖嵌入；最后計(jì)算余弦距離得到相似度。文獻(xiàn)［70］認(rèn)為CFG 節(jié)點(diǎn)的順序?qū)τ趫D相似度檢測(cè)很重要，因此融入語義感知、結(jié)構(gòu)感知、順序感知等信息，使用BERT（Bidirectional Encoder Representations from Transformers）預(yù)訓(xùn)練模型提取語義信息，并使用卷積神經(jīng)網(wǎng)絡(luò)（Convolutional Neural Network，CNN）模型提取節(jié)點(diǎn)順序信息。

2.3.4 討論與小結(jié)

由于搜索的二進(jìn)制代碼片段可以用圖來表示，因此在二進(jìn)制相似性搜索中通過成熟的圖比較技術(shù)來實(shí)現(xiàn)不失為一種解決方案?；趫D結(jié)構(gòu)的二進(jìn)制代碼相似性搜索方案間的比較如表3 所示。

表3 基于圖結(jié)構(gòu)的二進(jìn)制代碼相似性搜索方案間比較Tab 3 Comparison of binary code similarity search schemes based on graph structure

2.4 小結(jié)

基于語法的二進(jìn)制代碼相似性搜索是指在代碼片段比較的時(shí)候，比較的是代碼字面表示，主要包括基于哈希、指令序列和CFG 的代碼搜索技術(shù)。哈希技術(shù)能夠感知代碼細(xì)微變化，檢索匹配效率高；不足之處在于錯(cuò)誤率高。指令作為代碼分析最重要的組成部分，在實(shí)現(xiàn)代碼搜索方案中通常是將其作為方案預(yù)處理部分。圖結(jié)構(gòu)的搜索技術(shù)比較的是代碼片段圖表示后的相似度，由于圖中節(jié)點(diǎn)和邊都可以攜帶更多的語義信息，從而使得相似的代碼結(jié)構(gòu)變化較小，在搜索效果上具有更強(qiáng)魯棒性。表4 總結(jié)了基于語法的二進(jìn)制代碼相似性搜索方案異同。

表4 基于語法的二進(jìn)制代碼相似性搜索方案間比較Tab 4 Comparison of binary code similarity search schemes based on grammar

3 基于語義的二進(jìn)制代碼相似性搜索

由前面分析可知，更精確的語義相似性比較應(yīng)該聚焦在和語法無關(guān)的代碼行為語義比較上，當(dāng)前主要包括基本塊語義比較和特征語義比較。

3.1 基于基本塊語義的搜索技術(shù)

由于基本塊中指令是線序表示，不包含任何控制流，便于數(shù)據(jù)流分析，因此多數(shù)方案都是從基本塊粒度實(shí)現(xiàn)語義比較。核心基本思想是如果兩個(gè)基本塊具有相似的影響如更新某個(gè)寄存器或內(nèi)存中的內(nèi)容，則認(rèn)為兩代碼片段之間語義相似?；緣K語義可通過輸入輸出行為和符號(hào)公式兩種方式獲取。

3.1.1 輸入輸出行為

給定相同的輸入如果能夠產(chǎn)生相同的輸出，則認(rèn)為二進(jìn)制代碼片段在功能上是相等的。語義信息抽取出來后，統(tǒng)計(jì)相等的結(jié)果占比，依據(jù)占比結(jié)果是否達(dá)到閾值進(jìn)而判定函數(shù)相等或者不相等。

文獻(xiàn)［52］認(rèn)為二進(jìn)制代碼片段相似當(dāng)且僅當(dāng)代碼在機(jī)器狀態(tài)上具有相同的影響，因此從寄存器、內(nèi)存、函數(shù)調(diào)用參數(shù)、跳轉(zhuǎn)條件4 個(gè)角度構(gòu)建基本塊的輸入輸出行為模型。文獻(xiàn)［10］將機(jī)器狀態(tài)定義成由內(nèi)存、通用寄存器和條件標(biāo)志組成的三元組，然后在執(zhí)行路徑上獲得執(zhí)行前后符號(hào)表達(dá)式，利用文獻(xiàn)［6］提出的輸入輸出隨機(jī)產(chǎn)生樣本和約束求解技術(shù)，進(jìn)而比較執(zhí)行前后符號(hào)表達(dá)式產(chǎn)生的語義是否等價(jià)。

文獻(xiàn)［72］遍歷CFG，識(shí)別函數(shù)執(zhí)行過程用到的參數(shù)，通過函數(shù)的多路交換語句識(shí)別出所有的間接調(diào)轉(zhuǎn)地址，然后選擇一個(gè)隨機(jī)值作為輸入來產(chǎn)生語義簽名，最后比較簽名值來進(jìn)行相似性度量。文獻(xiàn)［34-35，73］提出的方案均將相同的輸入送入到基本塊中并執(zhí)行，然后比較代碼執(zhí)行后的輸出是否相等。相同輸入的比較優(yōu)勢(shì)在于處理流程可能需要多次，依據(jù)測(cè)試多種可能的輸入輸出結(jié)果進(jìn)而判定兩個(gè)片段是否相等。如果任一個(gè)輸入產(chǎn)生的輸出不同，則兩個(gè)片段不相等。這對(duì)一些不重要的二進(jìn)制片段來講是不切合實(shí)際的。

綜上可知，這種輸入輸出比較方法，比較的是代碼執(zhí)行后的最終狀態(tài)，由于忽略了代碼中間狀態(tài)，因此該方法得到的語義相等和代碼表示無關(guān)。輸入輸出行為實(shí)現(xiàn)方案最大的優(yōu)勢(shì)是能夠證明語義相等，但是不足之處也很明顯，即需要滿足所有輸入這一約束條件，一旦一個(gè)輸入產(chǎn)生的輸出結(jié)果不同，則認(rèn)為基本塊不相等。

3.1.2 符號(hào)公式

符號(hào)公式是一個(gè)賦值語句，等號(hào)左邊是輸出變量，等號(hào)右邊是輸入變量和實(shí)現(xiàn)輸出變量的邏輯表達(dá)式。如指令A(yù)DD EAX，EBX，用符號(hào)公式可表示為EAX2=EAX1+EBX，其中EAX2 和EAX1 分別表示指令執(zhí)行前后EAX 寄存器的值。為了便于符號(hào)公式化，該方案需要對(duì)各類指令操作規(guī)范化，如使用通用寄存器類型表示任意類型的寄存器。符號(hào)公式抽取出來后，可采用定理證明器、哈希和圖距離三種方法進(jìn)行符號(hào)執(zhí)行后的結(jié)果比較。

iBinHunt為基本塊中的每個(gè)寄存器和內(nèi)存變量都產(chǎn)生一個(gè)符號(hào)表達(dá)式，然后基于定理證明器來檢查兩個(gè)符號(hào)公式是否相等。方案假設(shè)輸入變量共享相同的值，符號(hào)公式執(zhí)行后如果輸出變量具有相同的值，則兩個(gè)符號(hào)公式相等。通常一個(gè)基本塊有多個(gè)寄存器和內(nèi)存變量組成，這樣會(huì)生成多個(gè)輸出，由于每一個(gè)輸出都需要單獨(dú)的符號(hào)公式，因此iBinHunt 須實(shí)現(xiàn)多對(duì)輸入輸出結(jié)果間的比較。XMATCH 方案、Expose 方案和BinSim 方案則采用從系統(tǒng)調(diào)用參數(shù)的執(zhí)行路徑軌跡上抽取符號(hào)公式，然后利用定理證明器方案進(jìn)行相等驗(yàn)證。基于定理證明器方法能夠?qū)崿F(xiàn)代碼片段的相等比較，不足在于計(jì)算代價(jià)高，符號(hào)公式越長搜索比較時(shí)間越長，受到定理證明器的約束。

語義哈希是檢查兩個(gè)符號(hào)表達(dá)式是否具有相同的哈希。如果兩個(gè)符號(hào)公式具有相同的哈希值則認(rèn)為它們是相等的。BinHASH 方案將內(nèi)存操作行為、寄存器操作行為用符號(hào)公式表示后，利用最小哈希技術(shù)計(jì)算符號(hào)公式的哈希值。GitZ 方案將不同平臺(tái)的指令轉(zhuǎn)換到中間語言后，抽取基本塊中數(shù)據(jù)依賴的相關(guān)指令并符號(hào)化為公式，利用MD5 技術(shù)生成語義哈希。語義哈希盡管效率高，仍存在兩個(gè)本來相等的公式在歸一化和簡化后會(huì)具有不同哈希值，如指令重新排序會(huì)引起符號(hào)公式中的符號(hào)項(xiàng)發(fā)生變化，從而產(chǎn)生不同的哈希值。

XMATCH方案和TEDEM（Tree Edit Distance based Equational Matching）方案把一個(gè)基本塊的符號(hào)公式表示為一個(gè)樹，通過樹/圖編輯距離計(jì)算相似性。圖編輯距離的計(jì)算代價(jià)要比語義哈希高，但是卻能處理符號(hào)重新排序帶來的問題。

3.1.3 討論與小結(jié)

由于基本塊不包含控制信息且計(jì)算代價(jià)較小，因此在二進(jìn)制相似性搜索通常從基本塊提取語義信息進(jìn)行比較。基于基本塊語義的二進(jìn)制代碼相似性搜索技術(shù)間比較結(jié)果如表5 所示。

表5 基于基本塊語義的二進(jìn)制代碼相似性搜索技術(shù)間比較Tab 5 Comparison of binary code similarity search schemes based on basic block semantics

3.2 基于特征語義的搜索技術(shù)

由于二進(jìn)制代碼的語法、語義或結(jié)構(gòu)屬性都可以表示為特征，這樣二進(jìn)制代碼片段間的比較就轉(zhuǎn)變?yōu)樘卣飨蛄康谋容^。

3.2.1 嵌入比較

Genius 方案首次使用圖嵌入實(shí)現(xiàn)二進(jìn)制代碼相似性分析，將基本塊中的統(tǒng)計(jì)屬性和結(jié)構(gòu)屬性編碼為向量。Gemini 沿用Genius 思路，增加Structure2vec 模型得到圖嵌入向量。借助自然語言處理技術(shù)如Word2vec、Doc2vec實(shí)現(xiàn)語義相似度比較，不少方案從圖和基本塊的研究轉(zhuǎn)移到指令上和原始字節(jié)上。文獻(xiàn)［78］的方案和INNEREYE 方案把指令看作單詞，基本塊看作句子，CFG 看作有多個(gè)基本塊組成的段落；SAFE 方案使用Word2vec 方法生成函數(shù)嵌入；ASM2VEC則采用Doc2vec 形成路徑嵌入，綜合函數(shù)中的不同路徑嵌入成一個(gè)向量；αDiff 方案認(rèn)為文獻(xiàn)［8，10，15］方案提取的特征存在偏見，因此直接對(duì)函數(shù)上的原始字節(jié)序列進(jìn)行編碼從而生成函數(shù)嵌入，該方案僅僅解決了不同版本之間的原始字節(jié)粒度的檢測(cè)，并沒有實(shí)現(xiàn)函數(shù)粒度的檢測(cè)。

3.2.2 機(jī)器學(xué)習(xí)比較

通過比較機(jī)器學(xué)習(xí)得到的分類結(jié)果或預(yù)測(cè)結(jié)果，也可以實(shí)現(xiàn)二進(jìn)制代碼相似性比較。BinDNN將相似性比較定義為一個(gè)二分類任務(wù)，采用神經(jīng)網(wǎng)絡(luò)分類器去判定兩個(gè)來自相同源代碼的不同編譯函數(shù)是否相似。ZeeK 方案將二進(jìn)制函數(shù)中的每個(gè)基本塊分割成多個(gè)串（strand），使用文獻(xiàn)［13］中的方法將每一個(gè)串進(jìn)行歸一化和標(biāo)準(zhǔn)化，之后采用MD5哈希這些標(biāo)準(zhǔn)化表示轉(zhuǎn)換成一個(gè)類似one-hot 的稀疏向量。這樣，每個(gè)函數(shù)轉(zhuǎn)換成向量之后，利用全連接網(wǎng)絡(luò)判定兩個(gè)函數(shù)是否屬于同一類。Zeek 沒有考慮函數(shù)之間的調(diào)用信息，串的分割損失串內(nèi)部的信息以及串之間的控制流程信息。文獻(xiàn)［73］在匯編指令級(jí)上捕獲trace 內(nèi)的程序行為集合并編碼為向量后，采用基于樹的機(jī)器學(xué)習(xí)模型來預(yù)測(cè)兩個(gè)函數(shù)相似概率值。

有學(xué)者將基于神經(jīng)網(wǎng)絡(luò)技術(shù)應(yīng)用到跨平臺(tái)二進(jìn)制代碼相似性搜索上。VDNS（Vulnerability Detection based on Neural network and Structures matching）方案以函數(shù)為最小關(guān)聯(lián)單元，對(duì)函數(shù)間調(diào)用圖ICFG、函數(shù)內(nèi)CFG、函數(shù)基本信息進(jìn)行特征選擇和特征編碼，然后利用反向傳播神經(jīng)網(wǎng)絡(luò)計(jì)算函數(shù)相似度。文獻(xiàn)［50］認(rèn)為不同編譯配置下編譯而生成的多個(gè)同源二進(jìn)制文件中，可讀字符串的內(nèi)容和順序基本保持一致，基于這種可讀字符串的編譯不變性，提出一種基于雙層雙向門控循環(huán)單元（Gated Recurrent Unit，GRU）模型的字符串序列編碼方法。MIRROR 方案將基本塊中的操作碼和操作數(shù)看作一個(gè)符號(hào)序列，利用NMT（Neural Machine Translation）在x86 和ARM 之間實(shí)現(xiàn)翻譯，從而實(shí)現(xiàn)跨平臺(tái)的相似性搜索。

3.2.3 討論與小結(jié)

基于特征語義的二進(jìn)制代碼相似性搜索方案間比較結(jié)果如表6 所示。

表6 基于特征語義的二進(jìn)制代碼相似性搜索方案間比較Tab 6 Comparison of binary code similarity search schemes based on features semantics

4 基于語用的二進(jìn)制代碼相似性搜索

本文中的二進(jìn)制代碼語用信息是指從二進(jìn)制代碼中恢復(fù)出高級(jí)語義用于代碼分析的信息，主要包括調(diào)試變量恢復(fù)和函數(shù)語義識(shí)別兩種。

4.1 調(diào)試信息恢復(fù)

為節(jié)省儲(chǔ)存空間，多數(shù)商用二進(jìn)制程序的調(diào)試信息通常被剝離。更嚴(yán)重的是，攜帶安全漏洞和惡意行為的二進(jìn)制程序經(jīng)常有意剝離掉，從而對(duì)抗安全分析。如果能夠嘗試恢復(fù)已剝離二進(jìn)制程序的數(shù)據(jù)類型或變量名稱，生成恢復(fù)二進(jìn)制程序中的調(diào)試信息，從高級(jí)語義角度開展相似性比較和搜索，可解釋性和魯棒性更強(qiáng)。

Debin 方案將變量識(shí)別為一個(gè)二分類問題，然后利用概率推導(dǎo)來預(yù)測(cè)變量值。該方案采用極端隨機(jī)樹（Extremely randomized Tree，ET）分類模型，用于程序變量的恢復(fù)和抽取。如果模型將寄存器或內(nèi)存偏移識(shí)別為變量，則在寄存器和變量、內(nèi)存偏離和變量之間打上變量標(biāo)簽。在變量值預(yù)測(cè)方面，Debin 給每一個(gè)未知節(jié)點(diǎn)分配一個(gè)屬性值，在概率圖模型上進(jìn)行最大后驗(yàn)概率推導(dǎo)，根據(jù)圖的結(jié)構(gòu)信息來預(yù)測(cè)所有未知節(jié)點(diǎn)的全局最優(yōu)值。

Debin 概率圖中的節(jié)點(diǎn)是函數(shù)、寄存器變量、內(nèi)存偏離變量、數(shù)據(jù)類型、標(biāo)志、指令、常量、位置和一元操作共計(jì)9 種類型，節(jié)點(diǎn)之間通過函數(shù)關(guān)系、變量關(guān)系、類型關(guān)系和因子關(guān)系建立連接，這些關(guān)系的引入更加接近高級(jí)語義，因此有助于代碼搜索。調(diào)試信息恢復(fù)方案不同于以往的函數(shù)相似性搜索，而是從數(shù)據(jù)相似性角度搜索代碼片段中是否包含感興趣的變量或關(guān)系。但是，Debin 方案預(yù)測(cè)準(zhǔn)確率低至68.8%，在代碼混淆處理上準(zhǔn)確率更低。類似的工作還有Dire 方案。

4.2 函數(shù)語義識(shí)別

如果順著函數(shù)的執(zhí)行流程，利用內(nèi)部調(diào)用關(guān)系，建立一個(gè)全局視圖來表達(dá)函數(shù)內(nèi)部意圖或用法的高級(jí)語義信息，那么二進(jìn)制代碼相似性搜索結(jié)果就符合人類理解和認(rèn)知，可解釋性更強(qiáng)。

Nero 方案通過建立神經(jīng)網(wǎng)絡(luò)翻譯模型，對(duì)給定的一個(gè)剝離二進(jìn)制函數(shù)，能夠預(yù)測(cè)產(chǎn)生API 調(diào)用序列高級(jí)語義名稱。具體實(shí)現(xiàn)為，提取函數(shù)的形成API 調(diào)用序列后，借助切片技術(shù)獲得API 參數(shù)的具體值或最大概率抽象值，從而形成增強(qiáng)Call 調(diào)用序列，然后將這些Call 調(diào)用序列喂入Encoder-Decoder 算法模型中從而實(shí)現(xiàn)預(yù)測(cè)。由于Nero 方案是利用API 調(diào)用序列來描述高級(jí)語義，能處理代碼混淆問題，卻無法處理調(diào)用的用戶自定義內(nèi)部函數(shù)。如果函數(shù)不包含API，是無法得到高級(jí)語義的。

Karonte 方案認(rèn)為設(shè)備通常使用多個(gè)二進(jìn)制文件實(shí)現(xiàn)其功能，因此建模和跟蹤多個(gè)二進(jìn)制文件的函數(shù)交互來分析嵌入式設(shè)備固件。該方案最大的優(yōu)勢(shì)在于不僅僅利用了多個(gè)文件，同時(shí)還利用了多個(gè)函數(shù)，因此能在多文件多函數(shù)之間傳播污染信息，進(jìn)而檢測(cè)出不安全的交互并識(shí)別漏洞。

識(shí)別函數(shù)語義方案最大優(yōu)勢(shì)在于給定一個(gè)代碼片段，可以理解代碼片段的高級(jí)語義，相較于基本塊語義方案，方案語義整體感強(qiáng)烈，便于人類認(rèn)知。

4.3 小結(jié)

不同于語法的寄存器等低級(jí)語言表述，也不同于語義在基本塊和嵌入向量上的語義描述，語用方案是從函數(shù)甚至整個(gè)程序上給出高級(jí)自然語言語義信息。從語用角度來搜索相似性的二進(jìn)制代碼片段，不僅可解釋性強(qiáng)，而且更符合人類語義。二進(jìn)制代碼相似性搜索方案間比較結(jié)果如表7所示。

表7 二進(jìn)制代碼相似性搜索方案間比較Tab 7 Comparison of binary code similarity search schemes

5 展望與挑戰(zhàn)

當(dāng)前二進(jìn)制代碼相似性搜索面臨可解釋性、語義識(shí)別和進(jìn)化性的挑戰(zhàn)。

5.1 可解釋性問題

可解釋性最大的挑戰(zhàn)就是方案間可比性差，在數(shù)據(jù)集、比較粒度、比較類型和向量表示上都會(huì)造成可解釋性差。

可解釋性差的第一個(gè)原因在于方案都是各自采用定制的數(shù)據(jù)集。即使有些方案在同樣的數(shù)據(jù)集進(jìn)行比較，但由于代碼不開源，在解釋性方面有點(diǎn)牽強(qiáng)。第二個(gè)原因是各種方案之間在輸入比較和輸入粒度上都不一樣，如有的比較是指令、有的比較是基本塊，有的比較是基于CFG，從而方案之間很難進(jìn)行比較。第三個(gè)原因是代碼比較類型不一樣。代碼比較類型分成代碼相似性比較、代碼等價(jià)比較和代碼相同比較。代碼相同比較的結(jié)果，代碼一定相似性；代碼相似比較的結(jié)果，代碼不一定相同。同時(shí)，指令歸一化后的比較方案和基于圖的相似性解決方案之間也無法比較。第四個(gè)原因是通過嵌入學(xué)習(xí)的向量，無法描述相似性決策過程，定位不了哪些片段區(qū)域相似。

近些年知識(shí)圖譜在很多任務(wù)中展現(xiàn)巨大應(yīng)用潛力。知識(shí)圖譜是以圖的形式表現(xiàn)客觀世界中的實(shí)體（概念）及其之間關(guān)系的知識(shí)庫。知識(shí)表示學(xué)習(xí)是面向知識(shí)庫中實(shí)體和關(guān)系的表示學(xué)習(xí)。通過將實(shí)體或關(guān)系投影到低維向量空間，能夠?qū)崿F(xiàn)對(duì)實(shí)體和關(guān)系的語義信息的表示，高效地計(jì)算實(shí)體、關(guān)系及其之間的復(fù)雜語義關(guān)聯(lián)，進(jìn)而理解搜索的語義，提供更精準(zhǔn)的搜索答案。以Word2vec、Doc2vec 和BERT 為代表的預(yù)訓(xùn)練語言模型，能從文本抽取出豐富的語言信息，但是很少考慮將知識(shí)圖譜的結(jié)構(gòu)化信息融入其中，從而提高語言的理解。ERNIE（Enhanced language Representation with Informative Entities）方案通過訓(xùn)練一個(gè)增強(qiáng)的語言表示模型，能夠同時(shí)利用詞匯、語義和知識(shí)信息，使得實(shí)體能夠增強(qiáng)語言表示。因此，從

n

個(gè)目標(biāo)中找到

k

個(gè)最相似的代碼搜索問題，可以嘗試?yán)肨ransE（Translating Embeddings for modeling multi-relational data）代表的知識(shí)表示學(xué)習(xí)二進(jìn)制代碼語義信息，從多個(gè)維度實(shí)現(xiàn)異質(zhì)信息融合。將二進(jìn)制代碼片段看作是一個(gè)知識(shí)圖譜，通過知識(shí)圖譜推理結(jié)果來比較代碼片段，在準(zhǔn)確性和可解釋性上可能會(huì)效果更好。

深度學(xué)習(xí)的不透明特性為找到網(wǎng)絡(luò)安全解決方案帶來挑戰(zhàn)。深度神經(jīng)網(wǎng)絡(luò)利用數(shù)以萬計(jì)的神經(jīng)元在大量的數(shù)據(jù)集上進(jìn)行訓(xùn)練而成。訓(xùn)練本身帶來的高度復(fù)雜性和黑盒操作，使得研究人員很難理解神經(jīng)網(wǎng)絡(luò)的某些決策，從而導(dǎo)致無法信任神經(jīng)網(wǎng)絡(luò)給出的安全結(jié)果，對(duì)于錯(cuò)誤的結(jié)果也無法有效判斷神經(jīng)網(wǎng)絡(luò)的錯(cuò)誤出現(xiàn)在哪里。LEMNA（Local Explanation Method using Nonlinear Approximation）方 案開啟了二進(jìn)制代碼逆向和惡意軟件聚類的可解釋性問題的研究，重點(diǎn)關(guān)注尋找函數(shù)邊界，確定函數(shù)類型，以及定位相似代碼，實(shí)驗(yàn)闡釋了為什么聚類操作會(huì)作出正確或者錯(cuò)誤的決定。

5.2 語義識(shí)別問題

準(zhǔn)確定義語義關(guān)系并識(shí)別代碼語義是解決代碼搜索的核心技術(shù)。語義比較能夠容忍源代碼轉(zhuǎn)換和二進(jìn)制代碼轉(zhuǎn)變。在評(píng)估兩個(gè)文件相似性的時(shí)候，基于語義的方案既能夠容忍跨編譯、跨優(yōu)化和跨平臺(tái)帶來的魯棒性搜索問題，更能夠處理代碼混淆轉(zhuǎn)換后的相似性問題。

由于動(dòng)態(tài)分析發(fā)生在運(yùn)行時(shí)，代碼運(yùn)行時(shí)的內(nèi)存地址、操作值和控制流去向都非常明確，因此可以處理部分代碼混淆從而應(yīng)用于語義相等比較。但是動(dòng)態(tài)分析在混淆代碼的處理上也存在困難，主要是因?yàn)橐淮沃荒軋?zhí)行一個(gè)路徑，并且只能在這個(gè)路徑執(zhí)行中比較相似性。二進(jìn)制代碼仍會(huì)面臨代碼混淆帶來的挑戰(zhàn)。研究表明由于函數(shù)邊界識(shí)別問題，當(dāng)前脫殼技術(shù)會(huì)造成20%～60%的原始代碼丟失，如對(duì)采用虛擬化加殼器技術(shù)帶來的混淆并沒有較好的解決方案。

從漏洞發(fā)現(xiàn)角度出發(fā)，融入數(shù)據(jù)語義相似性和數(shù)據(jù)流分析技術(shù)可能會(huì)產(chǎn)生比較好的語義相等結(jié)果，從而有助于漏洞進(jìn)化研究。因此，結(jié)合二進(jìn)制代碼類型恢復(fù)，定位代碼使用中的變量并對(duì)變量相關(guān)的操作進(jìn)行分類，生成攜帶調(diào)試信息的參數(shù)，進(jìn)一步挖掘二進(jìn)制的高級(jí)語義信息是二進(jìn)制代碼逆向分析的趨勢(shì)，其研究結(jié)果更有助于搜索等下游任務(wù)的實(shí)現(xiàn)。

5.3 進(jìn)化性問題

當(dāng)前二進(jìn)制代碼相似性比較方案，并沒有考慮比較片段是否進(jìn)化如代碼的新增、更新或者刪除。這些進(jìn)化可能會(huì)帶來語義的巨大差異，如深度學(xué)習(xí)模型中某個(gè)參數(shù)的修訂或者加解密算法中某個(gè)API 的更換?？傊?，相似性比較方案僅僅能夠鑒別相似性，但是卻無法鑒別語義進(jìn)化。

安全漏洞分析和bug 搜索中也會(huì)面臨這樣的需求，如很多程序在更新補(bǔ)丁信息后并不會(huì)透露更新細(xì)節(jié)。安全補(bǔ)丁大多是微小變化，92%的安全補(bǔ)丁是在一個(gè)文件中，30%的補(bǔ)丁修復(fù)僅僅包含一行條件。這樣一來，基于相似性的方法在識(shí)別細(xì)微變化上會(huì)更難，從而無法有效地區(qū)分補(bǔ)丁版本和未補(bǔ)丁版本，從而在bug 搜索或者漏洞發(fā)現(xiàn)時(shí)會(huì)產(chǎn)生很高的誤報(bào)率或漏報(bào)率。研究高級(jí)語義的描述，識(shí)別不同應(yīng)用場(chǎng)景的進(jìn)化模式，可能是進(jìn)化性搜索的解決之道。

有學(xué)者從演化網(wǎng)絡(luò)入手，研究惡意代碼之間的多繼承關(guān)系。文獻(xiàn)［98］提出了利用分割圖的惡意代碼家族世襲網(wǎng)絡(luò)構(gòu)建算法，能夠自動(dòng)構(gòu)建包含多繼承關(guān)系的演化網(wǎng)絡(luò)。該方案雖然能夠自動(dòng)地進(jìn)行分析，但面對(duì)海量待分析惡意代碼時(shí)，計(jì)算時(shí)間將急劇增加。有學(xué)者從基因視角來描述惡意代碼之間的演化關(guān)系，通過計(jì)算基因之間的相似性來判斷惡意代碼之間的相似性。為識(shí)別相似的惡意代碼之間是否發(fā)生進(jìn)化，文獻(xiàn)引入時(shí)間特征來反映惡意代碼出現(xiàn)的先后順序，從而指導(dǎo)惡意代碼演化網(wǎng)絡(luò)的建立。

6 結(jié)語

本文討論了二進(jìn)制代碼相似性搜索當(dāng)前的研究現(xiàn)狀，分別從語法、語義和語用角度對(duì)比分析各種方案。未來的二進(jìn)制代碼分析需要從低級(jí)語義分析變更到高級(jí)語義或語用的分析上來，需要能夠處理進(jìn)化性、可解釋性帶來的問題挑戰(zhàn)。盡管逆向分析話題很老，但是技術(shù)難度大，并伴隨著閉源和安全對(duì)抗的需要會(huì)永遠(yuǎn)持續(xù)活躍下去，并會(huì)在網(wǎng)絡(luò)安全漏洞發(fā)現(xiàn)和惡意代碼分析等真實(shí)應(yīng)用場(chǎng)景大放異彩。