• Non ci sono risultati.

Introduction to Formal Methods Chapter 06: Fair CTL Model Checking

N/A
N/A
Protected

Condividi "Introduction to Formal Methods Chapter 06: Fair CTL Model Checking"

Copied!
16
0
0

Testo completo

(1)

Introduction to Formal Methods Chapter 06: Fair CTL Model Checking

CDLM in Informatica, academic year 2019-2020

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

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

Sebastiani and Tonetta Ch. 06: Fair CTL Model Checking Monday 18thMay, 2020 1 / 19

(2)

Outline

3 Checking Fair EG (Symbolic)

(3)

Fair CTL Model Checking: Generalities

Fairness/Justice

0

0

There is no CTL formula equivalent to FGφ (FGφ 6= AFAGφ and FGφ 6= EFEGφ).

Sebastiani and Tonetta Ch. 06: Fair CTL Model Checking Monday 18thMay, 2020 4 / 19

(4)

Fair CTL Model Checking: Generalities

Fair CTL Model Checking

f

i

i

i+1

f

i

i

i+1

f

f

f

f

is, a state s is a fair state in M f iff M f , s |= EGtrue.

(5)

Fair CTL Model Checking: Generalities

Fair CTL Model Checking

f

f

f

f

f

(ϕUψ) ≡ E(ϕU(ψ ∧ fair ))

Sebastiani and Tonetta Ch. 06: Fair CTL Model Checking Monday 18thMay, 2020 6 / 19

(6)

Fair CTL Model Checking: Generalities

Fair CTL Model Checking

ψ fair

(7)

Checking FairEG (Explicit-State)

SCC-based Check_FairEG

F2 F1

Sebastiani and Tonetta Ch. 06: Fair CTL Model Checking Monday 18thMay, 2020 9 / 19

(8)

Checking FairEG (Explicit-State)

SCC-based Check_FairEG (cont.)

(iv) compute the states that can reach C (Check_EU([φ],C)).

(9)

Checking FairEG (Explicit-State)

Example: Check_FairEG

F := {{ not C1},{not C2}}

turn=1

turn=2

turn=2 turn=2

turn=1 turn=1

turn=1

turn=2

T1, C2 N1, C2 T1, T2

T1, T2

N1, T2

C1, T2 C1, N2

T1, N2

N1, N2 turn=0

not C1 not C2

turn=1

turn=2

turn=2 turn=2

turn=1 turn=1

turn=1

turn=2

T1, C2 N1, C2 T1, T2

T1, T2

N1, T2

C1, T2 C1, N2

T1, N2

N1, N2 turn=0

not C1 not C2

turn=1

turn=2

turn=2 turn=2

turn=1 turn=1

turn=1

turn=2

T1, C2 N1, C2 T1, T2

T1, T2

N1, T2

C1, T2 C1, N2

T1, N2

N1, N2 turn=0

not C1 not C2

turn=1

turn=2

turn=2 turn=2

turn=1 turn=1

turn=1

turn=2

T1, C2 N1, C2 T1, T2

T1, T2

N1, T2

C1, T2 C1, N2

T1, N2

N1, N2 turn=0

not C1 not C2

turn=1

turn=2

turn=2 turn=2

turn=1 turn=1

turn=1

turn=2

T1, C2 N1, C2 T1, T2

T1, T2

N1, T2

C1, T2 C1, N2

T1, N2

N1, N2 turn=0

not C1 not C2

turn=1

turn=2

turn=2 turn=2

turn=1 turn=1

turn=1

turn=2

T1, C2 N1, C2 T1, T2

T1, T2

N1, T2

C1, T2 C1, N2

T1, N2

N1, N2 turn=0

not C1 not C2

turn=1

turn=2

turn=2 turn=2

turn=1 turn=1

turn=1

turn=2

T1, C2 N1, C2 T1, T2

T1, T2

N1, T2

C1, T2 C1, N2

T1, N2

N1, N2 turn=0

not C1 not C2

