VDNS: 一種跨平臺的固件漏洞關聯算法

常 青 劉中金 王猛濤 陳 昱 石志強 孫利民

1(物聯網信息安全技術北京市重點實驗室(中國科學院信息工程研究所) 北京 100093)2(中國科學院信息工程研究所 北京 100093)3(中國科學院大學 北京 100049)4(國家計算機網絡應急技術處理協調中心 北京 100029) (changqing@iie.ac.cn)

?

VDNS: 一種跨平臺的固件漏洞關聯算法

常 青1,2,3劉中金4王猛濤1,2,3陳 昱1,2,3石志強1,2,3孫利民1,2,3

1(物聯網信息安全技術北京市重點實驗室(中國科學院信息工程研究所) 北京 100093)2(中國科學院信息工程研究所 北京 100093)3(中國科學院大學 北京 100049)4(國家計算機網絡應急技術處理協調中心 北京 100029) (changqing@iie.ac.cn)

當前，越來越多的物聯網廠商將第三方代碼庫編譯并部署在不同平臺上.現有研究主要集中在同平臺固件漏洞關聯場景，不能直接用于檢測其他平臺上的同源漏洞，而跨平臺場景的研究則剛剛起步.針對現有跨平臺方法準確率低的問題，提出基于神經網絡和局部調用結構匹配的2階段跨平臺固件漏洞關聯方法(vulnerability detection based on neural networks and structure matching, VDNS).以函數為最小關聯單元，對函數間調用圖、函數內控制流圖、函數基本信息進行特征選擇和數值化處理，并采用神經網絡計算待匹配函數對的相似程度，在此基礎上采用結構化匹配方法進一步提高匹配精度.實驗結果表明：該方法在二進制文件OpenSSL上性能指標Top1從32.1%提高至76.49%；采用5個漏洞函數對OpenSSL進行關聯的Rank值均為1；采用4個常見的路由器漏洞函數在372個D-Link路由器固件上進行關聯獲得了良好的實驗效果.

跨平臺；漏洞關聯；特征選擇；神經網絡；二分圖匹配

固件(firmware)是嵌入在硬件設備中的軟件，表現為存儲于非易失存儲器中的二進制程序，為上層軟件有效使用硬件設備提供調用接口，是電子系統的重要組成部分，計算機系統中的BIOS和擴展ROM中的程序，以及常見的網絡設備如路由器、交換機、網絡攝像頭的可執行程序都是典型的固件.固件方便了用戶的使用，同時也為信息系統的安全留下隱患.開放式Web應用程序安全項目(open Web application security project, OWASP)的調查結果顯示，2014年排名前10位的針對物聯網設備系統的漏洞威脅和攻擊中，對軟件和嵌入式設備固件的攻擊排名第9位[1].ZoomEye的統計報告指出，2013年10月發生的D-Link路由器后門事件中，受影響的路由器型號多達10多個，可在公網搜索訪問到的6萬多臺路由器中受影響的多達23%[2].愈來愈多因惡意固件導致的安全事件的發生，讓人們認識到固件安全防護的重要性.

固件漏洞關聯是指利用已知固件中存在的漏洞檢測出其他固件中存在的同源漏洞.由于固件源代碼難以獲取，一般采用二進制程序相似性檢測等技術，從待檢測固件的二進制文件中搜索并定位包含已知漏洞的代碼片段.早期的應用場景中，包含漏洞函數的二進制文件和待檢測的二進制文件是針對同平臺進行編譯的，具有相同的指令集.按分析對象的不同，漏洞關聯方法包括比特流比對[3-4]、指令序列比對[5-12]和動態插裝[13]等.比特流比對技術研究01序列的相似性，采用滑動窗口獲得的01序列作為特征計算相似度；指令序列比對技術研究匯編語句的相似程度；動態插裝技術則模擬程序的動態執行過程，比較同環境下程序執行帶來的“副作用”的相似程度.

當前，越來越多的物聯網廠商將第三方代碼庫編譯并部署在不同的CPU平臺上，如何利用1個平臺(如x86)上的漏洞函數去關聯其他平臺(如ARM,MIPS等)上的同源漏洞變得越來越重要.然而，現有的同平臺漏洞關聯方法并不能直接應用到跨平臺場景中來：比特流比對技術分析的對象是比特流，它與平臺采用的編碼方式相關；指令序列比對技術分析的對象是指令序列，它與平臺采用的指令集相關；動態插裝技術分析的是動態分析過程的中間結果，受限于分析工具的平臺兼容性，例如動態插裝工具PIN僅支持x86平臺.2015年Pewny等人首次提出基于語義的跨平臺漏洞關聯方法[14]，采用了提升中間語言表示、轉語義表達式、數值采樣和最小Hash加速等技術，將二進制代碼相似性檢測問題轉化為基本塊的語義信息比較問題，使用該方法對心臟流血漏洞函數進行關聯獲得了不錯的效果.由于采用了基于可信基點的基本塊擴張算法，對平臺不同導致的函數內部控制流圖細節異構敏感，即在圖匹配的過程中不能跳過不匹配的代碼塊，重新找到比較的開始點，導致后面的匹配全不正確，在對二進制文件OpenSSL進行關聯時其性能指標Top1僅達到32.1%.

