使用 rellic-headergen 解析 C/C++ 数据结构

你是否曾想过编译器是如何看待你的数据结构的？Compiler Explorer 可以帮助你理解源代码和机器码之间的关系，但在数据布局方面，它提供的支持并不多。你可能听说过填充（padding）、对齐（alignment）和“普通旧数据类型”（plain old data types）。也许你甚至尝试过通过在 C 语言中嵌入一个结构体来模拟继承。但你能猜出所有这些类型的确切内存布局吗，而不需要查看平台的 ABI 参考或标准库的源代码？

1
2
3

struct A { int x; };
struct B { double y; };
struct C : A, B { char z; };

具备必要的 ABI 知识后，推理 C 结构体相对简单。然而，更复杂的 C++ 类型则完全是另一回事，尤其是当模板和继承介入时。理想情况下，我们能够将这些复杂类型转换为简单的 C 结构体，以便更轻松地推理它们的内存布局。这正是 rellic-headergen 的确切目的，这是我在 Trail of Bits 实习期间开发的一个工具。在这篇博客文章中，我将解释它为什么以及如何工作。

rellic-headergen

rellic-headergen 的目的是生成与 LLVM 位码文件中包含的类型定义等效的 C 类型定义，这些类型不一定是从 C 源代码生成的。这有助于分析包含复杂数据布局的程序。以下图像提供了 rellic-headergen 功能的一个示例。

左侧窗口显示我们的源代码。我们在底部窗口执行第一个命令将代码编译为 LLVM 位码，并使用第二个命令通过 rellic-headergen 运行它。右侧窗口显示 rellic-headergen 的输出，这是与输入 C++ 代码布局匹配的有效 C 代码。

该工具基于一个假设：被分析的程序可以编译为具有完整调试信息的 LLVM 位码。该工具开始构建所有可用调试信息的类型列表，从函数（“子程序”）定义开始。

现在，该工具需要决定类型定义的顺序，但考虑到 C 语言的要求，这并非易事：语言要求在引用尚未定义的类型时进行显式前向声明，并且结构体不能包含，例如，其类型仅被前向声明的字段。

解决这个问题的一种方法是预防性地前向声明所有现有类型。然而，这还不够。例如，结构体不能包含其类型尚未完全定义的字段，尽管它可以包含其类型是指向前向声明类型的指针的字段。

因此，该工具从类型定义形成一个有向无环图（DAG），并在其上找到拓扑排序。

一旦工具找到拓扑排序，它就可以按此顺序检查类型，并确信任何字段的类型都已完全定义。

结构体的花招

DWARF 元数据提供了一些信息，我们可以用来恢复它描述的类型 C 结构定义：

• 类型的大小
• 每个字段的类型
• 每个字段的偏移量
• 类型最初是结构体还是联合体

rellic-headergen 的重建算法首先按偏移量递增的顺序对字段进行排序，然后定义一个新的结构体来添加每个字段。元数据没有提供原始定义是否声明为打包（packed）的信息，因此 rellic-headergen 首先尝试直接按照元数据的指定生成布局。如果生成的布局与输入的布局不匹配，该工具会从头开始并生成打包布局，根据需要手动插入填充。

现在，我们可以使用任何数量的复杂启发式方法来确定每个字段从结构体开始的偏移量，但事情可能会变得相当复杂，尤其是在位字段的情况下。更好的方法是从已经解决了逻辑的东西中获取这些信息：编译器。

幸运的是，rellic-headergen 已经使用 Clang 来生成定义。不幸的是，查询 Clang 本身关于字段偏移的信息并不那么简单，因为 Clang 只允许检索完整定义的布局信息。为了绕过 API 的这个特殊怪癖，该工具生成临时的结构定义，其中包含直到当前正在处理的字段的所有字段。

结构体和继承

在处理更复杂的用例时，我遇到了一些 ABI 工作方式并不立即明显的情况。例如，处理 C++ 继承需要一些小心，因为朴素的方法并不总是正确的。将

1
2

struct A { int x; };
struct B : A { int y; };

转换为

1
2
3
4
5

struct A { int x; };
struct B {
    struct A base;
    int y;
};

似乎是个好主意，并且在实践中有效，但这种方法扩展性不好。例如，以下代码片段无法以这种方式转换：

1
2

struct A { int x; char y; };
struct B : A { char z; };

原因是在 int 为 4 个字符宽的机器上，结构体 A 通常在 y 之后包含 3 个额外的填充字符。因此，将结构体 A 直接嵌入到 B 中会将 z 放在偏移量 8。为了最小化结构体中的填充量，编译器选择将派生类型的字段直接放在基结构体中。

