基于OpCode 的融合終端代碼相似性檢測(cè)方法研究

陸藺，程磊，卜樹坡

( 蘇州工業(yè)職業(yè)技術(shù)學(xué)院電子與通信工程系，江蘇 蘇州 215104)

0 引言

伴隨著“數(shù)字電網(wǎng)”的加速建設(shè)和配電側(cè)臺(tái)區(qū)智能化逐步推進(jìn)，采用Linux 嵌入式硬件平臺(tái)、搭載輕量級(jí)容器及微應(yīng)用App 的臺(tái)區(qū)智能融合終端( 簡(jiǎn)稱融合終端) 應(yīng)用前景廣泛［1］。融合終端的優(yōu)點(diǎn)在于底層解耦硬件結(jié)構(gòu)實(shí)現(xiàn)硬件平臺(tái)化，中間層將環(huán)境容器化實(shí)現(xiàn)App 跨平臺(tái)運(yùn)行，應(yīng)用層軟件化使融合終端全部功能均由可加載的各類App 實(shí)現(xiàn)。由此可見，融合終端生態(tài)架構(gòu)已能夠支撐平臺(tái)間的互操作和微應(yīng)用的可移植。但是由于終端類設(shè)備可用資源受限，難以部署完善的安全防護(hù)機(jī)制，出于源代碼安全等原因，開發(fā)人員將編譯后形成的二進(jìn)制ELF 文件及運(yùn)行環(huán)境打包成可移植的鏡像文件，在融合終端的中間層實(shí)現(xiàn)跨平臺(tái)運(yùn)行［2］?？缙脚_(tái)和通用性極大降低了準(zhǔn)入門檻和開發(fā)難度，大量的第三方廠家采用重用技術(shù)并行開發(fā)多個(gè)相似App 產(chǎn)品，節(jié)約成本的同時(shí)提高了開發(fā)效率。

《臺(tái)區(qū)智能融合終端微應(yīng)用開發(fā)及檢測(cè)規(guī)范》( 簡(jiǎn)稱《規(guī)范》) 中按功能劃分了30 個(gè)微應(yīng)用App，包括配/用電業(yè)務(wù)、通訊協(xié)議和外部接口等定義以便于進(jìn)行標(biāo)準(zhǔn)化開發(fā)。本文所述App 均特指符合《規(guī)范》的微應(yīng)用，詳細(xì)分類如表1 所示。

表1 融合終端App 分類Tab.1 Fusion terminal App classification

目前，國(guó)家電網(wǎng)計(jì)量中心要求將產(chǎn)品的二進(jìn)制目標(biāo)代碼備案以防范和控制軟件運(yùn)行風(fēng)險(xiǎn)［3］。同時(shí)《規(guī)范》還規(guī)定不同廠家開發(fā)的相似App 必須進(jìn)行互換性試驗(yàn)，互換后應(yīng)滿足功能需求及具體指標(biāo)要求。由此可見，能夠通過互換性試驗(yàn)的App 必定具備相同功能和標(biāo)準(zhǔn)化接口，這為借鑒并重用代碼提供了環(huán)境依據(jù)，而豐富的公共組件庫(kù)和代碼重用率使不同廠家源代碼之間天然呈現(xiàn)某種相似性。

但若公共組件庫(kù)存在安全隱患并被多個(gè)程序重用，則會(huì)產(chǎn)生包括缺陷、惡意代碼傳播等負(fù)面影響，引起的連鎖反應(yīng)甚至?xí)斐蓢?yán)重后果。心臟滴血漏洞［4］( Heart Bleed) 就是重用隱患代碼導(dǎo)致安全問題的典型案例，其影響至今仍未消除［5］。

近年來，軟件安全問題頻發(fā)，繼承自第三方代碼的漏洞一直困擾著開發(fā)人員，有效的App 代碼相似性檢測(cè)成為保障系統(tǒng)穩(wěn)定運(yùn)行的關(guān)鍵，也成為目前熱點(diǎn)的研究課題，因此開展融合終端App 同源或相似性分析、評(píng)價(jià)源代碼相似度量化指標(biāo)，對(duì)于解決融合終端的安全隱患，具有非常重要的意義。

