💻 computer science

Divergent Multi-Version Execution (DME): Canonical Instruction-Trace Fault Detection via Structural Address-Space Decorrelation

本文介绍了发散多版本执行（DME），这是一种运行时故障检测技术，它通过为副本编译独立的内存布局来中和相关故障，并通过比较规范指令轨迹（同时忽略依赖地址的值）来验证执行正确性。

原作者： Petro Baran Yrievich

发布于 2026-05-14

📖 1 分钟阅读☕ 轻松阅读

原作者： Petro Baran Yrievich

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正与三胞胎进行一场高风险的赛跑。在传统赛跑中（论文称之为“传统冗余”），你给这三胞胎完全相同的地图、完全相同的鞋子和完全相同的路线。他们并排奔跑，你检查他们是否同时到达终点。

问题所在：
如果一阵突然而猛烈的狂风（“相关故障”）在同一瞬间吹向三胞胎，以完全相同的幅度将他们全部推离路径，他们将以完全相同的方式踉跄。他们都会犯同样的错误转弯，掉进同一个沟里，而你可能永远无法察觉他们犯了错，因为他们都在“一致地”走向错误的道路。这就像计算机故障：单个电磁脉冲同时扰乱了三个处理器的“大脑”，导致它们静默地破坏数据。

解决方案：发散多版本执行（DME）
论文提出了一种新的赛跑方式。与其给三胞胎相同的地图，不如给他们不同的地图，但这些地图都通向同一个目的地。

以下是 DME 的工作原理，分解为简单概念：

1. “不同地图”策略（结构去相关）

在赛跑开始前，系统会创建三个程序副本。然而，它们会以不同方式编译：

不同布局：在副本 A 中，“厨房”在左侧；在副本 B 中，“厨房”在右侧；在副本 C 中，它在地下室。
不同节奏：系统在每份副本的不同位置插入微小停顿（称为NOP或“无操作”指令）。副本 A 在第 3 步后停顿；副本 B 在第 4 步后停顿。
相反转向：如果代码说“左转”，副本 A 被编程为在地址 100 处执行物理左转；副本 B 被编程为在地址 500 处执行物理左转。

结果：尽管三胞胎在执行完全相同的逻辑（烹饪一顿饭），但他们是在不同的位置、以略微不同的时间物理执行这一过程。

2. “关注你做了什么，而非你在何处做”检查（规范轨迹）

在赛跑过程中，裁判并不关心街道地址（内存地址）。裁判只关心动作。

你切洋葱了吗？
你烧开水了吗？
你得到了“汤”这个结果吗？

系统剥离了“在哪里”（具体的内存地址），仅比较“做了什么”（指令和结果）。只要三胞胎都在切洋葱和烧开水，他们就是安全的。

3. 捕捉“狂风”（故障检测）

现在，想象那阵狂风再次袭来。

在旧系统中：三胞胎都被向右推了 5 米。他们最终都落在了同一个错误的位置。
在 DME 系统中：由于他们的地图不同，“向右推 5 米”对每个三胞胎意味着完全不同的事情。
- 三胞胎 A（靠近墙壁）撞墙并停下。
- 三胞胎 B（靠近门）从门中跌落。
- 三胞胎 C（靠近花园）踏入了花坛。

裁判观察他们的动作：“三胞胎 A 停下了，三胞胎 B 跌倒了，三胞胎 C 迈进了花坛。”他们不再在做相同的事情！ 裁判立即大喊：“出问题了！”并停止比赛。

4. “双重检查”安全网

论文引入了一种巧妙的第二层安全机制，称为地址非别名化。

在正常赛跑中，如果三胞胎突然决定跑向完全相同的坐标（例如，他们都困惑地跑向"0,0"），这是一个巨大的红旗。
在 DME 中，由于地图不同，除非出现故障，否则他们不可能自然地跑向相同的坐标。
如果裁判看到三胞胎都指向完全相同的地址（例如被破坏的返回地址或空指针），即使在他们执行正确动作之前，也会立即触发警报。这能立即捕获特定类型的软件错误（如“空指针”错误）。

两种类型的保证

论文声称提供两个层级的安全保障：

“保证”捕获（确定性）：如果风将三胞胎推动一个特定的、较大的幅度（大于插入的微小停顿），系统100% 保证能立即捕获错误。三胞胎肯定会做出不同的事情。
“几乎确定”捕获（概率性）：如果风将他们推动一个微小的幅度，或者风以不同方式吹向他们，他们可能会偶然地做出相同的错误事情，但这种可能性极小。然而，数学证明这种几率微乎其微（就像连续多次中彩票），因此在所有实际用途中，这种情况永远不会发生。

总结

DME 就像雇佣三位厨师烹饪同一道食谱，但给予他们：

布局不同的不同厨房。
不同的计时器。
放置在不同位置的不同工具。

如果停电或恶作剧者扰乱了厨房，由于环境不同，厨师们会有不同的反应。通过比较他们烹饪的结果（而非他们站立的位置），系统可以立即发现故障是否破坏了进程，即使故障在同一瞬间袭击了所有三位厨师。

这种方法专门针对嵌入式系统（如汽车或医疗设备的“大脑”）设计，在这些系统中，单个故障可能带来危险，而传统的“三重冗余”（三台相同的计算机）如果同时受到相同故障的袭击，可能会无法察觉。

技术摘要：发散多版本执行（DME）

问题陈述

传统的冗余机制，如步调一致执行（lockstep execution）和三模冗余（TMR），依赖于执行具有相同内存布局的相同二进制文件。虽然这些系统对独立故障有效，但它们容易受到关联故障的影响。实验研究（例如 Dutertre 等人）表明，物理干扰（如电磁故障注入）可以在所有副本上同时引发相同的扰动（例如特定的 $\Delta PC$ ）。在传统系统中，此类关联扰动会将所有副本重定向到同一条错误的执行路径，导致静默数据损坏，且由于所有副本产生相同的错误状态而未被检测到。此外，传统冗余通常无法检测特定类别的软件缺陷（如未初始化的指针、返回地址覆盖）或在所有副本上以相同方式表现的编译器/链接缺陷。

方法论

本文提出了发散多版本执行（DME），这是一种运行时语义一致性验证器，旨在通过确保相同的数值扰动导致语义发散的执行路径来检测关联故障。

核心原则

DME 在编译时强制执行四个基本原则：

独立编译： $N$ 个副本从相同的源代码独立编译。这会生成不同的物理代码和数据内存布局，同时保持相同的操作码级语义和同构的控制流图。
粗粒度去相关：利用互补的分支位移模式（例如，一个副本中的前向分支在另一个副本中变为后向分支），将函数和基本块放置在不同副本的不同地址。这确保了相同的控制流扰动映射到语义不同的路径。
细粒度去相关：在副本特定的偏移量（ $offset_r = \frac{l}{N} \cdot r$ ）处周期性插入 NOP 指令。这在对应的逻辑指令之间创建了最小空间间隔，从而能够检测小幅度程序计数器（PC）扰动。
数据地址去相关：为每个副本分配全局变量、栈帧和堆分配的唯一绝对基地址。

故障检测机制

DME 采用双层检测策略：

语义层（规范指令迹）：
- 系统比较各副本之间的“规范迹”。规范迹包括操作码、寄存器标识符、立即数操作数、加载/存储的值以及计算结果。
- 关键在于，绝对地址被排除在迹之外。
- 在无故障执行下，所有副本产生相同的规范迹。任何改变执行语义的故障（例如执行了不同的指令或计算了不同的结果）都会导致迹发散。
结构层（地址空间去相关与非别名化）：
- DME 将各副本之间物理地址的相等性（例如 $PC_1 = PC_2 = \dots = PC_N$ ）视为结构独立性的违反，而非允许的状态。
- 地址非别名化不变量：系统强制要求语义上对应的内存访问（数据或指令）必须在各副本中指向不同的有效地址。
- 如果故障（例如缓冲区溢出或空指针解引用）导致所有副本计算出相同的错误地址，系统将立即触发错误。这使得在语义发散发生之前就能检测到指针损坏和返回地址覆盖。

故障模型与检测机制

本文根据扰动的性质对检测保证进行了分类：

确定性检测：
- 适用于完全关联故障，即所有副本的 $\Delta PC$ 相同。
- 如果 $|\Delta PC| \geq l/N$ （其中 $l$ 是 NOP 插入步长），则保证该扰动会导致至少一个副本执行不同的逻辑指令，从而导致立即的迹发散。
- 地址空间坍缩（相同的 PC 或指针）作为结构违反被立即检测到。
概率性检测：
- 适用于部分关联故障（即各副本的 $\Delta PC$ 不同）或 $|\Delta PC| < l/N$ 的故障。
- 检测依赖于副本偶然对齐到相同逻辑指令并产生相同结果的极低概率。
- 在 $k$ 步内保持未被检测到的概率被限制为 $(\frac{C}{|S|} \cdot \epsilon)^k$ ，其中 $C$ 是规范等价指令的数量， $|S|$ 是总指令空间， $\epsilon$ 是产生相同结果的概率。对于典型的 32 位 ISA，该概率呈指数级衰减（例如 $\epsilon \leq 2^{-52}$ ）。

主要贡献

结构地址空间去相关：本文提出了一种方法，通过在编译期间主动多样化内存布局和分支位移，将关联的低级扰动转化为可观察的语义发散。
规范迹监控：它定义了一种与布局无关的迹表示法，捕获语义执行（操作码、寄存器、结果），同时丢弃依赖地址的信息，从而实现对不同二进制文件的稳健比较。
双层检测：DME 将语义迹比较与结构地址监控相结合。这使得能够立即检测“地址坍缩”事件（例如相同的返回地址），而传统冗余如果生成的执行路径恰好相同，可能会错过此类事件。
形式化正确性模型：本文区分了运行时语义正确性（迹的相等性）和系统级正确性（语义相等性 + 结构独立性）。它形式化地证明了结构独立性是保证关联故障可观测性的充分条件。

结果与主张

本文声称 DME 提供：

对于扰动幅度超过去相关步长（ $|\Delta PC| \geq l/N$ ）的关联 PC 故障，提供确定性检测。
对于其他故障类型，提供具有指数级衰减的概率性检测，其界限由指令集架构的状态空间决定。
通过地址非别名化不变量，立即检测指针语义违反（例如空指针、值即指针错误），通常早于语义发散。
实际可行性：作者引用了在 Altera Cyclone IV FPGA 上运行的 32 位软处理器（3o|||sheet）上的原型实现，以及在 Cortex-M 核心上的虚拟机实现，证明了开销是可管理的（例如，每个副本 3000 个 LUT 和 16 KB BRAM）。

意义

本文将 DME 定位为对安全关键嵌入式系统冗余的重新定义。与主要利用多样化来阻碍漏洞利用可移植性的多变体执行环境（MVEE）不同，DME 将结构去相关用作形式化运行时正确性不变量，以检测由物理干扰引起的位级损坏。

作者强调，DME 解决了现有容错机制中的一个特定缺口：传统冗余无法检测关联指令级扰动，这些扰动保持了状态相等性但违反了程序语义。通过强制执行结构独立性，DME 确保相同的数值故障不会导致相同的逻辑行为，从而将静默数据损坏的风险转化为可检测的事件。这项工作被提出为一种与硬件无关、可形式化分析的机制，适用于电磁或环境故障注入是现实威胁的环境。