Ablaufüberwachung objektorientierter Programme (eBook)

Inhaltsverzeichnis 10
Definitionsverzeichnis 14
Algorithmenverzeichnis 16
Abbildungsverzeichnis 18
Tabellenverzeichnis 22
Kapitel 1 Einleitung 24
Kapitel 2 Aktueller Stand der Software-Fehleranalyse 28
2.1 Fehler 28
2.2 Existierende Techniken 29
2.3 Beispiel einer Fehleranalyse 30
2.4 Problembeschreibung 32
2.5 Verwandte Arbeiten 34
2.5.1 Program-Profiling 34
2.5.2 Program-Tracing 37
2.5.3 Werkzeuge für die Fehlersuche 38
2.6 Zusammenfassung 39
Kapitel 3 Graphentheoretische Grundlagen 42
3.1 Grundbegriffe 42
3.1.1 Allgemeine Graphen 42
3.1.2 Wege: Definitionen und elementare Eigenschaften 43
3.1.3 Erreichbarkeit und Zusammenhang 45
3.1.4 Klassifizierung von Zusammenhangskomponenten 46
3.1.5 Abgeleitete Graphen 47
3.2 Die Standard-a-Zerlegung 49
3.2.1 Klassen geschlossener a-Wege und Kantenzerlegungen 49
3.2.2 Die Standard-a-Zerlegung allgemeiner Graphen 50
Kapitel 4 Ablaufgraphen von Programmen 54
4.1 Überblick 54
4.2 Ablaufgraphen prozeduraler Sprachen 54
4.3 Ablaufgraphen objektorientierter Sprachen 56
4.4 Fehlerbehandlung mit Ausnahmen in objektorientierten Sprachen 56
4.5 Definitionen 58
4.6 Format einer Java-Class-Datei 59
4.7 Java-Bytecode 62
4.8 Instrumentierung des Codes 66
Kapitel 5 Rekonstruieren von Abläufen in einem Ablaufgraphen 68
5.1 Algorithmus zum Auffinden der Ereignisknoten SETEVENTS 68
5.2 Markieren der Bögen 71
5.3 Rekonstruieren von Abläufen (Algorithmus RECONSTRUCTFLOW) 73
5.4 Beweis des Rekonstruierungsverfahrens 74
5.5 Verheftungsknoten als Ereignisknoten 76
5.6 Modifizierung des SETEVENTS Algorithmus 81
5.7 Beispiel einer Ablaufrekonstruktion 84
5.7.1 Auffinden der Ereignisknoten 84
5.7.2 Markieren der Bögen 89
5.7.3 Rekonstruieren der Abläufe 89
5.8 Effizienzbetrachtungen des Algorithmus SETEVENTS 90
5.9 Effizienzbetrachtungen des Algorithmus RECONSTRUCTFLOW 91
Kapitel 6 Analyse der Optimalität der Menge von Ereignisknoten 94
6.1 Formalisierung der Minimalitäts- und Optimalitätskriterien 94
6.2 Vergleich des SETEVENTS Algorithmus mit dem Knuth-Stevenson Algorithmus 97
6.3 Kombinieren des Algorithmus mit dem Knuth-Stevenson Algorithmus 99
6.4 Zerlegen der starken Zusammenhangskomponenten 104
6.5 Hierarchie der Algorithmen zum Finden der Überwachungsmenge der Knoten 110
6.6 Häufigkeitsanalyse und Wahrscheinlichkeitsanalyse 112
Kapitel 7 Ablaufrekonstruktion objektorientierter Programme 120
7.1 Auffinden und Platzieren von Überwachungspunkten in einem Programm 120
7.2 Protokollierung eines Ablaufes 121
7.3 Rekonstruieren eines Ablaufes in einem objektorientierten Programm 122
7.3.1 Ablauf innerhalb einer Methode 122
7.3.2 Algorithmus zur Rekonstruktion eines Ablaufs im kompletten Programm 122
7.3.3 Beispiel einer Rekonstruktion eines Objektorientierten Programms 128
7.3.4 Erweiterungen des Algorithmus zum Rekonstruieren eines Ablaufes im kompletten Programm 134
Kapitel 8 Überwachungsagent für Java-basierte Anwendungen 146
8.1 Beschreibung 146
8.1.1 Phase 1: Bestimmen von Überwachungspunkten eines Programms 147
8.1.2 Phase 2: Aktivieren der Überwachungspunkte und Protokollieren der Ereignisse 147
8.1.3 Phase 3: Rekonstruieren der Abläufe 149
8.2 Beispiele 149
8.3 Verifikation der Algorthmen 151
Kapitel 9 Zusammenfassung und Ausblick 156
A Abgeleitete Graphen 158
B gprof -Beispiel 160
C strace-Beispiel 161
D Byte-Code der main-Methode 162
Literatur 164
Index 168

Kapitel 2 Aktueller Stand der Software-Fehleranalyse (S. 5-6)

Dieses Kapitel soll einen Einstieg in die Thematik dieser Arbeit ermöglichen. Zuerst wird der Begriff „Fehler" erläutert und eine De.nition des Fehlers eingeführt. Danach wird auf die existierenden Techniken für die Fehlerlokalisierung eingegangen und ein Beispiel der Fehlersuche vorgestellt, um die Bedeutung der Ablaufanalyse zu veranschaulichen. Im weiteren wird die Problemstellung festgelegt und die verwandten Arbeiten untersucht, die sich mit dieser Thematik befassen.

