ＩＡ－３２反編譯中的多分支語句恢復技術

摘 要：對IA-32反編譯后多分支結構的各種實現模式進行了系統的研究分析，并對復雜條件下典型的多分支結構實現模式進行了形式化的描述。在多分支結構的識別過程中，通過對索引表和跳轉表調用指令的格式分析，提出了雙特征指令匹配算法。通過程序切片建立了索引表和跳轉表調用的表達式標準型，消除了多分支語句恢復過程中編譯器類型和版本差異帶來的影響，提高了算法通用性，對于進行程序反解及軟件逆向工程具有重要的參考價值。

關鍵詞：多分支語句結構； 跳轉表； 識別算法； 反編譯

中圖分類號：TP11文獻標志碼：A

文章編號：1001-3695(2009)06-2359-03

doi:10.3969/j.issn.1001-3695.2009.06.108

Recovery technique of n-conditional branch statements in IA-32 decompilation

ZHANG Long-jie， XIE Xiao-fang， YUAN Sheng-zhi， LI Hong-zhou

(Dept. of Ordnance Science Technology， Naval Aeronautical Astronautical University， Yantai Shandong 264001， China)

Abstract:

This paper had a systemic research on the compiling strategy of n-conditional branch statements in IA-32 architecture， and offered a formal description to the typical realization strategy of n-conditional branch statements under intricacy mode. By analyzing the formats of calling instructions to the indexed table and the jump table， proposed a novel recognition algorithmbased on character instruction matching. To eliminate the influence caused by type and edition varieties of different compilers， it established two standard calling expressions to the indexed table and the jump table， which improved the universality of the algorithm greatly. The work of this paper has great reference value to program disassembling as well as software reverse engineering.

Key words：n-conditional branch statements; jump table; recognition algorithm; decompilation

1 多分支結構的編譯模式

在馮#8226;諾依曼體系結構下，二進制機器碼中的指令和數據均采用相同的表示方式。在機器指令進行解碼時，一個基本問題就是對指令和數據進行分離。

對于數據區的分離，傳統的方法是從可執行程序入口點開始，沿著所有可達路徑進行解碼，該方法的缺點在于當存在跳轉或索引表時（在高級代碼程序中表現為多分支語句結構，即switch-case結構，以下簡稱SC結構）不能覆蓋全部代碼空間。為解決這一問題，本文研究了IA-32模式下基于跳轉表和索引表的目標地址的恢復技術，從而可以將包含跳轉表的二進制代碼恢復為高級switch-case結構。

1.1 SC結構的語法

下面給出了一個SC結構的C代碼實現。

void main()

{

 int v;

 scanf(\"%d\"，v);

 switch(v)

 {

case 17: { printf(\"17\");break; }

case 9: { printf(\"9\"); break; }

case 7: { printf(\"7\"); break; }

case 3: { printf(\"3\"); break; }

case 5: { printf(\"5\"); break; }

default: { printf(\"Default!\\"); break;}

}

}

其中：v為索引子，用于對case分支進行選擇。各個case分支后的變量vi（此處為17、9、7、3、5）為索引變量，通常情況下為數值型常數或字符型常數。

1.2 SC結構的編譯模式

出于算法優化的需要，針對不同的case分支情況，編譯器采用了不同的實現模式。經過大量的實驗，根據索引變量vi的不同分類如下：a)vi有限且連續；b)vi有限但離散；c)vi較多但連續；d)vi較多，總體上呈離散狀態，但局部存在連續的情況；e)vi較多，總體上呈離散狀態，且局部不存在連續的情況。其中：有限是指索引變量vi的個數較少（一般不超過三個）；連續是指索引變量vi的ASCII碼是連續的；離散與連續相對應。

a)和b)屬于簡單模式，在該模式下編譯器使用線性比較序列將索引子同每個索引變量進行比較，在匯編代碼中表現為若干條條件轉移指令。由于vi個數有限，反編譯過程中可以通過if-then-else結構對其進行恢復，方法簡單，本文不再對其進行討論。c)~e)屬于復雜模式，各自的編譯方式如下：

對于模式c)，編譯器采用跳轉表的方式來實現。跳轉表中保存著各個case分支地址與跳轉表起始地址之間的偏移量，其順序即為case分支的書寫順序。對于這種模式，已有了較好的恢復算法^[1，2]。

對于模式d)，編譯器采用多個索引表和多個跳轉表相結合的方式對SC結構進行處理。針對這種模式，安全技術專家Kris Kaspersky^[3]提出了一種邏輯樹處理方法，將其統一到模式e)中。本文的重點將放在模式e)下SC結構的恢復上。

