基于結構語義樹的高級控制結構恢復技術

劉絮穎， 尹 青， 蔣烈輝， 劉建林

(解放軍信息工程大學信息工程學院，河南鄭州450002)

0 引 言

目前，遺產軟件的理解、維護和移植等工作變得日益重要，可執行代碼的逆向分析成為當前研究的熱點問題[1-2]。反編譯將低級代碼轉換為功能和語義上等價的高級語言代碼形式，是代碼逆向分析中的關鍵部分[3-5]。高級控制結構恢復是反編譯的重要組成部分，恢復出的高級控制結構信息用于后期的高級語言代碼生成，恢復出的高級控制結構信息的準確性與完備性直接影響反編譯結果的準確性[6-7]。

針對高級控制結構恢復問題，Cifuentes提出了啟發式算法，理論基礎是圖論和編譯技術[8-10]；Moretti等人提出了歸納算法[11-12]來識別分支指令，區間方法識別循環，但這些方法需要使用復雜Interval/DSG等數據結構，復雜數據結構會降低算法運行效率，且該方法在編譯優化的情形下無法區分相鄰分支語句，無法處理循環分支中的復合條件；Kaspersky提出了手工分析復合條件分支的方法[13]，該方法與Moretti所提的方法類似，但其自動化實現還存在很多困難。經典高級控制結構恢復算法在識別高級控制結構的正確性、效率等方面各有優勢，但是在解決高級控制結構嵌套關系的問題上都沒有提出較好的解決方案。為了解決高級控制結構嵌套關系的問題，本文提出了結構語義樹的概念，在進行控制流圖結構化之后，構建結構語義樹，從而得到高級控制結構的嵌套關系信息。最后通過前序遍歷結構語義樹，則可恢復過程的高級控制結構。準確恢復過程的高級控制結構對提高反編譯結果的正確性，代碼語義與功能的等價性等方面具有重要意義。

1 預備知識

定義1 基本塊[14-15]b=[i1,…,in-1,in],n≥1是一個滿足下列條件的指令序列：

[i1,…,in-1]∈NTI

in∈NTI

或

[i1,…,in-1,in]∈NTI

in+1是另一個基本塊的第一條指令。

其中NTI是指非轉移類指令。

由上述定義可知一個基本塊就是一個連續的單入口單出口的指令序列，如果基本塊內一條指令被執行，那么其它指令也會被執行。一個程序的指令集合能夠從程序的入口點開始被唯一地分成一組相互不重疊的基本塊。

定義2 控制流圖CFG[14-15]是一個有向圖，可定義為三元組G=(N,E,h)，其中N是結點集合，結點n∈N代表一個基本塊，E是有向邊集合，如果在控制流圖中結點m的語句能夠到達結點n的語句，則邊(m,n)在E中，其中n∈N，m∈N，h是該有向圖的頭結點。

定義3 前序遍歷[14-15]是指對圖的遍歷過程中，每個結點n的處理早于其后裔ne，入口結點h最先處理。前序遍歷不唯一。

定義4 復合結點nc代表一個高級語言中的高級控制結構，是結構語義樹中子樹的父結點，其孩子結點是由構成該高級控制結構的結點構成的，這些孩子結點可以是葉子結點nl也可以是復合結點nc，如果是復合結點nc，則說明這兩個高級控制結構之間存在嵌套關系，每個結點屬于且僅屬于一個復合結點。

定義5 結構語義樹SST是一個二元組(N,E)，其中N是結點集合，結點n∈N可以是葉結點nl或者復合結點nc，其中葉結點nl對應的是控制流圖中的基本塊，復合結點代表一個高級控制結構，E是樹的邊，邊e∈E表示高級控制結構由哪些孩子結點構成。

2 高級控制結構恢復的框架

