Introduction to Formal Methods Chapter 10: Abstraction in Model Checking

(1)

Introduction to Formal Methods

Chapter 10: Abstraction in 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 18^thMay, 2020, 14:49

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.

th

(2)

Outline

1 Abstraction

2 Abstraction-Based Symbolic Model Cheching Abstraction

Checking the counter-examples Refinement

3 Exercises

th

(3)

Abstraction

Outline

1 Abstraction

2 Abstraction-Based Symbolic Model Cheching Abstraction

Checking the counter-examples Refinement

3 Exercises

th

(4)

Abstraction

Model Checking Safety Properties: M |= AG¬BAD

Add reachable states until reaching a fixed-point or a “bad” state

S11

S12

S13

S21

S22

S23

S31

S32

S33

S41

S42

S43

S51

S52

S53

S61

S62

S63

Problem: too many states to handle! (even for symbolic MC)

th

(5)

Abstraction

Model Checking Safety Properties: M |= AG¬BAD

Add reachable states until reaching a fixed-point or a “bad” state

S11

S12

S13

S21

S22

S23

S31

S32

S33

S41

S42

S43

S51

S52

S53

S61

S62

S63

Problem: too many states to handle! (even for symbolic MC)

th

(6)

Abstraction

Model Checking Safety Properties: M |= AG¬BAD

Add reachable states until reaching a fixed-point or a “bad” state

S11

S12

S13

S21

S22

S23

S31

S32

S33

S41

S42

S43

S51

S52

S53

S61

S62

S63

Problem: too many states to handle! (even for symbolic MC)

th

(7)

Abstraction

Model Checking Safety Properties: M |= AG¬BAD

Add reachable states until reaching a fixed-point or a “bad” state

S11

S12

S13

S21

S22

S23

S31

S32

S33

S41

S42

S43

S51

S52

S53

S61

S62

S63

Problem: too many states to handle! (even for symbolic MC)

th

(8)

Abstraction

Model Checking Safety Properties: M |= AG¬BAD

Add reachable states until reaching a fixed-point or a “bad” state

S11

S12

S13

S21

S22

S23

S31

S32

S33

S41

S42

S43

S51

S52

S53

S61

S62

S63

Problem: too many states to handle! (even for symbolic MC)

th

(9)

Abstraction

Model Checking Safety Properties: M |= AG¬BAD

Add reachable states until reaching a fixed-point or a “bad” state

S11

S12

S13

S21

S22

S23

S31

S32

S33

S41

S42

S43

S51

S52

S53

S61

S62

S63

Problem: too many states to handle! (even for symbolic MC)

th

(10)

Abstraction

Model Checking Safety Properties: M |= AG¬BAD

Add reachable states until reaching a fixed-point or a “bad” state

S11

S12

S13

S21

S22

S23

S31

S32

S33

S41

S42

S43

S51

S52

S53

S61

S62

S63

Problem: too many states to handle! (even for symbolic MC)

th

(11)

Abstraction

Model Checking Safety Properties: M |= AG¬BAD

Add reachable states until reaching a fixed-point or a “bad” state

S11

S12

S13

S21

S22

S23

S31

S32

S33

S41

S42

S43

S51

S52

S53

S61

S62

S63

Problem: too many states to handle! (even for symbolic MC)

th

(12)

Abstraction

Model Checking Safety Properties: M |= AG¬BAD

Add reachable states until reaching a fixed-point or a “bad” state

S11

S12

S13

S21

S22

S23

S31

S32

S33

S41

S42

S43

S51

S52

S53

S61

S62

S63

Problem: too many states to handle! (even for symbolic MC)

th

(13)

Abstraction

Idea: Abstraction

Apply a (non-injective) Abstraction Function h to M

=⇒ Build an abstract (and much smaller) system M’

Ground System

Abstract System S11

S12

S13

S21

S22

S23

S31

S32

S33

S41

S42

S43

S51

S52

S53

S61

S62

S63

T1 T2 T3 T4 T5 T6

M

M’

h h h h h h

th

(14)

Abstraction

Abstraction & Refinement

Let S be the ground (concrete) state space Let S ⁰ be the abstract state space

Abstraction: a (typically non-injective) map h : S 7−→ S ⁰ h typically a many-to-one function

Refinement: a map r : S ⁰ 7−→ 2 ^S s.t. r (s ⁰ )

^def

= {s ∈ S | s ⁰ = h(s)}

th

(15)

Abstraction

Simulation and Bisimulation

Simulation

Let M ₁

^def

= hS ₁ , I ₁ , R ₁ , AP ₁ , L ₁ i and M 2

def

= hS ₂ , I ₂ , R ₂ , AP ₂ , L ₂ i. Then p ⊆ S ₁ × S ₂ is a simulation between M ₁ and M ₂ iff

for every s ₂ ∈ I ₂ exists s ₁ ∈ I ₁ s.t. hs ₁ , s ₂ i ∈ p for every hs ₁ , s ₂ i ∈ p:

for every hs ₂ , t ₂ i ∈ R ₂ , exists hs ₁ , t ₁ i ∈ R ₁ s.t. ht ₁ , t ₂ i ∈ p

(Intuitively, for every transition in M ₂ there is a corresponding transition in M ₁ .) We say that M ₁ simulates M ₂ .

Example of p (spy game): “follower M ₁ keeps escaper M ₂ at eyesight” Bisimulation

P is a bisimulation between M and M ⁰ iff it is both a simulation between M and M ⁰ and between M ⁰ and M. We say that M and M ⁰ bisimulate each other.

th

(16)

Abstraction

Simulation and Bisimulation

Simulation

Let M ₁

^def

= hS ₁ , I ₁ , R ₁ , AP ₁ , L ₁ i and M 2

def

