曹琰，劉龍，王禹，王清賢

基于函數(shù)語(yǔ)義分析的軟件補(bǔ)丁比對(duì)技術(shù)

曹琰1，劉龍1，王禹2，王清賢1

(1.數(shù)學(xué)工程與先進(jìn)計(jì)算國(guó)家重點(diǎn)實(shí)驗(yàn)室，河南 鄭州 450000；2. 河南工程學(xué)院，河南 鄭州 450000)

基于結(jié)構(gòu)化的補(bǔ)丁比對(duì)是軟件漏洞輔助分析的重要方法。在分析總結(jié)已有補(bǔ)丁比對(duì)技術(shù)及反補(bǔ)丁比對(duì)技術(shù)的基礎(chǔ)上，針對(duì)結(jié)構(gòu)化比對(duì)存在無法進(jìn)行語(yǔ)義分析而導(dǎo)致誤報(bào)的問題，提出了基于函數(shù)語(yǔ)義分析的軟件補(bǔ)丁比對(duì)方法。利用傳統(tǒng)的結(jié)構(gòu)化比對(duì)方法，在函數(shù)級(jí)進(jìn)行語(yǔ)法差異比較得到最大同構(gòu)子圖；通過程序依賴分析，構(gòu)建函數(shù)輸入輸出之間的路徑包絡(luò)，基于符號(hào)執(zhí)行以包絡(luò)為對(duì)象計(jì)算函數(shù)輸出特征；通過函數(shù)摘要進(jìn)行語(yǔ)義級(jí)比對(duì)，結(jié)合最大同構(gòu)子圖的匹配函數(shù)結(jié)果，進(jìn)一步分析得出發(fā)生語(yǔ)義變化的函數(shù)。最終，通過實(shí)驗(yàn)比對(duì)測(cè)試，驗(yàn)證了所提方法的可行性和優(yōu)勢(shì)。

漏洞分析；補(bǔ)丁比對(duì)；符號(hào)執(zhí)行；語(yǔ)義分析

1 引言

軟件廠商為了維護(hù)信息產(chǎn)品安全性，針對(duì)已發(fā)現(xiàn)存在的軟件漏洞，開發(fā)相應(yīng)的修補(bǔ)代碼，稱為“安全補(bǔ)?。╯ecurity patch）”。使用補(bǔ)丁修補(bǔ)漏洞，即用安全的程序代碼替換原有不安全的程序片段，使同一文件因?yàn)檠a(bǔ)丁發(fā)布在不同版本之間存在差異。補(bǔ)丁比對(duì)技術(shù)就是通過比較可執(zhí)行文件的差異，揭示漏洞的確切位置和成因，而這些信息一般在安全公告中未指明。通過對(duì)補(bǔ)丁比對(duì)，進(jìn)一步分析漏洞的成因和觸發(fā)機(jī)理，有助于軟件開發(fā)過程中規(guī)避已出現(xiàn)的漏洞模式。

補(bǔ)丁比對(duì)技術(shù)的發(fā)展已有近20年的歷史。1999年的BMAT[1]是補(bǔ)丁比對(duì)技術(shù)的開端，研究在兩個(gè)可執(zhí)行文件中函數(shù)匹配的問題，該方法嚴(yán)重依賴于符號(hào)文件。

指令級(jí)別的同構(gòu)比較受編譯器優(yōu)化和函數(shù)匹配的影響較大，需要進(jìn)一步改進(jìn)，而利用調(diào)用圖及控制流圖進(jìn)行比較的結(jié)構(gòu)化比較方法可以很好地解決匹配問題，并且在一定程度上解決編譯器優(yōu)化所帶來的問題。2004年，F(xiàn)lake[2]提出了基于結(jié)構(gòu)化比較的二進(jìn)制文件比較方法。同時(shí)，F(xiàn)lake還提出了使用函數(shù)的指紋（fingerprints）進(jìn)行比較，開發(fā)了著名的Bindiff。

結(jié)構(gòu)化的比較方法可以一定程度上避免因優(yōu)化而使指令變化所帶來的影響而且跨平臺(tái)。結(jié)構(gòu)化比較的基本思想影響深遠(yuǎn)，依然是當(dāng)前補(bǔ)丁比對(duì)的主流方法，已在Sabre Security Bindiff、PatchDiff2、TurboDiff等工具中使用，得到了較好的效果。潘璠等[3]通過改進(jìn)固定點(diǎn)傳播算法，避免錯(cuò)誤匹配的傳播，且對(duì)錯(cuò)誤匹配進(jìn)行修正，優(yōu)化了結(jié)構(gòu)化比對(duì)結(jié)果。肖雅娟[4]提出了基于函數(shù)內(nèi)部和外部緊寬約束特征進(jìn)行函數(shù)相似性比較。