針對當前方法準確率不高的問題，本文提出一種基于神經網絡和局部調用結構匹配的2階段跨平臺固件漏洞關聯方法(vulnerability detection based on neural networks and structure matching, VDNS)，該方法不依賴特定的指令集，可以跨平臺進行固件漏洞關聯.實驗證明：該方法具有良好的關聯效果.

1 跨平臺的固件漏洞關聯框架

本文提出的固件漏洞關聯框架包括2個階段：1)基于神經網絡的函數數值相似度的計算階段；2)基于局部調用結構匹配的函數整體相似度計算階段.

1個固件下載解壓過濾后包含多個二進制文件，對固件進行漏洞關聯等同于對固件包含的二進制文件進行漏洞關聯.二進制文件在逆向分析后被劃分為多個函數.框架輸入為2個二進制文件F和G，假設F包含已知的漏洞函數f，需要對G中的所有函數進行漏洞關聯，即目的是獲得漏洞函數f與G中所有待檢測函數g的相似程度，記f,g為待匹配函數，(f,g)為待匹配函數對.圖1是VDNS整體框架.

Fig. 1 The framework of VDNS.圖1 VDNS整體框架

在函數數值相似度計算階段，對二進制文件中每個函數的函數間調用關系、函數內控制流圖、函數基本信息進行數值化處理和特征提取，其中特征的表現形式有數量型、集合型和序列型.針對不同的表現形式，分別采用歐氏距離、Jaccard系數和最長公共子序列占比這3種度量方法計算待匹配函數對(f,g)各維特征的相似程度得到相似度向量.基于相似度向量采用ReliefF算法進行特征選擇.篩選后的相似度向量作為神經網絡的輸入，將神經網絡的輸出作為待匹配函數對(f,g)的數值相似度.在進行第2階段之前，可以根據數值相似度結果對規模較大的待檢測函數集進行初步篩選后再進行較為精確的結構化匹配.

在函數整體相似度計算階段，分別在二進制文件F和G生成的函數調用圖中截取以待匹配函數f和g為中心的局部調用結構，轉化為分層賦權二分圖，將其最大權匹配作為最終的整體相似度得分.

在進行關聯結果分析時，可以根據數值相似度得分進行關聯分析，也可以根據整體相似度得分進行關聯分析.數值相似度計算是整體相似度計算過程的中間步驟，由于計算數值相似度不需要進行后期的子圖匹配，因此速度較整體相似度快.但整體相似度考慮了函數調用圖的結構信息，準確率高.在實際應用中，可以根據具體情況進行選擇.

由于該方法在第1階段較為全面地提取了函數在函數調用圖、函數基本屬性和函數控制流圖3方面信息，并進行了特征選擇，使得提取的特征具有一定的區分能力，同時，這些特征不依賴指令集，具有一定的跨平臺能力，可以對2個不同指令集的二進制代碼進行相似性度量.而在第2階段采用的局部調用結構匹配算法結合了函數調用圖層面的局部結構信息，考慮了與待匹配函數對存在調用關系的其他函數對的相似程度對待匹配函數對的影響，提高了關聯準確率.在第1階段計算出數值相似度的基礎上，可以對規模較大的待檢測函數集進行初步篩選，再進行較為精確的局部調用結構匹配，提高整體性能.

2 基于神經網絡的函數數值相似度計算

2.1 提取函數數值特征

函數數值特征是指函數中可以進行數值化處理的特征，如指令個數、基本塊數、棧大小等.函數數值特征提取的難點和思路如下：

1) 提取的特征應忽略平臺不同帶來的差異.既使是同一份源碼針對不同平臺編譯得到的二進制文件反匯編后呈現的匯編程序，其指令集、寄存器、尋址方式和函數內控制流圖也存在很大差異.這就要求提取的特征能忽略平臺不同帶來的差異.而比特流、指令集或寄存器名稱等嚴重依賴平臺，因此選擇的特征不能基于這些對象.二進制文件進行反匯編和信息提取后，大部分信息表達為1個函數調用圖、一系列匯編形式的函數和一系列函數控制流圖.經實驗觀察發現，同一份源碼針對不同平臺編譯，函數間調用關系基本保持一致；函數的某些基本屬性，例如調用的字符串，也具有跨平臺特性；至于函數控制流圖，平臺不同可能導致圖的細節發生變化，但某些描述性特征，例如規模大小等不會發生巨大變化.因此，本文主要從函數調用關系、函數基本信息和函數控制流圖信息3個方面入手，提取平臺依賴較弱的特征.

2) 對匯編程序、圖的數值化處理.由于分析的對象是匯編程序和圖，無法直接輸入神經網絡，這就有必要對匯編程序和圖進行數值化處理.匯編程序和圖提供的數值特征眾多，各特征的跨平臺性及區分度也不盡相同.對匯編程序，可以對棧、字符串、特殊指令所占比例等方面提取；對于圖，可以從點邊信息、度信息和路徑信息進行分析.

具體的提取過程如下：

1) 函數調用圖

函數調用圖是1個有向圖，節點表示函數，有向邊表示函數間調用關系.對函數調用圖進行分析，提取該函數被其他函數調用的次數callt和該函數調用其他函數的次數callf，以及去重后次數callt2和callf2，構成調用關系特征.

2) 函數基本屬性

分析函數基本信息，計算棧空間stack、代碼量code、調用字符串個數str和調用的字符串集合strSet.對函數進行指令分析，統計指令個數inst、跳轉指令個數jump、跳轉指令占比jumpp，結合式(1)計算指令熵instEpt和跳轉指令熵jumpEpt，Pk表示(跳轉)指令k的占比，以上特征構成函數基本特征.

(1)

3) 函數控制流圖

1個函數對應1個函數控制流圖(control flow graph, CFG)，圖中每個節點對應函數中的1個基本塊，節點間的有向邊對應基本塊間的跳轉關系.從點邊、度和路徑3個方面對函數控制流圖進行分析.

對函數控制流圖進行點邊分析.計算節點數node和邊數edge；按式(2)計算圖密度density，以上構成CFG圖點邊屬性特征.

(2)

對函數控制流圖進行路徑分析，采用Floyd或Dijkstra算法計算入口基本塊到任意基本塊的最小距離，構造升序距離序列pathList，計算圖的平均路徑長度avePath、圖直徑(即最長路徑)diameter，按式(3)計算圖鏈路效率effect，以上構成CFG圖路徑特征.

(3)

對函數控制流圖進行度分析，統計每個節點的出度、入度，將CFG圖轉化為無向圖，計算無向CFG圖的每個節點的度，構成入度升序序列iList、出度升序序列oList、無向度升序序列uList.由3種度序列，分別計算3種最大度imax,omax,umax和3種平均度ieva,oeva,ueva；由式(1)計算無向圖度的熵uEpt.按式(4)(5)計算圖的聚類系數cluster[15]，其中，c表示節點k的所有鄰居節點構成的無向CFG圖的子圖邊數，dk表示節點k的度,以上構成CFG圖度特征.

(4)

(5)

以上共計31維特征作為1個函數的數值特征.

2.2 計算待匹配函數對的相似度向量

由于本文待解決的是每個待比較的函數對(f,g)的相似性度量問題，不是分類問題，因此神經網絡的輸入不是1個函數的31維特征，而是待比較函數對(f,g)的每維特征的相似度構成的相似度向量.以上提取的31維特征有3種表現形式：數量型、序列型和集合型，本文采用不同的相似度度量方法：

1) 針對序列型特征：pathList,iList,oList,uList.采用式(6)計算待比較函數f和g的序列型特征L1和L2的最長公共子序列(LCS)占比作為相似度[16]:

(6)

其中,c0為0，1之間的1個常量.

2) 針對集合型特征：strSet.計算待比較函數f和g的strSet特征sf和sg的Jaccard系數[17]作為相似度：

(7)

其中,c1為0，1之間的1個常量.

3) 針對26維特征數量型特征.采用式(8)對待比較函數f和g的數量型特征Ff和Fg進行相似度計算:

(8)

其中,c2為0，1之間的1個常量.

這樣便得到了31維特征的相似程度，取值范圍是[0,1]，構成了每個待比較的函數對(f,g)的相似度特征向量.待比較的函數對(f,g)相似程度越高，按以上方法計算得到的特征相似度越高.

2.3 特征選擇

特征選擇是從原始特征中選擇出一些最有效的特征以降低數據集維度的過程，是提高學習算法性能的重要手段.以上31維特征是根據經驗進行選取的，在對未知樣本進行預測之前，應決定哪些特征應該采用、哪些特征應該忽略.本文采用ReliefF算法[18-19]進行特征選擇，同時采用直觀的統計方法輔證特征選擇的合理性.由于神經網絡輸入是相似度向量，因此以相似度向量為分析對象進行特征選擇.

ReliefF算法是一種特征選擇算法，基于特征對近距離樣本的區分能力賦予特征不同的權重.權重越大，表示該特征的分類能力越強，權重小于某個閾值的特征應被移除.本文采用ReliefF算法計算各個特征相似度的重要程度，實驗數據集采用ARM×MIPS的OpenSSL.31個特征的類型和采用ReliefF算法計算31個特征的權重結果如表1和圖2所示.如圖2所示，“·”表示每次迭代對應編號的特征權重，“*”表示20次迭代的平均權重.權重低于0.015的特征，包括指令熵instEpt、跳轉指令熵jumpEpt、度熵uEpt、平均入度ieva、平均出度oeva、最大出度omax、聚類系數cluster、鏈路效率effect，這8個特征對近距離樣本的區分能力不高，將其移除.其中指令熵和跳轉指令熵代表了函數的指令分布情況，這2個特征顯著性不高說明不同函數的指令分布差異性不大.而聚類系數則代表了函數控制流圖中三角結構的密度，這與函數循環結構密度和形狀有關，該特征顯著性不高說明不同函數的分支結構差異性不大.

Table 1 The Table of Weight of Features Based on ReliefF

Fig. 3 Separating capacity of code and omax.圖3 代碼量code和最大出度omax的區分能力示意圖

