这篇文章将介绍切片表达式(slicing expression)和部分控制流图(Control Flow Graph, CFG)的概念，将它们结合起来实现一个 SMT 驱动的算法来探索虚拟化的 CFG。最后，还将花一些时间介绍 LLVM 优化管道以及它的配置和使用过程中的局限性。

切片器（slicer）

对符号表达式进行切片以对其进行评估、将其发送给 SMT 求解器或将其与某种模式匹配，这在所有符号推理工具中都极为常见。幸运的是，使用另一个 C++ 辅助函数来实现这个功能是微不足道的。在 VMProtect 环境中，我们主要对切片程序计数器感兴趣。我们想要在探索单个 VmBlocks（一旦连接，形成 VmStub）或在探索 VmStubs（一旦连接，形成 VmFunction）时这样做。以下 C++ 代码旨在仅保留与 VmBlock 或 VmStub 末尾的虚拟指令指针的最终值相关的计算：

敏锐的观察者可能会注意到函数定义与之前给出的 HelperFunction 定义基本相同，基本区别在于参数按值传递，因此如果与切片表达式的计算有关，则很有用。

使用上述辅助函数的步骤是：

◼HelperSlicePC 被复制到一个新的抛弃型(Throwaway) 函数中；

◼对 HelperStub 函数的调用与对我们想要切片最终指令指针的 VmBlock 或 VmStub 的调用交换；

◼被调用的函数被强制内联到 HelperSlicePC 函数中；

◼优化管道在复制的 HelperSlicePC 函数上执行，导致作为优化副作用的最终指令指针表达式的切片。

下面的 LLVM-IR 片段展示了这个想法的实际效果，最终得到优化的函数，其中条件分支的条件和边缘都清晰可见。

接下来，我们将探索如何使用这种技术的变体来探索虚拟化控制流图、解决条件分支和恢复切换案例。

虚拟化控制流图的探索可以通过不同的方式完成，通常像VMProtect或Themida这样的保护程序会显示一个独特的形状，可以轻松地进行模式匹配、简化和解析，以获得条件块的出边。

不同VMProtect条件跳转版本使用的逻辑在前面已经讲过了，所以接下来我们将深入研究基于探索的控制流图的增量构建。

鉴于详细算法的通用性质，没有什么能阻止它在其他保护程序上使用。通常的问题显然是由嵌入难以解决的约束的保护引起的，这些约束可能会阻碍自动求解阶段，但部分 CFG 约束和表达式的构建和传播在实践中仍然有用，以拉出自动化程度较低的探索算法，或识别并简化反动态符号执行技巧，例如，导致路径爆炸的虚拟循环可以通过 LLVM 的循环优化传递或自定义用户传递来简化。

部分CFG

部分控制流图是在给定已知边的情况下连接当前探索的基本块的控制流图。构建它背后的想法是，每次我们探索一个新的基本块都可能导致一些新的基本块，甚至是已知的基本块。因此，两个块之间的每条新边界都向整个控制流图添加信息，我们实际上可以传播新的有用约束和值以实现更强大的优化，可能简化条件分支的求解，甚至将已知分支从无条件改为有条件。

接下来我会讲解两个示例，说明为什么构建部分 CFG 可能是一个好主意，因为这可以复制通常由符号执行工具实现的推理类型，并添加有用的内置LLVM通道。

示例1

考虑下面的部分控制流图，其中蓝色表示刚刚处理过的VmBlock，橙色表示未处理的VmBlock，紫色表示示例中感兴趣的VmBlock。

假设我们刚刚解决了基本块 A 的输出边界，获得了通向新基本块 B 和 C 的两个连接。 现在假设我们对唯一基本块 B 的分支条件进行切片，获得对常量数组的访问64 位符号索引。枚举所有有效索引可能不是一项简单的任务，因此我们可能希望使用符号索引上的已知约束来限制搜索，如果存在，这些约束很可能来自前驱链基本块 B。为了绘制一个符号执行并行，我们需要从一定数量的原有内容中收集路径约束的情况，例如，我们可能想要增量地获取约束，因为有时所需的约束在我们正在求解的基本块附近，并将它们链接起来，以提供给SMT求解器，执行有效索引的成功枚举。