由于源代碼無法獲取，分析二進(jìn)制ELF 文件成為研究App 相似性的理想途徑［6］。二進(jìn)制OpCode 操作碼是從ELF 文件中提取的字符串序列，是Linux 執(zhí)行靜態(tài)編譯時(shí)由詞法、語法轉(zhuǎn)化而來［7］。文獻(xiàn)［8］指出重用代碼有很大的相似性和典型特征，可通過OpCode 操作碼進(jìn)行特征提取。文獻(xiàn)［9］指出反編譯的二進(jìn)制ELF 文件，源代碼序列對(duì)應(yīng)OpCode 序列相同。文獻(xiàn)［10］指出兩段OpCode 序列特征相同則可判定相似，多段OpCode 序列特征相同可判定為同源，這為二進(jìn)制代碼相似和同源判定提供了理論借鑒。

傳統(tǒng)的OpCode 序列相似性判定采用N-gram 語義切分模型［11］，缺點(diǎn)是過于龐大的特征集合會(huì)導(dǎo)致稀疏矩陣和維度風(fēng)暴問題［12］。盡管采用多種方法如混合特征提取能夠提高N-gram 的區(qū)分度，但準(zhǔn)確性和計(jì)算性能仍有待進(jìn)一步商榷［13］。

編輯距離( Edit Distance) 是通過轉(zhuǎn)換步數(shù)來度量相似程度的方法［14］，通過構(gòu)建最優(yōu)路徑實(shí)現(xiàn)近似字符串在字符級(jí)別上的容錯(cuò)匹配，是本文采用的相似性衡量標(biāo)準(zhǔn)，主要應(yīng)用于圖相似性判斷、數(shù)據(jù)清洗和語義特征提取等多種領(lǐng)域，其本質(zhì)仍然是字符或數(shù)字序列的保序匹配與檢索。二進(jìn)制OpCode 操作碼序列作為字符串序列的特例，同樣適用字符串的相似性判定方法。

代碼相似性比較是OpCode 特征向量的距離計(jì)算，文中首次引入編輯距離判定代碼段相似性，提出一種面向二進(jìn)制ELF 文件、以O(shè)pCode 為特征、基于代碼段編輯距離和所有公共子序列圖相似性相結(jié)合的融合終端相似性度量模型，為解決融合終端二進(jìn)制代碼快速相似性度量提供了新的思路。

1 操作碼編輯距離的相似性計(jì)算

1.1 OpCode 操作碼

文中的OpCode 操作碼序列提取自二進(jìn)制ELF 文件，其中操作碼和操作數(shù)是基本元素。操作碼指示代碼行為，操作數(shù)體現(xiàn)行為目標(biāo)。文獻(xiàn)［15］指出改變編譯環(huán)境只會(huì)影響操作數(shù)，而操作碼不變，所以目前基本采用操作碼序列作為相似性判斷的依據(jù)。圖1 為某用電AppA 的二進(jìn)制Main 代碼段。

圖1 反匯編代碼段Fig.1 Disassembly code snippet

圖1中第1-2 行指令中title:"0"表示AppA 的首代碼段節(jié)點(diǎn)名稱是Main，其編號(hào)為node0，本文所有ELF 文件的首代碼段均為Main。第9 行指令中"MOV"為操作碼，則從圖中可得到代碼段的操作碼序列為:OMain={PUSH，VPUSH，SUBW，MOV，ADDS，STR，MOV，LDR，STR，MOVS，STR.W，MOV，ADDS，LDR，BLX，BNE}。

1.2 操作碼序列的編輯距離相似度

設(shè)操作碼序列O1={O11，…，O1r}，O2={O21，…，O2s} 的編輯距離定義為: 將O1轉(zhuǎn)換為O2所需的最少操作步驟［16］，其中r、s分別為O1、O2的長(zhǎng)度。操作步驟包括操作碼的刪除、插入和替換。操作碼序列的編輯距離通過動(dòng)態(tài)規(guī)劃法計(jì)算匹配距離矩陣［17］:

其中，wins(O1i) 為插入操作權(quán)重，wdel(O2j) 為刪除操作權(quán)重，wsub(O1i，O2j) 為替換操作權(quán)重，當(dāng)O1i=O2j時(shí)wsub(O1i，O2j)=0 。例如將給定的操作碼序列O1={PUSH，VPUSH，SUBW，MOV，ADDS}轉(zhuǎn)換為O2={SUBW，VPUSH，MOV}需編輯3 步:

1) 將PUSH 替換為SUBW: { SUBW，VPUSH，SUBW，MOV，ADDS};

2) 刪除SUBW:{SUBW，VPUSH，MOV，ADDS};

3) 刪除ADDS:{SUBW，VPUSH，MOV}。

編輯距離匹配矩陣的具體計(jì)算過程見文獻(xiàn)［18］，此處不再詳述。圖2 為O1和O2的編輯距離匹配矩陣。

圖2 編輯距離計(jì)算矩陣Fig.2 Editing distance calculation matrix

根據(jù)動(dòng)態(tài)規(guī)劃的思想，刪除、插入和替換在計(jì)算矩陣中分別體現(xiàn)為路徑的垂直、水平和對(duì)角移動(dòng)。從圖中可見，自矩陣D(4，6) 單元格回溯至D(1，1) 單元格能繪制出一條最短的操作步驟路徑，此路徑即為O1轉(zhuǎn)換為O2的具體操作步驟: 替換SUBW、刪除SUBW、刪除ADDS。矩陣的D(4，6) =3 即為操作碼序列O1轉(zhuǎn)換為O2的編輯距離。操作碼序列的編輯距離相似度定義為:操作碼序列O1，O2間的編輯距離與較長(zhǎng)序列長(zhǎng)度的比值［19］，公式如下:

從式(3) 可知轉(zhuǎn)換步驟越少，操作碼序列O1，O2相似程度越高，否則相似程度越低。

需要說明的是，ARM64 指令集中能夠進(jìn)行排列組合的指令數(shù)量只有200 多個(gè)，相似性度量過程就是統(tǒng)一操作碼序列中差異部分的過程，即只考慮序列中操作碼的刪除、插入和替換順序，因此相對(duì)于其他方法，編輯距離更適合二進(jìn)制操作碼序列比對(duì)，這也是本文引入編輯距離的主要原因。其次從耗費(fèi)時(shí)間角度，在程序執(zhí)行過程中若兩個(gè)操作碼一致，則只執(zhí)行公式(1)的賦值操作而不執(zhí)行式( 2) ，顯然式( 1) 的執(zhí)行速度相對(duì)較快，因此若序列相似度越高，編輯距離的執(zhí)行步驟越少，執(zhí)行速度就越快。從式( 1) 、式( 2) 可知編輯距離時(shí)間復(fù)雜度較低，為O(| r | ×| s |) ，適合進(jìn)行長(zhǎng)序列對(duì)比。最后編輯距離只需動(dòng)態(tài)規(guī)劃迭代實(shí)現(xiàn)，無需矩陣參與計(jì)算，不會(huì)因稀疏矩陣導(dǎo)致維度風(fēng)暴而產(chǎn)生額外的消耗。綜上所述，采用編輯距離度量操作碼序列的相似性具有速度快、長(zhǎng)序列等優(yōu)點(diǎn)。

1.3 基于拓?fù)湫蛄兴泄沧有蛄械南嗨贫?/h3>

邏輯相似度計(jì)算是二進(jìn)制代碼相似性度量不可或缺部分，文獻(xiàn)［20］指出反編譯的二進(jìn)制文件代碼與源代碼的邏輯調(diào)用關(guān)系大致相同。假設(shè)兩個(gè)App 代碼有相似的執(zhí)行順序，可認(rèn)為這兩個(gè)App 的邏輯調(diào)用關(guān)系也具有相似性。

目前，二進(jìn)制文件調(diào)用關(guān)系主要以代碼段為基礎(chǔ)的有向流程圖的邏輯關(guān)系［21］。文中采用所有公共子序列法( All Common Subsequences，ACS) 將流程圖跳轉(zhuǎn)邏輯相似性問題轉(zhuǎn)化為有向圖的相似性度量。

設(shè)ACS(x，y) 為待求的所有公共子序列數(shù)量，有如下公式:

Vx ={V1，…Vm}，Vy ={V1，…Vn} 是將有向圖進(jìn)行深度優(yōu)先搜索后轉(zhuǎn)化的多重拓?fù)湫蛄?，其中Vi∈(Vx，Vy) 是操作碼序列的集合，即代碼段。ACS(x，y)值越大，多重拓?fù)湫蛄邢嗨贫仍礁?，否則相似度越低［22］。兩個(gè)有向圖所有公共子序列的相似度為:

現(xiàn)舉例簡(jiǎn)要說明拓?fù)湫蛄兴泄沧有蛄械膱D相似度判定方法。如圖3 所示有兩個(gè)程序調(diào)用邏輯有向圖為(G1，G2) ，各節(jié)點(diǎn)分別為代碼段且節(jié)點(diǎn)編號(hào)均不相同。從圖中可見有部分子圖相同，說明兩個(gè)有向圖的調(diào)用邏輯具有相似性。

圖3 有向圖轉(zhuǎn)化序列Fig.3 Directed graph transformation sequence

從頂點(diǎn)開始對(duì)(G1，G2) 進(jìn)行深度優(yōu)先搜索形成的拓?fù)湫蛄袨?

按照公式(4) 建立所有公共子序列數(shù)量矩陣如圖4 所示。

圖4 ACS 計(jì)算矩陣Fig.4 ACS calculation matrix

矩陣計(jì)算結(jié)果可得:ACS(VG1，VG2)= D(8，8)=10 ，所有公共子序列為: {，3，4，2，5，25，34，35，45，345}。根據(jù)公式(5) 得:

1.4 二進(jìn)制ELF 文件同源性判定

二進(jìn)制代碼相似性度量需要等同考慮代碼段和調(diào)用邏輯的作用，得到二進(jìn)制ELF 文件最終的相似度估算結(jié)果［19，23］:

2 臺(tái)區(qū)智能融合終端代碼反編譯

2.1 融合終端App 分類

《規(guī)范》中將融合終端App 按照功能分為基礎(chǔ)App和業(yè)務(wù)App?；A(chǔ)App 對(duì)通信接口、通信協(xié)議、數(shù)據(jù)模型、數(shù)據(jù)中心接口服務(wù)等基礎(chǔ)資源統(tǒng)一管理，為業(yè)務(wù)App 提供技術(shù)支撐。業(yè)務(wù)App 分為采集通信類和應(yīng)用分析類。采集通信類App 實(shí)現(xiàn)與上行主站通信交互及下行設(shè)備數(shù)據(jù)采集;應(yīng)用分析類App 實(shí)現(xiàn)配電、用電業(yè)務(wù)場(chǎng)景的需求應(yīng)用。表1 為App 分類及其主要功能，其中序號(hào)1-7 為基礎(chǔ)App，序號(hào)8-30 為業(yè)務(wù)App。從表1 可以看出，融合終端App 種類較多，范圍涵蓋中壓、低壓大部分功能。

2.2 二進(jìn)制ELF 鏡像文件反編譯

Linux 軟件包分為源碼包和二進(jìn)制ELF 鏡像包，后者是直接運(yùn)行的機(jī)器代碼。因鏡像包不能直接讀取，需將其反編譯為匯編指令序列。文中反編譯某用電AppA 的二進(jìn)制ELF 鏡像包，得結(jié)構(gòu)框圖及部分代碼結(jié)果如圖5 所示。

