• Non ci sono risultati.

Introduction to Formal Methods Chapter 08: Automata-theoretic LTL Model Checking

N/A
N/A
Protected

Academic year: 2021

Condividi "Introduction to Formal Methods Chapter 08: Automata-theoretic LTL Model Checking"

Copied!
84
0
0

Testo completo

(1)

Introduction to Formal Methods

Chapter 08: Automata-theoretic LTL Model Checking

Roberto Sebastiani and Stefano Tonetta

DISI, Università di Trento, Italy – roberto.sebastiani@unitn.it URL: http://disi.unitn.it/rseba/DIDATTICA/fm2020/

Teaching assistant:Enrico Magnago– enrico.magnago@unitn.it

CDLM in Informatica, academic year 2019-2020

last update: Monday 18thMay, 2020, 14:49

Copyright notice: some material (text, figures) displayed in these slides is courtesy of R. Alur, M. Benerecetti, A. Cimatti, M.

Di Natale, P. Pandya, M. Pistore, M. Roveri, and S.Tonetta, who detain its copyright. Some exampes displayed in these slides are taken from [Clarke, Grunberg & Peled, “Model Checking”, MIT Press], and their copyright is detained by the authors. All the other material is copyrighted by Roberto Sebastiani. Every commercial use of this material is strictly forbidden by the copyright laws without the authorization of the authors. No copy of these slides can be displayed in public

without containing this copyright notice.

Sebastiani and Tonetta Ch. 08: Automata-theoretic LTL Model Checking Monday 18thMay, 2020 1 / 97

(2)

Outline

1

Background: Finite-Word Automata Language Containment

Automata on Finite Words

2

Infinite-Word Automata Automata on Infinite Words Emptiness Checking

3

The Automata-Theoretic Approach to Model Checking Automata-Theoretic LTL Model Checking

From Kripke Structures to Büchi Automata

From LTL Formulas to Büchi Automata: generalities

On-the-fly construction of Bu¨chi Automata from LTL

(3)

System’s computations

The behaviors (computations) of a system can be seen as sequences of assignments to propositions.

MODULE main

VAR done: Boolean;

ASSIGN

init(done):=0;

next(done):= case

!done: {0,1};

done: done;

esac;

Since the state space is finite, the set of computations can be represented by a finite automaton.

or

!done done

done

Sebastiani and Tonetta Ch. 08: Automata-theoretic LTL Model Checking Monday 18thMay, 2020 5 / 97

(4)

Correct computations

Some computations are correct and others are not acceptable.

We can build an automaton for the set of all acceptable computations.

Example: eventually, done will be true forever (FGdone).

(5)

Language Containment Problem

Solution to the verification problem

=⇒ Check if language of the system automaton is contained in the language accepted by the property automaton.

The language containment problem is the problem of deciding if a language is a subset of another language.

L(A

1

) ⊆ L(A

2

) ⇐⇒ L(A

1

) ∩ L(A

2

) = {}

In order to solve the language containment problem, we need to know:

(i) how to complement an automaton, (ii) how to intersect two automata,

(iii) how to check the language emptiness of an automaton.

Sebastiani and Tonetta Ch. 08: Automata-theoretic LTL Model Checking Monday 18thMay, 2020 7 / 97

(6)

Finite Word Languages

An Alphabet Σ is a collection of symbols (letters).

E.g. Σ = {a, b}.

A finite word is a finite sequence of letters. (E.g. aabb.) The set of all finite words is denoted by Σ

.

A language U is a set of words, i.e. U ⊆ Σ

.

Example: Words over Σ = {a, b} with equal number of a’s and b’s.

(E.g. aabb or abba.)

Language recognition problem: determine whether a word belongs to a language.

Automata are computational devices able to solve language

(7)

Finite-State Automata

Basic model of computational systems with finite memory.

Widely applicable

Embedded System Controllers.

Languages: Ester-el, Lustre, Verilog.

Synchronous Circuits.

Regular Expression Pattern Matching Grep, Lex, Emacs.

Protocols

Network Protocols

Architecture: Bus, Cache Coherence, Telephony,...

Sebastiani and Tonetta Ch. 08: Automata-theoretic LTL Model Checking Monday 18thMay, 2020 10 / 97

(8)

Notation

a, b ∈ Σ finite alphabet.

u, v , w ∈ Σ

finite words.

 empty word.

u.v concatenation.

u

i

= u.u. .u repeated i-times.

U, V ⊆ Σ

Finite word languages.

(9)

Finite-State Automata Definition

Definition

A Nondeterministic Finite-State Automaton (NFA) is (Q, Σ, δ, I, F ) s.t.

Q Finite set of states.

Σ is a finite alphabet I ⊆ Q set of initial states.

F ⊆ Q set of final states.

δ ⊆ Q × Σ × Q transition relation (edges).

We use q −→ q

a 0

to denote (q, a, q

0

) ∈ δ.

Definition

A Deterministic Finite-State Automaton (DFA) is a NFA s.t.:

δ : Q × Σ → Q is a total function Single initial state I = {q

0

}.

Sebastiani and Tonetta Ch. 08: Automata-theoretic LTL Model Checking Monday 18thMay, 2020 12 / 97

(10)

Regular Languages

A run of NFA A on u = a

0

, a

1

, . . . , a

n−1

is a finite sequence of states q

0

, q

1

, . . . , q

n

s.t. q

0

∈ I and q

i

−→ q

ai i+1

for 0 ≤ i < n.

An accepting run is one where q

n

∈ F . The language accepted by A is

L(A) = {u ∈ Σ

| A has an accepting run on u}

