Optimierungsverfahren für Fehlerinjektionsexperimente

Optimierungsverfahren für Fehlerinjektionsexperimente

Seminarvortrag: Softwarebasierte Fehlertoleranz

Adrian Böckenkamp([email protected])

Montag, 04. März 2013

Veranstalter: Olaf Spinczyk, Horst Schirmeier, Christoph Borchert, Boguslaw Jablkowski

2

Agenda

1. Einleitung

2. Konzepte eines FI-Frameworks

3. Reduktion des Fehlerraums

4. Bewertung der Verfahren

5. Diskussion

A. Böckenkamp: Optimierungstechniken für FI-Experimente (SFt)

3

Übersicht

1. Einleitung• Szenario• Problemstellung

2. Konzepte eines FI-Frameworks• Struktur & Ablauf• Motivation: Optimierungen

3. Reduktion des Fehlerraums• Klassifikation von Verfahren• Exakte Verfahren• Heuristisches Verfahren

4. Bewertung der Verfahren• Effektivität: Reduktionsfaktor• Genauigkeit der Heuristik

5. DiskussionA. Böckenkamp: Optimierungstechniken für FI-Experimente (SFt)

4

Rückblick & Szenario

1. Einleitung Szenario


• Erinnerung: FI-Grundlagen– Zuverlässigkeitsaspekte von Software– Was ist FI?– Fehlermodelle– Welche Techniken gibt es?– Verwandt: Fehlertoleranz

• Anwendungsziele von FI:– Güte von Fehlertoleranz-Mechanismen bestimmen– Zuverlässigkeit von Software testen– Identifikation von Schwachstellen

5

Begriffe (1)



• Fehlermodell (hier) immer– Transiente Single-Bitflips– In Register und/oder Speicher

• Statische Instruktion vs. dynamische Instanzen

•

int i = 0;while (i < 10) { test(i++);}

C++-Code:

x86-Assembler:Ausführung:

Statische Instruktionen

DynamischeInstanzen

4004d2: movl4004d9: jmp4004e9: cmpl4004ed: setle4004f0: test4004f2: jne4004db: mov4004de: addl4004e2: mov4004e4: callq4004e9: cmpl …

4004d2: movl4004d9: jmp4004db: mov4004de: addl4004e2: mov4004e4: callq4004e9: cmpl4004ed: setle4004f0: test4004f2: jne

4004d2: movl4004d9: jmp4004db: mov4004de: addl4004e2: mov4004e4: callq4004e9: cmpl4004ed: setle4004f0: test4004f2: jne

4004d2: movl4004d9: jmp4004e9: cmpl4004ed: setle4004f0: test4004f2: jne4004db: mov4004de: addl4004e2: mov4004e4: callq4004e9: cmpl …

:-Beziehung

6

Begriffe (2)



• Golden-Run– Protokoll eines fehlerfreien Durchlaufs (Trace)– mit vordefinierter fester Testeingabe– Gewinnt Menge der

• Fehlerraum = alle möglichen Fehler– Festgelegt durch „wann“ (Instruktionen) und „wo“ (Hardware)– Beispiel (x86):

• Rechenbeispiel (1D-FFT, x86) mit – Annahme: nur 9 „Basisregister“ (eax, edx, …), je 32 Bit Fehler!

8048700: add $0xa,%eax8048702: mov %eax,0x14(%esp) Wann (PC)

Wo (Register)

7

Begriffe (3)



• Auswirkung von Fehlern: Fehler …– … hat keinen Effekt (Maskierung) – … wird erkannt (Detektion)– … bewirkt Systemänderung (Silent-Data-Corruption)

kann zur Fehlerraumreduktion genutzt werden!

• Maß für die Robustheit einer Software? kleine SDC-Rate!– Für stat. Instruktion :

– Für gesamte Software :

– Klar: Soll bei Optimierungen berechenbar bleiben …

Indikatorfunktion für SDC bei FI in mit

8

Problem & Lösungsidee

1. Einleitung Problemstellung


• Problem: Fehlerraum zu groß– 158 Mrd. Experimente praktisch nicht machbar

• Praxisbeispiel: 170 Mio. Experimente– Dauer: „Mehrere Tage“ @3584 Cores

• Wo können Optimierungen ansetzen?– Art und Weise der FI beschleunigen– Menge der Experimente reduzieren

