反编译理论基础

参考论文：Decompiling

Introduction

The Phases of a Decompiler

Syntax Analyzer 语法分析

什么是数据，什么是指令？

Semantic Analyzer 语义分析

语义分析阶段检查源程序中指令组的语义，收集类型信息，并在子例程中传播该类型。如果二进制程序是由编译器生成的，则机器语言的语义是正确的，以便程序执行。它实际上是由于编译器生成的代码中的错误而导致二进制程序不能运行的情况。因此，除非语法分析器错误地分析了一条指令，或者分析了数据而不是指令，否则源程序中不会出现语义错误。

Intermediate Code Generator 中间语言生成器

Control Flow Graph Generator 控制流图生成器

Data Flow Analyzer 数据流分析

Control Flow Analyzer 控制流分析

Code Generator 代码生成器

The Grouping of Phases

• 前端：包括那些依赖于机器和机器语言的阶段，这些阶段包括词法、语法和语义分析，以及中间代码和控制流图的生成。作为一个整体，这些阶段产生了一个中间的、独立于机器的程序表示；
• udm：是一种完全独立于机器和语言的中间模块，它执行反编译分析的核心。该模块包括两个阶段：数据流和控制流分析器。
• 后端：由那些与高级或目标语言无关的阶段组成。此模块是代码生成器。

The Context of a Decompiler

A Decompilation System：

Loader

加载器是一个程序，它将二进制程序加载到内存中，如果机器代码是可重定位的，则重新定位机器代码。在重新定位期间，指令会被更改并放回内存中。

Signature Generator

签名生成器是自动确定编译器和签名库性质的程序；唯一标识每个编译器和库子例程的二进制模式。使用这些签名试图反转链接器执行的任务，链接器将库和编译器启动代码链接到程序中。这样，所分析的程序只由用户子程序组成；用户在最初的高级语言程序中编译的那些。

Prototype Generator

原型生成器是一个程序，它自动确定库子程序的参数类型，以及函数返回值的类型。这些原型是从库头文件派生的，反编译器使用和来确定库子例程的参数类型和这些参数的数量。

Disassembler

反汇编程序是将机器语言转换成汇编语言的程序。一些反编译程序将汇编程序转换为更高的表示形式。在这些情况下，汇编程序是由反汇编程序生成的，是在汇编程序中编写的，或者编译到汇编程序。

Library Bindings

每当反编译器的目标语言与编译二进制源程序所用的原始语言不同时，如果生成的目标代码使用库名（即检测到库签名），尽管该程序是正确的，它不能在目标语言中重新编译，因为它不为该语言使用库例程，而是为另一种语言使用库例程。库绑定的引入通过将一种语言的子例程绑定到另一种语言来解决这个问题。

Postprocessor

后处理器是将高级语言程序转换为用同一种语言编写的完全等效的高级程序的程序。

Run-time Environment

Storage Organization 存储组织

The Stack Frame

在运行时，每个子例程都与一个堆栈帧相关联。堆栈帧是调用子程序的参数、局部变量和返回地址的集合。堆栈帧中的参数表示子程序特定调用的实际参数：二进制文件中未存储的子程序形式参数信息。

Data Types

数据对象通常存储在连续的内存位置。基本数据类型（如字符、整数和长整型）可以保存在寄存器中，同时对它们进行操作。聚合数据类型（如数组、字符串和记录）不能全部保存在寄存器中，因为它们的大小通常超出寄存器的大小，因此通过指向它们的起始地址的指针来访问它们更容易。

Array

数组是一个连续的内存块，其中包含一个或多个特定类型的项。数组在内存中实现为一系列行或列，具体取决于语言使用的顺序

String

字符串是一系列字符。不同语言使用不同的表示形式进行跨距，例如：C语言字符串是以空字符（即0）结尾的字节数组。

Record

记录是一个连续的内存块，它保存一个或多个数据类型的相关项；struct in c、record in pascal和user-defined type in Basic。

Complex Numbers

Boolean

High-Level Language Interface

高级语言的编译器使用一系列约定来允许混合语言编程，这样一个程序可以有一些用一种语言编写的子程序，而其他子程序则用另一种语言编写，所有这些子程序都链接到同一个程序中。这一系列约定与堆栈的设置方式以及用于调用子例程的调用约定有关。

Symbol Table

反编译器使用符号表来存储整个程序中使用的变量的信息。在二进制程序中，变量由地址标识；没有名字。具有物理内存地址的变量是全局变量；它们的段和偏移量用于访问它们。位于帧指针负偏移量处的变量是相应堆栈帧初始值的局部变量，正偏移量处的变量是子例程的实际参数。由于编译器使用寄存器变量是为了提高效率，所以所有寄存器最初也是考虑变量；对寄存器的进一步分析确定它们是否代表寄存器变量。