采用直觀的統計結果輔證特征選擇的合理性.相似度向量的每個元素取值區間是[0,1]，值越大，代表2個待比較函數在該特征上相似程度越高.如果大量正樣本特征取值很高，則認為這一特征是好的特征.本文將0～1區間均分為10個小區間，統計每個小區間正樣本的比例.落入各取值區間的正樣本比例應隨著取值區間的變大而越大.以代碼量特征code和最大出度特征omax為例，考察特征在不同取值區間包含的正樣本比例.如圖3所示，菱形折線表示代碼量code的區分能力.隨著代碼量相似度取值區間的增大，落入對應區間的正樣本比例呈遞增趨勢，說明該特征有較好的區分能力；倒三角折線表示最大出度omax的區分能力，其正樣本比例與特征相似度的取值區間的遞增沒有正相關性，因此不具有良好的區分能力，這與ReliefF算法的結果相對應.

2.4 神經網絡預測

Fig. 5 The local calling structure matching.圖5 局部調用結構匹配示意圖

神經網絡采用反向傳播(back propagation, BP)神經網絡[20]，可以實現輸入和輸出間的任意非線性映射，網絡由輸入層、隱層和輸出層的節點構成，如圖4所示.將篩選得到的23維特征的相似度向量作為神經網絡的輸入，每維特征相似度都從不同方面反映了函數之間的相似性.通過神經網絡整合這些相似度獲得1個值，作為待比較函數對(f,g)的數值相似度.

Fig. 4 The structure of BP neural network.圖4 BP神經網絡結構

3 基于局部調用結構匹配的整體相似度計算

經實驗觀察發現，相比函數內部控制流圖，函數調用圖對平臺和優化選項更具魯棒性.文獻[14]在函數控制流圖層面上采用了基于可信基點的基本塊擴張算法，對函數控制流圖異構現象敏感，關聯效果并不理想.這是由于在圖匹配的過程中，算法不能跳過一小段不匹配的代碼塊，重新找到比較的開始點.這就意味著，一旦有局部異構，其后面的匹配結果全不正確.因此，本文在對平臺和優化選項魯棒性較好的函數調用圖層級上進行結構匹配.

局部調用結構是指在函數調用圖中以待匹配函數為中心，與其有調用關系的函數構成的子圖，按調用關系的跳數可分為1級調用(直接調用)、2級調用等.基于局部調用結構匹配計算整體相似度是指以函數數值相似度為基礎，計算待比較函數對的局部調用子圖的相似程度.本文假設距離待匹配函數越近的函數對匹配的貢獻越大，采用分層構造賦權二分圖求最大權匹配的方法，具體流程如下：

1) 從函數調用圖中截取待比較函數的局部結構信息構成2個結構子圖.

2) 將截取的結構子圖按離待比較函數的跳數分為+1層、+2層等和-1層、-2層等，并按距離跳數賦權重ω+1，ω+2等和ω-1，ω-2等.其中待匹配節點對為0層，權重為ω0.

3) 逆調用方向，從距離待匹配節點對最近+1層開始，將2個節點集抽象為賦權完全二分圖，其中邊權為數值相似度.采用Kuhn-Munkres算法[21]計算該賦權完全二分圖的最大權匹配作為該圖的相似度，并基于節點匹配結果對+2層的節點集構造賦權二分圖，計算最大權匹配，直至到達距離中心節點最遠的一層為止.

4) 順調用方向，具體步驟同3).

5) 計算所有匹配節點的相似度加權均值作為待比較函數的整體相似度.

如圖5所示，計算函數a0和b0的整體相似度.從+1層開始，將由函數a11，a12，a13構成的節點集和由函數b11，b12，b13，b14構成的節點集轉化為賦權二分圖，計算最大權匹配.假設函數a11與函數b11匹配，那么下一步將計算調用函數a11的函數a21，a22構成的節點集和調用函數b11的函數b21構成的節點集的最大權匹配.

理論上局部調用結構的階數越多，附加信息越多，匹配結果應越精確.但事實上，隨著階數的增加，前一層二分圖匹配的誤差會傳遞到后一層，這將導致關聯結果變差，并且階數的增加意味著時間成本的增加.分析局部調用結構的階數對算法時間復雜度的影響，計算第n-1層節點向第n層擴張的時間復雜度.設每層節點向外平均擴張m個節點，第n層共有mn個節點，需要進行mn-1次二分圖匹配，每次匹配的時間復雜度是O(m3)，總共的時間復雜度是O(mn+2)，隨階數指數級增長.因此，在進行局部調用結構匹配時應同時考慮關聯精度和時間成本.實驗表明，2階能夠取得良好的關聯效果.

4 實驗與結果分析

實驗主要驗證VDNS的漏洞關聯性能，所涉及的平臺包括x86，ARM和MIPS.

4.1 實驗設置

1) 實驗設備和實現

實驗所用臺式機配置是Intel?CoreTMi7-4790 CPU @3.60 GHz 3.5 GHz，8 GB內存.在64位Window平臺上采用python語言實現了VDNS.利用反匯編軟件IDA Pro 6.6對二進制文件進行逆向分析，編寫IDA插件進行特征提取；神經網絡采用Matlab R2014b提供的神經網絡工具箱完成.