為了應(yīng)對(duì)圖形匹配效率問題，研究人員考慮將函數(shù)代碼特征轉(zhuǎn)化為數(shù)字化編碼。Liu等[5]提出了基于DNN的二進(jìn)制代碼相似性檢測(cè)方法，將函數(shù)代碼特征編碼為64 bit向量，以數(shù)字向量比較計(jì)算二進(jìn)制函數(shù)相似度。Xu等[6]提出了基于網(wǎng)絡(luò)嵌入的二進(jìn)制函數(shù)數(shù)字化向量方法。

研究人員也將結(jié)構(gòu)化比對(duì)技術(shù)應(yīng)用于指導(dǎo)模糊測(cè)試和Concolic（Concrete & Symbolic的合成）測(cè)試[7-8]；基于補(bǔ)丁比對(duì)技術(shù)對(duì)修補(bǔ)方式進(jìn)行識(shí)別，還可以開展針對(duì)未打補(bǔ)丁原文件的利用代碼自動(dòng)生成技術(shù)的研究[9-11]。

為了防止被攻擊者利用，出現(xiàn)了各類對(duì)抗二進(jìn)制比對(duì)的混淆、欺騙技術(shù)[12-13]，如改變符號(hào)、擾亂指令順序、擾亂CFG、使用proxy調(diào)用、調(diào)用不返回、共享基本塊等方法。這些方法的基本思想是針對(duì)結(jié)構(gòu)化匹配的方法，混淆結(jié)構(gòu)化簽名的相關(guān)信息，使之比較結(jié)果出現(xiàn)差錯(cuò)。

如果混淆技術(shù)使用于軟件補(bǔ)丁代碼的編寫過程中，則基于結(jié)構(gòu)化比對(duì)的準(zhǔn)確率會(huì)降低。為了實(shí)現(xiàn)更為精準(zhǔn)的分析，在一定程度上抵抗代碼混淆，使結(jié)構(gòu)化差異分析更加精確，相關(guān)研究人員提出了在結(jié)構(gòu)化比對(duì)結(jié)構(gòu)基礎(chǔ)上，分別利用基本塊語(yǔ)義和trace語(yǔ)義信息進(jìn)一步加強(qiáng)比對(duì)結(jié)構(gòu)的精確度[14-16]。

基于結(jié)構(gòu)化或靜態(tài)特征的比對(duì)本質(zhì)是語(yǔ)法分析。如果要防止混淆技術(shù)帶來的不利影響，就不僅能在代碼結(jié)構(gòu)特征上比較，更要比較文件間的語(yǔ)義功能變化情況，這就需要進(jìn)行語(yǔ)義級(jí)的比對(duì)。已有的語(yǔ)義比對(duì)方法主要在基本塊級(jí)實(shí)現(xiàn)，用于修正函數(shù)比對(duì)結(jié)果。但基本塊粒度對(duì)漏洞信息包含不全，只能局部表現(xiàn)某些語(yǔ)義差異。函數(shù)級(jí)的分析能夠更加精準(zhǔn)反映漏洞觸發(fā)語(yǔ)義。本文設(shè)計(jì)實(shí)現(xiàn)了面向二進(jìn)制函數(shù)級(jí)的語(yǔ)義差異分析技術(shù)，基于函數(shù)符號(hào)執(zhí)行的輸入輸出差異，判斷函數(shù)語(yǔ)義；通過路徑包絡(luò)和函數(shù)摘要分析提高函數(shù)級(jí)符號(hào)執(zhí)行的效率。

2 問題的提出

通過比對(duì)原文件（unpatch）文件和補(bǔ)丁文件（patched）文件之間代碼結(jié)構(gòu)的差異，掌握修補(bǔ)漏洞的方式。

如圖1所示，把可執(zhí)行文件看作函數(shù)的集合，令=M∪N，= M∪N，其中N、N分別表示原文件和補(bǔ)丁文件中不匹配的函數(shù)集合，M、M分別表示原文件和補(bǔ)丁文件中匹配的函數(shù)集合，M=M∪M，M=M∪M，其中，M和M分別表示原文件中匹配且發(fā)生改變的函數(shù)和匹配且無任何變化的函數(shù)；M和M分別表示補(bǔ)丁文件中匹配且發(fā)生改變的函數(shù)和匹配且無任何變化的函數(shù)。M和M中的函數(shù)本質(zhì)上是同一函數(shù)，即補(bǔ)丁前后沒發(fā)生變化。

在進(jìn)行比較分析后，重點(diǎn)關(guān)注的是不匹配部分和發(fā)生改變的匹配部分的集合=N∪N∪M∪M，進(jìn)一步分析，是漏洞或補(bǔ)丁最有可能出現(xiàn)的位置。

圖1 補(bǔ)丁比較差異示意

