• Non ci sono risultati.

Introduction to Formal Methods Chapter 04: CTL Model Checking

N/A
N/A
Protected

Academic year: 2021

Condividi "Introduction to Formal Methods Chapter 04: CTL Model Checking"

Copied!
160
0
0

Testo completo

(1)

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

(2)

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

(3)

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

(4)

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

(5)

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)

(6)

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

(7)

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)

(8)

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

(9)

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 ⊆ [ϕ] ?

(10)

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

(11)

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 ϕ

i

of AG(p → AFq):

[q], [AFq], [p],

[p → AFq],

[AG(p → AFq)]

(12)

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 ϕ

i

of AG(p → AFq):

[q], [AFq], [p],

[p → AFq], [AG(p → AFq)]

Roberto Sebastiani Ch. 04: CTL Model Checking Monday 18thMay, 2020 6 / 72

(13)

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 ϕ

i

of AG(p → AFq):

[q], [AFq], [p],

[p → AFq],

[AG(p → AFq)]

(14)

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 ϕ

i

of AG(p → AFq):

[q], [AFq], [p],

[p → AFq], [AG(p → AFq)]

Roberto Sebastiani Ch. 04: CTL Model Checking Monday 18thMay, 2020 6 / 72

(15)

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 ϕ

i

of AG(p → AFq):

[q], [AFq], [p],

[p → AFq],

[AG(p → AFq)]

(16)

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 ϕ

i

of AG(p → AFq):

[q], [AFq], [p],

[p → AFq], [AG(p → AFq)]

Roberto Sebastiani Ch. 04: CTL Model Checking Monday 18thMay, 2020 6 / 72

(17)

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 ϕ

i

of AG(p → AFq):

[q], [AFq], [p],

[p → AFq],

[AG(p → AFq)]

(18)

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

(19)

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

(20)

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

(21)

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

(22)

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

(23)

CTL Model Checking: general ideas

Tableaux rules: a quote

(24)

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

(25)

CTL Model Checking: a simple example

CTL Model Checking: Example: AG(p → AFq)

p q

1

2

3 4

p

p q

1

2

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}

(26)

CTL Model Checking: a simple example

CTL Model Checking: Example: AG(p → AFq)

p q

1

2

3 4

p

p q

1

2

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

(27)

CTL Model Checking: a simple example

CTL Model Checking: Example: AG(p → AFq)

p q

1

2

3 4

p

p q

1

2

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}

(28)

CTL Model Checking: a simple example

CTL Model Checking: Example: AG(p → AFq)

p q

1

2

3 4

p

p q

1

2

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

(29)

CTL Model Checking: a simple example

CTL Model Checking: Example: AG(p → AFq)

p q

1

2

3 4

p

p q

1

2

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}

(30)

CTL Model Checking: a simple example

CTL Model Checking: Example: AG(p → AFq)

p q

1

2

3 4

p

p q

1

2

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

(31)

CTL Model Checking: a simple example

CTL Model Checking: Example: AG(p → AFq)

p q

1

2

3 4

p

p q

1

2

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}

(32)

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

(33)

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 −> 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}

(34)

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 −> 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

(35)

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 −> 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}

(36)

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 −> 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

(37)

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 −> 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}

(38)

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 −> 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

(39)

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 −> 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}

(40)

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

(41)

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.

(42)

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

(43)

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.

(44)

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

(45)

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

(46)

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

S

7−→ 2

S

is monotonic provided S

1

⊆ S

2

⇒ F (S

1

) ⊆ F (S

2

).

Roberto Sebastiani Ch. 04: CTL Model Checking Monday 18thMay, 2020 15 / 72

(47)

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

S

7−→ 2

S

is monotonic provided

S

1

⊆ S

2

⇒ F (S

1

) ⊆ F (S

2

).

(48)

Some theoretical issues

Fixed Points

Definition

Let h2

S

, ⊆i be a complete lattice, S finite.

Given a function F : 2

S

7−→ 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

0

of F , a ⊆ a

0

a is a greatest fixed point (GFP) of F , written νx .F (x ), iff, for every other fixed point a

0

of F , a

0

⊆ a

Roberto Sebastiani Ch. 04: CTL Model Checking Monday 18thMay, 2020 16 / 72

(49)

Some theoretical issues

Fixed Points

Definition

Let h2

S

, ⊆i be a complete lattice, S finite.

Given a function F : 2

S

7−→ 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

0

of F , a ⊆ a

0

a is a greatest fixed point (GFP) of F , written νx .F (x ), iff, for every

other fixed point a

0

of F , a

0

⊆ a

(50)

Some theoretical issues

Fixed Points

Definition

Let h2

S

, ⊆i be a complete lattice, S finite.

Given a function F : 2

S

7−→ 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

0

of F , a ⊆ a

0

a is a greatest fixed point (GFP) of F , written νx .F (x ), iff, for every other fixed point a

0

of F , a

0

⊆ a

Roberto Sebastiani Ch. 04: CTL Model Checking Monday 18thMay, 2020 16 / 72

(51)

Some theoretical issues

Fixed Points

Definition

Let h2

S

, ⊆i be a complete lattice, S finite.

Given a function F : 2

S

7−→ 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

0

of F , a ⊆ a

0

a is a greatest fixed point (GFP) of F , written νx .F (x ), iff, for every

other fixed point a

0

of F , a

0

⊆ a

(52)

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

S

is finite, convergence is obtained in a finite number of steps.

Roberto Sebastiani Ch. 04: CTL Model Checking Monday 18thMay, 2020 17 / 72

(53)

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)) . . .

(54)

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

S

is finite, convergence is obtained in a finite number of steps.

Roberto Sebastiani Ch. 04: CTL Model Checking Monday 18thMay, 2020 17 / 72

(55)

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)) . . .

(56)

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

S

is finite, convergence is obtained in a finite number of steps.

Roberto Sebastiani Ch. 04: CTL Model Checking Monday 18thMay, 2020 17 / 72

(57)

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

S

7−→ 2

S

on the

complete lattice h2

S

, ⊆i

(58)

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

S

7−→ 2

S

on the complete lattice h2

S

, ⊆i

Roberto Sebastiani Ch. 04: CTL Model Checking Monday 18thMay, 2020 18 / 72

(59)

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

S

7−→ 2

S

on the

complete lattice h2

S

, ⊆i

(60)

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

0

i ∈ R}

[EGβ] = νZ .( [β] ∩ [EXZ ] )

[E(β

1

2

)] = µZ .( [β

2

] ∪ ([β

1

] ∩ [EXZ ]) )

Roberto Sebastiani Ch. 04: CTL Model Checking Monday 18thMay, 2020 19 / 72

(61)

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

0

i ∈ R}

[EGβ] = νZ .( [β] ∩ [EXZ ] )

(62)

Some theoretical issues

Case EX

P PreImage(P)

