肖睿卿，祝躍飛，劉勝利，蘆斌

基于候選函數(shù)組的固件間函數(shù)對應(yīng)關(guān)系構(gòu)建方法

肖睿卿，祝躍飛，劉勝利，蘆斌

（數(shù)學(xué)工程與先進(jìn)計算國家重點(diǎn)實驗室，河南 鄭州 450001）

由于固件的特點(diǎn)，傳統(tǒng)二進(jìn)制比對方法在匹配函數(shù)節(jié)點(diǎn)傳播匹配的過程中易產(chǎn)生誤匹配。針對匹配函數(shù)傳播效果不理想的問題，設(shè)計了基于候選函數(shù)組的函數(shù)對應(yīng)關(guān)系構(gòu)建方法，并引入了函數(shù)層局部網(wǎng)絡(luò)匹配的概念。然后，結(jié)合3種候選函數(shù)組構(gòu)造策略形成候選函數(shù)組構(gòu)造方法及候選函數(shù)組匹配方法，并分析了時間開銷。最后，基于所提方法實現(xiàn)了原型系統(tǒng)，并與Bindiff進(jìn)行比較。通過隨機(jī)抽樣和人工核對，所提方法匹配結(jié)果的86.04%與Bindiff匹配結(jié)果一致，所提方法匹配結(jié)果的11.3%可以修正Bindiff的匹配錯誤，緩解了傳播帶來的誤匹配問題。

固件；二進(jìn)制比對；函數(shù)匹配；候選函數(shù)組

1 引言

二進(jìn)制代碼比對旨在確定兩段代碼（基本塊、函數(shù)、程序）是否相似[1]，也稱作二進(jìn)制比對。文獻(xiàn)[2-5]的工作表明，二進(jìn)制比對技術(shù)具有廣泛的應(yīng)用場景，可用于固件補(bǔ)丁/漏洞比對[4]、軟件抄襲檢測[6]、惡意軟件檢測[7]等領(lǐng)域。

本文研究鄰近版本固件間構(gòu)建函數(shù)對應(yīng)關(guān)系的方法，對固件安全性進(jìn)行分析，此問題屬于二進(jìn)制比對范疇。文獻(xiàn)[1]將二進(jìn)制比對的粒度分為基本塊、函數(shù)、程序三級；輸入形式包括一對一、一對多、多對多；比對形式包括同構(gòu)、等價、相似3種。依據(jù)此條件，本文研究內(nèi)容可以描述為，對于輸入兩個固件程序，以一定方法判別每個固件中的每一個函數(shù)在另一個固件中是否有函數(shù)與之對應(yīng)（也稱為匹配）。對應(yīng)可以理解為，即使是本身發(fā)生了一定幅度修改的補(bǔ)丁函數(shù)，通過固件比對方法也可以在鄰近版本的固件之間（補(bǔ)丁前后）判定補(bǔ)丁前后的兩個函數(shù)最為相似。

從現(xiàn)有研究工作看，二進(jìn)制比對大體分為兩個步驟。

1) 函數(shù)對相似性計算。通過各類特征判斷一對函數(shù)的相似性。

2) 匹配節(jié)點(diǎn)傳播。在各文獻(xiàn)（如文獻(xiàn)[4-11]等）中稱為選擇器、過濾器等，主要目的是提供待計算相似性的函數(shù)對。通過不同的方法（如基于固定點(diǎn)傳播算法）選擇一組可能匹配的函數(shù)對，而后計算相似性。目的是避免全局范圍內(nèi)尋找待匹配函數(shù)對，借此減少計算量。

多數(shù)研究者對于二進(jìn)制比對的研究聚焦于函數(shù)對相似性計算方法，特別是聚焦于函數(shù)本身的信息提取以表達(dá)函數(shù)自身；而對匹配節(jié)點(diǎn)的傳播方法關(guān)注較少。

近年來二進(jìn)制比對的研究聚焦于跨指令集比對和深度學(xué)習(xí)，并未聚焦于匹配節(jié)點(diǎn)傳播問題。文獻(xiàn)[3]采用部分統(tǒng)計特征和結(jié)構(gòu)特征表示控制流圖（CFG，control flow graph）中的基本塊。通過譜聚類形成質(zhì)心和碼本。利用質(zhì)心計算編輯距離，以代表該函數(shù)CFG。文獻(xiàn)[4]沿用上述特征但不再使用碼本表示CFG。在使用特定維度向量的基礎(chǔ)上，將CFG周邊具有調(diào)用關(guān)系的圖的向量以一定權(quán)重整合入自身，通過神經(jīng)網(wǎng)絡(luò)，訓(xùn)練出合適的權(quán)重。其特征整合了函數(shù)所在局部子圖的特征，可以更好地用以區(qū)分函數(shù)。文獻(xiàn)[5]利用中間語言模擬執(zhí)行函數(shù)，提取函數(shù)中分支指令的值及系統(tǒng)調(diào)用相關(guān)信息，以代表函數(shù)語義。然后，利用最大公共子序列進(jìn)行匹配。文獻(xiàn)[8]利用中間語言對基本塊的輸入輸出對進(jìn)行捕獲，判別函數(shù)語義是否一致。文獻(xiàn)[9]使用函數(shù)調(diào)用數(shù)、邏輯指令等數(shù)字特征以及結(jié)構(gòu)特征，結(jié)合機(jī)器學(xué)習(xí)的KNN算法，降低匹配時間代價，完成匹配。

以結(jié)構(gòu)化比對為代表的早期研究提出傳播算法嘗試解決函數(shù)對應(yīng)關(guān)系構(gòu)建問題，但其測試用例程序規(guī)模較小，相關(guān)實驗無法暴露其在固件比對上的缺陷。文獻(xiàn)[10]首次將CFG用于二進(jìn)制比對，之后基于該方法出現(xiàn)了二進(jìn)制比對工具Bindiff。文獻(xiàn)[11]在此基礎(chǔ)上，引入了屬性的概念，并且提出了基于固定點(diǎn)和傳播的方法進(jìn)行匹配。文獻(xiàn)[12]對指令歸一化處理后進(jìn)行指令排序，以此解決匹配過程中發(fā)現(xiàn)指令順序變化的問題。文獻(xiàn)[13]提取了匯編指令的操作碼以及數(shù)據(jù)常量，該文僅提取CFG中大小為的圖或圖的子圖，減少了提取量。文獻(xiàn)[14]使用Bindiff完成初步匹配，對未匹配函數(shù)節(jié)點(diǎn)使用圖編輯距離（GED）和Hungarian算法進(jìn)行匹配。