在模式e)下，編譯器采用單個索引表與單個跳轉表相結合的方式對SC結構進行實現。首先通過索引子v在索引表S中定位選擇子Si；再通過Si定位跳轉表中的偏移地址信息，從

而實現對case分支的選擇。索引過程如圖1所示。

2 研究現狀

在SC結構的識別以及恢復方面，國內外出現過一些研究^[1~5]，但這些研究大都不全面。Cifuentes等人^[1]曾對IA-32處理器模式下SC結構的幾種編譯模式進行過討論，對于不同編譯環境下代碼的組織方式也進行了對比分析，但是他們主要把重心放在模式a)~c)的研究上，沒有討論復雜情況下的模式d)e)，也沒有給出恢復算法。在IA-16處理器模式下，陳凱明^[2]對SC結構進行了研究，并利用模板庫的方式討論了模式c）下SC結構的恢復方法。該方法的優點是擴展性較強，但是在處理模式d)e)時將兩者簡單歸為一類，原因是沒有對這兩種模式下代碼的組織方式進行深入研究分析。在IA-64處理器模式下，齊寧等人^[4]對SC結構進行了研究，但面向64位系統的應用程序還沒有大規模推向市場，距離對其進行逆向處理的周期更長，實時性不強。最近，Eilam^[5]也在IA-32處理器模式下對各種方式下SC結構的編譯模式進行了探討，但沒有給出恢復算法。

綜上所述，國內外有關SC結構的研究大都不全面，所選取的處理對象總體上也以簡單模式為主，特別是在IA-32處理器模式下，沒有提出一種系統的、復雜模式下識別和恢復SC結構的算法。

本文探討了基于 IA-32處理器模式的SC結構的識別和恢復算法，并選用復雜模式下最具代表性的一種實現模式作為研究對象。通過Cifuentes等人^[1]的工作，對于同一種SC結構，不同編譯器產生的編譯模式是一致的，因此本文選用的VC編譯器亦不會使相關研究失去代表性。

3 SC結構的識別

在SC結構的識別中，采用雙特征指令匹配法，主要過程為：構造特征指令模板；獲取匯編代碼清單，識別SC結構。

1)構造特征指令模板

定義1 索引表特征指令。在由編譯器生成的可執行文件經反匯編后得到的代碼中，若存在一條形如mov reg0， reg1:[address+reg2]或mov reg0， reg1:address[reg2]的指令，則稱其為索引表特征指令，記為I。

定義2 跳轉表特征指令。在由編譯器生成的可執行文件經反匯編后得到的代碼中，若存在一條形如jmp reg1:[reg2*4+address]或jmp reg1:address[reg2*4]的指令，則稱其為跳轉表特征指令，記為J。

一般情況下，reg0為16位寄存器，reg1為32位寄存器CS或DS（有時被略去），reg2為32位寄存器eax、edx或ecx；address為地址常數或地址偏移量，則I與J就是所構造的特征指令模板。對于VC編譯器生成的可執行代碼，其特征指令模板如下：

I：mov reg16， reg32:address[eax]

J：jmp reg32:[address+edx*4]

2)識別SC結構

在對SC結構進行識別之前，首先要獲取待處理文件的匯編代碼。對于給出的SC代碼，將其生成的目標代碼經VC編譯器逆向處理后，得到的匯編代碼片段如下所示（為了節省空間，略去各case分支的具體實現代碼）：

40FA36 mov ecx，dword ptr [ebp-4];switch(v)

40FA39 mov dword ptr [ebp-8]，ecx

40FA3C mov edx，dword ptr [ebp-8]

40FA3F sub edx，3

40FA42 mov dword ptr [ebp-8]，edx

40FA45 cmp dword ptr [ebp-8]，0Eh

40FA49 ja $L352+0Fh (0040faa8)

40FA4B mov ecx，dword ptr [ebp-8]

40FA4E xor eax，eax

40FA50 mov al，byte ptr (0040fade)[ecx]

40FA56 jmp dword ptr [eax*4+40FAC6h]

40FA5D ;case 17；case vi

40FA6C ;case 9

40FA7B ;case 7

40FA8A ;case 3

40FA99 ;case 5

40FAA8 ;default