• Optimierungen sollten Ziele nicht einschränken– Beispiel: Fehler nur „sinnvoll“ reduzieren keine Schwachstellen verstecken

9

Übersicht






Fehlerinjektionstechniken

• Varianten (von FI):– Hardware-basiert– Software-basiert– Simulator-basiert

• Abstraktionsebenen (des FI-Ziels):– Gatter-Ebene– Mikroarchitektur-Ebene– Architektur-Ebene

2. Konzepte eines FI-Frameworks Struktur & Ablauf

A. Böckenkamp: Optimierungstechniken für FI-Experimente (SFt) 10

11

Generische Sicht: FI-Framework

2. Konzepte eines FI-Frameworks Struktur & Ablauf


Datenbank

initiale Fehlerliste

Erzeugung der Fehlerliste mit Golden-Run

Optimierung der Fehlermenge

SimulationAnalyse

Ziel-Software NebenbedingungenTesteingaben

Statistiken

Table 1Table 2

Table 3

Table 4

Datenbank

initiale Fehlerliste

Erzeugung der Fehlerliste mit Golden-Run

Analyse

Ziel-Software NebenbedingungenTesteingaben

Statistiken

Table 1Table 2

Table 3

Table 4

Schwerpunkt 1

Schwerpunkt 2

(Simulator-basiert)

12

Motivation: Optimierungen (1)

2. Konzepte eines FI-Frameworks Motivation: Optimierungen


• Mögliche Lösung: Fehlerraum gleichverteilt samplen– Kann Fehler nach Belieben reduzieren– Übersieht aber potentielle Schwachstellen

Instruktionen

Spei

cher

[KiB

]

1

2

3

4

5

0x1000

0x2000

0x3000

0x4000

0x5000

SDC?

FI-Experiment(e)

13

Motivation: Optimierungen (1)



• Mögliche Lösung: Fehlerraum gleichverteilt samplen– Kann Fehler nach Belieben reduzieren– Übersieht aber potentielle Schwachstellen

Instruktionen

Spei

cher

[KiB

]

1

2

3

4

5

0x1000

0x2000

0x3000

0x4000

0x5000

SDC?

FI-Experiment(e)

… eher ungeeignet!

Jetzt: Optimierung der FI-Infrastruktur

14

Beschleunigungskonzepte: Framework (1)



• Parallelität nutzen– Experimente parallel (und verteilt) ausführen– Ergebnisse lokal zusammenführen

• Viele (gleichverteilte) Snapshots verwenden– Speichere viele Simulationszustände (Checkpoints )– Injektion von : Lade mit – Trade-Off: Speicherplatz

Instruktionen

Start:𝑓 𝑖𝑡0 100 𝑡 300 400 500

𝑐𝑡

15

Beschleunigungskonzepte: Framework (2)



• „Modifikation“ des Simulatorcodes (z. B. durch Aspekte)– Simulator-Code muss verfügbar sein– Ermöglicht hohe Effizienz– Keine (?) Simulator-Anpassung nötig (AOP-abhängig)

• Früheres Simulationsende– Wann darf eine Simulation eig. enden? … nachdem Target durchgelaufen ist (exakt) … für weitere Instruktionen ab nach FI von … Tests in exponentiellen Zeitschritten 1, 2, 4, … Heuristiken

16

Übersicht






17

Klassifikation: Fault-Space-Pruning

3. Reduktion des Fehlerraums Klassifikation von Verfahren


• Mögliche Klassifikation:1. Ergebnisvorhersage-basiert (known-outcome-based)2. Äquivalenzklassen-basiert (equivalence-based)

a) Exaktb) Heuristisch

• Allgemeine Ideen der Techniken:– Keine Fehler simulieren, deren Ausgang vorhergesagt werden kann– Möglichst viele „gleichartige“ Fehler finden– „Gleichartig“ über Heuristiken definieren

• Jetzt: Verfahren zum Fault-Space-Pruning– i. W. Architektur-unabhängig

18

Ergebnisvorhersage-basiert: Adressgrenzen

3. Reduktion des Fehlerraums Exakte Verfahren


• Idee: Einige Fehler in Speicheradressen sind detektierbara) Zugriffe auf ungültige Adressen Segmentation Faultb) Zugriffe auf gültige Adressen FI-Experiment nötig

• Verfahren:– Ermittle gültigen Adressbereich (Stack + Heap) mit Golden-Run– Deklariere alle Fehler in Speicheradressen als detektiert– Anwendbar auf Load- und Store-Instruktionen