= hS ₂ , I ₂ , R ₂ , AP ₂ , L ₂ i. Then p ⊆ S ₁ × S ₂ is a simulation between M ₁ and M ₂ iff

for every s ₂ ∈ I ₂ exists s ₁ ∈ I ₁ s.t. hs ₁ , s ₂ i ∈ p for every hs ₁ , s ₂ i ∈ p:

for every hs ₂ , t ₂ i ∈ R ₂ , exists hs ₁ , t ₁ i ∈ R ₁ s.t. ht ₁ , t ₂ i ∈ p

(Intuitively, for every transition in M ₂ there is a corresponding transition in M ₁ .) We say that M ₁ simulates M ₂ .

Example of p (spy game): “follower M ₁ keeps escaper M ₂ at eyesight”

Bisimulation

P is a bisimulation between M and M ⁰ iff it is both a simulation between M and M ⁰ and between M ⁰ and M. We say that M and M ⁰ bisimulate each other.

th

(17)

Abstraction

Simulation and Bisimulation

Simulation

Let M ₁

^def

= hS ₁ , I ₁ , R ₁ , AP ₁ , L ₁ i and M 2

def

= hS ₂ , I ₂ , R ₂ , AP ₂ , L ₂ i. Then p ⊆ S ₁ × S ₂ is a simulation between M ₁ and M ₂ iff

for every s ₂ ∈ I ₂ exists s ₁ ∈ I ₁ s.t. hs ₁ , s ₂ i ∈ p for every hs ₁ , s ₂ i ∈ p:

for every hs ₂ , t ₂ i ∈ R ₂ , exists hs ₁ , t ₁ i ∈ R ₁ s.t. ht ₁ , t ₂ i ∈ p

(Intuitively, for every transition in M ₂ there is a corresponding transition in M ₁ .) We say that M ₁ simulates M ₂ .

Example of p (spy game): “follower M ₁ keeps escaper M ₂ at eyesight”

Bisimulation

P is a bisimulation between M and M ⁰ iff it is both a simulation between M and M ⁰ and between M ⁰ and M. We say that M and M ⁰ bisimulate each other.

th

(18)

Abstraction

Example I

Ground System

Abstract System S11

S12

S13

S21

S22

S23

S31

S32

S33

S41

S42

S43

S51

S52

S53

S61

S62

S63

T1 T2 T3 T4 T5 T6

M

M’

Does M simulate M’?

No: e.g., no arc from S23 to any S3i.

Does M’ simulate M?

Yes

th

(19)

Abstraction

Example I

Ground System

Abstract System S11

S12

S13

S21

S22

S23

S31

S32

S33

S41

S42

S43

S51

S52

S53

S61

S62

S63

T1 T2 T3 T4 T5 T6

M

M’

Does M simulate M’?

No: e.g., no arc from S23 to any S3i. Does M’ simulate M?

Yes

th

(20)

Abstraction

Example I

Ground System

Abstract System S11

S12

S13

S21

S22

S23

S31

S32

S33

S41

S42

S43

S51

S52

S53

S61

S62

S63

T1 T2 T3 T4 T5 T6

M

M’

Does M simulate M’? No: e.g., no arc from S23 to any S3i.

Does M’ simulate M?

Yes

th

(21)

Abstraction

Example I

Ground System

Abstract System S11

S12

S13

S21

S22

S23

S31

S32

S33

S41

S42

S43

S51

S52

S53

S61

S62

S63

T1 T2 T3 T4 T5 T6

M

M’

Does M simulate M’? No: e.g., no arc from S23 to any S3i.

Does M’ simulate M?

Yes

th

(22)

Abstraction

Example I

Ground System

Abstract System S11

S12

S13

S21

S22

S23

S31

S32

S33

S41

S42

S43

S51

S52

S53

S61

S62

S63

T1 T2 T3 T4 T5 T6

M

M’

Does M simulate M’? No: e.g., no arc from S23 to any S3i.

Does M’ simulate M? Yes

th

(23)

Abstraction

Example II

Ground System

Abstract System S11

S12

S13

S21

S22

S23

S31

S32

S33

S41

S42

S43

S51

S52

S53

S61

S62

S63

T1 T2 T3 T4 T5 T6

M

M’

h h h h h h

Does M simulate M’?

Yes

Does M’ simulate M?

No: e.g., no arc from T 4 to T 3.

th

(24)

Abstraction

Example II

Ground System

Abstract System S11

S12

S13

S21

S22

S23

S31

S32

S33

S41

S42

S43

S51

S52

S53

S61

S62

S63

T1 T2 T3 T4 T5 T6

M

M’

h h h h h h

Does M simulate M’?

Yes Does M’ simulate M?

No: e.g., no arc from T 4 to T 3.

th

(25)

Abstraction

Example II

Ground System

Abstract System S11

S12

S13

S21

S22

S23

S31

S32

S33

S41

S42

S43

S51

S52

S53

S61

S62

S63

T1 T2 T3 T4 T5 T6

M

M’

h h h h h h

Does M simulate M’? Yes

Does M’ simulate M?

No: e.g., no arc from T 4 to T 3.

th

(26)

Abstraction

Example II

Ground System

Abstract System S11

S12

S13

S21

S22

S23

S31

S32

S33

S41

S42

S43

S51

S52

S53

S61

S62

S63

T1 T2 T3 T4 T5 T6

M

M’

h h h h h h

Does M simulate M’? Yes Does M’ simulate M?

No: e.g., no arc from T 4 to T 3.

th

(27)

Abstraction

Example II

Ground System

Abstract System S11

S12

S13

S21

S22

S23

S31

S32

S33

S41

S42

S43

S51

S52

S53

S61

S62

S63

T1 T2 T3 T4 T5 T6

M