由于固件相較于普通應(yīng)用程序函數(shù)數(shù)量較大，特別是網(wǎng)絡(luò)設(shè)備固件，以Bindiff為代表的傳統(tǒng)二進(jìn)制比對方法直接應(yīng)用于固件易出現(xiàn)預(yù)期外的誤匹配。其原因主要是傳播算法對匹配準(zhǔn)確性有較高的依賴，函數(shù)匹配算法帶來的錯誤被傳播算法放大。另外，固件函數(shù)數(shù)量大，往往存在一個函數(shù)與多個函數(shù)相似接近，如果基于匹配節(jié)點(diǎn)傳播的過程選擇待比較函數(shù)對較少，則可能導(dǎo)致遺失真正匹配的函數(shù)節(jié)點(diǎn)；如果選擇過多的待比較函數(shù)對，則會導(dǎo)致時間開銷較大和誤匹配。

為解決上述問題，本文設(shè)計了基于候選函數(shù)組的函數(shù)間對應(yīng)關(guān)系構(gòu)建方法以提高函數(shù)匹配準(zhǔn)確率，本文工作如下。

1) 設(shè)計了基于候選函數(shù)組的函數(shù)間對應(yīng)關(guān)系構(gòu)建方法，補(bǔ)充了適用于固件比對場景的函數(shù)匹配的定義。

2) 提出候選函數(shù)組構(gòu)造方法。該方法結(jié)合了基于統(tǒng)計特征、調(diào)用關(guān)系和函數(shù)地址分布的候選函數(shù)組構(gòu)造策略。此外，分析了候選函數(shù)組構(gòu)造帶來的時間開銷。

3) 提出基于候選函數(shù)組的節(jié)點(diǎn)匹配方法。使用低時間開銷的指令統(tǒng)計特征提高函數(shù)對匹配的效率，利用局部網(wǎng)絡(luò)特征提高節(jié)點(diǎn)對匹配準(zhǔn)確率，并提供候選函數(shù)組節(jié)點(diǎn)匹配結(jié)果篩選策略。

4) 使用本文方法形成原型系統(tǒng)，對樣本固件進(jìn)行二進(jìn)制比對。分析了各個候選函數(shù)組構(gòu)造策略對匹配工作產(chǎn)生的影響，并與Bindiff5[23]的匹配結(jié)果進(jìn)行比對。

2 模型建立

2.1 相關(guān)概念

在固件升級的場景下，由于固件函數(shù)數(shù)量過大，基于上述概念構(gòu)建函數(shù)對應(yīng)關(guān)系會產(chǎn)生問題。例如，圖1(a)指令序列與圖1(b)完全一致（Bindiff認(rèn)為這對函數(shù)匹配），但實際圖1(a)應(yīng)與結(jié)構(gòu)不同的圖1(c)匹配。

此例反映了兩個問題：一是基于函數(shù)本身進(jìn)行匹配分析有局限性；二是函數(shù)指令序列相同（基于指令提取的特征值必相同），并不代表函數(shù)匹配。推廣而之，即使兩個函數(shù)本身相似性最高甚至語義等價，也不能表示這對函數(shù)有對應(yīng)關(guān)系，即匹配。

因此，需要補(bǔ)充限定條件，現(xiàn)引入相關(guān)概念如下。

圖1 兩版本固件的3個函數(shù)控制流圖

Figure 1 Three CFG of two firmwares with different version

函數(shù)匹配并不僅僅有層局部網(wǎng)絡(luò)匹配。但層局部網(wǎng)絡(luò)匹配，是現(xiàn)行條件下可以給出嚴(yán)格定義的一種情況。

2.2 匹配流程

本文采用二進(jìn)制文件匹配流程如圖2所示，算法表示如算法1。

首先，從待比較的二進(jìn)制文件中挑選函數(shù)節(jié)點(diǎn)構(gòu)造候選函數(shù)集合，如果兩個候選函數(shù)集合具有相似性，則生成候選函數(shù)組；然后，進(jìn)行候選函數(shù)組匹配操作，主要針對候選函數(shù)組內(nèi)的函數(shù)進(jìn)行相似性分析，并從中篩選出函數(shù)匹配結(jié)果。重復(fù)上述過程，直到?jīng)]有新的匹配結(jié)果產(chǎn)生。

算法1 二進(jìn)制文件比對算法

輸入 二進(jìn)制文件,的函數(shù)調(diào)用圖G,G；已匹配節(jié)點(diǎn)集合oldmatchset

輸出 匹配節(jié)點(diǎn)集合matchset

過程1 二進(jìn)制文件比對流程

1) matchset =old_matchset

2) DO{

3) (Ca,Ca)get_ca (matchset,G,G)

4) //獲取候選函數(shù)組

5) new_matchset=math_ca(Ca,Ca)

6) //獲取新匹配結(jié)果集合

7) FOREACH node_pair in new_matchset DO

8) matchsetappend(node_pair)

9) END

10) }WHILE nematchset is empty

11) END//無新增匹配節(jié)點(diǎn)出現(xiàn)則結(jié)束比對

12) RETURN matchset

候選函數(shù)組構(gòu)造：目的是從大量函數(shù)中選擇部分具有關(guān)聯(lián)性的函數(shù)用于后續(xù)分析，避免全局性的比對，借此減少工作量。此階段工作側(cè)重于研究匹配節(jié)點(diǎn)傳播方法，即利用已有的匹配結(jié)果，挑選候選函數(shù)集合。

圖2 二進(jìn)制文件匹配流程

Figure 2 Binary file matching process

候選函數(shù)組匹配：通過對候選函數(shù)組所有的函數(shù)對進(jìn)行相似性分析，計算相似度，而后，根據(jù)相似度篩選出函數(shù)匹配的結(jié)果。其中，使用層局部網(wǎng)絡(luò)匹配的概念輔助函數(shù)匹配工作，并研究匹配結(jié)果篩選策略，用以挑選最優(yōu)匹配結(jié)果。

3 候選函數(shù)組構(gòu)造方法

候選函數(shù)組構(gòu)造的目的是利用已有匹配結(jié)果，確定下一步匹配工作范圍。由于候選函數(shù)組是由候選函數(shù)集合構(gòu)成的二元組，對兩個待比較文件采用相同的候選函數(shù)集合構(gòu)造方法即可。如果兩個候選函數(shù)集合具備一定的相似性（如集合內(nèi)函數(shù)數(shù)量、函數(shù)平均長度近似），即可形成候選函數(shù)組。本節(jié)重點(diǎn)是從候選函數(shù)集合構(gòu)建的角度進(jìn)行說明，對于集合相似性不再贅述。

3.1 候選函數(shù)組構(gòu)造流程