• Auf Sprunginstruktionen übertragbar:– Sprünge, deren Ziele nicht in .text liegen, sind detektierbar– Problematisch: Sprünge in dyn. Bibliotheken

Ausnutzen!

19

Äquivalenzklassen-basiert: Def-Use-Analyse (1)



• Betrachte:– Schreibzugriff auf ein Register zu Zeit (W)– Lesezugriff auf zu Zeit (R)

• Idee: FI in bei äquivalent zu FI in bei

• D. h.: Instruktionen auf Register …– … vor einem R bis zum letzten W zusammenfassen äquivalent– … vor einem W bis zum letzten R ignorieren bekannt

0x43: r1 = r2 + r30x45: r4 = r1 + r5

W

R

20

Äquivalenzklassen-basiert: Def-Use-Analyse (2)



• Beispiel:

• Beachte: Mehrere R'smit versch. Fehler-Propagationen möglich

• Bisher nur auf Registern betrachtet– Klar: Auf Speicherzugriffe erweiterbar

• Beobachtung: Exaktes Verfahren!

Instruktionen

Regi

ster

𝑡5𝑡 4

𝑟1

𝑟2

𝑟3

R

W

𝑡 6

W

𝑡 8𝑡7

R

R

𝑡 3𝑡 2

R

R

W

Bei 32-Bit Registern FI weniger!

𝑡1

W

W

W

𝑡10𝑡 9

R

W R

𝑡11

RW

21

Äquivalenzklassen-basiert: Kontrollpfade (1)

3. Reduktion des Fehlerraums Heuristisches Verfahren


• Beobachtungen:– Fehler, die durch ähnlichen Code propagieren, verhalten sich ähnlich– Mehrfachausführung von Code: Fehlerw.k. steigt

• Idee: – Betrachte mit vielen im Golden-Run– Teile in Äquivalenzklassen auf Basis des Kontrollpfades nach – Führe FI nur für Repräsentanten der Klassen durch

• Verfahren:– Zähle alle Pfade ab Basisblock von auf– … durch dynamische Analyse des Golden-Run– Sprunginstruktionen (Heuristik)

22




• Beispiel (CFG):

• Verfahren (Forts.):– Population: Pfade , die mehrfach ausgeführt werden– Pilot : Wähle zufälligen Pfad – Verwerfe alle Pfade Reduktion!

1

2 3

4 5

6

7

8

Kontrollpfade mit :

besucht

unbesucht

∈ 𝐼𝑑

5 Äquivalenzklassen

23




• Beispiel (Forts.):– Betrachte Pfad und FI in

1

2 3

4 5

6

7

8

Ann.: wird 1.000x durchlaufen− Etwa weil:

− entspricht diesen Pfaden− Wähle zufälligen Pilot

FI in Reg.-Bits von für ...