此外，空结构体在技术上在 C 中无效。它们可以通过 GCC 和 Clang 扩展使用，并且在 C++ 中有效，但它们带来了一个问题：空结构体的 sizeof 永远不会是 0。相反，它通常是 1。除其他原因外，这是为了在像下面这样的代码片段中，每个字段都保证有单独的地址：

1
2
3
4
5

struct A {};
struct B {
    struct A a;
    int b;
};

上面的例子工作得很好，但在某些地方，以朴素的方式处理空结构体是行不通的。考虑以下：

1
2
3
4

struct A {};
struct B : A {
    int x;
};

这个例子产生以下 DWARF 元数据：

1
2
3
4
5
6
7
8
9

!2 = !{}
!10 = distinct !DICompositeType(
    tag: DW_TAG_structure_type, name: "A", size: 8, elements: !2)
!11 = distinct !DICompositeType(
    tag: DW_TAG_structure_type, name: "B", size: 32, elements: !12)
!12 = !{!13, !14}
!13 = !DIDerivedType(tag: DW_TAG_inheritance, baseType: !10)
!14 = !DIDerivedType(tag: DW_TAG_member, name: "x", baseType: !15, size: 32)
!15 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed)

如果我们对 DW_TAG_inheritance 采用与 DW_TAG_member 相同的逻辑，我们最终会得到这个转换：

1
2
3
4
5

struct A {};
struct B {
    struct A a;
    int b;
};

这与原始定义不等效！字段 b 最终会处于不同于 0 的偏移量，因为字段不能有大小 0。让所有这些 C++ 细节工作起来具有挑战性但值得。现在我们可以使用 rellic-headergen 将任意 C++ 类型转换为普通的旧 C 类型。许多逆向工程工具嵌入某种形式的 basic C 解析支持，以便用户提供“类型库”，这些库描述机器代码使用的类型。这些基本解析器通常没有任何 C++ 支持，因此 rellic-headergen 弥合了这一差距。

rellic-headergen 的下一步是什么？

有机会进一步改进 rellic-headergen。该工具的目标之一是能够从已优化的代码中恢复字段访问模式。考虑以下程序：

1
2
3
4
5

struct A {
    char a, b, c, d;
};

char test(struct A x) { return x.c; }

这个程序产生以下位码：

1
2
3
4
5
6

define dso_local signext i8 @test(i32 %x.coerce) local_unnamed_addr #0 {
entry:
    %x.sroa.1.0.extract.shift = lshr i32 %x.coerce, 16
    %x.sroa.1.0.extract.trunc = trunc i32 %x.sroa.1.0.extract.shift to i8
    ret i8 %x.sroa.1.0.extract.trunc
}

在这个位码中，关于 x 结构的原始信息已经丢失。本质上，如果 Clang/LLVM 在发出位码或从编译的机器代码提升位码之前执行优化，这可能导致生成的位码过于低级，在调试元数据中的类型信息与位码本身中的信息之间创建不匹配。在这种情况下，rellic-headergen 无法自行解决这种不匹配。未来改进该工具以能够解决这些问题将是有益的；知道结构体的确切布局在尝试将位移和掩码与字段访问匹配以生成尽可能接近原始的反编译代码时非常有用。

此外，使用不同 DWARF 特性的语言 rellic-headergen 处理得不好。例如，Rust 对 discriminated unions 使用一种临时表示，这对该工具来说很难处理。有机会有一天向该工具添加功能来处理这些 DWARF 特性。

最后，另一个值得探索的未来 rellic-headergen 特性是改变输出语言的可能性：有时你确实想保留那个继承信息作为 C++！

结束语

尽管 rellic-headergen 目前范围非常狭窄，但在处理 C 和 C++ 代码库时已经非常强大，因为它能够为 rellic 本身提取类型信息，其中包括 LLVM 和 Clang。它已经在导航使用调试信息构建的二进制文件时提供了有用的见解，但扩展其功能集以能够从更多样化的代码库中提取信息将使其在处理更大项目时更加有用。

从事 rellic-headergen 的工作非常有趣、引人入胜且富有教育意义。我感谢 Trail of Bits 有机会与有才华的人一起从事这样一个创新项目。这是一次很好的学习经历，我要感谢我的导师 Peter Goodman 在项目中给予我几乎完全自由的指导，以及 Marek Surovič 耐心地与我分享他在 rellic 方面的经验。