Read

SSA-for-decompilation-5

《Static Single Assignment for Decompilation》 第五章 类型分析

划词翻译+人工校对

5 类型分析

SSA 形式支持基于稀疏数据流的类型分析系统，非常适合反编译。

编译器执行类型分析以在软件开发过程的早期拒绝无效程序，避免以后进行更昂贵的纠正（例如在调试时或部署后）。某些源语言（例如 C 和 Java）需要所有变量的类型定义。对于这些语言，编译器在称为类型检查的过程中检查在编译时具有类型含义的语句的相互一致性。由于反编译源代码的编译器需要很多类型信息，而典型的机器代码程序中不存在显式类型信息，因此机器代码反编译器需要做大量工作来恢复变量的类型。这个过程称为反编译器的类型分析。

其他语言，如 Self、C/C++ 和 Smalltalk 需要很少的类型定义，变量可以在整个程序中包含不同的类型，并且大多数类型检查是在运行时执行的。这些语言是动态类型检查的。这些语言通常仍会执行静态（编译时）类型分析，以发现变量在运行时可以采用哪些类型进行优化。这个过程称为类型推断或类型重建，对于编译器来说比类型检查 [KDM03] 更难。由于类 C 语言更为常见，因此这里将不再考虑这种更复杂的情况

反编译器的类型分析问题是将每条数据与一个高级类型相关联。可以合理地期望该程序没有类型错误，即使某些语言（例如 C）允许从一种类型转换为几乎任何其他类型。各种不同的数据需要分析类型：已初始化和未初始化的全局数据、局部变量、堆分配变量和常量。

类型分析在概念上是在数据流分析之后和控制流分析之前进行的，如图5.1所示。

image-20230516151123785

从编译器的角度来看，（编译器那边的）类型分析甚至比数据流分析在文献中的讨论要多得多。此处详细考虑了机器代码程序中类型的性质，以及反编译器输出中类型的要求。

机器代码程序中存在的类型信息可以看作是一组要解决的约束，或者是一组要处理的操作，类似于数据流分析。本章介绍了基于静态单一赋值形式（SSA 形式）的稀疏数据流类型分析。由于类型信息可以与每个定义（和常量）一起存储，因此每次使用一个位置时都可以随时访问当前类型。（因为只需要为每个定义存储类型而不是为每个程序点存储？）这种稀疏表示节省的内存是相当可观的。

每个生成三个约束的加法和减法指令在基于数据的类型分析系统中需要不同的方法。类似地，任意表达式的类型在这样的系统中值得特别注意，因为没有地方可以存储中间表达式结果的类型。

在任何用于机器代码反编译器的类型分析系统中，都有数量惊人的多种内存表达式，它们表示从简单变量到数组和结构成员的数据对象。

  • 5.1 节列出了构成本章基础的先前工作。
  • 5.2 节从机器代码的角度介绍了类型的本质，以及它们为何如此重要。类型信息的来源在第 5.3 节中列出。常量需要类型和位置，如第 5.4 节所示。
  • 5.5 节讨论了将类型分析作为约束满足问题来解决的局限性。加法和减法指令的特殊要求在第 5.6 节中讨论，并在第 5.7.4 节中重新讨论。
  • 第 5.7 节提出了一种基于迭代数据流的解决方案，SSA 版本的优点在第 5.7.2 节中给出。
  • 5.8 节列举了大量的内存位置模式。反编译器需要处理数据和代码，这个过程与类型分析密切相关，如第 5.9 节所述。
  • 5.10 节提到了一些在类型分析中有用的特殊类型，5.11 节讨论了相关工作，5.12 节列出了未来需要做的工作。最后，第 5.13 节总结了 SSA 形式对类型分析的贡献。

5.1 现有工作

Mycroft 和 Reps 等人的工作。有一定的局限性，但为机器码反编译中的类型分析奠定了基础。

Mycroft 的论文 [Myc99] 是第一个认真考虑反编译类型分析的论文。他认识到 SSA 形式的有用性，可以用于“反-”寄存器着色优化，即分离同位变量。他指出了由数组索引引起的问题，其中编译器为数组元素访问生成了不止一条指令。第 5.5.1 节讨论了这个限制。

Mycroft 的工作还有许多其他限制，例如似乎没有考虑全局数组。然而，本章中的工作很大程度上受到了 Mycroft 论文的启发。

Reps 等人描述 x86 可执行文件的分析框架 [RBL06, BR05]。他们的目标是生成一个 IR，该 IR 类似于可以从源代码生成的 IR，但具有对安全分析很重要的低级元素。他们最终使用旨在读取源代码的工具来进行浏览和安全查询。图 5.2 给出了一个概览。

声明的目标之一是类型信息，但除了简要提及从库函数传播信息外，论文没有详细说明这些信息的来源。他们的论文提到反编译是一种潜在的应用，但这不是他们主要感兴趣的领域之一。

使用了三种主要分析：Value-set Analysis（VSA），一种值分析；仿射关系分析 (ARA) 和结构体识别 (ASI)。 VSA 发现一个位置在给定程序点可能采用的值的过高估计。 ARA 是作者修改的用于可执行程序的源代码分析。它找到位置之间的关系，例如索引变量和运行指针。 ASI 恢复聚合的结构，例如结构和数组，包括结构的数组。

作者报告的结果是合理的，特别是与大多数分析可执行程序中复杂数据结构的工具完全失败相比。然而，只有 55% 的虚函数被成功分析 [BR06]，并且 60% 的测试程序具有一个或多个无法分析的虚函数 [BR06、BR05]。 72% 的堆分配结构被正确分析（即计算出的结构与编译器的调试信息一致），但对于 20% 的程序，只有 12% 或更少是正确的 [BR05]。正如稍后将展示的，表示对数据项（尤其是聚合元素）的访问的内存表达式的形式非常复杂。特别是，不清楚他们的分析是否可以将原始指针与偏移指针分开（第 19 页第 1.5.3 节）。希望考虑到所有各种可能的内存表达形式的分析能够正确分析更大比例的数据访问，同时还能为每个数据项找到类型。

机器代码的类型分析

类型信息封装了很多区分低级机器代码和高级源代码的信息。

下一节将从机器代码的角度考虑类型的性质和用途。

类型的作用（角色）

类型是断言；它们划分程序语义域，并将数据划分为不同的对象。

当程序员在静态类型检查语言中将变量声明为整数类型或类 Customer 时，会断言变量可以取什么值，以及可以对它们执行什么操作。程序语义的部分域适用于整数类型的变量（例如左移 2 位），而其他域（例如调用方法 getName()）适用于类 Customer 的对象。当发现程序对变量应用了错误的语义时，可以表明该程序违反了语言的类型规则，因此可以在编译时发出错误消息。

类型包括有关数据对象大小的信息。类型将数据部分从字节块划分为具有已知属性的不同对象集。

在机器代码程序中，类型声明通常已被编译器删除。 （一个例外是调试信息，在软件开发过程中插入，在某些情况下可能仍然存在。）因此，在反编译程序时，变量在某个点左移两位的事实强烈表明它应该是类型为整数，而不是类 Customer。

类似地，当四个字节的数据用作整数时，这四个字节与数据部分中的其他数据对象不同。这四个字节不太可能是另一个数据对象的一部分，例如一个字符串，恰好在数据部分中位于它之前。这样，反编译器可以有效地重建从地址到原始编译器符号表中存在的类型的映射。

将类型视为断言的观点导致了为每个变量生成约束的想法，只要它在暗示其类型的上下文中使用。并非所有使用都暗示完整的类型信息。例如，一条 32 位复制（寄存器到寄存器移动）指令只约束类型的大小，而不约束它是整数、浮点数还是指针。以上假定指针的大小为 32 位。程序通常对指针使用一种大小，这可以通过检查二进制文件格式找到。本章中的示例将采用 32 位指针；显然可以容纳其他尺寸。

一些操作隐含基本类型，例如整数，但没有类型的详细信息，例如它的符号性（有符号与无符号）。左移运算符就是一个例子。右移算术等运算符暗示基本类型（整数）和符号性（在本例中为带符号）。某些类型信息的部分性质导致了类型层次或格的概念。类型 unsigned short 比短整数（符号未知）更精确，而它比 size16 更精确，而后者又比 \(\top\)（根本没有类型信息）更精确。

在面向对象的程序中，一组重要的类型是类类型。例如，希望知道某个指针是 Customer* 类型还是 Employee* 类型。这样的类型信息不是直接来自单个指令的语义，而是来自类层次结构分析

用高级语言表达的程序必须包含一些类型声明以满足该语言的规则。然而，在最trivial的层面上可能不使用类型系统。例如，考虑一个二进制翻译器，它不尝试理解它正在翻译的程序，而是将原始程序的数据部分复制为一个非结构化字节的整体块。还假设它使用 C 语言作为目标机器独立的汇编程序； UQBT 二进制翻译器以这种方式运行 [CVE00, CVEU+99, UQB01]。翻译器发出的这种低级 C 将包含与类型相关的结构，因为 C 语言要求每个变量定义都用类型声明，但所有变量都声明为整数，并根据需要插入强制转换以重现原始程序。内存由 *(<type> *)(<address expression>) 形式的表达式引用。

诸如此类的代码本质上是用高级语言表达的低级反汇编。这种代码缺少的主要特征之一是数据的真实类型信息。

（注：这里“高级语言表达的低级反汇编”说得很好。很多时候遇到人不懂lifter和decompiler产生的IR的区别，比如觉得都是转LLVM IR，转出来不就可以了。经常不知道怎么反驳。。。）

高级语言中的类型

类型对于以高级语言表达程序是必不可少的：它们有助于提高可读性、封装知识、将指针与数字常量分开，并支持面向对象。

