[發明專利]一種基于變量關聯樹的復雜類型重構方法

有效

• 申請號: 201810793950.2
• 申請日: 2018-07-19
• 公開（公告）號: CN108897572B
• 公開（公告）日: 2020-09-15
• 發明（設計）人: 胡昌振;馬銳;菅澤峰;朱天保;劉健雄
• 申請（專利權）人: 北京理工大學;北京計算機技術及應用研究所
• 主分類號: G06F8/72
• 分類號: G06F8/72
• 代理公司: 北京理工大學專利中心 11120
• 代理人: 高會允;仇蕾安

本發明公開了一種基于變量關聯樹的復雜類型重構方法，該方法具體為：將待處理的二進制程序轉化為匯編程序，并對匯編程序中的各函數單元進行變量關聯樹VRT的創建；依據變量關聯樹VRT創建變量地址映射表VAM；根據匯編程序對變量關聯樹VRT中節點的屬性信息進行更新得到最終VRT，同時更新變量地址映射表VAM，最終VRT對應的變量地址映射表VAM包含了匯編程序的基本類型重構結果。識別篩選出根節點的運算符屬性為解引用的最終VRT作為指針VRT，其中B+C形式指針VRT對應的復雜類型為結構體，B+V+C形式指針VRT對應的復雜類型為數組，對于B+C形式指針VRT和B+V+C形式指針VRT分別采用不同的方法進行結構體和數組的重構。該方法能夠實現快速、有效的復雜類型重構，且重構結果較為準確。

技術領域

本發明涉及軟件維護和安全技術領域，具體涉及一種基于變量關聯樹的復雜類型重構方法。

背景技術

反編譯是編譯的逆過程，其目標是將二進制代碼轉換成與之邏輯和功能等價的高級語言形式。源程序中變量的結構類型決定了變量的存儲空間和使用規則，然而源代碼經過編譯優化之后，有關程序的類型及調試信息都不復存在，轉而以匿名的字節塊信息代之，通過內存的分配訪問形式及其相互間的依賴關系體現變量的類型信息。隨著第三方軟件的大量使用，出于安全的考慮，越來越多的軟件需要進行安全分析，檢測軟件中是否含有漏洞以及惡意代碼，而常規手段就是對比分析程序中的數據結構類型。類型重構作為“源代碼再現”的過程，能夠有效增強代碼的可讀性，提高程序分析的效率。類型重構的原則通常是先恢復基本類型，而后通過綜合的分析方法恢復出復雜數據類型。

類型重構屬于反編譯過程中重要步驟之一，而數據類型重構又可以分為基本類型重構和復雜類型重構，現階段對于基本類型重構的研究和技術已經比較成熟，但對于復雜類型重構卻沒有比較深入的研究能夠得出好的結果。

目前的復雜類型重構方案有靜態的，主要思想是基于中間語言，對指針進行分析，但存在指針別名問題，處理較為困難；大多數方案是動態的，主要思想是基于中間語言，在指針使用處插入插樁代碼，再將中間語言翻譯成可執行程序(或模擬運行環境下的可執行程序)，(模擬)運行程序，獲得指針變量指向的實際地址，根據這些地址重構復雜類型的內部布局。但動態方法準確率較低，重構結果往往需要手工去重等處理。

Mycroft在1999年提出的Type-based decompilation系統能夠恢復不同架構下二進制代碼中常規的變量類型，該系統先把可執行代碼轉化為RTL(Register TransferLanguage)代碼以達到跨架構的目標，然后為RTL指令添加約束條件，最后為約束方程求解以獲得變量的類型信息。但該方法無法避免約束求解方法的通病，即約束方程可能無解或多解，同時該方法對復雜變量類型也無法恢復。

2007年，Ilfak Guilfanov發布了反匯編器IDA Pro的一個反編譯插件Hex-Rays，這是一款功能強大的商業軟件，它能快速地將32位windows可執行程序轉換成與源碼功能和語義等價的類C代碼，但只可用于分析而不能編譯。它對函數的參數和返回值檢測很準確，但對于變量的符號及復雜類型的重構效果欠佳。

2008年由A.Cozzie等人提出的Laika系統，利用動態分析的方法對數據結構進行恢復。該系統采用了貝葉斯自適應算法檢測數據結構，但是其結果很不準確，并且不能處理復雜類型結構。對于結構化的類型變量，只能給出結構的大體輪廓，無法對其內部成員變量的類型進行處理。

卡耐基梅隆大學的Jong Hyup Lee在2011年提出了基于規則的可執行程序的類型重構方法，先使用BAP(Binary Analysis Platform)將二進制代碼轉化為靜態單賦值SSA(Static Single Assignment)的形式，然后對推斷出的變量做類型標記，根據這些變量的使用產生對應的類型約束，最后對約束求解。該方法雖能識別指針，但對結構、數組和指針都一概而論，未做區分。

因此目前缺少一種有效準確的方案來實現復雜類型的重構。