Data Structures

Unordered List

Ordered List

Hash Table

Symbol Table Representation for Decompilation

The Front-end

前端是一个依赖于机器的模块，它以二进制源程序作为输入，对程序进行解析，并产生控制流图和程序的中间语言表示作为输出。

Syntax Analysis 语法分析

语法分析器是反编译器的第一阶段。它的作用是将一系列字节组合成一种语言的短语或句子。检查此字节序列的语法结构，即字符串是否属于该语言。有效的字符串由解析树表示，解析树被输入到下一个阶段，即语义分析器。

Syntax Error

在二进制程序中很少发现语法错误，因为编译器会为编译后的程序生成正确的代码以在计算机上运行。但是，考虑到机器体系结构的升级会产生支持所有先前机器的新机器，新体系结构的机器指令集是旧体系结构指令集的扩展。

Finite State Automaton

有限状态自动机（FSA）是一种语言识别器。它接受一个字符串作为输入，并回答该字符串是否属于该语言。字符串是给定字母表的符号序列。给定一个任意字符串，FSA可以确定该字符串是否属于该语言。

数学模型：一个FSA的基本组成

• 有限状态集S，state

• 初始状态s0

• 最终状态或接受状态F

• 输入符号的字母表∑，symbol

• 转换函数t:state × symbol → state

使用了两个元符号“”和“%”。符号“”表示字母表∑中零个或多个符号的任意序列，“%”表示∑中的任意单个符号。

• Non-deterministic Finite State Automaton 非确定性有限状态自动机
• Deterministic Finite State Automaton 确定性有限状态自动机

Finite State Automatons and Parsers 有限状态自动机和解析器

Separation of Code and Data 代码和数据分离

给定程序的入口点，语法分析器的功能是按照程序的所有可能路径解析机器指令。解析器面临的主要问题是数据和代码在von Neumann机器中是以同样的方式表示的，因此不容易确定一条指令后面的字节是属于另一条指令还是表示数据。

Indirect Addressing Mode 间接寻址

间接寻址模式利用寄存器或内存位置的内容来确定使用这种寻址模式的指令的目标地址。间接寻址模式可与无条件跳转（例如，实现索引的事例表）和过程调用指令一起使用。这种寻址方式的主要问题是，在程序执行过程中，内存的内容可能会发生变化，因此，对程序的静态分析将无法提供正确的值，也无法确定内存位置是否已被修改。这同样适用于寄存器内容，除非寄存器的内容正在被仿真，但同样，如果寄存器在循环中使用，寄存器的内容很可能是错误的（除非循环也被仿真）。

Initial Parser Algorithm

Final Algorithm

Semantic Analysis 语义分析

语义分析阶段确定一组机器指令的含义，收集关于子例程的单个指令的信息，并在子例程的指令之间传播这些信息。通过这种方式，整数和长整数等基本数据类型会在子例程中传播。

Idioms

Idioms是具有逻辑意义的指令序列，不能从单个指令中推导出来。

Calling Conventions

C调用约定也称为C参数传递序列。在这个约定中，调用者按照参数在源代码中出现的相反顺序(即从右到左的顺序)将参数推送到堆栈上，然后调用过程。

Long Variable Operations

长变量作为两个连续的内存或堆栈位置存储在内存中。当对这些变量进行简单的加法或减法运算时，通常会识别出这些变量。用于这些操作的习惯用法通常是因为它们的指令数量简单。

Miscellaneous Idioms

一个广为人知的机器习惯用法是给变量赋值零。不使用mov指令，而是使用xor:每当一个变量与自身进行xor运算时，结果为零。这个机器习惯用法使用的机器周期和字节比它的对应用法少。

Simple Type Propagation

字节和整数等基本数据类型的符号很容易由用于比较操作数的条件跳转类型决定。这种技术也用于确定更复杂的基本数据类型(如long和real)的符号。

Intermediate Code Generation 中间代码生成

在反编译程序中，前端将机器语言源代码翻译成适合通用反编译机分析的中间表示。

反编译采用两步方法:首先使用低级中间表示来表示机器语言程序。习惯用法分析和类型传播可以在这种表示中完成，也可以从中生成汇编代码(即，它是适合反汇编器的中间代码，反汇编器不对代码执行高级分析)。然后，该表示被转换成适合于高级语言生成的高级中间表示。表示需要足够通用，以便为任何高级语言生成代码。

Low-level Intermediate Code

低级中间表示以四元组实现，这使得指令中使用的操作数显式，操作码字段保存低级中间操作码，目的字段保存目的操作数(即标识符)，src1和src2字段保存指令的源操作数。有些指令不使用两个源操作数，因此只使用src1字段。

