Traduzione di LTL in GBA: costruzione di un tableau

(1)

Traduzione di LTL in GBA: costruzione di un tableau

1. Si costruisce un tableau T = (N, ∆

T

, {n

⁰

}, L

T

, Σ

T

, F

_T

) per la formula G da tradurre (in cui sono eventualmente stati cancellati i nodi chiusi), e dove:

• N `e l’insieme dei nodi,

• n

⁰

∈ N `e la radice,

• ∆

_T

`e la relazione padre-figlio,

• Σ

_T

`e l’alfabeto:

Σ _T = 2 ^subf (G)∪{ B|B∈subf (G)}

• L

_T

: N → Σ `e la funzione di etichettatura dei nodi;

• F

_T

= {f

_E1

, ..., f

_Em

}, dove E

¹

, ..., E

_m

sono tutte le eventualities in subf (G) e per ogni i = 1, ..., m, se E

_i

= 3A

i

oppure E

_i

= B

_i

U A

_i

:

f

_E_i

= {n ∈ N | E

i

6∈ L

T

(n) oppure A

i

∈ L

T

(n)}

(2)

Traduzione di LTL in GBA: estrazione dell’automa dal tableau 2. Da T si estrae il grafo degli stati (foglie del tableau, oppure nodi a cui `e applicata la

regola NEXT), ciascuno dei quali `e etichettato dalla congiunzione dei letterali del nodo corrispondente.

A

_G

= (S, ∆, I, L, 2

²^P

, F )

Stati: S = {n ∈ N | n `e espanso mediante la regola NEXT}

Stati iniziali:

I = {n ∈ S | esiste un cammino in T da n

⁰

a n in cui n `e l’unico elemento di S (nel cammino non `e mai applicata la regola NEXT)}

Relazione di transizione:

∆ = {(n

_i

, n

_j

) | n

_i

, n

_j

∈ S e esiste un cammino in T da n

_i

a n

_j

che non contiene altri elementi di S}

Etichette:

L(n) = ℓ

¹

∧ ... ∧ ℓ

_k

se n ∈ N e ℓ

¹

, ..., ℓ

_k

sono tutti i letterali che occorrono in L

_T

(n) (se k = 0 allora L(n) = ⊤)

Stati di accettazione: F = {f

¹

, ..., f

_m

}, dove per ogni i = 1, ..., m f

_i

= (f

Ei

∩ S)

Si ottiene un GBA etichettato da congiunzioni di letterali

(3)

Esempio 1

1 : 23p

2 : 3p ,

23p, (23p)

^∗

3 : p,

23p, ( 3p )

^∗

, (23p)

^∗

23p = 1

4 :

3p,

23p, ( 3p )

^∗

,

(23p)

^∗

5 : 3p, 23p

3p,

23p, (23p)

^∗

= 2

P = {p}.

Non ci sono nodi chiusi da cancellare.

3 e 4 sono stati.

Nodi di accettazione per 3p: {1, 3}

A

_23p

= (S, ∆, I, L, 2

²^P

, {f

¹

}) dove:

S = {3, 4}, ∆ = S × S, I = {3, 4}, f

¹

= {3}

L(3) = p, L(4) = ⊤

(4)

Esempio 1: semplificazione dell’automa L’automa

A

_23p

= (S, ∆, I, L, 2

²^P

, {f

¹

})

si pu`o semplificare nel BA in cui c’`e un unico insieme di stati di accettazione: F = {3}.

3 p

4 true

Semplificazione

