利用死存储消除优化提升Bitcode性能

引言

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

为什么需要专门的DSE优化？

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

安全性和正确性保证

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

提升过程中的状态结构

Remill/McSema提升bitcode的骨干是State结构，它模拟机器的寄存器状态。Remill通过使用对State结构中的指针进行操作的LLVM加载和存储指令来模拟对寄存器的读写。以下是一个具有两个寄存器（eax和ebx）的玩具x86架构的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显示，某些加载和存储操作是冗余的，可以被转发或消除。这个过程在实际的bitcode中会持续进行，直到没有更多可以转发或消除的内容。

构建消除器：槽位分割

DSE过程需要将通过%eax_ptr和%ebx_ptr的加载/存储识别为不同的操作。DSE通过将State结构分割成"槽位"来实现这一点，这些槽位大致代表寄存器，对于将数组和向量等序列类型捆绑为一个逻辑对象的情况有一些小的区别。

指针偏移和槽位映射

为了确定任何给定指针引用的槽位，我们需要计算该指针的偏移量，并将偏移量映射回槽位。如果是指针派生，则需要计算基指针的偏移量。这本质上是一个递归的偏移量计算过程。

使用ForwardAliasVisitor识别别名

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

我们使用ForwardAliasVisitor（FAV）来识别别名指令。FAV跟踪所有指向状态结构偏移量的指针以及涉及访问状态结构的所有指令。顾名思义，它向前遍历给定的指令，如果注意到它跟踪的某个地址已被修改或使用，就会保持计数。

实时性分析和死指令消除

LiveSetBlockVisitor（LSBV）负责检查模块函数的每个基本块，以确定State中槽位的整体实时性。简而言之，实时变量分析允许DSE检查存储是否会在加载访问（“复活”）槽位之前被覆盖（“杀死”）。

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

指令转发优化

在LSBV之前，我们可以通过ForwardingBlockVisitor进行指令转发。使用FAV收集的别名，它可以从前到后迭代块的指令，跟踪对State每个槽位的即将加载。如果我们发现较早的操作访问相同的槽位，可以将其转发以减少操作数量。

优化成果展示

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

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

候选存储：210,855
死存储：117,059
DSE移除的指令：273,322
转发的加载：840
转发的存储：2,222

可视化优化效果

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

未来优化方向

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

如果您认为Tim的工作很酷，请查看McSema和Remill上的"实习项目"GitHub问题标签，在Empire Hacking Slack的#binary-lifting频道与我们交谈，或通过我们的招聘页面联系我们。