基于结构语义树的高级控制结构恢复技术

刘絮颖， 尹 青， 蒋烈辉， 刘建林

(解放军信息工程大学信息工程学院，河南郑州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路条件结构，再结构化循环结构，最后结构化二路条件结构的顺序对控制流图进行结构化。控制流图结构化过程要进行三遍，在整个结构化过程中每识别出一种高级控制结构，就将该结构的头结点、所对应的循环关闭结点或者二路分支后随结点、N路分支后随结点，以及各种高级控制结构的类型进行标记，最后得到具有标记信息的控制流图。

2.2 构建结构语义树

结构语义树构建模块对前期得到的含有标记信息的控制流图进行降序反向后序遍历，每遍历一个结点就根据其是否含有标记信息对其进行区分，如果是叶子结点就直接加入结构语义树中，如果是复合结点，还要再根据其标记信息采用不同方式加入到结构语义树中。控制流图遍历结束后得到能够表达目标代码高级控制结构以及高级控制结构关系的结构语义树。

如图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.