arXiv CSopen access

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

2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

software-architecture software-engineering testing

software engineering, software architecture, testing

Divergent Multi-Version Execution (DME): Canonical Instruction-Trace Fault Detection via Structural Address-Space Decorrelation Petro Baran Yr Independent Researcher, Uzhgorod

arXiv:2605.12576v1 [cs.PL] 12 May 2026

2026

Abstract

roneous value: guaranteed detectable via structural address equality violation.

Traditional redundancy (lockstep, TMR) executes identical binaries with identical memory layouts. A single correlated fault — for example, an arbitrary program counter value or a perturbation ∆P C in all replicas — redirects all replicas along the same incorrect path. The same applies to corruption of data pointers. Both types of faults, regardless of their origin (deliberate tampering, software bug, compilation bug, or physical disturbance), cause silent data corruption and erroneous program execution. This work presents Divergent MultiVersion Execution (DME) — a runtime semantic consistency verifier for diversified executions. Each replica is compiled independently, producing different code and data memory layouts while preserving identical semantics. Faults are detected by comparing canonical instruction traces, which include opcodes, register identifiers, loaded/stored values, and results — while discarding layout-dependent addresses. Under fault-free execution, all replicas produce identical canonical traces. Any fault related to erroneous code or data addresses causes trace divergence and fault detection.

• ∗p1 = ∗p2 = · · · = ∗pN = const error — all replicas’ data pointers become set to the same erroneous value: guaranteed detectable via structural address equality violation. • Data divergence in one or N − 1 replicas: deterministic detection.

Probabilistic detection: These are faults where program counters or data pointers diverge to different erroneous values across replicas (e.g., P C1 ̸= P C2 ̸= . . . ̸= P CN or corruption occurs in only one replica or N − 1 replicas). Such faults are not covered by the deterministic regime and are detected with probability bounded by exponential decay. For typical 32-bit ISAs and a 4 kB memory region, the per-step probability of remaining undetected is bounded by ε ≤ 2−52 . This upper bound is determined statically from the program structure, including the control-flow graph, instruction distribution, and memory layout. Consequently, probabilistic faultdetection guarantees can be evaluated at compile time for a given fault model, enabling verification that the resulting protection satisfies the required safety or security Key features: targets. • Semantic execution trace monitoring. Fault Amplification through Structural Address-Space Decorrelation • Structural correctness monitoring during execution. Fundamental principle. Under fault-free execution, Depending on the chosen detection method (semantic all replicas produce identical canonical traces; under comparison only, or combined with structural correct- any fault, structural decorrelation guarantees maxiness monitoring), DME provides either deterministic or mally divergent outcomes. probabilistic fault detection guarantees.

Deterministic detection: • Instruction pointer corruption is guaranteed detectable within one instruction within the finegrained NOP-decorrelated region.

Motivation: Failure of Conventional Redundancy under Correlated Faults

Conventional redundancy schemes such as lockstep exe• P C1 = P C2 = · · · = P CN = const error — all repli- cution and TMR primarily assume that faults affecting cas’ program counters become set to the same er- different replicas are independent. 1

However, experimental studies on electromagnetic fault injection have shown that strongly correlated instruction-level perturbations are physically realizable in practice [ 6 ]. In particular, Dutertre et al. demonstrated that a single electromagnetic pulse can skip multiple consecutive instruction fetches on an 8-bit microcontroller. In conventional lockstep or TMR systems executing identical binaries with identical memory layouts, such correlated perturbations may redirect all replicas along the same incorrect execution path, causing silent data corruption. Divergent Multi-Version Execution (DME) is designed to detect not only such correlated control-flow faults, but more generally perturbations capable of altering the intended execution semantics of a program, including pointer corruption, memory-address faults, and misdirected control transfers. Unlike conventional MVEE systems, DME interprets cross-replica address equality as a violation of structural independence rather than as a permissible execution state. This invariant enables detection of a broad class of faults that manifest identically across all replicas — including data pointer corruptions (e.g., null or value-as-pointer errors), application software bugs (e.g., uninitialized pointers or return address overwrites), and compiler/linking defects that produce correlated layout or addressing anomalies — all of which are detected immediately upon address collapse, without relying on semantic trace divergence.

3. Fine-Grained Decorrelation: Deterministic NOP Insertion. Periodic NOP instructions are inserted at replica-specific offsets: offsetr =

l · r, N

r = 0, . . . , N − 1

where l is the insertion period (stride) specified by the application developer. The density 1/l controls the trade-off between detection granularity and overhead. The developer may enable NOP insertion either: • Globally — across the entire code section, or • Selectively — only within critical code regions (e.g., control-flow intensive loops, security-sensitive paths). This flexibility allows tuning of fault detection resolution versus performance cost. 4. Data Address Decorrelation. Global variable addresses are shuffled independently for each replica. Stack frames and heap allocations are placed at different base offsets across replicas. Combined with canonical trace comparison (which excludes absolute addresses), this ensures that identical memoryaddressing faults produce different loaded/stored values across replicas, exposing data-path faults. Together, these principles transform correlated lowlevel perturbations into observable semantic divergence while maintaining identical program semantics across replicas.

DME Model

2.1

Architectural Summary: Core Prin- 2.2 ciples

Replicas

N ≥ 2 replicas, same source program.

The DME architecture rests on four fundamental principles enforced at compile time and optionally customized by the application developer.

• Each compiled independently → distinct physical layouts • Private code, stack, heap per replica

1. Independent Compilation. All N replicas are compiled independently from the same source program. This produces distinct code and data layouts while preserving identical opcode-level semantics and isomorphic control-flow graphs. No runtime coordination is required for layout generation.

• Identical opcode-level semantics and control-flow graph (isomorphic)

2. Coarse-Grained Decorrelation: Function and Block Interleaving. Functions and basic blocks are placed at different addresses across replicas using complementary branch displacement patterns. Specifically, inter-block and inter-function jump offsets are assigned opposite signs in different replicas (e.g., forward branches in replica 0 become backward branches in replica 1). This ensures that identical control-flow perturbations map to semantically divergent execution paths.

Address-Space Decorrelation

Since DME targets bare-metal embedded systems without virtual memory (no MMU), all addressing is performed using absolute physical addresses. Structural address-space decorrelation is achieved by compiling and linking each replica independently with completely different absolute memory layouts. For each replica r, the compiler and linker assign unique absolute base addresses to code sections, data sections, stack, and heap regions. As a result, the same 2

To mitigate this, DME applies forced fragmentation during independent compilation of each replica. For any block exceeding Lcrit , the compiler selects fragmentation points. At each point:

Divergent Multi-Version Execution: ( 3o|||sheet Compilator )

Program

Replica�1

Main:

Method1:

Replica� n Method3:

• The original instruction sequence is split into fragments.

0x0000

0x0400

Method1:

Method3:

Method2:

Main:

0x0800

• Each fragment is placed at a replica-unique absolute memory location.

0x0C00

0x1000

0x1400 BLOCK n

• The original site receives an unconditional JMP to the fragment.

0x1800

Method3:

Method2: 0x1C00

Method n:

Data�A

Data�C

Data�B

Data�C

Data�B

Data�D

Data�B

Data�A

Data�D

Data��C

• The fragment ends with a JMP back to the continuation point. Example (N = 2): Consider a logical block consisting of instructions A, B, C, D, E, F . Replica 0 (fragments after B and D):

0x2000

0x2400

0x2800

0x2C00

Main: A, B, JMP f1 f1: C, D, JMP f2 f2: E, F, JMP ret Replica 1 (fragments after C and E): Main: A, B, C, JMP f1

Figure 1: Architecture.

f1: D, E, JMP f2

f2: F, JMP ret

A correlated fault ∆P C = +2 causes the replicas to execute different instructions (B → D in Replica 0 vs. source-level function or variable is placed at significantly B → E in Replica 1), leading to immediate divergence different absolute memory addresses across replicas. of the canonical instruction trace. DME employs three complementary mechanisms to achieve strong address-space decorrelation: Overhead: Each fragmentation point increases code 1. Block-level diversification — functions and ba- size by 2–4 bytes (JMP pair). To limit overhead, fragsic blocks are placed at different absolute addresses mentation can be applied selectively only to control-flow in each replica. Complementary branch displace- intensive or security-critical regions. ment patterns are used (e.g., forward branches in one replica become backward branches in another). Relationship to DME mechanisms: 2. Instruction-level asymmetry — periodic NOP insertion with replica-specific offsets: offsetr =

l · r, N

r = 0, . . . , N − 1

where l is the insertion period (stride).

Mechanism NOP insertion

Scope fine-grained

Block interleaving Fragmentation

coarse-grained oversized blocks

Detection type deterministic (≥ l/N ) probabilistic deterministic probabilistic

3. Data layout diversification — global variables, Forced fragmentation ensures that no single contiguous static data, stack frames, and heap allocations are block remains large enough to hide a correlated fault. placed at different absolute addresses in each replica. The deterministic detection bound (Theorem 1) applies Stack pointers are initialized to replica-specific base independently to each fragment. addresses.

3.1

Forced Fragmentation of Oversized 4 Functions / Blocks

Canonical Instruction (Full Definition)

Trace

When a function or basic block exceeds a critical size The canonical instruction representation C(I, s) for an Lcrit (e.g., 256 bytes), deterministic detection granularity instruction I and resulting architectural state s includes: degrades and coarse-grained decorrelation weakens due to locally similar branch displacements within the block. • opcode and condition codes, 3

Program

Replica�N

Main: iA

Method1: iC

∀i,�j,�∀v�:�instr�at�φi(v)�=�instr�at�φj�(v)�=�I(v)

Call M1

Call M2

Method1: iC

Call M2

iF iG

Method2: iE

iF iL

iF iG

Call M3

Method3: iG iJ

Main: iA

iB Call M1

Method3:

Method2:

call M3

Figure 2: Normal (fault-free) execution. Each replica’s methods, objects, and variables are relocated in memory, with recompilation applying new addresses for instruction use during runtime. • source and destination register identifiers,

Stack

Stack Main: iA

Method1: iC

Call M1

Call M2

iB iP

Address-Space�Collapse PC1�=�PCn

iD iN

iO Method2: iE

iF Call M3

iM Method3: iG

• stored values (for store instructions).

iK Main: iA

Absolute or relative addresses are explicitly excluded, as are NOP instructions. Example. Two replicas with different NOP layouts:

iB Call M1

iM Method2: iE

iF CALL M3

Program

• computed results (for ALU operations),

Method3: iG

• loaded memory values (for load instructions),

Method1: iC Call M2

• immediate operands,

Replica 1: A, B, C, NOP, D, E, F, G Replica 2: NOP, A, B, C, D, E, NOP, F

Replica�N

Under fault-free execution, both produce the same Figure 3: During normal execution, each replica’s canonical trace: ⟨A, B, C, D, E, F, G⟩. method has its own return address. Stack overflow can If a fault causes ∆P C = +3 during instruction B: direct all replicas to the same address, causing trace divergence: P C1 = P C2 = · · · = P CN . Simultaneous cor• Replica 1: B → D (skips NOP) ruption of the return address in all replicas (via buffer overflow) → all PCs equal → immediate error. In N• Replica 2: B → E Variant Systems, this could go undetected if the address falls into the allowed region. Canonical traces diverge → fault detected immediately. 4

Program Main: iA iB

Replica�N iA

Call M1

iQ Method1: iC iD

Call M2

iF iG

Method1: iC iD

Call M2

iF iG

Method3: iG

iH iI

Method2: iE

Error��=�PC+∆

Main: iF

Call M3

Key observation. The inclusion of computed results in the canonical trace creates a temporal coupling between consecutive instructions. For an ALU operation, the result becomes an input to subsequent instructions. Consequently, if two replicas produce identical canonical traces at time t, their register states must be identical at time t (at least for the destination registers). By induction, identical traces over a sequence imply identical full register states throughout that sequence. Thus, undetected execution requires not only semantically equivalent instructions but also identical prior computation history. This dramatically reduces the probability of prolonged undetected faults compared to schemes that compare only opcodes or control-flow signatures.

Call M1

4.1

Control-flow fault:

Normal

iM Method3:

Method2:

Fault Model

(r)

P Cf

call M3

(r)

= P Ci

+ ∆(r)

We consider:

Normal

• Independent faults (single replica affected)

Error��=�PC+∆

• Partially correlated faults (∆(i) ̸= ∆(j) )

Figure 4: Address corruption in replicas may be par• Fully correlated faults (∆(1) = ∆(2) = · · · = ∆) — tial (e.g., single-bit or multi-bit flips), resulting not in the dangerous case for conventional redundancy. a uniform replacement address but in an offset from the normal value while remaining distinct across replicas. To detect such errors, DME employs opposite branch signs 4.2 Unified Perturbation Model and NOP insertion to shift entry points. Conventional fault-tolerance models distinguish between hardware faults, software defects, compiler bugs, and environmental disturbances as separate categories. DME does not fundamentally depend on the origin of a perturbation. Instead, any mechanism capable of altering execution semantics is modeled uniformly as a semantic perturbation operator: iA

i iC iD

i iC

iiG

iH in

Π : St → St′

where:

JMP->A

• St is the expected architectural state at time t,

iiG

• St′ is the perturbed architectural state.

Label�B: iH in Label�A: iD

The origin of Π is irrelevant to the DME model. Examples include:

• transient hardware faults,

JMP->B

• permanent hardware defects,

Figure 5: Forced fragmentation of oversized blocks. This technique can optionally complement or replace NOP padding for fine-grained decorrelation.

• compiler miscompilation, • linker corruption, • memory corruption, • undefined behavior manifestations, 5

• malicious fault injection,

• identical semantic-preserving compiler bugs,

• control-flow hijacking,

• faults affecting shared architectural state identically,

• voltage or clock glitches,

• perturbations confined entirely to excluded shared regions.

• electromagnetic interference, • radiation-induced bit flips.

Detectability Guarantees

DME verifies only whether diversified executions reDME provides two complementary regimes of semantic main semantically equivalent. Let Tr denote the canonical execution trace of replica divergence observability: r. Runtime correctness is defined as: 1. Deterministic detection, ensured by fine-grained address-space asymmetry via replica-specific NOP T1 = T2 = · · · = TN insertion. Violation of semantic equivalence: 2. Probabilistic detection, activated when execution exits the deterministic region or when perturba∃i ̸= j : Ti ̸= Tj tions are not fully correlated, and relies on structural indicates incorrect execution independently of the peraddress-space decorrelation. turbation origin. Thus, DME should not be viewed solely as a fault deDetection (Finetection mechanism, but more generally as a runtime se- 5.1 Deterministic Grained) mantic consistency verifier for diversified executions.

4.3

Theorem 1 (Deterministic Detection Bound). Let N replicas employ periodic NOP padding with stride l and replica-specific offsets

Assumptions and Threat Model

DME assumes that replicas preserve semantic equivalence under fault-free execution while maintaining structural independence of address mappings. The model assumes:

offsetr =

l · r, N

r = 0, . . . , N − 1.

Assume a fully correlated perturbation:

• independent replica compilation,

∆P C (1) = ∆P C (2) = · · · = ∆P C.

• non-identical code and data layouts, If

• deterministic canonicalization,

l , N then at least one replica executes a different logical instruction, causing canonical trace divergence within one execution slice. |∆P C| ≥

• correct synchronization of execution slices, • trusted trace comparison logic. DME targets perturbations capable of modifying execution semantics, including:

Proof. Replica-specific offsets induce a minimum spatial separation of l/N between corresponding logical instructions across replicas. A perturbation of magnitude |∆P C| ≥ l/N exceeds this separation. Therefore, identical numerical perturbations cannot map all replicas to the same logical instruction. Hence, there exist replicas i ̸= j executing different logical instructions, which leads to divergence of canonical traces within one execution slice.

• transient hardware faults, • memory corruption, • compiler or linker defects, • control-flow corruption, • pointer corruption, • fault injection attacks.

Remark. Experimental work on electromagnetic fault injection confirms that fully correlated perturbations capable of skipping multiple consecutive instructions are realizable in practice 6. Thus, the adversarial model assumed in Theorem 1 is not merely theoretical.

The model does not guarantee detection of perturbations that preserve semantic equivalence across all replicas. Examples include: 6

Altering�the�symmetry�of�logical�blocks�for�detection�of��small-magnitude�program�counter�faults

Map�Trace

Replica�1

oﬀset��l/N

0x1000

0x4000

PC�1

iB iiC

NOP iA

PC�N iB

∆P�C

NOP

Hash�Trace

Replica��N

∆P�C

iiG

i iC iD

Replica��N

i iC iD

iiC iD

iH in

step�l

iE NOP iF

ε = sup P (equal result), be the probability that two instructions produce identical results. For an ISA with:

iiG

iH NOP in

Replica�1

• bop bits for opcode,

iiG

• breg bits for register identifiers, • bval bits for result values,

we obtain:

in PC�1�=�iB��PC�N=iB�

P�Cf�=�P�Ci�+�∆P�C

Let

State consistency factor.

ε ≤ 2−(bop +breg +bval ) .

>iD�=�iE

Example. For 8-bit opcode, three 4-bit register fields, Figure 6: Deterministic NOP decorrelation: and 32-bit result: replica-specific offsets create minimum separation ε ≤ 2−52 . l/N , ensuring detection of correlated PC faults with Theorem 2 (Probabilistic Detectability Bound). Un|∆P C| ≥ l/N . der structural independence, the probability that a fault remains undetected for k consecutive instructions is Interpretation. Any perturbation satisfying bounded by: |∆P C| ≥ l/N is guaranteed to be detected immek C diately. Perturbations with |∆P C| < l/N fall within ·ε . Pundetected (k) ≤ |S| an alignment window in which replicas may remain synchronized. Proof. At each step, undetected execution requires: Example. bytes.

1. fetching a canonically equivalent instruction (probability ≤ C/|S|),

Let l = 8 bytes and N = 2, so l/N = 4

2. producing an identical result (probability ≤ ε).

• |∆P C| < 4: alignment window (no guarantee),

Thus:

• |∆P C| ≥ 4: deterministic detection,

5.2

Probabilistic Grained)

Detection

Pstep ≤

(Coarse-

C · ε. |S|

Over k steps: Pundetected (k) ≤

When execution exits the NOP-padded region (e.g., due to a large perturbation or corrupted control transfer), or when perturbations are not fully correlated, detection relies on divergence in decorrelated address spaces.

C ·ε |S|

k .

The bound is conservative:

Discussion.

• assumes uniform instruction distribution,

Instruction-space density. Let: • |S|: number of valid instruction entry points,

• ignores control-flow constraints,

• C: number of instructions canonically equivalent to the expected instruction.

• ignores state divergence amplification. In practice, detection is significantly stronger.

Define:

C , |S| which bounds the probability of landing on a canonically equivalent instruction.

Example.

γ=

Let:

• |S| = 2048, • C = 12, • ε ≤ 2−52 .

Canonical equivalence. Each instruction I with resulting state s is mapped to:

For k = 2:

P ≤

C(I, s) = (opcode, src_regs, dst_reg, result), excluding layout-dependent information.

which is negligible. 7

12 · 2−52 2048

2 ,

5.3

Probabilistic Detection for Partially 5.3.3 Comparison with Lockstep Correlated Faults In classical lockstep, differing perturbations or a single-

replica fault cause immediate detection (different PCs → error flagged). In DME, the same scenario may temporarily escape detection if the different perturbations coincidentally map to the same logical instruction. However:

The deterministic guarantee (Theorem 1) applies only to fully correlated faults with identical perturbations across all replicas, and only when |∆P C| ≥ l/N . Two important practical cases fall outside this guarantee:

• The probability of such coincidence is extremely low for realistic ISAs (γ · ϵ ≈ 2−52 in the example of Section 5.2).

1. Differing perturbations: A fault affects all replicas, but ∆P C (i) ̸= ∆P C (j) for some i ̸= j.

• Even if alignment occurs at step 1, the probability of maintaining it for k ≥ 2 becomes negligible.

2. Single-replica fault: Only one replica experiences a perturbation; others execute correctly.

Thus, DME provides probabilistic detection with exponential decay, whereas lockstep provides determinIn both cases, deterministic detection may fail due to istic detection for differing perturbations. possible re-alignment, but detection is still possible with high probability. Detection comparison: lockstep vs. DME (A) Fully correlated, identical ∆P C, |∆P C| ≥ l/N : Lockstep: not detected (silent data corruption); DME: 5.3.1 Detection Condition deterministic detection. For a fault to remain undetected for k consecutive in(B) Fully correlated, identical ∆P C, |∆P C| < structions, three conditions must hold simultaneously: l/N : Lockstep: not detected; DME: not guaranteed. (C) Differing ∆P C or single-replica fault: Lock1. Equal logical instruction: All replicas fetch in- step: deterministic detection; DME: probabilistic detection with bound (γ · ϵ)k . structions that are canonically equivalent: Pr ≤

C |S|

5.3.4

Let N = 2, l = 8 bytes, w = 4 bytes. Consider a fault affecting only Replica 0: ∆P C (0) = +2, ∆P C (1) = 0.

2. Equal computed result: The instructions produce identical result values:

• Lockstep: P C0 ̸= P C1 → immediate detection. • DME: Replica 0 may land on a NOP, Replica 1 on a real instruction. Since NOP has no result, canonical equivalence is impossible — detection occurs immediately. If both land on different real instructions that accidentally produce the same result (rare), detection is delayed but bounded by (γ · ϵ)k .

Pr ≤ ϵ 3. No structural divergence: Address-space collapse does not occur (i.e., PCs may differ, but the above two conditions still hold). 5.3.2

Example

Thus, even in the probabilistic regime, practical detection is effectively immediate for most fault patterns.

Probability Bound

Under structural independence, the probability of unde- 5.4 Non-Correlated Perturbations tected execution over k steps is bounded by the same If perturbations differ across replicas: exponential expression as in Theorem 2: ∆P C (i) ̸= ∆P C (j) , k deterministic guarantees do not apply, even within C Pundetected (k) ≤ ·ϵ (1) padded regions. |S| Justification. Even when ∆P C values differ, the worst Re-alignment effect. Execution may temporarily recase for detection is when replicas accidentally align to align. For example: the same logical instruction and produce identical re• Replica 1 skips a real instruction, sults. The per-step probability of this coincidence is exC • Replica 2 skips a NOP, actly γ · ϵ = |S| · ϵ, independent of whether the perturbations were identical or not. resulting in both reaching the same logical instruction. 8

address-space collapse — a violation of structural independence — and triggers a system error. Address-space collapse violates the assumption ϕi ̸= ϕj and removes deterministic guarantees. It is detected and reported.

Example. • Replica 1: ∆P C = +3, • Replica 2: ∆P C = +4. Both replicas may fetch the same instruction, delaying detection.

6.1

Address-Space Collapse

Undetected execution requires: Definition. Under correct structural diversification, address mappings ϕr are pairwise distinct: 1. alignment to the same logical instruction,

Detection condition.

2. canonical equivalence,

∀r ̸= q : ϕr ̸= ϕq . Address-space collapse occurs if, during execution, two or more replicas resolve semantically corresponding operations to the same physical address:

3. identical computed results. Thus, detection follows: Pundetected (k) ≤

C ·ε |S|

k . ∃i ̸= j : P Ci = P Cj

∃i ̸= j : addri = addrj .

Detection. The structural address comparator monitors program counters and memory addresses across • Deterministic regime: For fully correlated perreplicas. Equality of physical addresses indicates a viturbations with |∆P C| ≥ l/N , detection is guaranolation of structural independence — a condition that teed within one instruction. cannot occur under correct compilation. Consequence. When address-space collapse hap• Alignment window: For |∆P C| < l/N , replicas pens: may remain aligned; no guarantee.

5.5

Summary of Detection Regimes

• Non-correlated perturbations: Detection becomes probabilistic due to possible re-alignment.

• Identical numerical perturbations ∆ applied to all replicas produce identical instruction fetches and memory accesses.

• Probabilistic regime: Outside padded regions or under misalignment, detection probability decays exponentially: k C ·ε . |S|

• Canonical traces remain equal: T1 = T2 = · · · = TN . • Deterministic detectability guarantees are lost. System response. Address-space collapse is treated as a system-level error, signalling either:

Alignment window behavior. If |∆P C| < l/N and perturbations are fully correlated, detection is not guar• compiler-induced layout aliasing, or anteed. However, if ∆P C (i) ̸= ∆P C (j) for any i ̸= j, seman• a fault that forced address convergence despite tic divergence occurs immediately, guaranteeing detecstructural independence. tion within one slice. Thus, the only undetectable case inside the window is Thus, DME provides dual-layer detection: semantic identical small perturbations — a scenario equally unde- divergence (canonical traces) and structural violation tectable in classical lockstep. (address equality).

Dual-Layer Detection

6.2

DME employs two orthogonal detection layers: Semantic layer. Compares canonical traces Ti across replicas. Detection condition: Ti ̸= Tj for any i ̸= j indicates a fault. Structural layer. Compares physical addresses (program counter, memory addresses) across replicas. Detection condition: P C1 = P C2 = · · · = P CN indicates

Address Non-Aliasing Detection (Early Memory Fault Detection)

In addition to semantic trace comparison and structural address-space independence, we introduce a runtime invariant that enables early detection of memory corruption errors by comparing effective memory access addresses across replicas. This includes both data pointers and instruction pointers (program counters). 9

Placement�in�memory�of�identical�branches�and�jumps�across�diﬀerent�replicas

Replica�1

Replica��2

predecessor 1 iA

target`=�target+

successor 2

iteration�N

iB iiH

iteration�N

iE iF

Other:

predecessor 2 iA

predecessor n iA

iB Call /JMP

target`=�target-

Call /JMP

target`=�target-

Addr[predcessor�1,�successor�1]

NOP iD

L1 L2 Ln

successor n

successor 1 iC

Call /JMP

Other:

Replica��N

Addr[predcessor�,N�successor�N]

Figure 7: Example of compiler placement of three identical logical blocks and functions in memory. For instance, if a branch in the first replica has a positive offset (PC+ = 64), the same branch in a second replica may have a negative offset (PC- = 96). The delta between branch targets also differs across replicas, ensuring structural address-space diversity.

Address Non-Aliasing Invariant. Under correct compilation and layout diversification, corresponding memory accesses in different replicas must not target the same effective address. This applies to both data accesses and instruction fetches: ∀a ∈ O, ∀i ̸= j :

Under correct structural independence such coincidence must not occur. Equality of effective addresses (including PCs) across replicas therefore violates the invariant and can be detected immediately by a dedicated address comparator. □

ϕi (a) ̸= ϕj (a)

where O is the set of logical memory objects (variables, stack frames, heap allocations, and instruction addresses), and ϕr denotes the address mapping function of replica r that maps a logical object a to its effective address. Effective Address. The effective address is the address actually used for memory access or instruction fetch in the context of the comparison:

Corollary 4.1 (Early Detection of Return Address Corruption). When a return address is corrupted with the same erroneous value in all replicas (e.g., due to buffer overflow or systematic fault), all replicas will attempt to fetch the next instruction from the same effective address. This leads to PC 1 = PC 2 = · · · = PC N , which is immediately detected as a violation of the Address Non-Aliasing Invariant — often earlier than semantic trace divergence.

• physical address in bare-metal systems without an MMU;

Interpretation. This mechanism introduces a third detection dimension in DME:

• virtual or replica-specific normalized address in virtualized, emulated, or time-multiplexed executions on a single physical core.

• Semantic layer: divergence of canonical traces, • Structural layer: enforcement of address-space independence (including PC non-equality),

Theorem 4 (Early Detection via Address Non• Address non-aliasing layer: runtime enforcement Aliasing). Let a DME system consist of N ≥ 2 repliof distinct effective access targets for both data and cas with structurally independent address mappings ϕr . instructions. Consider a memory access or instruction fetch (load, store, or instruction fetch) to the same logical object a The address non-aliasing layer is particularly effective performed by all replicas within the same execution slice. against correlated pointer and control-flow faults (such If during execution the effective addresses coincide: as identical return address corruption), providing zerolatency detection based purely on structural violations. ϕ1 (a) = ϕ2 (a) = · · · = ϕN (a), then this constitutes a violation of the Address Non- Limitations. Aliasing Invariant and indicates a fault (or a violation • Dependence on layout guarantees. The invariof structural independence). ant requires strict enforcement of non-overlapping In particular, if the program counters of all replicas address mappings. Any compiler or linker behavior become equal (PC 1 = PC 2 = · · · = PC N ), this is a sethat produces identical mappings for some addresses vere case of address-space collapse and must immediately may lead to false positives. trigger an exception. Such violations are detectable immediately at the mo• Legitimate shared regions. Memory regions inment the address is computed or the instruction is tentionally shared across replicas (e.g., memoryfetched, prior to any semantic divergence in canonical mapped I/O, communication buffers) violate the intraces. variant and must be excluded. Proof (informal). Under correct DME compilation, each replica receives a distinct address mapping ϕr . Therefore, the same logical instruction or data object resides at different effective addresses across replicas. Consider a fault that corrupts a pointer or return address (for example, via buffer overflow) such that all replicas compute the same erroneous effective address: p(1) = p(2) = · · · = p(N ) = addr.

• Partial coverage. The mechanism detects only faults that result in identical logical addresses. If corrupted pointers differ numerically, detection falls back to semantic divergence. • No semantic validation. Address equality or inequality does not directly encode program correctness. The mechanism detects violations of structural assumptions rather than logical errors. • Hardware overhead. Continuous comparison of memory access addresses introduces additional hardware cost and may impact timing in constrained systems.

Typical example — corruption of a return address: /* buffer overflow */ return_address = corrupted_value; 11

Summary. Address Non-Aliasing Detection strengthThus, DME transforms certain classes of latent softens DME by transforming a subset of latent memory cor- ware bugs into immediately observable structural violaruption faults into immediately observable structural vi- tions. olations, reducing detection latency and complementing Examples include: canonical trace comparison. • null-pointer dereference,

6.3

Detection of Pointer-Semantics Violations

• use of uninitialized pointers, • accidental value-to-pointer assignment,

Structural address-space decorrelation in DME requires that semantically corresponding objects reside at different effective addresses in different replicas. Consequently, pointers referring to corresponding logical objects must also differ numerically across replicas:

• corrupted function pointers, • invalid return addresses, • pointer truncation or overflow, • pointer arithmetic errors.

∀i ̸= j : pi (a) ̸= pj (a)

Interpretation. Address-space decorrelation is therewhere pr (a) denotes the pointer value referencing logfore not only a mechanism for correlated fault detection, ical object a in replica r. This property enables detection of a broad class of soft- but also a runtime validator of pointer semantic correctness. ware errors involving invalid pointer semantics. Null-pointer collapse. Consider a fault or software defect that replaces a valid pointer with zero:

Formal Correctness Criteria in DME

p1 = p2 = · · · = pN = 0

Conventional redundancy mechanisms such as lockstep When replicas attempt to dereference the pointer, all execution and Triple Modular Redundancy (TMR) dereplicas access the identical effective address: fine correctness solely in terms of equality of architectural states across replicas. While effective against indeaddr1 = addr2 = · · · = addrN = 0 pendent faults, this definition admits a class of correlated This violates the Address Non-Aliasing Invariant and faults that preserve equality while violating the intended immediately triggers detection as an address-space col- program semantics. lapse event. Divergent Multi-Version Execution (DME) extends Importantly, detection occurs even if the fault origi- this notion by explicitly separating two orthogonal asnates purely from software logic rather than from hard- pects: (i) correctness of execution and (ii) conditions reware corruption. quired for reliable fault observability. Rather than treating all deviations uniformly, DME introduces a two-level Value-as-pointer corruption. Consider a program- model consisting of a runtime semantic correctness conming error in which a computed value is mistakenly dition and a design-time structural constraint. stored into a pointer variable:

7.1

Semantic Equivalence

p := A + B

Let Tr denote the canonical execution trace of replica r, Since arithmetic results are semantically equivalent defined as a sequence of layout-independent representaacross replicas during correct execution, all replicas com- tions of executed instructions. We define semantic equivpute the same numerical value: alence as: (A + B)1 = (A + B)2 = · · · = (A + B)N

Psem = (T1 = T2 = · · · = TN )

Consequently, the corrupted pointer values also become identical:

(1)

This condition ensures that all replicas execute logically identical instruction sequences and produce identical semantic effects. p1 = p2 = · · · = pN Importantly, Psem is agnostic to the origin of deA subsequent load/store operation through the cor- viations. Any violation of semantic equivalence caprupted pointer causes all replicas to access the same effec- tures incorrect execution regardless of whether it arises tive address, violating structural independence and pro- from transient hardware faults, memory corruption, or ducing an address-space collapse. compiler-induced errors. 12

7.2

Structural Independence

Let ϕr denote the address mapping function for replica r, assigning logical program elements to physical memory addresses. We define structural independence as: Pstr = (∀r ̸= q : ϕr ̸= ϕq )

(2)

In contrast to conventional redundancy schemes, which rely solely on state equivalence, DME explicitly models the conditions under which faults become observable. Structural independence does not define correctness by itself, but guarantees that violations of semantic correctness are detectable.

This condition ensures that replicas do not share identical memory layouts, eliminating structural correlation in address space. Structural independence is established at compile time through replica-specific transformations and is invariant during execution. Its purpose is not to define correctness directly, but to ensure that identical numerical perturbations across replicas do not result in identical logical behavior.

7.6

System correctness additionally requires structural independence:

7.7

Discussion

Structural independence is enforced at compile time through replica-specific layout transformations and remains invariant during execution. It serves as a prerequisite for fault detectability rather than a runtime correctness condition. Intuitively, DME narrows the correctness criterion to semantic equivalence while simultaneously preventing fault masking due to structural correlation. As a result, faults originating from diverse sources — including 7.3 Correctness Model hardware faults, memory corruption, and compiler errors — are uniformly exposed as semantic divergence in We distinguish between runtime correctness and systemcanonical execution traces. level correctness. This dual perspective allows DME to be interpreted Runtime correctness is defined solely in terms of senot only as a fault detection mechanism, but also as a mantic equivalence: general runtime validator of semantic equivalence across Correctruntime = Psem (3) diversified execution pipelines.

Detectability Guarantee Structural Independence

under

(4) The role of structural independence can be formalized as a condition that guarantees observability of semantic This distinction reflects the separation between exe- deviations under correlated perturbations. Fault model. Assume a fault that induces identical cution behavior and the conditions that guarantee its numerical perturbations ∆ across all replicas, affecting reliable verification. either: Correctsystem = Psem ∧ Pstr

7.4

• the program counter (control-flow faults), or

Error Condition

A runtime error is detected when semantic equivalence • data values or memory addresses (data-path faults). is violated: Such faults may arise from global disturbances (e.g., voltError = ¬Psem (5) age fluctuations, clock glitches) or systematic effects. Violation of structural independence does not correTheorem 3 (Detectability under structural indepenspond to a runtime fault, but rather to a configuration dence). Let a DME system satisfy structural indepenor design-time error that may reduce the detectability of dence Pstr . Assume that the address mapping functions faults. ϕr are pairwise distinct and that canonicalization removes all layout-dependent information. 7.5 Interpretation If a fault induces identical perturbations ∆ in all replicas and the perturbation leads to a semantic deviation in This formulation separates two complementary dimenat least one replica, then there exist replicas i ̸= j such sions: that: Ti ̸= Tj (6) • Semantic correctness (Psem ), capturing all deviations in execution behavior, including control-flow and therefore the fault is detectable via violation of Psem errors, data corruption, and miscompilation. within a finite number of execution steps. • Structural independence (Pstr ), ensuring that such Proof (informal). Because structural independence endeviations manifest as observable divergence be- sures ϕi ̸= ϕj for all i ̸= j, identical numerical pertween replicas. turbations ∆ applied to different replicas are mapped 13

through distinct address spaces. Consequently, the same perturbed value (e.g., program counter or pointer) resolves to different logical instructions or data locations in different replicas. This divergence in logical behavior produces different canonical instruction representations C(It , st ) across replicas. Since canonicalization removes layoutdependent artifacts while preserving semantic effects, any difference in executed instructions, loaded values, or computed results results in different canonical traces. Therefore, for at least two replicas i and j, the traces diverge (Ti ̸= Tj ), which violates Psem and is detected by the comparison mechanism. Detection occurs within a bounded number of execution steps determined by the trace comparison granularity. □ Stronger formulation. The same argument extends to data-path faults. Suppose a fault induces identical perturbations to register values or memory operands across all replicas. Because structural independence ensures ϕi ̸= ϕj , the same perturbed numerical value maps to different logical data locations. Consequently, loaded values differ across replicas, producing different computed results in ALU operations. These differences appear in the canonical traces as divergent computed_result fields, triggering detection. Thus, structural independence guarantees not only control-flow divergence but also register state divergence within a bounded number of steps. The only way for a fault to remain undetected is to preserve identical register states and identical instruction sequences indefinitely — a scenario whose probability is bounded by ρN −1 · pk with p extremely small for k ≥ 2. Corollary 3.1. In the absence of structural independence (i.e., if ∃i ̸= j : ϕi = ϕj ), there exists a class of correlated faults for which: T1 = T2 = · · · = TN

(7)

across all replicas. If a fault produces identical canonical instruction effects in every replica, then: T1 = T2 = · · · = TN and no divergence is observable. This limitation is inherent to all redundancy-based detection mechanisms, including lockstep execution and TMR. DME mitigates this limitation by introducing structural diversity, which reduces the class of faults that preserve semantic equivalence, but does not eliminate it entirely.

7.8

While structural independence Pstr is established at compile time, runtime address-level consistency checks (e.g., verifying P Ci ̸= P Cj for semantically equivalent instructions or comparing section base addresses) provide partial enforcement, detecting address-space collapse as defined in Section 4.

7.9

Execution Slice

Definition. An execution slice St is the interval during which each of the N replicas executes exactly one logical instruction before the canonical hashes are compared. The physical duration of a slice is: Tslice = N · Tinstr + Tcmp in a time-multiplexed implementation, or simply Tslice = Tinstr in a spatially parallel (e.g., FPGA) implementation. Property. Any fault that causes semantic divergence is detected within at most one execution slice. Interrupts and exceptions are handled identically across replicas before slice boundaries.

despite incorrect execution, leading to potential silent data corruption.

Runtime Enforcement of Structural Independence

Limitations

DMEinherits the fundamental limitation of all redundancy-based schemes: Faults that preserve identical canonical traces across all replicas remain undetectable. Examples:

Interpretation. The theorem establishes that structural independence is a sufficient condition for transforming correlated low-level perturbations into observable semantic divergence. In this sense, structural diversity acts • Perturbations that map to equivalent logical instrucas a fault amplification mechanism: identical numerical tions faults are mapped to different logical effects, ensuring their detectability. • Faults affecting only shared microarchitectural comThus, while semantic equivalence defines correctness, ponents identically structural independence guarantees that violations of correctness cannot remain hidden due to correlated exe• Compiler-induced correlated transformations that cution. preserve semantics Remark (Limit of detectability). The detectability guarantee established above assumes that identi- DMEreduces the probability of such masking but does cal perturbations do not preserve semantic equivalence not eliminate it. 14

Replica�N Critical�D

Method�F

Method��A

Method�C

Critical�B

Method��E

Program Method�A

Critical�B

Method��C

Critical�D

Method��E

Method�F

NOP�padding�density�(layout�shift�strength)

Figure 8: Adaptive DME layout diversification. Fine-grained instruction padding is applied only to critical program regions, while the rest of the code relies on coarse-grained structural addressspace decorrelation. The density of vertical stripes schematically represents the density of inserted NOP instructions, illustrating increased finegrained layout diversification in critical functions. • Deterministic detection for |∆P C| ≥ l/N — provRemark on the undetectable class. While undeable, not probabilistic tectable faults theoretically exist, our analysis shows that they require the preservation of identical register states • Dual-layer detection (semantic + structural) catches across all replicas throughout the faulty execution. For a both divergence and address-space collapse program with n instructions, the number of distinct register states is exponential in the number of registers and • Practical implementations: bit width. The probability that a random PC perturbation lands on an instruction sequence that preserves reg– VM on Cortex-M: 8 KB RAM total, VM ocister equality for k steps is bounded by ρN −1 · ϵk , where cupies 4 KB, remaining 4 KB shared among ϵ is the probability that two randomly chosen instrucreplicas (2 KB per replica for N = 2) tions produce the same result given identical inputs. For typical ALU operations on 32-bit data, ϵ ≈ 2−32 for ad– FPGA implementation on Altera Cyclone IV dition/subtraction, and even smaller for operations with EP4CE6E22C8 operating in dual-core mode. carry or flags. Each core consumes 3000 LUTs and 16 KB of Hence, while not strictly impossible, the undetectable BRAM per replica. Soft processor, designated fault class is practically negligible for any k ≥ 2. This 3o|||sheet, features a custom 32-bit instruction distinguishes DME from lockstep/TMR, where undeset designed for industrial controller workloads tectable correlated faults are not exponentially suppressed by state width. DME provides a formally analyzable, configurable, and hardware-independent fault detection mechanism suitable for safety-critical embedded systems.

Conclusion 9.1

Divergent Multi-Version Execution redefines redundancy: from comparing physical state to comparing logical execution trajectories. Key results:

Relation to Multi-Variant Execution Environments (MVEE)

Unlike Multi-Variant Execution Environments (MVEE), which primarily employ diversification to reduce exploit 15

portability while validating coarse-grained external behavior (e.g., system calls), DME uses structural addressspace decorrelation as a fault-observability mechanism. In MVEE systems, diversified layouts are mainly a security-oriented property and do not generally constitute a formal runtime correctness invariant. Correlated instruction-level perturbations may therefore remain undetected as long as externally observable behavior remains sufficiently consistent across variants. In contrast, DME is explicitly designed to detect bitlevel corruptions of the program counter caused by physical disturbances (e.g., electromagnetic or clock glitches). Such faults typically shift P C by a small offset rather than overwriting it with an arbitrary value. To make these small, correlated shifts observable, DME does not rely on passive layout randomness. Instead, it actively modifies branch displacements during compilation: the same logical branch is compiled with opposite signs across replicas (e.g., forward in replica 0, backward in replica 1). Consequently, an identical ∆P C perturbation pushes replicas onto semantically different execution paths, guaranteeing detection. More generally, DME continuously validates semantic equivalence of canonical instruction traces and treats violations of structural independence as explicit runtime fault conditions. These violations include not only control-flow collapse: P C1 = P C2 = · · · = P CN ,

9.3

Distinction from EDDI and SWIFT

EDDI execute identical binaries with identical memory layouts, detecting only uncorrelated faults. DME executes independently compiled replicas with decorrelated address spaces. Consequently, DME provides: • Deterministic detection of fully correlated PC faults when |∆P C| ≥ l/N (Theorem 1); • Immediate structural violation detection for identical pointer corruptions via the Address Non-Aliasing Invariant. Neither property holds in EDDI or SWIFT.

Selected References 1. S. Manoni et al., “CVA6-CFI: A First Glance at RISC-V Control-Flow Integrity Extensions,” arXiv preprint arXiv:2602.04991, Feb. 2026. 2. A. Avizienis, “The N-Version Approach to FaultTolerant Software,” IEEE Trans. Software Eng., 1985. 3. N. Oh et al., “Error Detection by Duplicated Instructions (EDDI),” MICRO-35, 2002.

but also data address collapse: p1 = p2 = · · · = pN , where pr denotes a data pointer in replica r. A null pointer dereference, a corrupted return address, or an arithmetic result mistakenly assigned to a pointer — if identical across all replicas — is detected immediately via the Address Non-Aliasing Invariant, often before any semantic divergence occurs. Thus, structural diversity in DME is not merely intended to increase exploit diversity, but to guarantee that identical numerical perturbations cannot preserve identical logical execution across replicas — for both code and data addresses.

9.2

• Relationship: CFI ⊆ DME per replica; DME adds cross-replica semantic equivalence and structural address invariants.

DME vs. CFI

4. G. A. Reis et al., “SWIFT: Software Implemented Fault Tolerance,” CGO, 2005. 5. M. Abadi et al., “Control-Flow Integrity,” CCS, 2005. 6. J.-M. Dutertre, A. Menu, O. Potin, J.-B. Rigaud, J.-L. Danger, “Experimental Analysis of the Electromagnetic Instruction Skip Fault Model and Consequences for Software Countermeasures,” Microelectronics Reliability, 2021. 7. B. Randell, “System structure for software fault tolerance,” IEEE Transactions on Software Engineering, vol. SE-1, no. 2, pp. 220-232, June 1975.

• CFI: single execution, enforces legal control-flow transitions (CFG), cannot detect correlated faults that stay within the CFG or data-pointer errors without illegal jumps.

8. J. Just and M. Cornwell, “Review and analysis of synthetic diversity for breaking monocultures,” in Proc. 2004 ACM Workshop on Rapid Malcode (WORM ’04), Washington DC, USA, 2004, pp. 2332.

• DME: multiple diversified replicas, compares canonical instruction traces (opcodes, registers, results, load/store values), detects correlated PC faults (|∆P C| ≥ l/N ) and identical pointer corruptions via address non-aliasing invariant.

9. H.-M. Pham, S. Pillement, and S. J. Piestrak, “Lowoverhead fault-tolerance technique for a dynamically reconfigurable softcore processor,” IEEE Transactions on Computers, vol. 62, no. 6, pp. 1202-1215, June 2013.

10. M. Barbiottia et al., “Dynamic Triple Modular Redundancy in Interleaved Hardware Threads,” IEEE Access, vol. 12, pp. 32456-32470, 2024. 11. S. Binosi et al., “The Illusion of Randomness: An Empirical Analysis of Address Space Layout Randomization Implementations,” in Proc. ACM SIGSAC Conf. Computer and Communications Security (CCS ’24), 2024. 12. A. Avizienis, J. C. Laprie, B. Randell, and C. Landwehr, “Basic concepts and taxonomy of dependable and secure computing,” IEEE Transactions on Dependable and Secure Computing, vol. 1, no. 1, pp. 11-33, Jan.-March 2004. 13. M. Amel Solouki, S. Angizi, and M. Violante, “Dependability in Embedded Systems: A Survey of Fault Tolerance Methods and SoftwareBased Mitigation Techniques,” arXiv preprint arXiv:2404.10509, April 2024. 14. A. A. Malik, H. Mihir, and A. Aysu, “Honest to a Fault: Root-Causing Fault Attacks with Pre-Silicon RISC Pipeline Characterization,” arXiv preprint arXiv:2503.04846, March 2025. 15. “Improved address space layout randomization,” Google Patents DE112017002277T5, 2017.

Record · ID 180736 · SHA-256 59722b4859d8ba1a
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.