2.1 Fehler

Spricht man über Fehler in der Ausführung eines Programms, so .nden Begriffe wie error, failure, fault und bug ihre Verwendung. Hierzu existiert in der Literatur eine Reihe oft unterschiedlicher De.nitionen. Eine gebräuchliche, wenn auch informale Definition für den Begriff Fehler (hier error gemeint), liefert [Cla03]. Demnach ist ein Fehler die Ermittlung oder Ausgabe eines falschen Ergebnisses durch eine Rechenanlage. Man unterscheidet des Weiteren Hardwareund Softwarefehler. Diese Arbeit konzentriert sich auf Softwarefehler, welche aus der falschen Anweisungsfolge innerhalb eines Programms resultieren. Dies kann zum Beispiel durch eine fehlerhafte Implementierung oder durch falsche Algorithmen entstehen.

Erschwert wird die Begriffswahl auch dadurch, dass eine Unterscheidung zwischen dem beobachteten Fehler (Folgefehler) und dem eigentlichen Fehler erfolgen muss. Beim eigentlichen Fehler ist der Programmzustand, in welchem er initial auftritt, von Bedeutung. Bei den meisten beobachteten Fehlern handelt es sich hingegen um Folgefehler. Solch ein Folgefehler existiert immer nur als Konsequenz und erschwert dabei die Suche nach dem eigentlichen Fehler. Aus diesen Überlegungen lässt sich folgende De.nition eines Fehlers formulieren:

Definition 2.1 Ein Fehler (error) in einem Programm wird durch einen inkorrekten Programmzustand st ersichtlich. Dieser ist dann dadurch gekennzeichnet, dass eine oder mehrere Variablen einen inkorrekten Wert zum Zeitpunktt besitzen.

Hierzu wird in der Literatur auch der Begriff des dynamischen bzw. Laufzeitfehlers verwendet. Diesem stehen Fehler gegenüber, welche zur Zeit der Übersetzung (Kompilierung) eines Programms auftreten. Letztere resultieren zum Beispiel aus Fehlern in der Programmsyntax (statische Fehler). Die Laufzeitfehler bilden die logischen Fehler, die durch eine falsche Anordnung von ansonsten syntaktisch korrekten Programmanweisungen entstehen. Deren Auf.nden ist mit hohem Aufwand verbunden, da sie in der Regel nicht vom Programm erkannt werden.

Stattdessen liefert das Programm lediglich ein falsches Ergebnis. Der Nutzer muss daher den Programmablauf analysieren, um den eigentlichen Fehler (die Ursache für Folgefehler) zu finden. Der Laufzeitfehler und der Fehler (De.nition 2.1) haben in dieser Arbeit die gleiche Bedeutung.

2.2 Existierende Techniken

Es gibt mehrere Strategien, um Fehler zu lokalisieren und deren Ursachen zu finden:

• Schritt für Schritt Debugging von Programmen
• und Logging während der Ausführung des Programms
• Post-Mortem Analyse nach dem Absturz eines Programms (core-dump)

Debugging

Debugger ermöglichen, ein Programm Schritt für Schritt auszuführen und bei jedem Schritt den Zustand des Programms zu kontrollieren [Ric04]. Um die Fehlersuche zu erleichtern, können Visualisierungswerkzeuge eingesetzt werden wie zum Beispiel der Data Display Debugger (DDD) [Nor03].

Tracing

Um sich einen Überblick über ein Programm während der Ausführung zu verschaffen, kann das Programm mit Ausgabefunktionen instrumentiert werden. Zum Beispiel können in C/C++ die printf-Anweisung und in java die System.out.print-Anweisung dafür benutzt werden. Diese Anweisungen können jedoch nicht immer alle Kontrollpfade abdecken und sie können sogar manchmal selbst Fehler verursachen. Das nächste Problem ist, dass die permanent laufenden Server-Applikationen in kurzer Zeit eine große Menge von Daten generieren können, was das Leistungsverhalten des Gesamtsystem negativ beein.ussen kann.

core-Dumps

Die modernen Betriebssysteme haben die Möglichkeit den Zustand eines Prozesses im Fehlerfall in einer Datei (core-dump) abzuspeichern. Diese Datei enthält folgende Informationen über den Prozess zum Zeitpunukt des Auftretens des Fehlers:

• Registerinhalt
• Adressen der zuletzt ausgeführten Instruktion
• Speicherabbild des Prozesses

Debugger können diese Informationen bearbeiten und erlauben es, den Fehler auf der Instruktionsoder Quellcode-Ebene zu lokalisieren. Trotzdem gibt ein Core-Dump nicht alle nötigen Informationen, um einen Fehler zu lokalisieren. Zum Beispiel kann der Kontroll.uss bis zum Auftreten des Fehlers nicht reproduziert werden. Einige Fehler können außerdem ohne den kompletten Kontroll.uss nicht rekonstruiert werden. Eine detaillierte Beschreibung über die Core-Dump Dateien kann in [Ric04] gefunden werden.