确定性记录与回放

专注于进程的非确定性行为

Andrew Quinn，Peter Alvaro 引言

实践研究结合了数字图书馆（世界上最大的计算机科学研究集合）的资源和会员的专业知识。“实践研究”专栏的共同目标是分享阅读计算机科学研究的乐趣和实用性，这些研究在学术界人士和他们在业界的同行之间交流。

今年夏季的“实践研究”栏目涵盖了一个虽然成熟但仍在不断产生前沿研究的主题：确定性记录与回放。确定性记录与回放技术能够忠实地重新执行（回放）过去运行的程序（并且可能遇到了罕见的错误、性能异常或来自对手的入侵）。但这需要记录（记录）程序执行期间的所有非确定性输入。

此处介绍的技术选择由加州大学圣克鲁兹分校计算机科学与工程系助理教授 Andrew Quinn 策划。我们选择这个主题是因为它与我们的从业者受众越来越相关，我们选择 Quinn 教授是因为他在该领域的专业知识。他在此处的选择都来自顶级计算机科学会议的最新出版物，它们涵盖了从提供记录与回放的核心技术到稍微更具异国情调的应用等一系列主题。它们揭示了这项技术在各个领域应用的广泛性，以及即使记录与回放已经是一个活跃的研究领域很长时间，它仍然有多么热门。

Quinn 教授的摘要非常详细，所以我将保持我的简短。他的第一个选择名为 RR，它提供了一个绝佳的机会，让您通过一个“最大化可部署性”的系统来入门，该系统利用任何现代系统上可用的硬件和软件功能，开箱即用。

第二篇论文（刚刚在 2024 年发表）使用记录与回放技术不是为了按原样重新执行程序，而是为了解决轻量级审计问题——例如，确保云提供商确实在运行您提交的程序，而无需求助于提供商提供的大量计算资源。

最后，他分享了一篇论文，该论文创造性地将记录与回放的思想应用于一个看似不相关的领域：通过将新输入上的每次执行视为规范执行的“回放”，来保护移动设备上的 GPU 计算。

我想不出有什么比花一个周末下午阅读这三篇论文以及 Quinn 教授的专家总结更好的方式了。

—Peter Alvaro

实践研究：确定性记录与回放

Andrew Quinn

确定性记录与回放是一种允许用户记录程序执行，然后在稍后时间回放完全相同执行的技术。可以将其视为计算机上进程的 TiVo。研究人员创建了数百个在许多领域中使用确定性记录与回放的系统。例如，安全取证系统（例如，Backtracker⁵）使用记录与回放来确定安全漏洞期间泄露了哪些数据，而基于回放的调试器（例如，Instant Replay⁶）使用记录与回放来调试罕见的生产问题和海森堡 bug（一旦您观察到它们就会消失的 bug）。

确定性记录与回放的关键挑战在于，进程会产生大量执行状态，远远超过可以捕获和存储的量。为了说明这一点，让我们对进程的指令序列的大小进行粗略计算，指令序列是必须为记录与回放编码的信息的子集。假设每个指令指针为 8 个字节，进程是单线程的并且执行 10 分钟，并且系统使用 2GHz 处理器。在这种情况下，指令序列将需要 1.2TB 的存储空间。想象一下对所有工作负载执行此操作的存储需求，这些工作负载执行时间更长、具有更多线程并使用更快的进程。

实现确定性记录与回放的关键见解是，进程大多数操作都是确定性的——这意味着它们的行为完全取决于进程的当前状态。因此，确定性记录与回放系统可以避免存储大多数执行状态，而只存储有关进程的非确定性操作的信息。在记录期间，此类系统将传递给进程的非确定性输入（例如，从网络读取的字节）存储到日志中；在回放期间，系统然后使用日志中的值重新执行进程以重新创建执行状态。

本专栏描述了三个使用确定性记录与回放的最新研究成果，重点介绍了该技术的多样化用例。

易于部署的记录与回放

Robert O'Callahan、Chris Jones、Nathan Froyd、Kyle Huey、Albert Noll 和 Nimrod Partush。
为可部署性工程记录和回放。
Usenix 年度技术会议论文集, 2017.
https://www.usenix.org/conference/atc17/technical-sessions/presentation/ocallahan

这个名为 RR 的系统，您现在可能可以将其添加到您的工程工作流程中，因为它是一个易于部署的记录与回放调试器。该系统的关键创新在于它在非特权用户空间实现上执行记录与回放，该实现支持在标准 Linux 内核、编译器、语言运行时和标准 x86/x86-64 CPU 上未修改的用户空间应用程序。RR 甚至支持存在错误的程序，例如数据竞争，这一直是过去记录与回放系统的主要问题来源。RR 也是一个开源系统，如果您还没有机会，您应该构建并摆弄它。