从上面的讨论中可以清楚地看出，类型是用高级语言编写的代码的一个基本特征，没有它们，可读性将非常差。指针和数字常量的分离隐含在决定变量的类型中。指令中的立即数（在反汇编中可以表示内存中某个结构的地址、整数或浮动点数）显然是指针或常量，一旦分配了类型。回想一下 1.5 节，将指针与数字常量分开是从机器代码进行逆向工程的基本问题之一。

机器代码程序与其高级语言等效程序之间的差异之一是空指针检查和数组边界检查等功能通常由编译器隐式应用。换句话说，它们存在于机器代码级别，但一个好的反编译器应该删除它们。此删除需要进行类型分析；要删除空指针检查，分析必须发现变量是指针。同样，在删除数组边界检查之前，必须识别数组和数组索引。有人可能会争辩说，如果空指针或数组边界检查被反编译器删除但存在于原始源代码中，那么反编译程序仍然是正确的。

递归类型指的是类型表达式的一部分引用自身的类型。例如，链表可能有一个名为 Next 的元素，它是指向同一链表的另一个元素的指针。处理此类类型时必须小心。例如，将类型打印为字符串的简单算法如下：遇到指针时，发出星号并递归指针类型的孩子。这适用于非递归类型，但不适用于链表示例（它将尝试产生无限的星）。这个问题当然不是反编译器独有的

基本和聚合类型

虽然基本类型从单个指令的语义中出现，但聚合类型有时必须通过间距分析（stride analysis）来发现。

大多数机器指令处理基本（简单）类型。这些类型包括整数和浮动点数。枚举和函数指针在机器代码级别表示为整数。聚合类型是基本类型的组合：数组、结构体和基本类型的union类型。

其他主要类型（基本类型和聚合类型除外）是指针。这些将在接下来的部分中更详细地考虑。

聚合类型通常在机器代码级别一次处理一个元素。处理聚合类型的少数机器指令，例如块移动或块设置指令，可以在循环中分解为更基本的指令。虽然机器指令语义通常会确定基本数据项的类型，但聚合类型通常只能从基本指令的上下文中发现，例如在循环中执行的基本操作，或在指针的固定偏移处执行的一些基本操作。