Se tra le sottoformule della formula iniziale c’`e una sola eventuality E, allora si costruisce direttamente un BA con F = f

_E

.

Nota: se la formula iniziale non contiene eventualities, allora tutti gli stati sono stati di

accettazione dell’automa.

(5)

Esempio 2 1 : p ∨ 3q

2 : p, (p ∨ 3q)

^∗

9 : ⊤

⊤ = 9

3 : 3q, (p ∨ 3q)

^∗

4 : q, (3q)

^∗

, (p ∨ 3q)

^∗

⊤ = 9

5 :

3q, (3q)

^∗

, (p ∨ 3q)

^∗

6 : 3q

7 : q, (3q)

^∗

⊤ = 9

8 :

3q, (3q)

^∗

3q = 6

Notare: nel calcolo senza memoria delle formule espanse il nodo 6 non sarebbe generato,

ma verrebbe aggiunto un link dal nodo 5 al nodo 3.

(6)

Esempio 2: l’automa

2 p

4 q 5

true

9 true 7

q 8

true

(7)

Esempio 3 G

⁰

= 3p

G

¹

= 3¬p

1 : 3p, 3¬p

3 : p, 3¬p, G

^∗⁰

4 : ¬p, p, G

^∗1

, G

^∗0

5 :

3¬p, p, G

^∗1

, G

^∗0

6 : 3¬p 7 : ¬p, G

^∗1

15 : ⊤

⊤ = 15

8 :

3¬p, G

^∗¹

3¬p = 6

9 :

3p, 3¬p, G

^∗⁰

10 : ¬p,

3p, G

^∗1

, G

^∗0

11 : 3p 12 : p, G

^∗0

⊤ = 15

13 :

3p, G

^∗⁰

3p = 11

14 :

3¬p,

3p, G

^∗1

, G

^∗0

3¬p, 3p = 1

(8)

Dopo aver cancellato i nodi chiusi 1 : 3p, 3¬p

3 : p, 3¬p, G

^∗⁰

5 :

3¬p, p,

G

^∗1

, G

^∗0

6 : 3¬p

7 : ¬p, G

^∗1

15 : ⊤

⊤ = 15

8 :

3¬p, G

^∗¹

3¬p = 6

9 :

3p, 3¬p, G

^∗⁰

10 : ¬p,

3p, G

^∗1

, G

^∗0

11 : 3p

12 : p, G

^∗0

⊤ = 15

13 :

3p, G

^∗⁰

3p = 11

14 :

3¬p,

3p, G

^∗1

, G

^∗0

3¬p, 3p = 1

(9)

L’automa

5 p

10 -p 14

true

7 -p

8 true

12 p

13 true

15 true

F = {f

¹

, f

²

} con

f

1

= {5, 7, 8, 12, 15}

e

f

²

= {7, 10, 12, 13, 15}

(10)

Relazione tra la formula iniziale e l’automa generato dalla traduzione L’automa A

G

generato dalla traduzione della formula G `e tale che:

L(A

_G

) ` e l’insieme dei modelli di G (ogni accepting run rappresenta un modello di G, e viceversa).

Quindi G ` e soddisfacibile sse L(A

_G

) 6= Ø.

Per trovare un modello di G

Costruire A

_G

e, se L(A

_G

) 6= ∅, scegliere un’esecuzione accettante ρ e una qualsiasi parola accettata da ρ: `e un modello di G.

Complessit` a della traduzione

Il numero di nodi costruiti ed il tempo per costruirli `e esponenziale nella dimensione della formula iniziale.

L’esperienza mostra comunque che generalmente l’automa costruito `e relativamente piccolo.

(11)

Algoritmo di costruzione dell’automa conservando soltanto gli stati (descrizione intuitiva)

• I nodi vengono modificati dalle regole di espansione, e non si mantengono tutti in memoria

• Il controllo di cicli viene effettuati soltanto su stati

Applicazione di regole statiche

• Quando un nodo viene espanso mediante una regola “statica” (diversa dalla rego- la NEXT) che non ramifica, l’espansione sostituisce il nodo stesso:

• Quando un nodo viene espanso con una regola che ramifica, il nodo viene copiato, insieme agli archi entranti:

S’ S’ S’ S’

A&B,S A,B,S,(A&B)* AvB,S A,S,(AvB)* B,S,(AvB)*

(12)

Applicazione della regola NEXT

Quando non si possono pi`u applicare regole statiche si controlla l’esistenza di cicli:

• se il grafo gi`a contiene un nodo s

^′

etichettato dallo stesso insieme di formule di quello attuale s, il nodo s non viene espanso, ma i suoi archi entranti sono aggiunti a quelli di s

^′

e s viene cancellato.

Altrimenti:

• se L(s) = Λ,

A

1

, ...,

A

_n

, si crea un nuovo nodo s

^′

, etichettato da A

¹

, ..., A

_n

e si aggiunge un arco da s a s

^′

.

Stati di accettazione

Per ogni eventuality E

i

= 3A

i

o E

i

= B

i

U A

_i

sottoformula dell’insieme iniziale:

F = {f

¹

, ...., f

_k

} con