RR 的工作原理是建立在最初用于传统调试和性能分析的软件和硬件功能之上。它使用 ptrace，ptrace 旨在实现捕获系统调用结果和信号的软件调试器（例如，gdb）。该系统通过引入进程内系统调用交叉来加速 ptrace 的性能，这是一种选择性抑制 ptrace 陷阱从而最小化上下文切换的技术，使用 seccomp-bpf（安全计算-伯克利包过滤器）。RR 一次只执行一个线程以避免非确定性数据竞争，并且它使用 CPU 硬件性能计数器（最初为性能分析而设计）来测量应用程序进度，以便它可以在程序中的正确点传递信号并执行上下文切换。此评估表明该系统是否满足作为调试器定期使用的合理计算、内存和存储要求。

审计事件驱动的 Web 应用程序

Ioanna Tzialla、Jeffery Wang、Jingyi Zhu、Aurojit Panda 和 Michael Walfish。
事件驱动的 Web 应用程序的高效审计。
在第 19 届欧洲计算机系统会议 (EuroSys) 论文集中。2024
https://dl.acm.org/doi/10.1145/3627703.3650089

假设您在远程云机器上部署了一个 Web 服务器。您如何确定该机器实际上正在执行您的 Web 服务器？这使我们想到了第二个感兴趣的系统：Karousos，它使用记录与回放的变体来回答关于您的 Web 服务器运行状况的问题，研究人员将其称为“执行完整性”。具体而言，Karousos 提供了一种解决方案，使主体（即您）确信在给定输入（用户请求）上运行给定程序（您的 Web 服务器）实际上会产生从第三方机器（远程云机器）观察到的所谓输出（用户响应）。

Karousos 使用了 Orochi⁷ 的模型，即受信任的收集器机器捕获程序的所有输入和输出，而验证器重新执行跟踪中的输入以检查重新执行的输出是否与跟踪匹配。该模型通过批量重新执行请求来加速该过程，使用不受信任的机器产生的不受信任的建议，该建议由程序执行的一些非确定性操作组成。

Karousos 专门针对事件驱动的 Web 应用程序，而先前的工作对这些应用程序的支持较差。该系统的主要贡献围绕平衡重新执行吞吐量和建议大小之间权衡的技术。该技术和分析非常深入，超出了本专栏的范围。因此，我鼓励有兴趣的读者深入研究这篇论文。（我保证您会学到一些东西！）

最后，Karousos 的重新执行本质上是确定性记录与回放，但有两个关键注意事项。首先，它的重新执行旨在比记录的执行需要更少的计算；否则，首先使用云就没有意义了。其次，确定性记录与回放假设非确定性事件的日志是正确的，而 Karousos 针对的是第三方恶意构建建议的场景。

GPUReplay 用于客户端 ML

Heejin Park 和 Felix Xiaozhu Lin。
GPUReplay：用于客户端 ML 的 50-KB GPU 堆栈。
第 27 届编程语言和操作系统架构支持国际会议 (ASPLOS) 论文集, 2022.
https://dl.acm.org/doi/10.1145/3503222.3507754

假设您设计和维护一个移动应用程序，该应用程序使用 GPU 来加速机器学习 (ML) 组件。此外，假设此应用程序在 GPU 堆栈上执行，该堆栈由 ML 框架（例如，TensorFlow）、运行时（例如，OpenCL）和 GPU 驱动程序组成。GPU 堆栈共同将您程序的高级语言定义转换为低级 GPU 命令并将它们放置在 GPU 上。不幸的是，这些复杂的堆栈带来了三个主要问题：安全性弱、部署困难和启动缓慢。

GPUReplay 使用确定性记录与回放来改善这种状况。在开发时，它执行您的 ML 应用程序并记录 GPU 堆栈执行。执行编码了 GPU 堆栈如何与 GPU 交互以初始化每次执行。在部署时，GPUReplay 通过在给定新输入数据时调用记录的 GPU 堆栈执行来执行您的 ML 应用程序。在这样做时，它需要处理记录的执行和回放的执行之间可能出现的非确定性，它通过允许不影响程序输出的非确定性（例如，时序变化）、从一开始就防止非确定性发生或检测非确定性并尝试重新执行来做到这一点。作者表明，GPUReplay 消除了部署中发生的大量高影响 CVE（通用漏洞和暴露），并验证了回放的执行确实是正确的。

总结

本专栏描述了与确定性记录与回放相关的三项最新研究进展，旨在展示经典用例（基于回放的调试）和新兴用例（执行完整性和 GPU 加速）。越来越多的系统使用较弱形式的确定性记录与回放（我称之为“大部分确定性”记录与回放）。本质上，这些系统利用许多程序执行中存在的确定性，但出于性能原因有意允许一些非确定性。这种趋势在 GPUReplay 中尤为突出，但在 ShortCut⁴ 和 Dora⁸ 等系统中也很明显。

有关确定性记录与回放的更多信息，我建议查阅任何关于该主题的详细调查报告。^1,2,3

参考文献

1. Chen, Y., Zhang, S., Guo, Q., Li, L., Wu, R., Chen, T. 2015. 确定性回放：一项调查。 Computing Surveys 48(2); https://dl.acm.org/doi/10.1145/2790077。

