Introduction to Formal Methods Chapter 06: Fair CTL Model Checking

Introduction to Formal Methods Chapter 06: Fair CTL 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 18^thMay, 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

without containing this copyright notice.

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

Outline

1 Fair CTL Model Checking: Generalities

2 Checking Fair EG (Explicit-State)

3 Checking Fair EG (Symbolic)

Fair CTL Model Checking: Generalities

Fairness/Justice

An event E occurs infinitely often. Example:

Let R _i be true iff the process i is running.

Fairness: every process runs infinitely often.

^

i

GFR _i

(It is often used as condition for other properties.) You cannot express the condition in CTL:

GFφ = AGAFφ,

but (GFφ) → ψ 6= (AGAFφ) → ψ, because FGφ

6= EFEGφ

.

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 18^thMay, 2020 4 / 19

Fair CTL Model Checking: Generalities

Fair CTL Model Checking

Let M be the KS M = hS, S ₀ , R, L, APi and M _f the fair version M _f = hS, S ₀ , R, L, AP, FT i, FT = {F ₁ , ..., F _n }.

A path is fair iff it visits every F _i infinitely often.

Fair CTL model checking restricts the path quantifiers to fair paths:

M

, s

|= Aφ iff π |= φ for every fair path π = s

, s

, ...

M

, s

|= Eφ iff π |= φ for some fair path π = s

, s

, ...

We introduce A _f and E _f , the restricted versions of the quantifiers A and E:

M

, s |= Aφ iff M, s |= A

φ M

, s |= Eφ iff M, s |= E

φ

Fair state: a state from which at least one fair path originates, that

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

Fair CTL Model Checking: Generalities

Fair CTL Model Checking

In order to solve the fair CTL model checking problem, we must be able to compute:

[E

X(ϕ)]

[E

(ϕUψ)]

[E

Gϕ].

Suppose we have a procedure Check_FairEG to compute [E _f Gϕ].

Let fair = E _f Gtrue. (M, s |= E _f Gtrue if s is a fair state.) if ϕ is Boolean, then M _f , s |= ϕ iff M, s |= (ϕ ∧ fair ) We can rewrite all the other fair operators:

E

X(ϕ) ≡ EX(ϕ ∧ fair ) E

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

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

Fair CTL Model Checking: Generalities

Fair CTL Model Checking

E _f X(ϕ) ≡ EX(ϕ ∧ fair ):

fair F

ϕ

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

ϕ ϕ ϕ ϕ ϕ ϕ

F

ψ fair

Checking FairEG (Explicit-State)

SCC-based Check_FairEG

A Strongly Connected Component (SCC) of a directed graph is a maximal subgraph s.t. all its nodes are reachable from each other.

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) SCC are fair states

F3

F2 F1

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

Checking FairEG (Explicit-State)

SCC-based Check_FairEG (cont.)

Check_FairEG([φ]):

(i) restrict the graph of M to [φ];

(ii) find all fair non-trivial SCCs C i

(iii) build C := ∪ _i C _i ;

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

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

M |= A _f G(T ₁ → A _f FC ₁ ) = ¬E _f F(T ₁ ∧ E _f G¬C ₁ )

Check_FairEG(¬C ₁ ): 1. compute [¬C ₁ ] Check_FairEG(¬C ₁ ): 2.

restrict the graph to [¬C ₁ ] Check_FairEG(¬C ₁ ): 3. find all fair non-trivial SCC’s Check_FairEG(¬C ₁ ): 4. build the union C of all SCC’s Check_FairEG(¬C ₁ ): 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 18^thMay, 2020 11 / 19

Checking FairEG (Explicit-State)

SCC-based Check_FairEG - Drawbacks

SCCs computation requires a linear (O(#nodes + #edges) ) DFS (Tarjan).

The DFS manipulates the states explicitly, storing information for every state.

A DFS is not suitable for symbolic model checking where we manipulate sets of states.

We want an algorithm based on the preimage computation.

Checking FairEG (Symbolic)

Emerson-Lei Algorithm

Recall the fixpoint characterization of EG:

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

The greatest set Z s.t. every state z in Z satisfies φ and reaches another state in Z in one step.

We can characterize E _f G similarly:

[E _f Gφ] = νZ .([φ] ∩ T

F

∈FT [EX E(Z U(Z ∩ F _i ))])

The greatest set Z s.t. every state z in Z satisfies φ and, for every set F _i ∈ FT, z reaches a state in F _i ∩ Z by means of a non-trivial path that lies in Z.

[EG ] φ

Z [φ]

[E G ]

φ

F1 F2

Fn

Z

F3

[φ]

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

Checking FairEG (Symbolic)

Emerson-Lei Algorithm

Recall: [E _f Gφ] = νZ .([φ] ∩ T

F

∈FT [EX E(Z U(Z ∩ F _i ))]) state_set Check_FairEG( state_set [φ]) {

Z’:= [φ];

repeat Z:= Z’;

for each Fi in FT

Y:= Check_EU(Z,Fi∩Z);

Z’:= Z’ ∩ PreImage(Y));

end for;

until (Z’ = Z);

return Z;

}

Implementation of the above formula

Checking FairEG (Symbolic)

Emerson-Lei Algorithm

Recall: [E _f Gφ] = νZ .([φ] ∩ T

F

∈FT [EX E(Z U(Z ∩ F _i ))]) state_set Check_FairEG( state_set [φ]) {

Z’:= [φ];

repeat Z:= Z’;

for each Fi in FT

Y:= Check_EU(Z’,Fi∩Z’);

Z’:= Z’ ∩ PreImage(Y));

end for;

until (Z’ = Z);

return Z;

}

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

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

Checking FairEG (Symbolic)

Emerson-Lei Algorithm (symbolic version)

Recall: [E _f Gφ] = νZ .([φ] ∩ T

F

∈FT [EX E(Z U(Z ∧ F _i ))]) Obdd Check_FairEG( Obdd φ) {

Z’:= φ;

repeat Z:= Z’;

for each Fi in FT

Y:= Check_EU(Z’,Fi∧Z’);

Z’:= Z’ ∧ PreImage(Y));

end for;

until (Z’ ↔ Z);

return Z;

}

Symbolic version.

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

M |= AG(T ₁ → AFC ₁ ) = ¬EF(T ₁ ∧ EG¬C ₁ )

EGg = νZ .g ∧ EXZ

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

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

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

M |= A _f G(T ₁ → A _f FC ₁ ) = ¬E _f F(T ₁ ∧ E _f G¬C ₁ )

E _f Gg = νZ .g ∧ EXE(Z U(Z ∧ F ₁ )) ∧ EXE(Z U(Z ∧ F ₂ ))

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

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