优化提升后的Bitcode与死存储消除

作为我在Trail of Bits春季实习项目的一部分，我创建了一系列基于数据流的优化技术，用于消除McSema提升程序中模拟机器代码寄存器写入的大部分"死"存储操作。例如，将我的死存储消除（DSE）过程应用于Apache httpd时，成功消除了117,059个存储操作，相当于Remill寄存器状态结构中50%的存储操作。如果您是McSema的常规用户，请拉取最新代码以享受这些优化好处——DSE现已默认启用。

您可能会想：“等等，Tim，DSE不是LLVM中已经存在的基础优化吗？“这个问题问得很好（答案确实是肯定的），因为如果您使用过LLVM，就会知道它拥有优秀的优化器。然而，尽管LLVM非常出色，但事实是，就像任何优化器一样，LLVM只能删除它认为不必要的指令。Remill死代码消除器的优势在于拥有关于提升后bitcode性质的更高层次信息，这使得它在执行优化时比LLVM更加激进。

但每个问题的解答都会引发更多问题！您现在可能在想：“LLVM只进行安全优化。这个DSE更加激进…我们怎么知道它没有破坏提升后的httpd程序？“请放心！死存储消除工具专门设计用于对已经优化过的提升bitcode执行全程序分析。这确保了它能够在最大可能的上下文中找到死指令，避免程序假设某些代码不会被使用的错误。最终输出是一个功能完整的httpd可执行文件，只是去除了一大堆无用的计算。

提升时会发生什么

Remill/McSema提升bitcode的骨干是State结构，它模拟了机器的寄存器状态。Remill通过使用LLVM加载和存储指令来模拟对寄存器的读写，这些指令操作指向State结构的指针。以下是一个玩具x86架构（具有两个寄存器：eax和ebx）的Remill State结构可能的样子：

1
2
3
4

struct State {
  uint32_t eax;
  uint32_t ebx;
};

在LLVM中，这将表示为：

1

%struct.State = type { i32, i32 }

假设我们正在查看这个架构中的几行机器代码：

1
2

mov eax, ebx
add eax, 10

这段代码的LLVM IR简化版本可能如下所示：

前两行从状态指针（%state）派生出支持模拟eax和ebx寄存器的内存指针（分别为%eax_addr和%ebx_addr）。这个派生过程使用getelementptr指令执行，相当于C代码&(state->eax)和&(state->ebx)。接下来的两行表示mov指令，其中模拟的ebx寄存器被读取（load），然后读取的值被写入（store）到模拟的eax寄存器。最后，最后三行表示add指令。

我们可以看到%ebx_0被存储到%eax_ptr，然后%eax_0从%eax_ptr加载，期间没有任何对%eax_ptr指针的干预存储。这意味着加载到%eax_0是冗余的。我们可以在任何使用%eax_0的地方直接使用%ebx_0，即将存储转发到加载。

接下来，我们可能还会注意到存储指令%ebx_0, %eax_ptr也不是特别有用，因为在%eax_ptr再次被读取之前，存储指令%eax_1, %eax_ptr已经发生。实际上，这是一个死存储。消除这类死存储正是我的优化重点！

这个过程将在真实的bitcode中持续进行，直到没有更多可以转发或删除的内容。

构建消除器

介绍完毕，让我们深入了解这个死代码消除应该如何工作。

插槽划分

DSE过程需要识别通过%eax_ptr和%ebx_ptr的加载/存储是不同的。DSE过程通过将State结构划分为"插槽"来实现这一点，这些插槽大致代表寄存器，但在我们将数组和向量等序列类型捆绑为一个逻辑对象的情况下有一些小区别。我们简化State结构的插槽如下：

在划分State结构后，DSE过程尝试用指令可能引用的插槽来标记指令。但我们如何进行这种标记呢？我之前提到过，我们对提升bitcode的性质有更深入的了解，这里就是我们可以使用这些知识的地方。在提升的bitcode中，State结构作为参数传递给每个提升的函数。因此，对模拟寄存器的每次加载或存储都源自这个State指针（例如通过getelementptr、bitcast等）。每个这样的派生都会产生一个可能从其基础偏移的新指针。因此，要确定任何给定指针引用的插槽，我们需要计算该指针的偏移量，并将偏移量映射回插槽。如果它是一个派生指针，那么我们需要计算基础指针的偏移量。如果基础指针是派生的…实际上，这只是一直向下计算偏移量。

插槽匹配

我们最感兴趣的情况是当两个指令变得友好并别名到同一个插槽时。这就是一个指令杀死另一个指令所需的全部条件：在Remill中，这是丛林法则。

为了识别别名的指令，我们使用ForwardAliasVisitor（FAV）。FAV在两个相应的映射中跟踪所有指向状态结构偏移量的指针和所有涉及访问状态结构的指令。顾名思义，它向前遍历给定的指令，如果注意到它跟踪的某个地址已被修改或使用，就会进行统计。

以下是这些信息如何从我们的指令中构建：

每次FAV访问指令时，它都会检查是否需要更新其映射。

访问映射存储访问状态偏移量的指令。我们稍后将使用此映射来确定哪些加载和存储指令可能别名。您已经可以在这里看到三个指令的偏移量都相同：这清楚地表明我们以后可以消除指令！