單輪次的候選函數(shù)組構(gòu)建流程如圖3所示，使用符號如前文所述。其中，G,G表示二進(jìn)制文件的FCG圖，SM表示匹配節(jié)點(diǎn)集合，SLM表示上一輪匹配的匹配節(jié)點(diǎn)集合，F(xiàn)g表示策略選擇標(biāo)識（Fg不為負(fù)），Cagp表示構(gòu)造的候選函數(shù)組集合。

圖3 單輪次的候選函數(shù)組構(gòu)建流程

Figure 3 Single round of candidate function group construction process

3.2 基于統(tǒng)計特征構(gòu)建候選函數(shù)組

候選函數(shù)組的構(gòu)造基于已函數(shù)匹配節(jié)點(diǎn)。若沒有函數(shù)匹配節(jié)點(diǎn)，應(yīng)當(dāng)使用基于統(tǒng)計特征構(gòu)建候選函數(shù)組的策略，篩選特征特征值相同或相似的節(jié)點(diǎn)以構(gòu)建候選函數(shù)組。

本文選擇的特征為函數(shù)長度、基本塊數(shù)、子節(jié)點(diǎn)數(shù)、被調(diào)用次數(shù)，并依照上述次序?qū)瘮?shù)進(jìn)行排序，選取特征值相同的函數(shù)構(gòu)建候選函數(shù)組。以上統(tǒng)計特征，特征值越大，同一文件內(nèi)出現(xiàn)函數(shù)具有相似特征的可能性越小。

統(tǒng)計特征本身不像其他兩種方法具備傳播能力，即從已匹配節(jié)點(diǎn)關(guān)聯(lián)其他節(jié)點(diǎn)能力，因此不依賴已匹配節(jié)點(diǎn)也可工作。統(tǒng)計特征是對函數(shù)部分語義信息的提取，相較于全函數(shù)匹配，運(yùn)算量更小、篩選速度快。在篩選過程中，應(yīng)當(dāng)盡量避免同文件內(nèi)特征相同的函數(shù)加入候選組，這會對后續(xù)分析帶來干擾。

當(dāng)基于調(diào)用關(guān)系和地址分布不產(chǎn)生新的匹配節(jié)點(diǎn)時，可考慮再次使用基于統(tǒng)計特征來構(gòu)建候選函數(shù)組。但匹配后期的剩余函數(shù)以短小函數(shù)為主，將存在大量同文件內(nèi)函數(shù)相似的情況，實際效果可能不夠理想。

本文基于統(tǒng)計特征構(gòu)建候選函數(shù)組主要是為了替代人工提供初期的匹配節(jié)點(diǎn)，給后續(xù)的傳播類算法提供基礎(chǔ)，因此并不追求利用統(tǒng)計特征解決全部匹配問題。使用統(tǒng)計特征篩選初始匹配節(jié)點(diǎn)的過程中，候選函數(shù)集合包含函數(shù)節(jié)點(diǎn)的數(shù)量以及篩選函數(shù)節(jié)點(diǎn)的長度下限值是需要討論的。

對基于特征篩選的候選函數(shù)集合，其集合內(nèi)節(jié)點(diǎn)數(shù)量最大值（后文以表示）的選擇，將影響初始匹配節(jié)點(diǎn)的生成量，進(jìn)而對后續(xù)分析的時耗產(chǎn)生影響。實驗表明，基于統(tǒng)計特征策略構(gòu)建候選函數(shù)組，其數(shù)量限定為100時實驗效果最好。

對于函數(shù)長度下限的設(shè)定，則將影響函數(shù)匹配的準(zhǔn)確率。在代碼中修改同樣數(shù)量的寄存器、操作碼，對于長函數(shù)而言，修改量所占百分比低于短函數(shù)。這意味著同等數(shù)量的修改，對長函數(shù)而言影響更小。因此本文基于統(tǒng)計特征的匹配過程中，特征值越大越可靠。

此外，實驗使用候選函數(shù)長度下限為50條指令。固件函數(shù)數(shù)量較大，即使構(gòu)建候選函數(shù)組的過程中達(dá)到候選函數(shù)數(shù)量限制，所選函數(shù)的長度遠(yuǎn)大于長度限制，不影響后續(xù)分析，因此本文對候選函數(shù)長度不做實驗進(jìn)行分析。

3.3 基于調(diào)用關(guān)系構(gòu)建候選函數(shù)組

3.3.1 基于父子節(jié)點(diǎn)的構(gòu)建候選函數(shù)組

6) 重復(fù)步驟2)~步驟5)，將生成的候選函數(shù)組匯總，并輸出。

基于子節(jié)點(diǎn)已匹配的候選函數(shù)組構(gòu)建策略與上述流程類似，區(qū)別僅在于，候選函數(shù)集合是上輪匹配節(jié)點(diǎn)的子節(jié)點(diǎn)構(gòu)成的集合。

文獻(xiàn)[11]提出針對已匹配函數(shù)節(jié)點(diǎn)的子節(jié)點(diǎn)進(jìn)行相似性分析的方法。實際上，這是較為可靠的分析方法，這種傳播方法將節(jié)點(diǎn)周邊局部網(wǎng)絡(luò)的信息間接融入分析流程；若子函數(shù)語義一致，計算子節(jié)點(diǎn)相似性的過程中可以不再進(jìn)行局部網(wǎng)絡(luò)的相似性分析。

并沒有文獻(xiàn)提出利用已經(jīng)匹配函數(shù)節(jié)點(diǎn)分析其父節(jié)點(diǎn)的思路。此法同樣可行，但分析難度較前者略大。因為匹配函數(shù)的子節(jié)點(diǎn)易做到一一對應(yīng)，便于候選函數(shù)組構(gòu)造分析。但函數(shù)父節(jié)點(diǎn)常難以找到對應(yīng)關(guān)系，在構(gòu)造候選函數(shù)組時易包含較多不匹配節(jié)點(diǎn)，后續(xù)的候選函數(shù)組匹配工作負(fù)擔(dān)相對大。但匹配函數(shù)節(jié)點(diǎn)的父函數(shù)集合，仍是一種降低匹配量的思路，可以用作構(gòu)造候選函數(shù)組。

實驗結(jié)果表明，基于已匹配節(jié)點(diǎn)的父節(jié)點(diǎn)構(gòu)造候選函數(shù)組，最終貢獻(xiàn)的匹配節(jié)點(diǎn)量遠(yuǎn)大于利用已匹配節(jié)點(diǎn)子節(jié)點(diǎn)的策略貢獻(xiàn)的匹配節(jié)點(diǎn)量。

3.3.2 基于兄弟節(jié)點(diǎn)構(gòu)建候選函數(shù)組

算法2 基于兄弟節(jié)點(diǎn)構(gòu)建候選函數(shù)的算法