[EXϕ] = {s | ∃s

0

∈ [ϕ] s.t. hs, s

0

i ∈ 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

(63)

Some theoretical issues

Case EX

P PreImage(P)

[EXϕ] = {s | ∃s

0

∈ [ϕ] s.t. hs, s

0

i ∈ R}

[EXϕ] is said to be the Pre-image of [ϕ] (Preimage([ϕ]))

Key step of every CTL M.C. operation

(64)

Some theoretical issues

Case EX

P PreImage(P)

[EXϕ] = {s | ∃s

0

∈ [ϕ] s.t. hs, s

0

i ∈ 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

(65)

Some theoretical issues

Case EX

P PreImage(P)

[EXϕ] = {s | ∃s

0

∈ [ϕ] s.t. hs, s

0

i ∈ R}

[EXϕ] is said to be the Pre-image of [ϕ] (Preimage([ϕ]))

Key step of every CTL M.C. operation

(66)

Some theoretical issues

Case EG

νZ .( [β] ∩ [EXZ ] ): greatest fixed point of the function F

β

: 2

S

7−→ 2

S

, s.t.

F

β

([ϕ]) = ([β] ∩ Preimage([ϕ])

= ([β] ∩ {s | ∃s

0

∈ [ϕ] s.t. hs, s

0

i ∈ 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

(67)

Some theoretical issues

Case EG

νZ .( [β] ∩ [EXZ ] ): greatest fixed point of the function F

β

: 2

S

7−→ 2

S

, s.t.

F

β

([ϕ]) = ([β] ∩ Preimage([ϕ])

= ([β] ∩ {s | ∃s

0

∈ [ϕ] s.t. hs, s

0

i ∈ 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 ] )

(68)

Some theoretical issues

Case EG

νZ .( [β] ∩ [EXZ ] ): greatest fixed point of the function F

β

: 2

S

7−→ 2

S

, s.t.

F

β

([ϕ]) = ([β] ∩ Preimage([ϕ])

= ([β] ∩ {s | ∃s

0

∈ [ϕ] s.t. hs, s

0

i ∈ 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

(69)

Some theoretical issues

Case EG

νZ .( [β] ∩ [EXZ ] ): greatest fixed point of the function F

β

: 2

S

7−→ 2

S

, s.t.

F

β

([ϕ]) = ([β] ∩ Preimage([ϕ])

= ([β] ∩ {s | ∃s

0

∈ [ϕ] s.t. hs, s

0

i ∈ 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 ] )

(70)

Some theoretical issues

Case EG

νZ .( [β] ∩ [EXZ ] ): greatest fixed point of the function F

β

: 2

S

7−→ 2

S

, s.t.

F

β

([ϕ]) = ([β] ∩ Preimage([ϕ])

= ([β] ∩ {s | ∃s

0

∈ [ϕ] s.t. hs, s

0

i ∈ 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

(71)

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

j

for every j ≥ 0, and that

([β] ∩ Y ) ⊆ X

j

⊆ [β] =⇒ ([β] ∩ Y ) = (X

j

∩ Y ), we can use instead the following inductive schema:

X

j

Y

[β]

(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

j

for 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

j

Y

[β]

Roberto Sebastiani Ch. 04: CTL Model Checking Monday 18thMay, 2020 22 / 72

(73)

Some theoretical issues

Case EU

µZ .( [β

2

] ∪ ([β

1

] ∩ [EXZ ]) ): least fixed point of the function F

β12

: 2

S

7−→ 2

S

, s.t.

F

β12

([ϕ]) = [β

2

] ∪ ([β

1

] ∩ Preimage([ϕ]))

= [β

2

] ∪ ([β

1

] ∩ {s | ∃s

0

∈ [ϕ] s.t. hs, s

0

i ∈ R}) F

β12

Monotonic: a ⊆ a

0

=⇒ F

β12

(a) ⊆ F

β12

(a

0

)

(Tarski’s theorem): µx .F

β12

(x ) always exists

(Kleene’s theorem): µx .F

β12

(x ) can be computed as the limit

∅ ⊆ F

β12

(∅) ⊆ F

β12

(F

β12

(∅)) ⊆ . . ., in a finite number of steps.

Theorem (Clarke & Emerson)

[E(β

1

2

)] = µZ .( [β

2

] ∪ ([β

1

] ∩ [EXZ ]) )

(74)

Some theoretical issues

Case EU

µZ .( [β

2

] ∪ ([β

1

] ∩ [EXZ ]) ): least fixed point of the function F

β12

: 2

S

7−→ 2

S

, s.t.

F

β12

([ϕ]) = [β

2

] ∪ ([β

1

] ∩ Preimage([ϕ]))

= [β

2

] ∪ ([β

1

] ∩ {s | ∃s

0

∈ [ϕ] s.t. hs, s

0

i ∈ R}) F

β12

Monotonic: a ⊆ a

0

=⇒ F

β12

(a) ⊆ F

β12

(a

0

)

(Tarski’s theorem): µx .F

β12

(x ) always exists

(Kleene’s theorem): µx .F

β12

(x ) can be computed as the limit

∅ ⊆ F

β12

(∅) ⊆ F

β12

(F

β12

(∅)) ⊆ . . ., in a finite number of steps.

Theorem (Clarke & Emerson)

[E(β

1

2

)] = µZ .( [β

2

] ∪ ([β

1

] ∩ [EXZ ]) )

Roberto Sebastiani Ch. 04: CTL Model Checking Monday 18thMay, 2020 23 / 72

(75)

Some theoretical issues

Case EU

µZ .( [β

2

] ∪ ([β

1

] ∩ [EXZ ]) ): least fixed point of the function F

β12

: 2

S

7−→ 2

S

, s.t.

F

β12

([ϕ]) = [β

2

] ∪ ([β

1

] ∩ Preimage([ϕ]))

= [β

2

] ∪ ([β

1

] ∩ {s | ∃s

0

∈ [ϕ] s.t. hs, s

0

i ∈ R}) F

β12

Monotonic: a ⊆ a

0

=⇒ F

β12

(a) ⊆ F

β12

(a

0

)

(Tarski’s theorem): µx .F

β12

(x ) always exists

(Kleene’s theorem): µx .F

β12

(x ) can be computed as the limit

∅ ⊆ F

β12

(∅) ⊆ F

β12

(F

β12

(∅)) ⊆ . . ., in a finite number of steps.

Theorem (Clarke & Emerson)

[E(β

1

2

)] = µZ .( [β

2

] ∪ ([β

1

] ∩ [EXZ ]) )

(76)

Some theoretical issues

Case EU

µZ .( [β

2

] ∪ ([β

1

] ∩ [EXZ ]) ): least fixed point of the function F

β12

: 2

S

7−→ 2

S

, s.t.

F

β12

([ϕ]) = [β

2

] ∪ ([β

1

] ∩ Preimage([ϕ]))

= [β

2

] ∪ ([β

1

] ∩ {s | ∃s

0

∈ [ϕ] s.t. hs, s

0

i ∈ R}) F

β12

Monotonic: a ⊆ a

0

=⇒ F

β12

(a) ⊆ F

β12

(a

0

)

(Tarski’s theorem): µx .F

β12

(x ) always exists

(Kleene’s theorem): µx .F

β12

(x ) can be computed as the limit

∅ ⊆ F

β12

(∅) ⊆ F

β12

(F

β12

(∅)) ⊆ . . ., in a finite number of steps.

Theorem (Clarke & Emerson)

[E(β

1

2

)] = µZ .( [β

2

] ∪ ([β

1

] ∩ [EXZ ]) )

Roberto Sebastiani Ch. 04: CTL Model Checking Monday 18thMay, 2020 23 / 72

(77)

Some theoretical issues

Case EU

µZ .( [β

2

] ∪ ([β

1

] ∩ [EXZ ]) ): least fixed point of the function F

β12

: 2

S

7−→ 2

S

, s.t.

F

β12

([ϕ]) = [β

2

] ∪ ([β

1

] ∩ Preimage([ϕ]))

= [β

2

] ∪ ([β

1

] ∩ {s | ∃s

0

∈ [ϕ] s.t. hs, s

0

i ∈ R}) F

β12

Monotonic: a ⊆ a

0

=⇒ F

β12

(a) ⊆ F

β12

(a

0

)

(Tarski’s theorem): µx .F

β12

(x ) always exists

(Kleene’s theorem): µx .F

β12

(x ) can be computed as the limit

∅ ⊆ F

β12

(∅) ⊆ F

β12

(F

β12

(∅)) ⊆ . . ., in a finite number of steps.

Theorem (Clarke & Emerson)

[E(β

1

2

)] = µZ .( [β

2

] ∪ ([β

1

] ∩ [EXZ ]) )

(78)

Some theoretical issues

Case EU [cont.]

We can compute X := [E(β

1

2

)] inductively as follows:

X

0

:= ∅

X

1

:= F

β12

(∅) = [β

2

]

X

2

:= F

β12

(F

β12

(∅)) = [β

2

] ∪ ([β

1

] ∩ Preimage(X

1

)) . . .

X

j+1

:= F

βj+1

12

(∅)) = [β

2

] ∪ ([β

1

] ∩ Preimage(X

j

)) Noticing that X

1

= [β

2

] and X

j+1

⊇ X

j

for 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

(79)

Some theoretical issues

Case EU [cont.]

We can compute X := [E(β

1

2

)] inductively as follows:

X

0

:= ∅

X

1

:= F

β12

(∅) = [β

2

]

X

2

:= F

β12

(F

β12

(∅)) = [β

2

] ∪ ([β

1

] ∩ Preimage(X

1

)) . . .

X

j+1

:= F

βj+1

12

(∅)) = [β

2

] ∪ ([β

1

] ∩ Preimage(X

j

)) Noticing that X

1

= [β

2

] and X

j+1

⊇ X

j

for 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

]

(80)

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

(81)

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

)

(82)

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

(83)

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

(84)

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 ϕ

i

is 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

(85)

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 ϕ

i

is a

Propositional atoms: apply labeling function Boolean operator: apply standard set operations

temporal operator: appy recursively the tableaux rules, until a

fixpoint is reached

(86)

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 ϕ

i

is 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

(87)

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 ϕ

i

is a

Propositional atoms: apply labeling function Boolean operator: apply standard set operations

temporal operator: appy recursively the tableaux rules, until a

fixpoint is reached

(88)

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 ϕ

i

is 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

(89)

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 ϕ

i

is a

Propositional atoms: apply labeling function Boolean operator: apply standard set operations

temporal operator: appy recursively the tableaux rules, until a

fixpoint is reached

(90)

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 ϕ

i

is 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

(91)

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 ϕ

i

is a

Propositional atoms: apply labeling function Boolean operator: apply standard set operations

temporal operator: appy recursively the tableaux rules, until a

fixpoint is reached

Riferimenti

Documenti correlati

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

Kripke structure encoded as Boolean formulas (OBDDs) All operations handled as (quantified) Boolean operations Avoids building the state graph explicitly. reduces dramatically the

(E.g., 300 Boolean vars =⇒ up to 2 300 ≈ 10 100 states!) State Space Explosion:.. too much

Copyright notice: some material (text, figures) displayed in these slides is courtesy of R..

Given a fair Kripke model M, a fair non-trivial SCC is an SCC with at least one edge that contains at least one state for every fair condition. =⇒ all states in a fair (non-trivial)

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> fairness condition, which is equivalent to say that all states belong to the fairness

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: