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

陸藺，程磊，卜樹坡

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

0 引言

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

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

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

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

但若公共組件庫存在安全隱患并被多個程序重用，則會產生包括缺陷、惡意代碼傳播等負面影響，引起的連鎖反應甚至會造成嚴重后果。心臟滴血漏洞［4］( Heart Bleed) 就是重用隱患代碼導致安全問題的典型案例，其影響至今仍未消除［5］。

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

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

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

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

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

1 操作碼編輯距離的相似性計算

1.1 OpCode 操作碼

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

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

圖1中第1-2 行指令中title:"0"表示AppA 的首代碼段節(jié)點名稱是Main，其編號為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 操作碼序列的編輯距離相似度

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

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

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

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

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

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

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

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

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

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

1.3 基于拓撲序列所有公共子序列的相似度

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

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

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

Vx ={V1，…Vm}，Vy ={V1，…Vn} 是將有向圖進行深度優(yōu)先搜索后轉化的多重拓撲序列，其中Vi∈(Vx，Vy) 是操作碼序列的集合，即代碼段。ACS(x，y)值越大，多重拓撲序列相似度越高，否則相似度越低［22］。兩個有向圖所有公共子序列的相似度為:

現(xiàn)舉例簡要說明拓撲序列所有公共子序列的圖相似度判定方法。如圖3 所示有兩個程序調用邏輯有向圖為(G1，G2) ，各節(jié)點分別為代碼段且節(jié)點編號均不相同。從圖中可見有部分子圖相同，說明兩個有向圖的調用邏輯具有相似性。

圖3 有向圖轉化序列Fig.3 Directed graph transformation sequence

從頂點開始對(G1，G2) 進行深度優(yōu)先搜索形成的拓撲序列為:

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

圖4 ACS 計算矩陣Fig.4 ACS calculation matrix

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

1.4 二進制ELF 文件同源性判定

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

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

2.1 融合終端App 分類

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

2.2 二進制ELF 鏡像文件反編譯

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

圖5 調用過程圖Fig.5 Calling process diagram

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

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

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

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

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

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

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

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

圖7 AppA 調用過程有向圖Fig.7 Directed graph of AppA calling procedure

有向圖中每個節(jié)點代表一個代碼段，每條路徑的節(jié)點1 均為主程序節(jié)點Main，并進行深度優(yōu)先搜索后形成拓撲序列V1。采用同樣方法將AppB-AppE 的調用過程轉化成有向圖，如圖8 所示:

圖8 AppB-AppE 調用過程有向圖Fig.8 Directed graph of AppB-AppE calling procedure

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

將有向圖進行深度優(yōu)先搜索得全部多重拓撲序列路徑V1-V5，結果見表3。

表3 多重拓撲路徑表Tab.3 Multiple topology path table

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

表4 文件相似度計算結果Tab.4 File similarity calculation results

2.4 二進制ELF 文件同源性判定

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

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

圖9 試驗版本調用過程有向圖Fig.9 Directed graph of trial version calling process

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

文獻［25］指出不同源代碼段相似度上限為30%，綜上所述的計算結果符合要求。

3 結束語

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

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