輸出 候選函數(shù)組集合newca

2) //提取所有已匹配節(jié)點(diǎn)對

3) Son_set = get_son_matched(1,2,G,G)

4) //獲取匹配節(jié)點(diǎn)對的已匹配子節(jié)點(diǎn)

5) FOREACH (fs1, fs2) in Sonset DO

6) (Ca, Ca) = get_pa(fs1, fs2,G,G)

7) //獲取匹配子節(jié)點(diǎn)的父節(jié)點(diǎn)集合

8) new_caappend (Ca, Ca>)

9) // 錄入候選函數(shù)組集合

10) END

11) Pa_set = get_pa_matched (1,2)

12) //獲取匹配節(jié)點(diǎn)對的父節(jié)點(diǎn)

13) FOREACH (fp1, fp2) in Pa_set DO

14) (Ca, Ca) = get_son(fp1, fp2,G,G)

15) //獲取匹配父節(jié)點(diǎn)的子節(jié)點(diǎn)集合

16) new_ca) append (, Ca>)

17) // 錄入候選函數(shù)組集合

18) END

19) END

20) RETURN newca

此策略的設(shè)計基于如下考慮。理論上，只要反復(fù)判別已匹配節(jié)點(diǎn)的父子節(jié)點(diǎn)集合是否會出現(xiàn)新的匹配點(diǎn)，就可以完成基于調(diào)用關(guān)系的匹配工作。但實際上，由于匹配工作是基于候選函數(shù)集合進(jìn)行的，如果候選函數(shù)集合中存在無法區(qū)分的相似節(jié)點(diǎn)（同文件內(nèi)的相似函數(shù)），則策略上會放棄匹配這種節(jié)點(diǎn)，以避免產(chǎn)生誤匹配或由于相似度過于接近以至無法選擇匹配結(jié)果的問題。此時，若后期成功匹配了一個早期被放棄的相似節(jié)點(diǎn)，那么同文件內(nèi)相似節(jié)點(diǎn)應(yīng)當(dāng)重新嘗試尋找匹配點(diǎn)，因為早期放棄匹配的節(jié)點(diǎn)已經(jīng)成功匹配，不再影響其分析。反復(fù)對早期節(jié)點(diǎn)進(jìn)行重復(fù)的調(diào)用關(guān)系分析，就是在處理這類問題。

已匹配節(jié)點(diǎn)數(shù)量是隨著每一輪分析而遞增的，如果每次產(chǎn)生新增匹配節(jié)點(diǎn)時都對前幾輪的匹配節(jié)點(diǎn)進(jìn)行再分析，會帶來大量的時耗。實際上，后期匹配節(jié)點(diǎn)對早期不匹配節(jié)點(diǎn)的影響，主要發(fā)生在兄弟節(jié)點(diǎn)上。例如，某個節(jié)點(diǎn)的若干父節(jié)點(diǎn)相似性較高，被放棄分析；如果后續(xù)分析過程中，其中一個被放棄的父節(jié)點(diǎn)已經(jīng)完成匹配，則可以嘗試重新分析這些被放棄的父節(jié)點(diǎn)。這樣，不再需要每次對全部的早期匹配節(jié)點(diǎn)進(jìn)行重復(fù)分析，只需要根據(jù)新增匹配節(jié)點(diǎn)查找兄弟節(jié)點(diǎn)即可，減少了運(yùn)算量。

實驗表明，在所有基于調(diào)用關(guān)系匹配貢獻(xiàn)的匹配節(jié)點(diǎn)中，基于兄弟節(jié)點(diǎn)的策略貢獻(xiàn)了50%以上的匹配量，充分說明對早期匹配節(jié)點(diǎn)進(jìn)行重匹配的必要，也說明此策略降低時耗的必要。

3.4 基于地址分布構(gòu)建候選函數(shù)組

本節(jié)主要介紹基于地址分布的構(gòu)建候選函數(shù)組策略，包括基于連續(xù)地址和基于未匹配區(qū)間兩個角度。目的是突破基于調(diào)用關(guān)系構(gòu)建候選函數(shù)組的局限。

3.4.1 基于連續(xù)地址構(gòu)建候選函數(shù)組

基于連續(xù)地址構(gòu)建候選函數(shù)組的策略，主要篩選與已匹配函數(shù)節(jié)點(diǎn)在地址上鄰接的函數(shù)節(jié)點(diǎn)，檢查其是否已經(jīng)匹配，如未匹配，則加入候選函數(shù)組。連續(xù)地址可以突破調(diào)用關(guān)系的傳播壁壘，此策略對于以短小函數(shù)為代表的低特征函數(shù)具有較好的匹配效果。

基于調(diào)用關(guān)系構(gòu)建候選函數(shù)組的方法本身屬于傳播算法。實際上，基于已有匹配結(jié)果進(jìn)行擴(kuò)展分析的方法，應(yīng)當(dāng)視為傳播算法，本質(zhì)上是為了利用已匹配節(jié)點(diǎn)篩選候選函數(shù)組，縮小后續(xù)匹配工作的匹配范圍。理想狀態(tài)下的二進(jìn)制文件，如果其FCG圖以一棵樹的形態(tài)存在，使用前文策略即可完成匹配。即任意兩個函數(shù)節(jié)點(diǎn)之間存在一條路徑可以從一個節(jié)點(diǎn)經(jīng)過若干節(jié)點(diǎn)后到達(dá)另一個節(jié)點(diǎn)。然而，現(xiàn)實中更為可能的情況是，二進(jìn)制文件的FCG是以森林狀態(tài)存在的，此種情況下會出現(xiàn)傳播壁壘，以圖4為例。

這種方法的合理性在于，如果沒有特殊要求，編譯器在編譯過程中會將同一文件內(nèi)的函數(shù)連續(xù)編譯，這些函數(shù)在物理上連續(xù)存在是大概率事件。邏輯上講，程序中某段特定功能相關(guān)的代碼一般存在于一段鄰近空間，這也符合局部性原理和開發(fā)規(guī)律。此外，這種基于連續(xù)地址進(jìn)行分析的策略，也可以看作對最大公共序列問題的延伸。連續(xù)匹配的函數(shù)越多，連續(xù)匹配的指令就越多，匹配結(jié)果就更為可靠。

實驗表明，使用本策略后，新增匹配節(jié)點(diǎn)占總匹配函數(shù)量的38%。

圖4 調(diào)用關(guān)系隔離的匹配示例

Figure 4 Matching example of call relation isolation

3.4.2 基于未匹配區(qū)間構(gòu)建候選函數(shù)組