基于結構語義樹的高級控制結構恢復框架如圖1所示。高級控制結構恢復框架由控制流圖結構化模塊，結構語義樹構建模塊，高級控制結構恢復模塊3個模塊組成。輸入控制流信息，控制流圖結構化模塊對目標代碼的控制流圖進行結構化，獲得目標程序的高級控制結構信息，結構語義樹構建模塊根據這些高級控制結構信息對控制流圖進行遍歷構建控制流圖的結構語義樹，高級控制結構恢復模塊對構建成功的結構語義樹進行前序遍歷恢復目標代碼的高級控制結構，生成結構化的結果文件。

2.1 結構化控制流圖

降序反向后序遍歷控制流圖，采用先結構化n路條件結構，再結構化循環結構，最后結構化二路條件結構的順序對控制流圖進行結構化?？刂屏鲌D結構化過程要進行三遍，在整個結構化過程中每識別出一種高級控制結構，就將該結構的頭結點、所對應的循環關閉結點或者二路分支后隨結點、N路分支后隨結點，以及各種高級控制結構的類型進行標記，最后得到具有標記信息的控制流圖。

2.2 構建結構語義樹

結構語義樹構建模塊對前期得到的含有標記信息的控制流圖進行降序反向后序遍歷，每遍歷一個結點就根據其是否含有標記信息對其進行區分，如果是葉子結點就直接加入結構語義樹中，如果是復合結點，還要再根據其標記信息采用不同方式加入到結構語義樹中?？刂屏鲌D遍歷結束后得到能夠表達目標代碼高級控制結構以及高級控制結構關系的結構語義樹。

如圖2所示，結構語義樹采用類似鄰接表的數據結構來表示，主要包括頂點結點vexnode，邊表結點edgenode。

圖2 結構語義樹的數據結構

2.3 恢復高級控制結構

程序的結構化信息包括結構模式和非結構模式，結構模式又包括順序模式，條件模式和循環模式，非結構模式主要包括非結構循環和非結構條件。為了使得反編譯的結果可讀性更好，在進行高級控制結構恢復時只考慮結構模式，對于非結構模式的情況使用goto語句來代替。

高級控制結構恢復模塊對構建成功的結構語義樹進行左優先前序遍歷，生成結構化的中間語言代碼，其中可以包括多種高級控制結構，如if-then，if-then-else，自循環，前測試循環，后測試循環，switch-case等。

圖1 高級控制結構恢復框架

3 關鍵問題的實現

3.1 結構語義樹的構建

降序反向后序遍歷控制流圖構建結構語義樹，構建過程中每遇到一個未曾訪問過的結點，就根據控制流圖中結點類型按照以下步驟進行相應處理，直到控制流圖遍歷結束：

(1)對于沒有任何標記的控制流圖結點即葉子結點，直接加結構語義樹；

(2)對于有標記的高級控制結構頭結點header，把header加入結構語義樹；

1)根據header上的標識獲得header所屬高級控制結構的高級控制結構類型等相關信息；

2)根據上述信息，針對該高級控制結構找到屬于該結構體的所有結點；

3)在結構語義樹中添加一復合結點nc1，將高級控制結構類型以及結點之間的關系附加到nc1中；

4)將屬于該高級控制結構的所有結點都鏈接到nc1上以作為其后裔。其中可以包括葉結點和復合結點，若屬于該高級控制結構的葉結點nl已經是另一個復合結點nc2的后裔，則將nc2作為孩子結點鏈接到nc1上。

構建成功的結構語義樹中如果某復合結點的孩子結點依然是復合結點，則說明該復合結點與其孩子結點之間存在嵌套關系。

算法1：遍歷控制流圖構建結構語義樹

//輸入：控制流圖

//輸出：SST

FirstNode=NULL;

n_c=sizeof(N);

For n∈N in descending reverse post order{

If(n.isloopheader){

n_c=ConLoopAdj(CFG,n,n_c);}

Else{

If(n.is2wayheader){

n_c=ConTwayAdj(CFG,n,n_c);}

Else{

If(n.isNwayheader){

n_c=ConNwayAdj(CFG,n,n_c);}

Else{

VexN=AddVexNode(n.id,FirstNode,NULL,0);

FirstNode=VexN;}}}}