High-level Intermediate Code

三地址代码是三地址机器的一种通用汇编代码。这种中间代码最适合反编译程序，因为三地址代码是程序抽象语法树(AST)的线性化表示。这样，在数据流分析过程中可以重建程序的完整AST。三地址指令具有一般形式：x := y op z。

高级中间表示由三元组实现。在三元组中，两个表达式以及指令操作码都是显式的。结果和参数字段是指向表达式的指针，表达式的最小形式是指向符号表的标识符。

Control Flow Graph Generation 控制流图生成

控制流图生成阶段构建源程序的调用图，以及程序每个子程序的基本块的控制流图。这些图表用于分析通用反编译机(UDM)模块中的程序。

Basic Blocks

基本数学抽象和原理

Control Flow Graphs

• 单向基本块:基本块中的最后一条指令是无条件跳转。这个街区有一条外边。
• 双向基本块:最后一条指令是条件跳转，因此，该块有两条外沿。
• n路基本块:最后一条指令是索引跳转。案例表中的n个分支成为该节点的n个外边缘。
• 调用基本块:最后一条指令是对子程序的调用。这个块有两个外沿:一个指向子程序调用后的指令(如果子程序返回)，另一个指向被调用的子程序。
• 返回基本块:最后一条指令是程序返回或程序结束。这个基本块没有外边缘。
• fall基本块:下一条指令是分支指令的目标地址(即下一条指令有标签)。该节点被视为落入下一个节点的节点，因此，只有一个外边缘。

Graph Optimization

一次通过编译器生成的机器代码以跳转到跳转、条件跳转到跳转以及跳转到条件跳转的形式利用冗余或不必要的跳转。这些不必要的跳跃可以通过控制流上的窥视孔优化来消除。不过，这种优化并不总是被使用。窥视孔优化是一种通过检查目标指令的短序列(称为窥视孔)并用更短或更快的指令序列替换这些指令来提高目标程序性能的方法。窥视孔是目标代码的一个移动的小窗口；窥视孔中的代码不需要连续。通过窥视孔优化所做的每一个改进都可能产生额外改进的机会，因此，重复传递代码是必要的。控制流优化是消除冗余跳跃的方法。对于反编译，我们感兴趣的是消除到跳转的所有跳转，以及到跳转的条件跳转，因为目标跳转保存目标分支的地址，并且利用可以从图中移除的中间基本块。删除跳转到条件跳转是不可取的，因为它涉及几个指令的重新排列，而不仅仅是修改一个目标分支地址。

The Call Graph

调用图是程序子程序的数学表示。每个节点代表一个子例程，每个边代表对另一个子例程的调用。

Data Flow Analysis

前端生成的低级中间代码是利用寄存器和条件代码的汇编型表示。这种表示可以被转换成不使用这种低级概念的更高级的表示，并再生高级的表达概念。低级到高级中间代码的转换是通过程序转换来完成的，传统上称为优化。

Previous Work

Elimination of Condition Codes

Elimination of Redundant Loads and Stores

Types of Optimizations

优化的目的是消除条件代码、寄存器和中间指令的低级语言概念，并引入两个以上操作数的表达式的高级概念。为此，需要注意的是，推送指令被当今的编译器以多种方式使用。参数传递是这个指令最常见的用法，它是在子程序调用之前，按照正在使用的调用约定指定的顺序推送它们。每当编译器用完寄存器来计算表达式时，就使用寄存器溢出。push和pop还用于跨过程调用保存寄存器的内容，并将值复制到寄存器中。

Dead-Register Elimination

如果一个标识符的值没有按照变量的定义来使用，那么它在程序中的某一点上就是死的。据说定义死标识符的指令是无用的，因此可以从代码中删除。

Dead-Condition Code Elimination

与死寄存器消除类似，如果条件代码的值在重定义之前没有被使用，那么它在程序中的某个点上就是死的。在这种情况下，条件代码的定义是无用的，并且不是必需的，但是如果指令定义的标识符不是死的，则定义该条件代码的指令仍然是有用的，因此，指令本身不一定被消除。

Condition Code Propagation

条件代码是机器用来发出条件发生信号的标志。一般来说，几条机器指令设置这些标志，一条指令设置1到3个不同的标志，较少的指令使用这些标志，仅使用1或2个标志。在死条件代码消除之后，条件代码的多余定义被消除，因此，所有剩余的标志被后续指令使用。

Register Arguments

子程序使用寄存器参数来加速对这些参数的访问，并消除子程序调用前将参数推入堆栈所带来的开销。许多运行时支持例程和使用寄存器调用约定编译的用户例程都使用寄存器参数(在某些编译器中可用)。

Function Return Register(s)