在匹配分析的后期，整個二進(jìn)制文件的未匹配函數(shù)節(jié)點(diǎn)被已匹配節(jié)點(diǎn)分割成若干段。此時，從局部性原理考慮，對于兩段連續(xù)未匹配函數(shù)區(qū)間，如果其邊界的匹配節(jié)點(diǎn)是互相匹配的，則直接將兩段函數(shù)構(gòu)造成候選函數(shù)組，用以后續(xù)分析。

此情況產(chǎn)生的原因可能是多樣的。如編譯器在編譯過程中，不同文件在鏈接的過程中可能插入未知數(shù)據(jù)；文件編譯時，文件內(nèi)的小函數(shù)往往分布在編譯結(jié)果的邊緣；將編輯結(jié)果鏈接成可執(zhí)行文件的過程中，排序可能有變化。雖然有局限性，此策略依然可以用作突破調(diào)用關(guān)系的傳播壁壘。由于傳播過程沒有融入語義信息，一旦產(chǎn)生新的匹配節(jié)點(diǎn)，仍優(yōu)先采用更為可靠的基于調(diào)用關(guān)系的策略。

圖5 匹配結(jié)果示例

Figure 5 Examples of matching results

在實際操作過程中，可以考慮利用函數(shù)序列關(guān)系、剔除函數(shù)特征相似節(jié)點(diǎn)、優(yōu)先分析鄰近已匹配點(diǎn)函數(shù)等策略加以優(yōu)化。

實驗表明，使用基于未匹配區(qū)間構(gòu)建候選函數(shù)組策略后，新增匹配節(jié)點(diǎn)量占總匹配量的5%。

3.5 時間開銷分析

候選函數(shù)組構(gòu)造過程本身不涉及函數(shù)節(jié)點(diǎn)的比較，主要是基于已有匹配結(jié)果查找具有關(guān)聯(lián)性的未匹配節(jié)點(diǎn)，并匯入候選函數(shù)組。在已經(jīng)構(gòu)建FCG的條件下，這種查找過程的時間開銷是常量級的。因此，構(gòu)造過程本身的時耗可以忽略。

但函數(shù)節(jié)點(diǎn)相似性分析是具有一定時間開銷的，候選函數(shù)組的構(gòu)建結(jié)果直接影響每個候選函數(shù)組需要進(jìn)行的節(jié)點(diǎn)相似性分析計算次數(shù)。因此，本節(jié)主要分析候選函數(shù)組構(gòu)造方法對節(jié)點(diǎn)匹配過程帶來的影響，進(jìn)而分析對整個固件匹配分析流程帶來的時耗影響。

3.5.1 等尺寸候選函數(shù)集合的時間開銷分析

在假設(shè)1的條件下，補(bǔ)充假設(shè)2。

除了初始階段，本文候選函數(shù)組的構(gòu)建是需要依賴匹配節(jié)點(diǎn)的。因此，每次候選函數(shù)組至少應(yīng)當(dāng)有一個新匹配節(jié)點(diǎn)產(chǎn)生，才能保證生成用于分析的新的候選函數(shù)組。

3.5.2 不等尺寸候選函數(shù)集合節(jié)點(diǎn)的時間開銷分析

在假設(shè)1的條件下，補(bǔ)充假設(shè)3。

3.5.3 節(jié)點(diǎn)相似性重分析對時間開銷的影響

除上述因素外，需要對節(jié)點(diǎn)重分析帶來的時耗進(jìn)行討論。部分早期不匹配節(jié)點(diǎn)，隨著匹配過程的推進(jìn)，可以完成匹配。因此，重新構(gòu)建候選函數(shù)組進(jìn)行分析，以圖6為例。

圖6 重匹配示例

Figure 6 Rematch example

公共節(jié)點(diǎn)匯總工作主要受兩個因素影響：首先是單輪匹配節(jié)點(diǎn)數(shù)量帶來的影響，匹配節(jié)點(diǎn)數(shù)量越多，關(guān)聯(lián)到的節(jié)點(diǎn)越多，排序時耗越大；其次，匹配輪次的影響，匹配輪次越多，排序查找次數(shù)越多，時耗越大。

4 候選函數(shù)組匹配分析方法

圖7 節(jié)點(diǎn)匹配流程

Figure 7 Node matching process

其主要思路如下。

3) 最優(yōu)匹配結(jié)果篩選。根據(jù)所有節(jié)點(diǎn)對的相似度計算結(jié)果，首先基于函數(shù)層局部網(wǎng)絡(luò)匹配的概念完成部分函數(shù)節(jié)點(diǎn)匹配工作。然后，對于多函數(shù)對相似度接近等不同情況，從候選函數(shù)集合的角度，挑選出整個集合的最優(yōu)匹配結(jié)果的組合。

4.1 節(jié)點(diǎn)相似度計算方法

對于一對函數(shù)節(jié)點(diǎn)相似度的計算應(yīng)當(dāng)包含兩部分，函數(shù)自身特征的相似性和函數(shù)所在局部網(wǎng)絡(luò)的相似性。因此，節(jié)點(diǎn)相似性計算如式（6）所示。

4.1.1 基于函數(shù)自身特征的相似度計算方法

基于函數(shù)自身特征的相似性分析，本文直接使用函數(shù)中匯編指令序列進(jìn)行比對。如果函數(shù)指令序列相同，則視為函數(shù)自身特征相同。理論上，依靠LCS算法，可以直接計算兩個函數(shù)之間指令序列的最大公共子序列，以此來完成相似度計算。在實際處理上略有差異。

4.1.2 基于局部網(wǎng)絡(luò)特征的相似度計算方法

4.2 匹配節(jié)點(diǎn)篩選策略

匹配節(jié)點(diǎn)篩選工作主要是利用前文計算出各個節(jié)點(diǎn)對相似度，在候選函數(shù)組內(nèi)挑選出匹配節(jié)點(diǎn)，形成匹配節(jié)點(diǎn)集合。其中，要解決單個函數(shù)與多個函數(shù)相似度較高等問題。

4.2.1 無序列關(guān)系的候選函數(shù)組匹配方法

構(gòu)建候選函數(shù)組時，候選函數(shù)集合內(nèi)的函數(shù)節(jié)點(diǎn)并沒有直接順序關(guān)系。在完成各個節(jié)點(diǎn)相似度計算后，匹配篩選流程如下。

3) 多相似節(jié)點(diǎn)匹配結(jié)果篩選。在完成前兩步工作后，剩余的相似度大于0的節(jié)點(diǎn)多數(shù)含有多個匹配節(jié)點(diǎn)。參考解決皇后問題的思想，解決剩余子節(jié)點(diǎn)匹配問題。

4.2.2 有序候選函數(shù)組匹配方法