2) 關聯模式的定義

引入1個概念：關聯模式，它描述了待匹配函數f和g所在的二進制文件F和G的平臺和優化選項等信息.例如，采用針對x86平臺編譯的二進制文件F與針對MIPS平臺編譯的二進制文件G相關聯構成的訓練集訓練神經網絡，記“x86×MIPS”為訓練集的關聯模式.如果應用場景是將x86平臺的二進制文件F中函數f作為漏洞函數，對MIPS平臺的二進制文件G的函數g作漏洞關聯，記“x86×MIPS”為測試集的關聯模式.本文的實驗數據建立在已知測試集的關聯模式的假設之上，采用同關聯模式的神經網絡進行計算.本文將在4.6節驗證即使訓練集和測試集的關聯模式不同，其關聯結果仍可滿足實際需求.

3) 訓練集的構造

本文實驗所用的訓練集采用BusyBox v1.21.1.以x86×MIPS關聯模式的訓練集為例，給出具體的構造過程.將BusyBox v1.21.1源碼針對x86平臺和MIPS平臺進行編譯得到二進制文件F和G.對于F中每一函數f，其在G中同名函數f′即為f真正匹配的函數.取(f,f′)的特征相似度向量為正樣本，標簽為1；在G中隨機取10個函數gi≠f′,i=1,2,…,10，這10個函數對(f,g)的特征相似度向量作為負樣本，標簽為0.正負樣本比例為1∶10.

4) 神經網絡的參數設置

神經網絡的輸入層和輸出層分別含有23個節點和1個節點.隱含層50個節點為經驗值，與實驗的樣本有關，可根據具體情況調節隱含層的節點數.

5) 動態鏈接的函數處理

函數調用圖中某些節點是動態鏈接的函數，二進制文件中不包含其函數體，不能直接對其特征提取.本文實驗中設定涉及動態鏈接函數的函數對的相似度為1個常量.

4.2 評價指標

為了和文獻[14]的結果對比，我們采用文獻[14]所用的評價指標：Rank和Top，定義如下：

設漏洞函數集合為F，待檢測函數集合為G，對F中的某個漏洞函數f，計算f與G中所有函數的相似度.記與漏洞函數f真正匹配的G中函數f′的相似度排名為漏洞函數f的Rank值，Rank值越小表示關聯效果越好，Rank值為1表示關聯效果最好.

統計F中所有漏洞函數的Rank值，如果F中有y%的漏洞函數的Rank值不大于x，記F的Topx值為y%.y%取值范圍為0～1，y%越大表示關聯效果越好.通常用Top1，Top10和Top100描述漏洞函數集合F的整體關聯情況.

4.3 時間復雜度分析

由于本文在計算數值和整體相似度時是將函數兩兩進行比較，時間復雜度是O(nm)，其中n是漏洞函數的個數，m是待檢測的固件函數的個數，這與文獻[14]相同.由于實際應用中漏洞函數個數較少，所以本文方法可以應用于大規模固件函數漏洞檢測.

4.4 跨平臺漏洞關聯實驗

實驗主要驗證該方法能夠在跨平臺場景下有效地漏洞關聯，分為2個部分：二進制文件OpenSSL的函數關聯實驗和真實漏洞函數的關聯實驗.

1) 二進制文件OpenSSL的函數關聯實驗

實驗思路是采用同一份源碼針對不同平臺進行編譯得到2個二進制文件F和G，則與F中函數f真正匹配的函數是G中f的同名函數f′.匹配F的所有函數與G的所有函數，計算F的Top1，Top10和Top100描述整體關聯情況.為了與文獻[14]進行結果對比，測試采用的二進制文件為OpenSSL，版本是v1.0.1f.

圖6展示了關聯模式為ARM×MIPS的Rank值的累計分布函數圖，橫軸表示x，縱軸表示Topx的值.文獻[14]中的實驗結果是Top1=32.1%，Top10=56.1%，Top100=80.0%.從圖6中可見，在相同配置下，該方法計算得到的數值相似度是Top1=39.26%，Top10=69.11%，Top100=83.70%；該方法計算得到的整體相似度是Top1=76.49%，Top10=85.07%，Top100=88.10%.在ARM×MIPS關聯模式下，無論是數值相似度還是整體相似度，本文的實驗結果都優于文獻[14].由于文獻[14]沒有給出OpenSSL在其他關聯模式下的實驗結果，我們僅給出本文方法的實驗結果，如表2所示，可見關聯效果良好.

Fig. 6 Cumulative distribution function of ARM×MIPS.圖6 ARM×MIPS關聯模式下的累計分布圖