图 5.3 显示了使用基本类型和聚合类型的源代码和机器代码。请注意在 Intel x86 等复杂指令集上，基本类型的对象如何使用简单的寻址模式（如 m[r1）访问，而聚合类型使用更复杂的寻址模式，如 m[r1+r2*S]（寻址模式 (r1,r2,S)） 和 m[r1+K]（r1 和 r2 是寄存器，S 和 K 是常量）。

image-20230516164938196

变化的指针（Running Pointer）

虽然变化的指针和数组索引在大多数情况下是等效的，但运行指针在初始化数组的情况下会产生问题。

C 程序员知道可以使用索引或通过数组递增指针来访问数组。通常，指针比索引更有效；因此，用索引编写的程序可能会被优化编译器转换为操作指针的等效代码。这意味着反编译器可以自由地以任何一种方式表示数组处理代码。用户可能更喜欢一种表示而不是另一种表示。可以争论的是，表示可以安全地留给运行时选项或交互式用户选择。或者，总是可以产生一种表示，并且如果需要另一种表示，则使用后反编译转换阶段。

在数组上使用运行指针对于恢复预初始化数组具有重要意义。期望看到数组索引语义的简单类型分析（例如 [Myc99]）可能会正确地反编译程序的代码部分，但无法恢复数组的初始值。图 5.4 说明了这个问题。

在图5.4(a)中，类型分析发现了一个数组，为了正确声明数组，提示分析数组的大小。如果它在二进制文件的只读部分中，它的大小和类型可用于声明数组的初始值（示例中未显示）。在图5.4(b)中，p的类型是char，常量的类型也是char。地址 10 000 用作 char 的事实可能会提示将一个 char 声明为字符，并且如果在二进制文件的只读部分中，它可能会被赋予一个初始值。请注意，没有提示将其他九个值声明为 char 类型。更糟糕的是，常量 10 010 被用作 char* 类型，可能提示类型分析将地址 10010 处的对象声明为 char 类型，而实际上这只是数据段中数组 a 之后的下一个数据项。该对象可以是任何类型，也可以是未使用的。这表明每当常量 K 与类型 Y* 一起使用时，它并不总是遵循位置 K*（即 m[K]）与类型 Y 一起使用。

image-20230516165158780

以 5.4(a) 风格编写的程序可以由编译器转换为 5.4(b) 风格的机器代码程序。

图 5.4(a) 中数组的大小比较容易确定。在其他情况下，可能很难或不可能确定数组的长度。例如，可以使用一个特殊值来终止循环。循环终止条件可以任意复杂，实际上需要执行程序才能找到终止条件。即使执行程序也可能无法确定数组的完整大小，因为对于每次执行，可能只会访问数组的一部分。在这些情况下，类型分析可能会确定存在已初始化的数组，但无法计算数组的长度。

image-20230516165337787

图 5.5：从同一指针引用两种不同类型的程序。

另一种情况是使用运行指针遍历结构数组，如图 5.5(a) 所示。这里的结构包含一个整数和一个浮点数；在循环内部，指针交替引用一个整数和一个浮点数。原始编译器重新安排了代码，在每次引用后将指针递增整数的大小和浮点数的大小，从而使机器代码更加紧凑和高效。如图 5.5(b) 所示，指针的类型现在是 void*，因为它被用作两个不兼容的指针类型。

如果数组未初始化，如图 5.4(b) 和 5.5(b) 所示的程序可读性较差但正确（假设适当的转换并在适当的地址分配内存）。然而，如果数组被初始化，使它们正确的唯一方法是使用二进制翻译技术：强制数据访问到原始地址，如果源机器和目标机器的字节序不同，则反转数据部分。不用说，结果远非可读，并且翻译到具有不同指针大小（以及其他重要特征）的机器根本不可行。

为了避免这种极端的不可读性，有必要分析包含基于指针的代码的循环，并找出指针的范围。

这里不考虑反编译器的指针范围分析；分析，例如 Reps 等人的VSA分析。可能是合适的 [RBL06]。

类型信息的来源

类型信息来自机器指令opcode，来自库函数的签名，在一定程度上来自某些常量的值，偶尔来自调试信息。

机器代码程序中类型信息的最佳来源之一是对库函数的调用。通常，库函数的签名是已知的，因为库函数的目的是执行已知和记录的功能。签名由函数名称、参数的数量和类型以及函数的返回类型（如果有）组成。此信息可以存储在从解析头文件派生的签名数据库中，由函数名称（如果动态链接）或通过模式匹配静态链接代码 [FLI00，VE98] 获得的标识符进行索引。

有限的类型信息来自于一些常量的值。在许多架构中，某些值可以被排除为指针（例如，小于 0x100 的值）。类型分析的主要决定之一是常量是否为指针，因此此信息可能很有价值。

类型信息的第三个来源是单个机器指令的语义。所有机器指令都将暗示每个非立即操作数的大小。寄存器有确定的大小，所有内存操作都有一个编码到指令操作码中的大小。对于某些加载、存储和移动指令等指令，除了大小之外没有关于类型的信息，并且源和目标的类型通过T(dest)≥T(src)相关。 （T (x) 表示 x 的类型。不等式只出现在类指针中；目标可以指向至少与源一样多的东西）。相同的指针大小的移动指令可用于移动指针、整数、游标点值等。因此，需要有一种类型的表示，其唯一信息是大小，例如任何 16 位数量的 size16。

在某些机器代码程序中，有运行时类型信息（有时称为 RTTI 或运行时类型标识）。这通常在原始程序使用 C++ dynamic_cast 操作或类似操作的情况下可用。即使原始源代码没有显式使用此类操作，某些库（例如 Microsoft 基础类 (MFC)）的使用也可能会隐式引入 RTTI [VEW04]。当输入程序中存在 RTTI 时，类的名称和层次结构都可用。类层次结构提供类型信息；例如，如果 A 类是 B 类的父类，则 T (A) > T (B)。

最后，输入程序可能包含调试信息或符号。调试信息通常在程序开发期间打开以帮助调试。在某些情况下，调试信息可能仍然存在于反编译器可用的机器代码中。当调试信息在输入程序中可用时，所有过程的名称以及参数的名称和类型通常都是可用的。函数返回和局部变量的类型也可能可用，具体取决于存在的调试信息的详细信息。

大多数类型信息从被调用者传递到调用者，这对于反编译很方便，因为大多数其他信息（例如关于参数和返回的信息）也从被调用者传递到调用者。然而，一些类型信息以相反的方向传播。参数/参数和返回/结果之间存在对称性，值从参数发送到参数并返回到结果。上面讨论的源类型信息的传播方向取决于库函数、常量、机器指令等是否驻留在调用者或被调用者中。

考虑一个返回其两个 32 位（指针大小）参数之和的函数的简单示例。单独来看，关于这个函数的参数和返回值的唯一已知类型信息，参数和返回都是 32 位大小，而且不是任何浮动点类型。换句话说，指针和整数的多种组合都是可能的。如果为调用者的实际参数或结果找到了类型，则类型信息将从调用者流向被调用者。

这个例子也突出了类型分析的一个普遍问题：可能有几种可能的解决方案，但都是有效的。用于添加指针和整数、整数和指针以及两个整数的程序都可以编译为相同的机器代码程序。然而，这个问题对于小过程最为严重，因为随着考虑更大的过程，遇到暗示特定类型的使用的机会增加。

类型分析被认为是一个双向问题 [KDM03]。换句话说，如果实现为数据流问题，则流图的正向或反向遍历都不会显着提高性能。双向性的根源在于大多数类型定义操作都会影响目的地（定义）和一些操作数（使用）。定义的类型效果会影响该定义的使用；用途的类型影响回溯到这些用途的定义。库函数调用同样具有双向效果。按值调用库调用的实际参数是对先前定义的位置的使用（类型信息向后流动）。返回值类型和引用参数调用是类型向前影响的定义。因此，类型分析是少数可以用数据流术语表达的问题之一，并且是真正双向的。

比较操作导致可能不直观的类型约束。相等关系运算符（= 和 !=）仅表示被比较的变量的类型是可比较的。 （如果两个类型是可比较的，则意味着它们在 C 意义上是兼容的；int 和 char* 不兼容，因此无法比较它们。）任一操作数的类型都可以大于或等于操作数的类型另一个操作数，因为等式关系是可交换的，如图 5.6 所示。

image-20230516165932660

相比之下，诸如 ≤ 之类的非交换关系运算符表示统一类型对象的数组，因为高级语言不允许假设其他对象的相对地址。图 5.7(b) 显示了一个示例，其中常量 a+10 的类型应为 int*，即使相同的数字常量可能是在其他地方被用作浮点数 f 的地址。因此，这些运算符意味着操作数的类型是相等的。

image-20230516170012790

一些关系运算符暗示操作数的符号性（例如，符号小于或等于）。编译器通常会忽略整数操作数的符号不匹配，因此不应将有符号整数、无符号整数和未知符号的整数视为不同类型。相反，整数类型的符号是一种属性，变量的最终声明符号可以通过启发式方法确定，例如统计上最常用的类型（ the statically most commonly used variant）。

通常，在比较整数和浮点数时会使用不同的比较运算符，因此这些运算符隐含了基本类型。定点数通常由整数运算符（例如比较运算符、加法和减法）进行操作，只有少数操作（例如固定点乘法）将操作数识别为固定点。因此，可以将整数提升为固定点数，即\(fixpoint \sqsubset integer\)。

5.4 类型约束

常量与内存位置一样具有类型，并且由于具有相同数值的常量不一定相关，因此常量被必须独立设置类型。

在高级语言中，常量具有隐含类型。比如2.0的类型是double； 'a' 是字符，0x61 是整数，依此类推。但是，在反编译中，这并不适用。常量和位置一样需要输入。根据常量的类型，相同的立即值（机器语言常量）可能最终在反编译代码中作为 1084227584、5.000000、&foo、ENUM_40A00000 或可能的其他表示形式发出。重要的是要认识到每个常量都必须独立类型化。例如，在下面的语句中，每个值为 1000 的常量都可以是不同的类型：

\(m[1000_1] := m[1000_2] + 1000_3\)

三种可能的结果是：

  • \(T (1000_1) = int*\) and \(T (1000_2) = int*\) and \(T (1000_3) = int\)
  • \(T (1000_1) = α**\) and \(T (1000_2) = α**\) and \(T (1000_3) = int\)
  • \(T (1000_1) = α**\) and \(T (1000_2) = int*\) and \(T (1000_3) = α*\)

其中每个 α 表示任意类型，但 α 的每次出现都暗示与其他 α 相同的任意类型。在第三个例子中，\(1000_3\) 是一个指向 α 的指针，它被一个整数（在内存地址 1000 处找到）加，产生一个指向 α 的指针，它覆盖了临时位于位置 1000 的整数。必须使用转换才能使第三个方案有效，并且需要反映在反编译输出中。

另请注意，寄存器中的值可以是没有类型的中间值，例如在以下 SPARC 代码中：

1
2
3
sethi 0x10 000, %o0
add %o0, 0x500, %o1 // %o1 used later as char*, value 0x10 500
add %o0, 0x600, %o2 // %o2 used later as integer, value 0x10 600

寄存器 %o0 中的值 0x10 000 没有标准类型，尽管它似乎被用作两种不同类型（char* 和整数）的一部分。它不得出现在反编译输出中。中间值来源于 RISC 机器的一个共同特征：由于 RISC 指令的长度通常是一个字，因此需要两条指令来产生大多数字长常量。 SSA 形式促进了常量传播和死代码消除，通过删除中间常量很容易解决这个问题。

5.5 类型约束满足

在反编译输出中查找变量和常量的类型可以视为约束满足问题；它的具体特征表明了一种充分利用约束传播的算法。

可以将类型分配给反编译变量视为约束满足问题 (CSP) [VH89, Bar98]。类型变量的域比较小：

  • 基本类型（在第 5.2.3 节中列举）

  • 指向 α 的指针（其中 α 是任何类型，包括另一个指针）

  • α 的数组（其中 α 是任何类型，包括另一个数组）

  • 结构或类

  • 枚举类型

图 5.8 显示了源代码中的程序片段、机器代码（带有 SSA 转换）、生成的约束以及约束的解决方案。

在第二条指令中，寄存器 r1a（寄存器 r1 的第一个 SSA 值）被设置为 0。由于零可以用作整数，也可以用作 NULL 指针，约束条件是 r1a 可以是整数（t1a = int ) 或指向某物的指针，称其为 α1 (t1a = ptr(α1))。 add指令产生的约束条件比较复杂，反映了三种可能：指针+整数=指针，整数+指针=指针，整数+整数=整数。约束通常使用标准约束求解器算法来求解，但是图 5.8 中的简单问题的一部分可以通过肉眼求解。例如，加载指令的约束只有一种可能性，t0b = ptr(mem(0: t2a)（意味着 r0b 指向内存中类型为 t2a 的结构，位于 r0b 指向的偏移量 0 处）。这可以是代入标签为 3F2: 的指令的约束中，因此 t0a 和 t0c 的类型必须与此相同。

继续约束求解，找到两个解。在大多数情况下，不会有不止一种解决方案。

因为常量是独立类型的（上一节），并且表达式（包括常量）必须根据约束来表达，所以有必要以某种方式区分常量。例如，常量可以被下标，就像 SSA 变量被重命名一样，例如\(1000_3\) 正如已经看到的那样。常量 1000 的每个版本的类型都需要被视为一个单独的变量。

类型常量（常量类型变量的值）很常见。例如，xor 指令意味着整数操作数和结果； sqrt 指令表示游标点操作数和结果； itof 指令意味着整数操作数和浮动点结果。库函数调用会导致每个参数（如果有）和结果（如果有）的类型常量。

为类型变量选择一个值（在 CSP 术语中）通常隐含在约束中。例如图5.8的add指令，add r2a,r1b,r1c，结果为约束：

image-20230516172503569 \[ \begin{align} t2a = ptr (α_3), t1b = int, t1c = ptr(α_3) ∨ \\ t2a = int, t1a = ptr (α_4), t1c = ptr (α_4) ∨ \\ t2a = int, t1b = int, t1c = int \end{align} \]

在这里，约束表示为连词的disjunction（或-ing）（一些术语 and 在一起；这里的逗号表示 and）。通过选择三个连词之一，同时查找 t2a、t1b 和 t1c 的值。通常通过拒绝与其他约束冲突的合取来做出选择。希望在流程结束时，有一组约束代表类型分析问题的解决方案。

一些约束求解器基于约束传播（例如前向检查技术）。其他更多地依赖于检查冲突（例如简单的回溯或生成和测试）。综上所述，上述因素（小域大小、常量和等式很常见，等等）表明约束传播将快速修剪搜索树中会导致失败的分支。因此，约束传播技术似乎更适合类型约束满足问题，因为它比另一组技术更适用于反编译。

基于约束的类型分析算法的一个弱点是一些这样的算法是不完整的，即给定的算法可能找到一个或多个解决方案，或者证明约束无法解决（证明它们不一致），或者这两个都做不到。

数组和结构体

基于约束的类型分析需要额外的规则才能正确处理数组。

Mycroft 提出了一种基于约束的类型分析系统，用于反编译机器代码程序（以寄存器传输语言形式或 RTL）[Myc99]。他为单个指令生成约束，并解决约束以给被反编译程序的变量创建类型。他假定双寄存器寻址模式指令的可用性和使用来指示数组的使用。例如，在他论文的第 4 节中，

image-20230516172844425

但是，某些机器架构不支持双寄存器索引，即使支持，编译器也可能出于各种原因决定对加载或存储指令单独执行加法。因此，上述指令可以作为两条指令发出，具有如图 5.9 所示的约束。

image-20230516172857092

图 5.9：上述两个指令版本的约束。来自 [Myc99] 的示例。

由于 r1 在第二条指令中用作指针，因此立即删除第一条指令的最后一个（带下划线的）条件句。最终约束现在是根据 ptr (t3)，而不是 ptr (array(t3))。这些在 C 意义上是等价的，但涉及数组的事实并不明显。换句话说，仅考虑单个指令本身（至少在某些情况下）不足以分析聚合类型。要么必须在约束系统之外添加一些辅助规则，要么可以将表达式传播与高级类型模式结合使用。 （在他论文的第 4.3 节中，Mycroft 似乎建议成对地考虑指令来解决这个问题。）这是另一个可以使用第 3 章和第 4 章中描述的表达式传播和简化的领域。

加法和减法操作

编译器隐式地使用指针大小的加法指令来访问结构成员，这导致将一个整数与 α* 类型的指针相加会产生另一个 α* 类型的指针的一般规则出现异常。

指针大小的加法和减法指令是类型分析的一种特殊情况，因为它们可以用于指针或整数。 Mycroft [Myc99] 将指令 add a,b,c（其中 c 是目的地，即 c := a + b）的类型约束声明为：

image-20230516174842091

其中 T (x) 再次表示 “x 的类型”（Mycroft 使用 tx ）并且 ptr(α) 表示指向任何类型的指针，类型变量 α 表示该类型。Mycroft 使用 C 指针算术规则，其中将整数与 α* 类型的变量相加将始终得到 α* 类型的指针。但是，C 定义并不总是适用于机器代码级别。编译器发出 add 指令以在源程序中实现加法运算符，但也用于其他两个目的：数组索引和结构成员访问。对于数组索引，C 指针规则适用。 α 类型元素数组的基是 α* 类型，（可能缩放的）索引是整数类型，结果是指向索引元素的指针，它是 α* 类型。

但是，结构成员访问不遵循 C 规则。考虑一个类型为 Σ 的结构，其在偏移 K 的地方包含类型为 ε 的元素。结构的地址可以是类型 Σ*（指向结构的指针）或类型 ε0*（指向结构的第一个元素 0 的指针），具体取决于关于它是如何使用的。在机器代码级别，Σ 和 Σ.0 具有相同的地址并且除了它们的使用方式外无法区分。 K 被添加到这个指针以产生一个指向元素 的指针，它是类型 ε*，通常是与 Σ* 或 ε0* 不同的类型。

不幸的是，在类型分析完成之前，不知道任何特定指针是否会变成结构指针。图 5.10 给出了一个例子。

image-20230516174950921

图 5.10：一个程序片段说明了指针如何最初看起来不是结构指针，但后来用作结构指针。

最初，参数 p 仅被认为是一个指针。在处理完过程的第一条语句后，p 与类型 int* 一起使用，因此 T (p) 被设置为 int。在第二个语句中（通常，任意时间之后），发现 p 指向一个结构，其中一个 int 位于 oset 0 处，一个 oat 位于 oset 4 处。如果使用 C 规则，则 p 的总和（然后type int) 和 4 产生一个与 p 类型相同的指针，然后在第二个语句中 p 被有效地用作 int* 类型和 oat* 类型。这可能导致 p 被声明为 int* 和 oat* 的联合。