The languages accepted by a NFA are called regular languages.

(11)

Finite-State Automata: examples

The DFA A

1

over Σ = {a, b}:

Recognizes words which do not end in b.

The NFA A

2

over Σ = {a, b}:

Recognizes words which end in b.

Sebastiani and Tonetta Ch. 08: Automata-theoretic LTL Model Checking Monday 18thMay, 2020 14 / 97

(12)

Determinisation

Theorem (determinisation)

Given a NFA A we can construct a DFA A

0

s.t. L(A) = L(A

0

).

Size: |A

0

| = 2

O(|A|)

.

Each state of A

0

corresponds to a set {s

1

, ..., s

j

} of states in A (Q

0

⊆ 2

Q

), with the intended meaning that :

A0is in the state {s1, ..,sj} if A is in one of the states s1, ..., sj

The (unique) initial state is I

0

=

def

{s

i

| s

i

∈ I}

The deterministic transition relation δ

0

: 2

Q

× Σ 7−→ 2

Q

is

{s}−→ {sa i | s−→ sa i}

{s1, ...,sj, ...,sn}−→a Sn

j=1{si | sj −→ sa i}

(13)

Determinisation [cont.]

NFA A

2

: Words which end in b.

A

2

can be determinised into the automaton DA

2

below.

(#States = 2

Q

.)

There are NFAs of size n for which the size of the minimum sized DFA must have size O(2

n

).

Sebastiani and Tonetta Ch. 08: Automata-theoretic LTL Model Checking Monday 18thMay, 2020 16 / 97

(14)

Closure Properties

Theorem (Boolean closure)

Given NFA A

1

, A

2

over Σ we can construct NFA A over Σ s.t.

L(A) = L(A

1

) (Complement). |A| = 2

O(|A1|)

. L(A) = L(A

1

) ∪ L(A

2

) (union). |A| = |A

1

| + |A

2

|.

L(A) = L(A

1

) ∩ L(A

2

) (intersection). |A| ≤ |A

1

| · |A

2

|.

(15)

Complementation of a NFA

A NFA A = (Q, Σ, δ, I, F ) is complemented by:

determinising it into a DFA A

0

= (Q

0

, Σ

0

, δ

0

, I

0

, F

0

) complementing it: A

0

= (Q

0

, Σ

0

, δ

0

, I

0

, F

0

)

|A

0

| = |A

0

| = 2

O(|A|)

Sebastiani and Tonetta Ch. 08: Automata-theoretic LTL Model Checking Monday 18thMay, 2020 18 / 97

(16)

Union of two NFAs

Definition: union of NFAs

Let A

1

= (Q

1

, Σ

1

, δ

1

, I

1

, F

1

), A

2

= (Q

2

, Σ

2

, δ

2

, I

2

, F

2

).

Then A = A

1

∪ A

2

= (Q, Σ, δ, I, F ) is defined as follows Q := Q

1

∪ Q

2

, I := I

1

∪ I

2

, F := F

1

∪ F

2

R(s, s

0

) :=

 R

1

(s, s

0

) if s ∈ Q

1

R

2

(s, s

0

) if s ∈ Q

2

Theorem

L(A) = L(A

1

) ∪ L(A

2

)

|A| = |A

1

| + |A

2

|

(17)

Synchronous Product Construction

Definition: product of NFAs

Let A

1

= (Q

1

, Σ, δ

1

, I

1

, F

1

) and A

2

= (Q

2

, Σ, δ

2

, I

2

, F

2

).

Then, A

1

× A

2

= (Q, Σ, δ, I, F ) where Q = Q

1

× Q

2

,

I = I

1

× I

2

, F = F

1

× F

2

,

hp, qi −→ hp

a 0

, q

0

i iff p −→ p

a 0

and q −→ q

a 0

.

Theorem

L(A

1

× A

2

) = L(A

1

) ∩ L(A

2

).

|(A

1

× A

2

)| ≤ |A

1

| · |A

2

|.

Sebastiani and Tonetta Ch. 08: Automata-theoretic LTL Model Checking Monday 18thMay, 2020 20 / 97

(18)

Example

A

1

recognizes words with an even number of b’s.

A

2

recognizes words with a number of a’s multiple of 3.

The Product Automaton A

1

× A

2

with F = {s

0

, t

0

}.

(19)

Regular Expressions

Syntax: ∅ |  | a | reg

1

.reg

2

| reg

1

|reg

2

| reg

. Every regular expression reg denotes a language L(reg).

Example: a

.(b|bb).a

. The words with either 1 b or 2 consecutive b’s.

Theorem

For every regular expression reg we can construct a language equivalent NFA of size O(|reg|).

Theorem

For every DFA A we can construct a language equivalent regular expression reg(A).

Sebastiani and Tonetta Ch. 08: Automata-theoretic LTL Model Checking Monday 18thMay, 2020 22 / 97

(20)

Infinite Word Languages

Modeling infinite computations of reactive systems.

An ω-word α over Σ is an infinite sequence a

0

, a

1

, a

2

. . ..

Formally, α : N → Σ.

The set of all infinite words is denoted by Σ

ω

.

A ω-language L is collection of ω-words, i.e. L ⊆ Σ

ω

. Example All words over {a, b} with infinitely many a’s.

Notation:

omega words α, β, γ ∈ Σ

ω

.

omega-languages L, L ⊆ Σ

ω

(21)

Omega-Automata

We consider automaton running over infinite words.

Let α = aabbbb . . ..

There are several (infinite) possible runs.

Run ρ

1

= s

1

, s

1

, s

1

