优化提升后的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的骨干是状态结构，它模拟机器的寄存器状态。Remill通过使用LLVM加载和存储指令来模拟对寄存器的读写，这些指令操作指向状态结构的指针。以下是一个玩具x86架构（有两个寄存器：eax和ebx）的Remill状态结构可能的样子：

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的极度简化版本可能如下所示：

1
2
3
4
5
6
7


%eax_addr = getelementptr %struct.State, %struct.State* %state, i32 0, i32 0
%ebx_addr = getelementptr %struct.State, %struct.State* %state, i32 0, i32 1
%ebx_0 = load i32, i32* %ebx_addr
store i32 %ebx_0, i32* %eax_addr
%eax_0 = load i32, i32* %eax_addr
%eax_1 = add i32 %eax_0, 10
store i32 %eax_1, i32* %eax_addr

前两行从指向状态（%state）的指针派生指向模拟eax和ebx寄存器（分别为%eax_addr和%ebx_addr）的内存指针。此派生使用getelementptr指令执行，等效于C代码&(state->eax)和&(state->ebx)。接下来的两行表示mov指令，其中模拟ebx寄存器被读取（加载），然后读取的值被写入（存储）到模拟eax寄存器。最后，最后三行表示add指令。

我们可以看到%ebx_0被存储到%eax_ptr，然后%eax_0从%eax_ptr加载，而没有任何干预存储到%eax_ptr指针。这意味着加载到%eax_0是冗余的。我们可以在任何使用%eax_0的地方简单地使用%ebx_0，即向前传递存储到加载。

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

这个过程将在真实的bitcode中继续，直到没有更多可以向前传递或杀死的指令。

现在您了解了死存储消除的工作原理，让我们探索如何将这种技术教给计算机。

事实证明，上述每个步骤都与数据流分析相关。为了构建我们的消除器，我们将需要弄清楚如何使用数据流技术来表示这些决策。

构建消除器

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

玩转槽位

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

偏移量	槽位
0	eax
4	ebx

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

它们是槽位伙伴！

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

为了识别别名的指令，我们使用ForwardAliasVisitor（FAV）。FAV在两个各自的映射中跟踪所有指向状态结构偏移的指针以及所有涉及访问状态结构的指令。顾名思义，它向前遍历给定的指令，如果注意到它跟踪的地址之一已被修改或使用，则保持计数。

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

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

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

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

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

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

您马上就会死掉

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

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

活跃和设置活跃

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

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

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

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

不要向前，但是……

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

在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将为每个访问的函数生成三个图，显示识别的偏移量、标记为移除的存储以及移除后的指令。

生成显示消除指令的DOT图

仍然渴望优化？

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

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

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

如果您喜欢这篇文章，请分享： Twitter LinkedIn GitHub Mastodon Hacker News

页面内容提升时会发生什么构建消除器玩转槽位它们是槽位伙伴！您马上就会死掉 DSE饮食见证仍然渴望优化？最近的帖子构建安全消息传递很难：对Bitchat安全辩论的 nuanced 看法使用Deptective调查您的依赖项系好安全带，Buttercup，AIxCC的评分回合正在进行中！使您的智能合约超越私钥风险成熟 Go解析器中意想不到的安全陷阱 © 2025 Trail of Bits。使用Hugo和Mainroad主题生成。