本文提出的基于函數(shù)語(yǔ)義分析的軟件補(bǔ)丁比對(duì)方法是符號(hào)執(zhí)行技術(shù)與圖同構(gòu)匹配的結(jié)合，其主要步驟如下。

步驟1 對(duì)函數(shù)調(diào)用圖、控制流圖進(jìn)行同構(gòu)比較。找出兩個(gè)調(diào)用圖之間的最大同構(gòu)子圖，目的是找出漏洞或補(bǔ)丁存在的可疑函數(shù)集合=N∪N∪M，其中M=M∪M。

步驟2 對(duì)集合M中的函數(shù)對(duì)進(jìn)行語(yǔ)義比較。進(jìn)一步排除結(jié)構(gòu)特征發(fā)生變化而語(yǔ)義無變化的函數(shù)對(duì)，重點(diǎn)關(guān)注真正語(yǔ)義發(fā)生變化的函數(shù)對(duì)，以更加精準(zhǔn)定位漏洞所在函數(shù)。

3 基于圖形同構(gòu)的函數(shù)級(jí)結(jié)構(gòu)化比較

基于結(jié)構(gòu)特征簽名信息的比較是目前主流的同構(gòu)匹配方法。選用能夠表達(dá)結(jié)構(gòu)化特征的屬性集合作為函數(shù)簽名，可選的函數(shù)簽名屬性包括函數(shù)名、節(jié)點(diǎn)的入度/出度、遞歸屬性、循環(huán)體（while循環(huán)、for循環(huán)等）、相同字符串引用、可歸約結(jié)構(gòu)的素?cái)?shù)乘積、參數(shù)個(gè)數(shù)、標(biāo)準(zhǔn)應(yīng)用程序編程接口（API, application programming interface）函數(shù)調(diào)用、棧布局、遠(yuǎn)程過程調(diào)用（RPC, remote procedure call）函數(shù)等。函數(shù)簽名間的歐幾里得德距離用于表示相似程度。

根據(jù)上述的設(shè)計(jì)簽名，對(duì)于原文件中的函數(shù)A和補(bǔ)丁文件中的函數(shù)B，如果A和B匹配，需要同時(shí)滿足以下3個(gè)條件。

1)A和B簽名的歐幾里得距離滿足閾值。

2) 補(bǔ)丁文件中除了B沒有其他的函數(shù)與A簽名的歐幾里得距離滿足閾值。

3) 原文件中除了A沒有其他的函數(shù)與B簽名的歐幾里得距離滿足閾值。

在進(jìn)行了函數(shù)同構(gòu)比較后，找到了最大同構(gòu)子圖。接下來，在最大同構(gòu)子圖的基礎(chǔ)上，對(duì)已匹配函數(shù)未發(fā)生結(jié)構(gòu)變化的函數(shù)對(duì)M進(jìn)行語(yǔ)義比較，以判斷發(fā)生了語(yǔ)義變化的函數(shù)對(duì)。

4 基于符號(hào)執(zhí)行的函數(shù)級(jí)語(yǔ)義比較

函數(shù)級(jí)語(yǔ)義比較的基本思路是：基于程序依賴圖（PDG, program dependence graph）分析函數(shù)輸入、輸出之間的依賴關(guān)系，構(gòu)建路徑包絡(luò)；基于符號(hào)執(zhí)行計(jì)算函數(shù)輸出的符號(hào)值，每個(gè)路徑包絡(luò)對(duì)應(yīng)一個(gè)輸出的符號(hào)值；根據(jù)函數(shù)輸入、路徑包絡(luò)和輸出關(guān)系建立函數(shù)摘要，通過比對(duì)函數(shù)摘要信息，判斷兩個(gè)函數(shù)間的輸入、輸出之間是否存在相似關(guān)系，進(jìn)而判斷函數(shù)語(yǔ)義（功能）等價(jià)性。

4.1 函數(shù)功能相似性的判定原理

程序語(yǔ)義反映的是功能，如果兩個(gè)函數(shù)的功能相同，則語(yǔ)義無差別。而函數(shù)的功能可以使用輸入輸出的映射關(guān)系來刻畫。對(duì)于相同的輸入，不同的函數(shù)執(zhí)行后能夠得到相同的輸出，可認(rèn)為它們的功能相同。為了實(shí)現(xiàn)函數(shù)級(jí)的語(yǔ)義分析，本文使用靜態(tài)符號(hào)執(zhí)行技術(shù)，是單元程序分析的重要方法。在函數(shù)內(nèi)以符號(hào)值代替具體值，實(shí)現(xiàn)函數(shù)的符號(hào)化模擬執(zhí)行。即對(duì)某個(gè)函數(shù)靜態(tài)模擬執(zhí)行時(shí)，所有的函數(shù)參數(shù)進(jìn)行符號(hào)化，用符號(hào)值代入運(yùn)算；在執(zhí)行結(jié)束后，收集函數(shù)所有輸出形態(tài)（全局變量、返回值、引用參數(shù)、指針等）的運(yùn)算符號(hào)值。

