💻 computer science

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

Dieser Artikel stellt die divergente Multi-Version-Ausführung (DME) vor, eine Laufzeit-Fehlererkennungstechnik, die Replikate mit unabhängigen Speicherlayouts kompiliert, um korrelierte Fehler zu neutralisieren, und die Ausführungskorrektheit durch den Vergleich kanonischer Instruktionsverläufe unter Vernachlässigung adressenabhängiger Werte verifiziert.

Ursprüngliche Autoren: Petro Baran Yrievich

Veröffentlicht 2026-05-14

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Petro Baran Yrievich

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie führen ein hochriskantes Rennen mit drei identischen Zwillingen. Bei einem traditionellen Rennen (was das Papier als „konventionelle Redundanz" bezeichnet) geben Sie allen drei Zwillingen exakt dieselbe Karte, exakt dieselben Schuhe und exakt dieselbe Route. Sie laufen nebeneinander, und Sie prüfen, ob sie gemeinsam am Ziel ankommen.

Das Problem:
Wenn ein plötzlicher, kräftiger Windstoß (eine „korrelierte Störung") alle drei Zwillinge im exakt gleichen Moment trifft und sie alle um denselben Betrag von der Strecke drückt, werden sie alle auf exakt dieselbe Weise straucheln. Sie werden alle dieselbe falsche Abzweigung nehmen, in denselben Graben fallen, und Sie werden möglicherweise nie merken, dass sie einen Fehler gemacht haben, weil sie sich alle über den falschen Weg „einig" sind. Dies ist vergleichbar mit einem Computerfehler, bei dem ein einzelner elektromagnetischer Impuls das Gehirn aller drei Prozessoren gleichzeitig durcheinanderbringt und sie dazu veranlasst, Daten stillschweigend zu korrumpieren.

Die Lösung: Divergente Multi-Version-Ausführung (DME)
Das Papier schlägt eine neue Art vor, das Rennen zu führen. Anstatt den Zwillingen dieselbe Karte zu geben, erhalten sie unterschiedliche Karten, die zum selben Ziel führen.

So funktioniert DME, aufgeschlüsselt in einfache Konzepte:

1. Die Strategie der „unterschiedlichen Karten" (Strukturelle Dekorrelierung)

Bevor das Rennen beginnt, erstellt das System drei Kopien des Programms. Diese werden jedoch unterschiedlich kompiliert:

Unterschiedliche Anordnungen: In Kopie A befindet sich die „Küche" links. In Kopie B ist die „Küche" rechts. In Kopie C befindet sie sich im Keller.
Unterschiedliches Tempo: Das System fügt an unterschiedlichen Stellen in jeder Kopie winzige Pausen ein (sogenannte NOPs oder „No Operation"-Anweisungen). Kopie A pausiert nach Schritt 3; Kopie B pausiert nach Schritt 4.
Gegenteilige Wendungen: Wenn der Code sagt „Links abbiegen", ist Kopie A so programmiert, dass sie eine Linkskurve nimmt, die sich physisch an Adresse 100 befindet. Kopie B ist so programmiert, dass sie eine Linkskurve nimmt, die sich physisch an Adresse 500 befindet.

Das Ergebnis: Obwohl die Zwillinge exakt dieselbe Logik ausführen (eine Mahlzeit zubereiten), tun sie dies physisch an unterschiedlichen Orten und zu leicht unterschiedlichen Zeiten.

2. Die Prüfung von „Was Sie taten, nicht wo Sie es taten" (Kanonsche Spuren)

Während des Rennens interessiert sich der Schiedsrichter nicht für die Straßenadressen (Speicheradressen). Dem Schiedsrichter sind nur die Aktionen wichtig.

Haben Sie die Zwiebeln gehackt?
Haben Sie das Wasser zum Kochen gebracht?
Haben Sie das Ergebnis „Suppe" erhalten?

Das System entfernt das „Wo" (die spezifische Speicheradresse) und vergleicht nur das „Was" (die Anweisung und das Ergebnis). Solange alle drei Zwillinge Zwiebeln hacken und Wasser kochen, ist alles in Ordnung.

3. Das Einfangen des „Windstoßes" (Fehlererkennung)

Stellen Sie sich nun vor, dieser Windstoß trifft erneut zu.

Im alten System: Alle drei Zwillinge werden um 5 Meter nach rechts gedrückt. Sie landen alle am selben falschen Ort.
Im DME-System: Da ihre Karten unterschiedlich sind, bedeutet ein Stoß von „5 Meter nach rechts" für jeden Zwilling etwas völlig anderes.
- Zwilling A (der sich in der Nähe einer Wand befand) prallt gegen die Wand und bleibt stehen.
- Zwilling B (der sich in der Nähe einer Tür befand) fällt durch die Tür.
- Zwilling C (der sich in der Nähe eines Gartens befand) tritt in ein Blumenbeet.

Der Schiedsrichter betrachtet ihre Aktionen: „Zwilling A blieb stehen, Zwilling B fiel, Zwilling C trat." Sie tun nicht mehr dasselbe! Der Schiedsrichter schreit sofort: „Etwas stimmt nicht!" und stoppt das Rennen.

4. Das Sicherheitsnetz der „Doppelprüfung"

Das Papier führt eine kluge zweite Sicherheitsebene namens Adress-Non-Aliasing ein.

Bei einem normalen Rennen, wenn alle drei Zwillinge plötzlich beschließen, zur exakt gleichen Koordinate zu laufen (z. B. weil sie alle verwirrt sind und zu „0,0" laufen), ist das ein riesiges Warnsignal.
Bei DME ist es aufgrund der unterschiedlichen Karten unmöglich, dass sie auf natürliche Weise zur gleichen Koordinate laufen, es sei denn, etwas ist defekt.
Wenn der Schiedsrichter sieht, dass alle drei Zwillinge auf exakt dieselbe Adresse zeigen (wie eine korrumpierte Rückkehradresse oder einen Nullzeiger), wird sofort ein Alarm ausgelöst, noch bevor geprüft wird, ob sie die richtigen Aktionen ausführen. Dies fängt bestimmte Arten von Softwarefehlern (wie „Nullzeiger"-Fehler) sofort ab.

Die zwei Arten von Garantien

Das Papier behauptet zwei Sicherheitsstufen:

Die „garantierte" Abfangung (Deterministisch): Wenn der Windstoß die Zwillinge um eine spezifische, große Menge drückt (größer als die eingefügten winzigen Pausen), ist das System zu 100 % garantiert in der Lage, den Fehler sofort zu erkennen. Die Zwillinge werden definitiv unterschiedliche Dinge tun.
Die „fast sichere" Abfangung (Probabilistisch): Wenn der Windstoß sie nur um einen winzigen Betrag drückt oder wenn der Windstoß sie unterschiedlich trifft, besteht eine winzige, winzige Chance, dass sie versehentlich dasselbe falsche Ding tun. Die Mathematik zeigt jedoch, dass diese Chance so gering ist (wie mehrmals hintereinander im Lotto zu gewinnen), dass sie für alle praktischen Zwecke niemals eintreten wird.

Zusammenfassung

DME ist wie die Anstellung von drei Köchen, um dasselbe Rezept zu kochen, wobei man ihnen gibt:

Unterschiedliche Küchen mit unterschiedlichen Anordnungen.
Unterschiedliche Timer.
Unterschiedliche Werkzeuge, die an unterschiedlichen Stellen platziert sind.

Wenn ein Stromausfall oder ein Scherzkeks die Küche durcheinanderbringt, reagieren die Köche unterschiedlich, weil ihre Umgebungen unterschiedlich sind. Indem man vergleicht, was sie gekocht haben (das Ergebnis) und nicht wo sie standen, kann das System sofort feststellen, ob ein Fehler den Prozess korrumpiert hat, selbst wenn der Fehler alle drei Köche im exakt gleichen Moment getroffen hat.

Diese Methode ist speziell für eingebettete Systeme (wie die Gehirne von Autos oder medizinischen Geräten) entwickelt, bei denen ein einzelner Fehler gefährlich sein könnte und bei denen die traditionelle „dreifache Redundanz" (drei identische Computer) versagen könnte, einen Fehler zu bemerken, wenn sie alle von demselben Fehler betroffen sind.

Technische Zusammenfassung: Divergente Multi-Version-Ausführung (DME)

Problemstellung

Traditionelle Redundanzmechanismen, wie die schrittweise Ausführung (Lockstep Execution) und die Triple Modular Redundancy (TMR), basieren auf der Ausführung identischer Binärdateien mit identischen Speicherlayouts. Obwohl diese Systeme gegenüber unabhängigen Fehlern effektiv sind, sind sie anfällig für korrelierte Fehler. Experimentelle Studien (z. B. Dutertre et al.) haben gezeigt, dass physikalische Störungen, wie elektromagnetische Fehlerinjektion, identische Störungen (z. B. ein spezifisches $\Delta PC$ ) gleichzeitig über alle Replikate hinweg hervorrufen können. In konventionellen Systemen lenken solche korrelierten Störungen alle Replikate auf denselben falschen Ausführungspfad um, was zu einer stillen Datenkorruption führt, die unentdeckt bleibt, da alle Replikate identische fehlerhafte Zustände produzieren. Darüber hinaus versagt konventionelle Redundanz häufig beim Erkennen spezifischer Klassen von Softwarefehlern (z. B. nicht initialisierte Zeiger, Überschreibungen von Rückkehradressen) oder von Compiler-/Linking-Fehlern, die sich über alle Replikate hinweg identisch manifestieren.

Methodik

Der Artikel schlägt Divergente Multi-Version-Ausführung (DME) vor, einen Laufzeit-Semantik-Konsistenzverifizierer, der entwickelt wurde, um korrelierte Fehler zu erkennen, indem sichergestellt wird, dass identische numerische Störungen zu semantisch divergenten Ausführungspfaden führen.

Grundprinzipien

DME arbeitet auf vier fundamentalen Prinzipien, die zur Compile-Zeit durchgesetzt werden:

Unabhängige Kompilierung: $N$ Replikate werden unabhängig voneinander aus demselben Quellcode kompiliert. Dies erzeugt unterschiedliche physische Code- und Datenspeicherlayouts, während die semantische Identität auf Opcode-Ebene und isomorphe Kontrollflussgraphen erhalten bleiben.
Grobrasterige Dekorrelation: Funktionen und Grundblöcke werden unter Verwendung komplementärer Verzweigungsverschiebungsmuster an unterschiedlichen Adressen über die Replikate verteilt platziert (z. B. werden Vorwärtsverzweigungen in einem Replikat zu Rückwärtsverzweigungen in einem anderen). Dies stellt sicher, dass identische Kontrollflussstörungen auf semantisch unterschiedliche Pfade abbilden.
Feinstrukturelle Dekorrelation: Periodische NOP-Anweisungen werden an replikatspezifischen Versatzstellen eingefügt ( $offset_r = \frac{l}{N} \cdot r$ ). Dies erzeugt einen minimalen räumlichen Abstand zwischen entsprechenden logischen Anweisungen und ermöglicht die Erkennung von Störungen mit geringer Magnitude des Programmcounters (PC).
Datenadressen-Dekorrelation: Globale Variablen, Stack-Frames und Heap-Allokationen erhalten für jedes Replikat eindeutige absolute Basisadressen.

Fehlererkennungsmechanismen

DME setzt eine zweischichtige Erkennungsstrategie ein:

Semantische Schicht (Kanonischer Anweisungsverlauf):
- Das System vergleicht „kanonische Verläufe" über die Replikate hinweg. Ein kanonischer Verlauf umfasst Opcodes, Registerkennungen, unmittelbare Operanden, geladene/gespeicherte Werte und berechnete Ergebnisse.
- Entscheidend ist, dass absolute Adressen aus dem Verlauf ausgeschlossen sind.
- Bei fehlerfreier Ausführung produzieren alle Replikate identische kanonische Verläufe. Jeder Fehler, der die Ausführungsssemantik verändert (z. B. die Ausführung einer anderen Anweisung oder die Berechnung eines anderen Ergebnisses), führt zu einer Divergenz des Verlaufs.
Strukturelle Schicht (Adressraum-Dekorrelation & Nicht-Aliasing):
- DME betrachtet die Gleichheit physischer Adressen (z. B. $PC_1 = PC_2 = \dots = PC_N$ ) über die Replikate hinweg als Verletzung der strukturellen Unabhängigkeit und nicht als zulässigen Zustand.
- Invariant der Adressen-Nicht-Aliasing: Das System erzwingt, dass semantisch entsprechende Speicherzugriffe (Daten oder Anweisungen) über die Replikate hinweg unterschiedliche effektive Adressen anvisieren müssen.
- Wenn ein Fehler (z. B. Pufferüberlauf oder Dereferenzierung eines Nullzeigers) dazu führt, dass alle Replikate dieselbe fehlerhafte Adresse berechnen, löst das System sofort einen Fehler aus. Dies ermöglicht die Erkennung von Zeigerkorruptionen und Überschreibungen von Rückkehradressen, bevor eine semantische Divergenz eintritt.

Fehlermodelle und Erkennungsregime

Der Artikel kategorisiert die Erkennungsgarantien basierend auf der Art der Störung:

Deterministische Erkennung:
- Gilt für vollständig korrelierte Fehler, bei denen $\Delta PC$ über alle Replikate hinweg identisch ist.
- Wenn $|\Delta PC| \geq l/N$ gilt (wobei $l$ die NOP-Einfügungsstrecke ist), führt die Störung garantiert dazu, dass mindestens ein Replikat eine andere logische Anweisung ausführt, was zu einer sofortigen Verlaufsdivergenz führt.
- Ein Zusammenbruch des Adressraums (identische PCs oder Zeiger) wird sofort als strukturelle Verletzung erkannt.
Probabilistische Erkennung:
- Gilt für teilweise korrelierte Fehler (bei denen $\Delta PC$ über die Replikate hinweg variiert) oder Fehler, bei denen $|\Delta PC| < l/N$ ist.
- Die Erkennung basiert auf der geringen Wahrscheinlichkeit, dass Replikate zufällig auf dieselbe logische Anweisung ausgerichtet werden und identische Ergebnisse produzieren.
- Die Wahrscheinlichkeit, für $k$ Schritte unentdeckt zu bleiben, ist durch $(\frac{C}{|S|} \cdot \epsilon)^k$ begrenzt, wobei $C$ die Anzahl der kanonisch äquivalenten Anweisungen, $|S|$ der gesamte Anweisungsraum und $\epsilon$ die Wahrscheinlichkeit identischer Ergebnisse ist. Für typische 32-Bit-ISAs klingt diese Wahrscheinlichkeit exponentiell ab (z. B. $\epsilon \leq 2^{-52}$ ).

Hauptbeiträge

Strukturelle Adressraum-Dekorrelation: Der Artikel stellt eine Methode vor, um korrelierte Low-Level-Störungen in beobachtbare semantische Divergenzen umzuwandeln, indem während der Kompilierung Speicherlayouts und Verzweigungsverschiebungen aktiv diversifiziert werden.
Überwachung kanonischer Verläufe: Es wird eine layoutunabhängige Verlaufsrepräsentation definiert, die die semantische Ausführung (Opcodes, Register, Ergebnisse) erfasst, während adressabhängige Informationen verworfen werden, was einen robusten Vergleich über verschiedene Binärdateien hinweg ermöglicht.
Zweischichtige Erkennung: DME kombiniert den semantischen Verlaufsvergleich mit der strukturellen Adressüberwachung. Dies ermöglicht die sofortige Erkennung von „Adresszusammenbruch"-Ereignissen (z. B. identische Rückkehradressen), die traditionelle Redundanz möglicherweise übersehen würde, wenn der resultierende Ausführungspfad zufällig identisch ist.
Formales Korrektheitsmodell: Der Artikel unterscheidet zwischen Laufzeit-Semantikkorrektheit (Gleichheit der Verläufe) und Systemkorrektheit (semantische Gleichheit + strukturelle Unabhängigkeit). Er beweist formal, dass strukturelle Unabhängigkeit eine hinreichende Bedingung ist, um die Beobachtbarkeit korrelierter Fehler zu garantieren.

Ergebnisse und Behauptungen

Der Artikel behauptet, dass DME Folgendes bietet:

Deterministische Erkennung für korrelierte PC-Fehler, bei denen die Störungsmagnitude die Dekorrelationsstrecke übersteigt ( $|\Delta PC| \geq l/N$ ).
Probabilistische Erkennung mit exponentieller Abklingrate für andere Fehlertypen, begrenzt durch den Zustandsraum der Befehlssatzarchitektur.
Sofortige Erkennung von Verletzungen der Zeigerssemantik (z. B. Nullzeiger, Fehler bei der Behandlung von Werten als Zeiger) über die Invariant der Adressen-Nicht-Aliasing, oft früher als eine semantische Divergenz.
Praktische Machbarkeit: Die Autoren zitieren eine Prototyp-Implementierung auf einem 32-Bit-Soft-Prozessor (3o|||sheet), der auf einem Altera Cyclone IV FPGA läuft, sowie eine Virtual-Machine-Implementierung auf einem Cortex-M-Kern, und zeigen, dass der Overhead beherrschbar ist (z. B. 3000 LUTs und 16 KB BRAM pro Replikat).

Bedeutung

Der Artikel positioniert DME als Neudefinition von Redundanz für sicherheitskritische eingebettete Systeme. Im Gegensatz zu Multi-Variant Execution Environments (MVEE), die Diversifizierung hauptsächlich nutzen, um die Portierbarkeit von Ausnutzungen zu erschweren, verwendet DME strukturelle Dekorrelation als formale Laufzeit-Korrektheitsinvariante, um Bit-für-Bit-Korruptionen zu erkennen, die durch physikalische Störungen verursacht werden.

Die Autoren betonen, dass DME eine spezifische Lücke in der bestehenden Fehlertoleranz adressiert: die Unfähigkeit konventioneller Redundanz, korrelierte Störungen auf Anweisungsebene zu erkennen, die die Zustandsgleichheit bewahren, aber die Programmssemantik verletzen. Durch die Durchsetzung struktureller Unabhängigkeit stellt DME sicher, dass identische numerische Fehler nicht zu identischem logischem Verhalten führen können, wodurch Risiken einer stillen Datenkorruption in nachweisbare Ereignisse umgewandelt werden. Die Arbeit wird als hardwareunabhängiger, formal analysierbarer Mechanismus präsentiert, der für Umgebungen geeignet ist, in denen elektromagnetische oder umweltbedingte Fehlerinjektion eine realistische Bedrohung darstellt.