Introduction to Formal Methods Chapter 04: CTL Model Checking
Roberto Sebastiani
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:48
Outline
1
CTL Model Checking: general ideas
2
CTL Model Checking: a simple example
3
Some theoretical issues
4
CTL Model Checking: algorithms
5
CTL Model Checking: some examples
6
A relevant subcase: invariants
7
Exercises
Roberto Sebastiani Ch. 04: CTL Model Checking Monday 18thMay, 2020 2 / 72
CTL Model Checking: general ideas
Outline
1
CTL Model Checking: general ideas
2
CTL Model Checking: a simple example
3
Some theoretical issues
4
CTL Model Checking: algorithms
5
CTL Model Checking: some examples
6
A relevant subcase: invariants
CTL Model Checking: general ideas
CTL Model Checking
CTL Model Checking is a formal verification technique where...
...the system is represented as a Finite State Machine M:
...the property is expressed a CTL formula ϕ:
AG(p → AFq)
...the model checking algorithm checks whether in all initial states of M all the executions of the model satisfy the formula (M |= ϕ).
Roberto Sebastiani Ch. 04: CTL Model Checking Monday 18thMay, 2020 4 / 72
CTL Model Checking: general ideas
CTL Model Checking
CTL Model Checking is a formal verification technique where...
...the system is represented as a Finite State Machine M:
p q
1
2
3 4
p
...the property is expressed a CTL formula ϕ:
AG(p → AFq)
CTL Model Checking: general ideas
CTL Model Checking
CTL Model Checking is a formal verification technique where...
...the system is represented as a Finite State Machine M:
p q
1
2
3 4
p
...the property is expressed a CTL formula ϕ:
AG(p → AFq)
...the model checking algorithm checks whether in all initial states of M all the executions of the model satisfy the formula (M |= ϕ).
Roberto Sebastiani Ch. 04: CTL Model Checking Monday 18thMay, 2020 4 / 72
CTL Model Checking: general ideas
CTL Model Checking
CTL Model Checking is a formal verification technique where...
...the system is represented as a Finite State Machine M:
p q
1
2
3 4
p
...the property is expressed a CTL formula ϕ:
AG(p → AFq)
CTL Model Checking: general ideas
CTL Model Checking: General Idea
Two macro-steps:
1 construct the set of states where the formula holds:
[ϕ] := {s ∈ S : M, s |= ϕ}
([ϕ] is called the denotation of ϕ)
2 then compare with the set of initial states:
I ⊆ [ϕ] ?
Roberto Sebastiani Ch. 04: CTL Model Checking Monday 18thMay, 2020 5 / 72
CTL Model Checking: general ideas
CTL Model Checking: General Idea
Two macro-steps:
1 construct the set of states where the formula holds:
[ϕ] := {s ∈ S : M, s |= ϕ}
([ϕ] is called the denotation of ϕ)
2 then compare with the set of initial states:
I ⊆ [ϕ] ?
CTL Model Checking: general ideas
CTL Model Checking: General Idea
Two macro-steps:
1 construct the set of states where the formula holds:
[ϕ] := {s ∈ S : M, s |= ϕ}
([ϕ] is called the denotation of ϕ)
2 then compare with the set of initial states:
I ⊆ [ϕ] ?
Roberto Sebastiani Ch. 04: CTL Model Checking Monday 18thMay, 2020 5 / 72
CTL Model Checking: general ideas
CTL Model Checking: General Idea [cont.]
In order to compute [ϕ]:
proceed “bottom-up” on the structure of the formula, computing [ϕ
i] for each subformula ϕ
iof AG(p → AFq):
[q], [AFq], [p],
[p → AFq],
[AG(p → AFq)]
CTL Model Checking: general ideas
CTL Model Checking: General Idea [cont.]
In order to compute [ϕ]:
proceed “bottom-up” on the structure of the formula, computing [ϕ
i] for each subformula ϕ
iof AG(p → AFq):
[q], [AFq], [p],
[p → AFq], [AG(p → AFq)]
Roberto Sebastiani Ch. 04: CTL Model Checking Monday 18thMay, 2020 6 / 72
CTL Model Checking: general ideas
CTL Model Checking: General Idea [cont.]
In order to compute [ϕ]:
proceed “bottom-up” on the structure of the formula, computing [ϕ
i] for each subformula ϕ
iof AG(p → AFq):
[q], [AFq], [p],
[p → AFq],
[AG(p → AFq)]
CTL Model Checking: general ideas
CTL Model Checking: General Idea [cont.]
In order to compute [ϕ]:
proceed “bottom-up” on the structure of the formula, computing [ϕ
i] for each subformula ϕ
iof AG(p → AFq):
[q], [AFq], [p],
[p → AFq], [AG(p → AFq)]
Roberto Sebastiani Ch. 04: CTL Model Checking Monday 18thMay, 2020 6 / 72
CTL Model Checking: general ideas
CTL Model Checking: General Idea [cont.]
In order to compute [ϕ]:
proceed “bottom-up” on the structure of the formula, computing [ϕ
i] for each subformula ϕ
iof AG(p → AFq):
[q], [AFq], [p],
[p → AFq],
[AG(p → AFq)]
CTL Model Checking: general ideas
CTL Model Checking: General Idea [cont.]
In order to compute [ϕ]:
proceed “bottom-up” on the structure of the formula, computing [ϕ
i] for each subformula ϕ
iof AG(p → AFq):
[q], [AFq], [p],
[p → AFq], [AG(p → AFq)]
Roberto Sebastiani Ch. 04: CTL Model Checking Monday 18thMay, 2020 6 / 72
CTL Model Checking: general ideas
CTL Model Checking: General Idea [cont.]
In order to compute [ϕ]:
proceed “bottom-up” on the structure of the formula, computing [ϕ
i] for each subformula ϕ
iof AG(p → AFq):
[q], [AFq], [p],
[p → AFq],
[AG(p → AFq)]
CTL Model Checking: general ideas
CTL Model Checking: General Idea [cont.]
In order to compute each [ϕ
i]:
assign Propositional atoms by labeling function handle Boolean operators by standard set operations
handle temporal operators AX, EX by computing pre-images handle temporal operators AG, EG, AF, EF, AU, EU, by (implicitly) applying tableaux rules, until a fixpoint is reached
Roberto Sebastiani Ch. 04: CTL Model Checking Monday 18thMay, 2020 7 / 72
CTL Model Checking: general ideas
CTL Model Checking: General Idea [cont.]
In order to compute each [ϕ
i]:
assign Propositional atoms by labeling function handle Boolean operators by standard set operations
handle temporal operators AX, EX by computing pre-images
handle temporal operators AG, EG, AF, EF, AU, EU, by (implicitly)
applying tableaux rules, until a fixpoint is reached
CTL Model Checking: general ideas
CTL Model Checking: General Idea [cont.]
In order to compute each [ϕ
i]:
assign Propositional atoms by labeling function handle Boolean operators by standard set operations
handle temporal operators AX, EX by computing pre-images handle temporal operators AG, EG, AF, EF, AU, EU, by (implicitly) applying tableaux rules, until a fixpoint is reached
Roberto Sebastiani Ch. 04: CTL Model Checking Monday 18thMay, 2020 7 / 72
CTL Model Checking: general ideas
CTL Model Checking: General Idea [cont.]
In order to compute each [ϕ
i]:
assign Propositional atoms by labeling function handle Boolean operators by standard set operations
handle temporal operators AX, EX by computing pre-images
handle temporal operators AG, EG, AF, EF, AU, EU, by (implicitly)
applying tableaux rules, until a fixpoint is reached
CTL Model Checking: general ideas
CTL Model Checking: General Idea [cont.]
In order to compute each [ϕ
i]:
assign Propositional atoms by labeling function handle Boolean operators by standard set operations
handle temporal operators AX, EX by computing pre-images handle temporal operators AG, EG, AF, EF, AU, EU, by (implicitly) applying tableaux rules, until a fixpoint is reached
Roberto Sebastiani Ch. 04: CTL Model Checking Monday 18thMay, 2020 7 / 72
CTL Model Checking: general ideas
Tableaux rules: a quote
CTL Model Checking: a simple example
Outline
1
CTL Model Checking: general ideas
2
CTL Model Checking: a simple example
3
Some theoretical issues
4
CTL Model Checking: algorithms
5
CTL Model Checking: some examples
6
A relevant subcase: invariants
7
Exercises
Roberto Sebastiani Ch. 04: CTL Model Checking Monday 18thMay, 2020 9 / 72
CTL Model Checking: a simple example
CTL Model Checking: Example: AG(p → AFq)
p q
12
3 4
p
p q
12
3 4
p
"q" "AF q"
Recall the AF tableau rule: AFq ↔ (q ∨ AXAFq) Iteration: [AFq]
(1)= [q]; [AFq]
(i+1)= [q] ∪ AX[AFq]
(i)[AFq]
(1)= [q] = {2}
CTL Model Checking: a simple example
CTL Model Checking: Example: AG(p → AFq)
p q
12
3 4
p
p q
12
3 4
p
"q" "AF q"
Recall the AF tableau rule: AFq ↔ (q ∨ AXAFq) Iteration: [AFq]
(1)= [q]; [AFq]
(i+1)= [q] ∪ AX[AFq]
(i)[AFq]
(1)= [q] = {2}
[AFq]
(2)= [q ∨ AXq] = {2} ∪ {1} = {1, 2}
[AFq]
(3)= [q ∨ AX(q ∨ AXq)] = {2} ∪ {1} = {1, 2}
=⇒ (fix point reached)
Roberto Sebastiani Ch. 04: CTL Model Checking Monday 18thMay, 2020 10 / 72
CTL Model Checking: a simple example
CTL Model Checking: Example: AG(p → AFq)
p q
12
3 4
p
p q
12
3 4
p
"q" "AF q"
Recall the AF tableau rule: AFq ↔ (q ∨ AXAFq) Iteration: [AFq]
(1)= [q]; [AFq]
(i+1)= [q] ∪ AX[AFq]
(i)[AFq]
(1)= [q] = {2}
CTL Model Checking: a simple example
CTL Model Checking: Example: AG(p → AFq)
p q
12
3 4
p
p q
12
3 4
p
"q" "AF q"
Recall the AF tableau rule: AFq ↔ (q ∨ AXAFq) Iteration: [AFq]
(1)= [q]; [AFq]
(i+1)= [q] ∪ AX[AFq]
(i)[AFq]
(1)= [q] = {2}
[AFq]
(2)= [q ∨ AXq] = {2} ∪ {1} = {1, 2}
[AFq]
(3)= [q ∨ AX(q ∨ AXq)] = {2} ∪ {1} = {1, 2}
=⇒ (fix point reached)
Roberto Sebastiani Ch. 04: CTL Model Checking Monday 18thMay, 2020 10 / 72
CTL Model Checking: a simple example
CTL Model Checking: Example: AG(p → AFq)
p q
12
3 4
p
p q
12
3 4
p
"q" "AF q"
Recall the AF tableau rule: AFq ↔ (q ∨ AXAFq) Iteration: [AFq]
(1)= [q]; [AFq]
(i+1)= [q] ∪ AX[AFq]
(i)[AFq]
(1)= [q] = {2}
CTL Model Checking: a simple example
CTL Model Checking: Example: AG(p → AFq)
p q
12
3 4
p
p q
12
3 4
p
"q" "AF q"
Recall the AF tableau rule: AFq ↔ (q ∨ AXAFq) Iteration: [AFq]
(1)= [q]; [AFq]
(i+1)= [q] ∪ AX[AFq]
(i)[AFq]
(1)= [q] = {2}
[AFq]
(2)= [q ∨ AXq] = {2} ∪ {1} = {1, 2}
[AFq]
(3)= [q ∨ AX(q ∨ AXq)] = {2} ∪ {1} = {1, 2}
=⇒ (fix point reached)
Roberto Sebastiani Ch. 04: CTL Model Checking Monday 18thMay, 2020 10 / 72
CTL Model Checking: a simple example
CTL Model Checking: Example: AG(p → AFq)
p q
12
3 4
p
p q
12
3 4
p
"q" "AF q"
Recall the AF tableau rule: AFq ↔ (q ∨ AXAFq) Iteration: [AFq]
(1)= [q]; [AFq]
(i+1)= [q] ∪ AX[AFq]
(i)[AFq]
(1)= [q] = {2}
CTL Model Checking: a simple example
CTL Model Checking: Example: AG(p → AFq) [cont.]
p q 1
2
3 4
p
p q 1
2
3 4
p
p q 1
2
3 4
p
"p"
"AF q"
"p −> AF q"
Roberto Sebastiani Ch. 04: CTL Model Checking Monday 18thMay, 2020 11 / 72
CTL Model Checking: a simple example
CTL Model Checking: Example: AG(p → AFq) [cont.]
p q
12
3 4
p
p q
12
3 4
p
"p −> AF q" "AG(p −> AF q)"
Recall the AG tableau rule: AGϕ ↔ (ϕ ∧ AXAGϕ) Iteration: [AGϕ
(1)] = [ϕ]; [AGϕ]
(i+1)= [ϕ] ∩ AX[AGϕ]
(i)1
[AGϕ]
(1)= [ϕ] = {1, 2, 4}
CTL Model Checking: a simple example
CTL Model Checking: Example: AG(p → AFq) [cont.]
p q
12
3 4
p
p q
12
3 4
p
"p −> AF q" "AG(p −> AF q)"
Recall the AG tableau rule: AGϕ ↔ (ϕ ∧ AXAGϕ) Iteration: [AGϕ
(1)] = [ϕ]; [AGϕ]
(i+1)= [ϕ] ∩ AX[AGϕ]
(i)1
[AGϕ]
(1)= [ϕ] = {1, 2, 4}
2
[AGϕ]
(2)= [ϕ] ∩ AX[AGϕ]
(1)= {1, 2, 4} ∩ {1, 3} = {1}
3
[AGϕ]
(3)= [ϕ] ∩ AX[AGϕ]
(2)= {1, 2, 4} ∩ {} = {}
=⇒ (fix point reached)
Roberto Sebastiani Ch. 04: CTL Model Checking Monday 18thMay, 2020 12 / 72
CTL Model Checking: a simple example
CTL Model Checking: Example: AG(p → AFq) [cont.]
p q
12
3 4
p
p q
12
3 4
p
"p −> AF q" "AG(p −> AF q)"
Recall the AG tableau rule: AGϕ ↔ (ϕ ∧ AXAGϕ) Iteration: [AGϕ
(1)] = [ϕ]; [AGϕ]
(i+1)= [ϕ] ∩ AX[AGϕ]
(i)1
[AGϕ]
(1)= [ϕ] = {1, 2, 4}
CTL Model Checking: a simple example
CTL Model Checking: Example: AG(p → AFq) [cont.]
p q
12
3 4
p
p q
12
3 4
p
"p −> AF q" "AG(p −> AF q)"
Recall the AG tableau rule: AGϕ ↔ (ϕ ∧ AXAGϕ) Iteration: [AGϕ
(1)] = [ϕ]; [AGϕ]
(i+1)= [ϕ] ∩ AX[AGϕ]
(i)1
[AGϕ]
(1)= [ϕ] = {1, 2, 4}
2
[AGϕ]
(2)= [ϕ] ∩ AX[AGϕ]
(1)= {1, 2, 4} ∩ {1, 3} = {1}
3
[AGϕ]
(3)= [ϕ] ∩ AX[AGϕ]
(2)= {1, 2, 4} ∩ {} = {}
=⇒ (fix point reached)
Roberto Sebastiani Ch. 04: CTL Model Checking Monday 18thMay, 2020 12 / 72
CTL Model Checking: a simple example
CTL Model Checking: Example: AG(p → AFq) [cont.]
p q
12
3 4
p
p q
12
3 4
p
"p −> AF q" "AG(p −> AF q)"
Recall the AG tableau rule: AGϕ ↔ (ϕ ∧ AXAGϕ) Iteration: [AGϕ
(1)] = [ϕ]; [AGϕ]
(i+1)= [ϕ] ∩ AX[AGϕ]
(i)1
[AGϕ]
(1)= [ϕ] = {1, 2, 4}
CTL Model Checking: a simple example
CTL Model Checking: Example: AG(p → AFq) [cont.]
p q
12
3 4
p
p q
12
3 4
p
"p −> AF q" "AG(p −> AF q)"
Recall the AG tableau rule: AGϕ ↔ (ϕ ∧ AXAGϕ) Iteration: [AGϕ
(1)] = [ϕ]; [AGϕ]
(i+1)= [ϕ] ∩ AX[AGϕ]
(i)1
[AGϕ]
(1)= [ϕ] = {1, 2, 4}
2
[AGϕ]
(2)= [ϕ] ∩ AX[AGϕ]
(1)= {1, 2, 4} ∩ {1, 3} = {1}
3
[AGϕ]
(3)= [ϕ] ∩ AX[AGϕ]
(2)= {1, 2, 4} ∩ {} = {}
=⇒ (fix point reached)
Roberto Sebastiani Ch. 04: CTL Model Checking Monday 18thMay, 2020 12 / 72
CTL Model Checking: a simple example
CTL Model Checking: Example: AG(p → AFq) [cont.]
p q
12
3 4
p
p q
12
3 4
p
"p −> AF q" "AG(p −> AF q)"
Recall the AG tableau rule: AGϕ ↔ (ϕ ∧ AXAGϕ) Iteration: [AGϕ
(1)] = [ϕ]; [AGϕ]
(i+1)= [ϕ] ∩ AX[AGϕ]
(i)1
[AGϕ]
(1)= [ϕ] = {1, 2, 4}
CTL Model Checking: a simple example
CTL Model Checking: Example: AG(p → AFq) [cont.]
The set of states where the formula holds is empty
=⇒ the initial state does not satisfy the property
=⇒ M 6|= AG(p → AFq)
Counterexample: a lazo-shaped path: 1, 2, {3, 4}
ω(satisfying EF(p ∧ EG¬q))
Note
Counter-example reconstruction in general is not trivial, based on intermediate sets.
Roberto Sebastiani Ch. 04: CTL Model Checking Monday 18thMay, 2020 13 / 72
CTL Model Checking: a simple example
CTL Model Checking: Example: AG(p → AFq) [cont.]
The set of states where the formula holds is empty
=⇒ the initial state does not satisfy the property
=⇒ M 6|= AG(p → AFq)
Counterexample: a lazo-shaped path: 1, 2, {3, 4}
ω(satisfying EF(p ∧ EG¬q))
Note
Counter-example reconstruction in general is not trivial, based on
intermediate sets.
CTL Model Checking: a simple example
CTL Model Checking: Example: AG(p → AFq) [cont.]
The set of states where the formula holds is empty
=⇒ the initial state does not satisfy the property
=⇒ M 6|= AG(p → AFq)
Counterexample: a lazo-shaped path: 1, 2, {3, 4}
ω(satisfying EF(p ∧ EG¬q))
Note
Counter-example reconstruction in general is not trivial, based on intermediate sets.
Roberto Sebastiani Ch. 04: CTL Model Checking Monday 18thMay, 2020 13 / 72
CTL Model Checking: a simple example
CTL Model Checking: Example: AG(p → AFq) [cont.]
The set of states where the formula holds is empty
=⇒ the initial state does not satisfy the property
=⇒ M 6|= AG(p → AFq)
Counterexample: a lazo-shaped path: 1, 2, {3, 4}
ω(satisfying EF(p ∧ EG¬q))
Note
Counter-example reconstruction in general is not trivial, based on
intermediate sets.
CTL Model Checking: a simple example
CTL Model Checking: Example: AG(p → AFq) [cont.]
The set of states where the formula holds is empty
=⇒ the initial state does not satisfy the property
=⇒ M 6|= AG(p → AFq)
Counterexample: a lazo-shaped path: 1, 2, {3, 4}
ω(satisfying EF(p ∧ EG¬q))
Note
Counter-example reconstruction in general is not trivial, based on intermediate sets.
Roberto Sebastiani Ch. 04: CTL Model Checking Monday 18thMay, 2020 13 / 72
Some theoretical issues
Outline
1
CTL Model Checking: general ideas
2
CTL Model Checking: a simple example
3
Some theoretical issues
4
CTL Model Checking: algorithms
5
CTL Model Checking: some examples
6
A relevant subcase: invariants
Some theoretical issues
The fixed-point theory of lattice of sets
Definition
For any finite set S, the structure (2
S, ⊆) forms a complete lattice with ∪ as join and ∩ as meet operations.
A function F : 2
S7−→ 2
Sis monotonic provided S
1⊆ S
2⇒ F (S
1) ⊆ F (S
2).
Roberto Sebastiani Ch. 04: CTL Model Checking Monday 18thMay, 2020 15 / 72
Some theoretical issues
The fixed-point theory of lattice of sets
Definition
For any finite set S, the structure (2
S, ⊆) forms a complete lattice with ∪ as join and ∩ as meet operations.
A function F : 2
S7−→ 2
Sis monotonic provided
S
1⊆ S
2⇒ F (S
1) ⊆ F (S
2).
Some theoretical issues
Fixed Points
Definition
Let h2
S, ⊆i be a complete lattice, S finite.
Given a function F : 2
S7−→ 2
S, a ⊆ S is a fixed point of F iff F (a) = a
a is a least fixed point (LFP) of F , written µx .F (x ), iff, for every other fixed point a
0of F , a ⊆ a
0a is a greatest fixed point (GFP) of F , written νx .F (x ), iff, for every other fixed point a
0of F , a
0⊆ a
Roberto Sebastiani Ch. 04: CTL Model Checking Monday 18thMay, 2020 16 / 72
Some theoretical issues
Fixed Points
Definition
Let h2
S, ⊆i be a complete lattice, S finite.
Given a function F : 2
S7−→ 2
S, a ⊆ S is a fixed point of F iff F (a) = a
a is a least fixed point (LFP) of F , written µx .F (x ), iff, for every other fixed point a
0of F , a ⊆ a
0a is a greatest fixed point (GFP) of F , written νx .F (x ), iff, for every
other fixed point a
0of F , a
0⊆ a
Some theoretical issues
Fixed Points
Definition
Let h2
S, ⊆i be a complete lattice, S finite.
Given a function F : 2
S7−→ 2
S, a ⊆ S is a fixed point of F iff F (a) = a
a is a least fixed point (LFP) of F , written µx .F (x ), iff, for every other fixed point a
0of F , a ⊆ a
0a is a greatest fixed point (GFP) of F , written νx .F (x ), iff, for every other fixed point a
0of F , a
0⊆ a
Roberto Sebastiani Ch. 04: CTL Model Checking Monday 18thMay, 2020 16 / 72
Some theoretical issues
Fixed Points
Definition
Let h2
S, ⊆i be a complete lattice, S finite.
Given a function F : 2
S7−→ 2
S, a ⊆ S is a fixed point of F iff F (a) = a
a is a least fixed point (LFP) of F , written µx .F (x ), iff, for every other fixed point a
0of F , a ⊆ a
0a is a greatest fixed point (GFP) of F , written νx .F (x ), iff, for every
other fixed point a
0of F , a
0⊆ a
Some theoretical issues
Iteratively computing fixed points
Tarski’s Theorem
A monotonic function over a complete finite lattice has a least and a greatest fixed point.
(A corollary of) Kleene’s Theorem
A monotonic function F over a complete finite lattice has a least and a greatest fixed point, which can be computed as follows:
the least fixed point of F is the limit of the chain
∅ ⊆ F (∅) ⊆ F (F (∅)) . . . ,
the greatest fixed point of F is the limit of chain S ⊇ F (S) ⊇ F (F (S)) . . .
Since 2
Sis finite, convergence is obtained in a finite number of steps.
Roberto Sebastiani Ch. 04: CTL Model Checking Monday 18thMay, 2020 17 / 72
Some theoretical issues
Iteratively computing fixed points
Tarski’s Theorem
A monotonic function over a complete finite lattice has a least and a greatest fixed point.
(A corollary of) Kleene’s Theorem
A monotonic function F over a complete finite lattice has a least and a greatest fixed point, which can be computed as follows:
the least fixed point of F is the limit of the chain
∅ ⊆ F (∅) ⊆ F (F (∅)) . . . ,
the greatest fixed point of F is the limit of chain
S ⊇ F (S) ⊇ F (F (S)) . . .
Some theoretical issues
Iteratively computing fixed points
Tarski’s Theorem
A monotonic function over a complete finite lattice has a least and a greatest fixed point.
(A corollary of) Kleene’s Theorem
A monotonic function F over a complete finite lattice has a least and a greatest fixed point, which can be computed as follows:
the least fixed point of F is the limit of the chain
∅ ⊆ F (∅) ⊆ F (F (∅)) . . . ,
the greatest fixed point of F is the limit of chain S ⊇ F (S) ⊇ F (F (S)) . . .
Since 2
Sis finite, convergence is obtained in a finite number of steps.
Roberto Sebastiani Ch. 04: CTL Model Checking Monday 18thMay, 2020 17 / 72
Some theoretical issues
Iteratively computing fixed points
Tarski’s Theorem
A monotonic function over a complete finite lattice has a least and a greatest fixed point.
(A corollary of) Kleene’s Theorem
A monotonic function F over a complete finite lattice has a least and a greatest fixed point, which can be computed as follows:
the least fixed point of F is the limit of the chain
∅ ⊆ F (∅) ⊆ F (F (∅)) . . . ,
the greatest fixed point of F is the limit of chain
S ⊇ F (S) ⊇ F (F (S)) . . .
Some theoretical issues
Iteratively computing fixed points
Tarski’s Theorem
A monotonic function over a complete finite lattice has a least and a greatest fixed point.
(A corollary of) Kleene’s Theorem
A monotonic function F over a complete finite lattice has a least and a greatest fixed point, which can be computed as follows:
the least fixed point of F is the limit of the chain
∅ ⊆ F (∅) ⊆ F (F (∅)) . . . ,
the greatest fixed point of F is the limit of chain S ⊇ F (S) ⊇ F (F (S)) . . .
Since 2
Sis finite, convergence is obtained in a finite number of steps.
Roberto Sebastiani Ch. 04: CTL Model Checking Monday 18thMay, 2020 17 / 72
Some theoretical issues
CTL Model Checking and Lattices
If M = hS, I, R, L, APi is a Kripke structure, then h2
S, ⊆i is a complete lattice
We identify ϕ with its denotation [ϕ]
=⇒ we can see logical operators as functions F : 2
S7−→ 2
Son the
complete lattice h2
S, ⊆i
Some theoretical issues
CTL Model Checking and Lattices
If M = hS, I, R, L, APi is a Kripke structure, then h2
S, ⊆i is a complete lattice
We identify ϕ with its denotation [ϕ]
=⇒ we can see logical operators as functions F : 2
S7−→ 2
Son the complete lattice h2
S, ⊆i
Roberto Sebastiani Ch. 04: CTL Model Checking Monday 18thMay, 2020 18 / 72
Some theoretical issues
CTL Model Checking and Lattices
If M = hS, I, R, L, APi is a Kripke structure, then h2
S, ⊆i is a complete lattice
We identify ϕ with its denotation [ϕ]
=⇒ we can see logical operators as functions F : 2
S7−→ 2
Son the
complete lattice h2
S, ⊆i
Some theoretical issues
Denotation of a CTL formula ϕ: [ϕ]
Definition of [ϕ]
[ϕ] := {s ∈ S : M, s |= ϕ}
Recursive definition of [ϕ]
[true] = S
[false] = {}
[p] = {s|p ∈ L(s)}
[¬ϕ
1] = S/[ϕ
1] [ϕ
1∧ ϕ
2] = [ϕ
1] ∩ [ϕ
2]
[EXϕ] = {s | ∃s
0∈ [ϕ] s.t. hs, s
0i ∈ R}
[EGβ] = νZ .( [β] ∩ [EXZ ] )
[E(β
1Uβ
2)] = µZ .( [β
2] ∪ ([β
1] ∩ [EXZ ]) )
Roberto Sebastiani Ch. 04: CTL Model Checking Monday 18thMay, 2020 19 / 72
Some theoretical issues
Denotation of a CTL formula ϕ: [ϕ]
Definition of [ϕ]
[ϕ] := {s ∈ S : M, s |= ϕ}
Recursive definition of [ϕ]
[true] = S
[false] = {}
[p] = {s|p ∈ L(s)}
[¬ϕ
1] = S/[ϕ
1] [ϕ
1∧ ϕ
2] = [ϕ
1] ∩ [ϕ
2]
[EXϕ] = {s | ∃s
0∈ [ϕ] s.t. hs, s
0i ∈ R}
[EGβ] = νZ .( [β] ∩ [EXZ ] )
Some theoretical issues
Case EX
P PreImage(P)
[EXϕ] = {s | ∃s
0∈ [ϕ] s.t. hs, s
0i ∈ R}
[EXϕ] is said to be the Pre-image of [ϕ] (Preimage([ϕ])) Key step of every CTL M.C. operation
Note
Preimage() is monotonic: X ⊆ X
0=⇒ Preimage(X ) ⊆ Preimage(X
0)
Roberto Sebastiani Ch. 04: CTL Model Checking Monday 18thMay, 2020 20 / 72
Some theoretical issues
Case EX
P PreImage(P)
[EXϕ] = {s | ∃s
0∈ [ϕ] s.t. hs, s
0i ∈ R}
[EXϕ] is said to be the Pre-image of [ϕ] (Preimage([ϕ]))
Key step of every CTL M.C. operation
Some theoretical issues
Case EX
P PreImage(P)
[EXϕ] = {s | ∃s
0∈ [ϕ] s.t. hs, s
0i ∈ R}
[EXϕ] is said to be the Pre-image of [ϕ] (Preimage([ϕ])) Key step of every CTL M.C. operation
Note
Preimage() is monotonic: X ⊆ X
0=⇒ Preimage(X ) ⊆ Preimage(X
0)
Roberto Sebastiani Ch. 04: CTL Model Checking Monday 18thMay, 2020 20 / 72
Some theoretical issues
Case EX
P PreImage(P)
[EXϕ] = {s | ∃s
0∈ [ϕ] s.t. hs, s
0i ∈ R}
[EXϕ] is said to be the Pre-image of [ϕ] (Preimage([ϕ]))
Key step of every CTL M.C. operation
Some theoretical issues
Case EG
νZ .( [β] ∩ [EXZ ] ): greatest fixed point of the function F
β: 2
S7−→ 2
S, s.t.
F
β([ϕ]) = ([β] ∩ Preimage([ϕ])
= ([β] ∩ {s | ∃s
0∈ [ϕ] s.t. hs, s
0i ∈ R}) F
βMonotonic: a ⊆ a
0=⇒ F
β(a) ⊆ F
β(a
0)
(Tarski’s theorem): νx .F
β(x ) always exists
(Kleene’s theorem): νx .F
β(x ) can be computed as the limit S ⊇ F
β(S) ⊇ F
β(F
β(S)) ⊇ . . ., in a finite number of steps.
Theorem (Clarke & Emerson) [EGβ] = νZ .( [β] ∩ [EXZ ] )
Roberto Sebastiani Ch. 04: CTL Model Checking Monday 18thMay, 2020 21 / 72
Some theoretical issues
Case EG
νZ .( [β] ∩ [EXZ ] ): greatest fixed point of the function F
β: 2
S7−→ 2
S, s.t.
F
β([ϕ]) = ([β] ∩ Preimage([ϕ])
= ([β] ∩ {s | ∃s
0∈ [ϕ] s.t. hs, s
0i ∈ R}) F
βMonotonic: a ⊆ a
0=⇒ F
β(a) ⊆ F
β(a
0)
(Tarski’s theorem): νx .F
β(x ) always exists
(Kleene’s theorem): νx .F
β(x ) can be computed as the limit S ⊇ F
β(S) ⊇ F
β(F
β(S)) ⊇ . . ., in a finite number of steps.
Theorem (Clarke & Emerson)
[EGβ] = νZ .( [β] ∩ [EXZ ] )
Some theoretical issues
Case EG
νZ .( [β] ∩ [EXZ ] ): greatest fixed point of the function F
β: 2
S7−→ 2
S, s.t.
F
β([ϕ]) = ([β] ∩ Preimage([ϕ])
= ([β] ∩ {s | ∃s
0∈ [ϕ] s.t. hs, s
0i ∈ R}) F
βMonotonic: a ⊆ a
0=⇒ F
β(a) ⊆ F
β(a
0)
(Tarski’s theorem): νx .F
β(x ) always exists
(Kleene’s theorem): νx .F
β(x ) can be computed as the limit S ⊇ F
β(S) ⊇ F
β(F
β(S)) ⊇ . . ., in a finite number of steps.
Theorem (Clarke & Emerson) [EGβ] = νZ .( [β] ∩ [EXZ ] )
Roberto Sebastiani Ch. 04: CTL Model Checking Monday 18thMay, 2020 21 / 72
Some theoretical issues
Case EG
νZ .( [β] ∩ [EXZ ] ): greatest fixed point of the function F
β: 2
S7−→ 2
S, s.t.
F
β([ϕ]) = ([β] ∩ Preimage([ϕ])
= ([β] ∩ {s | ∃s
0∈ [ϕ] s.t. hs, s
0i ∈ R}) F
βMonotonic: a ⊆ a
0=⇒ F
β(a) ⊆ F
β(a
0)
(Tarski’s theorem): νx .F
β(x ) always exists
(Kleene’s theorem): νx .F
β(x ) can be computed as the limit S ⊇ F
β(S) ⊇ F
β(F
β(S)) ⊇ . . ., in a finite number of steps.
Theorem (Clarke & Emerson)
[EGβ] = νZ .( [β] ∩ [EXZ ] )
Some theoretical issues
Case EG
νZ .( [β] ∩ [EXZ ] ): greatest fixed point of the function F
β: 2
S7−→ 2
S, s.t.
F
β([ϕ]) = ([β] ∩ Preimage([ϕ])
= ([β] ∩ {s | ∃s
0∈ [ϕ] s.t. hs, s
0i ∈ R}) F
βMonotonic: a ⊆ a
0=⇒ F
β(a) ⊆ F
β(a
0)
(Tarski’s theorem): νx .F
β(x ) always exists
(Kleene’s theorem): νx .F
β(x ) can be computed as the limit S ⊇ F
β(S) ⊇ F
β(F
β(S)) ⊇ . . ., in a finite number of steps.
Theorem (Clarke & Emerson) [EGβ] = νZ .( [β] ∩ [EXZ ] )
Roberto Sebastiani Ch. 04: CTL Model Checking Monday 18thMay, 2020 21 / 72
Some theoretical issues
Case EG [cont.]
We can compute X := [EGβ] inductively as follows:
X
0:= S
X
1:= F
β(S) = [β]
X
2:= F
β(F
β(S)) = [β] ∩ Preimage(X
1) . . .
X
j+1:= F
βj+1(S) = [β] ∩ Preimage(X
j) Noticing that X
1= [β] and X
j+1⊆ X
jfor every j ≥ 0, and that
([β] ∩ Y ) ⊆ X
j⊆ [β] =⇒ ([β] ∩ Y ) = (X
j∩ Y ), we can use instead the following inductive schema:
X
jY
[β]
Some theoretical issues
Case EG [cont.]
We can compute X := [EGβ] inductively as follows:
X
0:= S
X
1:= F
β(S) = [β]
X
2:= F
β(F
β(S)) = [β] ∩ Preimage(X
1) . . .
X
j+1:= F
βj+1(S) = [β] ∩ Preimage(X
j) Noticing that X
1= [β] and X
j+1⊆ X
jfor every j ≥ 0, and that
([β] ∩ Y ) ⊆ X
j⊆ [β] =⇒ ([β] ∩ Y ) = (X
j∩ Y ), we can use instead the following inductive schema:
X
1:= [β]
X
j+1:= X
j∩ Preimage(X
j)
X
jY
[β]
Roberto Sebastiani Ch. 04: CTL Model Checking Monday 18thMay, 2020 22 / 72
Some theoretical issues
Case EU
µZ .( [β
2] ∪ ([β
1] ∩ [EXZ ]) ): least fixed point of the function F
β1,β2: 2
S7−→ 2
S, s.t.
F
β1,β2([ϕ]) = [β
2] ∪ ([β
1] ∩ Preimage([ϕ]))
= [β
2] ∪ ([β
1] ∩ {s | ∃s
0∈ [ϕ] s.t. hs, s
0i ∈ R}) F
β1,β2Monotonic: a ⊆ a
0=⇒ F
β1,β2(a) ⊆ F
β1,β2(a
0)
(Tarski’s theorem): µx .F
β1,β2(x ) always exists
(Kleene’s theorem): µx .F
β1,β2(x ) can be computed as the limit
∅ ⊆ F
β1,β2(∅) ⊆ F
β1,β2(F
β1,β2(∅)) ⊆ . . ., in a finite number of steps.
Theorem (Clarke & Emerson)
[E(β
1Uβ
2)] = µZ .( [β
2] ∪ ([β
1] ∩ [EXZ ]) )
Some theoretical issues
Case EU
µZ .( [β
2] ∪ ([β
1] ∩ [EXZ ]) ): least fixed point of the function F
β1,β2: 2
S7−→ 2
S, s.t.
F
β1,β2([ϕ]) = [β
2] ∪ ([β
1] ∩ Preimage([ϕ]))
= [β
2] ∪ ([β
1] ∩ {s | ∃s
0∈ [ϕ] s.t. hs, s
0i ∈ R}) F
β1,β2Monotonic: a ⊆ a
0=⇒ F
β1,β2(a) ⊆ F
β1,β2(a
0)
(Tarski’s theorem): µx .F
β1,β2(x ) always exists
(Kleene’s theorem): µx .F
β1,β2(x ) can be computed as the limit
∅ ⊆ F
β1,β2(∅) ⊆ F
β1,β2(F
β1,β2(∅)) ⊆ . . ., in a finite number of steps.
Theorem (Clarke & Emerson)
[E(β
1Uβ
2)] = µZ .( [β
2] ∪ ([β
1] ∩ [EXZ ]) )
Roberto Sebastiani Ch. 04: CTL Model Checking Monday 18thMay, 2020 23 / 72
Some theoretical issues
Case EU
µZ .( [β
2] ∪ ([β
1] ∩ [EXZ ]) ): least fixed point of the function F
β1,β2: 2
S7−→ 2
S, s.t.
F
β1,β2([ϕ]) = [β
2] ∪ ([β
1] ∩ Preimage([ϕ]))
= [β
2] ∪ ([β
1] ∩ {s | ∃s
0∈ [ϕ] s.t. hs, s
0i ∈ R}) F
β1,β2Monotonic: a ⊆ a
0=⇒ F
β1,β2(a) ⊆ F
β1,β2(a
0)
(Tarski’s theorem): µx .F
β1,β2(x ) always exists
(Kleene’s theorem): µx .F
β1,β2(x ) can be computed as the limit
∅ ⊆ F
β1,β2(∅) ⊆ F
β1,β2(F
β1,β2(∅)) ⊆ . . ., in a finite number of steps.
Theorem (Clarke & Emerson)
[E(β
1Uβ
2)] = µZ .( [β
2] ∪ ([β
1] ∩ [EXZ ]) )
Some theoretical issues
Case EU
µZ .( [β
2] ∪ ([β
1] ∩ [EXZ ]) ): least fixed point of the function F
β1,β2: 2
S7−→ 2
S, s.t.
F
β1,β2([ϕ]) = [β
2] ∪ ([β
1] ∩ Preimage([ϕ]))
= [β
2] ∪ ([β
1] ∩ {s | ∃s
0∈ [ϕ] s.t. hs, s
0i ∈ R}) F
β1,β2Monotonic: a ⊆ a
0=⇒ F
β1,β2(a) ⊆ F
β1,β2(a
0)
(Tarski’s theorem): µx .F
β1,β2(x ) always exists
(Kleene’s theorem): µx .F
β1,β2(x ) can be computed as the limit
∅ ⊆ F
β1,β2(∅) ⊆ F
β1,β2(F
β1,β2(∅)) ⊆ . . ., in a finite number of steps.
Theorem (Clarke & Emerson)
[E(β
1Uβ
2)] = µZ .( [β
2] ∪ ([β
1] ∩ [EXZ ]) )
Roberto Sebastiani Ch. 04: CTL Model Checking Monday 18thMay, 2020 23 / 72
Some theoretical issues
Case EU
µZ .( [β
2] ∪ ([β
1] ∩ [EXZ ]) ): least fixed point of the function F
β1,β2: 2
S7−→ 2
S, s.t.
F
β1,β2([ϕ]) = [β
2] ∪ ([β
1] ∩ Preimage([ϕ]))
= [β
2] ∪ ([β
1] ∩ {s | ∃s
0∈ [ϕ] s.t. hs, s
0i ∈ R}) F
β1,β2Monotonic: a ⊆ a
0=⇒ F
β1,β2(a) ⊆ F
β1,β2(a
0)
(Tarski’s theorem): µx .F
β1,β2(x ) always exists
(Kleene’s theorem): µx .F
β1,β2(x ) can be computed as the limit
∅ ⊆ F
β1,β2(∅) ⊆ F
β1,β2(F
β1,β2(∅)) ⊆ . . ., in a finite number of steps.
Theorem (Clarke & Emerson)
[E(β
1Uβ
2)] = µZ .( [β
2] ∪ ([β
1] ∩ [EXZ ]) )
Some theoretical issues
Case EU [cont.]
We can compute X := [E(β
1Uβ
2)] inductively as follows:
X
0:= ∅
X
1:= F
β1,β2(∅) = [β
2]
X
2:= F
β1,β2(F
β1,β2(∅)) = [β
2] ∪ ([β
1] ∩ Preimage(X
1)) . . .
X
j+1:= F
βj+11,β2
(∅)) = [β
2] ∪ ([β
1] ∩ Preimage(X
j)) Noticing that X
1= [β
2] and X
j+1⊇ X
jfor every
j ≥ 0, and that
([β
2] ∪ Y ) ⊇ X
j⊇ [β
2] =⇒ ([β
2] ∪ Y ) = (X
j∪ Y ), we can use instead the following inductive schema:
X
1:= [β
2]
X
j+1:= X
j∪ ([β
1] ∩ Preimage(X
j))
Y X
j[β
2]
Roberto Sebastiani Ch. 04: CTL Model Checking Monday 18thMay, 2020 24 / 72
Some theoretical issues
Case EU [cont.]
We can compute X := [E(β
1Uβ
2)] inductively as follows:
X
0:= ∅
X
1:= F
β1,β2(∅) = [β
2]
X
2:= F
β1,β2(F
β1,β2(∅)) = [β
2] ∪ ([β
1] ∩ Preimage(X
1)) . . .
X
j+1:= F
βj+11,β2
(∅)) = [β
2] ∪ ([β
1] ∩ Preimage(X
j)) Noticing that X
1= [β
2] and X
j+1⊇ X
jfor every
j ≥ 0, and that
([β
2] ∪ Y ) ⊇ X
j⊇ [β
2] =⇒ ([β
2] ∪ Y ) = (X
j∪ Y ), we can use instead the following inductive schema:
Y X
j[β
2]
Some theoretical issues
A relevant subcase: EF
EFβ = E(>Uβ)
[>] = S =⇒ [>] ∩ Preimage(X
j) = Preimage(X
j) We can compute X := [EFβ] inductively as follows:
X
1:= [β]
X
j+1:= X
j∪ Preimage(X
j)
Roberto Sebastiani Ch. 04: CTL Model Checking Monday 18thMay, 2020 25 / 72
Some theoretical issues
A relevant subcase: EF
EFβ = E(>Uβ)
[>] = S =⇒ [>] ∩ Preimage(X
j) = Preimage(X
j) We can compute X := [EFβ] inductively as follows:
X
1:= [β]
X
j+1:= X
j∪ Preimage(X
j)
Some theoretical issues
A relevant subcase: EF
EFβ = E(>Uβ)
[>] = S =⇒ [>] ∩ Preimage(X
j) = Preimage(X
j) We can compute X := [EFβ] inductively as follows:
X
1:= [β]
X
j+1:= X
j∪ Preimage(X
j)
Roberto Sebastiani Ch. 04: CTL Model Checking Monday 18thMay, 2020 25 / 72
CTL Model Checking: algorithms
Outline
1
CTL Model Checking: general ideas
2
CTL Model Checking: a simple example
3
Some theoretical issues
4
CTL Model Checking: algorithms
5
CTL Model Checking: some examples
6
A relevant subcase: invariants
CTL Model Checking: algorithms
General Schema
Assume ϕ written in terms of ¬, ∧, EX, EU, EG A general M.C. algorithm (fix-point):
1. for every ϕ
i∈ Sub(ϕ), find [ϕ
i] 2. Check if I ⊆ [ϕ]
Subformulas Sub(ϕ) of ϕ are checked bottom-up To compute each [ϕ
i]: if the main operator of ϕ
iis a
Propositional atoms: apply labeling function Boolean operator: apply standard set operations
temporal operator: appy recursively the tableaux rules, until a fixpoint is reached
Roberto Sebastiani Ch. 04: CTL Model Checking Monday 18thMay, 2020 27 / 72
CTL Model Checking: algorithms
General Schema
Assume ϕ written in terms of ¬, ∧, EX, EU, EG A general M.C. algorithm (fix-point):
1. for every ϕ
i∈ Sub(ϕ), find [ϕ
i] 2. Check if I ⊆ [ϕ]
Subformulas Sub(ϕ) of ϕ are checked bottom-up To compute each [ϕ
i]: if the main operator of ϕ
iis a
Propositional atoms: apply labeling function Boolean operator: apply standard set operations
temporal operator: appy recursively the tableaux rules, until a
fixpoint is reached
CTL Model Checking: algorithms
General Schema
Assume ϕ written in terms of ¬, ∧, EX, EU, EG A general M.C. algorithm (fix-point):
1. for every ϕ
i∈ Sub(ϕ), find [ϕ
i] 2. Check if I ⊆ [ϕ]
Subformulas Sub(ϕ) of ϕ are checked bottom-up To compute each [ϕ
i]: if the main operator of ϕ
iis a
Propositional atoms: apply labeling function Boolean operator: apply standard set operations
temporal operator: appy recursively the tableaux rules, until a fixpoint is reached
Roberto Sebastiani Ch. 04: CTL Model Checking Monday 18thMay, 2020 27 / 72
CTL Model Checking: algorithms
General Schema
Assume ϕ written in terms of ¬, ∧, EX, EU, EG A general M.C. algorithm (fix-point):
1. for every ϕ
i∈ Sub(ϕ), find [ϕ
i] 2. Check if I ⊆ [ϕ]
Subformulas Sub(ϕ) of ϕ are checked bottom-up To compute each [ϕ
i]: if the main operator of ϕ
iis a
Propositional atoms: apply labeling function Boolean operator: apply standard set operations
temporal operator: appy recursively the tableaux rules, until a
fixpoint is reached
CTL Model Checking: algorithms
General Schema
Assume ϕ written in terms of ¬, ∧, EX, EU, EG A general M.C. algorithm (fix-point):
1. for every ϕ
i∈ Sub(ϕ), find [ϕ
i] 2. Check if I ⊆ [ϕ]
Subformulas Sub(ϕ) of ϕ are checked bottom-up To compute each [ϕ
i]: if the main operator of ϕ
iis a
Propositional atoms: apply labeling function Boolean operator: apply standard set operations
temporal operator: appy recursively the tableaux rules, until a fixpoint is reached
Roberto Sebastiani Ch. 04: CTL Model Checking Monday 18thMay, 2020 27 / 72
CTL Model Checking: algorithms
General Schema
Assume ϕ written in terms of ¬, ∧, EX, EU, EG A general M.C. algorithm (fix-point):
1. for every ϕ
i∈ Sub(ϕ), find [ϕ
i] 2. Check if I ⊆ [ϕ]
Subformulas Sub(ϕ) of ϕ are checked bottom-up To compute each [ϕ
i]: if the main operator of ϕ
iis a
Propositional atoms: apply labeling function Boolean operator: apply standard set operations
temporal operator: appy recursively the tableaux rules, until a
fixpoint is reached
CTL Model Checking: algorithms
General Schema
Assume ϕ written in terms of ¬, ∧, EX, EU, EG A general M.C. algorithm (fix-point):
1. for every ϕ
i∈ Sub(ϕ), find [ϕ
i] 2. Check if I ⊆ [ϕ]
Subformulas Sub(ϕ) of ϕ are checked bottom-up To compute each [ϕ
i]: if the main operator of ϕ
iis a
Propositional atoms: apply labeling function Boolean operator: apply standard set operations
temporal operator: appy recursively the tableaux rules, until a fixpoint is reached
Roberto Sebastiani Ch. 04: CTL Model Checking Monday 18thMay, 2020 27 / 72
CTL Model Checking: algorithms