f

_i

= {s | E

_i

6∈ L(s) oppure A

_i

∈ L(s)}

(13)

Traduzione di LTL in GBA: algoritmo Un nodo `e una struttura dati che contiene i seguenti campi:

Name: un identificatore unico per il nodo

Incoming: una lista degli identificatori dei nodi che hanno archi entranti nel nodo

New, Literals, Old, Next: insiemi di sottoformule della formula iniziale, o sottofor- mule precedute da

New contiene le formule ancora da espandere, o da prendere comunque in considerazione.

Esse verranno via via estratte da questo insime e spostate negli altri: i letterali vengono spostati in Literals, le formule espanse in Old; quando viene estratta una formula della forma

A, la formula A viene inserita nell’insieme Next.

Se N `e un nodo, N ame(N ), Incoming(N ), N ew(N ), Literals(N ), Old(N ) e N ext(N ) sono i valori dei rispettivi campi di N .

Algoritmo Inizializzazione: si crea il nodo iniziale N

⁰

con:

New(N

⁰

) = insieme iniziale di formule

Incoming(N

⁰

) = {init} (identifica gli stati iniziali dell’automa)

Literals(N

⁰

) = Old(N

⁰

) = Next(N

⁰

) = Ø

(14)

Ciclo di espansione dei nodi Per ogni nodo N :

• finch´e il campo New(N) non `e vuoto, si sceglie una formula A di New(N), si cancella da N ew(N ) e:

– Se A `e un letterale allora, se il campo Literals(N ) contiene il lettarale complemen- tare, allora il nodo N viene cancellato, altrimenti A si inserisce in Literals(N ).

– Se A non `e un letterale, si inserisce A in Old(N ), e:

∗ Se A si espande con una regola che non ramifica, le sue espansioni vengono aggiunte a N ew(N ).

∗ Se A si espande con una regola che ramifica, si crea una copia N

^′

del nodo N (copiandone tutti i campi, anche Incoming(N)), al campo N ew(N ) si aggiunge un’espansione di A, al campo N ew(N

^′

) si aggiunge l’altra espansione di A.

∗ Se A `e un letterale il cui complementare appartiene a Old(N), il nodo viene cancellato.

∗ Se A =

A

^′

, allora A

^′

viene aggiunta al campo N ext(N ).

(15)

Ciclo di espansione dei nodi (II)

• Quando il campo New(N) `e vuoto:

– se il grafo gi`a contiene un nodo N

^′

con Literals(N ) = Literals(N

^′

), Old(N

^′

) = Old(N ) e N ext(N

^′

) = N ext(N ), si aggiungono gli elmenti del campo Incoming(N ) al campo Incoming(N

^′

) e N viene cancellato.

– Altrimenti si crea un nuovo nodo N

^′

con:

N ew(N

^′

) = N ext(N ) Incoming(N

^′

) = {name(N )}

Literals(N

^′

) = Old(N

^′

) = N ext(N

^′

) = Ø

(16)

L’automa generato dall’algoritmo di traduzione Alfabeto Σ: congiunzioni di letterali (atomi e atomi negati in P )

Stati S: insieme dei nodi del grafo ottenuto mediante la costruzione sopra descritta.

Relazione di transizione

∆ = {(N, N

^′

) | N ame(N ) ∈ Incoming(N

^′

)}

Stati iniziali

I = {N | init ∈ Incoming(N )}

Etichette: Per ogni nodo N , se Literals(N ) = {ℓ

¹

, ..., ℓ

_m

} per m > 0, allora L(N ) = ℓ

¹

∧ ... ∧ ℓ

_m

altrimenti, se Literals(N ) = Ø,

L(N ) = ⊤

Stati di accettazione: siano E

¹

, ..., E

_k

tutte le eventualities che sono sottoformule del- l’insieme iniziale, dove per ogni i = 1, ..., k: E

_i

= 3A

i

o E

_i

= B

_i

U A

_i

.

Allora

F = {f

¹

, ...., f

_k

} dove per ogni i = 1, ..., k:

f

_i

= {N | E

i

6∈ Old(N) oppure A

_i

∈ Old(N) ∪ Literals(N)}

(17)

Esecuzioni e interpretazioni temporali

Ogni esecuzione ρ = N

⁰

, N

¹

, N

