Upload
hiltraud-weit
View
106
Download
0
Embed Size (px)
Citation preview
LTL Modellüberprüfung
LTL - Modellüberprüfung
Vortrag von
Olaf Noppens
Hauptseminar Modellüberprüfung
Wintersemester 2001/2002
LTL Modellüberprüfung
Einführung in die Modellüberprüfung
Überprüfung der Korrektheit von Soft- und Hardware Überprüfung der Korrektheit des Gesamtsystems Überprüfung der Korrektheit kritischer Teilbereiche
nebenläufige Programme & -teile (kritische Regionen) Systeme in Kernkraftwerken, in der Flugüberwachung,... Herstellung von Computerchips
LTL Modellüberprüfung
Spezifikation. . .. . .
?LTL
LTL Modellüberprüfung
Programbegin. . .end
Automatentheorie
Büchi - Automaten
LTL Modellüberprüfung
Lineare Temporallogik
Aussagenlogik: zeitlose Aussagen (inkl. Verknüpfungen)
Es regnet
Zeit
Lineare Temporallogik: zeitliche Aussagen
diskrete Zeit
Struktur der Aussagenlogik: (linear-time propositional temporallogic):
Vergangenheits- und zukunftsorientierte Operatoren
,...,
Es regnet nicht
LTL Modellüberprüfung
LTL: Grundlagen
Sei = ( 0, 1, 2,..) Folge von Belegungen für Formel p
( , i) |= p gdw. i |= p
( , i) |= p q gdw. ( , i) |= p und ( , i) |= q
LTL Modellüberprüfung
LTL-Operatoren: Zukunft
Next: ( , i) |= p gdw. ( , i+1) |= p
W/F
Zeit
Until: ( , i) |= (p U q) gdw. k j mit ( , k) |= q und j i<k mit ( , i) |= p
Eventually: p := true U p Always: p := p
LTL Modellüberprüfung
LTL-Operatoren: Vergangenheit
aktueller Zeitpunkt gehört zur Vergangenheit und Zukunft (schwache Relation!)
deshalb: strikte Operatoren (< bzw. > in Def. verwendet)
Vergangenheitsbezogene Operatoren:
Previous () Next ( )
Since (S) Until (U)
Once () Eventually( )
Has-Always-Been () Always ( )
Zeit
LTL Modellüberprüfung
Spezifikation
Spezifikation = geforderte Eigenschaften
Hier: beim fertigen Programm nachweisen (alternativ: Spezifikation in die Programmsynthese einfließen lassen)
LTL Modellüberprüfung
Nichtdeterministischer Automat über Worten unendlicher Länge w = a0 a1 a2 a3 a4 a5...
A=(
Büchi-Automat
, S,
S : Zustandsmenge
Lauf r von w : s0, s1, s2, s3, s4, ... mit s0 S0, si+1 (si, ai)
lim(r) = { s | s= si für unendliche viele i‘s} w akzeptiert falls lim(r) F .
a, b
ab
,
: S 2S
: Alphabet ={a, b}
S0,
S0 : Startzustände
F).
F S: Akzeptanzzustände
LTL Modellüberprüfung
Alternierender Automat(I) zunächst über endlichen Worten
Übergangsrelation als Formel aufgefasst:
(s, a) = (s1 s2) (s3 s4)
s
s2s1 s3 s4
aa
akzeptiert w akzeptiert w
(s,a) = s1 s2
(s, a) = {s1, s2}
s
s1
akzeptiert w
akzeptiert w
s2
a a
LTL Modellüberprüfung
B+(S): Menge aller Formeln über S, bestehend aus
S = {s1, s2, s3), = ( (s1 s2) s3 ) B+(S)
{s1, s3} erfüllt
Alternierender Automat
Aalternierender Automat =( , S, S0, , F) mit : Alphabet
S: Zustandsmenge S0 : Anfangszustände F : Akzeptanzzustände
: Übergangsrelation S B+(S)
LTL Modellüberprüfung
Alternierender Automat: Berechnungen
Sei w = a0 a1 a2 a3...an .
Berechnung über w:
s0
x1
x
x2
x11
x3
. . .
x1 x2 x3
r(x) = s und (s,a) = , x1,...,xk Kinder von x.
Dann muss {r(x1),...r(xk)} erfüllen
{s1,s2,s3} erfüllt
s1 s3
s2
Berechnung wird akzeptiert, wenn alle Knoten mit Tiefe n mit Zuständen aus F markiert sind
LTL Modellüberprüfung
Büchi: Abschlusseigenschaften
Analoge Definition für alternierende Büchi-Automaten Jeder alternierende Büchi-Automat kann in einen
„normalen“ Büchi – Automaten überführt werden Nichtleerheitsproblem ist entscheidbar Schnitt- und Vereinigungsautomat konstruierbar
LTL Modellüberprüfung
S \\
Von LTL nach Büchi: Konstruktion
Umformung anhand eines Beispiels:
S \\
= (O p) U q
{p, q} {p} {q} {}
• = Potenzmenge (p,q)
• S={a, a| a Teilfomel}
O p
p (O p)• (s,a) =
true, falls s a
truetrue
true true
• (p q, a) = (p, a) (q, a) • (p U q, a) = (q, a) ( (p, a) (p U q) )
p p false false
false falsefalse, falls s a
• ( p, a) = (p, a)
• (O p, a) = p
pp p p
truetrue
true true
false false
false false
• F={ = (a U b) | S}
{p, q} {p} {q} {}
O p
p (O p)
LTL Modellüberprüfung
Verifikation
Automaten aus dem Programm gewinnen (A1)
Automaten aus den LTL-Spezifikationen (A2)
A1 A2 = ?
LTL Modellüberprüfung
Zusammenfassung
Spezifikation LTL Büchi-Automaten Automatentheorie (Schnitt, Leerheitsproblem) Alternative Vorgehensweise: über nicht-
alternierenden Büchi Alternative Modellüberprüfung, z.B. CTL/CTL* -
Techniken