Upload
wilda-ehnes
View
108
Download
0
Embed Size (px)
Citation preview
UN IVERSITÄT PA DERBO RNDie U niversitä t der Inform ationsgesellsch a ft
Modelchecker – REDTool:“Region-Encoding Diagram”
Stefan Neumann
2
UN IVERSITÄT PA DERBO RNDie U niversitä t der Inform ationsgesellsch a ft
SOFTWARE ENGINEERING GROUP
Agenda
Einführung in RED
Grundlagen kontinuierliche Modelle
Darstellung kont. Modelle CDD / CRD
Zusammenfassung / Fazit
3
UN IVERSITÄT PA DERBO RNDie U niversitä t der Inform ationsgesellsch a ft
SOFTWARE ENGINEERING GROUP
Modelchecker RED
Entstanden: Dept. of Electrical Engineering National Taiwan UniversityStändig weiterentwickelt / theoretisch orientiertNutzbar für Bereiche Lehre und ForschungKommerzielle Nutzung nur nach AbspracheKonsolenanwendung
Weblink: http://www.iis.sinica.edu.tw/~farn/red
4
UN IVERSITÄT PA DERBO RNDie U niversitä t der Inform ationsgesellsch a ft
SOFTWARE ENGINEERING GROUP
Schwerpunkt/Ausrichtung
Diskrete Systeme Kontinuierliche SystemeHybride Systeme
Train-Gate-Control, modellierbar in REDDiskrete TeileKontinuierliche TeileHybride Teile
Diskret Kontinuierlich
Hybrid
5
UN IVERSITÄT PA DERBO RNDie U niversitä t der Inform ationsgesellsch a ft
SOFTWARE ENGINEERING GROUP
RED im Überblick
Rückwärts- und Vorwärtsanalyse
Automatische Erkennung:DiskretKontinuierlichHybrid=> Verwendung unterschiedlicher Datenstrukturen
Auffinden von Gegenbeispielen
Heuristiken zur Variablenordnung
6
UN IVERSITÄT PA DERBO RNDie U niversitä t der Inform ationsgesellsch a ft
SOFTWARE ENGINEERING GROUP
Motivation des Vortrags
Orientierung im theoretischer BereichKontinuierliche / Hybride Systeme
Vortrag konzentriert sich auf die TheorieTeilbereich: Datenstrukturen zur Darstellung kontinuierlicher Systeme
7
UN IVERSITÄT PA DERBO RNDie U niversitä t der Inform ationsgesellsch a ft
SOFTWARE ENGINEERING GROUP
Grundlagen – Kontinuierliche Systeme – Timed Automata
Bestandteile Timed Automata:Endlicher GraphEndliche Menge von clocks X
Graph besteht aus:Locations (Orte)Kanten
X : x1 , ... , xn
8
UN IVERSITÄT PA DERBO RNDie U niversitä t der Inform ationsgesellsch a ft
SOFTWARE ENGINEERING GROUP
Timed Automata - Aufbau
Locations:Haben Invarianten
Solange Invariante erfüllt, kann in verweilt werden
Kanten:Schalten in NullzeitMit Bedingung versehenKönnen Clocks zurücksetzen
S1x 1000
x 1000
x 0
S2
x: 0
S1
Location hat Invariante :
x 1000S1
9
UN IVERSITÄT PA DERBO RNDie U niversitä t der Inform ationsgesellsch a ft
SOFTWARE ENGINEERING GROUP
Darstellung von Bereichen / Clock-Regions
Fragestellung: Ist der Wert innerhalb einer Region?Schwierigkeiten:
Effiziente DarstellungEffiziente Modifikation
y
x1 3
3
2
1 X 3 2 Y 3
10
UN IVERSITÄT PA DERBO RNDie U niversitä t der Inform ationsgesellsch a ft
SOFTWARE ENGINEERING GROUP
Mögliche Darstellungform
BDD – artige Darstellungsformen, Vorteile:Platzeffizient (Reduzierbar, Variablenordnung)Effiziente Modifizierung möglich von z. B.:
BDD ähnliche FormenTypisch, Variablen in den KnotenKanten mit Bedingungen / Verschiedene Formen
X
Y
TR U E
1 X 3
Mögliche KantenbeschriftungIntervalldarstellung:Ungleichung:
1,3
1 3
11
UN IVERSITÄT PA DERBO RNDie U niversitä t der Inform ationsgesellsch a ft
SOFTWARE ENGINEERING GROUP
Lösung - CDD
CDD – Clock Difference DiagramEffiziente Darstellungsform
Kantenbeschriftung: Intervallgrenzen1,3
X
Y
TRUE
2,3y
x1 3
3
2
12
UN IVERSITÄT PA DERBO RNDie U niversitä t der Inform ationsgesellsch a ft
SOFTWARE ENGINEERING GROUP
RED – Darstellungsform CRD
CRD – Clock-Restriction-Diagram
y
x1 3
3
2
1 X 3 2 Y 3
Formel umstellen zu:
0-X
X – 0
0-Y
Y-0
TRUE
1
3
2
30 X 1 , X 0 3
0 Y 2,Y 0 3
13
UN IVERSITÄT PA DERBO RNDie U niversitä t der Inform ationsgesellsch a ft
SOFTWARE ENGINEERING GROUP
Eigenschaften CRD / CDD
Effizienz der Darstellung (CRD/CDD) im BeispielCDD erzeugt kleineren Graph
Im Beispiel zu beachtenBeispiel sehr einfachWas passiert bei Manipulation der Strukturen
NachfolgendVereinigung zweier Regionen
14
UN IVERSITÄT PA DERBO RNDie U niversitä t der Inform ationsgesellsch a ft
SOFTWARE ENGINEERING GROUP
Manipulation (CDD/CRD)
Vereinigung von zwei Clock-Regions
1 X 3 2 Y 3
Zu beobachtenDarstellungsgrößeDarstellungsform
2 X 3 1 Y 3
y
x1 3
3
2
15
UN IVERSITÄT PA DERBO RNDie U niversitä t der Inform ationsgesellsch a ft
SOFTWARE ENGINEERING GROUP
Vereinigung CDD
1 X 3 2 Y 3
y
x1 3
3
2
Stichwort: Fragmentierung
2 X 3 1 Y 3
1,2
TRUE
Y
X X X
Y Y
2,3 2,3
2,32,3
1,2
16
UN IVERSITÄT PA DERBO RNDie U niversitä t der Inform ationsgesellsch a ft
SOFTWARE ENGINEERING GROUP
Vereinigung CRD
BeobachtungNur zwei PfadeCRD und CDD fast gleich großRedundanz
y
x1 3
3
2
0-X
X - 0
0-Y
Y-0
TRUE
1
3
2
3
X - 0
0-Y
Y-0
3
1
2
3
0-X
TRUE
0-X
X - 0
0-Y
Y-0
TRUE
1
3
2
3
X - 0
0-Y
Y-0
3
1
2
3
17
UN IVERSITÄT PA DERBO RNDie U niversitä t der Inform ationsgesellsch a ft
SOFTWARE ENGINEERING GROUP
Beobachtung
Unterschiede nach Vereinigung:CDD/CRD fast gleich großMehrere Identische Teile beim CRD2 Pfade beim CRD / 3 Pfade beim CDD
Experimente bestätigen diese BeobachtungenZustandsmengenexplosion bei CDDs mit zunehmender Anzahl Clocks
18
UN IVERSITÄT PA DERBO RNDie U niversitä t der Inform ationsgesellsch a ft
SOFTWARE ENGINEERING GROUP
Zusammenfassen CRD
Vereinfachen nach VereinigungGleiche TeileZusammenfassen
0-X
X-0
0-Y
Y-0
TRUE
1
3
2
3
X-0
0-Y
Y-0
3
1
2
3
1,2
TRUE
Y
X X X
Y Y
2,3 2,3
2,32,3
1,2
0-X
X - 0
0-Y
Y-0
TRUE
1
3
2
X - 0
0-Y
3
1
2
19
UN IVERSITÄT PA DERBO RNDie U niversitä t der Inform ationsgesellsch a ft
SOFTWARE ENGINEERING GROUP
Darstellung von CRDs
Weitere Optimierungen möglich:Variablenordnung (Clock-Reihenfolge)Zone-ContainmentKaskadieren: Graph an bestimmten Stellen erweitern
Dadurch Zone-Containment Ermittlung einfacher
Weiterer Punkt: Kombination CRD / BDD
20
UN IVERSITÄT PA DERBO RNDie U niversitä t der Inform ationsgesellsch a ft
SOFTWARE ENGINEERING GROUP
CRD und BDD
CRD kombinierbar mit BDD, wenn:BDD hat nur TRUE-Endknoten
Operatoren wie Schnitt, Vereinigung bei CRDEntsprechend and bzw. or bei BDD
Beispiel: A BA
Bt
f
ft
TRUE FALSE
A
Bt
f
t
TRUE
21
UN IVERSITÄT PA DERBO RNDie U niversitä t der Inform ationsgesellsch a ft
SOFTWARE ENGINEERING GROUP
Kombiniert
0-X
X - 0
0-Y
Y-0
TRUE
1
3
2
3
A
Bt
f
t
A
Bt
f
t
TRUE
0-X
X - 0
0-Y
Y-0
TRUE
1
3
2
3
* =
22
UN IVERSITÄT PA DERBO RNDie U niversitä t der Inform ationsgesellsch a ft
SOFTWARE ENGINEERING GROUP
Zusammenfassung
Schwerpunkt Modelchecker RED
Beispiel Clock-Zones
Vergleich: Datenstrukturen CRD vs. CDDDarstellungsformModifikationEffizienz
23
UN IVERSITÄT PA DERBO RNDie U niversitä t der Inform ationsgesellsch a ft
SOFTWARE ENGINEERING GROUP
Fazit
REDSchwerpunkt Lehre - ForschungTheoretischer SchwerpunktAktive Weiterentwicklung
ProblematischEinsatz im kommerziellen Bereich schwierigWenig DokumentationWebseiten wenig hilfreich:
http://cc.ee.ntu.edu.tw/~farn/red/ http://cc.ee.ntu.edu.tw/~farn/