C++反編譯中控制流圖優(yōu)化方法研究

蔣海蘇，杜承烈

（西北工業(yè)大學(xué) 計算機學(xué)院，陜西 西安 710129）

反編譯是把可執(zhí)行的二進制代碼轉(zhuǎn)換成功能等價的可讀性強的高級語言代碼的過程[1]。反編譯是逆向工程的重要的步驟，在軟件的理解、維護、復(fù)用和開發(fā)方面發(fā)揮了重要的作用。近年來由于C++及其他面向?qū)ο笳Z言逐漸成為主流語言，現(xiàn)有的大量C++程序由于各種原因需要進行逆向工程。目前，已經(jīng)有一些反編譯器可用，如：IDA Hex_rays[2]，Boomerang[3]和C-Decompiler[4]。然而，使用這些工具對C++程序進行反編譯都普遍存在結(jié)果正確性低的問題。除去反編譯固有的困難外，還有就是反編譯生成的都是類C偽代碼，沒有考慮到C++語言的特性。

反編譯的基本步驟有：1）反匯編，將二進制代碼識別為匯編語言；2）庫函數(shù)識別，識別庫函數(shù)，分析調(diào)用入口；3）流程分塊，將程序分為獨立的可執(zhí)行模塊；4）控制流分析，對流程進行分析，為生成高級語言控制流做準(zhǔn)備；5）類型分析，識別數(shù)據(jù)的類型。最終生成可理解的高級語言代碼。其中步驟1），2）都有不少論文介紹這方面工作。其中，文獻[5]介紹了靜態(tài)反匯編的兩種方法。文獻[6]介紹了C++庫函數(shù)的識別方法。而且現(xiàn)在也出現(xiàn)了成熟的反匯編分析工具，如IDA。控制流分塊與控制流分析是反編譯器中間的部分，為輸出的高級語言代碼生成提供依據(jù)[7]，直接影響到生成高級代碼的正確性。文中首先介紹了現(xiàn)有的控制流分塊方法以及C++與C語言存在的差異，提出了一種針對C++語言改進控制流分塊的方法，并給出了實驗驗證。

1 控制流圖及其劃分方法

控制流圖是描述程序內(nèi)部流程的圖形表示。使用控制流程圖可以很容易地將它們轉(zhuǎn)化為高級語言的控制結(jié)構(gòu)以及形象地展示給逆向人員進行分析。圖1給出了3種典型的控制流圖結(jié)構(gòu)。分別是 if結(jié)構(gòu)，if…else… 和 for…結(jié)構(gòu)，圖中的圓圈表示基本塊。

圖1 3種典型的控制流結(jié)構(gòu)Fig.1 Three kinds of typical control flow structures

傳統(tǒng)的劃分控制流圖的方法是：將匯編指令分為兩類，轉(zhuǎn)移指令和非轉(zhuǎn)移指令。轉(zhuǎn)移指令是一些指令的集合，這些指令把指令執(zhí)行流（即IP寄存器的值）轉(zhuǎn)移到內(nèi)存中不同于下一條指令地址的地址。這些指令有：無條件跳轉(zhuǎn)（jmp），條件跳轉(zhuǎn)（jnb，je，jbe 等），子程序調(diào)用（call），子程序返回（ret）。除去這些指令外，其他的都是非轉(zhuǎn)移指令?；緣K總是以轉(zhuǎn)移指令的轉(zhuǎn)移目的地址或者轉(zhuǎn)移指令的下一條指令為開始，轉(zhuǎn)移指令或者轉(zhuǎn)移指令轉(zhuǎn)移目標(biāo)地址的前一條指令結(jié)束。并且基本塊內(nèi)部是連續(xù)的非轉(zhuǎn)移指令集。基本塊之間按照地址順序相連或者根據(jù)跳轉(zhuǎn)目的相連。按照這樣劃分基本塊非常具體，但也常常因為程序或某個函數(shù)過于復(fù)雜而導(dǎo)致控制流圖過于復(fù)雜。文獻[8]也給出了一些控制流圖的優(yōu)化方法，如：兩條連續(xù)的無條件跳轉(zhuǎn)到同一地址的指令，它們之間沒有任何的其他指令。另外一種優(yōu)化方式是根據(jù)語義進行優(yōu)化。例如：call指令雖然將程序的執(zhí)行流程改變，但是在執(zhí)行完子程序之后仍然返回執(zhí)行call之后的下一條指令。那么在這個方法中，call并沒有將執(zhí)行流程改變。那么將以call指令劃分的兩個基本塊合并為一個。這樣就能夠減少不少順序的基本塊（特別是在函數(shù)調(diào)用較多的情況下）。IDA的控制流圖就是采用這種優(yōu)化方式顯示的。