M’

h h h h h h

Does M simulate M’? Yes

Does M’ simulate M? No: e.g., no arc from T 4 to T 3.

th

(28)

Abstraction

Example III

Ground System

Abstract System S11

S12

S13

S21

S22

S23

S31

S32

S33

S41

S42

S43

S51

S52

S53

S61

S62

S63

T1 T2 T3 T4 T5 T6

M

M’

h h h h h h

Does M simulate M’?

Yes

Does M’ simulate M?

Yes

th

(29)

Abstraction

Example III

Ground System

Abstract System S11

S12

S13

S21

S22

S23

S31

S32

S33

S41

S42

S43

S51

S52

S53

S61

S62

S63

T1 T2 T3 T4 T5 T6

M

M’

h h h h h h

Does M simulate M’?

Yes Does M’ simulate M?

Yes

th

(30)

Abstraction

Example III

Ground System

Abstract System S11

S12

S13

S21

S22

S23

S31

S32

S33

S41

S42

S43

S51

S52

S53

S61

S62

S63

T1 T2 T3 T4 T5 T6

M

M’

h h h h h h

Does M simulate M’? Yes

Does M’ simulate M?

Yes

th

(31)

Abstraction

Example III

Ground System

Abstract System S11

S12

S13

S21

S22

S23

S31

S32

S33

S41

S42

S43

S51

S52

S53

S61

S62

S63

T1 T2 T3 T4 T5 T6

M

M’

h h h h h h

Does M simulate M’? Yes Does M’ simulate M?

Yes

th

(32)

Abstraction

Example III

Ground System

Abstract System S11

S12

S13

S21

S22

S23

S31

S32

S33

S41

S42

S43

S51

S52

S53

S61

S62

S63

T1 T2 T3 T4 T5 T6

M

M’

h h h h h h

Does M simulate M’? Yes Does M’ simulate M? Yes

th

(33)

Abstraction

Existential Abstraction (Over-Approximation)

An Abstraction from M to M’ is an Existential Abstraction (aka Over-Approximation) iff M ⁰ simulates M

Ground System

Abstract System S11

S12

S13

S21

S22

S23

S31

S32

S33

S41

S42

S43

S51

S52

S53

S61

S62

S63

T1 T2 T3 T4 T5 T6

M

M’

th

(34)

Abstraction

Model Checking with Existential Abstractions

Preservation Theorem

Let ϕ be a universally-quantified property (e.g., in LTL or ACTL) Let M ⁰ simulate M

Then we have that

M ⁰ |= ϕ =⇒ M |= ϕ

Intuition: if M has a countermodel, then M’ simulates it The converse does not hold

M |= ϕ 6=⇒ M ⁰ |= ϕ

=⇒ The abstract counter-example may be spurious

(e.g., in previous figure, T 1 → T 2 → T 3 → T 4 → T 5 → T 6)

th

(35)

Abstraction

Model Checking with Existential Abstractions

Preservation Theorem

Let ϕ be a universally-quantified property (e.g., in LTL or ACTL) Let M ⁰ simulate M

Then we have that

M ⁰ |= ϕ =⇒ M |= ϕ

Intuition: if M has a countermodel, then M’ simulates it

The converse does not hold

M |= ϕ 6=⇒ M ⁰ |= ϕ

=⇒ The abstract counter-example may be spurious

(e.g., in previous figure, T 1 → T 2 → T 3 → T 4 → T 5 → T 6)

th

(36)

Abstraction

Model Checking with Existential Abstractions

Preservation Theorem

Let ϕ be a universally-quantified property (e.g., in LTL or ACTL) Let M ⁰ simulate M

Then we have that

M ⁰ |= ϕ =⇒ M |= ϕ

Intuition: if M has a countermodel, then M’ simulates it The converse does not hold

M |= ϕ 6=⇒ M ⁰ |= ϕ

=⇒ The abstract counter-example may be spurious

(e.g., in previous figure, T 1 → T 2 → T 3 → T 4 → T 5 → T 6)

th

(37)

Abstraction

Model Checking with Existential Abstractions

Preservation Theorem

Let ϕ be a universally-quantified property (e.g., in LTL or ACTL) Let M ⁰ simulate M

Then we have that

M ⁰ |= ϕ =⇒ M |= ϕ

Intuition: if M has a countermodel, then M’ simulates it The converse does not hold

M |= ϕ 6=⇒ M ⁰ |= ϕ

=⇒ The abstract counter-example may be spurious

(e.g., in previous figure, T 1 → T 2 → T 3 → T 4 → T 5 → T 6)

th

(38)

Abstraction

Universal Abstraction (Under-Approximation)

An Abstraction from M to M’ is an Universal Abstraction (aka Under-Approximation) iff M simulates M ⁰

Ground System

Abstract System S11

S12

S13

S21

S22

S23

S31

S32

S33

S41

S42

S43

S51

S52

S53

S61

S62

S63

T1 T2 T3 T4 T5 T6

M

M’

h h h h h h

th

(39)

Abstraction

Model Checking with Universal Abstractions

Preservation Theorem

Let ϕ be a existentially-quantified property (e.g., in ECTL) Let M simulate M ⁰

Then we have that

M ⁰ |= ϕ =⇒ M |= ϕ

Intuition: if M’ has a model, then M simulates it The converse does not hold

M ⁰ 6|= ϕ 6=⇒ M 6|= ϕ

Note: here the authors use “M |= ϕ” as “there exists a path of M verifying ϕ”, so that M 6|= ¬ϕ ⇐⇒ M |= ϕ

th

(40)

Abstraction

Model Checking with Universal Abstractions

Preservation Theorem

Let ϕ be a existentially-quantified property (e.g., in ECTL) Let M simulate M ⁰

Then we have that