本文中函數(shù)的輸入指的是函數(shù)參數(shù)，以及全局變量和函數(shù)中定義的變量；輸出指的是參與函數(shù)內(nèi)部執(zhí)行的全局變量、函數(shù)返回值、引用參數(shù)、指針等。一般來說，語(yǔ)義相同的函數(shù)在相同的參數(shù)符號(hào)化條件下，也有相同的輸出形態(tài)的符號(hào)值對(duì)應(yīng)。

4.2 基于路徑包絡(luò)分析的執(zhí)行結(jié)果計(jì)算

函數(shù)的輸出因?yàn)槁窂綏l件的約束可能會(huì)產(chǎn)生多個(gè)，即多條執(zhí)行路徑可能會(huì)產(chǎn)生不同的輸出值。對(duì)于執(zhí)行路徑比較復(fù)雜的函數(shù)，如函數(shù)體包含的子調(diào)用、循環(huán)等較多時(shí)，如果遍歷每條路徑將輸入?yún)?shù)代入符號(hào)值運(yùn)算，以計(jì)算函數(shù)輸出符號(hào)值，顯然模擬計(jì)算帶來的開銷和龐大的路徑導(dǎo)致計(jì)算量很大，效率較低。為了快速分析全部的輸出值，可以對(duì)控制程序執(zhí)行路徑的約束條件進(jìn)行歸約，將對(duì)函數(shù)輸出符號(hào)值產(chǎn)生相同程序依賴影響的路徑集合構(gòu)建成路徑包絡(luò)，在路徑包絡(luò)內(nèi)部計(jì)算輸出符號(hào)值的計(jì)算，而無須遍歷全部路徑。

圖2 路徑包絡(luò)構(gòu)建流程

4.2.1 基于PDG的路徑包絡(luò)構(gòu)建

路徑包絡(luò)歸約是為了提取影響目標(biāo)點(diǎn)符號(hào)值的關(guān)鍵路徑控制條件，而去除對(duì)目標(biāo)點(diǎn)符號(hào)值無影響的路徑條件，即無用控制條件。路徑包絡(luò)的構(gòu)建是建立在對(duì)程序控制和數(shù)據(jù)依賴分析基礎(chǔ)上的，PDG能夠反映程序的控制依賴關(guān)系和數(shù)據(jù)依賴關(guān)系。因此，可以根據(jù)PDG的相關(guān)分析，建立路徑包絡(luò)。本文中研究的目標(biāo)點(diǎn)是4.1節(jié)提到的函數(shù)輸出，下文均用目標(biāo)點(diǎn)闡述。

路徑包絡(luò)本質(zhì)是滿足相同程序依賴關(guān)系的一組路徑集合，可由路徑約束條件及其布爾值進(jìn)行表示。如路徑包絡(luò)<(2,) ,(4,) ,(6,)>表示第2、4、6分支分別取值為、、時(shí)的路徑集合。

探索從函數(shù)入口點(diǎn)到目標(biāo)點(diǎn)具備相同運(yùn)算符號(hào)值的路徑集合，如圖2所示，基本流程是：通過入口點(diǎn)和目標(biāo)點(diǎn)的公共依賴域分析，建立局部程序依賴關(guān)系；通過反向數(shù)據(jù)依賴分析，探索與目標(biāo)點(diǎn)具有數(shù)據(jù)依賴關(guān)系的語(yǔ)句集合；如果沒有新的數(shù)據(jù)依賴語(yǔ)句加入則結(jié)束，否則，通過反向控制依賴分析，探索與數(shù)據(jù)依賴語(yǔ)句具有控制依賴關(guān)系的關(guān)鍵路徑控制條件；以關(guān)鍵控制路徑條件為目標(biāo)點(diǎn)，探索與之具有數(shù)據(jù)依賴關(guān)系的語(yǔ)句集合；當(dāng)新的數(shù)據(jù)依賴語(yǔ)句不再發(fā)生變化時(shí)，對(duì)具有兩個(gè)布爾值的關(guān)鍵路徑控制條件進(jìn)行消減（無用控制條件），構(gòu)建路徑包絡(luò)。

針對(duì)包絡(luò)構(gòu)建流程，本文提出了面向函數(shù)的路徑包絡(luò)構(gòu)建算法（PCE）。該算法主要功能是在PDG上分析程序的控制依賴和數(shù)據(jù)依賴關(guān)系，根據(jù)函數(shù)入口點(diǎn)和函數(shù)輸出點(diǎn)，找到到的路徑包絡(luò)集合。

算法 路徑包絡(luò)構(gòu)建算法

輸入：待分析函數(shù)

