1 N-Version Programmierung N-Version Programmierung von Rafael Bielen

1

N-Version N-Version ProgrammierungProgrammierung

von Rafael Bielen

2

InhaltInhalt Einleitung Motivation Funktionsprinzip Herausforderungen Abwandlungen wichtige historische Ansätze Probleme Fazit

3

weiterer Ansatz um Software fehlertoleranter und robuster zu entwickeln

Programmierfehler mildern Kernidee:

mehrfach dasselbe Programm implementieren

Hoffnung: Auftreten gleicher Fehler senken

Einleitung 1/2Einleitung 1/2

4

Implementierungen unabhängig voneinander

alle Implementierungen nach gleichen Spezifikationen ein Algorithmus wählt das vermutlich richtige Ergebnis

Einleitung 2/2Einleitung 2/2

5

Wieso Programmierfehlern vorbeugen?

Sichere Software spart Kosten! Ariane 5 Satelliten, 1,7 Milliarden DM Schaden

Programmierfehler: 64Bit – 16Bit Umwandlung Studie aus dem Jahr 1986:

pro 1 Million Zeilen Code 20.000 Bugs

MotivationMotivation

6

Software ist kein „ganzes Stück“ mehr

besteht aus verschiedenen Softwaremodulen

FunktionsprinzipFunktionsprinzip

7

Herausforderungen Herausforderungen 1/41/4 Spezifikationen:

Eingabespezifikation, ein Fehler N fehlerhafte Softwaremodule Cross-Check Punkte gut definieren Designfehler ausschließen Freiraum für verschiedene

Implementierungen lassen

8

unabhängige Entwicklung: Ziel: Auftreten von gemeinsamen

Fehlern in den unterschiedlichen Softwareversionen vermindern.

verschiedene Programmiersprachen benutzen

Verwendung von unterschiedlichen Instrumenten und Compilern

unterschiedliche Teams

Herausforderungen Herausforderungen 2/42/4

9

Herausforderungen Herausforderungen 3/43/4 Entscheidungs-Algorithmus:

effizient selber sicher von Fehlern Wie erkennt man das richtige

Ergebnis? oftmals einziger Weg

Mehrfachbeschluss

10

Herausforderungen Herausforderungen 4/44/4

Wartung eines laufenden Systems: Welches Modul verursacht einen

Fehler? Wartung aufwendiger als bei

„normaler“ Software höhere Wartungskosten

11

verschiedene Abwandlungen Darstellung von verschiedenen

Konfigurationen der Abwandlungen als 3er Tupel möglich.

Zeit | Plattformen | Software

N-Version N-Version Programmierung Programmierung Abwandlungen Abwandlungen

12

Nutzung einer einzigen Plattform zur Ausführung

N x Zeit | 1 x Plattform | N x Software Rollback-Methode Beispiel:

2 x Zeit | 1 x Plattform | 1 x Software Rollback zum letzten fehlerfreien Zustand mehrfacher Rollback bei einem Fehler auch

möglich nicht geeignet für permanente Fehler (zerstörte

Hardware) Reparatur von außen nötig

Single-Channel 1/2Single-Channel 1/2

13

neue Softwareinstanz-Methode Beispiel: Starten einer neuen Softwareinstanz 2 x Zeit | 1 x Plattform| 2 x Software Daten auf denen gearbeitet wird stabile und fehlerfreie gespeicherte

Kopie

Single-Channel 2/2Single-Channel 2/2

14

Multi-Channel 1/3Multi-Channel 1/3

alles nur einmal berechnen mehrere Softwareversionen, jede auf

einer eigenen Plattform 1 x Zeit | N x Plattformen | N x

Software NASA's Space Shuttle mit N = 4 2. Punkt wichtig für Realisierung

15

Multi-Channel 2/3Multi-Channel 2/3 1. Konsistenz:

Plattformen müssen alle die gleiche Eingabe bekommen sowie im gleichen Startzustand sein.

2. Zuverlässiger Entscheidungs- Algorithmus: Kontrolle aller Ergebnisse der

Berechnungen unnötig Akzeptanzbereich

16

Multi-Channel 3/3Multi-Channel 3/3

Entscheidungs-Algorithmus wird oft für jeden Bereich neu geschrieben.

hilft nicht gegen Designfehler Lösung: Erstelle von Software und

Hardware individuelle Versionen.

17

Welche Fehler Welche Fehler können können behoben werden? behoben werden?

Fehlerbehebung möglich bei: Programmierfehlern Programmfehlern Hardwarefehlern

Kein Erfolg bei: mangelhafter Spezifikation fehlerbehaftetem Input Fehler in der Bedienung

18

Wichtige historischeWichtige historischeAnsätzeAnsätze

Dr. Dionysius Lardner (1834): Fehler vorbeugen durch gleiche Berechnungen auf unterschiedlichen Plattformen

N-Version Programmierung: auch genannt Multi-Version Programmierung, Beginn 1970

zwei wichtige Ansätze von: Brian Randell UCLA (Universität von Kalifornia, Los Angels)

19

„ „Recovery Block“ von Recovery Block“ von