M ⁰ |= ϕ =⇒ M |= ϕ Intuition: if M’ has a model, then M simulates it

The converse does not hold

M ⁰ 6|= ϕ 6=⇒ M 6|= ϕ

Note: here the authors use “M |= ϕ” as “there exists a path of M verifying ϕ”, so that M 6|= ¬ϕ ⇐⇒ M |= ϕ

th

(41)

Abstraction

Model Checking with Universal Abstractions

Preservation Theorem

Let ϕ be a existentially-quantified property (e.g., in ECTL) Let M simulate M ⁰

Then we have that

M ⁰ |= ϕ =⇒ M |= ϕ

Intuition: if M’ has a model, then M simulates it The converse does not hold

M ⁰ 6|= ϕ 6=⇒ M 6|= ϕ

Note: here the authors use “M |= ϕ” as “there exists a path of M verifying ϕ”, so that M 6|= ¬ϕ ⇐⇒ M |= ϕ

th

(42)

Abstraction

Bisimulation Abstraction

An Abstraction from M to M’ is a Bisimulation Abstraction iff M simulates M ⁰ and M ⁰ simulates M

Ground System

Abstract System S11

S12

S13

S21

S22

S23

S31

S32

S33

S41

S42

S43

S51

S52

S53

S61

S62

S63

T1 T2 T3 T4 T5 T6

M

M’

h h h h h h

th

(43)

Abstraction

Model Checking with Bisimulation Abstractions

Preservation Theorem

Let ϕ be any CTL/LTL property Let M simulate M ⁰ and M ⁰ simulate M Then we have that

M ⁰ |= ϕ ⇐⇒ M |= ϕ

th

(44)

Abstraction-Based Symbolic Model Cheching

Outline

1 Abstraction

2 Abstraction-Based Symbolic Model Cheching Abstraction

Checking the counter-examples Refinement

3 Exercises

th

(45)

Abstraction-Based Symbolic Model Cheching

Counter-Example Guided Abstraction Refinement - CEGAR

GENERAL SCHEMA:

Model Checking

M,p,h

M’,p Spurious

No

counter example

h’

M 6|= p M |= p

Yes: Real:

Check

Abstraction Refinement

Counterex.

th

(46)

Abstraction-Based Symbolic Model Cheching Abstraction

Outline

1 Abstraction

2 Abstraction-Based Symbolic Model Cheching Abstraction

Checking the counter-examples Refinement

3 Exercises

th

(47)

Counter-Example Guided Abstraction Refinement

GENERAL SCHEMA:

Model Checking

M,p,h

M’,p Spurious

No

counter example

h’

M 6|= p M |= p

Yes: Real:

Check

Abstraction Refinement

Counterex.

th

(48)

Counter-Example Guided Abstraction Refinement

GENERAL SCHEMA:

Model Checking

M,p,h

M’,p Spurious

No

counter example

h’

M 6|= p M |= p

Yes: Real:

Check

Abstraction Refinement

Counterex.

th

(49)

A Popular Abstraction for Symbolic MC of AG¬BAD I

A.k.a. “Localization Reduction”

Partition Boolean variables into visible (V) and invisible (I) ones The abstract model built on visible variables only.

Invisible variables are made inputs (no updates in the transition relation)

All variables occurring in “¬BAD” must be visible

The abstraction function maps each state to its projection over V.

=⇒ Group ground states with same visible part to a single abstract state.







visible invisible x ₁ x ₂ x ₃ x ₄ S ₁₁ : 0 0 0 0 S ₁₂ : 0 0 0 1 S ₁₃ : 0 0 1 0 S ₁₄ : 0 0 1 1







=⇒

T ₁ : 0 0

th

(50)

A Popular Abstraction for Symbolic MC of AG¬BAD I

A.k.a. “Localization Reduction”

Partition Boolean variables into visible (V) and invisible (I) ones The abstract model built on visible variables only.

Invisible variables are made inputs (no updates in the transition relation)

All variables occurring in “¬BAD” must be visible

The abstraction function maps each state to its projection over V.

=⇒ Group ground states with same visible part to a single abstract state.







visible invisible x ₁ x ₂ x ₃ x ₄ S ₁₁ : 0 0 0 0 S ₁₂ : 0 0 0 1 S ₁₃ : 0 0 1 0 S ₁₄ : 0 0 1 1







=⇒

T ₁ : 0 0

th

(51)

A Popular Abstraction for Symbolic MC of AG¬BAD I

A.k.a. “Localization Reduction”

Partition Boolean variables into visible (V) and invisible (I) ones The abstract model built on visible variables only.

Invisible variables are made inputs (no updates in the transition relation)

All variables occurring in “¬BAD” must be visible

The abstraction function maps each state to its projection over V.

=⇒ Group ground states with same visible part to a single abstract state.







visible invisible x ₁ x ₂ x ₃ x ₄ S ₁₁ : 0 0 0 0 S ₁₂ : 0 0 0 1 S ₁₃ : 0 0 1 0 S ₁₄ : 0 0 1 1







=⇒

T ₁ : 0 0

th

(52)

A Popular Abstraction for Symbolic MC of AG¬BAD II

M’ can be computed efficiently if M is in functional form (e.g. sequential circuits).







next(x ₁ ) := f ₁ (x ₁ , x ₂ , x ₃ , x ₄ ) next(x ₂ ) := f ₂ (x ₁ , x ₂ , x ₃ , x ₄ ) next(x ₃ ) := f ₃ (x ₁ , x ₂ , x ₃ , x ₄ ) next(x ₄ ) := f ₄ (x ₁ , x ₂ , x ₃ , x ₄ )







=⇒