返回值的子程序叫做函数。函数通常在寄存器中返回值，然后这些寄存器被调用子例程使用。

Register Copy Propagation

如果一条指令定义了一个由唯一后续指令使用的寄存器值，则该指令是中间指令。在机器语言中，中间指令用于将操作数的内容移入寄存器，将指令的操作数移入特定指令使用的寄存器，并将寄存器中的计算结果存储到局部变量中。

Actual Parameters

调用子程序之前，子程序调用的实际参数要么放在堆栈上，要么放在寄存器上(用于寄存器参数)。这些参数可以映射到子程序的形式参数列表中，并放在调用指令的实际参数列表中。

Data Type Propagation Across Procedure Calls

子例程的实际参数的类型需要与形式参数的类型相同。在库子程序的情况下，形式参数类型是确定的，因此，这些类型需要与实际类型相匹配。如果有任何不同，形式类型将传播到实际参数。

Register Variable Elimination

寄存器复制传播优化可以找到高级表达式，并通过消除表达式计算中使用的大多数中间寄存器来消除中间指令。应用这种优化后，中间代码中只剩下几个寄存器(如果有的话)。这些剩余的寄存器代表寄存器变量或公共子表达式，由编译器或优化器用来加快访问时间。这些寄存器相当于高级程序中的局部变量，因此在使用它们的相应子程序中被新的局部变量代替。

Global Data Flow Analysis

Data Flow Analysis Definitions

• 如果寄存器的内容被修改(即被赋予一个新值)，则定义一个寄存器。以类似的方式，如果一个标志被一条指令修改，它就被定义（defined）。
• 如果寄存器被引用（used），则使用寄存器(即使用寄存器的值)。类似地，如果一条指令引用了一个标志，则使用该标志。
• 基本块Bi中的局部可用定义（ locally available definition）d是Bi中d的最后一个定义。
• 基本块Bi中局部向上暴露（locally upwards exposed）的用法u是一种以前在Bi中没有定义的用法。
• A definition d in basic block Bi reaches basic block Bj if：

• 基本块Bi中寄存器/标志的任何定义都被称为杀死（kill）到达Bi的同一寄存器/标志的所有定义。
• 如果基本块Bi中的d没有被重新定义（preserved），则该基本块Bi中的定义d被保留。
• 基本块Bi中的定义d很忙(有时称为非常忙)（busy），如果在从Bi开始的所有路径上重新定义之前使用了d。
• 如果基本块Bi中的定义d在从Bi开始的所有路径上被重新定义之前没有被使用(即d不忙或不活动)，则该定义d是死的（dead）。
• A definition-use chain (du-chain) for a definition d at instruction i is the set of instructions j where d could be used before being redefined (i.e. the instructions which can be affected by d).
• A use-definition chain (ud-chain) for a use u at instruction j is the set of instructions i where u was defined (i.e. the statements which can affect u).
• 如果一条路径上没有d的定义，那么这条路径就是d-clear。

Taxonomy of Data Flow Problems

数据流问题通过一系列方程来解决，这些方程使用每个基本块中收集的信息，并在整个控制流图中传播。过程流图中传播的信息称为过程内数据流分析，过程调用中传播的信息称为过程间数据流分析。

基本块Bi的典型数据流方程具有以下形式：

()中的摘要信息是通过以下形式的等式从图的前一个节点收集的:

• A data flow problem is said to be forward-flow if

1. The out() set is computed in terms of the in() set within the same basic block.
2. The in() set is computed from the out() set of predecessor basic blocks.

• A data flow problem is said to be backward-flow if

1. The in() set is computed in terms of the out() set within the same basic block.
2. The out() set is computed from the in() set of successor basic blocks.

Data Flow Equations

一般来说，数据流方程没有唯一的解；但是在数据流问题中，满足方程的最小或最大不动点解是感兴趣的。通过为前向流问题的头部基本块的in(B)集的初始值和反向流问题的出口基本块的out(B)集的值设置边界条件来找到这个解。根据对问题的解释，这些边界条件集被初始化为空集或泛集(即所有可能的值)。

• Let

• Bi be a basic block

• ReachIn(Bi) be the set of registers that reach the entrance to Bi

• ReachOut(Bi) be the set of registers that reach the exit from Bi

• Kill(Bi) be the set of registers killed in Bi

• Def(Bi) be the set of registers defined in Bi

• Let

• Bi be a basic block

• LiveIn(Bi) be the set of registers that are live on entrance to Bi

• LiveOut(Bi) be the set of registers that are live on exit from Bi

• Use(Bi) be the set of registers used in Bi

• Def(Bi) be the set of registers defined in Bi

• Let

• Bi be a basic block

• AvailIn(Bi) be the set of the registers that are available on entrance to Bi