：函數(shù)入口點(diǎn)

：函數(shù)輸出點(diǎn)

輸出—?dú)w約的路徑包絡(luò)

1)=Ф

2)(,)

3)=(,′)

4)to=(,)

5)=⊕to T

6)(ifather,)

7)1=(ifather,)

8)=⊕1

9) return

路徑包絡(luò)構(gòu)建算法描述如下。

步驟1 初始化歸約的路徑包絡(luò)為空。

步驟2 基于PDG分析以為根節(jié)點(diǎn)的樹上所有節(jié)點(diǎn)與節(jié)點(diǎn)的數(shù)據(jù)依賴關(guān)系，剪除與節(jié)點(diǎn)數(shù)據(jù)依賴無關(guān)的控制依賴域節(jié)點(diǎn)及其子樹。

步驟3 生成到′的路徑包絡(luò)，′是的直接后繼節(jié)點(diǎn)，并且是的祖先。

步驟4基于PDG上從到的路徑，收集控制依賴域節(jié)點(diǎn)，同時(shí)收集從到ifather路徑條件。ifather是在從到的路徑上，距離最近的控制依賴域節(jié)點(diǎn)的祖先。

步驟5 生成從到ifather的路徑包絡(luò)。

步驟6 基于PDG分析以ifather為根節(jié)點(diǎn)的子樹上的所有節(jié)點(diǎn)和的數(shù)據(jù)依賴關(guān)系，剪除與節(jié)點(diǎn)數(shù)據(jù)依賴無關(guān)的控制依賴域節(jié)點(diǎn)及其子樹。

步驟7 生成從ifather的直接后繼節(jié)點(diǎn)到的路徑包絡(luò)1。

步驟8 將到ifather的路徑包絡(luò)與1聯(lián)合，生成到的路徑包絡(luò)。

步驟9 輸出歸約的路徑包絡(luò)結(jié)果。

其中，子算法DataDependenseCut和GatherPC在文獻(xiàn)[17]中已經(jīng)提出。

4.2.2 函數(shù)執(zhí)行結(jié)果符號(hào)值計(jì)算

本文采用符號(hào)執(zhí)行以實(shí)現(xiàn)函數(shù)功能的相似性比較，見4.1節(jié)。因?yàn)橹恍枰容^函數(shù)輸出時(shí)的符號(hào)值是否相同，無須進(jìn)行具體值的運(yùn)算。但在符號(hào)執(zhí)行過程中，會(huì)遇到外部調(diào)用、循環(huán)等問題，如果處理不當(dāng)，會(huì)影響輸出符號(hào)值的計(jì)算結(jié)果。

鑒于函數(shù)內(nèi)部單元符號(hào)執(zhí)行特點(diǎn)和語(yǔ)義比對(duì)的需求，在處理外部調(diào)用和循環(huán)問題時(shí)可簡(jiǎn)化處理。

1) 外部調(diào)用：不跟進(jìn)外部調(diào)用的執(zhí)行，將調(diào)用的子函數(shù)名直接作為符號(hào)帶入后續(xù)符號(hào)執(zhí)行過程。包含子函數(shù)名的符號(hào)值相當(dāng)于黑盒運(yùn)算。

2) 循環(huán)計(jì)數(shù)：將循環(huán)計(jì)數(shù)與函數(shù)變量或輸入?yún)?shù)關(guān)聯(lián)，循環(huán)體內(nèi)的運(yùn)算結(jié)果與循環(huán)計(jì)數(shù)關(guān)聯(lián)。

因?yàn)檎Z(yǔ)義分析是針對(duì)函數(shù)輸出符號(hào)值的比較，不需要進(jìn)行約束求解，因此可以接受符號(hào)化的子函數(shù)調(diào)用和循環(huán)計(jì)數(shù)。

4.3 基于函數(shù)摘要分析的語(yǔ)義比對(duì)

在補(bǔ)丁文件發(fā)布時(shí)，可能加入針對(duì)控制流圖或函數(shù)調(diào)用圖的混淆機(jī)制[14-15]，干擾補(bǔ)丁分析結(jié)果。為了有效識(shí)別混淆代碼，剪除不可能執(zhí)行到達(dá)的分支路徑以及由此帶來的函數(shù)偽輸出，需要對(duì)包絡(luò)的關(guān)鍵路徑條件進(jìn)一步分析，發(fā)現(xiàn)可能存在的約束沖突，將該包絡(luò)產(chǎn)生的函數(shù)輸出標(biāo)記為偽輸出，從函數(shù)執(zhí)行結(jié)果的比對(duì)中剔除。