next(x ₁ ) := f ₁ (x ₁ , x ₂ , x ₃ , x ₄ ) next(x ₂ ) := f ₂ (x ₁ , x ₂ , x ₃ , x ₄ )

Note: The next values of invisible variables, next(x ₃ ) and next(x ₄ ), can assume every value nondeterministically

=⇒ do not constrain the transition relation

Since M ⁰ obviously simulates M, this is an Existential Abstraction M ⁰ |= ϕ =⇒ M |= ϕ

may produce spurious counter-examples

th

(53)

A Popular Abstraction for Symbolic MC of AG¬BAD II

M’ can be computed efficiently if M is in functional form (e.g. sequential circuits).







next(x ₁ ) := f ₁ (x ₁ , x ₂ , x ₃ , x ₄ ) next(x ₂ ) := f ₂ (x ₁ , x ₂ , x ₃ , x ₄ ) next(x ₃ ) := f ₃ (x ₁ , x ₂ , x ₃ , x ₄ ) next(x ₄ ) := f ₄ (x ₁ , x ₂ , x ₃ , x ₄ )







=⇒

next(x ₁ ) := f ₁ (x ₁ , x ₂ , x ₃ , x ₄ ) next(x ₂ ) := f ₂ (x ₁ , x ₂ , x ₃ , x ₄ )

Note: The next values of invisible variables, next(x ₃ ) and next(x ₄ ), can assume every value nondeterministically

=⇒ do not constrain the transition relation

Since M ⁰ obviously simulates M, this is an Existential Abstraction M ⁰ |= ϕ =⇒ M |= ϕ

may produce spurious counter-examples

th

(54)

A Popular Abstraction for Symbolic MC of AG¬BAD II

M’ can be computed efficiently if M is in functional form (e.g. sequential circuits).







next(x ₁ ) := f ₁ (x ₁ , x ₂ , x ₃ , x ₄ ) next(x ₂ ) := f ₂ (x ₁ , x ₂ , x ₃ , x ₄ ) next(x ₃ ) := f ₃ (x ₁ , x ₂ , x ₃ , x ₄ ) next(x ₄ ) := f ₄ (x ₁ , x ₂ , x ₃ , x ₄ )







=⇒

next(x ₁ ) := f ₁ (x ₁ , x ₂ , x ₃ , x ₄ ) next(x ₂ ) := f ₂ (x ₁ , x ₂ , x ₃ , x ₄ )

Note: The next values of invisible variables, next(x ₃ ) and next(x ₄ ), can assume every value nondeterministically

=⇒ do not constrain the transition relation

Since M ⁰ obviously simulates M, this is an Existential Abstraction M ⁰ |= ϕ =⇒ M |= ϕ

may produce spurious counter-examples

th

(55)

A Popular Abstraction for Symbolic MC of AG¬BAD II

M’ can be computed efficiently if M is in functional form (e.g. sequential circuits).







next(x ₁ ) := f ₁ (x ₁ , x ₂ , x ₃ , x ₄ ) next(x ₂ ) := f ₂ (x ₁ , x ₂ , x ₃ , x ₄ ) next(x ₃ ) := f ₃ (x ₁ , x ₂ , x ₃ , x ₄ ) next(x ₄ ) := f ₄ (x ₁ , x ₂ , x ₃ , x ₄ )







=⇒

next(x ₁ ) := f ₁ (x ₁ , x ₂ , x ₃ , x ₄ ) next(x ₂ ) := f ₂ (x ₁ , x ₂ , x ₃ , x ₄ )

Note: The next values of invisible variables, next(x ₃ ) and next(x ₄ ), can assume every value nondeterministically

=⇒ do not constrain the transition relation

Since M ⁰ obviously simulates M, this is an Existential Abstraction M ⁰ |= ϕ =⇒ M |= ϕ

may produce spurious counter-examples

th

(56)

Abstraction-Based Symbolic Model Cheching Checking the counter-examples

Outline

1 Abstraction

2 Abstraction-Based Symbolic Model Cheching Abstraction

Checking the counter-examples Refinement

3 Exercises

th

(57)

Counter-Example Guided Abstraction Refinement

GENERAL SCHEMA:

Model Checking

M,p,h

M’,p Spurious

No

counter example

h’

M 6|= p M |= p

Yes: Real:

Check

Abstraction Refinement

Counterex.

th

(58)

Counter-Example Guided Abstraction Refinement

GENERAL SCHEMA:

Model Checking

M,p,h

M’,p Spurious

No

counter example

h’

M 6|= p M |= p

Yes: Real:

Check

Abstraction Refinement

Counterex.

th

(59)

Checking the Abstract Counter-Example I

The problem

Let c ₀ , ..., c _m counter-example in the abstract space Note: each c i is a truth assignment on the visible variables Problem: check if there exist a corresponding ground counterexample s ₀ , ..., s m s.t. c _i = h(s _i ), for every i

th

(60)

Checking the Abstract Counter-Example II

Idea

Simulate the counterexample on the concrete model Use Bounded Model Checking:

Φ

^def

= I(s ₀ ) ∧

m−1

^

i=0

R(s _i , s _i+1 ) ∧

m

^

i=0

visible(s _i ) = c _i

If satisfiable, the counter example is real, otherwise it is spurious

Note: much more efficient than the direct BMC problem:

Φ =

^def

I(s ₀ ) ∧

m−1

^

i=0

R(s _i , s _i+1 ) ∧

m

_

i=0

¬BAD _i

=⇒ cuts a 2 ^{(m+1)·|V |} factor from the Boolean search space.

th

(61)

Checking the Abstract Counter-Example II

Idea

Simulate the counterexample on the concrete model Use Bounded Model Checking:

Φ

^def

= I(s ₀ ) ∧

m−1

^

i=0

R(s _i , s _i+1 ) ∧

m

^

i=0