restrict the graph to [¬C 1 ] Check_FairEG(¬C 1 ): 3. find all fair non-trivial SCC’s Check_FairEG(¬C 1 ): 4. build the union C of all SCC’s Check_FairEG(¬C 1 ): 5. compute the states which can reach it Check_FairEU(>, ϕ) = Check_EU(>, ϕ ∧ fair ) fair=Check_FairEG(>) Check_FairEU(>, ϕ) = Check_EU(>, ϕ ∧ fair ) =⇒ Property Verified

Sebastiani and Tonetta Ch. 06: Fair CTL Model Checking Monday 18thMay, 2020 11 / 19

(10)

Checking FairEG (Explicit-State)

SCC-based Check_FairEG - Drawbacks

We want an algorithm based on the preimage computation.

(11)

Checking FairEG (Symbolic)

i

f

[φ]

Sebastiani and Tonetta Ch. 06: Fair CTL Model Checking Monday 18thMay, 2020 14 / 19

(12)

Checking FairEG (Symbolic)

Emerson-Lei Algorithm

i

Implementation of the above formula

(13)

Checking FairEG (Symbolic)

Emerson-Lei Algorithm

i

Slight improvement: do not consider states in Z \ Z 0

Sebastiani and Tonetta Ch. 06: Fair CTL Model Checking Monday 18thMay, 2020 16 / 19

(14)

Checking FairEG (Symbolic)

Emerson-Lei Algorithm (symbolic version)

i

Symbolic version.

(15)

Checking FairEG (Symbolic)

Example: normal Check_EG

F := { { not C1},{not C2}}

turn=1

turn=2

turn=2 turn=2

turn=1 turn=1

turn=1

turn=2

T1, C2 N1, C2 T1, T2

T1, T2

N1, T2

C1, T2 C1, N2

T1, N2

N1, N2 turn=0

not C1 not C2

turn=1

turn=2

turn=2 turn=2

turn=1 turn=1

turn=1

turn=2

T1, C2 N1, C2 T1, T2

T1, T2

N1, T2

C1, T2 C1, N2

T1, N2

N1, N2 turn=0

not C1 not C2

turn=1

turn=2

turn=2 turn=2

turn=1 turn=1

turn=1

turn=2

T1, C2 N1, C2 T1, T2

T1, T2

N1, T2

C1, T2 C1, N2

T1, N2

N1, N2 turn=0

not C1 not C2

turn=1

turn=2

turn=2 turn=2

turn=1 turn=1

turn=1

turn=2

T1, C2 N1, C2 T1, T2

T1, T2

N1, T2

C1, T2 C1, N2

T1, N2

N1, N2 turn=0

not C1 not C2

turn=1

turn=2

turn=2 turn=2

turn=1 turn=1

turn=1

turn=2

T1, C2 N1, C2 T1, T2

T1, T2

N1, T2

C1, T2 C1, N2

T1, N2

N1, N2 turn=0

not C1 not C2

turn=1

turn=2

turn=2 turn=2

turn=1 turn=1

turn=1

turn=2

T1, C2 N1, C2 T1, T2

T1, T2

N1, T2

C1, T2 C1, N2

T1, N2

N1, N2 turn=0

not C1 not C2

turn=1

turn=2

turn=2 turn=2

turn=1 turn=1

turn=1

turn=2

T1, C2 N1, C2 T1, T2

T1, T2

N1, T2

C1, T2 C1, N2

T1, N2

N1, N2 turn=0

not C1 not C2

turn=1

turn=2

turn=2 turn=2

turn=1 turn=1

turn=1

turn=2

T1, C2 N1, C2 T1, T2

T1, T2

N1, T2

C1, T2 C1, N2

T1, N2

N1, N2 turn=0

not C1 not C2

turn=1

turn=2

turn=2 turn=2

turn=1 turn=1

turn=1

turn=2

T1, C2 N1, C2 T1, T2

T1, T2

N1, T2

C1, T2 C1, N2

T1, N2

N1, N2 turn=0

not C1 not C2

turn=1

turn=2

turn=2 turn=2

turn=1 turn=1

turn=1

turn=2

T1, C2 N1, C2 T1, T2

T1, T2

N1, T2

C1, T2 C1, N2

T1, N2

N1, N2 turn=0