候選組生成過程中，候選組內(nèi)函數(shù)會存在具有序列關(guān)系的情況，如連續(xù)地址區(qū)間、連續(xù)調(diào)用序列等。有序候選組相較于無序候選組實際上僅多了一個可以用于輔助分析的有序條件。在此，不再敘述候選結(jié)果篩選流程，僅討論如何在無序篩選的基礎(chǔ)上加以改進(jìn)。

一個較為簡單的方法是將LCS算法融入篩選過程。由于LCS中各個節(jié)點(diǎn)僅存在匹配與不匹配情況，而函數(shù)比對的相似性是一段連續(xù)的區(qū)間，相似度有高低區(qū)分。需要對算法進(jìn)行調(diào)整，其流程如下。

2) 利用LCS算法計算匹配結(jié)果。

3) 將步驟結(jié)果與4.2.1節(jié)結(jié)果進(jìn)行比對，修正步驟2)的誤匹配，以此避免由于LCS算法導(dǎo)致的連續(xù)誤匹配問題。

5 實驗與分析

5.1 實驗環(huán)境

本文實驗環(huán)境為Win10 x64操作系統(tǒng)，IntelXeonGold6150CPU@2.70 GHz處理器，128 GB內(nèi)存，SamsungT5SSD2TB硬盤。使用軟件IDApro[14]進(jìn)行輔助分析。實現(xiàn)語言是python2.7x64。實驗基于收集的Cisco[22]C2600 系列（約660個）和C800系列固件進(jìn)行，收集方法如文獻(xiàn)[24]。從C2600系列固件中挑選兩組固件，每組隨機(jī)抽取10個，標(biāo)號分別是A1-A10和B1-B10，兩組之間的固件兩兩比對以進(jìn)行相似性分析，共計100對比對樣例；從C800系列固件中選擇4個版本號、編譯次數(shù)、功能號相近的固件，標(biāo)號是C1-C4。所挑選的固件列表如表1所示。

C組固件的函數(shù)數(shù)量波動小于10%，主要用于參考和跨系列比對驗證；而A、B兩組固件的函數(shù)數(shù)量波動達(dá)到了90%，且選擇的固件源自不同的功能號，足以驗證本文方法在多種場景下的分析效果。

5.2 預(yù)處理

固件比對分析前，需要對固件進(jìn)行解析。主要依靠IDApro進(jìn)行反匯編，并提取函數(shù)比對需要的基本信息。本文對收集的600余個固件進(jìn)行了預(yù)處理，包括為Bindiff比對提前生成Binexport文件，共時耗23 h。

5.3 參數(shù)選擇

因此，兩個參數(shù)聯(lián)合進(jìn)行實驗，共計進(jìn)行20組實驗，每組都使用文件A1-A10和B1-B10進(jìn)行兩兩比對，即每組100對比對樣例。每組比對后，累加所有匹配節(jié)點(diǎn)數(shù)量和時耗秒數(shù)，形成表2。

表1 待比較文件列表

5.4 候選函數(shù)組構(gòu)造策略匹配效果

基于上述結(jié)果可以確定，調(diào)用關(guān)系貢獻(xiàn)了最多的節(jié)點(diǎn)匹配數(shù)量，約占匹配總量的60%；基于連續(xù)地址的策略是單位時間內(nèi)貢獻(xiàn)匹配量最多的策略，影響了匹配總量的38%。相當(dāng)于提升了前者效果的50%；基于未匹配區(qū)間的匹配策略同樣發(fā)揮了自身的價值。

需要說明的是，由于實際程序所限，基于連續(xù)地址與基于調(diào)用關(guān)系策略是混用的。因此在統(tǒng)計過程中，部分結(jié)果重復(fù)統(tǒng)計在表中，與上文中總的匹配數(shù)量有出入。但通過差值計算不難得出，純粹依靠連續(xù)地址匹配的函數(shù)節(jié)點(diǎn)仍然有782 709個，相當(dāng)于36%的貢獻(xiàn)量。

在時耗問題上，受程序提供API影響，程序時耗的精度是1 s，因此帶來誤差。結(jié)合連續(xù)地址和調(diào)用關(guān)系混用導(dǎo)致的時耗重計算，其數(shù)據(jù)的總和是高于第5.3節(jié)的。但從單位時間匹配節(jié)點(diǎn)量的角度看，即使是混合的數(shù)據(jù)，也可以證明連續(xù)地址策略的效率是絕對高于調(diào)用關(guān)系策略的。

對于調(diào)用關(guān)系內(nèi)的3種不同策略，其統(tǒng)計結(jié)果如表4所示。

基于兄弟節(jié)點(diǎn)策略本質(zhì)上是基于父子節(jié)點(diǎn)關(guān)系，從匹配數(shù)量上可以看出，基于父子關(guān)系匹配的節(jié)點(diǎn)總數(shù)是基于調(diào)用關(guān)系匹配的總數(shù)。但父子關(guān)系的總時耗上少于基于調(diào)用關(guān)系的時耗，因為基于兄弟節(jié)點(diǎn)本身有篩選兄弟節(jié)點(diǎn)的流程，以降低無效重匹配的時耗。這部分時耗差正是兄弟節(jié)點(diǎn)策略獨(dú)有的時耗。兄弟節(jié)點(diǎn)策略貢獻(xiàn)了半數(shù)以上的匹配量。

從單位時間匹配量而言，基于已匹配父節(jié)點(diǎn)的策略效率更高，但是基于已匹配子節(jié)點(diǎn)的策略可以匹配更多的節(jié)點(diǎn)。從失敗消耗上講，后者更高。

5.5 與Bindiff比較實驗

本節(jié)介紹本文方法匹配結(jié)果與Bindiff5匹配結(jié)果的差異，并使用A、B兩組樣本進(jìn)行比對實驗后，完成采樣分析。Bindiff5是2019年3月最新更新的工具，且其算法[14]主要依賴已匹配父節(jié)點(diǎn)的調(diào)用關(guān)系，具有比較價值。實驗表明，本文方法匹配的結(jié)果與Bindiff有差異，各個策略帶來的差異量如表5所示。

表2 單位時間節(jié)點(diǎn)匹配量（匹配個數(shù)/s）

注：每一單元格表示，在相應(yīng)參數(shù)下，比對100對樣例后，匹配量、時間開銷的總和，單位是個數(shù)和秒。

表3 各策略匹配函數(shù)效果

注：輪次表示候選函數(shù)組匹配的次數(shù)，失敗表示一輪匹配未產(chǎn)生新的匹配節(jié)點(diǎn)。

實驗結(jié)果表明以下結(jié)論。