visible(s _i ) = c _i

If satisfiable, the counter example is real, otherwise it is spurious Note: much more efficient than the direct BMC problem:

Φ

^def

= I(s ₀ ) ∧

m−1

^

i=0

R(s _i , s _i+1 ) ∧

m

_

i=0

¬BAD _i

=⇒ cuts a 2 ^{(m+1)·|V |} factor from the Boolean search space.

th

(62)

Abstraction-Based Symbolic Model Cheching Refinement

Outline

1 Abstraction

2 Abstraction-Based Symbolic Model Cheching Abstraction

Checking the counter-examples Refinement

3 Exercises

th

(63)

Counter-Example Guided Abstraction Refinement

GENERAL SCHEMA:

Model Checking

M,p,h

M’,p Spurious

No

counter example

h’

M 6|= p M |= p

Yes: Real:

Check

Abstraction Refinement

Counterex.

th

(64)

Counter-Example Guided Abstraction Refinement

GENERAL SCHEMA:

Model Checking

M,p,h

M’,p Spurious

No

counter example

h’

M 6|= p M |= p

Yes: Real:

Check

Abstraction Refinement

Counterex.

th

(65)

The cause of spurious counter-examples I

Problem

There is a state in the abstract counter-example (failure state) s.t. two different and un-connected kinds of ground states are mapped into it:

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 a refinement of the abstract counter-example

th

(66)

The cause of spurious counter-examples II

For the spurious counter-example: T 1 → T 2 → T 3 → T 4 → T 5 → T 6

Ground System

Abstract System S11

S12

S13

S21

S22

S23

S31

S32

S33

S41

S42

S43

S51

S52

S53

S61

S62

S63

T1 T2 T3 T4 T5 T6

M

M’

th

(67)

The cause of spurious counter-examples II

For the spurious counter-example: T 1 → T 2 → T 3 → T 4 → T 5 → T 6

Ground System

Abstract System S11

S12

S13

S21

S22

S23

S31

S32

S33

S41

S42

S43

S51

S52

S53

S61

S62

S63

T1 T2 T3 T4 T5 T6

M

M’

failure state

th

(68)

The cause of spurious counter-examples II

For the spurious counter-example: T 1 → T 2 → T 3 → T 4 → T 5 → T 6

Ground System

Abstract System S11

S12

S13

S21

S22

S23

S31

S32

S33

S41

S42

S43

S51

S52

S53

S61

S62

S63

T1 T2 T3 T4 T5 T6

M

M’

deadend states

failure state

th

(69)

The cause of spurious counter-examples II

For the spurious counter-example: T 1 → T 2 → T 3 → T 4 → T 5 → T 6

Ground System

Abstract System S11

S12

S13

S21

S22

S23

S31

S32

S33

S41

S42

S43

S51

S52

S53

S61

S62

S63

T1 T2 T3 T4 T5 T6

M

M’

bad states deadend states

failure state

th

(70)

The cause of spurious counter-examples III

Problem

There is a state in the abstract counter-example (failure state) s.t. two different and un-connected kinds of ground states are mapped into it:

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 a refinement of the abstract counter-example

Solution: Refine the abstraction function.

1. identify the failure state and its deadend and bad states 2. refine the abstraction function s.t. deadend and bad states are

mapped into different abstract state

th

(71)

The cause of spurious counter-examples III

Problem

There is a state in the abstract counter-example (failure state) s.t. two different and un-connected kinds of ground states are mapped into it:

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 a refinement of the abstract counter-example

Solution: Refine the abstraction function.

1. identify the failure state and its deadend and bad states 2. refine the abstraction function s.t. deadend and bad states are

mapped into different abstract state

th

(72)

Identify the failure state and its deadend & bad states

The failure state is the state of maximum index f in the abstract counter-example s.t. the following formula is satisfiable:

Φ D

=

def

I(s ₀ ) ∧

f −1

^

i=0

R(s _i , s _i+1 ) ∧

f

^

i=0

visible(s _i ) = c _i

The (restriction on index f of the) models of Φ _D identify the deadend states {d 1 , ..., d _k }

The bad states {b 1 , ..., b _n } are identified by the (restriction on index f of the) models of the following formula:

Φ _B

^def

= R(s _f , s _{f +1} ) ∧ visible(s _f ) = c _f ∧ visible(s _{f +1} ) = c _{f +1}

th

(73)

Identify the failure state and its deadend & bad states

The failure state is the state of maximum index f in the abstract counter-example s.t. the following formula is satisfiable:

Φ D

=

def

I(s ₀ ) ∧

f −1

^

i=0

R(s _i , s _i+1 ) ∧

f

^

i=0

visible(s _i ) = c _i

The (restriction on index f of the) models of Φ _D identify the deadend states {d 1 , ..., d _k }

The bad states {b 1 , ..., b _n } are identified by the (restriction on index f of the) models of the following formula:

Φ _B

^def

= R(s _f , s _{f +1} ) ∧ visible(s _f ) = c _f ∧ visible(s _{f +1} ) = c _{f +1}

th

(74)

Identify the failure state and its deadend & bad states

The failure state is the state of maximum index f in the abstract counter-example s.t. the following formula is satisfiable:

Φ D

=

def

I(s ₀ ) ∧

f −1

^

i=0

R(s _i , s _i+1 ) ∧

f

^

i=0

visible(s _i ) = c _i

The (restriction on index f of the) models of Φ _D identify the deadend states {d 1 , ..., d _k }

The bad states {b 1 , ..., b _n } are identified by the (restriction on index f of the) models of the following formula:

Φ _B

^def

= R(s _f , s _{f +1} ) ∧ visible(s _f ) = c _f ∧ visible(s _{f +1} ) = c _{f +1}

th

(75)