2. Cornelis, F., Georges, A., Christiaens, M., Ronsse, M., Ghesquiere, T., De Bosschere, K. 2003. 执行回放系统分类法。在电子商业、教育、科学、医学和移动互联网技术基础设施进展国际会议中； https://www.researchgate.net/publication/244149898_A_Taxonomy_of_Execution_Replay_Systems。

3. Dionne, C., Feeley, M., Desbiens, J. 1996. 基于执行回放的分布式调试器分类法。在并行和分布式处理技术国际会议 (PDPTA) 论文集中； http://www.iro.umontreal.ca/~feeley/papers/DionneFeeleyDesbiensPDPTA96.pdf。

4. Dou, X., Chen, P. M., Flinn, J. 2019. ShortCut：加速大部分确定性代码区域。在第 27 届操作系统原理研讨会论文集中，570–585； https://dl.acm.org/doi/10.1145/3341301.3359659。

5. King, S. T., Chen, P. M. 2003. 回溯入侵。在第 19 届操作系统原理研讨会论文集中，223–236； https://dl.acm.org/doi/10.1145/945445.945467。

6. Leblanc, T. J., Mellor-Crummey, J. M. 1987. 使用 Instant Replay 调试并行程序。IEEE Transactions on Computers C-36 (4), 471–482; https://dl.acm.org/doi/abs/10.1109/TC.1987.1676929。

7. Tan, C., Yu, L., Leners, J. B., Walfish, M. 2017. 高效服务器审计问题、重复数据删除重新执行和 Web。在第 26 届操作系统原理研讨会论文集中，546–564； https://dl.acm.org/doi/10.1145/3132747.3132760。

8. Viennot, N., Nair, S., Nieh, J. 2013. 用于多核调试和补丁验证的透明可变回放。在第 18 届编程语言和操作系统架构支持国际会议 (ASPLOS) 论文集中； https://dl.acm.org/doi/10.1145/2499368.2451130。

Peter Alvaro 是加州大学圣克鲁兹分校的计算机科学副教授，在那里他领导着 Disorderly Labs 研究小组 (disorderlylabs.github.io)。他的研究重点是使用以数据为中心的语言和分析技术来构建和推理数据密集型分布式系统，以便使它们可扩展、可预测且对大规模分布固有的故障和非确定性具有鲁棒性。他在加州大学伯克利分校获得博士学位，师从 Joseph M. Hellerstein。他是国家科学基金会职业奖、Facebook 研究奖、Usenix ATC 2020 最佳演示奖、SIGMOD 2021 杰出 PC 奖和 UCSC 卓越教学奖的获得者。

Andrew Quinn 是加州大学圣克鲁兹分校的助理教授。他们的工作领域是操作系统、编程语言和计算机体系结构的交叉点。Andrew 的工作曾获得 ASPLOS 最佳论文奖、IEEE Micro 最佳选择荣誉奖、微软奖学金、NSF GRFP 奖学金以及在这些领域的顶级场所发表的多篇出版物。

最初发表于 Queue vol. 22, no. 4—
在数字图书馆中评论本文

更多相关文章

Charisma Chan, Beth Cooper - 调试 Google 分布式系统中的事件
本文介绍了 2019 年对 Google 工程师如何调试生产问题进行的研究成果，包括工程师以不同组合有效调试所使用的工具类型、高级策略和低级任务。它检查了用于捕获数据的研究方法，总结了生产调查的常见工程历程，并分享了专家如何调试复杂分布式系统的示例。最后，本文将这项研究的 Google 特性扩展到提供一些您可以在组织中应用的实用策略。

Devon H. O'Dell - 调试心态
软件开发人员花费 35-50% 的时间来验证和调试软件。调试、测试和验证的成本估计占软件开发项目总预算的 50-75%，每年超过 1000 亿美元。虽然工具、语言和环境减少了个人调试任务所花费的时间，但它们并未显着减少调试的总时间，也未减少调试的成本。因此，过度关注开发期间消除 bug 是适得其反的；程序员应该将调试视为一种解决问题的练习。

Peter Phillips - 使用跟踪增强调试
创建一个模拟器来运行旧程序是一项艰巨的任务。您需要彻底了解目标硬件和模拟器要执行的原始程序的正确功能。除了功能正确之外，模拟器还必须达到以原始实时速度运行程序的性能目标。实现这些目标不可避免地需要大量的调试。这些 bug 通常是模拟器本身中的细微错误，但也可能是对目标硬件的误解或原始程序中实际已知的 bug。（原始程序的二进制数据也可能已受到细微损坏或不是预期的版本。）

Queue Readers - 又一天，又一个 Bug
作为本期关于程序员工具的一部分，我们在 Queue 决定就调试主题进行一次非正式的网络调查。我们请您告诉我们您使用的工具以及您如何使用它们。我们还收集了关于那些难以追踪的 bug 的故事，这些 bug 有时会让我们想到从事其他职业。