Hermit：用于受控测试和软件漏洞查找的确定性 Linux 系统
如果您使用过较旧平台的仿真器，则可能体验过我们在现代平台上所缺乏的对软件执行的精确控制程度。例如，如果使用现代游戏机在仿真环境下玩 8 位电子游戏，您可以暂停游戏和回档，并且在恢复游戏时，即将出现的生物或炮弹会按预期出现在相同的地方，这是因为在仿真器中所有随机性内容都能以确定性方式呈现出来。
然而，当多线程服务在瞬变情况下崩溃时，或者当测试不稳定时，软件工程师没有条件实现这些功能。从线程调度、随机数、虚拟内存地址到唯一标识符，处理器和操作系统为运行程序提供的所有数据构成了不可重复的唯一隐式输入集。标准测试驱动方法可控制 显式 程序输入，但并不会尝试控制这些隐式输入。
自 2020 年起，我们 DevInfra 团队一直致力于从根源解决此难题：应用程序与操作系统之间的接口普遍存在不确定性。我们构建了第一个实用的 确定性操作系统， 并将其命名为 Hermit（请参阅有关现有技术的尾注）。Hermit 不是新内核，而是基于 Linux 内核的仿真层。与 Wine 将 Windows 系统调用转换为 POSIX 调用的方式相同，Hermit 可拦截系统调用并将它们从确定性 Linux 抽象转换为基础 Vanilla Linux 操作系统的系统调用。
如需详细了解不确定性的根源和解决方案，请参阅白皮书“Reproducible Containers”（可复现的容器，发布于 2020 年 ASPLOS 大会），其中展示了我们系统的早期版本。我们已公开新 Hermit 系统和基础程序检测框架 Reverie 的源代码。
应用场景示例
现在我们探索一些 Hermit 的应用场景，以及[不]确定性的影响。在下一部分中，我们将深入探索 Hermit 的运作方式。
不稳定测试
首先是不稳定测试。这些是每家公司都会遇到的问题。Google、Apple、Microsoft 和 Meta 都发布过大量不稳定测试的经历。从根本上说，不稳定的原因是测试函数 真正 的签名并不是源代码中出现的签名。工程师可能认为他们正在测试一个输入类型和输出类型特定的函数，例如：
test : Fn(Input) -> Output;
诚然，如果不执行基于属性的测试，对于单元测试而言，此签名更简单。（输入为空，输出为布尔值。）遗憾的是，实际上，大多数测试可能受到系统状态和外部网络互动影响，因此测试函数 真正 的签名如下：
test : Fn(Input, ThreadSchedule, RNG, NetworkResponses) -> Output;
问题是其中大多数参数不受工程师控制。在主机设备上运行的测试工具和测试代码受操作系统和所有外部服务控制。
说明：操作系统中不可复现的隐式输入可影响测试结果。
因此，我们构建了 Hermit 系统。Hermit 的任务是创建容器化软件环境，每个隐式输入（如上图所示）在此环境中都是可重复的容器状态或容器配置函数，包括命令行标记。例如，当应用程序请求时间时，我们提供的确定性时间只是一个程序进度函数。当应用程序线程 I/O 阻塞时，相对于其他线程，会在确定性时间恢复正常。
Hermit 可保证不管何时何地，自身（不使用外部网络）运行的所有程序均采用一致的运行方式，从而生成一致的指令流，并在各指令执行时确定内存状态。这意味着，如果在 Hermit 系统下运行无网络回归测试，则可保证测试稳定：
hermit run ./testprog
而且，使用 Hermit，不仅可探索程序的 单个 可重复执行，还可系统性地浏览可能发生的执行情况。我们看看如何控制一种特定功能：伪随机数生成 (PRNG)。当然，为保证确定性，当应用程序在操作系统中请求随机字节时，我们提供可重复的伪随机字节。要使用 不同的 PRNG 种子运行程序，只需使用不同的 --rng-seed 参数：
hermit run --rng-seed=1 prog hermit run --rng-seed=2 prog
在此情况下，使用什么语言编写 prog 或使用什么随机数生成器资源库并不重要，最后必须请求操作系统提供 entropy ，此时该函数将用于接收可重复的伪随机输入。
线程调度也如此：Hermit 使用命令行种子控制线程交错。Hermit 的独特之处在于能够为完整的 Linux 程序可复现地生成调度，而不仅仅是记录实际发生的调度。此系统通过确定的随机化策略生成调度，旨在训练并发漏洞。此外，该系统还可以输入文件形式显式传入全部线程调度，这些调度可通过获取和修改之前运行的调度进行派生。我们将在下一个部分讨论此问题。
总结而言，就是让所有隐性影响变得清楚明确。处理不稳定程序的工程师可按预期控制运行，实现以下目标：
- 回归测试：通过设置使测试通过。
- 压力测试：随机化设置，以提高查找漏洞的效率。
- 诊断：系统性改变输入，以查找导致不稳定的隐式输入。
确定一般类并发漏洞
如上文所述，我们可改变输入以查找触发失败的事件，并且可直接控制调度。依托于这些基本功能，Hermit 可分析并发漏洞，并确定根本原因。首先，与 rr chaos 模式一样，Hermit 可搜索随机调度。在 Hermit 发现未通过和通过的调度后，可进一步分析这些调度，以确定 关键事件 对（即并行运行且改变事件顺序会导致程序失败的那些事件对）。这些漏洞有时被称为“违反执行顺序”或“争用条件”（包括但不限于数据争用）。
许多工程师使用争用检测器，比如 ThreadSanitizer 或 go run -race。但是，争用检测器通常需要编译时支持，采用特定语言设置，并且只用于检测 数据争用，特别是内存（而非文件、管道等）数据争用。以 Python 编写的客户端程序连接到以 C++ 编写的服务器程序时存在争用怎么办，客户端在服务器绑定套接字之前连接到何处？此不确定性失败是“异步等待”不稳定类别的实例，如不稳定测试的实证分析和分类所定义。
通过以确定性操作系统抽象层为基础，我们可以直接改变调度，以实证方式查找那些关键事件，并输出其堆栈踪迹。先使用随机化调度方法在可能的调度空间中生成大量示例：
说明：不同 Hermit 种子生成的可能的线程调度的（指数）空间的可视化效果。此空间按编辑距离进行组织，最靠近的红点和绿点之间的距离是在测试通过和失败的调度之间观察到的最小编辑距离。
我们可将线程调度视为表示连续调度历史记录的字符串，以此组织此空间。例如，对于两个线程 A 和 B，“AABBA”可以是事件历史记录。两点之间的距离是字符串之间的编辑距离（实际上，计算加权编辑距离更偏好使用交换而非插入或删除操作）。我们可选取测试通过和失败的最靠近的调度对，然后进行深入研究。具体而言，我们可在这两个调度之间，沿最小编辑距离途径将其分为二等分，如下所示。
说明：测试通过和失败的两个调度之间的二分搜索，可探测这两个调度之间的各点，直至找到单次换位即可发生改变的相邻调度，它们之间的距离即 Damerau-Levenshtein 距离。
现在，我们已将漏洞定位到线程调度中的 相邻 事件，而交换其顺序即可决定是通过还是失败。我们进而报告这些事件的堆栈踪迹作为不稳定的原因。（事实上，这只是 一个 原因，如果不稳定是由多因素决定， 可能 存在其他原因。）
挑战及运作方式
现在我们将稍微介绍下 Hermit 运作方式，重点介绍与 2020 年 ASPLOS 大会中的原型不同的内容。二者的基本情况相同，我们都着手构建了一个 用户空间 确定性操作层，不允许自由修改 Linux 内核或使用任何特权指令。
挑战 1：干预操作系统与应用程序之间的操作
遗憾的是，Linux 中没有标准高效的全面方法可干预用户空间应用程序与操作系统之间的操作。因此，我们使用 Rust 构建了名为 Reverie 的全新程序沙盒测试框架，以抽象出后端运作方式，即程序沙盒测试实现方式。Reverie 可提供高级 Rust API 以注册 处理程序：针对所需事件的回调。用户可编写 Reverie 工具， 以观测访客事件和维护自己的状态。
Reverie 不只是适用于 观测 事件。在您编写 Reverie 处理程序时，也是在编写操作系统代码片段。这样，可拦截系统调用，并可 充当 操作系统，从而随意更新访客和工具状态，将零个或多个系统调用注入基础 Linux 操作系统，最后将控制权交还给访客。这些处理程序都是异步程序，并且都可在热门的 Rust tokio 框架上运行，在多个访客线程阻塞时它们彼此交错，然后继续运行。
提及的 Reverie 后端可使用 ptrace 系统调用拦截访客事件，并且更高级的后端可使用内存程序检测。实际上，Reverie 是唯一可抽象出检测代码是在中心位置（自己的进程）中运行还是通过注入代码 在 访客进程中运行的程序检测资源库。
挑战 2：线程间同步
下面来聊聊通过套接字和管道 在 可复现的容器中通信。在此领域中，我们早期的原型主要使用将拦截操作转换为非拦截操作的策略，然后在顺序执行中在确定性时间点进行轮询。由于是在用户空间运行，我们无法直接询问内核是否已完成特定拦截操作，因此尝试使用非拦截版的系统调用充当轮询机制。
Hermit 以此策略为基础，加入了确定线程优先顺序的完善调度程序，以及多个随机化设置，以便通过代码探索“chaos 模式”方法。此调度程序实施后退策略轮询操作，以提高效率。
除了轮询机制以外，Hermit 还完全在 Hermit 内进行某些线程间通信。通过加入内置 futex 实现等功能，Hermit 的行为方式更像操作系统内核。但是 Hermit 仍比 Linux 简单得多，并会将大多数繁重任务交给 Linux 本身。
对于 Hermit 直接执行的特定功能，它不会将那些系统调用传递给 Linux。例如，在使用 futex 时，很难或无法将一系列原始 futex 系统调用发送给内核，取得确定性结果。微妙之处包括伪唤醒（futex 值没有更改）、对要唤醒的线程的不确定选择，以及在 Hermit 向 Linux 发出拦截系统调用之后且在我们确信 Linux 已对其执行相关操作之前不可磨灭的瞬间。
如果以确定性方式精确拦截各 futex 调用并更新 Hermit 调度程序的状态，完全可避免这些问题。基础 Linux 调用程序仍可运行一切线程，但 Hermit 自己的调用程序可优先决定接下来要取消拦截的线程。
挑战 3：复杂的大型二进制文件
Meta 极具挑战性的大型二进制文件需使用 Linux 内核的最新功能。但是，随着这几年的不断开发，Hermit 如今可以确定性方式运行上千种不同的程序。其中包括我们运行时使用的 90％ 以上的测试二进制文件。
其他应用场景
不稳定测试和并发漏洞是我们主要投资的项目，除此之外，我们将在下方简单介绍一些其他应用场景：
Reproducible Builds：属于安全软件供应链的一部分，消除了对信任二进制包及其服务器的需求。我们早期的原型可用于实现此目的，此原型是在 2019 年 Reproducible Builds 峰会上推出的。
复制状态机：在分布式系统中提供容错功能，并且需要保证确定性。可提供完全抽象出机器故障的微服务框架，但前提是可 确保 或 假设确定性。
智能合约：通常以受确定性约束的专业语言编写。使用可复现容器，可运行“链上合约”传统软件，并且同样可确保分布式可复制性。
我们自己无法探索所有的应用场景！因此，我们很高兴向整个社群公开这些可能实现的应用场景。
结论
对于调试、可审核性以及上述其他应用场景而言，软件的可重复执行性是一项重要功能。但是，此功能在我们大家依赖的技术堆栈中被视为开发后期的补救措施，开发者需负责创建“足够好”的可重复性才能生成稳定测试或可复现漏洞报告。
作为可复现容器，Hermit 有助于我们了解系统堆栈 以抽象方式提供可重复性时的情形：保证开发者能够加以信赖，就像信赖内存隔离或类型安全一样。我们只简单概述了使用此基础技术可能实现的应用。希望您查看开源 GitHub 存储库，帮助我们应用和改进 Hermit。
有关现有技术的备注：十多年前，关于 Determinator 和 dOS 的早期学术研究是该领域的探索性调研。这些系统分别是 Linux 的小型教育操作系统和实验分支对象。两者的设计都不是让用户在实践中以确定性方式运行真实软件的可维护机制。
如需了解有关 Meta Open Source 的更多信息，请访问我们的 Open Source 网站、订阅我们的 YouTube 频道，或在 Twitter、Facebook 和 LinkedIn 上关注我们。
