基于函數語義分析的軟件補丁比對技術

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

基于函數語義分析的軟件補丁比對技術

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

(1.數學工程與先進計算國家重點實驗室，河南 鄭州 450000；2. 河南工程學院，河南 鄭州 450000)

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

漏洞分析；補丁比對；符號執行；語義分析

1 引言

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

補丁比對技術的發展已有近20年的歷史。1999年的BMAT[1]是補丁比對技術的開端，研究在兩個可執行文件中函數匹配的問題，該方法嚴重依賴于符號文件。

指令級別的同構比較受編譯器優化和函數匹配的影響較大，需要進一步改進，而利用調用圖及控制流圖進行比較的結構化比較方法可以很好地解決匹配問題，并且在一定程度上解決編譯器優化所帶來的問題。2004年，Flake[2]提出了基于結構化比較的二進制文件比較方法。同時，Flake還提出了使用函數的指紋（fingerprints）進行比較，開發了著名的Bindiff。

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

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

研究人員也將結構化比對技術應用于指導模糊測試和Concolic（Concrete & Symbolic的合成）測試[7-8]；基于補丁比對技術對修補方式進行識別，還可以開展針對未打補丁原文件的利用代碼自動生成技術的研究[9-11]。

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

如果混淆技術使用于軟件補丁代碼的編寫過程中，則基于結構化比對的準確率會降低。為了實現更為精準的分析，在一定程度上抵抗代碼混淆，使結構化差異分析更加精確，相關研究人員提出了在結構化比對結構基礎上，分別利用基本塊語義和trace語義信息進一步加強比對結構的精確度[14-16]。

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

2 問題的提出

通過比對原文件（unpatch）文件和補丁文件（patched）文件之間代碼結構的差異，掌握修補漏洞的方式。

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

在進行比較分析后，重點關注的是不匹配部分和發生改變的匹配部分的集合=N∪N∪M∪M，進一步分析，是漏洞或補丁最有可能出現的位置。

圖1 補丁比較差異示意

本文提出的基于函數語義分析的軟件補丁比對方法是符號執行技術與圖同構匹配的結合，其主要步驟如下。

步驟1 對函數調用圖、控制流圖進行同構比較。找出兩個調用圖之間的最大同構子圖，目的是找出漏洞或補丁存在的可疑函數集合=N∪N∪M，其中M=M∪M。

步驟2 對集合M中的函數對進行語義比較。進一步排除結構特征發生變化而語義無變化的函數對，重點關注真正語義發生變化的函數對，以更加精準定位漏洞所在函數。

3 基于圖形同構的函數級結構化比較

基于結構特征簽名信息的比較是目前主流的同構匹配方法。選用能夠表達結構化特征的屬性集合作為函數簽名，可選的函數簽名屬性包括函數名、節點的入度/出度、遞歸屬性、循環體（while循環、for循環等）、相同字符串引用、可歸約結構的素數乘積、參數個數、標準應用程序編程接口（API, application programming interface）函數調用、棧布局、遠程過程調用（RPC, remote procedure call）函數等。函數簽名間的歐幾里得德距離用于表示相似程度。

根據上述的設計簽名，對于原文件中的函數A和補丁文件中的函數B，如果A和B匹配，需要同時滿足以下3個條件。

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

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

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

在進行了函數同構比較后，找到了最大同構子圖。接下來，在最大同構子圖的基礎上，對已匹配函數未發生結構變化的函數對M進行語義比較，以判斷發生了語義變化的函數對。

4 基于符號執行的函數級語義比較

函數級語義比較的基本思路是：基于程序依賴圖（PDG, program dependence graph）分析函數輸入、輸出之間的依賴關系，構建路徑包絡；基于符號執行計算函數輸出的符號值，每個路徑包絡對應一個輸出的符號值；根據函數輸入、路徑包絡和輸出關系建立函數摘要，通過比對函數摘要信息，判斷兩個函數間的輸入、輸出之間是否存在相似關系，進而判斷函數語義（功能）等價性。

4.1 函數功能相似性的判定原理

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

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

4.2 基于路徑包絡分析的執行結果計算