40FAC6 8A FA 40 00 ;jmp table V

40FACA 99 FA 40 00

40FACE 7B FA 40 00

40FAD2 6C FA 40 00

40FAD6 5D FA 40 00

40FADA A8 FA 40 00

40FADE 00 05 01 05 ;index table S

40FAE2 02 05 03 05

40FAE6 05 05 05 05

40FAEA 05 05 04

識別過程中，首先根據定義2在程序中搜索與跳轉表特征指令J格式相匹配的代碼語句J′；找到后再檢查J′的所有直接前驅語句中是否有與索引表特征指令I格式相匹配的代碼語句I′。I′的確認標志著識別工作的結束。在以上所示的代碼中，通過模式匹配識別出的特征指令代碼如下：

I′：mov al， byte ptr (0040fade)[ecx]

J′：jmp dword ptr [eax*4+40FAC6h]

此外，對于模式c)，由于不存在索引表特征指令，可以采用單特征指令匹配法進行識別，即文獻[1]所使用的方法，此時不再需要索引表而直接通過跳轉表中的信息進行SC結構的恢復；對于模式e)，同樣存在著兩條特征指令，因而也能通過雙特征指令匹配法將其識別出來。

4 SC結構的恢復

Cifuentes等人在簡單模式下提出了一種基于程序切片的恢復算法，本文借鑒了這一思想。對復雜模式下SC結構的恢復工作共分三步進行：a）分別在I′和J′處對代碼進行后向靜態切片處理，得到相應的切片程序CI和CJ；b）對CI和CJ進行變量等價置換處理，得到各自的表達式標準型ΩI和ΩJ；c）通過ΩI和ΩJ，恢復SC結構。

4.1 切片

識別出SC結構后，采用Weiser^[6]提出的過程內靜態后向切片算法對匯編程序P進行兩次切片處理，切片標準分別為〈I′，reg0〉和〈J′，reg2〉。其中：reg0和reg2分別為指令語句I′和J′所使用的16位和32位寄存器變量；reg2為reg0對應的32位寄存器。

對于〈I′，reg0〉，切片結束條件為reg0直接或間接從堆棧處獲得值；對于〈J′，reg2〉，切片結束條件為reg2的低位從reg0處獲得值，reg2的高位被賦值。整個過程分為兩步進行：

a）計算數據流信息。通過跟蹤數據依賴關系，使用迭代方程計算直接相關變量的集合和直接相關語句的集合，通過跟蹤數據流依賴可以確定直接相關變量，進而得到直接相關語句的集合。

b）跟蹤控制流信息。通過對控制流信息的跟蹤處理得到新的代碼語句，并將其添加到要求解的程序切片中，同時對新添加的語句重復步驟a），直到把所有相關語句包含進來為止。最終計算得到的不動點就構成期望的程序切片。

對于第3章所示的匯編代碼片段，分別以〈I′，ecx〉和〈J′，eax〉為標準進行后向切片，得到切片程序CI、CJ，如下所示：

//切片CI

40FA36 mov ecx，dword ptr [ebp-4]

40FA39 mov dword ptr [ebp-8]，ecx

40FA3C mov edx，dword ptr [ebp-8]

40FA3F sub edx，3

40FA42 mov dword ptr [ebp-8]，edx

40FA45 cmp dword ptr [ebp-8]，0Eh

40FA49 ja $L352+0Fh (0040faa8)

40FA4B mov ecx，dword ptr [ebp-8]

40FA50 mov al，byte ptr (0040fade)[ecx]

//切片CJ

40FA4E xor eax，eax

40FA50 mov al，byte ptr (0040fade)[ecx]

40FA56 jmp dword ptr [eax*4+40FAC6h]

4.2 表達式標準型

分析第3章所示的匯編代碼片段，可以從中提取到的有效信息包括機器字長、case分支的上界upper和下界lower、S和V的起始/結束地址、default分支的起始地址、case分支的個數。通過這些信息就可以對SC結構進行恢復。

由于生成目標文件的編譯器類型、版本的不同，編譯SC結構所生成的指令代碼、指令條數、指令順序和操作數的格式都不完全相同，導致信息的收集比較困難。針對這一情況，采用構造標準型表達式的方式來消除這些差異，同時要求所構造的標準型能夠包含從匯編代碼中提取到的有效信息。

通過前文代碼可知，模式e）的一般執行過程如下：

v=[stack];

v=v-lower;