请注意，其他通用 C 规则的例外仅涉及添加结构指针和常量整数；编译器知道结构成员的集合，并将此信息保存在结构的符号表中。因此，如果整数不是常量，则可以将结果类型和输入指针的类型限制为相等，即适用 Mycroft 的限制条件。

为了避免这个问题，Mycroft 的约束可以重写如下：

image-20230516175122620
image-20230516175132852

这里，void*，表示一个已知为指针的变量，但指向的类型未知（输出）或被忽略（输入）。如果 void* 和 α* 之间存在冲突，则优先使用 α*。请注意，这已经暗示了类型的层次结构，void* 优于无类型，但任何 α* 优于 void*。

编译器不会隐式地执行指针减法或指针减法，因此可以导出指针大小减法运算的类似 Mycroft 的约束。对于 c := a - b:

image-20230516175205361

基于数据流的类型分析

对输出语言进行静态类型检查的反编译器的类型分析，由于使用了 SSA 形式，使得稀疏数据流算法变得可能。

类型可以被认为是变量的可能值的集合。可能值的集合越小，类型信息就越精确和有用。这些集合形成一个自然的层次结构：所有可能值的集合、所有可能的 32 位值的集合、有符号或无符号 32 位整数的集合、有符号的 32 位整数的集合、有符号整数的子范围， 等等。机器指令的作用通常是限制可能值的范围，例如从所有 32 位值到 32 位整数，或从 32 位整数到无符号 32 位整数。

该效应表明，调和位置类型的各种限制和约束的自然方法是使用迭代数据流框架 [MR90，KU76]。欠缺的数据是类型限制和约束，结果是在给定这些限制和约束的情况下程序中位置的最精确类型。

基于数据流的类型分析比第 5.5 节中概述的基于约束的类型分析有一些优势。由于在程序的正常中间表示之外没有要解决的显式约束，因此无需区分恰好具有一致值的常量。约束很难求解，有时候有不止一种解法，有时候根本就没有解法。相比之下，数据流方程的求解通常非常简单。这种简单性的两个例外是整数加法和减法指令；正如将要显示的那样，这些指令比其他指令更复杂，但复杂度适中。

类型格

由于类型是分层的并且某些类型对是不相交的，因此类型之间的关系形成了一个格。

类型可以被认为是可能值的集合，例如整数类型可以被认为是所有可能整数的无限集。在本章中，这两个视图将互换使用。整数集是无符号整数集（计数）的超集。整数集合中的元素多于无符号整数集合，即整数⊃无符号整数。因此，整数集在某种意义上大于无符号整数集；因此有一个类型的顺序关系。

然而，顺序关系并不完整，因为某些类型对是不相交的，即它们无法进行有意义的比较。例如，浮动点数、整数和指针在机器代码级别彼此不兼容，因此被认为是相互不兼容的（即不可比较）。这些基本类型中没有一个比其他类型包含更多信息。为了表示排序是部分排序，使用了常用集合运算符符号的方形版本：⊂、⊃、∩和∪分别变为 \(\sqsubset\)、\(\sqsupset\)、\(\sqcap\) 和 \(\sqcup\)。因此 “int \(\sqsupset\) unsigned int” 或 “int 是 unsigned int 的超类型”。

尽管数学数字 1027 是一个整数，它也是一个实数，并且它可以用作内存中某个对象的地址，但这些类型在机器代码级别是不兼容的。浮点数与整数有不同的位表示，因此用途不同。指针变量只能由加载和存储指令（包括包含加载和/或存储的复杂指令）或比较/测试指令使用。整数变量应类似地由整数指令（整数加法、移位、按位或）使用，而浮点变量应仅由浮点指令（浮动点加法、平方根等）使用。

这种将类型与指令类巧妙分离的两个例外是整数加法和减法指令。在大多数机器中，这些指令可用于整数变量和指针变量。第 5.6 节更详细地讨论了此例外情况的含义。事实上，不同类型的对象通常必须与不同的指令类一起使用，这使得避免类型错误变得如此重要。

在反编译中，除了计算机语言中使用的类型外，还会考虑其他类型，例如 size32（一个 32 位的量，其基本类型尚不清楚，但大小已知），或指针或整数类型。这些是临时类型，应该在反编译结束前删除。作为一个人为的例子，考虑一个由三个指令引用的位置：符号位的 32 位测试、整数加法指令和算术右移。在test指令之前，根本不知道该位置的任何信息。类型系统可以为它分配一个特殊的值，称为\(\top\)（top）。 \(\top\) 代表所有可能的类型，或通用集 \(\cup\)，或等效地，没有类型信息（因为一切都是 \(\cup\) 的成员）。test指令后，只知道它是一个32位有符号数，所以类型分析可以赋予它临时类型signed32。在 add 指令后，已知它是一个指针或一个整数：pointer-or-int。算术右移指令仅适用于整数变量，因此该位置可以分配为 int 类型。

到目前为止，类型层次结构可以被认为是一个有序列表，一端是 \(\top\)，另一端是 int。位置的类型最好朝一个方向移动（有一个例外，如下所述），朝向最受约束的类型（可能值较少的类型，远离 \(\top\)）。之后出现的信息也有可能与当前已知的类型发生冲突。例如，假设第四条指令使用该位置作为指针。从逻辑上讲，这可以用另一个特殊值 ⊥（bottom）表示，表示过度约束或类型冲突，或可能值的空集 ∅。这可能是由于原始程序中真正的不一致（例如，由于类型的联合或类型转换）或类型分析系统的某些限制而导致的。

实际上，对于反编译，最好永远不要将值 ⊥ 分配给变量的类型；这相当于完全放弃分析这个位置的类型。相反，反编译器将保留当前类型 (int) 或分配新类型（指针），并且位置的冲突使用将以这样一种方式进行标记，即强制转换或联合将被体现到反编译输出中。 （如果在输出语言中不允许强制转换或联合，警告注释可能是最好的选择。某些语言比其他语言更适合作为反编译器的输出语言。）

继续引用位置的示例三个指令，类型列表可以垂直表示，\(\top\) 和类型 size32、pointer-or-int 和 int 依次向下延伸，如图 5.11(a) 所示。

image-20230518155630693

图 5.11：说明glb(the greatest lower bound)

由于代替 add 指令的另一条指令（例如平方根指令）会确定该位置为 float 类型，因此有一条路径从size32到float，并且没有从 int 到 oat 的路径，因为它们是不兼容的。

到目前为止，当一个位置被用作两种类型 a 和 b 时，格中两种类型中较低的一种成为该位置的新类型。但是，请考虑一个位置是否已与类型 pointer-or-int 和 float-or-int 一起使用。 （后者可以通过分配一个已知对指针无效的值来实现）。结果类型不能是迄今为止使用过的任何一种类型 (pointer-or-int 或 float-or-int),，但实际上应该是新类型 int，它是小于 pointer-or-int 和 float-or-int 的最大类型。换句话说，使用类型为a和b的位置的一般结果是a和b的最大下界(greatest lower bound)，也称为a和b的meet，记为a \(\sqcap\) b。.

注意与集合交叉符号∩的相似性。满足类型 a 和 b 的结果基本上是 a ∩ b，其中 a、b 和结果被认为是可能值的集合。例如，如果当前类型是 ?signed-int（未知符号的整数），它可以被认为是集合 {sint, uint}。如果此类型遇到 unsigned-int ({uint})，则结果为 {sint, uint} ∩ {uint} = {uint} 或 unsigned-int。

图 5.11(b) 显示了为什么它是所需的最大下界。当遇到类型 a 和 c 时，结果应该是 d 或 e，它们是 a 和 c 的下界。事实上，它应该是 d，最大的下界，因为没有理由（只考虑 a 和 c 的meet操作）选择更特殊的类型 e。例如，如果结果稍后遇到 b，则结果必须是 d，因为类型 b 和 e 在格中不可比较（这意味着它们在高级语言中是不兼容的类型）。

image-20230518160535675

图 5.12：用于反编译的简化类型格。

图 5.12 显示了一个更实用的类型格，显示了数值的类型关系