函數的輸出因為路徑條件的約束可能會產生多個，即多條執行路徑可能會產生不同的輸出值。對于執行路徑比較復雜的函數，如函數體包含的子調用、循環等較多時，如果遍歷每條路徑將輸入參數代入符號值運算，以計算函數輸出符號值，顯然模擬計算帶來的開銷和龐大的路徑導致計算量很大，效率較低。為了快速分析全部的輸出值，可以對控制程序執行路徑的約束條件進行歸約，將對函數輸出符號值產生相同程序依賴影響的路徑集合構建成路徑包絡，在路徑包絡內部計算輸出符號值的計算，而無須遍歷全部路徑。

圖2 路徑包絡構建流程

4.2.1 基于PDG的路徑包絡構建

路徑包絡歸約是為了提取影響目標點符號值的關鍵路徑控制條件，而去除對目標點符號值無影響的路徑條件，即無用控制條件。路徑包絡的構建是建立在對程序控制和數據依賴分析基礎上的，PDG能夠反映程序的控制依賴關系和數據依賴關系。因此，可以根據PDG的相關分析，建立路徑包絡。本文中研究的目標點是4.1節提到的函數輸出，下文均用目標點闡述。

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

探索從函數入口點到目標點具備相同運算符號值的路徑集合，如圖2所示，基本流程是：通過入口點和目標點的公共依賴域分析，建立局部程序依賴關系；通過反向數據依賴分析，探索與目標點具有數據依賴關系的語句集合；如果沒有新的數據依賴語句加入則結束，否則，通過反向控制依賴分析，探索與數據依賴語句具有控制依賴關系的關鍵路徑控制條件；以關鍵控制路徑條件為目標點，探索與之具有數據依賴關系的語句集合；當新的數據依賴語句不再發生變化時，對具有兩個布爾值的關鍵路徑控制條件進行消減（無用控制條件），構建路徑包絡。

針對包絡構建流程，本文提出了面向函數的路徑包絡構建算法（PCE）。該算法主要功能是在PDG上分析程序的控制依賴和數據依賴關系，根據函數入口點和函數輸出點，找到到的路徑包絡集合。

算法 路徑包絡構建算法

輸入：待分析函數

：函數入口點

：函數輸出點

輸出—歸約的路徑包絡

1)=Ф

2)(,)

3)=(,′)

4)to=(,)

5)=⊕to T

6)(ifather,)

7)1=(ifather,)

8)=⊕1

9) return

路徑包絡構建算法描述如下。

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

步驟2 基于PDG分析以為根節點的樹上所有節點與節點的數據依賴關系，剪除與節點數據依賴無關的控制依賴域節點及其子樹。

步驟3 生成到′的路徑包絡，′是的直接后繼節點，并且是的祖先。

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

步驟5 生成從到ifather的路徑包絡。

步驟6 基于PDG分析以ifather為根節點的子樹上的所有節點和的數據依賴關系，剪除與節點數據依賴無關的控制依賴域節點及其子樹。

步驟7 生成從ifather的直接后繼節點到的路徑包絡1。

步驟8 將到ifather的路徑包絡與1聯合，生成到的路徑包絡。

步驟9 輸出歸約的路徑包絡結果。

其中，子算法DataDependenseCut和GatherPC在文獻[17]中已經提出。

4.2.2 函數執行結果符號值計算

本文采用符號執行以實現函數功能的相似性比較，見4.1節。因為只需要比較函數輸出時的符號值是否相同，無須進行具體值的運算。但在符號執行過程中，會遇到外部調用、循環等問題，如果處理不當，會影響輸出符號值的計算結果。

鑒于函數內部單元符號執行特點和語義比對的需求，在處理外部調用和循環問題時可簡化處理。

1) 外部調用：不跟進外部調用的執行，將調用的子函數名直接作為符號帶入后續符號執行過程。包含子函數名的符號值相當于黑盒運算。

2) 循環計數：將循環計數與函數變量或輸入參數關聯，循環體內的運算結果與循環計數關聯。

因為語義分析是針對函數輸出符號值的比較，不需要進行約束求解，因此可以接受符號化的子函數調用和循環計數。

4.3 基于函數摘要分析的語義比對

在補丁文件發布時，可能加入針對控制流圖或函數調用圖的混淆機制[14-15]，干擾補丁分析結果。為了有效識別混淆代碼，剪除不可能執行到達的分支路徑以及由此帶來的函數偽輸出，需要對包絡的關鍵路徑條件進一步分析，發現可能存在的約束沖突，將該包絡產生的函數輸出標記為偽輸出，從函數執行結果的比對中剔除。