PatternSimilarityTypeTop1Top10Top100ARM×MIPSResultsin[14]32.1056.1080.00ARM×MIPSNumericalSimilarity39.2669.1183.70ARM×MIPSOverallSimilarity76.4985.0788.10MIPS×x86NumericalSimilarity38.3365.2580.85MIPS×x86OverallSimilarity71.6181.4386.39x86×ARMNumericalSimilarity32.2662.8480.42x86×ARMOverallSimilarity78.9687.3291.97ARM×x86NumericalSimilarity32.9261.1676.68ARM×x86OverallSimilarity76.1485.4489.82MIPS×ARMNumericalSimilarity36.1565.1484.80MIPS×ARMOverallSimilarity75.5483.1289.12x86×MIPSNumericalSimilarity33.6863.4582.18x86×MIPSOverallSimilarity74.2383.9187.90

2) 真實漏洞函數的關聯實驗

為了說明該方法對真實漏洞函數的關聯能力，本文收集了二進制文件OpenSSL中5個漏洞函數，具體信息如表3所示.對二進制文件OpenSSL進行關聯，計算不同跨平臺關聯模式下5個漏洞函數的Rank值；實驗表明，除了漏洞函數X509_verify之外，其他4個漏洞函數的數值相似度Rank值保持在10以內，整體相似度的Rank值為1，關聯效果良好，具體如表4所示.

Table 3 Five Vulnerability Functions in OpenSSL

Table 4 Search Results of Five Vulnerability Functions in OpenSSL

表4 OpenSSL的5個漏洞函數的Rank值列表

4.5 在真實固件中關聯真實漏洞的關聯實驗

實驗主要驗證該方法在真實情況下，即采用真實漏洞函數在真實固件中進行關聯，具有良好的關聯效果.實驗過程如下：

1) 選擇D-Link路由器固件中常見的4個漏洞函數，如表5所示：

Table 5 Four Vulnerability Functions in D-Link Router Firmware

表5 D-Link路由器固件中4個漏洞函數列表

2) 從D-Link路由器固件中隨機抽選372個MIPS平臺的固件，篩選條件為文件名包含“cgi”和“web”子串的ELF文件，共計得到305個二進制文件共74 006個函數，其中漏洞函數同名函數個數n分別為29，28，51，58；

Fig. 7 Searching results of four vulnerability functions in routers.圖7 4個漏洞函數在路由器固件中的關聯結果

3) 分別計算1)中每個漏洞函數與這74 006個函數的數值相似度并進行排序.

設74 006個函數中與漏洞函數同名的函數個數為n，將得分最高的前n個函數中同名函數的個數m作為實驗結果的評價指標.理想情況下，得分最高的前n個函數中同名函數的個數應該為n，即這n個同名函數的數值相似度在74 006個函數中排在了前n位.m取值在0～n之間，m越接近n說明關聯效果越好.實驗表明，得分最高的前n個函數中同名函數個數為29，22，37，49，如圖7所示.以漏洞函數alpha_auth_check為例，其同名函數個數為29，在進行漏洞關聯過程中，所有同名函數在74 006個函數中排到了前29，表明關聯效果良好.

4.6 已知關聯模式對關聯結果的影響

4.5節的實驗結果建立在已知關聯模式的條件下，但在實際應用中存在未知關聯模式的情況.本實驗將驗證訓練集和測試集關聯模式不同時，包括平臺(ARM，MIPS，x86)不同和優化選項(-O0，-O1，-O2，-O3)不同，該方法仍能保持良好的關聯效果.測試集的關聯模式是ARM-O0×MIPS-O2，實驗將采用不同關聯模式的訓練集訓練好的神經網絡計算表3中5個漏洞函數的數值相似度的Rank值.

表6表示優化選項的關聯模式為-O0×-O2時，改變平臺的關聯模式的實驗結果.第1列表示漏洞函數的平臺，項目欄表示待關聯函數的平臺，表格數據表示表3中5個漏洞函數的數值相似度的Rank值.例如行1、列4的表格內容是1,1,1,1,2，這表示訓練集的關聯模式為ARM-O0×x86-O2，所在的二進制文件平臺是ARM、優化選項是-O0的5個漏洞函數，在平臺是MIPS、優化選項為-O2的二進制文件OpenSSL中的關聯結果分別是1,1,1,1,2.黑體結果表示訓練集與測試集關聯模式相同的關聯結果.

Table 6 Search Results for Different Platforms

通過觀察表6可以發現，即使訓練集與測試集關聯模式不同，關聯結果并沒有發生很大變化，Rank值依然保持在21以內.這就表明即使平臺關聯模式未知，本文提出的算法仍能獲得良好的關聯效果.

表7表示平臺的關聯模式為-O0×-O2時改變優化選項的關聯模式的實驗結果.其中，第1列表示漏洞函數的優化選項，項目欄表示待關聯函數的優化選項，表中數據表示表3中5個漏洞函數的數值相似度的Rank值.結果表明，即使訓練集與測試集優化選項不同，關聯結果并沒有發生很大變化，Rank值依然保持在20以內.這就表明即使優化選項關聯模式未知，本文提出的算法仍能獲得良好的關聯效果.

Table 7 Searching Results for Different Optimization Options

以編號為4的漏洞函數為例,相比黑體結果，采用與測試集不同關聯模式的訓練集訓練的神經網絡計算的排名略有下降.這就表明在進行關聯前，如果能夠識別二進制文件的平臺和優化選項，將一定程度提高關聯的準確率.

