💻 computer science

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

Dit artikel introduceert Divergent Multi-Version Execution (DME), een runtime-foutdetectietechniek die replica's compileert met onafhankelijke geheugenindelingen om gecorreleerde fouten te neutraliseren en de uitvoeringscorrectie verifieert door canonieke instructiesporen te vergelijken terwijl adresafhankelijke waarden worden genegeerd.

Oorspronkelijke auteurs: Petro Baran Yrievich

Gepubliceerd 2026-05-14

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Petro Baran Yrievich

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een race met hoge inzet loopt met drie identieke tweelingen. In een traditionele race (wat het artikel "conventionele redundantie" noemt) geef je alle drie de tweelingen exact dezelfde kaart, exact dezelfde schoenen en exact dezelfde route. Ze lopen naast elkaar en je controleert of ze samen de finish bereiken.

Het Probleem:
Als een plotselinge, krachtige windstoot (een "gecorreleerde fout") alle drie de tweelingen op exact hetzelfde moment raakt, waardoor ze allemaal even ver van het pad worden geduwd, zullen ze allemaal op exact dezelfde manier struikelen. Ze zullen allemaal dezelfde verkeerde afslag nemen, in dezelfde greppel vallen, en je zou misschien nooit merken dat ze een fout hebben gemaakt omdat ze allemaal "akkoord gaan" met het verkeerde pad. Dit is vergelijkbaar met een computerfout waarbij een enkele elektromagnetische puls de hersenen van alle drie de processors tegelijk verstoort, waardoor ze stilzwijgend data corrumperen.

De Oplossing: Divergente Multi-Versie Executie (DME)
Het artikel stelt een nieuwe manier van racen voor. In plaats van de tweelingen dezelfde kaart te geven, geef je ze verschillende kaarten die naar dezelfde bestemming leiden.

Hier is hoe DME werkt, opgesplitst in eenvoudige concepten:

1. De "Verschillende Kaarten"-Strategie (Structurele Decorrelatie)

Voordat de race begint, maakt het systeem drie kopieën van het programma. Deze worden echter verschillend gecompileerd:

Verschillende Indelingen: In Kopie A bevindt de "Keuken" zich links. In Kopie B bevindt de "Keuken" zich rechts. In Kopie C bevindt deze zich in de kelder.
Verschillende Tempo's: Het systeem voegt op verschillende plekken in elke kopie kleine pauzes in (genaamd NOP's of "No Operation"-instructies). Kopie A pauzeert na stap 3; Kopie B pauzeert na stap 4.
Omgekeerde Bochten: Als de code zegt "Sla linksaf", is Kopie A geprogrammeerd om een linkse bocht te nemen die fysiek op adres 100 ligt. Kopie B is geprogrammeerd om een linkse bocht te nemen die fysiek op adres 500 ligt.

Het Resultaat: Hoewel de tweelingen exact dezelfde logica uitvoeren (een maaltijd bereiden), doen ze dit fysiek op verschillende plaatsen en op iets verschillende tijdstippen.

2. De "Wat Je deed, Niet Waar Je Het deed"-Controle (Canonieke Traces)

Tijdens de race geeft de scheidsrechter niets om de straatadressen (geheugenadressen). De scheidsrechter geeft alleen om de acties.

Heb je de uien gesneden?
Heb je het water gekookt?
Heb je het resultaat "Soep" gekregen?

Het systeem verwijdert het "waar" (het specifieke geheugenadres) en vergelijkt alleen het "wat" (de instructie en het resultaat). Zolang alle drie de tweelingen uien snijden en water koken, zijn ze in orde.

3. Het Opvangen van de "Windstoot" (Foutdetectie)

Stel je nu voor dat die windstoot opnieuw toeslaat.

In het oude systeem: Alle drie de tweelingen worden 5 meter naar rechts geduwd. Ze belanden allemaal op exact dezelfde verkeerde plek.
In het DME-systeem: Omdat hun kaarten verschillend zijn, betekent een duw van "5 meter naar rechts" iets totaal anders voor elke tweeling.
- Tweeling A (die bij een muur was) botst tegen de muur en stopt.
- Tweeling B (die bij een deur was) valt door de deur.
- Tweeling C (die bij een tuin was) stapt in een bloembed.