if (v>span) goto default;

I: reg16=off_S[v]/[off_S+v];

J: goto reg1:off_V[reg2*4]/reg1:[off_V+reg2*4];

其中：[stack]表示堆棧內容；v∈{eax，ecx，edx}為索引子；span=upper-lower表示索引變量vi的跨度；reg2為reg0對應的32位寄存器，可統一記做reg。

分別對索引表和跳轉表切片語句進行變量等價置換，得到各自的復合表達式ΩI和ΩJ。

ΩI：([stack]-lower>upper)?(goto addr_default):(reg= off_S[[stack]])

ΩJ：goto ([reg*4+off_V])

ΩI、ΩJ即為所求的表達式標準型。其中：addr_default為default分支的起始地址；off_S為索引表S的起始地址；off_V為跳轉表V的起始地址。

對于4.1節所示的切片程序CI、CJ，通過變量等價置換處理，得到表達式標準型ΩI、ΩJ，如下所示：

ΩI：([ebp-4]-3>14)?(goto 0040faa8): (al=(0040fade) [ebp-4])

ΩJ：goto ([eax*4+40FAC6h])

4.3 SC結構的恢復

SC結構的恢復主要依賴于ΩI和ΩJ。基于ΩI、ΩJ中的有效信息就可以將SC結構恢復出來。

除可以直接獲取到的信息外，還可以從ΩI、ΩJ中推導出以下隱含信息：upper（span+lower）、V的結束地址（S的起始地址-1）、S的結束地址（S的起始地址+span+1）以及case分支的個數（統計S中的所有不同數值的個數num，則num-1即為case分支語句的個數）。此外，當lower=0時，出于性能優化考慮，編譯器將忽略對下界的判斷，此時lower取默認值0。

例如，對于上一節得到的表達式標準型ΩI、ΩJ，在取定索引子的值（如v=7）時，有[ebp-8]=7，根據ΩI、ΩJ，其索引過程如圖2所示。



最終得到的SC結構如下：

switch(v)

{

 case 17: { goto 40FA5D; break; }

 case 9: { goto 40FA6C; break; }

 case 7: { goto 40FA7B; break; }

 case 3: { goto 40FA8A; break; }

 case 5: { goto 40FA99; break; }

 default: { goto 40FAA8; break; }

}

可以看出，其結構與1.1節中的C程序代碼一致。在VC環境中對其進行編譯，得到的匯編代碼與第3章所示代碼也是一致的。

5 實驗數據與樣本分析

表1給出了某軟件逆向工程過程中得到的統計數據。

通過表1可以看出，本文提出的恢復技術不僅能夠對SC結構進行正確的識別，而且能夠將各種編譯模式下的SC結構準確地恢復出來。特別是在復雜模式d)e)下，已有算法無法對其進行重建，原因是缺少索引表的相關信息。

6 結束語

本文分析了國內外有關SC結構的研究成果，在32位處理器模式下，探討了軟件逆向工程過程中SC結構的識別和恢復算法，所提出的雙特征指令匹配技術和基于程序切片的變量等價置換技術已經在某軍用作戰軟件的逆向工程中得到應用，開發出的輔助處理軟件能夠正確地識別并恢復可執行程序中的SC結構。與已有的算法^[1，2]相比，其效率更高、定位更準確、通用性更強。此外，本文提出的恢復算法未能完全將識別出的SC結構進行重建，原因是索引表或跳轉表中存在無效項，此時對SC結構的恢復可能產生十分嚴重的異常，這是今后需要重點解決的問題。

參考文獻：

[1]CIFUENTES C， EMMERIK Mvan. Recovery of jump table case statements from binary code[J]. Science of Computer Programming， 2001，40(2-3):171-188.

[2]陳凱明. 逆編譯中幾項關鍵技術研究[D]. 合肥：合肥工業大學， 2003:37-58.

[3]KASPERSKY K. 黑客反匯編揭秘[M]. 北京: 電子工業出版社， 2005:415-432.

[4]齊寧，趙榮彩. IA-64 代碼翻譯中的跳轉表恢復技術[J]. 計算機工程， 2006，32(23):49-51.

[5]EILAM E. Recovering:逆向工程揭秘[M]. 韓琪， 楊艷， 王玉英，等譯. 北京:電子工程出版社， 2007:499-504.

[6]WEISER M. Program slicing[J]. IEEE Trans on Software Engineering， 1984，10(4):352-357.