, s

1

, s

2

, s

2

. . . Run ρ

2

= s

1

, s

1

, s

1

, s

1

, s

1

, s

1

. . .

Acceptance Conditions: Büchi (Muller, Rabin, Street):

Acceptance is based on states occurring infinitely often Notation Let ρ ∈ Q

ω

. Then,

Inf (ρ) = {s ∈ Q | ∃

i ∈ N. ρ(i) = s}.

(The set of states occurring infinitely many times in ρ.)

Sebastiani and Tonetta Ch. 08: Automata-theoretic LTL Model Checking Monday 18thMay, 2020 26 / 97

(22)

Büchi Automata

Nondeterministic Büchi Automaton

A = (Q, Σ, δ, I, F ), where F ⊆ Q is the set of accepting states.

A run ρ of A on ω-word α = a

0

, a

1

, a

2

, ... is an infinite sequence ρ = q

o

, q

1

, q

2

, . . . s.t. q

0

∈ I and q

i

−→ q

ai i+1

for 0 ≤ i.

The run ρ is accepting if Inf (ρ) ∩ F 6= ∅.

The language accepted by A

L(A) = {α ∈ Σ

ω

| A has an accepting run on α}

(23)

Büchi Automaton: Example

Let Σ = {a, b}.

Let a Deterministic Büchi Automaton (DBA) A

1

be

With F = {s

1

} the automaton recognizes words with infinitely many a’s.

With F = {s

2

} the automaton recognizes words with infinitely many b’s.

Sebastiani and Tonetta Ch. 08: Automata-theoretic LTL Model Checking Monday 18thMay, 2020 28 / 97

(24)

Büchi Automaton: Example (2)

Let a Nondeterministic Büchi Automaton (NBA) A

2

be

With F = {s

2

}, the automaton A

2

recognizes words with finitely many

a. Thus, L(A

2

) = L(A

1

).

(25)

Deterministic vs. Nondeterministic Büchi Automata

Theorem

DBAs are strictly less powerful than NBAs.

The subset construction does not work:

let DA

2

be

DA

2

is not equivalent to A

2

(e.g., it recognizes (b.a)

ω

)

There is no DBA equivalent to A

2

Sebastiani and Tonetta Ch. 08: Automata-theoretic LTL Model Checking Monday 18thMay, 2020 30 / 97

(26)

Closure Properties

Theorem (union, intersection)

For the NBAs A

1

, A

2

we can construct

the NBA A s.t. L(A) = L(A

1

) ∪ L(A

2

). |A| = |A

1

| + |A

2

|

the NBA A s.t. L(A) = L(A

1

) ∩ L(A

2

). |A| ≤ |A

1

| · |A

2

| · 2.

(27)

Union of two NBAs

Definition: union of NBAs

Let A

1

= (Q

1

, Σ

1

, δ

1

, I

1

, F

1

), A

2

= (Q

2

, Σ

2

, δ

2

, I

2

, F

2

).

Then A = A

1

∪ A

2

= (Q, Σ, δ, I, F ) is defined as follows Q := Q

1

∪ Q

2

, I := I

1

∪ I

2

, F := F

1

∪ F

2

R(s, s

0

) :=

 R

1

(s, s

0

) if s ∈ Q

1

R

2

(s, s

0

) if s ∈ Q

2

Theorem

L(A) = L(A

1

) ∪ L(A

2

)

|A| = |A

1

| + |A

2

|

Note

A is an automaton which just runs nondeterministically either A

1

or A

2

(same construction as with ordinary automata)

Sebastiani and Tonetta Ch. 08: Automata-theoretic LTL Model Checking Monday 18thMay, 2020 32 / 97

(28)

Synchronous Product of NBAs

Definition: synchronous product of NBAs

Let A

1

= (Q

1

, Σ, δ

1

, I

1

, F

1

) and A

2

= (Q

2

, Σ, δ

2

, I

2

, F

2

).

Then, A

1

× A

2

= (Q, Σ, δ, I, F ), where Q = Q

1

× Q

2

× {1, 2}.

I = I

1

× I

2

× {1}.

F = F

1

× Q

2

× {1}.

hp, q, 1i −→ hp

a 0

, q

0

, 1i iff p −→ p

a 0

and q −→ q

a 0

and p 6∈ F

1

.

hp, q, 1i −→ hp

a 0

, q

0

, 2i iff p −→ p

a 0

and q −→ q

a 0

and p ∈ F

1

.

hp, q, 2i −→ hp

a 0

, q

0

, 2i iff p −→ p

a 0

and q −→ q

a 0

and q 6∈ F

2

.

hp, q, 2i −→ hp

a 0

, q

0

, 1i iff p −→ p

a 0

and q −→ q

a 0

and q ∈ F

2

.

(29)

Product of NBAs: Intuition

The automaton remembers two tracks, one for each source NBA, and it points to one of the two tracks

As soon as it goes through an accepting state of the current track, it switches to the other track

=⇒ in order to visit infinitely often a state in F (i.e., F

1

), it must visit infinitely often some state also in F

2

Important subcase: If F

2

= Q

2

, then Q = Q

1

× Q

2

.

I = I

1

× I

2

. F = F

1

× Q

2

.

Sebastiani and Tonetta Ch. 08: Automata-theoretic LTL Model Checking Monday 18thMay, 2020 34 / 97

(30)

Product of NBAs: Example

(31)

Closure Properties (2)

Theorem (complementation) [Safra, MacNaughten]

For the NBA A

1

we can construct an NBA A

2

such that L(A

2

) = L(A

1

).

|A

2