像 Souper 这样的工具在切片表达式时会自动收集路径约束集，因此构建部分控制流图并将其提供给 Souper 可能足以完成任务。此外，使用 LLVM API 来遍历基本块的原有内容，也很容易获得所需的约束集，并且我们还可以利用LLVM提供的已知的真实条件。

示例2

考虑下面的部分控制流图，其中蓝色代表刚刚处理过的 VmBlock，橙色代表未处理的 VmBlock，紫色代表示例中感兴趣的 VmBlock，红色虚线箭头表示示例中边，实线绿色箭头表示边刚刚处理过的。

假设我们刚刚解决了基本块 E 的输出边界，获得了通向新块 G 和已知块 B 的两个连接。那就可以知道我们检测到了到先前访问过的块 B（绿色边）的跳转，这基本上形成了一个循环链（B→C→E→B），从B开始，我们可以到达目前已知为无条件的两条边（B→C和D→F，用红色虚线标记），但是，鉴于新获得的边 E → B，可能不再存在，因此需要再次证明。构建一个新的部分控制流图，包括所有新发现的基本块连接，并对块 B 和 D 的分支进行切片，现在可以将它们显示为有条件的。

在实践中，当处理conconic执行方法时，上面提到的是基于索引的循环的常见模式，从已知的具体索引开始运行，直到索引达到上限或下限N。在第一次执行N-1次时，工具将采用相同的路径，只有在迭代N时，才会探索其他路径。这就是为什么concolic和符号执行工具试图构建启发式或使用状态合并等技术来避免遇到路径爆炸问题或最多执行循环N次的原因。

相反，使用 LLVM 构建部分 CFG 会将第一次循环返回边缘标记为无条件，但再次构建它，包括新发现的后边缘的知识，将立即揭示循环模式。结果是 LLVM 现在将能够应用其循环分析传递，用户将能够使用API来构建特别的LoopPass传递来处理应用于循环组件的特殊混淆(例如，编码循环变量/不变变量)或SMT求解器将能够将合并点上新创建的Phi节点视为符号变量。

下面的LLVM-IR片段显示了在探索下面展示的虚拟化组装片段期间获得的切片部分控制流图。

FirstSlice函数显示已经检测到一个无条件分支，标识字节码地址0x1400B85C1(5369464257)，这是因为不知道后边界，比较结果为 cmp 1, 2000。 SecondSlice 函数显示有条件的分支检测到在字节码地址 0x140073BE7 (5369183207) 和 0x1400B85C1 (5369464257) 之间进行选择的分支。现在使用符号 PHINode 完成比较。 F_0x14000101f_WithLoopOpt 和 F_0x14000101f_NoLoopOpt 函数显示了应用和未应用循环优化的完全去虚拟化代码。

伪代码

部分 CFG伪代码如下：

1. 初始化算法创建：

2.我们将入口VmBlock的地址推入Worklist；

3.我们获取要探索的 VmBlock 的地址，如果第一次遇到，我们将其提升到 LLVM-IR，使用来自 Edges 映射的知识构建部分 CFG，然后我们对当前 VmBlock 的分支条件进行切片。最后，我们将分支条件提供给 Souper，Souper 将处理表达式，收集所需的约束并将其转换为 SMT 查询。然后，我们可以将查询发送到 SMT 求解器，询问有效的解决方案，逐步拒绝已知解决方案直至达到某个限制或直到找到所有解决方案。

4.一旦我们获得了当前 VmBlock 的输出边，就可以继续更新映射和集合：

4.1我们验证每个求解的边是否通向一个已知的 VmBlock，如果是，我们就会确认这一联系之前是否为人所知。如果未知，则意味着我们找到了已知 VmBlock 的新前身，然后我们继续将已知 VmBlock 可访问的所有 VmBlock 的地址添加到 Reprove 集并将它们从探索集中删除，为了加快速度，我们最终可以无条件跳过每个VmBlock。

4.2我们用新解决的边更新Edges映射。

此时我们检查 Worklist 是否为空。如果不是，我们跳回第 3 步。如果是，我们用 Reprove 集中的所有地址填充它，在这个过程中清除它并跳回第 3 步。如果 Reprove 集也是空的，它意味着我们探索了整个CFG，并最终在探索阶段对所有获得新原有内容的VmBlocks进行验证。