函數(shù)摘要技術(shù)一般用于頻繁執(zhí)行某個(gè)函數(shù)時(shí)，只在第一次執(zhí)行或未執(zhí)行時(shí)靜態(tài)分析，建立該函數(shù)的輸入輸出映射關(guān)系，以便在后續(xù)調(diào)用該函數(shù)時(shí)可以復(fù)用摘要信息，代替實(shí)際執(zhí)行該函數(shù)。

在本文中，通過路徑包絡(luò)的構(gòu)建，建立函數(shù)輸入、輸出符號(hào)值之間的映射關(guān)系。函數(shù)摘要用三元組表示，如下。

1) Input：表示函數(shù)輸入，這里的輸入包括全局變量、函數(shù)體內(nèi)定義的局部變量、函數(shù)參數(shù)等對(duì)應(yīng)的符號(hào)值。

2) Constrant：表示路徑包絡(luò)對(duì)應(yīng)的關(guān)鍵路徑條件及其取值。

3) Output：表示當(dāng)輸入符號(hào)值為Input，沿著在Constrant約束下程序路徑執(zhí)行時(shí)，得到的程序輸出符號(hào)值。這里的輸出指的是參與函數(shù)內(nèi)部執(zhí)行的全局變量、函數(shù)返回值、引用參數(shù)、指針等。

函數(shù)摘要構(gòu)建時(shí)，為了解決混淆代碼的影響，需要對(duì)路徑包絡(luò)的關(guān)鍵約束條件進(jìn)行相容檢查，發(fā)現(xiàn)可能存在的約束沖突，從而將不可能產(chǎn)生的函數(shù)輸出和對(duì)應(yīng)的Output和約束條件Constrant刪除，在一定程度上可以緩解混淆代碼的影響。

約束相容性檢查后，對(duì)處理過的函數(shù)摘要進(jìn)行比較。相同語(yǔ)義的函數(shù)對(duì)，可能因?yàn)榉峙涞妮斎敕?hào)不同，導(dǎo)致輸出符號(hào)值不同。這里對(duì)輸出符號(hào)值的比較不能用簡(jiǎn)單的匹配方式實(shí)現(xiàn)，必須找到一組相應(yīng)的序列映射，才可能判斷函數(shù)是否有語(yǔ)義差別。具體的形式化定義描述如下。

圖3 SymDiff系統(tǒng)結(jié)構(gòu)

5 系統(tǒng)實(shí)現(xiàn)

按照前文設(shè)計(jì)思路，本文實(shí)現(xiàn)了補(bǔ)丁比對(duì)工具SymDiff，其基本構(gòu)成如圖3所示。

1) 反匯編器

系統(tǒng)使用的反匯編器是IDA Pro，本文設(shè)計(jì)的補(bǔ)丁比對(duì)插件SymDiff是在IDA PRO 5.5版本上實(shí)現(xiàn)的。系統(tǒng)需要使用IDA的反匯編及插件功能。

2）函數(shù)級(jí)同構(gòu)比較

運(yùn)用圖同構(gòu)匹配方法進(jìn)行結(jié)構(gòu)化比對(duì)，生成最大同構(gòu)子圖。函數(shù)簽名模塊從待比較文件中提取簽名信息，利用同構(gòu)算法在函數(shù)調(diào)用圖級(jí)進(jìn)行分析，生成比對(duì)結(jié)果。詳細(xì)的過程見第3節(jié)內(nèi)容。

3）函數(shù)級(jí)語(yǔ)義比較

在最大同構(gòu)子圖基礎(chǔ)上，運(yùn)用符號(hào)執(zhí)行的方法對(duì)函數(shù)輸入輸出特征進(jìn)行語(yǔ)義級(jí)比對(duì)。也就是說，對(duì)于集合M中的函數(shù)對(duì)進(jìn)行語(yǔ)義比較，找出發(fā)生了功能變化的匹配函數(shù)對(duì)，從而找到補(bǔ)丁具體修補(bǔ)的指令。具體方法見第4節(jié)內(nèi)容。

6 實(shí)驗(yàn)分析

1) 測(cè)試目的

本節(jié)通過SymDiff與當(dāng)前常用的開源補(bǔ)丁比對(duì)工具PatchDiff2進(jìn)行比對(duì)測(cè)試，以驗(yàn)證本工具在確定可疑函數(shù)精度方面的優(yōu)勢(shì)。

2) 測(cè)試工具

自主開發(fā)的補(bǔ)丁比對(duì)分析工具SymDiff和開源工具PatchDiff2如表1所示。

表1 比對(duì)測(cè)試工具

3) 測(cè)試對(duì)象

CVE-2006-3439、CVE-2008-4205、CVE-2010- 2746、CVE-2017-6178這4個(gè)漏洞對(duì)應(yīng)的原文件和補(bǔ)丁文件，如表2~表5所示。

表2 CVE-2006-3439文件

表3 CVE-2008-4205文件

表4 CVE-2010-2746文件

表5 CVE-2017-6178文件