²

, .... di un automa generato dall’algoritmo rappresenta un insieme di interpretazioni temporali:

le interpretazioni associate a ρ sono tutte le interpretazioni M tali che se p ∈ Literals(N

i

) allora p ∈ M(i),

se ¬p ∈ Literals(N

i

) allora p 6∈ M(i).

In particolare, un’interpretazione rappresentata da ρ `e l’interpretazione M, con:

M(i) = Literals(N

_i

) ∩ P (per ogni p ∈ P : p ∈ M(i) sse p ∈ Literals(N

i

)).

Osservazione

La costruzione automatica di A

G

avviene in genere seguendo l’algoritmo sopra descritto, senza passare per la costruzione intermedia del tableau:

• non memorizza tutti i nodi del tableau, per poi cancellare quelli che non interessano;

• il controllo di cicli viene effettuato soltanto quando termina l’espansione statica di un nodo

La costruzione manuale di A

G

pu`o per contro avvantaggiarsi del fatto che il loop checking

viene eseguito ogni volta che viene generato un nodo del tableau, consentendo a volte di

(18)

Il sistema SPIN

http://spinroot.com/spin/whatispin.html

Spin is a popular open-source software tool, used by thousands of people worldwide, that can be used for the formal verification of distributed software systems. The tool was developed at Bell Labs in the original Unix group of the Computing Sciences Research Center, starting in 1980. The software has been available freely since 1991, and continues to evolve to keep pace with new developments in the field. In April 2002 the tool was awarded the prestigious System Software Award for 2001 by the ACM.

Some applications

• verification of the control algorithms for the new flood control barrier built in the late nineties near Rotterdam in the Netherlands.

• Logic verification of the call processing software for a commercial data and phone switch, the PathStar switch that was designed and built at Lucent Technologies.

• Selected algorithms for a number of space missions were verified with the Spin model

checker.

(19)

Traduzione di LTL in GBA: costruzione di un tableau

Traduzione di LTL in GBA: costruzione di un tableau

1. Si costruisce un tableau T = (N, ∆

, {n

}, L

, Σ

, F

) per la formula G da tradurre (in cui sono eventualmente stati cancellati i nodi chiusi), e dove:

• N `e l’insieme dei nodi,

• n

∈ N `e la radice,

• ∆

`e la relazione padre-figlio,

• Σ

`e l’alfabeto:

Σ T = 2 subf (G)∪{ B|B∈subf (G)}

• L

: N → Σ `e la funzione di etichettatura dei nodi;

• F

= {f

, ..., f

}, dove E

, ..., E

sono tutte le eventualities in subf (G) e per ogni i = 1, ..., m, se E

= 3A

oppure E

= B

U A

:

f

= {n ∈ N | E

6∈ L

(n) oppure A

∈ L

(n)}

Traduzione di LTL in GBA: estrazione dell’automa dal tableau 2. Da T si estrae il grafo degli stati (foglie del tableau, oppure nodi a cui `e applicata la

regola NEXT), ciascuno dei quali `e etichettato dalla congiunzione dei letterali del nodo corrispondente.

A

= (S, ∆, I, L, 2

, F )

Stati: S = {n ∈ N | n `e espanso mediante la regola NEXT}

Stati iniziali:

I = {n ∈ S | esiste un cammino in T da n

a n in cui n `e l’unico elemento di S (nel cammino non `e mai applicata la regola NEXT)}

Relazione di transizione:

∆ = {(n

, n

) | n

, n

∈ S e esiste un cammino in T da n

a n

che non contiene altri elementi di S}

Etichette:

L(n) = ℓ

∧ ... ∧ ℓ

se n ∈ N e ℓ

, ..., ℓ

sono tutti i letterali che occorrono in L

(n) (se k = 0 allora L(n) = ⊤)

Stati di accettazione: F = {f

, ..., f

}, dove per ogni i = 1, ..., m f

= (f

∩ S)

Si ottiene un GBA etichettato da congiunzioni di letterali

Esempio 1

1 : 23p

2 : 3p ,

23p, (23p)

3 : p,

23p, ( 3p )

, (23p)

23p = 1

4 :

3p,

23p, ( 3p )

,

(23p)

5 : 3p, 23p

3p,

Σ _T = 2 ^subf (G)∪{ B|B∈subf (G)}