| = O(2

|A1|·log(|A1|)

).

Method: (hint)

(i) convert a Büchi automaton into a Non-Deterministic Rabin automaton

(ii) determinize and Complement the Rabin automaton (iii) convert the Rabin automaton into a Büchi automaton.

Sebastiani and Tonetta Ch. 08: Automata-theoretic LTL Model Checking Monday 18thMay, 2020 36 / 97

(32)

Generalized Büchi Automaton

Definition

A Generalized Büchi Automaton is a tuple A := (Q, Σ, δ, I, FT ) where FT = hF

1

, F

2

, . . . , F

k

i with F

i

⊆ Q.

A run ρ of A is accepting if Inf (ρ) ∩ F

i

6= ∅ for each 1 ≤ i ≤ k .

Theorem

For every Generalized Büchi Automaton we can construct a language equivalent plain Büchi Automaton.

Intuition

Let Q

0

= Q × {1, . . . , K }.

(33)

De-generalization of a generalized NBA

Definition: De-generalization of a generalized NBA

Let A

def

= (Q, Σ, δ, I, FT ) a generalized BA s.f. FT

def

= {F

1

, ..., F

K

}.

Then a language-equivalent BA A

0def

= (Q

0

, Σ, δ

0

, I

0

, F

0

) is built as follows Q

0

= Q

1

× {1, ..., K }.

I

0

= I × {1}.

F

0

= F

1

× {1}.

δ

0

is s.t., for every i ∈ [1, ..., K ]:

hp, ii −→ hq, ii

a

iff p −→ q ∈ δ and p 6∈ F

a i

. hp, ii −→ hq, (i + 1)mod K i iff p

a

−→ q ∈ δ and p ∈ F

a i

.

Theorem

L(A

0

) = L(A).

|A

0

| ≤ K · |A|.

Sebastiani and Tonetta Ch. 08: Automata-theoretic LTL Model Checking Monday 18thMay, 2020 38 / 97

(34)

Degeneralizing a Büchi automaton: Example

(35)

Omega-regular Expressions

Definition

A language is called ω-regular if it has the form ∪

ni=1

U

i

.(V

i

)

ω

where U

i

, V

i

are regular languages.

Theorem

A language L is ω-regular iff it is NBA-recognizable.

Sebastiani and Tonetta Ch. 08: Automata-theoretic LTL Model Checking Monday 18thMay, 2020 40 / 97

(36)

NFA emptiness checking

Equivalent of finding a final state reachable from an initial state.

It can be solved with a DFS or a BFS.

A DFS finds a counterexample on the fly (it is stored in the stack of the procedure).

A BFS finds a final state reachable with a shortest

counterexample, but it requires a further backward search to reproduce the path.

Complexity: O(n).

Hereafter, assume w.l.o.g. that there is only one initial state.

(37)

NFA Emptiness Checking (cont.)

// returns True if empty language, false otherwise Bool DFS(NFA A) {

stack S=I;

Hashtable T=I;

while S!=∅ { v=top(S);

if v∈F return False

if ∃w s.t. w∈ δ(v) && T(w)==0 { hash(w,T);

push(w,S);

} else pop(S);

}

return True;

}

Sebastiani and Tonetta Ch. 08: Automata-theoretic LTL Model Checking Monday 18thMay, 2020 43 / 97

(38)

NBA emptiness checking

Equivalent of finding an accepting cycle reachable from an initial state.

A naive algorithm:

(i) a DFS finds the final states f reachable from an initial state;

(ii) for each f , a second DFS finds if it can reach f (i.e., if there exists a loop)

Complexity: O(n2).

SCC-based algorithm:

(i) Tarjan’s algorithm uses a DFS to find the SCCs in linear time;

(ii) another DFS finds if the union of non-trivial SCCs is reachable from an initial state.

Complexity: O(n).

(39)

Double Nested DFS algorithm

Double Nested DFS [Courcoubetis, Vardi, Wolper, Yannakakis, CAV’90]

two Hash tables:

T1: reachable states

T2: states reachable from a reachable final state two stacks:

S1: current branch of states reachable

S2: current branch of states reachable from final state f two nested DFS’s:

DFS1looks for a path from an initial state to a cycle starting from an accepting state

DFS2looks for a cycle starting from an accepting state It stops as soon as it finds a counterexample.

The counterexample is given by the stack of DFS2 (an accepting cycle) preceded by the stack of DFS1 (a path from an initial state to the cycle).

Sebastiani and Tonetta Ch. 08: Automata-theoretic LTL Model Checking Monday 18thMay, 2020 45 / 97

(40)

Double Nested DFS - First DFS

// returns True if empty language, false otherwise Bool DFS1(NBA A) {

stack S1=I; stack S2=∅;

Hashtable T1=I; Hashtable T2=∅;

