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

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

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

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

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

漏洞分析；補(bǔ)丁比對；符號執(zhí)行；語義分析

1 引言

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

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

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

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

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

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

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

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

2 問題的提出

通過比對原文件（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ù)語義分析的軟件補(bǔ)丁比對方法是符號執(zhí)行技術(shù)與圖同構(gòu)匹配的結(jié)合，其主要步驟如下。

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

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

3 基于圖形同構(gòu)的函數(shù)級結(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ì)簽名，對于原文件中的函數(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ǔ)上，對已匹配函數(shù)未發(fā)生結(jié)構(gòu)變化的函數(shù)對M進(jìn)行語義比較，以判斷發(fā)生了語義變化的函數(shù)對。

4 基于符號執(zhí)行的函數(shù)級語義比較

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

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

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

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

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

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

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

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

路徑包絡(luò)歸約是為了提取影響目標(biāo)點(diǎn)符號值的關(guān)鍵路徑控制條件，而去除對目標(biāo)點(diǎn)符號值無影響的路徑條件，即無用控制條件。路徑包絡(luò)的構(gòu)建是建立在對程序控制和數(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)算符號值的路徑集合，如圖2所示，基本流程是：通過入口點(diǎn)和目標(biāo)點(diǎn)的公共依賴域分析，建立局部程序依賴關(guān)系；通過反向數(shù)據(jù)依賴分析，探索與目標(biāo)點(diǎn)具有數(shù)據(jù)依賴關(guān)系的語句集合；如果沒有新的數(shù)據(jù)依賴語句加入則結(jié)束，否則，通過反向控制依賴分析，探索與數(shù)據(jù)依賴語句具有控制依賴關(guān)系的關(guān)鍵路徑控制條件；以關(guān)鍵控制路徑條件為目標(biāo)點(diǎn)，探索與之具有數(shù)據(jù)依賴關(guān)系的語句集合；當(dāng)新的數(shù)據(jù)依賴語句不再發(fā)生變化時(shí)，對具有兩個(gè)布爾值的關(guān)鍵路徑控制條件進(jìn)行消減（無用控制條件），構(gòu)建路徑包絡(luò)。

針對包絡(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é)果符號值計(jì)算

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

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

1) 外部調(diào)用：不跟進(jìn)外部調(diào)用的執(zhí)行，將調(diào)用的子函數(shù)名直接作為符號帶入后續(xù)符號執(zhí)行過程。包含子函數(shù)名的符號值相當(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義分析是針對函數(shù)輸出符號值的比較，不需要進(jìn)行約束求解，因此可以接受符號化的子函數(shù)調(diào)用和循環(huán)計(jì)數(shù)。

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

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

函數(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ù)輸入、輸出符號值之間的映射關(guān)系。函數(shù)摘要用三元組表示，如下。

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

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

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

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

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

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

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

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

1) 反匯編器

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

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

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

3）函數(shù)級語義比較

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

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

1) 測試目的

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

2) 測試工具

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

表1 比對測試工具

3) 測試對象

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

表2 CVE-2006-3439文件

表3 CVE-2008-4205文件

表4 CVE-2010-2746文件

表5 CVE-2017-6178文件

4) 測試方法

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

5) 測試結(jié)果

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

表6 比對測試結(jié)果

7 結(jié)束語

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

[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] 王欣, 郭濤, 董國偉, 等. 基于補(bǔ)丁比對的Concolic測試方法[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] 王嘉捷, 郭濤, 張普含, 等. 基于軟件代碼差異分析的智能模糊測試[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ì)算國家重點(diǎn)實(shí)驗(yàn)室講師，主要研究方向?yàn)榫W(wǎng)絡(luò)空間安全。

劉龍（1983? ），男，河南尉氏人，數(shù)學(xué)工程與先進(jìn)計(jì)算國家重點(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ì)算國家重點(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

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

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

曹琰, 劉龍, 王禹, 等. 基于函數(shù)語義分析的軟件補(bǔ)丁比對技術(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.