前面提到，在考虑程序中位置的类型时，类型并不总是在格中从上到下移动。这些例外涉及指向面向对象语言（如 C++）中的类对象的指针。

image-20230518160708098

图 5.13：类指针和引用

考虑图 5.13 中显示的示例类层次结构和网格。类层次结构和指向这些类的指针层次结构之间的相似性是显而易见的。一个指针可以在程序的一部分中被分配为 Sender* 类型，而在另一部分中被分配为 Receiver* 类型。如果这两个部分存在控制流合并，则指针将同时用作 Sender* 和 Receiver*。到目前为止的规则将产生 Transceiver* 类型，它是一个指向从类 Sender 和 Receiver 多重继承的类型的指针。但是，如果程序仅引用Sender和 Receiver 共有的那些方法和/或成员，即共同祖先 Communicator 的方法和成员，则这可能有点矫枉过正。此外，多重继承相对不常见，因此在许多程序中没有继承自多个类的类，并且在反编译输出中生成一个是不正确的。

这个例子说明有时关联两种类型的结果比所涉及的类型更高。在这些情况下，关联类型 α* 和 β* 导致类型 (α \(\sqcup\) β)*，其中 \(\sqcup\) 是join运算符，而 α \(\sqcup\) β 得到 α 和 β 的最小上界（lub, least upper bound）。注意与集合并集运算符符号 ∪ 的相似性

此行为仅发生在对类或结构对象的指针和引用中。对于指向其他类型对象的指针，指针或引用的类型与所引用的变量的类型必须在类型上完全对应。

类和结构指针和引用带来了额外的差异。在 a := b 这样的复制语句中，如果 a 和 b 不是这样的指针或引用，则 a 和 b 的类型相互影响；两者的类型都是 a 的类型与 b 的类型。但是，对于 p := q，其中 p 和 q 都是类或结构指针或引用，p 可能指向比 q 更大的对象集，并且 p 类型的这种扩展不会影响 q。因此，在这样的赋值之后，p 的类型变成了指向 p 的基类型和 q 的基类型的连接的指针，但是 q 的类型不受影响。只有这种形式的赋值才有这种例外，并且只有当涉及的变量是指针或类或结构的引用时。

出于类型分析的目的，过程参数在每次调用过程时由所有相应的实参表达式有效分配。该参数可以采用来自任何实际参数表达式的值。对于类型不是类或结构指针或引用的参数，所有参数的类型和参数的类型必须相同。但是，如果参数的类型是这样的指针或引用，则参数的类型必须是所有相应参数类型的join。

有关格的更多详细信息，参阅 [DP02]。

5.7.2 基于 SSA 的类型分析

SSA 形式把使用连接到定义，允许在赋值节点中对类型信息进行稀疏表示。

在 5.7 节的开头，有人指出反编译器类型恢复问题可以作为数据流问题来解决，就像编译器可以通过这种方式对静态检查语言进行类型检查一样。可以使用传统的数据流分析，通常使用bit vector实现 [ASU86]。但是，这涉及为程序的每个基本块（甚至每个语句，取决于实现）存储有关所有活动变量的信息。假设反编译器将为静态类型语言生成代码，每个 SSA 变量将保留相同的类型，因此更稀疏的表示是可能的。 SSA 位置的每次使用都链接到它的静态唯一定义，因此存储变量类型信息的逻辑位置是在与该定义关联的赋值语句中。对于没有显式赋值的参数和其他位置，可以在中间表示中插入隐式赋值。

这个框架是稀疏的，因为类型信息主要只位于需要的地方（对每个定义或常量创建一个类型变量，而不是对每个变量(或常量)和每个基本块）

基于数据流的类型分析的 SSA 形式是流不敏感的，因为计算类型是为整个程序总结的。但是，由于假定位置的类型在整个程序中都是相同的，因此这不是一个限制。换句话说，使用 SSA 形式允许以流不敏感的算法实现相同的结果精度，使用更少的开销。

5.7.3 给表达式创建类型

在稀疏中间表示中，不存储子表达式的类型，因此必须根据表达式叶节点的需要，计算这些类型。

在反编译过程的早期，赋值通常采用简单的形式，例如 c := a \(\odot\) b，其中 \(\odot\) 是二元运算符，c 是位置，a 和 b 是位置或常量。然而，有些指令比这更复杂，并且在传播之后，表达式可以变得任意复杂。图 5.14 显示了一个简单的例子。

image-20230518161755702

图 5.14：为一个简单的表达式创建类型。

表达式树的叶子总是位置或常量（赋值的目的地除外，它总是一个位置）。在反编译器的稀疏类型分析系统中，位置和常量具有与其关联的类型变量。然而，没有地方可以存储子表达式的类型，例如 a[2000] 或 s.b，除非所有子表达式都存储一个类型并且失去了稀疏性。

在这个例子中，从其他语句中唯一知道的类型信息是 a 是一个字符指针数组（即 a 当前的类型为 char*[]）。表达式的类型分析从表达式树的底部开始，称为 ascend-type的过程。在本例中，算法以子表达式 a[2000] 开始。 array-of 运算符是少数几个运算符之一，其中一个操作数的类型（这里是 a，而不是 2000 ），如果已知，会影响结果，而结果的类型，如果已知，会影响该操作数。由于a的类型已知，所以可以计算出a[2000]的类型；在这种情况下它是 char*。此子表达式类型没有被存储；它是按需计算的。整数加法运算符是一种特殊情况，如果已知一个操作数是指针，则结果是指针类型，因为将指针和整数相加会得到指针。因此，整个表达式的类型被计算为 void*。 （将一个整数添加到一个 char* 并不总是会产生另一个 char*，因此结果的类型为 void*）。同样，不存储此类型。无法从 s、b 或 s.b 获得任何类型信息，因为 s 和 b 的类型当前未知。

接下来，第二阶段开始，称为descend-type。现在类型信息沿着表达式树向下流动，从根到叶。为了找到在加法运算符右侧的表达式树下推的类型，在其左侧操作数上调用 ascend-type。这将导致 char* 类型，如前所述。此类型与加法结果的类型一起用于查找加法右子表达式的类型。因为指针加上整数等于指针，所以找到的类型是整数。结构成员运算符，如 array-of 运算符，可以向上或向下传输表达式树的类型信息。在这种情况下，它会导致 b 的类型被设置为整数，而 s 的类型被设置为具有整数成员的结构。

当对 add 节点的左子表达式重复该过程时，结果为类型 void*，这意味着 a 的类型为 void*[ ]。然而，当遇到更精确的现有类型 char*[ ] 时，a 的类型仍为 char*[ ]。常量 2000 的类型设置为整数（数组索引始终为整数）。

在上面的示例中，位置 a 的初始类型来自程序中其他地方的类型信息。与位置相反，常量与程序的其他部分没有联系，如第 5.4 节所示。因此，常量仅由第二阶段被赋类型，descend-type。

通常，类型信息必须在表达式树中向上传播，然后再向下传播，分两次分开进行。

表 5.1 显示了各种运算符和常量的操作数和结果之间的类型关系。大多数运算符属于第一组，其中操作数和结果类型是固定的。对于其他不太常见的运算符和常量，需要 ascend-type 和 descend-type 的完整循环

在图 5.14 的示例中，a[2000] 的类型被计算了两次；期间一次ascend-type，再次descend-type。对于更复杂的表达式，descend-type 可能会在表达式树的重要部分多次调用 ascend-type。图 5.15 (a) 显示了具有四级二元运算符的表达式的最坏情况示例。在叶子节点，检查位置的类型（如果存在）可以被认为是一个操作。这个表达式树有 16 个叶节点，总共有 16 个操作。在树的上一级，使用来自两个子节点的信息检查父节点的类型，总共进行了三个操作。有八个这样的父节点，在这个级别总共有 24 个操作。类似地，在顶层，31 个操作（将近 2h+1，其中 h 是表达式树的高度）由 descend-type 执行。

image-20230518162635863

表 5.1：表达式运算符和常量的类型关系。

image-20230518162656184

图 5.15：上升和下降类型算法的复杂性。

图 5.15(b) 显示了一个包含所有三元运算符（例如 C 的 ?: 运算符）的树。这样的树在现实世界的例子中永远不会出现，但它说明了下降型算法在最坏情况下的复杂性。这里，执行了 3h+1 次操作。这种潜在的成本抵消了稀疏存储类型信息的空间节省（仅在定义时，而不是在使用时）。

5.7.4 加法和减法

从指针大小的加法和减法指令推断出的类型在基于数据流的类型分析中需要特殊的类型函数。

5.6 节展示了 Mycroft 约束的修改，它考虑了将常量添加到结构指针所导致的异常。为了在基于数据流的分析中表示 Mycroft 的约束，需要一些额外的类型和运算符。让 π 在格中为指针或整数或更高。希望所有出现的 π 最终都将被替换为更低（更精确）的类型，例如整数或特定的指针类型。int被认为与指针大小相同。在图 5.12 的格中，π 的值可以是指针或整数、size32 或 >。与 add a, b, c 相关的数据流方程（即 c=a+b），结构指针例外，可以重述为： \[ \begin{align} T (a) = Σ_a(T (c), T (b)) \qquad (5.1) \\ T (b) = Σ_a(T (c), T (a)) \qquad (5.2) \\ T (c) = Σ_s(T (a), T (b)) \qquad (5.3) \end{align} \] 其中 Σa 和 Σs（a 代表加数或被加数，s 代表总和）是特殊函数，定义如下（译者注：第一行代入运算结果c的类型，然后左边第一列代入其中一个运算数的类型。图中只标了一行或者一列，但是是这个意思。比如行那边标T(c) = xx 表示该行查找和的类型，在a+b=c这个等式中。）（注2：由于是数据流分析，所有格变量最开始都有初始类型π，代表不知道是数字还是指针，因此只要加法运算任意一方因为外部原因被更新，其他两个格变量都可以被更新。）

