## 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^{th}May, 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^{th}May, 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φ**

^{0}

**6= EFEGφ**

^{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 18^{th}May, 2020 4 / 19

Fair CTL Model Checking: Generalities

## Fair CTL Model Checking

### Let M be the KS M = hS, S _{0} , R, L, APi and M _{f} the fair version M _{f} = hS, S _{0} , R, L, AP, FT i, FT = {F _{1} , ..., 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

_{f}

### , s

_{i}

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

_{i}

### , s

_{i+1}

### , ...

### M

_{f}

### , s

_{i}

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

_{i}

### , s

_{i+1}

### , ...

### We introduce **A** _{f} and **E** _{f} , the restricted versions of the quantifiers **A and E:**

### M

f### , s |= **Aφ iff M, s |= A**

_{f}

### φ M

_{f}

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

_{f}

### φ

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

f**X(ϕ)]**

### [E

_{f}

### (ϕUψ)]

### [E

_{f}

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

_{f}

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

_{f}

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

Sebastiani and Tonetta Ch. 06: Fair CTL Model Checking Monday 18^{th}May, 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 Fair**EG (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^{th}May, 2020 9 / 19

Checking Fair**EG (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 Fair**EG (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** _{1} **→ A** _{f} **FC** _{1} ) = **¬E** _{f} **F(T** _{1} **∧ E** _{f} **G¬C** _{1} )

### Check_FairEG(¬C _{1} ): 1. compute [¬C _{1} ] Check_FairEG(¬C _{1} ): 2.

### 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 18^{th}May, 2020 11 / 19

Checking Fair**EG (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 Fair**EG (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

i### ∈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 ]**

**f**

## φ

### F1 F2

### Fn

### Z

### F3

## [φ]

Sebastiani and Tonetta Ch. 06: Fair CTL Model Checking Monday 18^{th}May, 2020 14 / 19

Checking Fair**EG (Symbolic)**

## Emerson-Lei Algorithm

### Recall: [E _{f} **Gφ] = νZ .([φ] ∩** T

### F

i### ∈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 Fair**EG (Symbolic)**

## Emerson-Lei Algorithm

### Recall: [E _{f} **Gφ] = νZ .([φ] ∩** T

### F

i### ∈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 ^{0}

Sebastiani and Tonetta Ch. 06: Fair CTL Model Checking Monday 18^{th}May, 2020 16 / 19

Checking Fair**EG (Symbolic)**

## Emerson-Lei Algorithm (symbolic version)

### Recall: [E _{f} **Gφ] = νZ .([φ] ∩** T

### F

i### ∈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 Fair**EG (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** _{1} **→ AFC** _{1} ) = **¬EF(T** _{1} **∧ EG¬C** _{1} )

**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^{th}May, 2020 18 / 19

Checking Fair**EG (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** _{1} **→ A** _{f} **FC** _{1} ) = **¬E** _{f} **F(T** _{1} **∧ E** _{f} **G¬C** _{1} )

**E** _{f} **Gg = νZ .g** ∧ **EXE(Z U(Z ∧** F _{1} )) ∧ **EXE(Z U(Z ∧** F _{2} ))

**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^{th}May, 2020 19 / 19