算法2：檢查結點是否已經加入邊表中，若沒有則加入，否則查看其邊表的頂點結點是否已加入邊表中，遞歸查看直到找到沒有加入的結點將其加入。

//輸入：結點n，頂點結點VexN，邊表結點AdjN

//輸出：SST

If(n is a edgenode){

p=FindVexNode(n.id);

If(p is a edgenode){

CheckNodeIsIn(p,VexN,AdjN);}

Else{

q=AddAdjNode(p.id,NULL,VexN);

AdjN.next=q;

AdjN=q;}}

Else{

q=AddAdjNode(n.id,NULL,VexN);

AdjN.next=q;

AdjN=q;}

其中，ConTwayAdj()、ConNwayAdj()和ConLoopAdj()算法類似，分別用來構建二路分支結構，N路分支結構，以及循環結構，AddVexNode()建立頂點結點，AddAdjNode()建立邊表結點。

3.2 高級控制結構恢復

結構語義樹構建完成后對其進行從左至右的前序遍歷，如果當前結點未被訪問過，則分兩種情況對其進行分析：

(1)如果結點是葉子結點，則直接輸出該結點內的語句。

(2)如果結點是復合結點nc，則根據nc上所標記的高級控制結構的類型輸出不同的關鍵詞，再根據該高級控制結構不同分支判斷基本塊屬于哪路分支，按照控制流圖的關系輸出基本塊內語句。

判定各種高級控制結構的條件，當條件為真的時候，高級控制結構體被執行。如果進入結構體內的分支是“假”分支，則說明當條件為假的時候，結構體被執行，那么條件需要求否。

恢復過程中比較復雜的是if-then-else結構的恢復，因為該結構有兩條分支，所以必須區分在該高級控制結構內的結點分別屬于哪一條分支子樹。算法描述如下：

(1)輸出關鍵字，根據頭結點Root和左孩子結點S的邊的屬性輸出條件；

(2)輸出左孩子結點S；

(3)在S的下一個兄弟結點T不為空的情況下：

1)如果S是葉子結點，查看結點T是否是S的后繼結點：

A如果是，說明T和S在同一棵子樹中即同一條分支，輸出結點T中語句；

B如果不是，則查看T是否是復合結點：

a如果是，則查看T的左孩子是否是S的后繼：

a)如果是，則T和S在同一棵子樹中，繼續輸出該子樹；

b)如果不是，則T和S不在同一棵子樹中，那么輸出“else”關鍵字，開始輸出右子樹；

b如果不是，則T和S不在同一棵子樹中，那么輸出“else”關鍵字，開始輸出右子樹；

2)如果S是復合結點，那么結點T必然和S在同一子樹中，則繼續輸出該子樹；

(4)將 S 置結點 T，轉到(3)；

4 結構語義樹示例

因為構建結構語義樹過程中最后遍歷的結點是控制流圖的根結點，如果該結點不是任何高級控制結構的頭結點，則在結構語義樹中只加入該葉子結點即可，而結構語義樹的根結點即為一個虛根結點，即在實際構建的過程中不需要再構建該復雜結點，這樣在高級語言代碼生成過程中沿著結構語義樹依次遍歷即可；如果該結點是某種高級控制結構的頭結點，則需要在結構語義樹中加入該頭結點的葉子結點，且加入一個復雜結點表示整個高級控制結構，這時候要根據高級控制結構類型來判定：如果高級控制結構是無窮循環，即高級控制結構沒有出口，那么結構語義樹的根結點是一個實際存在的結點，即實根結點，如圖3所示；否則高級控制結構有出口，即高級控制結構必然有后隨結點，那么結構語義樹的根結點依然是虛根結點，如圖4所示。其中：矩形表示復合結點，復合結點中包含了有關該高級控制結構的一切信息；圓表示葉子結點，即控制流圖中的基本塊。

圖3 實根結構語義樹

5 實驗結果

斐波那契數列函數的源碼及其匯編表示如圖5所示。

圖4 虛根結構語義樹