image-20230518163304404

（译者注：这里可以观察到，上边的表中，当运算结果(行)为指针，其中一个参与数（列）不知道类型(var-π)，此时结果依然为var-π。表示放弃了考虑这个约束。）

为简洁起见，ptr(α) 记为 α*。如果操作数分别是位置或常量，则类型变量 T (a)、T (b) 和 T (c) 被初始化为 var-π 或 const-π。 178 反编译器的类型分析 例如，考虑 p = q+r，已知 q 的类型为 char*，并且需要 r 的类型。由于 p 的类型尚不清楚，因此 p 的类型保持其初始值 var-π。 p、q 和 r 分别代替等式 5.2 的 c、a 和 b。该等式使用上面左表中定义的函数 Σa。由于 T (c) = var-π，因此使用第三列，并且由于 T (other) = α* 其中 α = char，因此使用第一行。第三列和第一行的交集包含 var-int，因此 T (b) = T (r) = int。

类似地，与sub a, b, c（即 c=a-b）相关的数据流方程可以重述为： \[ \begin{align} T (a) = ∆_m(T (c), T (b)) \qquad (5.4) \\ T (b) = ∆_s(T (c), T (a)) \qquad (5.5) \\ T (c) = ∆_d(T (a), T (b)) \qquad (5.6) \end{align} \] 其中，Δm、Δs 和 Δd（m 代表被减数（被减去的项目），s 代表减数（被减去的项目），d 代表差值（结果））是如下定义的特殊函数：

image-20230518163517707

如前所述，编译器不使用减法来引用结构成员，因此这次无需区分 var-int 和 const-int，或 var-π 和 const-π。

5.8 类型模式

一小组高级模式可用于表示全局变量、局部变量和聚合元素访问。 5.8 类型模式 179 用于访问全局、局部或堆变量、数组元素或结构元素的一系列机器指令通常会产生一个内存表达式，该表达式可以用以下范式表示：

image-20230518163605241

其中：

  • m[x] 表示地址x 处的内存。
  • m[...] 中加法的各项只需要存在一个。
  • [ a ｜ b ] 表示可选的a 或b 但不是两者。
  • \(sp_0\) 表示过程开始时堆栈指针寄存器的值。
  • pl 是用作指针的非常量位置（虽然非常量，但它可以在运行时采用几个常量值之一）。
  • \(S_j\) 是比例常数，其中一些可以等于1。
  • 这里*代表乘法。
  • \(ie_j\) 是不包含堆栈指针寄存器的非常量整数表达式，并且已知不是 x+C 的形式，其中 x 是一个位置，C 是一个常量。常量可以出现在 \(ie_j\) 的其他地方，例如它可能是 4*r1*r2。
  • K 是常数（整数或指针常数）。

必要时应用分配律，例如在尝试匹配上述等式之前，m[4*(r1+1000)] 被转换为 m[r1*4 + 4000]。如第 3 章所述，表达式传播、简化和规范化可用于为高级模式匹配准备中间表示。

m[...] 中项的总和必须是定义的指针表达式。指针不能相加，两个或多个整数相加不会得到指针，指针和整数相加的结果是指针。因此，恰好有一项是指针，其余项必须是整数。由于\(sp_0\)永远是指针，\(sp_0\)和pl不能同时出现，如果\(sp_0\)或pl都存在，K就不能是指针。

可以认为，由于 pl 或 K 可能为负，因此 sp0、pl 和 K 的所有三个可以同时存在，两个指针相互减去，得到一个常量。然而，这样的组合需要指针的相减，这在真实程序中从未出现

最初，可能无法将 pl 与 \(S_j =1\) 的 \(ie_j\) 区分开来，因此可能需要临时表达式，例如 \(m[l_1 + K]\) 或 \(m[l_1 + l_2 + K]\)，直到弄清楚 \(l_1\)、 \(l_2\)和K中哪个是指针。如果存在，\(sp_0\) 表示内存表达式表示堆栈分配的变量、数组元素或结构体元素。

image-20230518164428872

表 5.2：类型模式和讨论它们的命题。

表 5.2 显示了在传播和死代码消除之后可以在中间表示中找到的一系列模式，以及在接下来的几页中讨论它们的命题。很明显，有很多可能的模式，区分它们并非易事。这种区分的大部分留作未来的工作。

命题 5.8：（\(ie_j\)存在）将非常量整数表达式添加到指针意味着数组访问。

数组是相同元素的集合，并且可以被索引。结构是任何类型元素的集合，类型不一定相同，因此无法进行索引。因此，数组可以使用常量或变量索引表达式进行索引；索引表达式是整数类型。只能使用常量偏移访问结构元素。

因此，非常量整数表达式唯一可以出现的地方是作为数组索引。因此，当存在时，\(ie_j\) 指示数组索引，并且整个内存表达式引用数组元素。对于具有 m 维且其中 n 为非常量的数组元素访问，将至少有 n 个这样的项。 （一个或多个索引表达式可以是 j+k 的形式，其中 j 和 k 是位置，因此 n 是最小值。）

对于元素占用超过一个字节的一维数组，会涉及到一个尺度。缩放可以实现为移位操作、自我加法或乘以常数，但表达式的规范化会将所有这些更改为乘法操作。多维数组通常实现为子数组的数组，因此高阶索引表达式按子数组的大小缩放。数组和子数组的大小是常数，因此对于任何特定数组，Sj 都是常数。两次数组访问之间 Sj 的变化表明正在访问不同的数组，或者在索引表达式的至少一种情况下似乎正在缩放的部分。

命题 5.9：（存在 K）当存在时，方程 5.7 的常数 K 可以表示以下各项的总和：

  1. 全局数组、全局结构或全局变量的地址（sp0 和 pl 不存在）。 K 的这个组件可能是有界的：反编译器的前端可能能够对落在只读或读/写数据部分内的地址提供限制。
  2. 从初始堆栈指针值到局部变量、数组或结构（存在 sp0）的（可能为零）偏移量。
  3. 一个或多个可能缩放的常量数组索引。
  4. 由数组索引表达式中的常数项产生的常数。例如，如果在一个10×10的4字节整数数组中，索引表达式为a*b+4和c*d+8，则数组元素的奥集表达式为(a*b+4)* 40 + (c*d+8)*4，这将规范化为 40*a*b + 4*c*d + 192。在没有其他常数的情况下，K 将是 192，这部分来自常数索引表达式中的 4 和 8，以及元素的大小 (\(S_2\)=4) 和子数组的大小 (\(S_1\)=40)。
  5. 数组下界产生的下标不为零（例如，a: array [-20 .. -11] of real ）。如果多维数组的不止一维具有非零的数组下界，则几个这样的偏移将集中在一起。在 C 语言中，数组总是从索引 0 开始，但是可以构造指向数组中间或数组范围之外的指针，以实现类似的效果，如图 5.16 所示。请注意，在图 5.16(b) 中，可以将 a0+100 传递给另一个函数，该函数使用从 -100 到 -91 的索引访问数组 a0。
  6. 父结构内变量、数组或结构的结构成员集。在存在嵌套结构的情况下，可以将多个结构成员 offset 集中在一起，以生成从提供的对象的开始到所涉及的结构成员的开始的 offset。例如，在 \(s.t.u[i]\) 中，K 将包括从 s 的开始到 u 的开始的 offsets，或者等效地从 s 的开始到 t 的开始以及 t 的开始以及从t的开始 到u的开始的offset。
image-20230518170122323

图 5.16：用于访问具有非零索引下限的数组的第一个元素的源代码。

许多组合是可能的；例如如果在具有至少一个常量索引的结构中访问数组，则可以组合选项 (d) 和 (f)，例如s.a[5] 或 s.b[5, y] 其中 s 是一个结构体，a 是一个数组，b 是一个二维数组。

\(ie_j\) 项表示索引表达式的可变部分，索引表达式的常量部分将 off 拆分为 K 的一部分，如上文选项 5.9(d) 所示。为了节省空间，诸如 ie represents the variable part of the index expression 之类的语句将缩短为 ie represents the index expression，理解为索引表达式的常量部分实际上与其他项一起合并到 K 中。

很明显，在要类型化的程序的 IR 中可能会遇到许多模式，并且这些模式对所涉及的各种子表达式的类型做出不同的断言。以下命题总结了可能遇到的模式。

命题 5.10：m[K] 表示全局变量、全局结构成员或具有常量索引的全局数组元素，可能在全局结构中

K 是选项 5.9(a) 和 5.9(c)-(f) 的总和。如第 83 页的第 3.4.4 节所述，假设体系结构为全局变量访问保留了单独的寄存器，并通过基于该寄存器的偏移访问全局变量，该寄存器由反编译器前端初始化为常量值，以确保所有全局变量访问（在不断传播之后）就是这种形式。由于此模式可以表示全局变量、结构元素或具有固定 offset(s) 的数组元素，因此可以将基本类型提升为结构或数组元素。为了将其纳入类型概念的格中，可以通过稍微滥用术语将此观察表示为 ξ(array(int)) v int。这里的符号 ξ(array(α)) 表示其元素类型为 α 的数组的一个元素。这种关系可以理解为类型“int 数组的元素”是类型“variable of int”的子类型或等于类型（前者出现频率较低，在某种意义上 比后者更受约束).这同样适用于结构元素；类型为 β 的结构 σ 的元素记为 ξ(σ)(β)，其中结构类型未知或未指定，记为 ξ(structure-containing-β)。这些想法导致以下命题：

命题 5.11：ξ(array( α)) \(\sqsubseteq\) α，以及 ξ(structure-containing-α) \(\sqsubseteq\) α。

