Upload
sonje-aber
View
108
Download
2
Embed Size (px)
Citation preview
Automatische Erzeugung und Bewertung virtueller Duplexsysteme zur Erkennung von Betriebsfehlern in
Mikroprozessoren
Markus Jochim
Fehlererkennung durch VDS
Einführung
DIVERSI-Module
Automatische
Diversität
Optimierung
Fehler-Injektion
Resultate
Pessimistische
Injektion
Zusammen-fassung
Seite 2Verlässlichkeit von RechensystemenInstitut für Informatik und WirtschaftsinformatikUniversität Duisburg-Essen
Annahme:In Abwesenheit von Soft- und
Hardwarefehlern gilt: f1 = f2 = f1,2 = f
Ziel:Berechnung von f(E) bzw. Fehlererkennung mit einem Rechenknoten K.
Unerkannte Wertefehler:
f1(E) = f2(E) = f1,2(E) aber f1,2(E) f(E)
V1
Knoten K
Eingabe E
V2
Maskierer
f2(E)
Einstimmig-keits-
entscheidung Fehlermeldungf1,2(E) oder
f1(E)
Virtuelles Duplexsystem (VDS)(Zielfunktion f)
Systemüberlistung
Ablauf im VDS:
1) Ausführung V1
2) Ausführung V2
3) Maskierer
V1 V2
Prozessor
Fehlererkennung durch VDS
Einführung
DIVERSI-Module
Automatische
Diversität
Optimierung
Fehler-Injektion
Resultate
Pessimistische
Injektion
Zusammen-fassung
Seite 3Verlässlichkeit von RechensystemenInstitut für Informatik und WirtschaftsinformatikUniversität Duisburg-Essen
V1
Knoten K
Eingabe E
V2
Maskierer
f2(E)
Einstimmig-keits-
entscheidung Fehlermeldungf1,2(E) oder
f1(E)
Virtuelles Duplexsystem (VDS)(Zielfunktion f)
Fehlerart Gegenmittel
HW-Fehler(temporär)
HW-Fehler(permanent)
SW-Fehler
Zeitredundanz
Diversität
Entwurfsdiversität
Source 1 Source 2
!
Ziele dieser Arbeit ?
Diversität aufKnopfdruck
Hauptziel . . .
Einführung
DIVERSI-Module
Automatische
Diversität
Optimierung
Fehler-Injektion
Resultate
Pessimistische
Injektion
Zusammen-fassung
Seite 4Verlässlichkeit von RechensystemenInstitut für Informatik und WirtschaftsinformatikUniversität Duisburg-Essen
Ziele:
• Vollautomatische Diversifizierung auf Assemblerebene
• Automatische zielgerichtete Suche wirksamer Diversitäts-Kombinationen
• Experimentelle Bewertung automatisch erzeugter VDSe
• Kombination: „Automatische Diversität + Entwurfsdiversität“
• Pessimistische Fehlerinjektion
Ziele und Gliederung . . .
Einführung
DIVERSI-Module
Automatische
Diversität
Optimierung
Fehler-Injektion
Resultate
Pessimistische
Injektion
Zusammen-fassung
Seite 5Verlässlichkeit von RechensystemenInstitut für Informatik und WirtschaftsinformatikUniversität Duisburg-Essen
DIVERSI-Module
Gliederung:
AutomatischeDiversität
Optimierung
Fehler-Injektion,Resultat
Resultat
PessimistischeInjektion
Bei Bedarf !
DIVERSI-Tool
Einführung
DIVERSI-Module
Automatische
Diversität
Optimierung
Fehler-Injektion
Resultate
Pessimistische
Injektion
Zusammen-fassung
Seite 6Verlässlichkeit von RechensystemenInstitut für Informatik und WirtschaftsinformatikUniversität Duisburg-Essen
Optimierer
Modifizierer Fehlerinjektor
Testeingaben Fehlerspezifikation
Initiales System(keine Diversität)
Optimiertes System(diversitäres VDS)
Veränderungsregeln
Veränderungsregeln
Einführung
DIVERSI-Module
Automatische
Diversität
Optimierung
Fehler-Injektion
Resultate
Pessimistische
Injektion
Zusammen-fassung
Seite 7Verlässlichkeit von RechensystemenInstitut für Informatik und WirtschaftsinformatikUniversität Duisburg-Essen
Anwendung derRegel R auf V2
Beispiel:
VDS ( V1, V2R )
VDS (V1,V2)
Instr. a
Instr. d
Instr. a
Instr. c
Instr. b‘1Instr. b‘2Instr. b‘3
Instr. b‘1Instr. b‘2Instr. b‘3
Instr. a
Instr. b
Instr. d
Instr. a
Instr. b
Instr. c
Variante V2 Variante V2R
Regel R
Ersetze„Instr. b“
Veränderungsregeln
Einführung
DIVERSI-Module
Automatische
Diversität
Optimierung
Fehler-Injektion
Resultate
Pessimistische
Injektion
Zusammen-fassung
Seite 8Verlässlichkeit von RechensystemenInstitut für Informatik und WirtschaftsinformatikUniversität Duisburg-Essen
Instr. a
Instr. d
Instr. a
Instr. c
Instr. b‘1Instr. b‘2Instr. b‘3
Instr. b‘1Instr. b‘2Instr. b‘3
Instr. a
Instr. b
Instr. d
Instr. a
Instr. b
Instr. c
Variante V2 Variante V2R
Regel R
Variante V2R,R‘
Regel R‘
Register-permutation
Ersetze„Instr. b“
Implementierte Veränderungsregeln
Einführung
DIVERSI-Module
Automatische
Diversität
Optimierung
Fehler-Injektion
Resultate
Pessimistische
Injektion
Zusammen-fassung
Seite 9Verlässlichkeit von RechensystemenInstitut für Informatik und WirtschaftsinformatikUniversität Duisburg-Essen
• Explizite Adressberechnungen• Arithmetische Befehle ersetzen• Zerschneiden und umsortieren• Registerpermutation• Logische Befehle ersetzen (z.B. deMorgan)• Diversitäre Daten• Registertests• Stackoperationen ersetzen• Bedingte / unbedingte Sprünge
• . . .
Σ: 27 Regeln
Zyklus1
Zyklus2
Zyklus3
Gierige Optimierung
Einführung
DIVERSI-Module
Automatische
Diversität
Optimierung
Fehler-Injektion
Resultate
Pessimistische
Injektion
Zusammen-fassung
Seite 10Verlässlichkeit von RechensystemenInstitut für Informatik und WirtschaftsinformatikUniversität Duisburg-Essen
V11 V1
2 V1r
V21 V 2
2 V2r
V31 V3
2 V3r
V0
R1 R2 Rr
R1 R2 Rr
R1 R2 Rr
. . .
. . .
. . .
Injektionstechnik
Einführung
DIVERSI-Module
Automatische
Diversität
Optimierung
Fehler-Injektion
Resultate
Pessimistische
Injektion
Zusammen-fassung
Seite 11Verlässlichkeit von RechensystemenInstitut für Informatik und WirtschaftsinformatikUniversität Duisburg-Essen
Haupt-Anforderungen: • Schnelle Injektion• Injektion permanenter Fehler• Breites Spektrum von Fehlerarten
Zwei SWIFI-Techniken:
1) Einbringen von Inj-Code in Assembler-Code des zu bewertenden Programmes
2) Injektion durch Modifikation ausführbarer Programme
Beispiele zu injizierender Fehler:
Haftfehler in Registern, Übersprechen zwischen Registern,
Fehlerhaftes Inkrementieren des Stackpointers, Fehler im
Statuswort, Fetch-Fehler, Speichertransfer-Fehler, Fehler
bei der Ausführung von ALU-Operationen, Fehler
beim Schieben, Decodierungsfehler, . . .
Σ: 49 Fehlerarten
FAIL-Spezifikationen
Einführung
DIVERSI-Module
Automatische
Diversität
Optimierung
Fehler-Injektion
Resultate
Pessimistische
Injektion
Zusammen-fassung
Seite 12Verlässlichkeit von RechensystemenInstitut für Informatik und WirtschaftsinformatikUniversität Duisburg-Essen
EndAllEndAll
All myVar3 substitute by {Carry,Zero,Sign,Overflow} All myVar4 substitute by {cleared, inverted, set}
All myVar1 substitute by {%eax,%ecx,%edx,%edi,%ebp} All myVar2 substitute by {0,1,2,6,7,8,9,15,16,22,23,28,31}
Stuck-at dice{0,1} Bit myVar2 Register myVar1
EndAllEndAll
EndallEndall
All myVar5 substitute by {text,rodata} All myVar6 substitute by {1,3,5,9,20,30,40,50,60,75,95,100,200,300}
FlagProblemAfter dice {addl, subl, cmpl} Instruction myVar3 is myVar4
MemoryError randomly inject myVar5 Errors into myVar6 Segment
Haftfehler inRegistern
Statuswort-Verfälschung
Speicherfehler
Einführung neuer Fehlerarten
Einführung
DIVERSI-Module
Automatische
Diversität
Optimierung
Fehler-Injektion
Resultate
Pessimistische
Injektion
Zusammen-fassung
Seite 13Verlässlichkeit von RechensystemenInstitut für Informatik und WirtschaftsinformatikUniversität Duisburg-Essen
All cc substitute by {o,no,b,ae,e,ne,be,a,s,ns,p,np,l,ge,le,g} Condition-action: Conditions instr_found = statement,"movl" s_register = sMode,"gpr" s_memory = sMode,"memoryOperand" d_register = dMode,"gpr" End-Conditions
Conjunctions r32_r32 = instr_found & s_register & d_register m32_r32 = instr_found & s_memory & d_register End-Conjunctions
Trigger: r32_r32 | m32_r32
Action (r32_r32 | m32_r32): "CMOVccL "source","dest End-Action End-Condition-Action EndAll
Neue Fehlerart:
„Fehlerbedingte Aktivierung derCondition-Unit bei Ausführung
von Datentransfer-Befehlen“
Experimentaufbau
Einführung
DIVERSI-Module
Automatische
Diversität
Optimierung
Fehler-Injektion
Resultate
Pessimistische
Injektion
Zusammen-fassung
Seite 14Verlässlichkeit von RechensystemenInstitut für Informatik und WirtschaftsinformatikUniversität Duisburg-Essen
• 9 DIVERSI-Experimente (bintree, hanoi, quicksort, crc_table, crc,...) • FAIL-Spezifikation: 49 verschiedene Fehlerarten, 4788 Fehler
• Pro VDS: 4788 Fehler · 5 Programmeingaben = 23940 FI-Experimente
• Ø 244 VDSe pro DIVERSI-Experiment:
9 · 244 · 23940 = 5,26 · 107 FI-Experimente
• Reduktion des Rechenaufwandes:
- Vermeidung absehbarer Injektionen- Vorgezogene Injektion erfolgreicher Fehler=> Einsparung von 97,27% aller FI-Experimente
ca. 1,72Prozessor-
Jahre !( P3, 500 MHz )
ca. 17Prozessor-
Tage
0
500
1000
1500
2000
2500
3000
3500
1 2 3 4 5 6 7 8 9 10 110
500
1000
1500
2000
2500
3000
3500
1 2 3 4 5 6 7 8 9 10 11
hexint arraywrk
adder crc_table
Systemüberlistungen im Verlauf der Optimierung
Einführung
DIVERSI-Module
Automatische
Diversität
Optimierung
Fehler-Injektion
Resultate
Pessimistische
Injektion
Zusammen-fassung
Seite 15Verlässlichkeit von RechensystemenInstitut für Informatik und WirtschaftsinformatikUniversität Duisburg-Essen
Überlistungen
Opt.-Zyklus
Überlistungen
Opt.-Zyklushanoi quicksort
bubblesortbintree crc
0
500
1000
1500
2000
2500
3000
3500
1 2 3 4 5 6 7 8 9 10 110
500
1000
1500
2000
2500
3000
3500
1 2 3 4 5 6 7 8 9 10 11
Systemüberlistungen im Verlauf der Optimierung
Einführung
DIVERSI-Module
Automatische
Diversität
Optimierung
Fehler-Injektion
Resultate
Pessimistische
Injektion
Zusammen-fassung
Seite 16Verlässlichkeit von RechensystemenInstitut für Informatik und WirtschaftsinformatikUniversität Duisburg-Essen
PGefahr = 1823 Überlistungen
23940 Fehler= 7,61%
Beispiel: „PGefahr für ein initiales System“
PGefahr = 23 Überlistungen
23940 Fehler
Zugehöriges optimiertes System:
= 0,09%
PGefahr für initiale Systeme = 8,41%
PGefahr für optimierte Systeme = 0,15%
Sicherheitsgewinnum Faktor 56
Kombination mit Entwurfsdiversität
Einführung
DIVERSI-Module
Automatische
Diversität
Optimierung
Fehler-Injektion
Resultate
Pessimistische
Injektion
Zusammen-fassung
Seite 17Verlässlichkeit von RechensystemenInstitut für Informatik und WirtschaftsinformatikUniversität Duisburg-Essen
0
100
200
300
400
500
1 2 3 4 5 6 7 8 9 10 11
crc/crc_table crc_table/crc
quick/bubble bubble/quick
+ Faktor 4 Faktor 56
+ weniger Opt.-Zyklen
+ evtl. Erkennung von Softwarefehlern
Ø PGefahr für initiale
Systeme = 1,94%
Ø PGefahr für optimierte
Systeme = 0,00%
Überlistungen
Opt.-Zyklus
Pessimistische Injektion
Einführung
DIVERSI-Module
Automatische
Diversität
Optimierung
Fehler-Injektion
Resultate
Pessimistische
Injektion
Zusammen-fassung
Seite 18Verlässlichkeit von RechensystemenInstitut für Informatik und WirtschaftsinformatikUniversität Duisburg-Essen
Beobachtung: Ca. 90% aller (zeitaufwendig) injizierten Fehler sind zurSystemüberlistung grundsätzlich ungeeignet.
Idee der pessimistischen Injektion: Absenkung des Anteils der zur Systemüberlistung grundsätzlichungeeigneten Fehler.
Effekt: Mehr Injektionen mit Überlistungspotential =>Strengere Systembewertungen bei gleichem Zeitbedarf.
Nennung der Grundidee . . . . . . mehr bei Bedarf !
Zusammenfassung
Einführung
DIVERSI-Module
Automatische
Diversität
Optimierung
Fehler-Injektion
Resultate
Pessimistische
Injektion
Zusammen-fassung
Seite 19Verlässlichkeit von RechensystemenInstitut für Informatik und WirtschaftsinformatikUniversität Duisburg-Essen
• Automatische Diversifizierung (Technik & Tool)• Unabhängigkeit von Compiler und Hochsprache• Automatische Suche wirksamer Diversitäts-Kombinationen • Geeignete Fehlerinjektionsumgebung & FAIL• Schnelle & intensive Systembewertung • Pessimistische Fehlerinjektion
1) Automatisch erzeugte VDSe:
Ø PGefahr: 8,41% 0,15% (Faktor: 56)
56 und besser... („90% temporäre Fehler“)
2) Kombination mit Entwurfsdiversität:
Ø PGefahr: 8,41% 1,94% 0,00%
„Kostengünstige HW-Fehlererkennung durch virtuelle Duplexsysteme“
Einführung
DIVERSI-Module
Automatische
Diversität
Optimierung
Fehler-Injektion
Resultate
Pessimistische
Injektion
Zusammen-fassung
Seite 20Verlässlichkeit von RechensystemenInstitut für Informatik und WirtschaftsinformatikUniversität Duisburg-Essen
Die folgenden Folien sind KEIN BESTANDTEIL
des Vortrages.
Dienen als Folienvorrat zur Klärung erwarteter Fragen.
Stand der Technik . . .
Einführung
DIVERSI-Module
Automatische
Diversität
Optimierung
Fehler-Injektion
Resultate
Pessimistische
Injektion
Zusammen-fassung
Seite 21Verlässlichkeit von RechensystemenInstitut für Informatik und WirtschaftsinformatikUniversität Duisburg-Essen
Prozedurenumgruppieren
mathematischeÄquivalenzen
verschiedeneDatentypen Übersetzer-
Diversität
Umwandlung von
Schleifen
Code-Optimierungen
Anzahl Code-Segmente Register-
Permutationkomplementäre
Bedingungen
UnabhängigerEntwurf
Resultierende VDSe zeigen bei HW-Fehlern deutlichen Sicherheitsgewinn gegenüber Simplexsystemen
VDS zur Erkennung temporärer + permanenter HW-Fehler geeignet preiswerte Alternative zum Duplexsystem
• Manuell / Automatisch• Hochsprache / Assembler / Übersetzer• Geeignete Kombinationen
Aufwand +Abhängigkeiten vonHochsprache und Übersetzer
Kombination mit Entwurfsdiversität
Einführung
DIVERSI-Module
Automatische
Diversität
Optimierung
Fehler-Injektion
Resultate
Pessimistische
Injektion
Zusammen-fassung
Seite 22Verlässlichkeit von RechensystemenInstitut für Informatik und WirtschaftsinformatikUniversität Duisburg-Essen
crc
virtuelles Duplexsystem
Bisher:
crcSimplexsystem
DIVERSISimplexsystem
crc‘
virtuelles Duplexsystem
crc‘‘Simplexsystem
Simplexsystem
crc
virtuelles Duplexsystem
Jetzt:
crc_tableSimplexsystem
DIVERSISimplexsystem
crc‘
virtuelles Duplexsystem
crc_table‘Simplexsystem
Simplexsystem
Faktor 56
Faktor 4
Motivation zur pessimistischen Injektion
Einführung
DIVERSI-Module
Automatische
Diversität
Optimierung
Fehler-Injektion
Resultate
Pessimistische
Injektion
Zusammen-fassung
Seite 23Verlässlichkeit von RechensystemenInstitut für Informatik und WirtschaftsinformatikUniversität Duisburg-Essen
Härtegrad Ereignis Gefährdung
zu weich
balanciert
zu hart
- Korrekter Ausgabewert im richtigen Format
- Fehlerhaftes Ausgabeformat
- Keine Ausgabe
- Timeout
- Absturz
- Fehlerhafter Ausgabewert im richtigen Format
harmlos
potentiellgefährlich
harmlos
Beobachtungen:• ca. 90% aller injizierten Fehler sind harmlos• Fehlerinjektionsexperimente sind zeitaufwendig
Idee: Zu harte Fehler abschwächen zu balancierten Fehlern
Einführung
DIVERSI-Module
Automatische
Diversität
Optimierung
Fehler-Injektion
Resultate
Pessimistische
Injektion
Zusammen-fassung
Seite 24Verlässlichkeit von RechensystemenInstitut für Informatik und WirtschaftsinformatikUniversität Duisburg-Essen
• Permanent injizierte Fehler wirken bei jeder Instruktion.
• Ziel: Wirkung nicht bei jeder Instruktion
• Aber: Temporäre Fehler sind ungeeignet
Pessimistische Injektionstechnik
Inst. 1
Inst. 2
Inst. 3
Inst. 4
Inst. 5
Inst. 6
VDS 1
DIVERSI
Inst. 1
Inst. 2
Inst. 3
Inst. 4
Inst. 5
Inst. 6
VDS 2
Inst. 2
Inst. 3‘Inst. 3‘‘Inst. 3‘‘‘
Inst. 4
Inst. 5
Inst. 6‘Inst. 6‘‘
Inst. 1
Inst. 2‘Inst. 2‘‘
Inst. 3
Inst. 4‘Inst. 4‘‘Inst. 4‘‘‘
Inst. 5
Inst. 6
Inst. 1