圖5 調(diào)用過程圖Fig.5 Calling process diagram

從圖5 中可見，反匯編后共有24 個(gè)代碼段節(jié)點(diǎn)，最頂端編號(hào)為node0 的節(jié)點(diǎn)是主程序節(jié)點(diǎn)Main，其指令如圖1 所示。去除node0 節(jié)點(diǎn)中指令序列的操作數(shù)，得OpCode 操作碼序列為1.1 節(jié)中的OMain_A。

另有AppB 主程序節(jié)點(diǎn)Main 的操作碼序列OMain_B= { MOVW，MOVW，POP，MOV，PUSH，PUSH，LDRW，STRW，LDR，LDR，BLX，BLX}，按式(1) 、式(2)可得編輯距離矩陣的計(jì)算結(jié)果，如圖6 所示。

圖6 Main 編輯距離計(jì)算矩陣Fig.6 Main editing distance calculation matrix

從圖6 中可得D(13，16) =12 為操作碼的編輯距離。根據(jù)式(3) ，OMain_A和OMain_B的編輯距離相似度為:1-12/16 =25%。同理，選擇AppA-AppE 中較長(zhǎng)的代碼段，采用同樣方法得編輯距離相似度結(jié)果見表2。從表2 知來自AppE 中的(O5－1，O5－2) 相似度最高達(dá)到44.6%。反編譯共享函數(shù)庫(kù)并與(O5－1，O5－2) 對(duì)比發(fā)現(xiàn)，這兩個(gè)代碼段重用了多個(gè)共享函數(shù)是導(dǎo)致相似比例過高的主要原因，類似情況還包括(O2－1，O2－2) 。

表2 編輯距離及相似度計(jì)算結(jié)果( 長(zhǎng)度、距離×100)Tab.2 Editing distance and similarity calculation results ( length，distance×10)

另外，編輯距離的相似度會(huì)出現(xiàn)極小數(shù)值情況，當(dāng)兩個(gè)代碼段長(zhǎng)度相差較大時(shí)會(huì)導(dǎo)致相似度變小，長(zhǎng)度相差越大相似度越小。根據(jù)式(3) 的計(jì)算結(jié)果表明，有時(shí)相似度數(shù)量級(jí)相差范圍在103以上，因此盡量不進(jìn)行類似的比較，或者可以忽略長(zhǎng)代碼段和短代碼段的比較結(jié)果。另外編程語言的基本語句結(jié)構(gòu)如if、switch、while、for 語句，盡管參數(shù)有所不同，但轉(zhuǎn)換成二進(jìn)制代碼后邏輯結(jié)構(gòu)是一致的，因此不同源的二進(jìn)制代碼段也有一定的相似度。由于篇幅有限，表2 只給出部分編輯距離的計(jì)算結(jié)果。

2.3 執(zhí)行序列相似度

按1.3 節(jié)中所述，將AppA 的調(diào)用過程圖( 圖5) 變形為有向圖，如圖7 所示。

圖7 AppA 調(diào)用過程有向圖Fig.7 Directed graph of AppA calling procedure

有向圖中每個(gè)節(jié)點(diǎn)代表一個(gè)代碼段，每條路徑的節(jié)點(diǎn)1 均為主程序節(jié)點(diǎn)Main，并進(jìn)行深度優(yōu)先搜索后形成拓?fù)湫蛄蠽1。采用同樣方法將AppB-AppE 的調(diào)用過程轉(zhuǎn)化成有向圖，如圖8 所示:

圖8 AppB-AppE 調(diào)用過程有向圖Fig.8 Directed graph of AppB-AppE calling procedure

從圖8 中可見，有向圖呈現(xiàn)不規(guī)則變化，無法從中判斷調(diào)用邏輯是否相似。

將有向圖進(jìn)行深度優(yōu)先搜索得全部多重拓?fù)湫蛄新窂絍1-V5，結(jié)果見表3。

表3 多重拓?fù)渎窂奖鞹ab.3 Multiple topology path table