Brian Randell 1/2 Brian Randell 1/2 Ziel:

Softwarefehler, auch welche die durch Hardwarefehler verursacht werden, im laufenden Betrieb zu erkennen.

Ursprungsversion der Software erstellen Berechnungen der Version im laufenden

Zustand mit der Berechnung der Ursprungsversion verglichen Akzeptanztest

20

„ „Recovery Block“ von Recovery Block“ von

Brian Randell 2/2 Brian Randell 2/2 Nichtbestehen des Akzeptanztests ältere Version der Software einspielen, die den Test bestanden hat N x Zeit | 1 x Hardware | N x Software

Variierung der „Recovery Block“ Methode möglich: unterschiedliche Plattformen um Design-

und Hardwarefehler auszuschließen

21

NVP von UCLANVP von UCLA

Erstellung von individuell gestalteten Softwaremodulen

Softwaremodule erfüllen alle die gleichen Spezifikationen

vermutlich richtiges Ergebnis mit Hilfe eines Algorithmus auswählen

1 x Zeit | N x Hardware | N x Software

22

Experimentale Experimentale Resultate Resultate der UCLA 1/4 der UCLA 1/4 UCLA negativ aufgefallen „Klassische“ Computersysteme sind

nicht gut dafür geeignet, N-Version Software auszuführen und zu überwachen.

Eigener Computer Prototyp designt und implementiert (DEDIX = Design Diversity Experiment).

23

Experimentale Experimentale Resultate Resultate der UCLA 2/4 der UCLA 2/4 Betriebssystem,

Unix Abwandlung,genannt LOCUS

DEDIX nutzt eine verteilte Rechenarchitektur, die auf 20 VAX 11/750 Computern basiert (3.125 MHz pro Maschine)

24

Experimentale Experimentale Resultate Resultate der UCLA 3/4 der UCLA 3/4 Studie:

Spezifikation in je 3 Sprachen für das gleiche Problem/Aufgabe

OBJ (Declarative "ultra high-level" Sprache)

PDL (Seitenbeschreibungssprache) Englisch als 3te Kontrollsprache

25

30 Programmierer beschäftigt, die 19 Programme erstellten

8 Programme aus der OBJ Spezifikation 5 aus der PDL Spezifikation 6 aus der Kontrollsprache Eng. Spezifikation = 10 Seiten OBJ Spezifikation = 7 Seiten PDL Spezifikation = 74 Seiten

Experimentale Experimentale Resultate Resultate der UCLA 4/4 der UCLA 4/4

26

Probleme 1/5Probleme 1/5 Tests:

6 unterschiedliche Versionen, alle untereinander testen, 21 Tests nötig

Aufwand fast um N-Mal höher als bei „normaler“ Software

Tests werden komplexer Wechselwirkung Entscheidungs-Algorithmus muss getestet

werden Kosten steigen damit

27

Unterschiedliche Plattformen und Betriebssysteme: Für jedes Betriebssystem meistens eigene

Testkonfigurationen und unterschiedliche Hilfsprogramme notwendig

Probleme Ergebnisse untereinander vergleichen

unterschiedliche Zeichensätze oder komplett andere Byte-Reihenfolge

Probleme 2/5Probleme 2/5

28

Probleme 3/5Probleme 3/5

29

Probleme 4/5Probleme 4/5 Kosten:

Es gibt keine konkreten Statistiken, die besagen wie viel teurer die Entwicklung von N-Software Versionen ist.

Zahlen schwanken von 25%-134% Die Idee, N-Versionen einer Software lassen

die Kosten um N-Mal multiplizieren, ist falsch!

viele Gemeinsamkeiten in der Entwicklung

30

Probleme 5/5Probleme 5/5

Unabhängige Versionen: Problemlösung lässt oft wenig

Spielraum Implementierungen oft ähnlich

Keine Studien die Beweisen, dass gleiche Fehler gemindert werden.

31

Fazit 1/2Fazit 1/2

Positiv: interessanter Ansatz praktisch Einsetzung z.B. NASA Space

Shuttle intuitiv verschiedene

Softwareversionen müssen nicht die gleichen Fehler enthalten

Fazit 2/2Fazit 2/2

• Negativ:

• nicht gut entwickelt/erforscht

• Kosten/Aufwand?

• Werden gleiche Fehler wirklich minimiert?!

• Entscheidungs-Algorithmus nicht trivial

33

Fragen?Fragen?

Fragen?

34

LiteraturverzeichnisLiteraturverzeichnis

Algirdas Avizienis.The N-Version Approach to Fault-Tolerant Software. Software Engineering, IEEE Transactions on , vol.SE-11, no.12, pp. 1491- 1501, Dec. 1985

Israel Koren and C. Mani Krishna. Fault-Tolerant Systems. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2007

Proseminar Software Desaster ARIANE 5 Absturz des Flugs 501 Mathias Riedl

4.12.2002, Vorlesung Universtität Zürich, Martin Glinz Software Engineering I

The Evolution of the Recovery Block ConceptBRIAN RANDELL and JIE XU University of Newcastle upon Tyne

35