• AvailOut(Bi) be the set of the registers that are available on exit from Bi

• Compute(Bi) be the set of the registers in Bicomputed and not killed

• Kill(Bi) be the set of the registers in Bithat are killed due to an assignment

• Let

• Bi be a basic block

• BusyIn(Bi) be the set of the registers that are busy on entrance to Bi

• BusyOut(Bi) be the set of the registers that are busy on exit from Bi

• Use(Bi) be the set of the registers that are used before killed in Bi

• Kill(Bi) be the set of the registers that are killed before used in Bi

• Let

• Bi be a basic block other than call and ret call

• LiveIn1(Bj) be the set of registers that are live on entrace to Bjduring phase one

• LiveOut1(Bj) be the set of registers that are live on exit from Bjduring phase one

• DeadIn(Bj) be the set of registers that have been killed on entrance to Bj

• DeadOut(Bj) be the set of registers that have been killed on exit from Bj

• Use(Bj) be the set of registers used in Bj

• Def(Bj) be the set of registers defined in Bj

• LiveIn2(Bj) be the set of registers that are live on entrace to Bjduring phase two

• LiveOut2(Bj) be the set of registers that are live on exit from Bjduring phase two

• Let

1. Bi be a basic block
2. Reach(Bi) be the set of reaching registers to Bi
3. Avail(Bi) be the set of available registers from Bi

• Let

1. Bibe a basic block
2. Avail(Bi) be the set of available registers from Bi
3. Reach(Bi) be the set of reaching registers to Bi
4. Propagate(Bi) be the set of the registers that are propagated across Bi
5. Def(Bi) be the set of locally available definitions in Bi

• Let

1. Bi be a basic block
2. Live(Bi) be the set of live registers on entrance to Bi
3. Reach(Bi) be the set of reaching registers to Bi
4. UpwardExp(Bi) be the set of the registers that are upwards exposed in Bi

Solving Data Flow Equations

给定一个子程序的控制流图，数据流方程可以用两种不同的方法求解:迭代法，重新计算一个解，直到满足一个定点；和区间方法，其中找到一个区间的解，然后在该区间的节点间传播。这些方程没有唯一解，但取最小解作为答案。

Code-improving Optimizations

Dead-Register Elimination

如果寄存器是由指令定义的，并且在被后续指令重新定义之前没有被使用，那么它就是死的。如果定义一个死寄存器的指令只定义了这一个寄存器，那么就说这个指令是无用的，因此被消除了。另一方面，如果该指令还定义了其他寄存器，则该指令仍然有用，但不应再定义死寄存器。在这种情况下，指令被修改以反映这一事实。死寄存器分析通过在寄存器上使用定义-使用链来解决，因为定义-使用链说明哪些指令使用定义的寄存器；如果没有使用该寄存器的指令，则寄存器失效。

• Dead Register Elimination Algorithm

• Update of du-chains

Dead-Condition Code Elimination

如果条件代码(或标志)是由指令定义的，并且在重新定义之前没有使用，那么它就是死的。由于条件码的定义是指令的副作用(即指令具有另一个功能)，消除死标志不会使指令冗余，因此，指令不会通过消除死标志而被消除。在这种分析中，一旦条件代码被确定为死代码，就不再需要由指令来定义它，因此从指令中移除该信息。关于条件码的信息以集合的形式保存在指令中:一组定义的条件和一组使用的条件(即位集合)。

• Dead Condition Code Elimination Algorithm

Condition Code Propagation

• Condition Code Propagation Algorithm

• BNF for Conditional Expressions

Register Arguments

编译器使用寄存器调用约定来加速子例程的调用。它是大多数当代编译器中可用的选项，也是编译器运行时支持例程使用的选项。给定一个子程序，在子程序中定义寄存器参数之前，寄存器参数被转换为子程序使用的寄存器；即整个子例程中寄存器的向上暴露的使用。

• Register Argument Algorithm

Function Return Register(s)

函数在寄存器中返回结果，没有机器指令说明函数正在返回哪些寄存器。在函数返回之后，调用方在重新定义之前使用函数返回的寄存器(即这些寄存器在函数调用之后的基本块入口时是活动的)。该寄存器信息跨子例程边界传播，并通过到达和实时寄存器分析来解决。

• Function Return Register(s)

Register Copy Propagation

寄存器复制传播是一种方法，通过这种方法，如果在赋值(即ax和cx都没有被修改)之后，两个寄存器都没有被修改(即被重新定义)。

• Register Copy Propagation Algorithm

Actual Parameters

子程序的实际参数通常在调用子程序之前被推送到堆栈上。由于大多数语言都允许嵌套的子例程调用，因此堆栈上的参数代表两个或多个子例程的参数，因此，有必要确定哪些参数属于哪个子例程。为此，使用了一个表达式堆栈，它存储与推送指令相关联的表达式。每当遇到调用指令时，从堆栈中弹出必要数量的参数。