控制流圖生成之后，經(jīng)過中間的控制流分析，生成對應(yīng)的高級語言。生成的代碼的流程基本上依賴于控制流圖結(jié)構(gòu)。如圖1中的控制流圖將被翻譯成if，if…else…，for…等。

2 現(xiàn)有的控制流圖用于C++反編譯存在的問題

C++語言雖然是由C語言發(fā)展而來，但卻與C語言有著很多區(qū)別。主要區(qū)別有：繼承、多態(tài)、模板等，對于目標(biāo)代碼有較大的影響[7]。由于C++是面向?qū)ο蟮恼Z言，支持用戶自定義的類型的向上自動轉(zhuǎn)換。而這些由C++編譯器實現(xiàn)的，而這其中就有可能產(chǎn)生控制流。如果不加以區(qū)分，反編譯生成的控制流將有很大區(qū)別。如圖2中，UML類圖描述了3個類的關(guān)系以及一個函數(shù)原型，控制流圖中虛線表示條件成立時的流程。雖然從C++語言的角度來看，只是一條普通的函數(shù)調(diào)用語句，但是其對應(yīng)的匯編語言確是包含有一個分支選擇結(jié)構(gòu)（編譯環(huán)境為Visual Studio 2005）。生成或者是模塊1中跳轉(zhuǎn)語句為jnz xxx，那么模塊2，3中的語句（除jmp外）剛好相反了。不管怎樣，反編譯器會將其翻譯成一個if…else…的偽代碼結(jié)構(gòu)。顯然這種結(jié)構(gòu)是多余的，在流控圖中增加基本塊，使得控制流圖更加復(fù)雜。

造成這種情況的原因是，C++作為一種面向?qū)ο笳Z言，它支持對象的類型自動向上轉(zhuǎn)換操作。因為當(dāng)對象的指針為NULL時，轉(zhuǎn)換后對象指針也為NULL[9]。這才會在底層匯編代碼中出現(xiàn)分支選擇的控制結(jié)構(gòu)。而對象的自動向上類型轉(zhuǎn)換在一些大型的面向?qū)ο罂蚣苤幸彩谴罅看嬖诘?，這將使得C++反編譯中的控制流圖更加復(fù)雜，反編譯器也會對此生成許多冗余的if…else…結(jié)構(gòu)。

解決這一問題，就需要在生成控制流程圖之后，根據(jù)C++語言的特性，將其中的這種對象指針自動向上類型轉(zhuǎn)換的基本塊合并。并標(biāo)明其中的判斷分支只是對對象的自動轉(zhuǎn)換，在進一步的控制流分析中不予分析。對于圖2中的例子，其中的控制流圖將4個基本塊合并成一個基本塊。在進一步控制流分析時對于上面的1，2，3個基本塊中的代碼不予分析，并且認為局部變量epb+pc與epb+pb是同一個值。主要的工作在于提取基本塊 1，2，3的特征，最終將2，3，4基本塊與模塊1合并。

3 控制流圖優(yōu)化算法及應(yīng)用

3.1 基本塊結(jié)構(gòu)描述

在給出描繪算法之前，要對基本塊進行描述。具體如下：

3.2 基本塊合并算法描述

根據(jù)上面的分析，算法主要在于判斷基本塊1，2，3的特征，合并基本塊?，F(xiàn)只考慮圖2中模塊1的跳轉(zhuǎn)語句jz結(jié)構(gòu)（當(dāng)其為jnz的情況類似，只是模塊2和模塊3剛好相反）?；緣K合并算法如下：

