使用rellic-headergen解析C数据结构 - The Trail of Bits博客

Francesco Bertolaccini
2022年1月19日
static-analysis, compilers, research-practice

你是否曾想过编译器是如何看待你的数据结构的？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的重建算法首先按偏移量递增的顺序对字段进行排序，然后定义一个新的结构体来添加每个字段。元数据没有提供关于原始定义是否声明为打包的信息，因此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。 among other reasons，这是为了在像下面这样的代码片段中，每个字段都保证有单独的地址：

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类型。许多逆向工程工具嵌入了某种形式的基本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方面的经验。