1) 基于連續(xù)地址和基于未匹配區(qū)間兩種非調(diào)用關(guān)系的策略提供了較高的差異量。差異函數(shù)的平均長度小于30，而兩種基于地址分布的策略提供的差異函數(shù)，其平均長度普遍小于其他方法，說明基于地址分布策略影響的匹配結(jié)果對小函數(shù)更有效。

2) 基于調(diào)用關(guān)系和統(tǒng)計特征的策略與Bindiff5的分析結(jié)果相比有97%以上的相似度，說明兩者實驗效果接近。

3) 基于地址分布策略累積貢獻(xiàn)的差異量占所有策略匹配總量13.18%，是很可觀的差異量。這些差異量是直接基于該方法產(chǎn)生的差異量，如果分析這些差異匹配節(jié)點(diǎn)影響到的匹配節(jié)點(diǎn)，可能會在調(diào)用關(guān)系的匹配結(jié)果中找到。由此說明，基于地址分布的策略對差異匹配的影響可能高于預(yù)期，而基于調(diào)用關(guān)系貢獻(xiàn)的差異可能低于預(yù)期。

針對差異匹配結(jié)果，需要人工核實Bindiff5與本文方法差異的函數(shù)匹配結(jié)果哪個正確。由于差異量較大，采用抽樣分析的方法，將A1-A10和B1-B10產(chǎn)生的100對測試樣例，針對不同的候選函數(shù)組構(gòu)造策略抽取500個差異匹配結(jié)果，共2 215個（基于統(tǒng)計特征僅有215個差異結(jié)果，無法抽取更多），對結(jié)果進(jìn)行人工核對，時耗10天，核對結(jié)果如表6所示。通過人工核對，差異結(jié)果中本文方法至少有70%的正確率，本文方法匹配結(jié)果的11.8%可以修正Bindiff的錯誤。需要說明的是，本文測試用例中確實存在人工無法判別是否匹配的情況，這主要發(fā)生在小函數(shù)中，對于以往的研究，研究者往往忽略了這些數(shù)據(jù)。

5.6 跨系列比較

本節(jié)使用A、C兩組樣本進(jìn)行比對實驗，通過分析本文方法比對結(jié)果和Bindiff比對結(jié)果的差異結(jié)果可知，本文方法各匹配策略的準(zhǔn)確率。

本實驗采用抽樣分析的方法，將A1-A10和C1-C4產(chǎn)生的40對測試樣例針對不同的候選函數(shù)組構(gòu)造策略抽取100個差異匹配結(jié)果，共計466個（基于統(tǒng)計特征僅有77個差異結(jié)果，基于未匹配區(qū)間僅有89個結(jié)果），對結(jié)果進(jìn)行人工核對，結(jié)果如表7所示。

實驗結(jié)果表明，在跨系列固件比對條件下，本文方法依然可以對Bindiff比對結(jié)果的錯誤進(jìn)行修正，且準(zhǔn)確率在60%以上。

表4 調(diào)用關(guān)系策略匹配函數(shù)效果

表5 各策略匹配結(jié)果與Bindiff5的差異量

注：差異匹配數(shù)量，本文匹配結(jié)果與Bindiff5不同的函數(shù)數(shù)量。

表6 同系列固件比對各策略匹配差異結(jié)果抽測情況

表7 跨系列固件比對各策略匹配差異結(jié)果抽測情況

實際上，跨系列的固件本身僅有部分功能模塊相似，固件間的相似函數(shù)數(shù)量較少。使用A、B兩組樣本進(jìn)行同系列不同功能和版本的固件間比對，足以證明本文方法在不同相似程度固件間的效果，A、C組的跨系列比對實驗，主要作用是更直觀地證明本文方法在低相似度固件間比對的效果。

6 相關(guān)工作

除引言提到的研究外，二進(jìn)制比對領(lǐng)域也有其他分支，但與本文目標(biāo)關(guān)聯(lián)較低。文獻(xiàn)[15]提取了函數(shù)調(diào)用圖（FCG，function call graph），引入圖編輯距離的概念進(jìn)行相似性比對。文獻(xiàn)[16]針對FCG使用SDMFG來計算圖的相似性距離，該法主要通過測量匹配過程中，最小匹配成本的路徑，形成最優(yōu)匹配路徑，以此計算相似性。文獻(xiàn)[17]針對已有簽名方法易被小變化欺騙、無法形成匹配的情況，使用調(diào)用圖，規(guī)避這類問題，并使用模擬退火算法來近似調(diào)用圖編輯距離。文獻(xiàn)[18]基于子圖匹配的層次分析方法，在剔除確定匹配節(jié)點(diǎn)后形成待檢測的相似子圖，利用函數(shù)調(diào)用序列，進(jìn)行相似序列比對，以此形成新的相似節(jié)點(diǎn)匹配。文獻(xiàn)[19]主要比對源碼中的補(bǔ)丁。文獻(xiàn)[20]通過提取Tracelet（一段短而連續(xù)的執(zhí)行路徑）完成比對。文獻(xiàn)[21]先將二進(jìn)制文件基本塊進(jìn)行符號簡化，以此抵抗語法變化。而后，針對符號簡化形成樹形圖，使用基于樹編輯距離等的匹配方法，進(jìn)行相似性計算。

7 結(jié)束語

[1] A survey of binary code similarity[R]. 2019.

[2] GAO J, YANG X, FU Y, et al. VulSeeker: a semantic learning based vulnerability seeker for cross-platform binary[C]//Conference on Automated Software Engineering(ASE 2018). 2018.

[3] FENG Q, ZHOU R, XU C, et al. Scalable graph-based bug search for firmware images[C]//Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. 2016: 480-491.

[4] XU X, LIU C, FENG Q, et al. Neural network-based graph embedding for cross-platform binary code similarity detection[C]//Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. 2017: 363-376.

[5] HU Y, ZHANG Y, LI J, et al. Cross-architecture binary semantics understanding via similar code comparison[C]//2016 IEEE 23rd International Conference on Software Analysis, Evolution, and Reengineering (SANER). 2016: 57-67.

[6] 劉春紅, 郭濤, 崔寶江, 等. 二進(jìn)制文件同源性檢測的結(jié)構(gòu)化相似度計算[J]. 北京郵電大學(xué)學(xué)報, 2012, 35(3): 56-60.

LIU C H, GUO T, CUI B J, et al. Similarity computation for executable objects homology detection based on structural signature [J]. Journal of Beijing University of Posts and Telecommunications, 2012, 35(3): 56-60.

[7] CESARE S, XIANG Y. Classification of malware using structured control flow[C]//Proceedings of the Eighth Australasian Symposium on Parallel and Distributed Computing-Volume 107. 2010: 61-70.

[8] PEWNY J, GARMANY B, GAWLIK R, et al. Cross-architecture bug search in binary executables[C]//2015 IEEE Symposium on Security and Privacy. 2015: 709-724.

