23
U N IV ER S ITÄ T PA DERBORN Die Universität der Informationsgesellschaft Modelchecker – RED Tool:“Region-Encoding Diagram” Stefan Neumann

Modelchecker – RED Tool: Region-Encoding Diagram Stefan Neumann

Embed Size (px)

Citation preview

Page 1: Modelchecker – RED Tool: Region-Encoding Diagram Stefan Neumann

UN IVERSITÄT PA DERBO RNDie U niversitä t der Inform ationsgesellsch a ft

Modelchecker – REDTool:“Region-Encoding Diagram”

Stefan Neumann

Page 2: Modelchecker – RED Tool: 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

Page 3: Modelchecker – RED Tool: Region-Encoding Diagram Stefan Neumann

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

Page 4: Modelchecker – RED Tool: Region-Encoding Diagram Stefan Neumann

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

Page 5: Modelchecker – RED Tool: Region-Encoding Diagram Stefan Neumann

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

Page 6: Modelchecker – RED Tool: Region-Encoding Diagram Stefan Neumann

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

Page 7: Modelchecker – RED Tool: Region-Encoding Diagram Stefan Neumann

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

Page 8: Modelchecker – RED Tool: Region-Encoding Diagram Stefan Neumann

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

Page 9: Modelchecker – RED Tool: Region-Encoding Diagram Stefan Neumann

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

Page 10: Modelchecker – RED Tool: Region-Encoding Diagram Stefan Neumann

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

Page 11: Modelchecker – RED Tool: Region-Encoding Diagram Stefan Neumann

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

Page 12: Modelchecker – RED Tool: Region-Encoding Diagram Stefan Neumann

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

Page 13: Modelchecker – RED Tool: Region-Encoding Diagram Stefan Neumann

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

Page 14: Modelchecker – RED Tool: Region-Encoding Diagram Stefan Neumann

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

Page 15: Modelchecker – RED Tool: Region-Encoding Diagram Stefan Neumann

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

Page 16: Modelchecker – RED Tool: Region-Encoding Diagram Stefan Neumann

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

Page 17: Modelchecker – RED Tool: Region-Encoding Diagram Stefan Neumann

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

Page 18: Modelchecker – RED Tool: Region-Encoding Diagram Stefan Neumann

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

Page 19: Modelchecker – RED Tool: Region-Encoding Diagram Stefan Neumann

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

Page 20: Modelchecker – RED Tool: Region-Encoding Diagram Stefan Neumann

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

Page 21: Modelchecker – RED Tool: Region-Encoding Diagram Stefan Neumann

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

* =

Page 22: Modelchecker – RED Tool: Region-Encoding Diagram Stefan Neumann

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

Page 23: Modelchecker – RED Tool: Region-Encoding Diagram Stefan Neumann

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/