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

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

Embed Size (px)

Citation preview

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

1

N-Version N-Version ProgrammierungProgrammierung

von Rafael Bielen

Page 2: 1 N-Version Programmierung N-Version Programmierung von Rafael Bielen

2

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

Page 3: 1 N-Version Programmierung N-Version Programmierung von Rafael Bielen

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

Page 4: 1 N-Version Programmierung N-Version Programmierung von Rafael Bielen

4

Implementierungen unabhängig voneinander

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

Einleitung 2/2Einleitung 2/2

Page 5: 1 N-Version Programmierung N-Version Programmierung von Rafael Bielen

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

Page 6: 1 N-Version Programmierung N-Version Programmierung von Rafael Bielen

6

Software ist kein „ganzes Stück“ mehr

besteht aus verschiedenen Softwaremodulen

FunktionsprinzipFunktionsprinzip

Page 7: 1 N-Version Programmierung N-Version Programmierung von Rafael Bielen

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

Page 8: 1 N-Version Programmierung N-Version Programmierung von Rafael Bielen

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

Page 9: 1 N-Version Programmierung N-Version Programmierung von Rafael Bielen

9

Herausforderungen Herausforderungen 3/43/4 Entscheidungs-Algorithmus:

effizient selber sicher von Fehlern Wie erkennt man das richtige

Ergebnis? oftmals einziger Weg

Mehrfachbeschluss

Page 10: 1 N-Version Programmierung N-Version Programmierung von Rafael Bielen

10

Herausforderungen Herausforderungen 4/44/4

Wartung eines laufenden Systems: Welches Modul verursacht einen

Fehler? Wartung aufwendiger als bei

„normaler“ Software höhere Wartungskosten

Page 11: 1 N-Version Programmierung N-Version Programmierung von Rafael Bielen

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

Page 12: 1 N-Version Programmierung N-Version Programmierung von Rafael Bielen

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

Page 13: 1 N-Version Programmierung N-Version Programmierung von Rafael Bielen

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

Page 14: 1 N-Version Programmierung N-Version Programmierung von Rafael Bielen

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

Page 15: 1 N-Version Programmierung N-Version Programmierung von Rafael Bielen

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

Page 16: 1 N-Version Programmierung N-Version Programmierung von Rafael Bielen

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.

Page 17: 1 N-Version Programmierung N-Version Programmierung von Rafael Bielen

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

Page 18: 1 N-Version Programmierung N-Version Programmierung von Rafael Bielen

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)

Page 19: 1 N-Version Programmierung N-Version Programmierung von Rafael Bielen

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

Page 20: 1 N-Version Programmierung N-Version Programmierung von Rafael Bielen

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

Page 21: 1 N-Version Programmierung N-Version Programmierung von Rafael Bielen

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

Page 22: 1 N-Version Programmierung N-Version Programmierung von Rafael Bielen

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).

Page 23: 1 N-Version Programmierung N-Version Programmierung von Rafael Bielen

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)

Page 24: 1 N-Version Programmierung N-Version Programmierung von Rafael Bielen

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

Page 25: 1 N-Version Programmierung N-Version Programmierung von Rafael Bielen

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

Page 26: 1 N-Version Programmierung N-Version Programmierung von Rafael Bielen

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

Page 27: 1 N-Version Programmierung N-Version Programmierung von Rafael Bielen

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

Page 28: 1 N-Version Programmierung N-Version Programmierung von Rafael Bielen

28

Probleme 3/5Probleme 3/5

Page 29: 1 N-Version Programmierung N-Version Programmierung von Rafael Bielen

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

Page 30: 1 N-Version Programmierung N-Version Programmierung von Rafael Bielen

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.

Page 31: 1 N-Version Programmierung N-Version Programmierung von Rafael Bielen

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

Page 32: 1 N-Version Programmierung N-Version Programmierung von Rafael Bielen

Fazit 2/2Fazit 2/2

• Negativ:

• nicht gut entwickelt/erforscht

• Kosten/Aufwand?

• Werden gleiche Fehler wirklich minimiert?!

• Entscheidungs-Algorithmus nicht trivial

Page 33: 1 N-Version Programmierung N-Version Programmierung von Rafael Bielen

33

Fragen?Fragen?

Fragen?

Page 34: 1 N-Version Programmierung N-Version Programmierung von Rafael Bielen

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

Page 35: 1 N-Version Programmierung N-Version Programmierung von Rafael Bielen

35