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
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
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
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).
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
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
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
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.
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 0to 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
Regular Languages
A run of NFA A on u = a
0, a
1, . . . , a
n−1is a finite sequence of states q
0, q
1, . . . , q
ns.t. q
0∈ I and q
i−→ q
ai i+1for 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.
Finite-State Automata: examples
The DFA A
1over Σ = {a, b}:
Recognizes words which do not end in b.
The NFA A
2over Σ = {a, b}:
Recognizes words which end in b.
Sebastiani and Tonetta Ch. 08: Automata-theoretic LTL Model Checking Monday 18thMay, 2020 14 / 97
Determinisation
Theorem (determinisation)
Given a NFA A we can construct a DFA A
0s.t. L(A) = L(A
0).
Size: |A
0| = 2
O(|A|).
Each state of A
0corresponds 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
Qis
{s}−→ {sa i | s−→ sa i}{s1, ...,sj, ...,sn}−→a Sn
j=1{si | sj −→ sa i}
Determinisation [cont.]
NFA A
2: Words which end in b.
A
2can be determinised into the automaton DA
2below.
(#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
Closure Properties
Theorem (Boolean closure)
Given NFA A
1, A
2over Σ 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|.
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
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
2R(s, s
0) :=
R
1(s, s
0) if s ∈ Q
1R
2(s, s
0) if s ∈ Q
2Theorem
L(A) = L(A
1) ∪ L(A
2)
|A| = |A
1| + |A
2|
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
0i iff p −→ p
a 0and 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
Example
A
1recognizes words with an even number of b’s.
A
2recognizes words with a number of a’s multiple of 3.
The Product Automaton A
1× A
2with F = {s
0, t
0}.
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
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 ⊆ Σ
ω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
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+1for 0 ≤ i.
The run ρ is accepting if Inf (ρ) ∩ F 6= ∅.
The language accepted by A
L(A) = {α ∈ Σ
ω| A has an accepting run on α}
Büchi Automaton: Example
Let Σ = {a, b}.
Let a Deterministic Büchi Automaton (DBA) A
1be
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
Büchi Automaton: Example (2)
Let a Nondeterministic Büchi Automaton (NBA) A
2be
With F = {s
2}, the automaton A
2recognizes words with finitely many
a. Thus, L(A
2) = L(A
1).
Deterministic vs. Nondeterministic Büchi Automata
Theorem
DBAs are strictly less powerful than NBAs.
The subset construction does not work:
let DA
2be
DA
2is not equivalent to A
2(e.g., it recognizes (b.a)
ω)
There is no DBA equivalent to A
2Sebastiani and Tonetta Ch. 08: Automata-theoretic LTL Model Checking Monday 18thMay, 2020 30 / 97
Closure Properties
Theorem (union, intersection)
For the NBAs A
1, A
2we 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.
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
2R(s, s
0) :=
R
1(s, s
0) if s ∈ Q
1R
2(s, s
0) if s ∈ Q
2Theorem
L(A) = L(A
1) ∪ L(A
2)
|A| = |A
1| + |A
2|
Note
A is an automaton which just runs nondeterministically either A
1or A
2(same construction as with ordinary automata)
Sebastiani and Tonetta Ch. 08: Automata-theoretic LTL Model Checking Monday 18thMay, 2020 32 / 97
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 0and q −→ q
a 0and p 6∈ F
1.
hp, q, 1i −→ hp
a 0, q
0, 2i iff p −→ p
a 0and q −→ q
a 0and p ∈ F
1.
hp, q, 2i −→ hp
a 0, q
0, 2i iff p −→ p
a 0and q −→ q
a 0and q 6∈ F
2.
hp, q, 2i −→ hp
a 0, q
0, 1i iff p −→ p
a 0and q −→ q
a 0and q ∈ F
2.
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
2Important 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
Product of NBAs: Example
Closure Properties (2)
Theorem (complementation) [Safra, MacNaughten]
For the NBA A
1we can construct an NBA A
2such 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
Generalized Büchi Automaton
Definition
A Generalized Büchi Automaton is a tuple A := (Q, Σ, δ, I, FT ) where FT = hF
1, F
2, . . . , F
ki with F
i⊆ Q.
A run ρ of A is accepting if Inf (ρ) ∩ F
i6= ∅ 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 }.
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}.
δ
0is s.t., for every i ∈ [1, ..., K ]:
hp, ii −→ hq, ii
aiff 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
Degeneralizing a Büchi automaton: Example
Omega-regular Expressions
Definition
A language is called ω-regular if it has the form ∪
ni=1U
i.(V
i)
ωwhere U
i, V
iare 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
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.
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
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).
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
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;
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
Double nested DFS: intuition
DFS1 invokes DFS2 on each f
1, ..., f
nonly after popping it (postorder):
suppose DFS2 is invoked on f
jbefore than on f
i=⇒ f
inot reachable from (any state s which is reachable from) f
jIf 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
jf
iS
f
jf
iS
f
jf
iS
f
jf
iS
???
f
jf
iS
f
jS
Sebastiani and Tonetta Ch. 08: Automata-theoretic LTL Model Checking Monday 18thMay, 2020 48 / 97
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
Automata-Theoretic LTL Model Checking
Let M be a Kripke model and ψ be an LTL formula
M |=Aψ(CTL∗)⇐⇒ M |= ψ (LTL)
⇐⇒ L(M) ⊆ L(ψ)
⇐⇒ L(M) ∩ L(ψ) = ∅
⇐⇒ L(M) ∩ L(¬ψ) = ∅
⇐⇒ L(AM) ∩ L(A¬ψ) = ∅
⇐⇒ L(AM× A¬ψ) = ∅
A
Mis 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 ψ)
Automata-Theoretic LTL M.C. (dual version)
Let M be a Kripke model and ϕ
def= ¬ψ be an LTL formula
M |=Eϕ⇐⇒ M 6|=A¬ϕ
⇐⇒ ...
⇐⇒ L(AM× Aϕ) 6= ∅
A
Mis 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
Mand A
ϕ.
Sebastiani and Tonetta Ch. 08: Automata-theoretic LTL Model Checking Monday 18thMay, 2020 53 / 97
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
ϕ)
Computing an NBA A
Mfrom 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
Computing a NBA A
Mfrom 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}
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
Computing a NBA A
Mfrom 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
0i 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
Computing a (Generalized) BA A
Mfrom 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
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).
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
Example
Xϕ Xϕ 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 ϕ
Example
Xϕ Xϕ Xϕ
−Xϕ 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
LTL Negative Normal Form (NNF)
Every LTL formula ϕ can be written into an equivalent formula ϕ
0using 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¬(ϕ
1Uϕ
2) =⇒ (¬ϕ
1R¬ϕ
2)
¬(φ
1Rφ
2) =⇒ (¬φ
1U¬φ
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
On-the-fly Construction of A
ϕ(Intuition)
Apply recursively the following steps:
Step 1: Apply the tableau expansion rules to ϕ ψ
1Uψ
2=⇒ ψ
2∨ (ψ
1∧ X(ψ
1Uψ
2))
ψ
1Rψ
2=⇒ ψ
2∧ (ψ
1∨ X(ψ
1Rψ
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
Tableaux rules: a quote
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
Xψ
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
On-the-fly Construction of A
ϕ(Intuition) [cont.]
Step 3: For every state S
irepresented by ( V
j
l
ij∧ X
ϕi
z }| {
^
k
ψ
ik) label the incoming edges of S
iwith V
j
l
ijmark that the state S
isatisfies ϕ
apply recursively steps 1-2-3 to ϕ
i def= V
k
ψ
ik,
rewrite ϕi intoWi0(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
ito all states S
ii0which satisfy V
k
ψ
ik(if no next part occurs, X> is implicitly assumed, so that an edge
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
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 ψ
iUϕ
i, for every state q
j, mark q
jwith F
iiff (ψ
iUϕ
i) / ∈ q
jor ϕ
i∈ q
j(If there is no U-subformulas, then mark all states with F
1—i.e., FT
def= {Q}).
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 followsSebastiani and Tonetta Ch. 08: Automata-theoretic LTL Model Checking Monday 18thMay, 2020 74 / 97
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,
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 ψ
2on the first, ψ
1on the second, add ψ
1∨ ψ
2to σ)
if ψ
1Uψ
2∈ Φ and s = hλ, χ, σi,
Expand (Φ, s) =Expand (Φ ∪ {ψ1}\{ψ1Uψ2}, hλ, χ ∪ {ψ1Uψ2}, σ ∪ {ψ1Uψ2}i)
∪Expand (Φ ∪ {ψ2}\{ψ1Uψ2}, hλ, χ, σ ∪ {ψ1Uψ2}i)
(split s in two copies and process ψ
1on the first, ψ
2on the second, add ψ
1Uψ
2to σ)
if ψ
1Rψ
2∈ Φ and s = hλ, χ, σi,
Expand (Φ, s) =Expand (Φ ∪ {ψ2}\{ψ1Rψ2}, hλ, χ ∪ {ψ1Rψ2}, σ ∪ {ψ1Rψ2}i)
∪Expand (Φ ∪ {ψ1, ψ2}\{ψ1Rψ2}, hλ, χ, σ ∪ {ψ1Rψ2}i)
(split s in two copies and process ψ
1on the first, ψ
2on the second, add ψ
1Rψ
2to σ)
Sebastiani and Tonetta Ch. 08: Automata-theoretic LTL Model Checking Monday 18thMay, 2020 76 / 97
On-the-fly Construction of A
φ- Expand
Two relevant subcases: Fψ
def= >Uψ and Gψ
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ψ}, ...) = ∅
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 ({φ}) ⊆ Qifhλ, χ, σ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
ki where, for all (ψ
iUφ
i) occurring positively in φ, F
i= {hλ, χ, σi ∈ Q | (ψ
iUφ
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