De scheidsrechter kijkt naar hun acties: "Tweeling A stopte, Tweeling B viel, Tweeling C stapte." Ze doen niet langer hetzelfde! De scheidsrechter schreeuwt direct: "Er is iets mis!" en stopt de race.

4. Het "Dubbelcheck"-Veiligheidsnet

Het artikel introduceert een slimme tweede veiligheidslaag genaamd Adres Non-Aliasing.

Bij een normale race, als alle drie de tweelingen plotseling besluiten naar exact dezelfde coördinaat te rennen (bijvoorbeeld omdat ze allemaal verward raken en naar "0,0" rennen), is dat een enorm rood vlaggetje.
Bij DME is het, omdat de kaarten verschillend zijn, onmogelijk dat ze op natuurlijke wijze naar dezelfde coördinaat rennen, tenzij er iets kapot is.
Als de scheidsrechter ziet dat alle drie de tweelingen naar exact hetzelfde adres wijzen (zoals een beschadigd retouradres of een null-pointer), wordt er direct een alarm geactiveerd, zelfs voordat wordt gecontroleerd of ze de juiste acties uitvoeren. Dit vangt specifieke soorten softwarefouten (zoals "null-pointer"-fouten) direct op.

De Twee Soorten Garanties

Het artikel claimt twee niveaus van veiligheid:

De "Garandeerde" Vangst (Deterministisch): Als de wind de tweelingen met een specifieke, grote hoeveelheid duwt (groter dan de ingevoegde kleine pauzes), is het systeem 100% gegarandeerd om de fout direct op te vangen. De tweelingen zullen zeker verschillende dingen doen.
De "Bijna Zekere" Vangst (Probabilistisch): Als de wind hen met een kleine hoeveelheid duwt, of als de wind hen verschillend raakt, is er een heel klein, heel klein kansje dat ze per ongeluk hetzelfde verkeerde ding doen. De wiskunde toont echter aan dat deze kans zo klein is (zoals meerdere keren op rij de loterij winnen) dat het voor alle praktische doeleinden nooit zal gebeuren.

Samenvatting

DME is vergelijkbaar met het inhuren van drie chefs om hetzelfde recept te koken, maar ze krijgen:

Verschillende keukens met verschillende indelingen.
Verschillende timers.
Verschillende gereedschappen die op verschillende plekken staan.

Als er een stroomstoring is of een plagerig iemand de keuken verstoort, zullen de chefs verschillend reageren omdat hun omgevingen verschillend zijn. Door te vergelijken wat ze hebben gekookt (het resultaat) in plaats van waar ze stonden, kan het systeem direct opmerken of een glitch het proces heeft verstoord, zelfs als de glitch alle drie de chefs op exact hetzelfde moment heeft geraakt.

Deze methode is specifiek ontworpen voor ingebouwde systemen (zoals de hersenen van auto's of medische apparaten) waar een enkele glitch gevaarlijk kan zijn, en waar traditionele "drie-voudige redundantie" (drie identieke computers) kan falen om te merken als ze allemaal door dezelfde glitch worden geraakt.

Technische Samenvatting: Divergente Multi-Versie Executie (DME)

Probleemstelling

Traditionele redundantiemechanismen, zoals lockstep-executie en Triple Modular Redundancy (TMR), vertrouwen op het uitvoeren van identieke binaries met identieke geheugenindelingen. Hoewel deze systemen effectief zijn tegen onafhankelijke fouten, zijn ze kwetsbaar voor gecorreleerde fouten. Experimentele studies (bijv. Dutertre et al.) hebben aangetoond dat fysieke storingen, zoals elektromagnetische foutinjectie, identieke verstoringen (bijv. een specifieke $\Delta PC$ ) kunnen induceren over alle replica's tegelijkertijd. In conventionele systemen leiden dergelijke gecorreleerde verstoringen ertoe dat alle replica's worden omgeleid naar hetzelfde onjuiste uitvoeringspad, wat resulteert in stille datacorruptie die onopgemerkt blijft omdat alle replica's identieke foutieve toestanden produceren. Bovendien faalt conventionele redundantie vaak om specifieke klassen van softwarebugs (bijv. niet-geinitialiseerde pointers, overschrijven van retouradressen) of compiler-/koppelingsfouten te detecteren die zich identiek manifesteren over replica's.

Methodologie

Het artikel stelt Divergente Multi-Versie Executie (DME) voor, een runtime semantische consistentieverificator die is ontworpen om gecorreleerde fouten te detecteren door ervoor te zorgen dat identieke numerieke verstoringen leiden tot semantisch divergente uitvoeringspaden.

Kernprincipes

DME werkt op vier fundamentele principes die tijdens het compileren worden afgedwongen:

Onafhankelijke Compilatie: $N$ replica's worden onafhankelijk gecompileerd vanuit dezelfde broncode. Dit produceert verschillende fysieke code- en data-geheugenindelingen terwijl identieke opcode-niveau semantiek en isomorfe controleflowgrafieken behouden blijven.
Grofkorrelige Decorrelatie: Functies en basisblokken worden op verschillende adressen geplaatst over replica's met behulp van complementaire takverplaatsingspatronen (bijv. worden voorwaartse takken in de ene replica achterwaartse takken in een andere). Dit zorgt ervoor dat identieke controleflowverstoringen worden gemapt naar semantisch verschillende paden.
Fijnkorrelige Decorrelatie: Periodieke NOP-instructies worden ingevoegd op replica-specifieke offsets ( $offset_r = \frac{l}{N} \cdot r$ ). Dit creëert een minimale ruimtelijke scheiding tussen overeenkomstige logische instructies, waardoor detectie mogelijk is van verstoringen van de Program Counter (PC) met kleine grootte.
Data-adres Decorrelatie: Globale variabelen, stackframes en heap-toewijzingen krijgen unieke absolute basisadressen toegewezen voor elke replica.

Foutdetectiemechanismen

DME hanteert een tweelaags detectiestrategie:

Semantische Laag (Canonieke Instructietrace):
- Het systeem vergelijkt "canonieke traces" over replica's. Een canonieke trace bevat opcodes, registeridentificatoren, directe operanden, geladen/opgeslagen waarden en berekende resultaten.
- Cruciaal zijn absolute adressen uitgesloten van de trace.
- Bij foutvrije uitvoering produceren alle replica's identieke canonieke traces. Elke fout die de uitvoersemantiek verandert (bijv. het uitvoeren van een andere instructie of het berekenen van een ander resultaat) veroorzaakt trace-divergentie.
Structurele Laag (Adresruimte-Decorrelatie & Non-Aliasing):
- DME behandelt de gelijkheid van fysieke adressen (bijv. $PC_1 = PC_2 = \dots = PC_N$ ) over replica's als een schending van structurele onafhankelijkheid, in plaats van een toelaatbare staat.
- Adres Non-Aliasing Invariant: Het systeem dwingt af dat semantisch overeenkomstige geheugentoegang (data of instructies) verschillende effectieve adressen moeten targeten over replica's.
- Als een fout (bijv. bufferoverloop of null-pointer dereferentie) ervoor zorgt dat alle replica's hetzelfde foutieve adres berekenen, activeert het systeem onmiddellijk een foutmelding. Dit maakt detectie mogelijk van pointercorrupties en overschrijven van retouradressen voordat semantische divergentie optreedt.

Foutmodellen en Detectieregimes

Het artikel categoriseert detectiegaranties op basis van de aard van de verstoring:

Deterministische Detectie:
- Geldt voor volledig gecorreleerde fouten waarbij $\Delta PC$ identiek is over alle replica's.
- Als $|\Delta PC| \geq l/N$ (waarbij $l$ de NOP-invoegstap is), wordt gegarandeerd dat de verstoring ten minste één replica ertoe brengt een andere logische instructie uit te voeren, wat leidt tot onmiddellijke trace-divergentie.
- Ineenstorting van de adresruimte (identieke PC's of pointers) wordt onmiddellijk gedetecteerd als een structurele schending.
Probabilistische Detectie:
- Geldt voor gedeeltelijk gecorreleerde fouten (waarbij $\Delta PC$ verschilt over replica's) of fouten waarbij $|\Delta PC| < l/N$ .
- Detectie berust op de lage waarschijnlijkheid dat replica's per ongeluk aligneren naar dezelfde logische instructie en identieke resultaten produceren.
- De waarschijnlijkheid om $k$ stappen ongedetecteerd te blijven, is begrensd door $(\frac{C}{|S|} \cdot \epsilon)^k$ , waarbij $C$ het aantal canoniek equivalent instructies is, $|S|$ de totale instructieruimte is, en $\epsilon$ de waarschijnlijkheid van identieke resultaten. Voor typische 32-bit ISA's neemt deze waarschijnlijkheid exponentieel af (bijv. $\epsilon \leq 2^{-52}$ ).

Belangrijkste Bijdragen

Structurele Adresruimte-Decorrelatie: Het artikel introduceert een methode om gecorreleerde low-level verstoringen om te zetten in waarneembare semantische divergentie door actief geheugenindelingen en takverplaatsingen tijdens het compileren te diversifiëren.
Canonieke Trace Monitoring: Het definieert een lay-outonafhankelijke trace-representatie die semantische uitvoering vastlegt (opcodes, registers, resultaten) terwijl adresafhankelijke informatie wordt weggegooid, waardoor robuuste vergelijking mogelijk is over diverse binaries.
Tweelaags Detectie: DME combineert semantische tracevergelijking met structureel adresmonitoring. Dit maakt onmiddellijke detectie mogelijk van "adresinstorting"-gebeurtenissen (bijv. identieke retouradressen) die traditionele redundantie zou kunnen missen als het resulterende uitvoeringspad toevallig identiek is.
Formeel Correctheidsmodel: Het artikel onderscheidt tussen runtime semantische correctheid (gelijkheid van traces) en systeemniveau correctheid (semantische gelijkheid + structurele onafhankelijkheid). Het bewijst formeel dat structurele onafhankelijkheid een voldoende voorwaarde is om de waarneembaarheid van gecorreleerde fouten te garanderen.

Resultaten en Beweringen

Het artikel beweert dat DME biedt:

Deterministische detectie voor gecorreleerde PC-fouten waarbij de verstoringsgrootte de decorrelatiestap overschrijdt ( $|\Delta PC| \geq l/N$ ).
Probabilistische detectie met exponentiële afname voor andere fouttypen, begrensd door de toestandsruimte van de instructiestructuur.
Onmiddellijke detectie van pointersemantiek-schendingen (bijv. null-pointers, waarde-als-pointer-fouten) via de Adres Non-Aliasing Invariant, vaak eerder dan semantische divergentie.
Praktische Haalbaarheid: De auteurs citeren een prototype-implementatie op een 32-bit soft processor (3o|||sheet) die draait op een Altera Cyclone IV FPGA, en een Virtual Machine-implementatie op een Cortex-M-kern, wat aantoont dat de overhead beheersbaar is (bijv. 3000 LUTs en 16 KB BRAM per replica).

Betekenis

Het artikel positioneert DME als een herdefiniëring van redundantie voor veiligheidskritieke ingebouwde systemen. In tegenstelling tot Multi-Variant Execution Environments (MVEE), die voornamelijk diversificatie gebruiken om exploit-portabiliteit te bemoeilijken, gebruikt DME structurele decorrelatie als een formeel runtime correctheidsinvariant om bit-niveau corrupties veroorzaakt door fysieke storingen te detecteren.

De auteurs benadrukken dat DME een specifiek gat in bestaande fouttolerantie aanpakt: het onvermogen van conventionele redundantie om gecorreleerde instructieniveau-verstoringen te detecteren die staatsgelijkheid behouden maar programmasemantiek schenden. Door structurele onafhankelijkheid af te dwingen, zorgt DME ervoor dat identieke numerieke fouten niet kunnen leiden tot identiek logisch gedrag, waardoor risico's op stille datacorruptie worden omgezet in detecteerbare gebeurtenissen. Het werk wordt gepresenteerd als een hardware-onafhankelijk, formeel analyseerbaar mechanisme dat geschikt is voor omgevingen waar elektromagnetische of omgevingsfoutinjectie een realistische bedreiging vormt.