偏移映射确保访问映射能够获取正确的信息。从基础%state指针开始，偏移映射累积程序运行时可能引用的任何指针。您可以将其视为加载和存储用来调用状态结构不同部分的地址簿。

这里显示的第三个数据结构是排除集。它跟踪指令可能引用的所有其他值，我们知道这些值不应该接触状态结构。这些将是加载指令读取的值，或指向alloca内存的指针。在这个例子中，您还可以看到，如果一个值已经在偏移映射或排除集中，从这样一个值产生的任何值将保留在同一个集合中（例如，%eax_1被排除，因为%eax_0已经被排除）。您可以将排除集视为偏移映射地址簿的"请勿呼叫"列表。

FAV仔细检查代码，确保能够访问每个函数的每条指令。完成后，我们可以将相关的状态插槽作为LLVM元数据与每个加载和存储关联起来，然后进入死代码消除器的高潮：消除死指令！

即将彻底死亡

现在是我们仔细检查别名指令并查看是否可以消除任何指令的时候了。我们有一些可用的技术，遵循与之前类似的模式。我们将检查指令并确定它们作为数据流消除的可行性。

按顺序，我们运行ForwardingBlockVisitor来转发不必要的加载和存储，然后使用LiveSetBlockVisitor来选择要消除的指令。然而，为了本文的目的，我们将以相反的顺序介绍这些步骤，以便更好地理解它们为什么有用。

活跃集分析

LiveSetBlockVisitor（LSBV）有着检查模块函数每个基本块以确定State中插槽整体活跃度的光荣任务。简而言之，活跃变量分析允许DSE检查存储是否会在加载访问（“复活”）插槽之前被覆盖（“杀死”）。LSBV的LiveSet是一个位集，表示State结构中每个插槽的活跃度：如果插槽是活跃的，则对应于插槽索引的位设置为1。

LSBV从函数的终止块（以ret指令结束的块）开始，返回到入口块，跟踪每个块的活跃集。这使它能够根据后继块的活跃度确定前驱块的活跃集。

以下是LSBV过程如何进行的一个例子。从终止块开始，我们向后遍历块的指令，并在此过程中更新其活跃集。完成后，我们将块的前驱添加到工作列表中并继续处理它们。分析完入口块后，我们完成过程。当插槽已经死亡时访问的任何存储都可以声明为死存储，然后我们可以删除它们。

为了避免任何未定义行为，LSBV有一些泛化处理。一些指令，如resume或indirectbr，可能对块的活跃集造成不确定变化，保守地将所有插槽标记为活跃。这提供了一种避免危险消除的简单方法和未来改进的机会。

转发优化

我们的工作本可以在这里以LSBV结束，但我们仍然可以对DSE进行潜在的改进。如前所述，我们可以通过用存储之前的值直接使用来替换存储值、加载该值和使用该值的不必要序列来"转发"一些指令。这是由ForwardingBlockVisitor处理的，这是另一个向后块访问器。使用FAV收集的别名，它可以从后向前迭代块的指令，跟踪接下来对State每个插槽的加载。如果我们发现较早的操作访问相同的插槽，我们可以转发它以减少操作数量，如前面的消除示例所示。

在LSBV过程之前执行此步骤允许LSBV识别比之前更多的死指令。再次查看我们的示例，我们现在设置了另一个存储供LSBV过程杀死。这种类型的程序允许我们通过更好地利用我们对插槽何时将被使用的知识来删除比之前更多的指令。以这种方式级联消除是DSE能够删除如此多指令的部分原因：如果一个存储被删除，可能会有更多变得无用的指令也可以被消除。

DSE减肥见证

得益于死存储消除的瘦身能力，我们可以对提升代码中的指令数量进行一些令人印象深刻的削减。

对于amd64 Apache httpd，我们能够生成以下报告：

• 候选存储：210,855
• 死存储：117,059
• DSE移除的指令：273,322
• 转发的加载：840
• 转发的存储：2,222
• 完美转发：2,836
• 通过截断转发：215
• 通过转换转发：11
• 通过重排序转发：61
• 无法转发：1,558
• 未分析函数：0

DSE的一个附加功能是能够生成已移除指令的DOT图。目前，DSE将为每个访问的函数生成三个图，显示识别的偏移量、标记为要移除的存储和移除后的指令。

仍然渴望优化？

虽然这可能是Tim在DSE上工作的暂时结束，但未来的改进已经在进行中，以使Remill/McSema的提升bitcode更加精简。工作将继续处理DSE目前不够勇敢处理的情况，例如当插槽只在一个分支中活跃时下沉存储指令，更精确地处理对其他函数的调用，以及将活跃区域提升到allocas以受益于LLVM的mem2reg过程。

认为Tim做得很酷？查看McSema和Remill上的"实习项目"GitHub问题标签以参与其中，在Empire Hacking Slack的#binary-lifting频道与我们交谈，或通过我们的招聘页面联系我们。

Tim今年九月将在普林斯顿大学开始编程语言理论的博士研究，在那里他将尝试遵循指令，而不是消除指令。