根據(jù)圖7 和圖8 還可得出有向圖V1-V5中節(jié)點(diǎn)最大度數(shù)、最大度數(shù)對(duì)應(yīng)節(jié)點(diǎn)數(shù)量及編號(hào)。根據(jù)式(4) 計(jì)算多重拓?fù)湫蛄?，?jì)算過程在1.3 節(jié)已有詳述，文中直接給出ACS 的結(jié)果及序列相似度，見表4。

表4 文件相似度計(jì)算結(jié)果Tab.4 File similarity calculation results

2.4 二進(jìn)制ELF 文件同源性判定

根據(jù)公式( 9) 計(jì)算AppA-AppB 二進(jìn)制文件相似度，從表4 中取SimACS(V1，V2) 、從表2 中取Simedit(O1，O2－1) 及Simedit(O1，O2－2) 、從表3 取Nmax及M得:

同理計(jì)算得各個(gè)App 之間的相似度結(jié)果如表4 中第7 列所示。從表4 中可見，參與測(cè)試的App 功能基本相似但相似度結(jié)果均不相同，范圍在( 9. 9393%，40.6097%) 之間。文獻(xiàn)［24］指出二進(jìn)制同源App 的相似度下限為50%，可知AppA-AppE 均未超過同源判定閾值。相同軟件代碼的不同版本被認(rèn)定是同源數(shù)據(jù)集，版本越靠近相似度越高。由于融合終端產(chǎn)品的特殊性，暫時(shí)不能進(jìn)行全部融合終端相鄰版本的相似性度量。為驗(yàn)證本文方法有效性，將AppD 的二進(jìn)制ELF 文件做適當(dāng)修改后作為試驗(yàn)版本，其有向圖如圖9 所示:

圖9 試驗(yàn)版本調(diào)用過程有向圖Fig.9 Directed graph of trial version calling process

從表3、表4 中提取數(shù)據(jù)計(jì)算AppD-AppDtest的相似度為:

文獻(xiàn)［25］指出不同源代碼段相似度上限為30%，綜上所述的計(jì)算結(jié)果符合要求。

3 結(jié)束語

近年來，軟件隱患代碼原因?qū)е碌腁pp 微應(yīng)用遭受攻擊的數(shù)量逐年升高。融合終端產(chǎn)品的快速發(fā)展、組件庫(kù)和代碼庫(kù)數(shù)量不斷攀升、同源代碼規(guī)模持續(xù)增加，安全缺陷檢測(cè)研究面臨嚴(yán)峻挑戰(zhàn)。如何判定App是否同源，作為解決安全問題的共性關(guān)鍵技術(shù)變得尤為重要。對(duì)二進(jìn)制代碼進(jìn)行快速相似性度量逐漸成為終端安全防護(hù)的重點(diǎn)研究方向。目前融合終端廠家較少，還處在硬件實(shí)現(xiàn)和運(yùn)維工具設(shè)計(jì)階段，沒有進(jìn)行批量上線運(yùn)行，能夠進(jìn)行對(duì)比的程序樣本較少，因此不適合采用深度學(xué)習(xí)、神經(jīng)網(wǎng)絡(luò)等大批量樣本訓(xùn)練的方法進(jìn)行相似性分析。

針對(duì)常規(guī)OpCode 檢測(cè)方法特征維度過高、檢測(cè)效率低等問題，提出了一種新的基于OpCode 代碼段編輯距離和所有公共子序列的圖相似性相結(jié)合的智能融合終端二進(jìn)制ELF 文件相似性判定方法。首次將編輯距離引入二進(jìn)制指令集的相似度比較，從OpCode 序列和代碼段調(diào)用順序兩個(gè)模式進(jìn)行組合，提出調(diào)整后相似度模型的量化公式。與N-gram 法相比規(guī)避了維度災(zāi)難并且時(shí)間復(fù)雜度較低，解決了代碼段層面的OpCode序列比較難題，為解決融合終端二進(jìn)制代碼相似性度量提供了一種新的途徑。