Dissertation
Automatische Testfallgenerierung aus
kontrolliert natürlichsprachlichen
Anforderungsspezifikationen für reaktive
Echtzeitsysteme
Schriftliche Arbeit
zur Erlangung des Grades
„Doktor der Naturwissenschaften“
vorgelegt von
Matthias Schnelte
Paderborn, März, 2011
Inhaltsverzeichnis
1 Einleitung 1
1.1 Motivation / Problemstellung ........................................................................... 1
1.2 Zielsetzung ....................................................................................................... 2
1.3 Lösungsansatz .................................................................................................. 3
1.4 Beitrag .............................................................................................................. 5
1.5 Aufbau der Arbeit ............................................................................................. 5
2 Grundlagen 7
2.1 Reaktive Echtzeitsysteme ................................................................................. 7
2.2 Testen ................................................................................................................ 7
2.3 Modellbasiertes Testen ..................................................................................... 8
2.3.1 Testauswahlkriterien ............................................................................... 10
2.4 Automatische Handlungsplanung ................................................................... 12
2.4.1 Repräsentationen von Planungsproblemen ............................................. 13
2.4.2 Bedingte Effekte ..................................................................................... 16
2.4.3 Repräsentation von Zeit .......................................................................... 17
2.4.4 Planungsalgorithmen .............................................................................. 21
2.5 Suchalgorithmen ............................................................................................. 23
2.5.1 Uninformierte Suchen ............................................................................ 24
2.5.2 Heuristische Suche ................................................................................. 25
2.6 Verarbeitung von natürlicher Sprache ........................................................... 27
2.7 Kontrollierte natürliche Sprache .................................................................... 28
3 Stand der Forschung 31
3.1 Kontrollierte natürliche Sprachen .................................................................. 31
3.1.1 Attempto Controlled English .................................................................. 31
3.1.2 Processable English ................................................................................ 35
3.1.3 Kontrollierte Sprachen für Logiken ........................................................ 35
3.1.4 Satzmuster für Echtzeitsysteme .............................................................. 39
3.2 Modellbasiertes Testen von Echtzeitsystemen ............................................... 42
3.2.1 Modellierung des Echtzeitverhaltens ...................................................... 43
3.2.2 Testfallgenerierung ................................................................................. 44
3.2.3 Behandlung von Nichtdeterminismus .................................................... 45
4 Lösungskonzept 47
4.1 Anwendungsbeispiel ....................................................................................... 48
4.1.1 Aufbau des Dokumentes ......................................................................... 48
4.1.2 Schnittstellenbeschreibung ..................................................................... 48
4.1.3 Funktionalität .......................................................................................... 49
4.1.4 Alarmsystem ........................................................................................... 51
4.2 Erfassen der Anforderungen ........................................................................... 52
4.2.1 Wörterbuch ............................................................................................. 52
4.2.2 Grammatik .............................................................................................. 53
4.3 Syntax der KNS .............................................................................................. 56
4.3.1 Grundsymbole ........................................................................................ 56
4.3.2 Wörterbuch ............................................................................................. 56
4.3.3 Anforderungen ........................................................................................ 57
4.3.4 Statische Semantik .................................................................................. 61
4.4 Spracherweiterungen ...................................................................................... 62
4.4.1 Numerische Signalwerte ......................................................................... 62
4.4.2 Disjunktionen ......................................................................................... 64
4.4.3 Konjunktionen im Trigger ...................................................................... 65
4.4.4 Reihung von Triggern ............................................................................. 67
4.4.5 Beschreibung gleichartiger Anforderungen ............................................ 71
4.5 Formales Modell ............................................................................................ 73
4.5.1 Repräsentation durch PDDL ................................................................... 74
4.5.2 Repräsentation durch TQEs und Chronicles .......................................... 75
4.6 Übersetzungsvorgang ..................................................................................... 80
4.6.1 Erzeugung der Aktionen aus den Eingabesignalen ................................. 80
4.6.2 Bedingte Effekte aus Anforderungen ...................................................... 81
4.6.3 Zuordnung zu Aktionen .......................................................................... 81
4.6.4 Übersetzungsmuster ............................................................................... 82
4.7 Testauswahlkriterien ....................................................................................... 90
4.7.1 Positivtests .............................................................................................. 91
4.7.2 Negativtests ............................................................................................ 93
4.7.3 Zusammenhang zu anderen Testauswahlkriterien .................................. 95
4.8 Testfallgenerierung ......................................................................................... 96
4.8.1 POCL Planungsalgorithmus mit Zeitbedingungen ................................. 97
4.8.2 Beispiel ................................................................................................. 100
4.8.3 Erklärung der Testfälle ......................................................................... 103
4.8.4 Heuristiken für die Suche ..................................................................... 104
4.8.5 Temporales Netzwerk ........................................................................... 107
4.8.6 Nicht deterministisches Zeitverhalten .................................................. 109
4.8.7 Nicht erreichbare Suchziele .................................................................. 111
4.8.8 Testfälle für verlinkte Anforderungen ................................................... 112
4.9 Ausführen und Bewerten der Testfälle ......................................................... 115
4.10 Alternatives Lösungskonzept ...................................................................... 116
4.10.1 Beispiel ............................................................................................... 117
4.10.2 Evaluierung ......................................................................................... 118
5 Realisierung und Evaluierung 121
5.1 Prototypische Implementierung .................................................................... 121
5.1.1 Spezifikationseditor .............................................................................. 121
5.1.2 Implementierungsdetails ....................................................................... 123
5.2 Fallstudie Türsteuergerät .............................................................................. 124
5.2.1 KNS Spezifikation ................................................................................ 124
5.2.2 Evaluation der Testfallgenerierung ....................................................... 137
5.3 Fallstudie KFZ-Alarmsystem ....................................................................... 139
5.4 Fallstudie Hausalarmsystem ......................................................................... 140
6 Zusammenfassung und Ausblick 143
6.1 Ausblick ........................................................................................................ 143
Loading more pages...