圖2 某條C++函數(shù)調(diào)用語句及其流程控制圖Fig.2 A certain C++function call statement and its process control chart

其中 CODE1表示cmp xxx，0 指令類型，xxx表示棧上的臨時變量

MegeBB（Bi，B3）是將兩個地址相鄰的基本塊合并。 將第二個基本塊中的指令復(fù)雜到第一個基本塊中去，修改第一塊基本塊的大小值，入度，出度，以及入度表和出度表。若入度表中或者出度表中的有相同的塊則刪除重復(fù)的。然后刪除第二個基本塊。

3.3 應(yīng)用實例

文中選取了一個面向?qū)ο蟮拈_源的網(wǎng)絡(luò)通信框架ACE[10]和實時CORBA的實現(xiàn)TAO[11]作為實驗分析對象。其中分析得到的數(shù)據(jù)如表1所示。

表1 算法識別結(jié)果Tab.1 Result of algorithm recognition

從上面實驗結(jié)果來看，識別對象的自動轉(zhuǎn)換的正確率比較高。識別錯誤的原因是，簡短的if…else…分支語句中，其中的模塊的特征碼與對象自動轉(zhuǎn)換的特征碼一致造成混淆，但是這種情況存在的可能性不大。正確識別了對象自動向上類型轉(zhuǎn)換后，在逆向工程師對匯編代碼進行分析時，減少了在分析類型轉(zhuǎn)換上花費的時間。同時也可以為高級C++代碼生成提供幫助，減少高級語言代碼中冗余的分支控制語句。提高了反編譯代碼輸出中的正確率。

4 結(jié)束語

介紹了反編譯中現(xiàn)有的控制流圖生成方法。分析了其在高級代碼生成中的作用和在反編譯C++程序中的局限性。提出了基于C++類型自動轉(zhuǎn)換的模塊優(yōu)化方法。結(jié)合類型自動轉(zhuǎn)換的特征碼，給出了控制流模塊優(yōu)化算法。并通過實驗驗證了該方法的有效性。下一步工作是，提取類型自動轉(zhuǎn)換中更加詳細的信息，提高識別的正確率。分析C++語言更多的特性，提高C++反編譯的正確率。

[1]Eilam E.Reversing:Secrets of Reverse Engineering[M].Indiarapolis，Indiana:Wiley Publishing，Inc， 2005.

[2]Bachaalany E.IDA hex-rays[EB/OL].http://www.hex-rays.com/contest2011/.

[3]Melanson M，Matignoni L. Boomerang[EB/OL].http://boomerang.sourceforge.net/papers.php.

[4]CHEN Geng-biao， WANG Zhuo， ZHANG Ruo-yu， et al.A refined decompiler to generate C code with high readablity[C]//2010 17th Working Conference on Reverse Engineering， 2010.

[5]許敏，陳前斌.靜態(tài)反匯編算法研究[J].計算機與數(shù)字工程，2007，35（5）:13－16.XU Min， CHEN Qian-bin.Static disassembly algorithms[J].Computer and Digital Engineering， 2007，35（5）:13－16.

[6]胡政，陳凱明.C++逆編譯中庫函數(shù)識別研究[J].計算機工程與應(yīng)用，2006，03:66－68.HU Zheng， CHEN Kai-ming.Reverse compile in C++library function recognition[J].Computer Engineering and Applications， 2006，03:66－68.

[7]胡政.C++逆編譯中模板庫函數(shù)識別研究[D].合肥：中國科學(xué)技術(shù)大學(xué)，2006.

[8]Cifuentes C.Reverse reverse compilation technique[D].School of Computer Science， Queensland University of Technology，1994.

[9]Lippman S B.深度探索C++對象模型[M].侯捷譯.武漢:華中科技大學(xué)出版社，2001.

[10]Douglas.ACE[EB/OL].（2010－06－02）http：//www.cs.wustl.edu/～schmidt/ACE.html.

[11]Douglas.TAO[EB/OL]. （2010－07－06）http://www.cs.wustl.edu/～schmidt/TAO.html.