摘要：为正确获得嵌入式可执行程序和汇编代码的高级语言制约结构，弥补现有高级程序制约结构恢复算法在处理非结构化区域的不足，将编译领域经典的制约流分析策略——结构分析算法引入到嵌入式汇编代码高级程序制约结构恢复研究中；针对嵌入式可执行程序的特点，对结构分析算法加以改善；利用结构分析算法的结果构造程序的制约树，生成高级语言代码与开源反编译器DCC的对比实验结果表明，改善的结构分析算法在高级程序结构恢复理由上是可行有效的
关键词：反编译； 制约流分析； 嵌入式系统； 逆向分析
：A
0引言
反编译是一个由机器代码或汇编代码生成更易理解的高级语言程序的过程 在这一过程中，根据程序制约流图提取高级程序制约结构是至关重要的一步在嵌入式程序中，为减少生成的代码所占用的存储空间，编译器对程序进行了大量的优化，导致程序中的跳转错综复杂，提取出的制约流图中包含了大量的非结构化子图，对高级程序制约结构恢复造成了较大的影响
目前制约结构恢复技术的研究主要针对桌面系统中的可执行程序进行，且主要关注结构化子图的分析与识别[1-3]，这些策略能够提取出制约流图中的大部分制约结构，但是对于非结构化区域的处理略显不足对于非结构化流图结构恢复理由的研究目前主要采取4种策略，分别是引入布尔变量[4-6]、代码复制[7-8]、引入特殊制约结构[9-10]和图转换系统[6，11]采用布尔变量和代码复制的策略虽然可以获得等价的结构化的制约流图，但是转变了程序的语法和逻辑结构，引入特殊制约结构导致某些结构无法被大多数高级程序语言正确描述，图转化系统保持程序制约结构不发生变化，但是在高级代码生成阶段产生大量的“goto”语句
为了更加准确地恢复嵌入式代码的高级程序制约结构，本文将编译领域经典的制约流分析算法——结构分析策略引入到制约结构恢复过程中，并在该策略上作了适当改善以适应嵌入式代码的特点在对非结构化流图进行结构化的过程中，本文针对结构分析涉及的三类非结构化区域分别提出了基于规则的结构化策略实验结果表明改善的结构分析算法能够更加准确地恢复程序的高级语言制约结构
1嵌入式代码高级程序制约结构恢复
结构分析是一种更为精致的区间分析策略，与基本的区间分析不同，它能表示出比循环更多的制约结构类型，并使每一种类型的制约结构形成一个区域结构分析考虑流图的深度为主生成树，然后对各种区域类型的实例按后序次序依次考察流图中的节点，将它们规约为抽象节点，蜕化掉连接边，并构造对应的制约树[12]
经典的结构分析算法可以准确识别顺序结构（图1（a））、ifthen（图1（b））、ifthenelse（图1 （c））、switch（图1（e））、selfloop（图1 （f））和whileloop（图1（d））等六种结构化区域；非正常选择路径（图 2（a））、自然循环（图2（b））和非正常区间（图2（c））三种非结构化区域需要说明的是，图2中的自然循环是指除了selfloop和whileloop以外的单入口循环非正常选择路径区间是指既没有包含环路也不能基于结构的高级语言制约结构恢复方法由优秀论文网站www.808so.com提供,助您写好论文.规约为任何简单无环结构的区域，这种结构在嵌入式代码中很常见图中所给出非结构化区域都是示意性的，因为循环可能不止两条出口边，非正常区间的入口基本块可能有两个以上的后继
由于结构分析算法在编译领域主要用于制约流分析和数据流分析，它没有对非结构化区域进行结构化处理，也不适合直接用于嵌入式代码的结构恢复为了使结构分析算法可以进行嵌入式代码的结构恢复，本文对算法进行了以下改善：
首先，由于在嵌入式汇编代码中，同一个函数中可能包含多条返回指令，这样得到的制约流图可能存在多个节点后继为空在此情况下，如果严格按照结构分析算法，流图无法规约为一个节点为了让结构分析算法顺利进行，本文将结构分析算法可以识别的结构加以扩充，使得其可以识别如图3所示的结构图中的虚线表示该边可以不存在，这样较好地解决了一个函数包含多条返回指令的理由
其次，结构分析算法识别到非结构化区域时，并不对非结构化区域进行结构化处理，而非结构化区域无法用现有的高级语言制约结构表示为了解决这个理由，本文设计了算法对这些非结构化区域进行结构化处理该算法对非结构化流图进行剪边处理，使其结构化剪下的边将被记录，在高级代码生成阶段，产生相应的“goto”语句形式对结构分析得到的三种非结构化区域的处理规则定义如下：
非正常选择路径区间无法规约，是由于ifthenelse结构的一个分支有多个前继，所以，只需要把通向该分支的边剪下，便可以将流图结构化对非正常选择路径区间的处理方式如图4所示
导致自然循环无法规约的理由是循环有多个出口，所以结构化策略可以选择破坏循环结构（图5（a））或者剪掉多余的出口（图5（b））在具体对非结构化流图进行处理时，可以根据程序的上下文选择合适的处理方式
导致非正常区间无法规约的理由在于它包含一个循环，该循环有多个入口所以非正常区间结构化的策略可以选择剪掉多余的入口（图6（a））或者破坏循环（图6（b）），需要根据程序的上下文选择更合适的处理方案
需要说明的是，对于非结构化区域的处理，往往不能简单通过一步处理实现结构化在实际处理过程中，可以按以上规则先剪一条边，然后对流图进行规约，如果不能完全规约，则对非结构化区域继续结构化处理，直到程序流图可以被完全规约
经过以上改善，结构分析算法便可以更好地应用于嵌入式代码的高级程序制约结构恢复当中下面通过一个制约流图的处理过程，详细介绍本文算法的工作流程
图7（a）是一个非结构化程序的制约流图，它包含7个基本块，分别记为B1～B7，在进行制约流分析时，其执行过程如下：
步骤1对制约流图进行深度优先后序遍历，获得制约流图的后序遍历序列：7， 5， 6， 3， 4， 2， 1步骤2依次对后序序列中的节点进行分析，判断其是否符合某一种高级程序制约结构，当扫描到基本块B6时，B6包含两个后继却不能识别为ifthen或者ifthenelse，所以它被认定是非结构化区域中的点，然后查找该非结构化区域包含的节点，可以找到B3、B5、B6、B7四个基本块构成非正常选择路径区间结构
步骤3对找到的非结构化区域进行结构化处理，利用前文定义的剪边规则，将流图中的边B6→B5剪去，得到图7（b）
步骤4由于制约流图已经转变，重新扫描后续遍历序列进行规约，当遍历到基本块B3时，B3有两个后继B5、B6，且符合ifthenelse结构特点，所以节点B3、B5、B6被抽象为一个新的节点，记为B8，制约流图也被变换为图7（c）
步骤5继续对后续遍历序列进行扫描，到达节点B2，B2有两个后继，两个前驱，并且B4和B2构成一个环路，B2和B4符合while循环特点，所以可以进行规约，抽象得到节点B9，制约流图转换为图7（d）
步骤6继续对后续遍历序列进行扫描，到达基本块B1，B1是入口基本块，且只有一个后继，不断沿着其后继进行分析可以知道基本块B1、B9、B8、B7满足顺序结构特点，所以可以规约得到节点B10，此时，制约流图变为图7（e）由于制约流图已经抽象成一个节点，说明制约流分析已经完成
经过制约流分析后，可以得到程序的制约树，如图8所示
在图8所示的制约树中，叶子节点是代码划分得到的基本块编号，其他节点是结构分析得到的制约结构信息需要说明的是，制约树展现的是结构化基于结构的高级语言制约结构恢复方法相关范文由写论文的好帮手www.808so.com提供,转载请保留.的程序信息，对于非结构化制约流图，无法展示剪下的边的信息，剪下的边被另外保存，在代码生成阶段进行特别处理
2高级代码生成
经过结构分析算法处理后，程序的制约流图便被转换为一棵制约树和一个被剪的边的集合（对于非结构化流图），这棵制约树的每个节点包含以下属性：节点ID、结构类型和所包含子节点信息等，通过这些信息，便可以进行程序的高级代码生成，高级代码生成算法如下：
功能：根据结构分析得到的节点信息生成程序的高级代码形式
输入：节点ID；
输出：该节点对应的高级代码形式
程序前
GenCode（NodeID）
{
根据节点ID找到相应节点CurrNode；
如果节点CurrNode的类型是基本块
2.1）进行该基本块的高级代码生成；
2.2）如果该基本块的后继有剪边的情况，
2.2.1）查找剪下的边的详细信息；
2.2.2）将该边的后继基本块在高级代码生成时加上标号；
2.2.3）该基本块加上跳转到后继基本块的“goto”语句；
如果节点CurrNode类型是高级程序制约结构
3.1）根据制约结构类型，产生高级代码框架；
3.2）递归调用高级代码生成函数，对孩子节点进行高级代码生成，将生成的高级代码嵌入到代码框架中；
返回生成的高级代码
}
程序后
该算法的特点是严格按照结构分析得到的程序制约结构信息进行代码生成，对于剪下的边进行“goto”语句的生成由于结构分析算法完整地提取了程序的制约结构，而代码生成算法也完整地展现了结构分析的结果，从而保证最终生成的高级代码完全体现了汇编代码的结构信息
下面针对上文提到的例子详细描述该算法的执行过程：
从结构B10开始进行代码生成，B10包含结构B1，B9，B8，B7四个子结构依次对这四个子结构进行高级代码生成B1，B7是基本块，首先进行基本块代码生成，然后判断B1，B7是否有剪边处理，若有，则进行“goto”语句生成处理B9，B8为非叶子节点，分别递归调用高级代码生成算法进行处理
当进行基本块B6的高级代码生成时，B6有剪边处理，所以需要额外产生一条“goto”语句，而对于基本块B5，由于有通向B5的边被剪，所以B5需要产生一个标签这样得到的高级代码既保证了与汇编代码的等价性，又最大可能地接近高级代码表示形式本文的例子经过高级代码生成后得到的高级代码形式如下：
程序前
B1.code
while（B2.code）
{B4.code}
if（B3.code）
{if（B6.code） goto L1；}
else{L1： B5.code}
B7.code
程序后
3实验结果及分析
为了对本文的策略进行可行性和有效性验证，从Intel 8051可执行程序中随机选择了10个非结构化程序的制约流图，并利用基于本文所述策略设计实现的反编译器BITDEC对这些流图进行反编译为了更好地说明本文的算法是有效的，利用一款开源的反编译工具DCC对同样的测试用例进行分析，并将实验结果加以对比实验结果如表1，其中“—”表示产生的高级代码没有正确描述汇编代码的结构
通过对实验结果的分析可知，改善的结构分析算法可以完全正确地描述嵌入式代码的程序结构，而DCC策略有4个函数产生的高级代码没能正确反映汇编代码的程序结构和内容由于在对非结构化区域结构化的过程中，采用的是基于规则的处理方式，因此无法保证在所有情况下都剪最少的边，进而产生最少的“goto”语句，这也是为什么图1和图4剪下的边比DCC算法多的理由
4结语
本文在深入了解嵌入式汇编代码程序结构的基础上，分析了现有高级程序制约结构恢复算法的不足，提出了利用编译领域经典的结构分析算法进行嵌入式代码高级程序制约结构恢复的策略，在实现的过程中，针对嵌入式代码的特点，对经典结构分析算法进行了改善，并针对结构分析算法没有很好解决的非结构化区域结构化的理由进行了深入研究，提出了可行的解决方案最后，在结构分析结果的基础上，设计算法实现了高级代码的生成算法通过与开源反编译器DCC的对比，实验结果表明，本文提出的算法是正确和有效的参考文献：
[1]侯文永，徐志宏.反编译过程中的结构变换[J].上海交通大学学报， 1996， 30（6）： 81-84.
[2]赵蕾，王开铸.C反编译制约流恢复的形式描述及算法[J].计算机学报，1998，21（1）：87-91.
[3]刘宗田，兰群.C子集程序到C语言程序的变换[J].计算机研究与发展，1991，28（3）：29-34.
[4]BOHM C， JACOPINI G. Flow diagrams， turing machines and languages with only two formation rules [J]. Communications of the ACM， 1966， 9（5）： 366-371.
[5]ASHCROFT E， MANNA Z. The translation of ‘go to’ programs to ‘w基于结构的高级语言制约结构恢复方法由专注毕业论文与职称论文的www.808so.com提供,转载请保留.hile’ programs [M]// Classics in Software Engineering. Upper Saddle River： Yourdon Press， 1979： 49-61.
[6]EROSA A M， HENDREN L J. Taming control flow： a structured approach to eliminating goto statements [C]// Proceedings of the 1994 International Conference on Computer Languages. Piscataway： IEEE， 1994： 229-240.
[7]KNUTH D E， FLOYED R W. Notes on oiding ‘go to’ statements [J]. Information Processing Letters， 1970， l（1）：22-23
[8]OULSNAM G. Unrelling unstructured programs [J]. The Computer Journal， 1982， 25（3）： 379-387.
[9]BER B S. An algorithm for structuring flowgraphs [J]. Journal of the ACM， 1977， 24（1）： 98-120.
[10]CIFUENTES C， GOUGH K J. A methodology for decompilation [C]// Proceedings for the XIX Conferencia Latinoamericana de Informatica. Buenos Aires： [s.n.]， 1993： 257-266.
[11]LICHTBLAU U. Decompilation of control structures by means of graph tranormations [C]// CAAP 85： Proceedings of the International Joint Conference on Theory and Practice of Software Development， Volume 1： Colloquium on Trees in Algebra and Programming： Mathematical Foundations of Software， LNCS 185. Berlin： SpringerVerlag， 1985： 284-297.
[12]MUCHINICK S S. Advanced compiler design and implementation [M]. San Francisco： Morgan Kaufmann， 1997.
对于基于结构高级语言制约结构恢复方法
更新时间：2024-02-25
作者：用户投稿
本站原创
本站原创
点赞:34361 浏览:158100