5 結束語

本文提出一種基于神經網絡和局部調用結構匹配的固件漏洞關聯方法，該方法以函數為最小關聯單元，較為全面地提取了函數在函數調用圖、函數基本屬性和函數控制流圖3方面信息，同時，這些特征的提取不依賴指令集，具有一定的跨平臺能力，可以對2個不同指令集的二進制代碼進行相似程度度量.局部調用結構匹配考慮了與待匹配函數有調用關系的其他函數相似程度的影響，提高了準確率.

本文在二進制文件OpenSSL上進行跨平臺漏洞關聯實驗，相比已有方法，該方法在同一固件上性能指標Top1從32.1%提高至76.49%；采用5個真實漏洞函數對二進制文件OpenSSL進行關聯時，整體相似度的Rank值均為1.最后，采用4個真實的漏洞函數在372個D-Link路由器固件上進行關聯實驗，結果表明該方法具有良好的關聯效果.下一步工作主要集中于5個方面：

1) 將其他諸如SVM、決策樹等機器學習算法應用于代碼相似性檢測，并分析其優缺點.

2) 識別二進制文件的平臺和編譯優化選項，在進行漏洞關聯前確定關聯模式，提高關聯準確率.

3) 實際應用中，判定閾值往往根據特定的實驗數據經驗獲取.不同關聯模式下其相似度的數值分布不同，經驗選取的閾值不能靈活地適應不同關聯模式的需求.下一步將研究閾值的確定方法.

4) 在對動態鏈接庫的處理上，本文在實驗中設定動態鏈接的函數的相似度為1個常量.下一步的工作可以通過分析其函數體所在的動態鏈接庫文件進行函數特征提取，提高關聯準確率.

5) 本文方法可以應用于大規模固件函數同源性檢測，時間復雜度是O(n2).為了減少時間成本，可以采用時間復雜度為O(n)的聚類算法進行提速，如LSH.

[1]Open Web Application Security Project. OWASP Internet of Things Project (Top 10 IoT Vulnerabilities (2014) Project)[EB/OL]. (2016-02-05)[2016-03-10]. https://www.owasp.org/ index.php/OWASP_Internet_of_Things_Top_Ten_Project#tab=Top_10_IoT_Vulnerabilities__282014_29

[2]Knownsec. A statistical analysis report about the back door of D-Link by ZoomEye.org[EB/OL]. (2013-10-28)[2016-09-05]. http://blog.knownsec.com/2013/10/zoomeye-org關于d-link后門的統計分析報告(知道創宇. ZoomEye.org關于D-Link后門的統計分析報告[EB/OL]. (2013-10-28)[2016-09-05]. http://blog.knownsec.com/2013/10/zoomeye-org關于d-link后門的統計分析報告)

[3]Myles G, Collberg C. K-gram based software birthmarks[C] //Proc of the 20th ACM Symp on Applied Computing. New York: ACM, 2005: 314-318

[4]Kolter J Z, Maloof M A. Learning to detect malicious executables in the wild[C] //Proc of the 10th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2004: 470-478

[5]Jin W, Chaki S, Cohen C, et al. Binary function clustering using semantic hashes[C] //Proc of Int Conf on Machine Learning & Applications. Piscataway, NJ: IEEE, 2012: 386-391

[6]David Y, Yahav E. Tracelet-based code search in executables[J]. ACM Sigplan Notices, 2014, 49(6): 349-360

[7]Gao D, Reiter M K, Song D. BinHunt: Automatically finding semantic differences in binary programs[C] //Proc of the 10th Int Conf on Information and Communications Security. Berlin: Springer, 2008: 238-255

[8]Lakhotia A, Preda M D, Giacobazzi R. Fast location of similar code fragments using semantic “juice”[C] //Proc of ACM Sigplan Program Protection and Reverse Engineering Workshop. New York: ACM, 2013: 1-6

[9]Ming J, Pan M, Gao D. iBinHunt: Binary hunting with inter-procedural control flow[C] //Proc of the 15th Information Security and Cryptology. Berlin: Springer, 2012: 92-109

[10]Ng B H, Prakash A. Expose: Discovering potential binary code re-use[C] //Proc of the 37th Annual Computer Software and Applications Conf (COMPSAC’13). Piscataway, NJ: IEEE, 2013: 492-501

[11]Xie Yuqiang, Zeng Ying, Shu Hui. Improved graph-based executable file comparison algorithm[J]. Computer Engineering and Design, 2007, 28(2): 257-260(謝余強, 曾穎, 舒輝. 改進的基于圖的可執行文件比較算法[J]. 計算機工程與設計, 2007, 28(2): 257-260)

[12]Zeng Ming, Zhao Rongcai, Wang Xiaoqin, et al. A binary patch analysis technique based on the disassembly technology[J]. Computer Science, 2006, 33(10): 283-287(曾鳴, 趙榮彩, 王小芹, 等. 一種基于反匯編技術的二進制補丁分析方法[J]. 計算機科學, 2006, 33(10): 283-287)

[13]Egele M, Woo M, Chapman P, et al. Blanket execution: Dynamic similarity testing for program binaries and components[C] //Proc of the 23rd USENIX Conf on Security Symposium. Berkeley, CA: USENIX Association, 2014: 303-317