Identify the failure state and its deadend & bad states

For the spurious counter-example: T 1 → T 2 → T 3 → T 4 → T 5 → T 6

Ground System

Abstract System S11

S12

S13

S21

S22

S23

S31

S32

S33

S41

S42

S43

S51

S52

S53

S61

S62

S63

T1 T2 T3 T4 T5 T6

M

M’

bad states deadend states

failure state

th

(76)

Refinement: separate deadend & bad states

The state separation problem

Input: sets D

^def

= {d ₁ , ..., d _k } and B

^def

= {b ₁ , ..., b _n } of states Output: (possibly smallest) set U ∈ I of invisible variables s.t.

∀d _i ∈ D, ∀b _j ∈ B, ∃u ∈ U s.t. d _i (u) 6= b _j (u)

=⇒ the truth values of U allow for separating each pair hd _i , b _j i

=⇒ The refinement h ⁰ is obtained by adding U to V.

th

(77)

Example

visible, invisible

x ₁ x ₂ x ₃ x ₄ x 5 x ₆ x 7

d ₁ 0 1 0 0 1 0 1

d ₂ 0 1 0 1 1 1 0

b ₁ 0 1 0 1 1 1 1

b ₂ 0 1 0 0 0 0 1

differentiating d ₁ , b ₁ : make x ₄ visible differentiating d ₁ , b ₂ : make x ₅ visible differentiating d ₂ , b ₁ : make x ₇ visible differentiating d ₂ , b ₂ : already different

=⇒ U = {x ₄ , x ₅ , x ₇ }, h ⁰ keeps only x ₆ invisible Goal: Keep U as small as possible!

th

(78)

Example

visible, invisible

x ₁ x ₂ x ₃ x ₄ x 5 x ₆ x 7

d ₁ 0 1 0 0 1 0 1

d ₂ 0 1 0 1 1 1 0

b ₁ 0 1 0 1 1 1 1

b ₂ 0 1 0 0 0 0 1

differentiating d ₁ , b ₁ : make x ₄ visible

differentiating d ₁ , b ₂ : make x ₅ visible differentiating d ₂ , b ₁ : make x ₇ visible differentiating d ₂ , b ₂ : already different

=⇒ U = {x ₄ , x ₅ , x ₇ }, h ⁰ keeps only x ₆ invisible Goal: Keep U as small as possible!

th

(79)

Example

visible, invisible

x ₁ x ₂ x ₃ x ₄ x 5 x ₆ x 7

d ₁ 0 1 0 0 1 0 1

d ₂ 0 1 0 1 1 1 0

b ₁ 0 1 0 1 1 1 1

b ₂ 0 1 0 0 0 0 1

differentiating d ₁ , b ₁ : make x ₄ visible differentiating d ₁ , b ₂ : make x ₅ visible

differentiating d ₂ , b ₁ : make x ₇ visible differentiating d ₂ , b ₂ : already different

=⇒ U = {x ₄ , x ₅ , x ₇ }, h ⁰ keeps only x ₆ invisible Goal: Keep U as small as possible!

th

(80)

Example

visible, invisible

x ₁ x ₂ x ₃ x ₄ x 5 x ₆ x 7

d ₁ 0 1 0 0 1 0 1

d ₂ 0 1 0 1 1 1 0

b ₁ 0 1 0 1 1 1 1

b ₂ 0 1 0 0 0 0 1

differentiating d ₁ , b ₁ : make x ₄ visible differentiating d ₁ , b ₂ : make x ₅ visible differentiating d ₂ , b ₁ : make x ₇ visible

differentiating d ₂ , b ₂ : already different

=⇒ U = {x ₄ , x ₅ , x ₇ }, h ⁰ keeps only x ₆ invisible Goal: Keep U as small as possible!

th

(81)

Example

visible, invisible

x ₁ x ₂ x ₃ x ₄ x 5 x ₆ x 7

d ₁ 0 1 0 0 1 0 1

d ₂ 0 1 0 1 1 1 0

b ₁ 0 1 0 1 1 1 1

b ₂ 0 1 0 0 0 0 1

differentiating d ₁ , b ₁ : make x ₄ visible differentiating d ₁ , b ₂ : make x ₅ visible differentiating d ₂ , b ₁ : make x ₇ visible differentiating d ₂ , b ₂ : already different

=⇒ U = {x ₄ , x ₅ , x ₇ }, h ⁰ keeps only x ₆ invisible Goal: Keep U as small as possible!

th

(82)

Example

visible, invisible

x ₁ x ₂ x ₃ x ₄ x 5 x ₆ x 7

d ₁ 0 1 0 0 1 0 1

d ₂ 0 1 0 1 1 1 0

b ₁ 0 1 0 1 1 1 1

b ₂ 0 1 0 0 0 0 1

differentiating d ₁ , b ₁ : make x ₄ visible differentiating d ₁ , b ₂ : make x ₅ visible differentiating d ₂ , b ₁ : make x ₇ visible differentiating d ₂ , b ₂ : already different

=⇒ U = {x ₄ , x ₅ , x ₇ }, h ⁰ keeps only x ₆ invisible

Goal: Keep U as small as possible!

th

(83)

Example

visible, invisible

x ₁ x ₂ x ₃ x ₄ x 5 x ₆ x 7

d ₁ 0 1 0 0 1 0 1

d ₂ 0 1 0 1 1 1 0

b ₁ 0 1 0 1 1 1 1

b ₂ 0 1 0 0 0 0 1

differentiating d ₁ , b ₁ : make x ₄ visible differentiating d ₁ , b ₂ : make x ₅ visible differentiating d ₂ , b ₁ : make x ₇ visible differentiating d ₂ , b ₂ : already different

