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

有效

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

1.一種基于變量關聯樹的復雜類型重構方法，其特征在于，該方法包括如下步驟：

步驟一、將待處理的二進制程序轉化為匯編程序，并對匯編程序中的各函數單元進行變量關聯樹VRT的創建；

所述變量關聯樹VRT的節點為所述函數單元中的變量，以變量之間的關聯關系創建節點間的關聯關系；

每個變量關聯樹VRT中的節點屬性信息包括：從所述匯編程序中提取的類型約束信息屬性以及運算符屬性；所述類型約束信息屬性為節點對應變量在所述匯編程序中的類型信息，所述運算符屬性為節點對應變量在所述匯編程序中對應的運算符信息；

同時依據所述變量關聯樹VRT創建變量地址映射表VAM，所述變量地址映射表VAM中存儲有所述變量關聯樹VRT中所有節點對應變量的索引，包括變量的屬性信息，即類型約束信息屬性以及運算符屬性；

根據匯編程序對變量關聯樹VRT中節點的屬性信息進行更新得到最終VRT，同時更新變量地址映射表VAM，最終的變量地址映射表VAM包含了基本類型重構結果；

步驟二、識別篩選出根節點的運算符屬性為解引用的最終VRT作為指針VRT；

所述指針VRT根據其結構形式分為B+C形式指針VRT以及B+V+C形式指針VRT；其中B+C形式指針VRT對應的復雜類型為結構體，B+V+C形式指針VRT對應的復雜類型為數組；其中B表示基址，C表示偏移常量，V表示數組下標中的變量；

所述B+C形式指針VRT的結構形式包括如下兩種：

第一種B+C形式結構為：由一個根節點以及一個葉子節點組成，其中根節點對應的變量為T1，表示結構體中的一個成員變量，該根節點的運算符屬性為解引用，采用符號“！”表示；葉子節點對應的變量為L1，表示所述指針VRT對應的結構體的基址；

第二種B+C形式結構為：由一個根節點、一個寄存器型節點以及兩個葉子節點組成；其中根節點對應的變量為T2，表示結構體中的一個成員變量，該根節點的運算符屬性為解引用，采用符號“！”表示；寄存器型節點對應的變量為寄存器EAX，該節點的運算符屬性為加；兩個葉子節點對應的變量分別為L2和C1，其中L2表示所述指針VRT對應的結構體的基址，C1表示T2指示的成員變量在所述結構體中的偏移常量；

所述B+V+C形式指針VRT的結構形式包括如下三種：

第一種B+V+C形式結構為：根節點對應的變量為T6，表示一個數組元素，該根節點的運算符屬性為解引用，采用符號“！”表示；根節點具有一個子節點，對應的變量為T5，運算符屬性為加；T5有兩個子節點，左兒子節點對應的變量為T3，運算符屬性為取地址，采用符號“”表示，右兒子節點對應的變量為T4，運算符屬性為乘；T3有一個子節點，對應的變量為S1，運算符屬性為空；T4有兩個子節點，左兒子節點對應的變量為L3，運算符屬性為空，右兒子節點對應的變量為C2，運算符屬性為空；其中T3和T5為指針，T3指向變量S1，T5指向變量T6，T6表示一個數組元素；

第二種B+V+C形式結構為：根節點對應的變量為T11，表示一個數組元素，該根節點的運算符屬性為解引用，采用符號“！”表示；根節點具有一個子節點，對應的變量為T10，運算符屬性為加；T10有兩個子節點，左兒子節點對應的變量為T8，運算符屬性為取地址，采用符號“”表示，右兒子節點對應的變量為T9，運算符屬性為加；T8有一個子節點，對應的變量為S2，運算符屬性為空；T9有兩個子節點，左兒子節點對應的變量為T7，運算符屬性為乘，右兒子節點對應的變量為C4，運算符屬性為空；T7有兩個子節點，左兒子節點對應的變量為L4，運算符屬性為空，右兒子節點對應的變量為C3，運算符屬性為空；其中T8和T10為指針，T8指向變量S2，T10指向變量T11，T11表示一個數組元素；

第三種B+V+C形式結構為：根節點對應的變量為T15，表示一個數組元素，該根節點的運算符屬性為解引用，采用符號“！”表示；根節點具有一個子節點，對應的變量為T14，運算符屬性為加；T14有兩個子節點，左兒子節點對應的變量為ESP，運算符屬性為空，右兒子節點對應的變量為T13，運算符屬性為加；T13有兩個子節點，左兒子節點對應的變量為T12，運算符屬性為乘，右兒子節點對應的變量為C6，運算符屬性為空；T12有兩個子節點，左兒子節點對應的變量為L5，運算符屬性為空，右兒子節點對應的變量為C5，運算符屬性為空；其中ESP和T14為指針，其中ESP為寄存器的一種，稱為棧寄存器，表示棧指針；T14指向變量T15，T15表示一個數組元素；

若所述指針VRT屬于B+C形式指針VRT，執行如下S201～S202；

S201、對所有的B+C形式指針VRT，提取基址B、偏移常量C以及所述指針VRT的根節點對應的變量在所述變量地址映射表VAM中對應的類型t，得到(B，C，t)集合；

S202、在(B，C，t)集合中，按照基址B分類，根據相同基址B下的偏移常量C和類型t所占的字節大小重構基址B對應結構體的內部布局，即可以得到結構體中每個偏移常量下數據的類型及其所占字節大小，重構出結構體的內部布局；

若所述指針VRT屬于B+V+C形式指針VRT的第一種和第二種B+V+C形式結構，執行如下S211；

S211、對第一種和第二種B+V+C形式結構的指針VRT，提取基址B、數組下標中的變量V以及當前指針VRT根節點對應的變量在所述變量地址映射表VAM中對應的類型t，B即為數組首地址，根據V即可推導數組大小，t即為數組元素的類型；

若所述指針VRT屬于B+V+C形式指針VRT的第三種B+V+C形式結構，執行如下S221～S226；

S221、對所有第三種B+V+C形式結構的指針VRT，提取基址B、偏移常量C、數組下標中的變量V以及當前指針VRT根節點對應的變量在所述變量地址映射表VAM中對應的類型t，得到(B+C，V，t)集合；

S222、從(B+C，V，t)集合中獲取三元組(C，size，t)，C為偏移常量，size為根據數組下標中的變量V的取值范圍推導出的數組的大小，t為B+V+C形式指針VRT的根節點對應的變量的類型；

S223、對于共n個的三元組(C，size，t)，按照C的大小進行排序，其中排序為第i位的三元組為(C_i，size_i，t_i)，i取值為1～n；

S224、令重構迭代次數k＝1；

S225、以B+C_k為數組首地址，size_k為數組大小，t_k為數組元素的類型，進行數組重構；

S226、若存在m，滿足km＝n且C_mC_k+size_k且C_m-1C_k+size_k；則令k＝m，返回S225，否則結束該迭代過程。