C++反编译中控制流图优化方法研究

蒋海苏，杜承烈

（西北工业大学 计算机学院，陕西 西安 710129）

反编译是把可执行的二进制代码转换成功能等价的可读性强的高级语言代码的过程[1]。反编译是逆向工程的重要的步骤，在软件的理解、维护、复用和开发方面发挥了重要的作用。近年来由于C++及其他面向对象语言逐渐成为主流语言，现有的大量C++程序由于各种原因需要进行逆向工程。目前，已经有一些反编译器可用，如：IDA Hex_rays[2]，Boomerang[3]和C-Decompiler[4]。然而，使用这些工具对C++程序进行反编译都普遍存在结果正确性低的问题。除去反编译固有的困难外，还有就是反编译生成的都是类C伪代码，没有考虑到C++语言的特性。

反编译的基本步骤有：1）反汇编，将二进制代码识别为汇编语言；2）库函数识别，识别库函数，分析调用入口；3）流程分块，将程序分为独立的可执行模块；4）控制流分析，对流程进行分析，为生成高级语言控制流做准备；5）类型分析，识别数据的类型。最终生成可理解的高级语言代码。其中步骤1），2）都有不少论文介绍这方面工作。其中，文献[5]介绍了静态反汇编的两种方法。文献[6]介绍了C++库函数的识别方法。而且现在也出现了成熟的反汇编分析工具，如IDA。控制流分块与控制流分析是反编译器中间的部分，为输出的高级语言代码生成提供依据[7]，直接影响到生成高级代码的正确性。文中首先介绍了现有的控制流分块方法以及C++与C语言存在的差异，提出了一种针对C++语言改进控制流分块的方法，并给出了实验验证。

1 控制流图及其划分方法

控制流图是描述程序内部流程的图形表示。使用控制流程图可以很容易地将它们转化为高级语言的控制结构以及形象地展示给逆向人员进行分析。图1给出了3种典型的控制流图结构。分别是 if结构，if…else… 和 for…结构，图中的圆圈表示基本块。

图1 3种典型的控制流结构Fig.1 Three kinds of typical control flow structures

传统的划分控制流图的方法是：将汇编指令分为两类，转移指令和非转移指令。转移指令是一些指令的集合，这些指令把指令执行流（即IP寄存器的值）转移到内存中不同于下一条指令地址的地址。这些指令有：无条件跳转（jmp），条件跳转（jnb，je，jbe 等），子程序调用（call），子程序返回（ret）。除去这些指令外，其他的都是非转移指令。基本块总是以转移指令的转移目的地址或者转移指令的下一条指令为开始，转移指令或者转移指令转移目标地址的前一条指令结束。并且基本块内部是连续的非转移指令集。基本块之间按照地址顺序相连或者根据跳转目的相连。按照这样划分基本块非常具体，但也常常因为程序或某个函数过于复杂而导致控制流图过于复杂。文献[8]也给出了一些控制流图的优化方法，如：两条连续的无条件跳转到同一地址的指令，它们之间没有任何的其他指令。另外一种优化方式是根据语义进行优化。例如：call指令虽然将程序的执行流程改变，但是在执行完子程序之后仍然返回执行call之后的下一条指令。那么在这个方法中，call并没有将执行流程改变。那么将以call指令划分的两个基本块合并为一个。这样就能够减少不少顺序的基本块（特别是在函数调用较多的情况下）。IDA的控制流图就是采用这种优化方式显示的。

控制流图生成之后，经过中间的控制流分析，生成对应的高级语言。生成的代码的流程基本上依赖于控制流图结构。如图1中的控制流图将被翻译成if，if…else…，for…等。

2 现有的控制流图用于C++反编译存在的问题