=⇒ U = {x ₄ , x ₅ , x ₇ }, h ⁰ keeps only x ₆ invisible Goal: Keep U as small as possible!

th

(84)

Two separation methods

Separation based on Decision-Tree Learning Not optimal.

Polynomial.

ILP-based separation Minimal separating set.

Computationally expensive.

th

(85)

Separation with decision tree (Example)

Idea: expand the decision tree until no hd _i , b _j i pair belongs to set.

x ₁ x ₂ x ₃ x ₄ x 5 x ₆ x 7

d ₁ 0 1 0 0 1 0 1

d ₂ 0 1 0 1 1 1 0

b ₁ 0 1 0 1 1 1 1

b ₂ 0 1 0 0 0 0 1

{d 1 , d 2 , b 1 , b 2 }

differentiating d ₁ , b ₁ : x ₄ differentiating d ₁ , b ₂ : x 5

differentiating d ₂ , b ₁ : x 7

=⇒ U = {x ₄ , x ₅ , x ₇ }

th

(86)

Separation with decision tree (Example)

Idea: expand the decision tree until no hd _i , b _j i pair belongs to set.

x ₁ x ₂ x ₃ x ₄ x 5 x ₆ x 7

d ₁ 0 1 0 0 1 0 1

d ₂ 0 1 0 1 1 1 0

b ₁ 0 1 0 1 1 1 1

b ₂ 0 1 0 0 0 0 1

0 x 4 1

{d 1 , b 2 } {d 2 , b ₁ } {d 1 , d 2 , b 1 , b 2 }

differentiating d ₁ , b ₁ : x ₄

differentiating d ₁ , b ₂ : x 5

differentiating d ₂ , b ₁ : x 7

=⇒ U = {x ₄ , x ₅ , x ₇ }

th

(87)

Separation with decision tree (Example)

Idea: expand the decision tree until no hd _i , b _j i pair belongs to set.

x ₁ x ₂ x ₃ x ₄ x ₅ x ₆ x ₇

d ₁ 0 1 0 0 1 0 1

d ₂ 0 1 0 1 1 1 0

b ₁ 0 1 0 1 1 1 1

b ₂ 0 1 0 0 0 0 1

0 1

x 5

B

{b 2 } {d 1 } D

x ₄

{d 1 , b 2 } {d 2 , b 1 } {d 1 , d 2 , b 1 , b 2 }

differentiating d ₁ , b ₁ : x ₄ differentiating d ₁ , b ₂ : x ₅

differentiating d ₂ , b ₁ : x ₇

=⇒ U = {x ₄ , x ₅ , x ₇ }

th

(88)

Separation with decision tree (Example)

Idea: expand the decision tree until no hd _i , b _j i pair belongs to set.

x ₁ x ₂ x ₃ x ₄ x ₅ x ₆ x ₇

d ₁ 0 1 0 0 1 0 1

d ₂ 0 1 0 1 1 1 0

b ₁ 0 1 0 1 1 1 1

b ₂ 0 1 0 0 0 0 1

0 1

x 7

D {d 2 }

B {b 1 } x 5

B

{b 2 } {d 1 } D

x ₄

{d 1 , b 2 } {d 2 , b 1 } {d 1 , d 2 , b 1 , b 2 }

differentiating d ₁ , b ₁ : x ₄ differentiating d ₁ , b ₂ : x ₅ differentiating d ₂ , b ₁ : x ₇

=⇒ U = {x ₄ , x ₅ , x ₇ }

th

(89)

Separation with 0-1 ILP

Idea

Encode the problem as a 0-1 ILP problem min X

x

_k

∈I

v _k , subject to : X

xk ∈I

d (x

k

)6=b(x

k

)

v _k ≥ 1 ∀d ∈ D, ∀b ∈ B,

intuition: v _k = > iff x _k must me made visible one constraint for every pair hd _i , b _j i

th

(90)

Separation with 0-1 ILP: Example

x ₁ x ₂ x ₃ x ₄ x 5 x ₆ x 7

d ₁ 0 1 0 0 1 0 1

d ₂ 0 1 0 1 1 1 0

b ₁ 0 1 0 1 1 1 1

b ₂ 0 1 0 0 0 0 1

min {v ₄ + v ₅ + v ₆ + v ₇ } subject to :



 



 



v ₄ + v ₆ ≥ 1 // separating d 1 , b ₁ v 5 ≥ 1 // separating d ₁ , b ₂ v ₇ ≥ 1 // separating d ₂ , b ₁ v ₄ + v ₅ + v ₆ + v ₇ ≥ 1 // separating d 2 , b ₂

=⇒ return {v ₄ , v ₅ , v ₇ } =⇒ U = {x 4 , x ₅ , x ₇ } or return {v 5 , v ₆ , v 7 } =⇒ U = {x 5 , x ₆ , x 7 }

th

(91)

Separation with 0-1 ILP: Example

x ₁ x ₂ x ₃ x ₄ x 5 x ₆ x 7

d ₁ 0 1 0 0 1 0 1

d ₂ 0 1 0 1 1 1 0

b ₁ 0 1 0 1 1 1 1

b ₂ 0 1 0 0 0 0 1

min {v ₄ + v ₅ + v ₆ + v ₇ } subject to :



 



 



v ₄ + v ₆ ≥ 1 // separating d 1 , b ₁ v 5 ≥ 1 // separating d ₁ , b ₂ v ₇ ≥ 1 // separating d ₂ , b ₁ v ₄ + v ₅ + v ₆ + v ₇ ≥ 1 // separating d 2 , b ₂

=⇒ return {v ₄ , v 5 , v 7 } =⇒ U = {x ₄ , x 5 , x 7 }

or return {v 5 , v ₆ , v 7 } =⇒ U = {x 5 , x ₆ , x 7 }

th