對該可執行文件進行高級控制結構恢復后的部分中間表示結果如圖6所示，其中r0負責傳遞參數以及存儲函數返回值，m32[r13-4-16]對應于源程序中的m，while循環對應于源程序中的for循環，其中m32[r13-4-32]對應于循環計數i，循環體內的m32[r13-4-28]、m32[r13-4-24]、m32[r13-4-20]分別對應于源程序中的f2、f1、f0。實驗結果表明該方法能夠正確無誤地恢復整個程序的高級控制結構。

并且我們選取了x86和ARM體系結構下的多個常用可執行文件進行測試，測試平臺為：Windows XP操作系統，Pentium4處理器，1G內存，測試結果如表1所示。

表1中S/F代表恢復成功或者失敗。測試結果表明該算法能夠成功恢復出不同體系結構下的可執行代碼的高級控制結構，且因其無需復雜數據結構，因此算法運行速度快，效率高，效果好。

圖5 測試用例源碼及匯編表示

圖6 高級控制結構恢復結果

表1 測試結果

6 結束語

本文提出了反編譯中恢復高級控制結構的新方法，即采用結構語義樹來表達目標代碼中的控制結構以及控制結構間關系信息，通過對結構語義樹進行前序遍歷可以完整恢復目標代碼中的高級控制結構，該方法解決了經典算法中高級控制結構嵌套關系難以恢復的關鍵問題。經過實驗驗證，該算法具有通用性，且運行效果良好，完成了反編譯中高級控制結構恢復的功能，恢復出的高級控制結構信息為后面生成高級語言代碼提供了非常大的幫助，提高了反編譯結果的準確性與可讀性。

[1]蔣烈輝.固件代碼逆向分析關鍵技術研究[D].鄭州:解放軍信息工程大學,2007:1-6.

[2]Eldad Eilam,Elliot Chikofsky.Reversing:逆向工程解密[M].韓琪,譯.北京:電子工業出版社,2007:13-46.

[3]José Manuel Rios Fonseca.Interactive decompilation[D].Portugal:Faculty of Engineering of the University of Porto,2006.

[4]Huang Hai,Jiang Liehui.A decompilation model based multiple disassemble front-end result[C].Jiaozuo:Proceeding of Information Technology and Environmental System Sciences,2008:769-773.

[5]Kinder J,Veith H.Jakstab:a static analysis platform for binaries[C].Proceedings of the 20th International Conference on Computer Aided Verification,2008:423-427.

[6]韋韜,毛劍,鄒維.反編譯中的復合條件分支識別算法[J].北京大學學報,2008,44(1):37-43.

[7]Tao Wei,Jian Mao,Wei Zou,et al.A newalgorithm for identifying loops in decompilation[C].Riis Nielson H,File G.SAS.Berlin,Heidelberg:Springer-Verlag,2007:170-183.

[8]Ung D,Cifuentes C.Dynamic re-engineering of binary code with run-time feedback[C].Science of Computer Programming,2006:189-204.

[9]Mike Van Emmerik.Boomerang[EB/OL].http://boomerang.sourceforge.net,2006.

[10]Grammatech Inc.CodeSurfer/x86[EB/OL].http://cayuga.grammatech.com/research/cs-x86,2009.

[11]Zhang Jingbo,Zhao Rongcai,Pang Jianmin,et al.A high-level control structure recovery method based on propositional calculus[C].Second International Conference on Future Information Technology and Management Engineering,2009:155-158.

[12]Eric Moretti,Gilles Chanteperdrix,Angel Osorio.New algorithms for control-flow graph structuring[C].Fifth European Conference on Software Maintenance and Reengineering,2001:184-187.

[13]Kaspersky K.Hacker disassembling uncovered[M].A-List LLC,2004:378-385.

[14]馬其尼克.高級編譯器設計與實現[M].趙克佳,沈志宇,譯.北京:機械工業出版社,2005:163-165.

[15]Alfred V Aho,Monica S Lam,Ravi Sethi,et al.Ullman編譯原理[M].趙建華,譯.2版.北京:機械工業出版社,2009:338-353.