Technical Summary: Divergent Multi-Version Execution (DME)

Problem Statement

Traditional redundancy mechanisms, such as lockstep execution and Triple Modular Redundancy (TMR), rely on executing identical binaries with identical memory layouts. While effective against independent faults, these systems are vulnerable to correlated faults. Experimental studies (e.g., Dutertre et al.) have demonstrated that physical disturbances, such as electromagnetic fault injection, can induce identical perturbations (e.g., a specific $\Delta PC$) across all replicas simultaneously. In conventional systems, such correlated perturbations redirect all replicas along the same incorrect execution path, leading to silent data corruption that remains undetected because all replicas produce identical erroneous states. Furthermore, conventional redundancy often fails to detect specific classes of software bugs (e.g., uninitialized pointers, return address overwrites) or compiler/linking defects that manifest identically across replicas.

Methodology

The paper proposes Divergent Multi-Version Execution (DME), a runtime semantic consistency verifier designed to detect correlated faults by ensuring that identical numerical perturbations result in semantically divergent execution paths.

Core Principles

DME operates on four fundamental principles enforced at compile time:

1. Independent Compilation: $N$ replicas are compiled independently from the same source code. This produces distinct physical code and data memory layouts while preserving identical opcode-level semantics and isomorphic control-flow graphs.
2. Coarse-Grained Decorrelation: Functions and basic blocks are placed at different addresses across replicas using complementary branch displacement patterns (e.g., forward branches in one replica become backward branches in another). This ensures that identical control-flow perturbations map to semantically different paths.
3. Fine-Grained Decorrelation: Periodic NOP instructions are inserted at replica-specific offsets ($offset_r = \frac{l}{N} \cdot r$). This creates a minimum spatial separation between corresponding logical instructions, enabling the detection of small-magnitude Program Counter (PC) perturbations.
4. Data Address Decorrelation: Global variables, stack frames, and heap allocations are assigned unique absolute base addresses for each replica.

Fault Detection Mechanisms

DME employs a dual-layer detection strategy:

1. Semantic Layer (Canonical Instruction Trace):

   • The system compares "canonical traces" across replicas. A canonical trace includes opcodes, register identifiers, immediate operands, loaded/stored values, and computed results.
   • Crucially, absolute addresses are excluded from the trace.
   • Under fault-free execution, all replicas produce identical canonical traces. Any fault altering execution semantics (e.g., executing a different instruction or computing a different result) causes trace divergence.

2. Structural Layer (Address-Space Decorrelation & Non-Aliasing):

   • DME treats the equality of physical addresses (e.g., $PC_1 = PC_2 = \dots = PC_N$) across replicas as a violation of structural independence, rather than a permissible state.
   • Address Non-Aliasing Invariant: The system enforces that semantically corresponding memory accesses (data or instructions) must target different effective addresses across replicas.
   • If a fault (e.g., buffer overflow or null-pointer dereference) causes all replicas to compute the same erroneous address, the system immediately triggers an error. This allows for the detection of pointer corruptions and return address overwrites before semantic divergence occurs.

Fault Models and Detection Regimes

The paper categorizes detection guarantees based on the nature of the perturbation:

• Deterministic Detection:

  • Applies to fully correlated faults where $\Delta PC$ is identical across all replicas.
  • If $|\Delta PC| \geq l/N$ (where $l$ is the NOP insertion stride), the perturbation is guaranteed to cause at least one replica to execute a different logical instruction, leading to immediate trace divergence.
  • Address-space collapse (identical PCs or pointers) is detected immediately as a structural violation.

• Probabilistic Detection:

  • Applies to partially correlated faults (where $\Delta PC$ differs across replicas) or faults where $|\Delta PC| < l/N$.
  • Detection relies on the low probability of replicas accidentally aligning to the same logical instruction and producing identical results.
  • The probability of remaining undetected for $k$ steps is bounded by $(\frac{C}{|S|} \cdot \epsilon)^k$, where $C$ is the number of canonically equivalent instructions, $|S|$ is the total instruction space, and $\epsilon$ is the probability of identical results. For typical 32-bit ISAs, this probability decays exponentially (e.g., $\epsilon \leq 2^{-52}$).

Key Contributions

1. Structural Address-Space Decorrelation: The paper introduces a method to transform correlated low-level perturbations into observable semantic divergence by actively diversifying memory layouts and branch displacements during compilation.
2. Canonical Trace Monitoring: It defines a layout-independent trace representation that captures semantic execution (opcodes, registers, results) while discarding address-dependent information, enabling robust comparison across diverse binaries.
3. Dual-Layer Detection: DME combines semantic trace comparison with structural address monitoring. This allows for the immediate detection of "address collapse" events (e.g., identical return addresses) which traditional redundancy might miss if the resulting execution path happens to be identical.
4. Formal Correctness Model: The paper distinguishes between runtime semantic correctness (equality of traces) and system-level correctness (semantic equality + structural independence). It formally proves that structural independence is a sufficient condition to guarantee the observability of correlated faults.

Results and Claims

The paper claims that DME provides:

• Deterministic detection for correlated PC faults where the perturbation magnitude exceeds the decorrelation stride ($|\Delta PC| \geq l/N$).
• Probabilistic detection with exponential decay for other fault types, bounded by the instruction set architecture's state space.
• Immediate detection of pointer semantics violations (e.g., null pointers, value-as-pointer errors) via the Address Non-Aliasing Invariant, often earlier than semantic divergence.
• Practical Feasibility: The authors cite a prototype implementation on a 32-bit soft processor (3o|||sheet) running on an Altera Cyclone IV FPGA, and a Virtual Machine implementation on a Cortex-M core, demonstrating that the overhead is manageable (e.g., 3000 LUTs and 16 KB BRAM per replica).

Significance

The paper positions DME as a redefinition of redundancy for safety-critical embedded systems. Unlike Multi-Variant Execution Environments (MVEE), which primarily use diversification to hinder exploit portability, DME uses structural decorrelation as a formal runtime correctness invariant to detect bit-level corruptions caused by physical disturbances.

The authors emphasize that DME addresses a specific gap in existing fault tolerance: the inability of conventional redundancy to detect correlated instruction-level perturbations that preserve state equality but violate program semantics. By enforcing structural independence, DME ensures that identical numerical faults cannot result in identical logical behaviors, thereby transforming silent data corruption risks into detectable events. The work is presented as a hardware-independent, formally analyzable mechanism suitable for environments where electromagnetic or environmental fault injection is a realistic threat.