not C1 not C2

EFg = E(>Ug) = µZ .g ∨ (> ∧ EXZ ) = µZ .g ∨ EXZ =⇒ Property not verified

Sebastiani and Tonetta Ch. 06: Fair CTL Model Checking Monday 18thMay, 2020 18 / 19

(16)

Checking FairEG (Symbolic)

Example: Check_FairEG

F := { { not C1},{not C2}}

turn=1

turn=2

turn=2 turn=2

turn=1 turn=1

turn=1

turn=2

T1, C2 N1, C2 T1, T2

T1, T2

N1, T2

C1, T2 C1, N2

T1, N2

N1, N2 turn=0

not C1 not C2

turn=1

turn=2

turn=2 turn=2

turn=1 turn=1

turn=1

turn=2

T1, C2 N1, C2 T1, T2

T1, T2

N1, T2

C1, T2 C1, N2

T1, N2

N1, N2 turn=0

not C1 not C2

turn=1

turn=2

turn=2 turn=2

turn=1 turn=1

turn=1

turn=2

T1, C2 N1, C2 T1, T2

T1, T2

N1, T2

C1, T2 C1, N2

T1, N2

N1, N2 turn=0

not C1 not C2

turn=1

turn=2

turn=2 turn=2

turn=1 turn=1

turn=1

turn=2

T1, C2 N1, C2 T1, T2

T1, T2

N1, T2

C1, T2 C1, N2

T1, N2

N1, N2 turn=0

not C1 not C2

turn=1

turn=2

turn=2 turn=2

turn=1 turn=1

turn=1

turn=2

T1, C2 N1, C2 T1, T2

T1, T2

N1, T2

C1, T2 C1, N2

T1, N2

N1, N2 turn=0

not C1 not C2

turn=1

turn=2

turn=2 turn=2

turn=1 turn=1

turn=1

turn=2

T1, C2 N1, C2 T1, T2

T1, T2

N1, T2

C1, T2 C1, N2

T1, N2

N1, N2 turn=0

not C1 not C2

turn=1

turn=2

turn=2 turn=2

turn=1 turn=1

turn=1

turn=2

T1, C2 N1, C2 T1, T2

T1, T2

N1, T2

C1, T2 C1, N2

T1, N2

N1, N2 turn=0

not C1 not C2

turn=1

turn=2

turn=2 turn=2

turn=1 turn=1

turn=1

turn=2

T1, C2 N1, C2 T1, T2

T1, T2

N1, T2

C1, T2 C1, N2

T1, N2

N1, N2 turn=0

not C1 not C2

turn=1

turn=2

turn=2 turn=2

turn=1 turn=1

turn=1

turn=2

T1, C2 N1, C2 T1, T2

T1, T2

N1, T2

C1, T2 C1, N2

T1, N2

N1, N2 turn=0

not C1 not C2

EGg = νZ .g ∧ EXE(Z U(Z ∧ F )) ∧ EXE(Z U(Z ∧ F )) Fixpoint

Sebastiani and Tonetta Ch. 06: Fair CTL Model Checking Monday 18thMay, 2020 19 / 19

Riferimenti

Documenti correlati

The course will concentrate mainly on formal validation and verification and, in particular, on Model Checking (MC). A laboratory will be given in which the students will experience

Reviewing, Testing &amp; Simulation (currently mostly used) Formal verification methods (increasingly used)... Problems with

Allows for both synchronous and asyncronous composition of processes (though asynchronous interaction more

Tipically a Kripke model is not given explicitly, rather it is usually presented in a structured language.. (e.g., SMV, SDL, PROMELA, StateCharts,

interpreted over each path of the Kripke structure linear model of time.

=⇒ it is reasonable enough to assume the protocol suitable under the condition that each user is infinitely often outside the restroom such a condition is called fairness

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

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

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

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&gt; 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:

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

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

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

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

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

=⇒ Substantially, add one initial state, move labels from states to incoming edges, set fair states as accepting states.. The Main Problem of M.C.: State

=⇒ It is reasonable enough to assume the protocol suitable under the condition that each user is infinitely often outside the restroom.. Such a condition is called

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

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