数据结构 考研(数据结构考研参考)

数据结构 考研，数据结构考研真题

你有没有想过编译器如何查看你的数据结构？Compiler Explorer 可以帮助你了解源代码和设备代码之间的关系，但它在数据布局方面提供的支持不多。你可能听说过填充、对齐和“普通旧数据类型”，甚至通过将一种结构嵌入到另一种结构中来模拟 C 中的继承。但是，你能猜出所有这些类型的确切内存布局，而无需查看你平台的 ABI 引用或标准库的源代码吗？

有了必要的 ABI 知识，关于 C 结构的推理就相对简单了。然而，更复杂的c++类型则是完全不同的情况，特别是当使用模板和继承时。理想情况下，我们能够将所有这些复杂的类型转换成简单的C结构，这样我们就可以更容易地推断它们在内存中的布局。这正是relic -headergen的目的，这是我在Trail of Bits实习期间开发的一个工具。在这篇文章中，我将解释它的工作原理。

rellic-headergen

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

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

该工具的工作原理是假设被分析的程序可以被编译成具有完整调试信息的LLVM位码。该实用程序开始构建一个包含调试信息可用的所有类型的列表，从函数 (“subprogram”)定义开始。

现在，该实用程序需要决定定义类型的顺序，但考虑到 C 语言的要求，这不是一项简单的任务：当引用尚未定义的类型时，该语言需要明确前置声明，例如，结构不能包含其类型仅被前向声明的字段。

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

因此，该实用程序根据类型定义形成一个有向无环图 (DAG)，它可以在其上找到拓扑排序。

一旦该实用程序找到了一个拓扑排序，它就可以按照这个顺序检查类型，并且确信任何字段的类型都已完全被定义。

关于结构的恶作剧

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

类型的大小；

每个字段的类型；

每个字段的偏移量；

类型最初是结构体还是联合体；

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

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

幸运的是，rellic-headergen已经使用Clang来生成定义。不幸的是，查询Clang本身关于字段的偏移量并不是那么简单，因为Clang只允许检索完整定义的布局信息。为了解决API的这个特殊问题，实用程序生成临时结构定义，其中包含当前正在处理的字段之前的所有字段。

结构和继承

当我在处理更多涉及的用例时，我偶然发现了一些 ABI 以不立即显而易见的方式工作的实例。例如，处理 C++ 继承需要小心，因为简单的方法并不总是正确的。

转换成

这似乎是个好主意，在实践中也很有效，但这种方法的可扩展性不太好。例如，以下代码段不能以这种方式转换:

原因是在 int 为 4 个字符宽的设备上，结构 A 通常在 y 之后包含 3 个额外的填充字符。因此，将结构 A 直接嵌入 B 将使 z 位于偏移量 8 处。为了最大限度地减少结构中的填充量，编译器选择将派生类型的字段直接放置在基本结构中。

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

上面的例子工作得很好，但是在有些地方，用简单的方法处理空结构是行不通的。考虑如下：

此示例生成以下 DWARF 元数据：

如果我们遵循dw_tag_继承和DW_TAG_member相同的逻辑，就会得到这样的转换：

这和原来的定义不一样！字段b最终的偏移量与0不同，因为字段的大小不能为0。让所有这些c++细节工作是有挑战性的，但非常值得。现在我们可以使用rellic-headergen将任意c++类型转换为普通的C类型。许多逆向工程工具嵌入了某种形式的基本C解析支持，以便用户提供“类型库”，描述设备代码使用的类型。这些基本的解析器通常不支持任何c++，所以rellic-headergen弥补了这一缺陷。

relic -headergen的改进空间?

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

该程序产生以下位码：

在这个位码中，关于x结构的原始信息已经丢失了。本质上，如果Clang/LLVM在发出位码或从已编译的设备码中提升位码之前执行优化，这可能会导致生成的位码级别过低，从而在调试元数据中找到的类型信息与位码本身中的信息不匹配。在这种情况下，relic -headergen无法自行解决这种不匹配。改进实用程序以便能够在未来解决这些问题将是有益的，当尝试将位移位和掩码与字段访问匹配以生成尽可能接近原始代码的反编译代码时，了解结构的确切布局可能很有用。

此外，rellic-headergen 也无法处理使用不同 DWARF 功能的语言。例如，Rust 对有区别的联合使用了一种特别的表示，这对于实用程序来说很难处理。有朝一日可以向该实用程序添加功能来处理这些 DWARF 功能。

总结

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

参考及来源：https://blog.trailofbits.com/2022/01/19/c-your-data-structures-with-rellic-headergen/

数据结构 考研(数据结构考研参考)

未经允许不得转载：考研网 » 数据结构 考研(数据结构考研参考)