for (int i=0; i<1000; i++) { // ...}

for (int i=1; i<1000; i++) { // ...}

for (int i=2; i<1000; i++) { // ...}

for (int i=3; i<1000; i++) { // ...}

for (int i=999; i<1000; i++) { // ...}


• Beobachtung: Heuristisches Verfahren!

• Implementierung auf Basisblock-Ebene

• Anwendbar auf alle Instruktionen außer– … Load/Store– … solche, die Load/Store beeinflussen Fehlerpropagation auch von Adressen (in Load) abhängig

• Ausblick: Speicheräquivalenz-Heuristik– Idee: Fehler in Store ähnlich, falls Werte ähnlich benutzt werden– Ähnelt der Kontrollpfadäquivalenz


A. Böckenkamp: Optimierungstechniken für FI-Experimente (SFt) 24

25

Übersicht






26

Bewertungsgrundlage der Verfahren

4. Bewertung der Verfahren Effektivität: Reduktionsfaktor


• Ziel war: Reduktion des Fehlerraums

• Bewertungsgrundlage– SPARC v9-Architektur– 12 Applikationen aus 3 versch. Benchmarks– Kontext: Physik / Informatik / Mathematik– Optimierte vs. unoptimierte Kompilate

• Eckdaten– Anzahl der : 22,3 Millionen – 4,57 Milliarden– Kardinalität von : 1,9 – 500,4 Milliarden– Beispiele: FFT, GCC, Water, Ocean, …

27

Ergebnisse (Auswahl)

4. Bewertung der Verfahren Effektivität: Reduktionsfaktor


Series1 27% 15% 10% 48%

AdressgrenzenDef-Use-AnalyseSpeicheräquivalenzKontrolläquivalenz

• 99,78 % aller Experimente reduziert, meistens 99,99 %– Größenordnung 3 – 6 für die meisten Anwendungen

• 0,004 % der Fehler repräsentieren 99 % aller Fehler!

• Reduktionsraten bei unoptimierten Anwendungen (viel) höher– Beispiel (FFT) optimiert: 48,7 Mrd. (initial) 0,3 Mio. (reduziert) unoptimiert: 61,18 Mrd. (initial) 0,16 Mio. (reduziert)

• Verfahrensanteile an Gesamtreduktion:

(optimiert)

28

Bewertungsmodell der Genauigkeit

4. Bewertung der Verfahren Genauigkeit von Heuristiken


• Wie genau repräsentieren die Piloten ihre Population?– Beispiel: FI in Pilot maskiert, FI in 98 % maskiert, 2 % SDCGenauigkeit 98 %

• Gesamtgenauigkeit: Gewichteter aller Piloten mit

• Praktisch unmöglich: „FI in“!

• Alternative (machbar):– Population zufällig abtasten– Nur in jedes 8-te Bit injizieren– Beschränke Piloten, sodass Simulationen 1 Mio.

29

Ergebnisse (Auswahl)



• 96 % Genauigkeit über Kontroll- und Speicheräquivalenz– Beinhaltet Vorhersage-basierte Techniken 100 % Genauigkeit!

• Speziell für Kontrolläquivalenz:– 95,7 % für FI in Register– 94,5 % für FI in Adressregister

• Pro Anwendung über alle Techniken gemittelt: > 91 %

• Schwachstelle:– Beschränkung auf Basisblock-Ebene

30

Zusammenfassung & Fazit



• Optimierungsziele waren:1. Reduktion des Fehlerraums2. Beschleunigung der Experimente

• Kernideen waren:– Fehlerauswirkung vorherzusagen oder– Fehler in Äquivalenzklassen einteilen

• Ergebnisse:– Hohe Reduktionsraten erzielbar (… ggf. mit Heuristiken)– Stark abhängig vom Kontext (Compiler, Target, Verfahren)

31

Übersicht






32

Diskussion

Vielen Dank für die Aufmerksamkeit!

Fragen? Anmerkungen? Kritik?

5. Diskussion


33

Literatur & Quellen (1)

Literaturverzeichnis


• „Relyzer: Exploiting Application-Level Fault Equivalence to Analyze Application Resiliency to Transient Faults”; S. K. S. Hari, S. V. Adve, H. Naeimi und P. Ramachandran; Proceedings of the 17th international conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS '12), http://rsim.cs.illinois.edu/Pubs/12-ASPLOS-Hari.pdf

WICHTIGSTE GRUNDLAGE DES VORTRAGS:

• „Fault-list collapsing for fault-injection experiments“; A. Benso, M. Rebaudengo, L. Impagliazzo und P. Marmo; Proceedings of the Annual Reliability und Maintainability Symposium, 1998; http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=653808

• „FAIL*: Towards a Versatile Fault-Injection Experiment Framework“; H. Schirmeier, M. Hoffmann, R. Kapitza, D. Lohmann und O. Spinczyk; 25th International Conference on Architecture of Computing Systems (ARCS '12), 2012; http://danceos.org/publications/VERFE-2012-Schirmeier.pdf

• „New Techniques for Speeding-up Fault-injection Campaigns“; L. Berrojo, I. González, F. Corno, M. Sonza Reorda, G. Squillero, L. Entrena und C. Lopez; Proceedings of the conference on Design, automation and test in Europe, 2002; http://www.date-conference.com/proceedings/PAPERS/2002/DATE02/PDFFILES/08D_4.PDF

WEITERE QUELLEN:

34

Literatur & Quellen (2)

Literaturverzeichnis


• „Investigating the limitations of PVF for realistic program vulnerability assessment“; B. Döbel, H. Schirmeier und M. Engel. In Proceedings of the 5rd HiPEAC Workshop on Design for Reliability (DFR '13), Berlin, Germany, Jan. 2013; http://danceos.org/publications/HiPEAC-DFR-2013-Doebel.pdf

WEITERE QUELLEN:

Documents

Optimierungsverfahren für Fehlerinjektionsexperimente