如本节开头所述，探索虚拟化 CFG 的方法有很多，使用 SMT 驱动的解决方案可以概括大部分步骤。显然，这也带来了一系列新问题（例如难以解决的约束），因此人们最终可以在需要时退回到基于模式匹配的解决方案。正如预期的那样，基于模式匹配的解决方案有时也会盲目地探索不可达的路径，因此混合解决方案确实可以提供最佳的 CFG 覆盖。

本节中提供的伪代码是 SATURN 目前使用的基于部分 CFG 的探索算法的简化版本，简化了在探索由 VMProtect 虚拟化的 CFG 时不必要的一组推理。

管道

到目前为止，我们已经多次介绍了LLVM的优化和分析的底层用法，现在就让我们看看它们的配置和局限性。

管理管道

运行整个 -O3 管道可能并不总是最好的主意，因为我们可能只想使用它的一个子集，此外，默认情况下，LLVM 提供了一个执行一次的优化链，旨在优化非混淆代码。

我们的要求如下：

1.添加一些自定义通道来解决特定于上下文的问题，并在管道中的精确点执行此操作以获得最佳输出，同时避免相位排序问题；

2.多次迭代优化管道，直到我们的自定义通道不能对IR代码应用任何更改；

3.能够向管道传递自定义标志，以便随意切换一些通道，并最终为它们提供从二进制文件中获得的信息，例如访问二进制文件部分。

LLVM 提供了一个 FunctionPassManager 类来自定义管道，使用 LLVM 的通道和自定义通道。下面的c++代码片段展示了我们如何添加一个混合的通道，这些通道将按顺序执行，直到不再有任何更改或达到阈值为止：

OptimizationGuide结构可以用来将信息传递给自定义通道，并控制管道的执行

配置

如前所述，LLVM默认管道意味着尽可能高效，因此它在配置时考虑了效率和效能之间的权衡。在对大函数进行去虚拟化时，看到默认使用的更严格配置的影响并不少见。

在Godbolt UI中，我们可以在左边看到一个LLVM-IR代码片段，该代码将 i32 值存储在名为 arr 的全局数组的递增索引处。第96行的store在arr[1]处写了值91，这有点特殊，因为它完全覆盖了第6行的store，在arr[1]处写了值1。如果我们查看右上角的结果，就会看到应用了DSE通道，但不知为什么它没有在第6行删除失效store。如果我们查看右下方的结果，就会看到DSE通道设法实现了它的目标，并在第 6 行成功阻止了失效store。 产生这种差异的原因完全与DSE通道的保守配置有关，默认情况下，在确定一个store没有阻止另一个后主导store之前，将估计多达90个MemorySSA定义。将memoryssaupwardsstepllimit设置为一个更高的值(例如示例中的100)，这肯定是我们在消除一些代码混淆时想要做的事情。

我们要添加到自定义管道的每个通道都可能会提供次优反混淆结果的配置，因此检查它们的 C++ 实现并确定调整某些选项是否可以改善输出是一个好主意。

当调整一些配置没有给出预期的结果时，我们可能需要更深入地研究一下通道的实现，以了解是否有什么阻碍了它的工作，下面是一些关于为什么深入研究通道实现可能会导致带来卓有成效的改进的示例。

IsGuaranteedLoopInvariant (DSE, MSSA)

在查看一些非虚拟化代码时，我注意到即使启用了调整后的配置，一些明显已经失效的存储并没有被 DSE 删除。原因是IsGuarenteedLoopInvariant函数使用的内镜下动态慢动作影像MSSA传递并没有使用一个指针的安全假设计算块的条目。

GetPointerBaseWithConstantOffset (DSE)

在查看一些访问不同大小内存插槽的非虚拟化代码时，我注意到一些明显已经失效的存储并没有被 DSE 删除，即使启用了调整后的配置。原因是，在计算部分重叠的内存存储时，DSE只考虑具有相同基址的内存插槽，而忽略了完全重叠的相互偏移的存储。解决方案是使用另一个补丁，它提供关于内存插槽偏移量的信息：D93529。

本文翻译自：https://secret.club/2021/09/08/vmprotect-llvm-lifting-2.html如若转载，请注明原文地址