Der Traum von fehlerfreier Software

Der Traum von fehlerfreier Software
Prof. Dr. Stefan Leue
Universität Konstanz
Lehrstuhl für Software Engineering
[email protected]
http://www.inf.uni-konstanz.de/~soft
22. Oktober 2005
software
Copyright © Stefan Leue 2005
engineering
Der Weg hierher...
1990
Diplom in Informatik und Wirtschaftswissenschaften
Universität Hamburg
1991 - 1995
Promotion Dr. phil.-nat.
Universität Bern
1995 - 2000
Assistant / Associate Professor
University of Waterloo, Kanada
1998
Member of Technical Staff
Bell Laboratories, USA
2000-2004
Professur für Rechnernetze und Telematik
Universität Freiburg
seit 2004
Universität Konstanz
© Stefan Leue 2005
2
software
Lehrstuhl für Angewandte Informatik / Software Engineering
engineering
Lehrstuhl für Software Engineering
♦ Wissenschaftliche MitarbeiterInnen
8Husain Aljazzar
8Alin Stefanescu
8Evghenia Stegantova
8Wei Wei
8NN1
© Stefan Leue 2005
3
software
8NN2
engineering
Quelle: IT-Forschung 2006 - Förderprogramm Informations- und Kommunikationstechnik
BMBF, 2002
© Stefan Leue 2005
4
software
Informations- und Kommunikationssektor
engineering
Quelle: IT-Forschung 2006 - Förderprogramm Informations- und Kommunikationstechnik
BMBF, 2002
© Stefan Leue 2005
5
software
Informations- und Kommunikationssektor
engineering
Bedeutung von Software
Quelle: IT-Forschung 2006 - Förderprogramm Informations- und Kommunikationstechnik
BMBF, 2002
© Stefan Leue 2005
6
software
♦ Werkstoff der Informationsgesellschaft
engineering
Ökonomische Bedeutung von Software
♦ Werkstoff der Informationsgesellschaft
8 Markt für Software-Produkte
– Deutschland: 16,5 Mrd. € (2001)
– Europa: 57 Mrd. € (2001)
8 Brutto-Wertschöpfung durch Softwareentwicklung und -anpassung
– ca. 25 Mrd. € (2001)
8 Martvolumen aller Produkte, die von Software abhängen, Primär- und
Sekundärbranchen
– ca. 500 Mrd. € (2001)
8 Hardware, Software, IT-Dienstleistungen (ohne Medien):
– 820.000 (2000)
8 davon Software und IT-Dienstleistungen
– 400.000 (2001, geschätzt)
8 Vergleich: Automobilindustrie
– 746.000 (2000, im Mittel)
© Stefan Leue 2005
7
software
♦ Beschäftigtenzahlen in Deutschland
engineering
Software-Krise
♦ Umfrage in IEEE Software, 1995
8 30% aller Softwareprojekte werden abgebrochen
8 50% aller Softwareprojekte überschritten ihr Budget um mind. 150%
8 nur 60% der ursprünglich geplanten Funktionalität ist in dem
endgültigen Produkt
♦ ...aber wir produzieren doch erfolgreich hochgradig
komplexe Softwaresysteme, die gut funktionieren?
8 Airbus A380
8 Toll Collect
8 SAP R/3
© Stefan Leue 2005
8
software
8 ...
engineering
Software-"Erkältung"
♦ Daher: es könnte noch besser gehen
8 "... bisher setzen nur 30% der Unternehmen systematische Prozesse
bei der Softwareentwicklung ein,,,"
8 Allerdings:
– Deutschland international zweitklassig in den Bereichen der
Entwicklung Betriebssysteme, Web-Systeme,
Informationssysteme, etc.
– Weltweit führend bei Entwicklung eingebetteter Softwaresysteme
iFlugzeugbau (EADS)
iAutomobilbau (Bosch, BMW, Daimler-Chrysler,...)
iSchienenverkehrstechnik
und hier auch weltweit führend in den Softwareprozessen!
8 bisher kein Todesfall in Flugzeugen durch fehlerhafte Software!
© Stefan Leue 2005
9
software
♦ Softwaregesteuerte Flugzeuge?
engineering
Software-Fehler und -Ausfälle (IEEE 729)
♦ Software-Fehler (fault)
8 durch einen Menschen verursachter Fehler (error) in einem Softwarebezogenen Arbeitsschritt, z. B.
– fehlerhafte Anforderungen,
– fehlerhafter Entwurf oder
– fehlerhafte Programmierung,
welcher zu einem falschen Programmzustand führt
♦ Software-Ausfall, Software-Fehlverhalten (failure)
8 beobachtete Abweichung des Systems von seinem geforderten
© Stefan Leue 2005
10
software
Verhalten
engineering
Software-Fehlverhalten
© Stefan Leue 2005
11
software
"... Schuld an der Abrechnungspanne sei die Texteingabehilfe. Das
Einfügen eines Apostrophs zum Beispiel bewirke, dass die SMS statt
der regulären 19 Cent bis zu 80 Cent koste. Vier Jahre lang sei
unerkannt geblieben, dass die Software bei einigen Sonderzeichen
Fehler verursache. ..."
engineering
© Stefan Leue 2005
12
software
Software-Fehlverhalten
engineering
Software-Fehlverhalten
© Stefan Leue 2005
13
software
"... Doch erst ein herbeieilender Wachmann konnte mit dem beherzten
Zertrümmern einer Scheibe den Minister befreien. "Wir konnten kaum noch
Atmen, weil die Klimaanlage ausgefallen war", sagte Jaovisidha später zu
Reportern. ... Schuld an der Panne sei ein Fehler des Bordcomputers
gewesen. "Es war äußerst unangenehm, weil nichts mehr funktionierte und
alles verschlossen war." ..."
engineering
Ökonomische Effekte von Software Fehlern
♦ Kosten Unzulänglicher Software-Test-Infrastruktur
8 Studie des National Institute for Standards and Technology (NIST,
USA)
– Kosten $59.5, entspricht etwa 0.6% des USBruttoinlandsproduktes
– potentielle Einsparungen $22.2 entsprechen etwa 0.2% des USBruttoinlandsproduktes
8 Schätzung Europa: Kosten €20 Mrd.
♦ Kosten des softwarebedingten Ariane-5 Absturzes
8 $500 Mio.
♦ Kosten von SW-Fehlern in Eingebetteten Systemen mit
hoher Replikation
© Stefan Leue 2005
14
software
8 ADAC (2003): 144 Rückrufaktionen aufgrund fehlerhafter
Bordelektronik, betroffen waren 940.000 Fahrzeuge
engineering
"... Tritt bei diesem Quersummen-Check ein Fehler auf, schaltet das Gerät
sofort auf ein Notlaufprogramm um; dazu bedient es sich der fest in die
Steuerplatte eingebrannten Basisdaten. ... Auf dieser Behelfsebene
existiert jedoch nur noch ein simpler Steuerbefehl: Im Falle eines Aufpralls
werden alle Airbags gezündet. Die einprogrammierte Deaktivierung ist dann
Makulatur. ..."
© Stefan Leue 2005
15
software
Software-Fehler in sicherheitskritischen Systemen
engineering
Warum ist Softwareproduktion so schwierig?
♦ Enorme Komplexität
8 mittlere eingebettete technische Systeme (z. B. Auto)
– ca. 500.000 - 2.000.000 Zeilen Code
8 grosse Softwaresysteme (z.B. Windows XP, TelefonVermittlungsstellen)
– > 50 Mio. Zeilen Code
♦ Einfache Formbarkeit
8 führt zu "code-and-fix"
♦ Diskrete Natur
8 Korrektheit kann nicht, wie in anderen ingenieurwissenschaftlichen
Disziplinen, approximiert werden
8 "Erst als ich das System das erste Mal sah, wusste ich, dass dies
nicht das war, was ich wollte."
© Stefan Leue 2005
16
software
♦ Fortwährende Änderungen der Anforderungen
engineering
Software-Prozess (Wasserfall)
Systementwurf
Anforderungen
Entwurf
Implementierung
Integration und
Testen
© Stefan Leue 2005
17
software
Wartung
engineering
Software-Qualitätssicherung
♦ Testen
8 spielen mit der Software
8 antizipieren der möglichen Fehler
♦ Code-Inspektion
8 Computer spielen
8 Vermeidung typischer Programmierfehler
8 Einhaltung von Programmierkonventionen
8 antizipieren möglicher Fehler
♦ Formale Verifikation
8 Theorembeweisen
© Stefan Leue 2005
18
software
8 Model Checking ("Modellprüfverfahren")
engineering
Software-Fehler
♦ Software ist Text
8 zu einem grossen Teil von Hand geschrieben
public void displayScreen ( int objectCount )
{ ...
if objectCount < 10
displayScreenDetailed();
if objectCount > 10
displayScreenOverview();
...
}
displayScreen(
displayScreen(
displayScreen(
displayScreen(
displayScreen(
© Stefan Leue 2005
0 );
1 );
9 );
10 );
11 ); ...
19
software
8 Code-Inspektion
– bei Entscheidungen alle Fälle abgedeckt?
8 Testen
– systematisches Testen der Boundary Conditions
engineering
Software-Fehler
♦ Komplexe Softwaresysteme besitzen gleichzeitig
arbeitende (= "nebenläufige") Komponenten
© Stefan Leue 2005
20
software
8 Frage: gehen Max und Paul immer so miteinander um, dass sie sich
nie gegenseitig blockieren?
iMax verlangt Cola und gibt erst dann Schokolade
iPaul verlangt Schokolade und gibt erst dann Cola
engineering
Software-Fehler
proctype Max(chan AnPaul, VonPaul )
{
Maxistgrosszuegig:
atomic {
if
:: true && true ->
AnPaul!Schokolade;
goto Maxistkleinlich;
fi
}
proctype Paul(chan AnMax, VonMax )
{
Paulistgrosszuegig:
atomic {
if
:: true && true ->
AnMax!Cola;
goto Paulistkleinlich
fi
}
Maxistkleinlich:
atomic {
if
:: VonPaul?[Cola] && true ->
VonPaul?PaulanMax_msg;
AnPaul!Schokolade;
goto Maxbetruegt
fi
}
Paulistkleinlich:
atomic {
if
:: VonMax?[Schokolade] && true ->
VonMax?MaxanPaul_msg;
AnMax!Cola;
goto Paulbetruegt
fi
}
Maxbetruegt:
atomic {
if
:: VonPaul?[Cola] && true ->
VonPaul?PaulanMax_msg;
goto Maxistkleinlich
fi
}
}
Paulbetruegt:
atomic {
if
:: VonMax?[Schokolade] && true ->
VonMax?MaxanPaul_msg;
goto Paulistkleinlich
fi
}
}
© Stefan Leue 2005
21
software
♦ Das Modell als textuelles Programm (Auszug):
engineering
Software-Fehler
♦ Testen? Inspektion?
© Stefan Leue 2005
22
software
8 Modell nicht mehr intuitiv nachvollziehbar
8 daher verhalten nicht antizipierbar
inicht inspizierbar
inicht testbar
8 außerdem: "Testing can always only show the presence of bugs, but
never their absence" (E. W. Dijkstra)
8 daher: vollständige, automatisierte Suchmethode
engineering
Model Checking
♦ Model Checking von Expliziten Zustandräumen
8 systematische Erzeugung aller Konfigurationen (= Zustände) des
Softwaresystems
8 systematische Erzeugung aller möglichen Schritte (Schokolade,
Cola) des Systems (= Zustandsübergänge)
AnPaul!Schoko
AnMax!Cola
© Stefan Leue 2005
23
software
AnPaul!Schoko
engineering
Counterexample with Depth-First Search (DFS)
♦ Model Checking von expliziten Zustandsräumen
8 durchsuchen aller erreichbaren Konfigurationen nach "schlechten"
Konfigurationen
– hier: Konfigurationen, die blockieren, also keinen Nachfolger
haben
8 der Weg zu einer solchen Fehler-Konfiguration heißt Fehlerpfad
– hilfreich zur Fehlerbehebung
AnPaul!Schoko
AnMax!Cola
AnPaul!Schoko
© Stefan Leue 2005
24
software
AnMax!Cola
engineering
© Stefan Leue 2005
25
software
Model-Checking
engineering
Model Checking
© Stefan Leue 2005
26
software
"... hat eine noch formalere Methode zur Fehlersuche die Schwelle zur
industriellen Anwendung auf Software überschritten: das "Model-Checking".
Ähnlich wie eine Ampel nicht gleichzeitig für den Straßenverkehr und den
Fußgängerüberweg Grün zeigen darf, lassen sich auch für SoftwareModule kritische Zustände beschreiben, die sie nicht gleichzeitig mit
anderen Programmteilen annehmen dürfen. Model-Checking versucht zu
beweisen, dass verbotene Kombinationen nie gemeinsam auftreten - oder
bricht mit einem solchen Fehlerbeispiel ab..."
engineering
Der Weg zur Industriellen Praxis?
© Stefan Leue 2005
27
software
"Intel setzt diese Methode heute zur Überprüfung komplexer SchaltungsLayouts ein. Auch Microsoft greift für Gerätetreiber zu Model-CheckingTools, bestätigt Tony Hoare vom Microsoft Research Center in Cambridge.
'Die Treiber werden oft von Fremdfirmen geschrieben, aber im
Betriebssystemkern ausgeführt, und können ernsthafte Auswirkungen
haben, wenn sie fehlerträchtig sind.'"
engineering
Projects
♦ DMC
8 Directed Model Checking
♦ DiRePro
8 Directed Model Checking in the Analysis of Real-Time and
Probabilitstic Systems
– associate membership in SFB TR 14 "AVACS"
– contribution to AVACS projects S3 and R3
♦ VisADyn
8 Visualization and Analysis of Dynamic Software Systems
– Graduiertenkolleg "Explorative Analysis and Visualization of Large
Information Spaces"
♦ IMCOS
© Stefan Leue 2005
28
software
8 Incomplete Model Checking for Concurrent, Object-Oriented Systems
engineering
DMC
informed, heuristic search
(best-first, A*,...)
O
g
g(s)
expansion criterion:
s ∈ O with min. g(s) + h(s)
h(s)
DFS
(Depth First Search)
A* directed search
8 explicit state model checking is state space search
8 ways to be smarter than just DFS?
– heuristics guided search (best-first, A*, IDA*,...)
– adequate heuristic estimates
8 shorter or even optimally short counterexamples
– improved error explanation
8 for some analyses improved scalability
© Stefan Leue 2005
29
software
♦ Directed Model Checking
engineering
DiRePro
♦ Analysis of Continuous Time Markov Chains
8 for instance, SCSI-2 based computing sytems
8 combined functional and dependability analysis
The probability to reach a state s violating a state proposition ϑ,
i.e., satisfying ϕ := ¬ ϑ, within the time interval [0, t], does not
exceed a probability p ∈ [0, 1]:
P<p : Transient probability does not exceed p.
♦· t : Timed reachability within [0, t]
8 CSL model checking does not produce counterexamples
Path-length optimizing search
(BFS, Best-First, A*)
Depth-First Search (DFS)
8 use heuristic search (Z*) to maximize timed run probability
© Stefan Leue 2005
30
software
we want this!
engineering
IMCOS
♦ Buffer Boundedness for Asynchronous Concurrent
Object-Oriented Models
8 inherently desired property (model sanity)
8 necessary precondition for finite-state analyzability
8 undecidable
– develop semi-test based on gross overapproximation of model
8 analysis of UML 2.0 / UML-RT models
8 developed tool directly linked to IBM Rational Rose RT
© Stefan Leue 2005
31
software
♦ Application
engineering
IMCOS
Verification of UML-RT models
UML
-RT model (from RoseRT)
UML-RT
capsule
hierarchical
state machine
port
Property
Java code on
transitions
e.g.
deadlock-freedom,
LTL formula
Java model checker
(Bogor)
© Stefan Leue 2005
+ extensions specialized for UML-RT
software
Abstractions + Translation to BIR
engineering
© Stefan Leue 2005
33
software
Software-Versagen?
engineering
© Stefan Leue 2005
34
software
Vielen Dank für Ihre Aufmerksamkeit!
engineering