下面将对上述命题进行改进。需要注意的是类型 α 和 ξ(array(α)) 严格来说是相同的类型，所以\(\sqsubseteq\) 关系实际上是 =（相等），但是这样表达 α 的各种形式可以让这些形式成为一部分类型的格。当找到各种触发器时（例如，K 在程序的其他地方用作指向数组的指针），可以将与位置关联的类型向下移动格子（例如，从 α 到 ξ(array(α))）。这使得数组和结构成员的处理与类型分析的整个过程更加统一。

命题 5.12：m[sp0 + K] 表示基于堆栈的局部变量、局部结构成员或具有常量索引的局部数组元素，可能在局部结构中。

K 代表选项 5.9(b)-(f) 的总和。

命题 5.13：m[l + K] 表示聚合（数组或结构）元素访问。

这里，l 是一个位置，它可以是一个 ie 表示一个未缩放的数组索引，或者一个 pl 表示一个指向聚合的指针。如果 l 在其他地方用作整数或指针，则可以将此表达式重新定义为以下模式之一。由于l+K用作指针，加上两项意味着两项中一项是整数，另一项是指针，那么如果K的值不能是指针，则K必须是整数而 l 是一个指针。正如 5.4 节中指出的，常量是独立的，因此在其他地方使用同一常量不会影响 l 或 K 是否为指针。因此，影响 l 或 K 是 m[l + K] 中的指针的唯一因素是 l 是否在其他地方用作指针或整数，以及 K 是否具有阻止它成为指针的值。

​ 命题 5.14：m[ie + K] 表示全局数组元素访问。此处 ie 已知用作整数。 K表示选项5.9(a)和5.9(c)-(f)之和，即可能缩放的索引表达式。多维数组可以有其他索引表达式，都是常量

命题 5.15：m[pl + K] 表示具有常量索引的结构元素访问或数组元素访问。

这里 pl 是指向数组或结构（全局、局部或堆分配）的指针，K 表示选项 5.9(c)-(f) 的总和。例如，m[pl + K] 可以表示 s.m，其中 s 是结构类型的变量（用 pl 表示），m 是 s 的成员（K 表示从 s 开始到 m 的偏移集）。它还可以表示 a[C]，其中 a 是数组类型的变量（用 pl 表示），C 是一个常量，其值为 \(\frac{K}{sizeof(a[0])}\)。除非在别处发现非常量数组访问，否则无法区分这两种表示。

image-20230519101057542

图 5.17：使用表示法 m[pl + K] 的等价程序。