Data Type Propagation Across Procedure Calls

在将实际参数实例化为形式参数的过程中，需要验证这些参数的数据类型，就好像它们不同一样，其中一个数据类型需要修改。

Register Variable Elimination

在高级语言程序中，寄存器变量转换为局部变量。这些寄存器被新的局部变量名替换。这种名称替换可以在数据流分析期间完成，也可以由代码生成器完成。

An Extended Register Copy Propagation Algorithm

跨过程调用的寄存器复制传播、实际参数检测和数据类型传播的优化可以在将寄存器信息传播到其他指令(包括参数)的一次传递中执行。

Further Data Type Propagation

一旦找到所有程序表达式，就可以进行进一步的数据类型确定，因为数据类型(如数组)使用地址计算来引用数组中的对象。这个地址计算是由一个表达式来表示的，为了达到高级语言表达式，这个表达式需要被简化。

• Extended Register Copy Propagation Algorithm

Control Flow Analysis

前端构建的控制流图没有关于高级语言控制结构的信息，例如if..然后..elses和while()循环。这样的图可以通过结构化算法转换成结构化的高级语言图。在图中检测高级控制结构，并且在图中标记控制结构的子图。

Graph Structuring

Structuring Loops

Control Flow Analysis

通过对程序图形的控制流分析，可以获得关于程序控制结构的信息。信息收集在图的不同节点中，无论它们属于循环和/或条件，还是不是任何结构的一部分。

Control Flow Analysis Definitions

• Given a node h, an interval I(h) is the maximal, single-entry subgraph in which h is the only entry node and in which all closed paths contain h. The unique interval node h is called the interval head or simply the header node.

• A latching node is any node in the interval which has the header node as an immediate successor.

Derived Sequence Construction

• Derived Sequence Algorithm

Irreducible Flow Graphs

一个流图是不可约的当且仅当它有一个标准型不可约图的子图。

High-Level Language Control Structures

不同的高级语言使用不同的控制结构，但是一般来说，没有一种高级语言使用所有不同的可用控制结构。

Control Structures - Classification

1. Action: a single basic block node is an action.
2. Composition: a sequence of 2 structures is a composition.
3. Conditional: a structure of the form if p then s1 else s2, where p is a predicate and s1,s2 are structures is a conditional structure.
4. Pre-tested loop: a loop of the form while p do s, where p is a predicate and s is a structure, is a pre-tested loop structure.
5. Single branch conditional: a conditional of the form if p then s, where p is a predicate and s is a structure, is a single branch conditional structure.
6. n-way conditional: a conditional of the form

case p of
1 : s1
2 : s2
...
n : sn
end case

where p is a predicate and s1..sn are structures, is an n-way conditional structure.

1. Post-tested loop: a loop of the form repeat s until p, where s is a structure and p

   is a predicate, is a post-tested loop structure.

2. Multiexit loop: a loop of the form

 while p1 do
 s1
 if p2 then exit
 s2
 if p3 then exit
 …
 if pn then exit
 sn
 end while

where s1..sn are structures and p1..pn are predicates, is a multiexit loop structure.Each exit statement branches out of the loop to the first statement/basic block after the loop.

1. Endless loop: a loop of the form loop s end, where s is a structure, is an endless loop.
2. Multilevel exit: an exit(i) statement causes the termination of i enclosing endless loops.
3. Multilevel cycle: a cycle(i) statement causes the i-th enclosing endless loop to be re-executed.
4. Goto: a goto statement transfers control to any other basic block, regardless of unique entrance conditions.

Control Structures in 3rd Generation Languages

• Classes of Control Structures in High-Level Languages

Generic Set of Control Structures

Structured and Unstructured Graphs

结构化控制流图是从使用高达DRECn类的结构的程序生成的图；即可分解为具有一个入口和一个或多个出口的子图的图。如果goto用于以结构化的方式转移控制(即，将控制转移到结构的开始或结束)，允许使用goto的语言仍然可以生成结构化的图形。非结构化图是通过goto语句的非结构化控制转移生成的，即在结构化图的中间转移控制，这将以前的结构化图分解成非结构化图，因为这个子图中有多个条目。当执行代码运动(即代码被移动)时，编译器的优化阶段也可以引入非结构化。

Loops

环是有向子图的任意两个节点之间有路径的强连通区域。这意味着循环的头节点必须至少有一个后沿。

结构化循环是一个子图，它有一个入口点、一个后边缘，可能还有一个或多个出口点，将控制转移到同一个节点。结构化循环包括所有自然循环(预测试和后测试循环)、循环和多出口循环。