[9] ESCHWEILER S, YAKDAN K, GERHARDS-PADILLA E. DiscovRE: efficient cross-architecture identification of bugs in binary code[C]//NDSS. 2016.

[10] Flake H. Structural comparison of executable objects[C]//Proc of the International GI Workshop on Detection of Intrusions and Malware & Vulnerability Assessment. 2004: 161-174.

[11] DULLIEN T, ROLLES R. Graph-based comparison of executable objects[J]. SSTIC, 2005, 5(1): 3.

[12] 王建新, 楊凡, 韓鋒. 二進(jìn)制文件比對中的指令歸并優(yōu)化算法[J].計算機(jī)應(yīng)用與軟件, 2013, 30(12): 40-42+126.

WANG J X, YANG F, HAN F. Instruction merging optimization algorithm in binary files comparison[J]. Computer Applications and Software,2013,30(12):40-42+126.

[13] KHOO W M, MYCROFT A, ANDERSON R. Rendezvous: a search engine for binary code[C]//Proceedings of the 10th Working Conference on Mining Software Repositories. 2013: 329-338.

[14] BOURQUIN M, KING A, ROBBINS E. Binslayer: accurate comparison of binary executables[C]//Proceedings of the 2nd ACM SIGPLAN Program Protection and Reverse Engineering Workshop. 2013: 4.

[15] HU X, CHIUEH T, SHIN K G. Large-scale malware indexing using function-call graphs[C]//Proceedings of the 16th ACM Conference on Computer and Communications Security. 2009: 611-620.

[16] 劉星, 唐勇. 惡意代碼的函數(shù)調(diào)用圖相似性分析[J]. 計算機(jī)工程與科學(xué), 2014, 36(3): 481-486.

LIU X, TANG Y. Similarity analysis of malware's function-call graphs[J]. Computer Engineering & Science, 2014, 36(3):481-486.

[17] KOSTAKIS O, KINABLE J, MAHMOUDI H, et al. Improved call graph comparison using simulated annealing[C]//Proceedings of the 2011 ACM Symposium on Applied Computing. 2011: 1516-1523.

[18] 孫賀, 吳禮發(fā), 洪征, 等. 基于函數(shù)調(diào)用圖的二進(jìn)制程序相似性分析[J]. 計算機(jī)工程與應(yīng)用, 2016, 52(21): 126-133.

SUN H, WU L F, HONG Z, et al. Research on function call graph based method for similarity analysis of binary files[J]. Computer Engineering and Applications, 2016, 52(21): 126-133.

[19] JANG J, AGRAWAL A, BRUMLEY D. ReDeBug: finding unpatched code clones in entire OS distributions[C]//2012 IEEE Symposium on Security and Privacy. 2012: 48-62.

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

[21] PEWNY J, SCHUSTER F, BERNHARD L, et al. Leveraging semantic signatures for bug search in binary programs[C]//Proceedings of the 30th Annual Computer Security Applications Conference. 2014: 406-415.

[22] Cisco 2600 Series Multiservice Platforms - Retirement Notification[EB].

[23] Bindiff5[EB]. 2019.

[24] COSTIN A, ZADDACH J, FRANCILLON A, et al. A large-scale analysis of the security of embedded firmwares[C]//23rd {USENIX} Security Symposium ({USENIX} Security 14). 2014: 95-110.

[25] 肖睿卿, 劉勝利, 顏猛, 等. 節(jié)點(diǎn)層次化的二進(jìn)制文件比對技術(shù)[J]. 計算機(jī)工程與應(yīng)用, 2017, 53(21): 144-150.

XIAO R Q, LIU S L, YAN M, et al. Comparison technology of binary files based on hierarchical nodes[J]. Computer Engineering and Applications, 2017, 53(21): 144-150.

Method for constructing function correspondence between firmware based on candidate function group

XIAO Ruiqing, ZHU Yuefei, LIU Shengli, LU Bin

State Key Laboratory of Mathematical Engineering and Advanced Computing, Zhengzhou 450001, China

Due to the characteristics of firmware, traditional binary comparison methods are prone to mismatches during the propagation of the matching function.Aiming at the problem that the matching function propagation algorithm is not ideal, a method for constructing function correspondence based on candidate function groups was designed, and the concept of function matching inlayer local network is supplemented.Then, three candidate function group construction strategies and candidate function group matching methods are proposed, and the time overhead were analyzed. Finally, a prototype system was implemented based on the method and compared with Bindiff. Through random sampling and manual check, 86.04% of the matching results of the proposed method are consistent with Bindiff matching results, while 11.3% can correct Bindiff matching errors.

firmware, binary comparison, function matching, candidate function group

TP393

A

10.11959/j.issn.2096?109x.2021018

2020?02?20；

2020?06?21

劉勝利，dr_liushengli@ 163.com

科技委基礎(chǔ)加強(qiáng)項目（2019-JCJQ-ZD-113）；國家重點(diǎn)研發(fā)計劃（2019QY1300, 2016YFB0801505）

Science and Technology Commission Foundation Enhancement Project (2019-JCJQ-ZD-113), The National Key R&D Program of China (2019QY1300, 2016YFB0801505)

肖睿卿, 祝躍飛, 劉勝利. 等. 基于候選函數(shù)組的固件間函數(shù)對應(yīng)關(guān)系構(gòu)建方法[J]. 網(wǎng)絡(luò)與信息安全學(xué)報, 2021, 7(2): 110-125.

XIAO R Q, ZHU Y F, LIU S L, et al. Method for constructing function correspondence between firmware based on candidate function group[J]. Chinese Journal of Network and Information Security, 2021, 7(2): 110-125.

肖睿卿（1992?），男，黑龍江牡丹江人，數(shù)學(xué)工程與先進(jìn)計算國家重點(diǎn)實驗室博士生，主要研究方向為二進(jìn)制分析。

祝躍飛（1962?），男，浙江蘭溪人，數(shù)學(xué)工程與先進(jìn)計算國家重點(diǎn)實驗室教授、博士生導(dǎo)師，主要研究方向為安全協(xié)議和密碼學(xué)。

劉勝利（1973?），男，河南周口人，數(shù)學(xué)工程與先進(jìn)計算國家重點(diǎn)實驗室教授、博士生導(dǎo)師，主要研究方向為網(wǎng)絡(luò)設(shè)備安全和網(wǎng)絡(luò)攻擊檢測。

蘆斌（1982-），男，山西靈石人，數(shù)學(xué)工程與先進(jìn)計算國家重點(diǎn)實驗室副教授，主要研究方向為信息安全、機(jī)器學(xué)習(xí)。