m[pl + K] 的两种表示是等价的，如图 5.17 所示。因此，这两种表述都不正确。结构表示看起来更自然，因此可以将此模式视为结构引用，除非并且直到找到具有非常量索引的数组引用。在任何一种情况下，由于可以随时在其他地方找到具有非常量索引的数组引用，因此数组元素在某种意义上比结构元素更受约束。再次滥用术语，这可以表示为 ξ(array(α)) \(\sqsubseteq\) ξ(structure containing α。

将其与命题 5.11 结合并注意到数组可以包含在结构中得到以下命题：

​ 命题 5.16: ξ(structure-containing-ξ(array(α))) \(\sqsubseteq\) ξ(array(α)) \(\sqsubseteq\) ξ(structure-containing-α) \(\sqsubseteq\) a.

这得到图 5.18 中所示的格片段。

上面的例子说明了这一点，即用于反编译的类型格至少部分不是基于源语言或程序的编写方式，而是基于在类型分析过程中如何发现信息。

image-20230519101330101

图 5.18：与包含数组元素、数组元素、结构成员和普通变量的结构相关的类型格片段

命题5.17：\(m[sp_0 + ie + K]\)表示局部数组元素访问

ie 是数组索引表达式，K 将选项 5.9(b)-(f) 合并在一起。

没有模式 \(m[sp_0 + pl + K]\) 因为 \(sp_0\) 和 pl 都是指针，并且假设指针永远不会和指针相加。

其中 \(l_1\) 和 \(l_2\) 是位置的模式 \(m[l_1 + l_2 + K]\) 很有趣，因为两个位置都可以匹配 ie 或 pl。在发现 \(l_1\) 或 \(l_2\) 的其他用途提供有关位置的类型信息之前，不知道哪个位置或 K 是指针。

命题 5.18：\(m[l_1 + l_2 + K]\) 表示数组元素访问。如果 \(l_1\) 或 \(l_2\) 在别处用作指针，或者 K 的值不能是指针并且 \(l_1\) 或 \(l_2\) 在别处用作指针或整数，则可以将此表达式重新定义为以下模式：

​ 命题 5.19：\(m[ie + pl + K]\) 表示数组元素访问。 ie是索引表达式，pl是指向数组的指针（全局、局部或堆分配），K代表选项5.9(c)-(f)的总和.

如果 l1 和 l2 在别处都作为整数使用，那么命题 5.18 可以重新定义为以下模式：

​ 命题 5.20：\(m[ie_1 + ie_2 + K]\) 表示全局数组元素访问。非常数索引表达式为\(ie_1 + ie_2\)，K表示选项5.9(a)和(c)-(f)之和。

命题 5.18 中模式的另一个特例是 K=0。 \(l_1\) 和 \(l_2\) 之一必须是整数，另一个必须是指针。根据命题 5.8，这意味着整数表达式表示数组索引。如果 \(l_1\) 或 \(l_2\) 之一在其他地方用作指针或整数，则此模式可以重新定义为以下模式。

​ 命题 5.21：\(m[ie + pl]\) 表示数组元素访问。 ie 是可能缩放的索引表达式，而 pl 是指向数组的指针。

命题 5.22：\(m[S_1*ie_1 + S_2*ie_2 + ... + S_n*ie_n + K]\) 表示 m 维全局数组元素访问。这里 \(ie_j\) 是索引表达式，\(S_1..S_n\) 是比例常数，K 将选项 5.9(a) 和 5.9(c)-(f) 合并在一起。如果有多个位置的索引表达式，则 m 可能小于 n。如果存在常量索引表达式，则 m 可能超过 n。这两个因素可以抵消或不存在，在这种情况下 m = n。

命题 5.23：\(m[pl + S_1*ie_1 + S_2*ie_2 + ... + S_n*ie_n + K]\) 表示一个 m 维数组元素访问。

这里 pl 指向数组或包含数组的结构，\(ie_j\) 是索引表达式，\(S_1.. S_n\) 是缩放常数，K 将选项 5.9(a) 和 5.9(c)-(f) 合并在一起。

命题 5.24：\(m[sp_0 + S_1*l_1 + S_2*l_2 + ... + S_n*l_n + K]\) 表示一个 m 维局部数组元素访问。

这里 \(l_i\) 是索引表达式，\(S_1..S_n\) 是缩放常数，K 将选项 5.9(b)-(f) 组合在一起。

命题 5.25：假定其他表达式是指针表达式的间接寻址。

C 语言中的示例包括 \((*p)[i]\) 和 \(*(ptrs[j])\)，其中上述表达式已应用于整个表达式的一部分以生成数组索引。

5.9 划分数据段

反编译器需要一个类似于编译器符号表（将符号映射到地址和类型）的数据结构来将地址映射到符号和类型。

第 155 页上的第 5.2.3 节指出，通常使用一系列机器代码指令而不是单个指令来操作聚合类型。例如，要对数组的内容求和，通常会使用循环。如果一个结构有 5 个基本类型的元素，通常至少有 5 段单独的代码来访问所有元素。换句话说，聚合类型的某些方面（例如元素数量和总大小）是许多指令的结果，而不是单个指令的结果。这与基本类型的类型和大小不同，后者通常可从单个指令获得。

因此，需要一个数据结构来构建数据部分如何组成的图景。这个过程可以被认为是将数据部分划分为各种类型的各种变量。这种数据结构在某种意义上相当于编译器或汇编器中最初为数据分配地址的符号表。在编译器或汇编器中，符号表本质上是一个从符号名到类型和数据地址的映射。在反编译器中，可以称为数据映射的适当数据结构是从数据地址到符号名称和类型的映射。

至少需要考虑两个地址空间：包含全局变量的全局地址空间和包含局部变量的堆栈局部地址空间。还有堆地址空间，其中变量（通常是聚合）是使用语言关键字（如 new）或调用堆分配库函数（如 malloc）创建的。但是，堆对象的分配通常一次只分配一个对象，并且设计的地址不会重叠。每个地址映射将使用单独的数据映射

5.9.1 并置变量(Colocated Variables)

需要逃逸分析来确定分离共置变量的有效性。

作为一种节省空间的优化，编译器可以将多个变量分配给同一地址。一旦确定这是安全的，这种托管对编译器来说就没有什么成本；它只是在符号表中有一些条目具有相同或重叠的数据地址值。然而，对于反编译器，问题要复杂得多。数据地址并不唯一标识数据映射条目，如图 5.19 所示。

image-20230519103443826

图 5.19：一个变量的活跃范围的各种可能

在图5.19(a)和(b)中，虽然变量有多种定义，但变量的定义和使用是通过φ-functions统一起来的。在情况 (c) 和 (d) 中，变量有多个活跃范围，从一个活跃范围到下一个活跃范围的数据流间断可以证明这一点。如果一个变量有多个活跃期，并且生存期中变量的类型不同，则必须生成两个或更多变量，因为编译器显然已将不相关的变量并置，并且每个命名变量只能有一种类型。

尽管必须生成多个名称，但仍然可以选择将这些名称的地址联合起来（例如使用 C Union），或者将它们分离为独立变量，生成代码的编译器可以将其分配给不同的地址。

然而，在各种活跃范围的类型一致的情况下，通常无法确定编译器是否将碰巧具有相同类型的不相关变量放在一起，或者原始源代码是否在多个活跃范围中使用了一个变量.后者可能发生的一个例子是数组索引在程序的第二个循环中被重新使用。始终将活动范围分成多个变量可能会使生成的源代码因过多的变量声明而变得混乱。当变量被赋予有意义的名称时，永远不将活动变量分成单独的变量可能会导致混淆。对一个活跃范围有意义的名称可能对其他活跃范围不正确。在这种情况下，专家用户可能会覆盖默认的反编译器行为。尽管可能会降低可读性，但这里没有不可避免地出现错误输出的情况。

有时，中间表示将有效地获取变量或聚合元素的地址。在高层，这可能是显式的，如 C 中的 & 一元运算符，或隐式的，如在 Java 中引用对象时（引用是字节码级别的指针）。获取地址可能与最终使用该变量或聚合元素相去甚远。变量或聚合元素地址的类型模式与第 5.8 节相同，但外部 m[. . .] 操作已删除。在某些情况下，这些将是非常常见的表达式，例如 K 或 ie + K。显然，并非所有此类模式都表示全局变量的地址或聚合元素的地址。

因此，这些模式在类型分析之后被应用，并且仅在类型分析显示模式（不包括 m[...]）是指针类型时使用。显然，第 5.8 节的模式带有 m[...] 保证内部表达式用作指针。

获取变量地址时，会引用该变量，但不会直接定义或使用它。数据流信息最终来自定义或使用，但当引用传递给库函数时，使用信息通常被浓缩为指定类型的常量引用或非常量引用。常量引用意味着所引用的位置已使用但未定义。一个非常量引用可能意味着各种定义和使用场景，所以保守的总结是可以定义和可以使用。库函数的目的可能比其原型携带更多的数据流信息。例如，CString::CString() 的 this 参数（字符串类的构造函数过程）在定义它之前不使用引用位置 (*this)。这个额外的信息可以帮助分离变量的生命范围，这些变量的存储与其他对象位于同一位置。虽然使用类型来帮助分离位于同一位置的变量可能很诱人，但原始程序使用强制类型转换的可能性使得类型对于此目的的可靠性降低。在 CString 构造函数的情况下，总是会启动一个新的活跃范围，但构造函数过程的原型中并未捕获这一事实。

image-20230519103918965

图 5.20：带有并置变量并获取地址的程序。

获取与其他变量位于同一位置的变量的地址可能会导致不清楚获取的是哪个对象的地址。例如，考虑图 5.20(a) 的机器码程序。位置 m[esp-16] 有三个独立的变量共享该位置。假设已知 proc1 和 proc2 保留且不使用 edi。用 proc2 的地址定义 m[esp-16] 完全杀死了整型变量的有效范围，但在程序早期获取的地址在程序的后期被使用，此时只有 char 定义是居住。 m[esp-16] 的定义不会终止单独变量 edi 的范围，它继续保持值 esp-16。 esp-16 代表什么的解释随着 m[esp-16] 的定义而改变，从 &i 到 &proc2 再到一个字符的地址。 edi的类型信息通过address taking操作链接到 m[esp-16]的数据流信息

在这种情况下，如果没有其他用途的 edi 并且没有其他指令获取 m[esp-16] 的地址，则三个变量可以在反编译输出中分开，如图 5.20(b) 所示。然而，如果 m[esi-16] 的地址逃脱了过程（例如 edi 被传递给 proc1），这种分离通常是不安全的。例如，可能不知道地址转义到的过程（这里是proc1）是否定义了原始变量。如果它只使用原始变量，那么它将作为一个整数来使用，参考图 5.20(b) 中的 i。但是，它可以定义和使用任何类型的位置。最后，它可以将地址复制到一个全局变量，该变量在变量超出范围之前被调用的某个过程使用。在这种情况下，传递给 proc1 的类型取决于实际使用该位置时哪个并置变量是活动的。 （编译器必须非常聪明才能安全地安排它，但这是可能的。）因此，如果地址逃逸，保守的方法是将三个变量声明为联合，就像 eect 中的机器代码所做的那样。这种逃逸分析通常由编译器执行，以确保优化的有效性；反编译器需要它来确保分离并置变量的有效性。

如果图 5.20 示例中的 proc1 是对 m[esp-16] 是非常量引用参数的库函数的调用，则会出现同样的歧义。参数的类型将是一个很大的线索，但由于存在强制转换的可能性，使用类型信息可能会导致反编译错误。因此，虽然库函数是类型信息的极好来源，但它们并不是可以帮助分离并置变量的数据流信息的良好来源。这可能是一种，至少部分反编译库函数有用的情况。

并置变量是一种原始程序地址代表多个原始变量的情况。第 20 页的图 1.6 显示了一个程序，其中使用相同的立即值（一个原始指针和两个偏移指针）在机器代码级别访问三个数组。这是一种不同的情况，尽管三个变量位于不同的地址，但使用相同的立即数常量来引用具有不同范围的索引的这些变量。它说明了公式 5.7 的常数 K 如何具有许多内部成分的问题，特别是命题 5.9(e) 的常数 K

图 5.21 显示了三个嵌套结构的声明。第一个元素的地址可以引用 large、large.medium、large.medium.small 或 large.medium.small.a 中的任何一个。其中每一个的类型都是不同的，因此可以使用类型分析来决定需要哪些可能的引用。

image-20230519104959738

图 5.21：嵌套结构体

5.10 特殊类型

需要一些特殊类型来满足某些机器语言细节，例如upper（float64）。

除了基本类型、聚合和指针之外，一些特殊类型在反编译中也很有用。显然不需要类型信息（> 在类型格中，或 C 类型 void），并且可能过度约束（在类型格中为 ⊥）。许多机器使用成对的位置（两个寄存器，或两个字大小的内存位置）实现双字类型。因此，定义 upper(τ) 和 lower(τ) 可能很有用，其中 τ 是类型变量，分别指代 τ 的上半部分或下半部分。对于较大的类型，这些可以组合，例如lower(upper(float128)) 对于 128 位浮动点类型的位 64 到 95。例如，size32 将与 upper(float64) 兼容。在适当的情况下，成对的上层和下层类型可以合并成更大的类型，例如其中双字值在机器语言级别在两个字大小的位置传递给函数，这可以用一个变量替换（例如double类型）

5.11 相关工作

大多数相关工作都是面向编译器的，因此没有解决机器代码反编译引起的一些问题。

许多作者都讨论过使用迭代数据流方程来解决编译器问题，首先是 Allen 和 Cocke [All70, AC72] 以及 Kildall [Kil73]。 Kam 和 Ullman [KU76] 证明了这些系统的理论性质

Khedker、Dhamdhere 和 Mycroft 主张更复杂的数据流分析框架，但他们试图解决动态类型语言 [KDM03] 的类型推断这一更困难的问题。

Guilfanov [Gui01] 讨论了通过可执行程序的 IR 从库函数传播类型的问题。但是，他没有尝试推断指令中固有的类型

通过为每个变量构建一个独特的评估图 [CCF91]，可以以比 SSA 形式支持的更稀疏的方式解决数据流问题。然而，这种方法受到为每个变量生成评估图以及该框架所需的一些其他表的空间和时间成本的影响。

Guo等，报告了汇编语言的指针分析，他们建议可以将其扩展以在运行时使用 [GBT+05]。在处理加法指令时，他们假设数组和结构元素访问的地址表达式的形式为 r2 + i × l + c，其中 i 是一个非常量（索引）值，l 是大小数组元素的个数，c 为常量。这与公式 5.7 的更复杂的表达式形成对比。后者比较复杂，主要是为了表达多维数组，例如a[x][y] 例如m[r1 * 40 + r2 * 4] + 8。但是，后者可以归一化为 m[(r1 * 10 + r2) * 4] + 8，表示 a[x*10+y]，其中 10是行中的元素数。机器代码数组似乎可以像这样分析，并在稍后阶段转换回 a[x][y] 或 a[x, y] 格式。

5.12 未来工作

虽然已经取得了很好的进展，但在机器代码反编译器的类型分析成熟之前，还有很多工作要做。

本章中提出的大部分想法至少已在 Boomerang 反编译器 [Boo02] 中部分实现。诸如基于迭代数据流的类型分析问题解决方案等基本原则足以用于类型化简单的程序。然而，类型分析的几个更高级的方面需要实验验证，包括

  • 更不寻常的情况涉及指针大小的加法和减法指令（第 177 页第 5.7.4 节）；
  • 将 K 的值拆分为其各种可能的来源（第 181 页的命题 5.9），这可能需要对指针和索引变量进行范围分析；
  • 分离并置变量和逃逸分析（第 187 页第 5.9.1 节）；和
  • 划分数据段（第 186 页第 5.9 节）

指针的范围分析对于初始化聚合数据也很重要，如第 5.2.4 节所述

当前对数组的处理假定多维数组的数组实现类 C 数组。应该可以修改高层的模式以适应其他实现

C++ 等面向对象的语言引入了更多需要考虑的元素，例如成员指针、类层次结构等。其中一些功能将在下一章中讨论

5.13 SSA 的作用

在 SSA 形式下，表达式传播与内存表达式简化相结合，为高级模式分析打下基础，并且 SSA 形式允许类型信息的稀疏表示。

第 178 页第 5.8 节的高级模式需要将整数常量与其他整数表达式区分开来。这很容易通过基于SSA的表达式传播和简化的组合来实现。这些还消除了 RISC 编译器生成的部分常量，这在任何类型分析系统中处理起来都很尴尬。

SSA 形式还允许在位置定义处对类型信息进行稀疏表示。每个 SSA 定义一种类型存储与每个基本块每个活动变量一种类型存储的要求形成对比，这是传统的基于bit vector的迭代框架所要求的。