4) 測(cè)試方法

使用兩個(gè)工具對(duì)4個(gè)比較對(duì)象進(jìn)行補(bǔ)丁比對(duì)，記錄漏洞所在函數(shù)/修補(bǔ)函數(shù)對(duì)數(shù)量，記錄可疑函數(shù)對(duì)M數(shù)量。通過和的比值，判斷比對(duì)工具對(duì)可疑函數(shù)篩選的精度。

5) 測(cè)試結(jié)果

M中的函數(shù)往往是漏洞存在或修補(bǔ)的位置，也是漏洞分析人員關(guān)注的重點(diǎn)。如果該函數(shù)集合范圍較小，能提高人工分析效率。由于結(jié)構(gòu)化比對(duì)存在誤報(bào)，將結(jié)構(gòu)化差異誤認(rèn)為語(yǔ)義差異，導(dǎo)致M函數(shù)過多。本次測(cè)試使用漏洞及修補(bǔ)函數(shù)對(duì)與M函數(shù)對(duì)做比較，得出的比例作為比對(duì)結(jié)果的精度。表6是比對(duì)測(cè)試結(jié)果，顯示SymDiff工具具有優(yōu)勢(shì)，這也源于使用函數(shù)級(jí)的語(yǔ)義比較修正了函數(shù)同構(gòu)匹配的結(jié)果。

表6 比對(duì)測(cè)試結(jié)果

7 結(jié)束語(yǔ)

本文闡述了函數(shù)級(jí)語(yǔ)義比對(duì)在軟件補(bǔ)丁比對(duì)中的應(yīng)用。軟件補(bǔ)丁比對(duì)分析是軟件漏洞分析的重要方法，可以對(duì)1day漏洞進(jìn)行快速定位，分析成因。經(jīng)典的結(jié)構(gòu)化比對(duì)方法雖然獲得了較好的效果，但是隨著反二進(jìn)制比對(duì)混淆代碼技術(shù)的出現(xiàn)，比對(duì)的難度不斷增加。為了應(yīng)對(duì)這些挑戰(zhàn)并綜合考慮符號(hào)執(zhí)行技術(shù)本身的瓶頸，本文提出了將函數(shù)級(jí)符號(hào)執(zhí)行運(yùn)用于語(yǔ)義差異分析的方法，盡可能減少結(jié)構(gòu)化比對(duì)帶來的誤差。

[1] WANG Z, PIERCE K, MCFARLING S. BMAT-a binary matching tool for stale profile propagation[J]. The Journal of Instruction-Level Parallelism (JILP), 2000,2:1-20.

[2] FLAKE H. Structural comparison of executable objects[C]//Dortmund GI SIG SIDAR Workshop, 2004.

[3] 潘璠, 吳禮發(fā), 孫傳魯, 等. 一種改進(jìn)的補(bǔ)丁比較模型的研究與實(shí)現(xiàn)[J]. 南京郵電大學(xué)學(xué)報(bào)（自然科學(xué)版）, 2012, 32(2): 75-83.

PAN F, WU L F, SUN C L, et al. Research and implementation of an improved patch comparison technique[J]. Journal of Nanjing University of Posts and Telecommunications(Natural Science), 2012, 32(2): 75-83.

[4] 肖雅娟.二進(jìn)制代碼函數(shù)相似度匹配技術(shù)研究[D]. 濟(jì)南: 山東大學(xué), 2016.

XIAO Y J. Research on similarity matching technology of binary code function[M]. Jinan: Shandong University. 2016.

[5] LIU B C, BINGCHANG L, WEI H, CHAO Z, et al. α Diff: cross-version binary code similarity detection with DNN[C]//IEEE ACM Automated Software Engineering (ASE’18). 2018.

[6] XU X J, LIU C, FENG Q, et al. Neural network-based graph embedding for cross-platform binary code similarity detection[C]//The 2017 ACM SIGSAC Conference on Computer and Communications Security. 2017.

[7] 王欣, 郭濤, 董國(guó)偉, 等. 基于補(bǔ)丁比對(duì)的Concolic測(cè)試方法[J]. 清華大學(xué)學(xué)報(bào)（自然科學(xué)版）, 2013, 53(12): 1737-1742.

WANG X, GUO T, DONG G W, et al. Concolic test method based on patch matching[J]. Journal of Tsinghua University(Science and Technology), 2013, 53(12): 1737-1742.

[8] 王嘉捷, 郭濤, 張普含, 等. 基于軟件代碼差異分析的智能模糊測(cè)試[J]. 清華大學(xué)學(xué)報(bào)（自然科學(xué)版）, 2013, 53(12): 1726-1730.

WANG J J, GUO T, ZHANG P H, et al. Intelligent fuzzy test based on software code difference analysis[J]. Journal of Tsinghua University(Science and Technology), 2013, 53(12): 1726-1730.