[14]Pewny J, Garmany B, Gawlik R, et al. Cross-architecture bug search in binary executables[C] //Proc of IEEE Symp on Security and Privacy. Piscataway, NJ: IEEE, 2015: 709-724

[15]Watts D J, Strogatz S H. Collective dynamics of “small-world” networks[J]. Nature, 1998, 393(6684): 440-442

[16]Bergroth L, Hakonen H, Raita T. A survey of longest common subsequence algorithms[C] //Proc of the 5th Int Symp on String Processing and Information Retrieval. Berlin: Springer, 2000: 39-48

[17]Hamers L, Hemeryck Y, Herweyers G, et al. Similarity measures in scientometric research: The Jaccard index versus Salton’s cosine formula[J]. Information Processing & Management, 1989, 25(3): 315-318

[18]Kononenko I. Estimating attributes: Analysis and extensions of RELIEF[C] //Proc of the 5th European Conf on Machine Learning. Berlin: Springer, 1994: 171-182

[19]Robnik-Sikonja M, Kononenko I. Theoretical and empirical analysis of ReliefF and RReliefF[J]. Machine Learning, 2003, 53(1/2): 23-69

[20]Hecht-Nielsen R. Theory of the back propagation neural network[J]. Neural Networks, 1989, 1(1): 593-605

[21]Bourgeois F, Lassalle J C. An extension of the Munkres algorithm for the assignment problem to rectangular matrices[J]. Communications of the ACM, 1971, 14(12): 802-804

Chang Qing, born in 1991. Master candidate. Received her BSc degree from University of Electronic and Technology of China in 2014. Her main research interests include IOT security, industrial control system security.

Liu Zhongjin, born in 1988. Received his PhD degree from Tsinghua University in 2014. Researcher in the National Computer Network Emergency Response Technical TeamCoordination Center of China. His main research interests include computer and network security, network virtualization, future Internet architecture.

Wang Mengtao, born in 1989. Master candidate. Received his BSc degree from Hainan University in 2014. His main research interests include IOT security.

Chen Yu, born in 1988. PhD candidate. Received his MSc degree from Beihang University in 2014. His main research interests include industrial control system security.

Shi Zhiqiang, born in 1970. Received his PhD degree from the Institute of Software, Chinese Academy of Sciences in 2001. Senior engineer in the Institute of Information Engineering, Chinese Academy of Sciences. His main research interests include industrial control system security, cyber security, etc.

Sun Limin, born in 1966. Received his BSc, MSc, and PhD degrees from National University of Defense Technology in 1988, 1995, and 1998 respectively. Associate professor in the Institute of Information Engineering, Chinese Academy of Sciences. His main research interests include IOT security.

VDNS: An Algorithm for Cross-Platform Vulnerability Searching in Binary Firmware

Chang Qing1,2,3, Liu Zhongjin4, Wang Mengtao1,2,3, Chen Yu1,2,3, Shi Zhiqiang1,2,3, and Sun Limin1,2,3

1(BeijingKeyLaboratoryofIOTInformationSecurity,InstituteofInformationEngineering,ChineseAcademyofSciences,Beijing100093)2(InstituteofInformationEngineering,ChineseAcademyofSciences,Beijing100093)3(UniversityofChineseAcademyofSciences,Beijing100049)4(NationalComputerNetworkEmergencyResponseTechnicalTeamCoordinationCenterofChina,Beijing100029)

Nowadays, most IOT vendors use the similar code to compile firmware for devices based on various CPU architectures. However, the prior vulnerability searching methods are limited to the same platform, which can’t be directly extended to the cross-platform case, and the cross-platform studies have just started. In this paper, we propose an algorithm to search vulnerabilities of firmware in a cross-platform model based on neural network and local calling structure matching. Firstly we extract the selected compared features from the call graphs, the basic attributes and the control flow graphs of the two compared functions as the input of the neural network, and gain the calculated results. Then we match the call sub-graphs of the compared functions with the results of the previous step as weight to improve the accuracy. The experimental results on the open source code OpenSSL demonstrate our method has better performance than the prior cross-platform vulnerability searching method with theTop1 increasing from 32.1% to 76.49% in the searching pattern from ARM to MIPS. The searching ranks of the common five vulnerabilities in OpenSSL are all No.1 rank. Moreover, we search the common four vulnerabilities in the firmware of the 372 types of D-Link routers and the results show good performance too.

cross-platform; vulnerability search; feature selection; neural network; bipartite matching

2016-06-16；

2016-08-11

中國科學院戰略性先導科技專項課題(XDA06040101)；國家重點研發計劃(2016YFB0800202)；國家自然科學基金項目(U1536107)

石志強(shizhiqiang@iie.ac.cn)

TP309.1

Chen Zhifeng, born in 1986. PhD. His main research interests include information security and trust computing.

This work was supported by the State Priority Research Program of the Chinese Academy of Sciences (XDA06040101), the National Key Technology Research and Development Program of China (2016YFB0800202), and the National Natural Science Foundation of China (U1536107).