C++语言虽然是由C语言发展而来，但却与C语言有着很多区别。主要区别有：继承、多态、模板等，对于目标代码有较大的影响[7]。由于C++是面向对象的语言，支持用户自定义的类型的向上自动转换。而这些由C++编译器实现的，而这其中就有可能产生控制流。如果不加以区分，反编译生成的控制流将有很大区别。如图2中，UML类图描述了3个类的关系以及一个函数原型，控制流图中虚线表示条件成立时的流程。虽然从C++语言的角度来看，只是一条普通的函数调用语句，但是其对应的汇编语言确是包含有一个分支选择结构（编译环境为Visual Studio 2005）。生成或者是模块1中跳转语句为jnz xxx，那么模块2，3中的语句（除jmp外）刚好相反了。不管怎样，反编译器会将其翻译成一个if…else…的伪代码结构。显然这种结构是多余的，在流控图中增加基本块，使得控制流图更加复杂。

造成这种情况的原因是，C++作为一种面向对象语言，它支持对象的类型自动向上转换操作。因为当对象的指针为NULL时，转换后对象指针也为NULL[9]。这才会在底层汇编代码中出现分支选择的控制结构。而对象的自动向上类型转换在一些大型的面向对象框架中也是大量存在的，这将使得C++反编译中的控制流图更加复杂，反编译器也会对此生成许多冗余的if…else…结构。

解决这一问题，就需要在生成控制流程图之后，根据C++语言的特性，将其中的这种对象指针自动向上类型转换的基本块合并。并标明其中的判断分支只是对对象的自动转换，在进一步的控制流分析中不予分析。对于图2中的例子，其中的控制流图将4个基本块合并成一个基本块。在进一步控制流分析时对于上面的1，2，3个基本块中的代码不予分析，并且认为局部变量epb+pc与epb+pb是同一个值。主要的工作在于提取基本块 1，2，3的特征，最终将2，3，4基本块与模块1合并。

3 控制流图优化算法及应用

3.1 基本块结构描述

在给出描绘算法之前，要对基本块进行描述。具体如下：

3.2 基本块合并算法描述

根据上面的分析，算法主要在于判断基本块1，2，3的特征，合并基本块。现只考虑图2中模块1的跳转语句jz结构（当其为jnz的情况类似，只是模块2和模块3刚好相反）。基本块合并算法如下：

图2 某条C++函数调用语句及其流程控制图Fig.2 A certain C++function call statement and its process control chart

其中 CODE1表示cmp xxx，0 指令类型，xxx表示栈上的临时变量

MegeBB（Bi，B3）是将两个地址相邻的基本块合并。 将第二个基本块中的指令复杂到第一个基本块中去，修改第一块基本块的大小值，入度，出度，以及入度表和出度表。若入度表中或者出度表中的有相同的块则删除重复的。然后删除第二个基本块。

3.3 应用实例

文中选取了一个面向对象的开源的网络通信框架ACE[10]和实时CORBA的实现TAO[11]作为实验分析对象。其中分析得到的数据如表1所示。

表1 算法识别结果Tab.1 Result of algorithm recognition

从上面实验结果来看，识别对象的自动转换的正确率比较高。识别错误的原因是，简短的if…else…分支语句中，其中的模块的特征码与对象自动转换的特征码一致造成混淆，但是这种情况存在的可能性不大。正确识别了对象自动向上类型转换后，在逆向工程师对汇编代码进行分析时，减少了在分析类型转换上花费的时间。同时也可以为高级C++代码生成提供帮助，减少高级语言代码中冗余的分支控制语句。提高了反编译代码输出中的正确率。

4 结束语

介绍了反编译中现有的控制流图生成方法。分析了其在高级代码生成中的作用和在反编译C++程序中的局限性。提出了基于C++类型自动转换的模块优化方法。结合类型自动转换的特征码，给出了控制流模块优化算法。并通过实验验证了该方法的有效性。下一步工作是，提取类型自动转换中更加详细的信息，提高识别的正确率。分析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]许敏，陈前斌.静态反汇编算法研究[J].计算机与数字工程，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++逆编译中库函数识别研究[J].计算机工程与应用，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++逆编译中模板库函数识别研究[D].合肥：中国科学技术大学，2006.

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

[9]Lippman S B.深度探索C++对象模型[M].侯捷译.武汉:华中科技大学出版社，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.