函數摘要技術一般用于頻繁執行某個函數時，只在第一次執行或未執行時靜態分析，建立該函數的輸入輸出映射關系，以便在后續調用該函數時可以復用摘要信息，代替實際執行該函數。

在本文中，通過路徑包絡的構建，建立函數輸入、輸出符號值之間的映射關系。函數摘要用三元組表示，如下。

1) Input：表示函數輸入，這里的輸入包括全局變量、函數體內定義的局部變量、函數參數等對應的符號值。

2) Constrant：表示路徑包絡對應的關鍵路徑條件及其取值。

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

函數摘要構建時，為了解決混淆代碼的影響，需要對路徑包絡的關鍵約束條件進行相容檢查，發現可能存在的約束沖突，從而將不可能產生的函數輸出和對應的Output和約束條件Constrant刪除，在一定程度上可以緩解混淆代碼的影響。

約束相容性檢查后，對處理過的函數摘要進行比較。相同語義的函數對，可能因為分配的輸入符號不同，導致輸出符號值不同。這里對輸出符號值的比較不能用簡單的匹配方式實現，必須找到一組相應的序列映射，才可能判斷函數是否有語義差別。具體的形式化定義描述如下。

圖3 SymDiff系統結構

5 系統實現

按照前文設計思路，本文實現了補丁比對工具SymDiff，其基本構成如圖3所示。

1) 反匯編器

系統使用的反匯編器是IDA Pro，本文設計的補丁比對插件SymDiff是在IDA PRO 5.5版本上實現的。系統需要使用IDA的反匯編及插件功能。

2）函數級同構比較

運用圖同構匹配方法進行結構化比對，生成最大同構子圖。函數簽名模塊從待比較文件中提取簽名信息，利用同構算法在函數調用圖級進行分析，生成比對結果。詳細的過程見第3節內容。

3）函數級語義比較

在最大同構子圖基礎上，運用符號執行的方法對函數輸入輸出特征進行語義級比對。也就是說，對于集合M中的函數對進行語義比較，找出發生了功能變化的匹配函數對，從而找到補丁具體修補的指令。具體方法見第4節內容。

6 實驗分析

1) 測試目的

本節通過SymDiff與當前常用的開源補丁比對工具PatchDiff2進行比對測試，以驗證本工具在確定可疑函數精度方面的優勢。

2) 測試工具

自主開發的補丁比對分析工具SymDiff和開源工具PatchDiff2如表1所示。

表1 比對測試工具

3) 測試對象

CVE-2006-3439、CVE-2008-4205、CVE-2010- 2746、CVE-2017-6178這4個漏洞對應的原文件和補丁文件，如表2~表5所示。

表2 CVE-2006-3439文件

表3 CVE-2008-4205文件

表4 CVE-2010-2746文件

表5 CVE-2017-6178文件

4) 測試方法

使用兩個工具對4個比較對象進行補丁比對，記錄漏洞所在函數/修補函數對數量，記錄可疑函數對M數量。通過和的比值，判斷比對工具對可疑函數篩選的精度。

5) 測試結果

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

表6 比對測試結果

7 結束語

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

[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] 潘璠, 吳禮發, 孫傳魯, 等. 一種改進的補丁比較模型的研究與實現[J]. 南京郵電大學學報（自然科學版）, 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] 肖雅娟.二進制代碼函數相似度匹配技術研究[D]. 濟南: 山東大學, 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] 王欣, 郭濤, 董國偉, 等. 基于補丁比對的Concolic測試方法[J]. 清華大學學報（自然科學版）, 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]. 清華大學學報（自然科學版）, 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? ），男，河南鄭州人，博士，數學工程與先進計算國家重點實驗室講師，主要研究方向為網絡空間安全。

劉龍（1983? ），男，河南尉氏人，數學工程與先進計算國家重點實驗室講師，主要研究方向為網絡空間安全和機器學習。

王禹（1984? ），男，河北博野人，博士，河南工程學院講師，主要研究方向為網絡空間安全和IPv6。

王清賢（1960? ），男，河南新鄉人，數學工程與先進計算國家重點實驗室教授、博士生導師，主要研究方向為網絡空間安全和軟件分析。

TP393

A

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

2018?09?27；

2019?01?14

曹琰，vspyan@hotmail.com

國家重點研發計劃基金資助項目(No. 2017YFB0803202，No.2016QY07X1404)

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

曹琰, 劉龍, 王禹, 等. 基于函數語義分析的軟件補丁比對技術[J]. 網絡與信息安全學報, 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.