[9] SHAHZAD M, SHAFIQ M Z, LIU A. X. A large scale exploratory analysis of software vulnerability life cycles[C]//International Conference on Software Engineering. 2012: 771-781.

[10] FREI S, MAY M, FIEDLER U, et al. Large-scale vulnerability analysis[C]//SIGCOMM Workshop on Large-Scale Attack Defense. 2006: 131-138.

[11] BRUMLEY D, POOSANKAM P, SONG D, et al. Automatic patch-based exploit generation is possible: techniques and implication[C]//Security & Privac. 2008.

[12] AVERY J, SPAFFORD E H. Ghost patches: fake patches for fake vulnerabilities[C]//International Conference on ICT Systems Security and Privacy Protection. 2017: 399-412.

[13] JEONG W O, CHEN S. Binary and anti-binary comparison[C]//XCon Information Security Conference. 2013: 1-27.

[14] DEBIN G, MICHAEL K R, DAWN S. BinHunt: automatically finding semantic differences in binary programs[C]//The 10th International Conference on Information and Communications Security. 2008.

[15] LANNAN L, JIANG M, DINGHAO W, et al. Semantics-based obfuscation-resilient binary code similarity comparison with applications to software plagiarism detection[J]. IEEE Transactions on Software Engineering, 2017,43(12): 1157 - 1177.

[16] ZHENG Z X, BIHUAN C, MAHINTHAN C, LIU Y, et al. SPAIN: security patch analysis for binaries towards understanding the pain and pills[C]//The 39th International Conference on Software Engineering. 2017.

[17] CAO Y, WEI Q, WANG Q X. Research on parallel symbolic execution through program dependence analysis[C]//The Fifth International Symposium on Computational Intelligence and Design. 2012: 222-226.

Software patch comparison technology through semantic analysis on function

CAO Yan1, LIU Long1, WANG Yu2, WANG Qingxian1

1. State Key Laboratory of Mathematical Engineering & Advanced Computing, Zhengzhou 450000, China 2. Henan University of Engineering, Zhengzhou 450000, China

Patch comparison provides support for software vulnerability, and structural comparison has been developed. Based on summarizing binary files comparison and anti-comparison methods, comparison technology was proposed by semantic analysis on function to address the issue that structural comparison cannot carry on semantic analysis. Through traditional structural comparison, syntax differences in function-level were analyzed to find the maximum common subgraph. Then, the path cluster was built between the input and output of the function depend on program dependency analysis. Function output characteristics was established based on symbolic execution. Semantic differences of functions were compared by functional summaries. Based on the maximum isomorphic subgraph, the matched functions which there are possible semantic changes between was further analyzed. Ultimately, the experimental results showed the feasibility and advantages of the proposed method.

vulnerability analysis, patch comparison, symbolic execution, semantic analysis

曹琰（1983? ），男，河南鄭州人，博士，數(shù)學(xué)工程與先進(jìn)計(jì)算國(guó)家重點(diǎn)實(shí)驗(yàn)室講師，主要研究方向?yàn)榫W(wǎng)絡(luò)空間安全。

劉龍（1983? ），男，河南尉氏人，數(shù)學(xué)工程與先進(jìn)計(jì)算國(guó)家重點(diǎn)實(shí)驗(yàn)室講師，主要研究方向?yàn)榫W(wǎng)絡(luò)空間安全和機(jī)器學(xué)習(xí)。

王禹（1984? ），男，河北博野人，博士，河南工程學(xué)院講師，主要研究方向?yàn)榫W(wǎng)絡(luò)空間安全和IPv6。

王清賢（1960? ），男，河南新鄉(xiāng)人，數(shù)學(xué)工程與先進(jìn)計(jì)算國(guó)家重點(diǎn)實(shí)驗(yàn)室教授、博士生導(dǎo)師，主要研究方向?yàn)榫W(wǎng)絡(luò)空間安全和軟件分析。

TP393

A

10.11959/j.issn.2096-109x.2019051

2018?09?27；

2019?01?14

曹琰，vspyan@hotmail.com

國(guó)家重點(diǎn)研發(fā)計(jì)劃基金資助項(xiàng)目(No. 2017YFB0803202，No.2016QY07X1404)

The National Key Plan R&D Program of China (No. 2017YFB0803202, No. 2016QY07X1404)

曹琰, 劉龍, 王禹, 等. 基于函數(shù)語(yǔ)義分析的軟件補(bǔ)丁比對(duì)技術(shù)[J]. 網(wǎng)絡(luò)與信息安全學(xué)報(bào), 2019, 5(5): 56-63.

CAO Y, LIU L, WANG Y, et al. Software patch comparison technology through semantic analysis on function[J]. Chinese Journal of Network and Information Security, 2019,5(5): 56-63.