非结构化循环是一个子图，它有一个或多个后边缘、一个或多个入口点以及一个或多个到不同节点的出口点。

Conditionals

结构化双向条件图是一个有向子图，它有一个双向条件头节点、一个入口点、两个或多个分支节点以及两个分支节点到达的公共端节点。这个最终的公共端节点被称为跟随节点，并且具有立即被头节点支配的属性。

非结构化双向条件是双向节点头子图，两个或多个条目进入头节点的分支，或者两个或多个出口离开头节点的分支。

Structured Graphs and Reducibility

Structuring Algorithms

在反编译中，结构化算法的目标是确定任意图的底层控制结构，从而将其转换为函数式和语义式等价图。任意图代表任何控制流图；可约或不可约的，来自结构化或非结构化语言。由于不知道初始程序是用什么语言编写的，使用了什么编译器(例如，启用了什么优化)，所以必须允许使用goto跳转，以防图形不能被构造成一组通用的高级结构。

Structuring Loops

为了构造循环，需要根据图形表示来定义循环。这种表示必须不仅能够确定循环的范围，而且能够为循环提供嵌套顺序。

Finding the Nodes that Belong to a Loop

Determining the Type of Loop

循环的类型由循环的头和锁存节点决定。在预先测试的循环中，双向头节点确定循环是否被执行，单向锁存节点将控制转移回头节点。经过测试的循环的特征在于双向锁存节点，其分支回到循环的头部或循环之外，以及任何类型的头部节点。最后，一个无限循环有一个单向锁存节点，它将控制转移回头节点和任何类型的头节点。

• Algorithm to Mark all Nodes that belong to a Loop induced by (y, x)

• Finding the Loop Follow Node

循环跟随节点是循环终止后到达的第一个节点。在自然循环的情况下，只有一个节点在循环终止后到达，但是在多出口和多级出口循环的情况下，可以有多个出口，因此，在循环后可以到达多个节点。由于结构化算法只结构化自然循环，所以所有的多出口循环都由一个“真实”出口和一个或多个异常出口构成。在循环中间有出口的情况下，在不同的出口之后可以到达几个节点。该算法的目的是只找到一个跟随节点。

Structuring 2-way Conditionals

单个分支条件(即如果..然后)和条件(即如果..然后..else)子图有一个公共的结束节点，从这里开始称为跟随节点，它具有立即被双向头节点支配的属性。

• Algorithm to Determine the Follow of a Loop

• 2-way Conditional Structuring Algorithm

Compound Conditions

在反编译中构造图时，不仅要考虑底层结构的结构，还要考虑底层中间指令信息。大多数高级语言允许对复合布尔条件(即包含and和or的条件)进行短路评估。在这些语言中，为这些条件表达式生成的控制流图变得非结构化，因为一旦检查到足够的条件并确定表达式整体为真或假，就可以执行退出。

• Compound Condition Structuring Algorithm

Structuring n-way Conditionals

• n-way Conditional Structuring Algorithm

Application Order

The Case of Irreducible Graphs

The Back-end

数据流分析器生成的高级中间代码和控制流分析器生成的结构化控制流图是后端的输入。这个模块整体上由代码生成器组成，它为目标高级语言生成代码。

Code Generation

Generating Code for a Basic Block 为基本块生成代码

数据流分析后，一个基本块中的中间指令都是高级指令；在此之前，伪高级指令必须已经从代码中消除。

Generating Code for asgn Instructions 为asgn指令生成代码

• Algorithm to Generate Code from an Expression Tree

Generating Code for call Instructions 为call指令生成代码

Generating Code for ret Instructions 为ret指令生成代码

• Algorithm to Generate Code from a Basic Block

Generating Code from Control Flow Graphs 从控制流图生成代码

Generating Code for Loops 为循环生成代码

给定以循环头节点为根的子图，基于循环的类型生成该循环的代码。无论循环类型如何，所有循环都具有相同的结构:循环头、循环体和循环尾。循环头和循环尾都是根据循环的类型生成的，循环体是通过为以循环体的第一个节点为根的子图生成代码来生成的。

• Algorithm to Generate Code for a Loop Header Rooted Graph

Generating Code for 2-way Rooted Graphs 生成双向有根图的代码

• Algorithm to Generate Code for a 2-way Rooted Graph

Generating Code for n-way Rooted Graphs 生成n路有根图的代码

• Algorithm to Generate Code for an n-way Rooted Graph

Generating Code for 1-way, Fall, and Call Rooted Graphs 为单向图、落图和调用根图生成代码

• Algorithm to Generate Code for 1-way, Call, and Fall Rooted Graphs

A Complete Algorithm

• Algorithm to Generate Code from a Control Flow Graph

