高效的云端确定性仿真

TL;DR：Antithesis 使用自定义的确定性虚拟机监控器和基于快照的写时复制（COW）技术，结合子树去重，在云端对完整系统进行大规模、可重复的模糊测试。 ## 背景：我们在做什么 我是 Alex Pishkin，Antithesis 的工程师。我们专注于自动化端到端软件测试——我们喜欢制造 P99 事件来发现有趣的 Bug。可以想象成策划一场大型车祸，然后观察你的软件在最不寻常的情况下如何表现。 我们的领域是确定性模拟测试和模糊测试。确定性模拟意味着将任何测试（例如集成测试）放入一个模拟环境中运行，你可以完全控制网络、磁盘和其他组件。你可以人为地注入故障，速度比现实快得多，并且能获得这些故障的干净日志——这些故障在正常情况下是不可见的。确定性增加了可重复性和一致性，因此你可以破坏性地探索一个 Bug 状态，并无限重现它。 我们的方法深受模糊测试启发，但侧重于“全系统测试”——大规模网络事件、并发、多层面故障注入。这就产生了一个问题：输入是什么？构成特定系统状态所需的状态是什么？我们的解决方案是将所有内容放入一个确定性虚拟机中。 ## 确定性虚拟机监控器 我们构建了自己的确定性虚拟机监控器。关键是要消除非确定性，这些非确定性通常来自一致性操作的不一致副作用——缓存未命中、分支预测、时序。我们伪造了时间。 我们做了必要的简化假设： - 仅针对一种架构（云端可用的大型 CPU 栈）。 - 每个虚拟机只有一个物理核心。这消除了一整类并发问题；我们仍然使用系统模拟器模拟许多并发 Bug。这也很好地契合了模糊测试模型——并行探索没问题，它是令人尴尬的并行化。 - 我们只使用极少数真实设备和 I/O 子集——因为我们模拟它们。如果 CPU 是确定性的，那么让网络和磁盘也变得确定性的问题就已经解决了。 ## 性能：快照挑战 性能至关重要。硬件虚拟化（例如嵌套页表、扩展页表）为我们免费提供了写时复制：通过在二级页表中将所有内容标记为只读，任何写入都会触发虚拟机监控器的故障，从而执行 COW。但快照会占用大量内存：每个虚拟机使用 10–30 GB，并且我们会创建许多快照。 我们的“多元宇宙调试”方法创建了一个快照树（历史树）。COW 自然形成了一棵树，其中每个快照都是其父快照的差异。但这没有考虑兄弟快照中的相同数据——不同的执行路径仍然可以共享大量数据。删除快照变成了一个混乱的继承问题。 ## 子树去重 我们不在页面级别进行去重，而是在**子树**级别进行去重。页表本身就是树结构；程序数据、指令和堆倾向于局部性。通过引用计数整个子树，我们避免了在页面级别去重时更新数百万个引用计数。成本变为与**变更集大小**（例如 10 KB 的变化）成 O(n) 关系，而不是与总内存大小成 O(n) 关系。 具体来说： - 页表是一个多级树，将地址映射到物理位置。 - 当我们拍摄快照时，我们会保留一个脏页列表（差异集）。对于每个子树，如果该子树中没有变化，我们只需增加整个子树的引用计数——无需复制或对单个叶子页面进行引用计数。 - 这大大减少了每个快照的开销，使得大规模并行模糊测试变得可行。 ## 结论 Antithesis 的方法结合了自定义的确定性虚拟机监控器和通过子树去重实现的高效快照技术，使我们能够在云规模上对复杂的真实世界系统进行模糊测试。关键教训是：**以数据结构的粒度工作**——在本例中是指页表子树——以保持引用计数成本与变更集成正比，而不是与总内存成正比。 来源：视频（https://youtu.be/DF3nGDi2-dc）