while S1!=∅ { v=top(S1);

if ∃w s.t. w∈ δ(v) && T1(w)==0 { hash(w,T1);

push(w,S1);

} else { pop(S1);

if (v∈F && !DFS2(v,S2,T2,A))

return False;

(41)

Double Nested DFS - Second DFS

Bool DFS2(state f, stack & S, Hashtable & T, NBA A) { hash(f,T);

S = {f}

while S!=∅ { v=top(S);

if f∈ δ(v) return False;

if ∃w s.t. w∈ δ(v) && T(w)==0 { hash(w);

push(w);

} else pop(S);

}

return True;

}

Remark: T passed by reference, is not reset at each call of DFS2 !

Sebastiani and Tonetta Ch. 08: Automata-theoretic LTL Model Checking Monday 18thMay, 2020 47 / 97

(42)

Double nested DFS: intuition

DFS1 invokes DFS2 on each f

1

, ..., f

n

only after popping it (postorder):

suppose DFS2 is invoked on f

j

before than on f

i

=⇒ f

i

not reachable from (any state s which is reachable from) f

j

If during DFS2(f

i

, ...) it is encountered a state S which has already been explored by DFS2(f

j

, ...) for some f

j

,

can we reach fi from S?

No, because fi is not reachable from fj!

=⇒ it is safe to backtrack.

f

j

f

i

S

f

j

f

i

S

f

j

f

i

S

f

j

f

i

S

???

f

j

f

i

S

f

j

S

Sebastiani and Tonetta Ch. 08: Automata-theoretic LTL Model Checking Monday 18thMay, 2020 48 / 97

(43)

Double Nested DFS: example

T1

S2 S1

3

4 2

1 6

5 T2

1

0 1

1 T1

S2 S1

3

4 2

1 6

5 T2

2

0 1

2 1

0 1

1 T1

S2 S1

3

4 2

1 6

5 T2

3

00 11

3 2

0 1

2 1

0 1

1 T1

S2 S1

3

4 2

1 6

5 T2

4

0 1

4 3

00 11

3 2

0 1

2 1

0 1

1 T1

S2 S1

3

4 2

1 6

5 T2

0 1

4 3

00 11

3 2

0 1

2 1

0 1

1 T1

S2 S1

3

4 2

1 6

5 T2

0 1

4

00 11

3 2

0 1

2 1

0 1

1 T1

S2 S1

3

4 2

1 6

5 T2

3

0 1

3

0 1

4

00 11

3 2

0 1

2 1

0 1

1 T1

S2 S1

3

4 2

1 6

5 T2

4

0 1

4 3

0 1

3

0 1

4

00 11

3 2

0 1

2 1

0 1

1 T1

S2 S1

3

4 2

1 6

5 T2

0 1

4 3

0 1

3

0 1

4

00 11

3 2

0 1

2 1

0 1

1 T1

S2 S1

3

4 2

1 6

5 T2

0 1

4

0 1

3

0 1

4

00 11

3 2

0 1

2 1

0 1

1 T1

S2 S1

3

4 2

1 6

5 T2

0 1

4

0 1

3

0 1

4

00 11

3

0 1

2 1

0 1

1 T1

S2 S1

3

4 2

1 6

5 T2

5

00 11

5

0 1

4

0 1

3

0 1

4

00 11

3

0 1

2 1

0 1

1 T1

S2 S1

3

4 2

1 6

5 T2

6

00 11

6 5

00 11

5

0 1

4

0 1

3

0 1

4

00 11

3

0 1

2 1

0 1

1 T1

S2 S1

3

4 2

1 6

5 T2

00 11

6 5

00 11

5

0 1

4

0 1

3

0 1

4

00 11

3

0 1

2 1

0 1

1 T1

S2 S1

3

4 2

1 6

5 T2

00 11

6

00 11

5

0 1

4

0 1

3

0 1

4

00 11

3

0 1

2 1

0 1

1 T1

S2 S1

3

4 2

1 6

5 T2

5

0 1

5

00 11

6

00 11

5

0 1

4

0 1

3

0 1

4

00 11

3

0 1

2 1

0 1

1 T1

S2 S1

3

4 2

1 6

5 T2

2

0 1

2 5

0 1

5

00 11

6

00 11

5

0 1

4

0 1

3

0 1

4

00 11

3

0 1

2 1

0 1

1 T1

S2 S1

3

4 2

1 6

5 T2

0 1

2 5

0 1

5

00 11

6

00 11

5

0 1

4

0 1

3

0 1

4

00 11

3

0 1

2 1

0 1

1 T1

S2 S1

3

4 2

1 6

5 T2

6

0 1

6

0 1

2 5

0 1

5

00 11

6

00 11

5

0 1

4

0 1

3

0 1

4

00 11

3

0 1

2 1

0 1

1 T1

S2 S1

3

4 2

1 6

5 T2

1

0 1

1 6

0 1

6

0 1

2 5

0 1

5

00 11

6

00 11

5

0 1

4

0 1

3

0 1

4

00 11

3

0 1

2 1

0 1

1 T1

S2 S1

3

4 2

1 6

5 T2

Sebastiani and Tonetta Ch. 08: Automata-theoretic LTL Model Checking Monday 18thMay, 2020 49 / 97

(44)

Automata-Theoretic LTL Model Checking

Let M be a Kripke model and ψ be an LTL formula

M |=(CTL)

⇐⇒ M |= ψ (LTL)

⇐⇒ L(M) ⊆ L(ψ)

⇐⇒ L(M) ∩ L(ψ) = ∅

⇐⇒ L(M) ∩ L(¬ψ) = ∅

⇐⇒ L(AM) ∩ L(A¬ψ) = ∅

⇐⇒ L(AM× A¬ψ) = ∅

A

M

is a Büchi Automaton equivalent to M (which represents all and only the executions of M)

A

¬ψ

is a Büchi Automaton which represents all and only the paths

that satisfy ¬ψ (do not satisfy ψ)

(45)

Automata-Theoretic LTL M.C. (dual version)

Let M be a Kripke model and ϕ

def

= ¬ψ be an LTL formula

M |=

⇐⇒ M 6|=A¬ϕ

⇐⇒ ...

⇐⇒ L(AM× Aϕ) 6= ∅

A

M

is a Büchi Automaton equivalent to M (which represents all and only the executions of M)

A

ϕ

is a Büchi Automaton which represents all and only the paths that satisfy ϕ

=⇒ A

M

× A

ϕ

represents all and only the paths appearing in both A

M

and A

ϕ

.

Sebastiani and Tonetta Ch. 08: Automata-theoretic LTL Model Checking Monday 18thMay, 2020 53 / 97

(46)

Automata-Theoretic LTL Model Checking

Four steps:

(i) Compute A

M

(ii) Compute A

ϕ

(iii) Compute the product A

M

× A

ϕ

(iv) Check the emptiness of L(A

M

× A

ϕ

)

(47)

Computing an NBA A

M

from a Kripke Structure M

Transform a Kripke structure M = hS, S

0

, R, L, APi into an NBA A

M

= hQ, Σ, δ, I, F i s.t.:

States:Q := S ∪ {init}, init being a new initial state Alphabet:Σ :=2AP

Initial State:I := {init}

Accepting States:F := Q = S ∪ {init}

Transitions:

δ : q−→ qa 0iff (q, q0) ∈R and L(q0) =a init−→ q iff q ∈ Sa 0and L(q) = a

L(A

M

) = L(M)

|A

M

| = |M| + 1

Sebastiani and Tonetta Ch. 08: Automata-theoretic LTL Model Checking Monday 18thMay, 2020 56 / 97

(48)

Computing a NBA A

M

from a Kripke Structure M:

Example

{p,q}

{p,q}

{p,q}

Kripke Structure Buechi Automaton

{p,q} {p}

{q}

{p,−q}

{p,−q}

{−p,q}

(49)

Labels on Kripke Structures and BA’s - Remark

Note that the labels of a Büchi Automaton are different from the labels of a Kripke Structure. Also graphically, they are interpreted differently:

p

in a Kripke Structure, it means that p is true and all other propositions are false;

in a Büchi Automaton, it means that p is true and all other propositions are irrelevant (“don’t care”), i.e. they can be either true or false.

Sebastiani and Tonetta Ch. 08: Automata-theoretic LTL Model Checking Monday 18thMay, 2020 58 / 97

(50)

Computing a NBA A

M

from a Fair Kripke Structure M

Transforming a fair K.S. M = hS, S

0

, R, L, AP, FT i,

FT = {F

1

, ..., F

n

}, into a generalized NBA A

M

= hQ, Σ, δ, I, FT

0

i s.t.:

States:Q := S ∪ {init}, init being a new initial state Alphabet:Σ :=2AP

Initial State:I := {init}

Accepting States:FT0 :=FT Transitions:

δ : q−→ qa 0iff (q, q0) ∈R and L(q0) =a init−→ q iff q ∈ Sa 0and L(q) = a

(51)

Computing a (Generalized) BA A

M

from a Fair Kripke Structure M: Example

{p,q}

{p,q}

{p,q}

{p,q} {p}

{q}

{p,−q}

{p,−q}

{−p,q}

Generalized Buechi Automaton Fair Kripke Structure

=⇒ Substantially, add one initial state, move labels from states to incoming edges, set fair states as accepting states

Sebastiani and Tonetta Ch. 08: Automata-theoretic LTL Model Checking Monday 18thMay, 2020 60 / 97

(52)

Translation problem

Problem

Given an LTL formula φ, find a Büchi Automaton that accepts the same language of φ.

It is a fundamental problem in LTL model checking (in other words, every model checking algorithm that verifies the correctness of an LTL formula translates it in some sort of finite-state machine).

We will translate an LTL formula into a Generalized Büchi

Automata (GBA).

(53)

Exponential Translation

From ϕ, create a fair Kripke model, like in chapter 7.

Convert it into a (Generalized) Büchi Automaton Remark

Inefficient: up to 2

EL(ϕ)

states.

Kripke models require total truth assignments to state variables

Sebastiani and Tonetta Ch. 08: Automata-theoretic LTL Model Checking Monday 18thMay, 2020 63 / 97

(54)

Example

Xϕ Xϕ

−Xϕ −Xϕ

3

4 5 6

7 8

2

1 p q

ϕ −p p −q

−p q −p−q p q

p −q −p −q

ϕ

ϕ −ϕ ϕ

q ϕ

(55)

Example

−Xϕ −Xϕ

−Xϕ −Xϕ

p q p q p q p q

−pq −pq

−pq−pq

−pq

−pq

−pq

−pq

−p−q

−p−q −p−q

−p−q p q p q p q

p q

p −q

p −q p −q

p −q

p −q p −q

p −q −p−q

−p−q

−p−q

−p−q p q

−pq

−pq

p −q

p q 3

4

5 6

7 8

2 1

ϕ

−q p

q

−p −q ϕ

ϕ −ϕ ϕ

−ϕ

−ϕ

ϕ

Sebastiani and Tonetta Ch. 08: Automata-theoretic LTL Model Checking Monday 18thMay, 2020 65 / 97

(56)

LTL Negative Normal Form (NNF)

Every LTL formula ϕ can be written into an equivalent formula ϕ

0

using only the operators ∧, ∨, X, U, R on propositional literals.

Done by pushing negations down to literal level:

¬(ϕ

1

∨ ϕ

2

) =⇒ (¬ϕ

1

∧ ¬ϕ

2

)

¬(ϕ

1

∧ ϕ

2

) =⇒ (¬ϕ

1

∨ ¬ϕ

2

)

¬Xϕ

1

=⇒ X¬ϕ

1

¬(ϕ

1

2

) =⇒ (¬ϕ

1

R¬ϕ

2

)

¬(φ

1

2

) =⇒ (¬φ

1

U¬φ

2

)

=⇒ the resulting formula is expressed in terms of ∨, ∧, X , U, R and literals (Negative Normal Form, NNF).

encoding linear if a DAG representation is used

(57)

On-the-fly Construction of A

ϕ

(Intuition)

Apply recursively the following steps:

Step 1: Apply the tableau expansion rules to ϕ ψ

1

2

=⇒ ψ

2

∨ (ψ

1

∧ X(ψ

1

2

))

ψ

1

2

=⇒ ψ

2

∧ (ψ

1

∨ X(ψ

1

2

))

until we get a Boolean combination of elementary subformulas of ϕ (An elementary formula is a proposition or a X-formula.)

Sebastiani and Tonetta Ch. 08: Automata-theoretic LTL Model Checking Monday 18thMay, 2020 68 / 97

(58)

Tableaux rules: a quote

(59)

On-the-fly Construction of A

ϕ

(Intuition) [cont.]

Step 2: Convert all formulas into Disjunctive Normal Form, and then push the conjunctions inside the next:

ϕ =⇒ _

i

( ^

j

l

ij

∧ ^

k

ik

) =⇒ _

i

( ^

j

l

ij

∧ X ^

k

ψ

ik

).

Each disjunct (

labels

z }| {

^

j

l

ij

next part

z }| {

X ^

k

ψ

ik

) represents a state:

the conjunction of literalsV

jlij representsa set of labels in Σ (e.g., if Vars(ϕ) = {p, q, r }, p ∧ ¬q represents the two labels {p, ¬q, r } and {p, ¬q, ¬r } )

XV

kψikrepresents thenext partof the state (obbligations for the successors)

N.B., if no next part occurs, X> is implicitly assumed

Sebastiani and Tonetta Ch. 08: Automata-theoretic LTL Model Checking Monday 18thMay, 2020 70 / 97

(60)

On-the-fly Construction of A

ϕ

(Intuition) [cont.]

Step 3: For every state S

i

represented by ( V

j

l

ij

∧ X

ϕi

z }| {

^

k

ψ

ik

) label the incoming edges of S

i

with V

j

l

ij

mark that the state S

i

satisfies ϕ

apply recursively steps 1-2-3 to ϕ

i def

= V

k

ψ

ik

,

rewrite ϕi intoW

i0(V

jli00j∧ XV

kψi00k) from each disjunct(V

jli00j ∧ XV

kψi00k)generate a new state Sii0 (if not already present) and label it as satisfying ϕi def=V

kψik

draw an edge from S

i

to all states S

ii0

which satisfy V

k

ψ

ik

(if no next part occurs, X> is implicitly assumed, so that an edge

(61)

On-the-fly Construction of A

ϕ

(Intuition) [cont.]

ϕ??

W

i(V

jlij∧ XV

kψik)!

(V

jl1j∧ XV

kψ1k)

(V

jl2j∧ XV

kψ2k)

(V

jlij∧ XV

kψik)

...

W

i(V

jlij∧ XV

kψik)!

V

jl1j

[V

kψ1k]

[V

kψ2k] V

jl2j

[V

kψik] V

jlij

(V

jl1j∧ XV

kψ1k)

(V

jl2j∧ XV

kψ2k)

(V

jlij∧ XV

kψik)

...

W

i(V

jlij∧ XV

kψik)!

...

V

kψik ?

...

W

i(V

jlij∧ XV

kψik)!

V

jl100j

V

jl200j

V

jli00j [V

kψ0ik] [V

kψ02k] [V

kψ01k] W

i0 (V

jli00j∧ XV

kψ0i0k)

....

V

jl1j

V

jl2j

V

jlij

...

W

i(V

jlij∧ XV

kψik)!

V

jl100j

V

jl200j

V

jli00j [V

kψ0ik] [V

kψ02k] [V

kψ01k]

....

Sebastiani and Tonetta Ch. 08: Automata-theoretic LTL Model Checking Monday 18thMay, 2020 72 / 97

(62)

On-the-fly Construction of A

ϕ

(Intuition) [cont.]

When the recursive applications of steps 1-3 has terminated and the automata graph has been built, then apply the following:

Step 4: For every ψ

i

i

, for every state q

j

, mark q

j

with F

i

iff (ψ

i

i

) / ∈ q

j

or ϕ

i

∈ q

j

(If there is no U-subformulas, then mark all states with F

1

—i.e., FT

def

= {Q}).

(63)

On-the-fly Construction of A

φ

- State

Henceforth, a state is represented by a tuple s := hλ, χ, σi where:

λis the set of labels

χis the next part, i.e. the set of X -formulas satisfied by s

σis the set of the subformulas of φ satisfied by s (necessary for the fairness definition)

Given a set of LTL formulas Ψ

def

= {ψ

1

, ..., ψ

k

}, we define

Cover (Ψ)

def

= Expand (Ψ, h∅, ∅, ∅i) to be the set of initial states of the Buchi automaton representing V

j

ψ

j

.

Combines steps 1. and 2. of previous slides Expand() defined recursively as follows

Sebastiani and Tonetta Ch. 08: Automata-theoretic LTL Model Checking Monday 18thMay, 2020 74 / 97

(64)

On-the-fly Construction of A

φ

- Expand

Given a set of formulas Φ to expand and a state s, we define the set of states Expand (Φ, s) recursively as follows:

if Φ = ∅, Expand (Φ, s) = {s}

if ⊥ ∈ Φ, Expand (Φ, s) = ∅ if > ∈ Φ and s = hλ, χ, σi,

Expand (Φ, s) = Expand (Φ\{>}, hλ, χ, σ ∪ {>}i) if l ∈ Φ and s = hλ, χ, σi, l propositional literal Expand (Φ, s) = Expand (Φ\{l}, hλ ∪ {l}, χ, σ ∪ {l}i) (add l to the labels of s and to set of satisfied formulas) if Xψ ∈ Φ and s = hλ, χ, σi,

Expand (Φ, s) = Expand (Φ\{X ψ}, hλ, χ ∪ {ψ}, σ ∪ {Xψ}i)

(add ψ to the next part of s and Xψ to set of satisfied formulas)

if ψ

1

∧ ψ

2

∈ Φ and s = hλ, χ, σi,

(65)

On-the-fly Construction of A

φ

- Expand

if ψ

1

∨ ψ

2

∈ Φ and s = hλ, χ, σi,

Expand (Φ, s) =Expand (Φ ∪ {ψ

1

}\{ψ

1

∨ ψ

2

}, hλ, χ, σ ∪ {ψ

1

∨ ψ

2

}i)

∪Expand (Φ ∪ {ψ

2

}\{ψ

1

∨ ψ

2

}, hλ, χ, σ ∪ {ψ

1

∨ ψ

2

}i) (split s in two copies, process ψ

2

on the first, ψ

1

on the second, add ψ

1

∨ ψ

2

to σ)

if ψ

1

2

∈ Φ and s = hλ, χ, σi,

Expand (Φ, s) =Expand (Φ ∪ {ψ1}\{ψ12}, hλ, χ ∪ {ψ12}, σ ∪ {ψ12}i)

∪Expand (Φ ∪ {ψ2}\{ψ12}, hλ, χ, σ ∪ {ψ12}i)

(split s in two copies and process ψ

1

on the first, ψ

2

on the second, add ψ

1

2

to σ)

if ψ

1

2

∈ Φ and s = hλ, χ, σi,

Expand (Φ, s) =Expand (Φ ∪ {ψ2}\{ψ12}, hλ, χ ∪ {ψ12}, σ ∪ {ψ12}i)

∪Expand (Φ ∪ {ψ1, ψ2}\{ψ12}, hλ, χ, σ ∪ {ψ12}i)

(split s in two copies and process ψ

1

on the first, ψ

2

on the second, add ψ

1

2

to σ)

Sebastiani and Tonetta Ch. 08: Automata-theoretic LTL Model Checking Monday 18thMay, 2020 76 / 97

(66)

On-the-fly Construction of A

φ

- Expand

Two relevant subcases:

def

= >Uψ and

def

= ⊥Rψ if Fψ ∈ Φ and s = hλ, χ, σi,

Expand (Φ, s) =Expand (Φ\{Fψ}, hλ, χ ∪ {Fψ}, σ ∪ {Fψ}i)

∪Expand (Φ ∪ {ψ}\{Fψ}, hλ, χ, σ ∪ {Fψ}i)

if Gψ ∈ Φ and s = hλ, χ, σi,

Expand (Φ, s) =Expand (Φ ∪ {ψ}\{Gψ}, hλ, χ ∪ {Gψ}, σ ∪ {Gψ}i) Note: Expand (Φ ∪ {⊥, ψ}\{Gψ}, ...) = ∅

(67)

Definition of A

φ

Given a set of LTL formulas Ψ, we define Cover (Ψ)

def

= Expand (Ψ, h∅, ∅, ∅i).

For an LTL formula φ, we construct a Generalized NBA A

φ

= (Q, Q

0

, Σ, L, T , FT ) as follows:

Σ = 2

vars(φ)

Q is the smallest set such that

Cover ({φ}) ⊆ Q

ifhλ, χ, σi ∈ Q, thenCover (χ) ∈ Q

Q

0

= Cover ({φ}).

L(hλ, χ, σi) = {a ∈ Σ|a |= λ}

(s, s

0

) ∈ T iff, s = hλ, χ, σi and s

0

∈ Cover (χ)

FT = hF

1

, F

2

, ..., F

k

i where, for all (ψ

i

i

) occurring positively in φ, F

i

= {hλ, χ, σi ∈ Q | (ψ

i

i

) / ∈ σ or φ

i

∈ σ}.

(If there is no U-subformulas, then FT

def

= {Q}).

Sebastiani and Tonetta Ch. 08: Automata-theoretic LTL Model Checking Monday 18thMay, 2020 78 / 97

Riferimenti

Documenti correlati

Example: although state 3 belongs to sat(¬heat Uclose), the path which loops forever in 3 does not satisfy ¬heatUclose, as close never holds in that path. We restrict the

[Alternatively: there is no positive U-subformula, so that we must add a AGAF&gt; fairness condition, which is equivalent to say that all states belong to the fairness

From LTL Formulas to Büchi Automata: generalities On-the-fly construction of Bu¨chi Automata from LTL Complexity..

limited sensitivity: one good setting, does not require expert users much higher capacity (more variables) than BDD based techniques Various techniques: Bounded Model

all but one literals in η are as “old” as possible Learning: in future branches, when all-but-one literals in η are assigned, the remaining literal is assigned to false

Deadend states: reachable states which do not allow to proceed along a refinement of the abstract counter-example. Bad states: un-reachable states which allow to proceed along

Some exampes displayed in these slides are taken from [Clarke, Grunberg &amp; Peled, “Model Checking”, MIT Press], and their copyright is detained by the authors?. All the

Given the following generalized Büchi automaton A def = hQ, Σ, δ, I, FT i, with two sets of accepting states FT def = {F 1, F 2} s.t.. Ex: