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

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

你是否曾想过编译器是如何看待你的数据结构的？Compiler Explorer可以帮助你理解源代码和机器代码之间的关系，但在数据结构布局方面提供的支持有限。你可能听说过填充、对齐和"普通旧数据类型"的概念。也许你甚至尝试过通过在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。除其他原因外，这是为了确保在以下代码片段中，每个字段都保证有单独的地址：

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方面的经验。