• Algorithm to Generate Code from a Call Graph

The Case of Irreducible Graphs

Decompilation Tools

反编译工具是一系列帮助反编译程序生成目标高级语言程序的程序。给定一个二进制文件，加载程序确定二进制映像从哪里开始，以及文件是否有任何位置调整信息。一旦二进制映像被加载到内存中(并且可能被重新定位)，反汇编器就可以用来解析二进制映像并生成程序的汇编形式。解析过程可以受益于编译器和库签名识别器的使用，后者根据另一个程序生成的一组预定义签名来确定一个子例程是否是库子例程。这样，只有用户编写的原始代码被分解和反编译。反汇编器可以被认为是反汇编器的一部分，因为它只解析二进制图像(即它是前端模块的一个阶段)。

The Loader

加载程序是一种操作系统程序，如果有足够的空闲内存供程序加载和运行，它会将可执行程序或二进制程序加载到内存中。大多数二进制程序包含运行程序所需的内存量、重定位地址和初始段寄存器值等信息。一旦程序被加载到内存中，加载程序通过设置代码和指令段将控制权转移给二进制程序。

• Loader Algorithm

Signature Generator

签名生成器是为输入文件自动生成签名的程序。签名是用于识别病毒、编译器和库子程序的二进制模式。反编译中签名的目的是撤销链接器执行的过程，即确定哪些子程序是库和编译器启动代码，并用它们的名称替换它们(在前一种情况下)或从目标输出代码中删除它们(在后一种情况下)。这是不共享库的操作系统的情况，因此将库子例程的目标代码绑定到程序的二进制映像中。二进制程序中没有关于子程序名称或参数的信息，因此，如果没有一种方法将它们与用户编写的子程序区分开，就不可能将它们与其他子程序区分开。在共享库子程序的操作系统的情况下，子程序不构成二进制程序的一部分，并且在程序中引用子程序，因此，子程序的名称作为二进制文件的一部分存储(很可能在标题部分)。

Library Subroutine Signatures

标准库文件是一个可重定位的目标文件，它实现特定语言/编译器中可用的不同子程序。库子例程签名是一种二进制模式，它唯一地将库中的子例程与同一库中的任何其他子例程区分开来。由于所有子程序执行不同的功能，一个包含子程序的完整二进制模式的签名将唯一地识别子程序和任何其他子程序。

• Signature Algorithm

Integration of Library Signatures and the Decompiler

给定一个子例程的入口点，解析器从入口点沿着所有路径反汇编指令。如果知道某个特定的编译器被用来编译当前正在分析的源二进制程序，解析器可以检查该子例程是否属于某个库(对于该特定的编译器)。如果有，代码不需要被解析，因为它知道调用了哪个子例程，因此使用了子例程的名称。由于库中存在大量的子程序，线性搜索对于检查文件中所有可能的签名是非常低效的。在这种情况下，散列是一种很好的技术，更好的是，可以使用完美的散列，因为签名对于给定库中的每个子例程都是唯一的，并且具有固定的大小。完美的散列信息可以存储在库签名文件的头部，解析器可以在需要确定一个子例程是否属于该库时使用。

Compiler Signature

Determining the Main Program 确定主程序

Integration of Compiler Signatures with the Decompiler 编译器签名与反编译程序的集成

Manual Generation of Signatures

Library Prototype Generator

库原型生成器是一个自动生成库子程序原型信息的程序；也就是子例程使用的参数类型，以及函数返回值的类型。确定库子例程的原型信息有助于反编译程序检查参数的正确类型和数量，并传播由于分析中缺乏信息而被错误地认为是另一种类型的任何类型信息。

Comment on Runtime Support Routines 运行时支持例程评论

Integration of the Library Prototypes and the Decompiler 库原型和反编译程序的集成

Disassembler

反汇编程序是将源二进制程序转换成目标汇编程序的程序。汇编代码使用代表机器操作码的助记符。

Language Independent Bindings

反编译程序为特定的目标语言生成代码。借助编译器和库签名反编译的二进制程序产生目标语言程序，这些程序使用库签名文件中定义的库例程的名称。如果二进制程序最初使用的语言与反编译程序的目标语言不同，则目标程序不能针对这种语言重新编译，因为它使用了在另一种语言/编译器中定义的库例程。

Postprocessor

反编译程序生成的目标高级语言程序的质量可以通过后处理器阶段来提高，该后处理器阶段用语言特定的结构来替换通用控制结构。

dcc

dcc是用C语言为DOS操作系统编写的原型反编译程序。dcc最初是在运行Ultrix的DecStation 3000上开发的，在DOS下移植到PC架构上。dcc将作为输入.exe和.com文件，并生成目标C和汇编程序。

利用前几章节的理论知识实现的反编译程序。