• Non ci sono risultati.

Introduction to Formal Methods Chapter 10: Abstraction in Model Checking

N/A
N/A
Protected

Condividi "Introduction to Formal Methods Chapter 10: Abstraction in Model Checking"

Copied!
43
0
0

Testo completo

(1)

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 18thMay, 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

th

(2)

1

2

3

(3)

Model Checking Safety Properties: M |= AG¬BAD

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

Roberto Sebastiani Ch. 10: Abstraction in Model Checking Monday 18thMay, 2020 4 / 49

(4)

Idea: Abstraction

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

Ground System S11

S12

S13

S21

S22

S23

S31

S32

S33

S41

S42

S43

S51

S52

S53

S61

S62

S63

M

h h h h h h

(5)

Abstraction & Refinement

0

Abstraction: a (typically non-injective) map h : S 7−→ S

0 h typically a many-to-one function

0

S

0

def

0

th

(6)

Simulation and Bisimulation

1def

1

1

1

1

1

2

def

2

2

2

2

2

1

2

1

2

2

2

1

1

1

2

1

2

i ∈ p:

for every hs2,t2i ∈ R2, exists hs1,t1i ∈ R1s.t. ht1,t2i ∈ p

2

1

1

2

1

2

0

(7)

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’

th

(8)

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

(9)

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

th

(10)

Existential Abstraction (Over-Approximation)

0

simulates M

Ground System S11

S12

S13

S21

S22

S23

S31

S32

S33

S41

S42

S43

S51

S52

S53

S61

S62

S63

M

(11)

0

0

0

th

(12)

Universal Abstraction (Under-Approximation)

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

0

Ground System S11

S12

S13

S21

S22

S23

S31

S32

S33

S41

S42

S43

S51

S52

S53

S61

S62

S63

M

h h h h h h

(13)

Model Checking with Universal Abstractions

0

0

0

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

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

th

(14)

Bisimulation Abstraction

0

0

simulates M

Ground System S11

S12

S13

S21

S22

S23

S31

S32

S33

S41

S42

S43

S51

S52

S53

S61

S62

S63

M

h h h h h h

(15)

0

0

0

th

(16)

(17)

th

(18)

(19)

A Popular Abstraction for Symbolic MC of AG¬BAD I

Partition Boolean variables into visible (V) and invisible (I) ones

The abstract model built on visible variables only.

All variables occurring in “¬BAD” must be visible

1

2

3

4

11

12

13

14

1

th

(20)

1

1

1

2

3

4

2

2

1

2

3

4

3

3

1

2

3

4

4

4

1

2

3

4

1

1

1

2

3

4

2

2

1

2

3

4

3

4

0

(21)

th

(22)

(23)

Checking the Abstract Counter-Example I

0

m

counter-example in the abstract space

Note: each ci is a truth assignment on thevisiblevariables

0

m

i

i

th

(24)

def

0

m−1

i=0

i

i+1

m

i=0

i

i

def

0

m−1

i

i+1

m

i

(25)

th

(26)

(27)

th

(28)

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’

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

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

Ground System S11

S12

S13

S21

S22

S23

S31

S32

S33

S41

S42

S43

S51

S52

S53

S61

S62

S63

Roberto Sebastiani Ch. 10: Abstraction in Model Checking Monday 18thMay, 2020 33 / 49

(29)

The cause of spurious counter-examples III

th

(30)

D

def

0

f −1

i=0

i

i+1

f

i=0

i

i

D

1

k

1

n

def

(31)

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

(32)

def

1

k

def

1

n

i

j

i

j

i

j

0

(33)

Example

1

2

3

4

5

6

7

1

2

1

2

1

2

3

4

5

6

7

1

2

1

2

1

2

3

4

5

6

7

1

2

1

2

1

2

3

4

5

6

7

1

2

1

2

1

1

4

1

2

5

2

1

7

2

2

4

5

7

0

6

invisible Goal: Keep U as small as possible!

Roberto Sebastiani Ch. 10: Abstraction in Model Checking Monday 18thMay, 2020 38 / 49

(34)

Two separation methods

Not optimal.

Polynomial.

ILP-based separation

Minimal separating set.

Computationally expensive.

(35)

Separation with decision tree (Example)

i

j

1

2

3

4

5

6

7

1

2

1

2

1

2

3

4

5

6

7

1

2

1

2

1

2

3

4

5

6

7

1

2

1

2

1

2

3

4

5

6

7

1

2

1

2

1

2

1

2

4

1

2

2

1

1

2

1

2

5

2

1

4

1

2

2

1

1

2

1

2

7

2

1

5

2

1

4

1

2

2

1

1

2

1

2

1

1

4

1

2

5

2

1

7

4

5

7

}

Roberto Sebastiani Ch. 10: Abstraction in Model Checking Monday 18thMay, 2020 40 / 49

(36)

xk∈I

k

xk ∈I

d (xk)6=b(xk)

k

k

k

i

j

(37)

Separation with 0-1 ILP: Example

1

2

3

4

5

6

7

1

2

1

2

1

2

3

4

5

6

7

1

2

1

2

4

5

6

7

4

6

1

1

5

1

2

7

2

1

4

5

6

7

2

2

4

5

7

4

5

7

5

6

7

5

6

7

}

Roberto Sebastiani Ch. 10: Abstraction in Model Checking Monday 18thMay, 2020 42 / 49

(38)

Ex: Simulation

Consider the following pair of ground and abstract machines M and M0, and the abstraction α : M 7−→ M0which, for every j ∈ {1, ..., 6}, maps Sj1, Sj2, Sj3 into Tj.

Ground System S11

S12

S13

S21

S22

S23

S31

S32

S33

S41

S42

S43

S51

S52

S53

S61

S62

S63

M

(39)

0

0

0

0

0

0

th

(40)

Ex: Abstraction-based MC

Consider the following pair of ground and abstract machines M and M0, and the abstraction α : M 7−→ M0which makes the variable z invisible.

M:

MODULE main VAR

x : boolean;

y : boolean;

z : boolean;

ASSIGN

init(x) := FALSE;

init(y) := FALSE;

init(z) := TRUE;

TRANS

(next(x) <-> y) &

M0:

MODULE main VAR

x : boolean;

y : boolean;

z : boolean;

ASSIGN

init(x) := FALSE;

init(y) := FALSE;

TRANS

(next(x) <-> y) &

(41)

Ex: Abstraction-based MC [cont.]

(a) Draw the FSM’s for M and M0(n.b.: in M0only v1and v2are state variables).

[ Solution: (We label states with xyz and xy . respectively. “z = 0” and “z = 1” are comments.)

001 010 100

00. 01. 10. 11.

M

M’

z=0

z=1 z=0

z=1 z=1

z=0

z=0

z=1 ]

(b) Does M simulate M0?[ Solution: No. E.g. the M0execution looping on (00) cannot be simulated in M. ]

(c) Does M0simulate M?[ Solution: Yes ]

(d) Is α a suitable abstraction for solving the MC problem M |=G¬(v1∧ v2)?

If yes, explain why. If no, produce a spurious counter-example.

[ Solution: No, since M |=G¬(v1∧ v2)but M06|= G¬(v1∧ v2). A spurious counter-example is Cdef= (00) =⇒ (01) =⇒ (11). ]

th

(42)

Ex: Abstraction-based MC [cont.]

(e) Use the SAT-based refinement technique to show that the abstract counter-example Cdef= (00) =⇒ (01) =⇒ (11) is spurious.

[ Solution: We generate the following formula and feed it to a SAT solver:

(¬x0∧ ¬y0∧ z0) ∧ //I(x0,y0,z0) ∧

((x1↔ y0) ∧ (y1↔ z0) ∧ (z1↔ x0)) ∧ //T (x0,y0,z0,x1,y1,z1) ∧ ((x2↔ y1) ∧ (y2↔ z1) ∧ (z2↔ x1)) ∧ //T (x1,y1,z1,x2,y2,z2) ∧ (¬x0∧ ¬y0) ∧ // (visible(s0) =c0)∧

(¬x1∧ y1) ∧ // (visible(s1) =c1)∧

( x2∧ y2) // (visible(s2) =c2)

=⇒ {¬x0, ¬y0, z0, ¬x1, y1, ¬z1, x2,¬y2, ¬z2} are unit-propagated due to the first three rows

=⇒ UNSAT

(43)

Ex: Separation problem

In a counter-example-guided-abstraction-refinement model checking process using localization reduction, variables x3,x4,x5,x6,x7,x8are made invisible.

Suppose the process has identified a spurious counterexample with an abstract failure state [00], two ground deadend states d1,d2and two ground bad states b1,b2as described in the following table:

x1 x2 x3 x4 x5 x6 x7 x8

d1 0 0 0 0 0 1 1 1

d2 0 0 0 1 1 1 1 0

b1 0 0 1 1 1 1 0 1

b2 0 0 0 1 0 0 0 0

Identify a minimum-size subset of invisible variables which must be made visible in the next abstraction to avoid the above failure. Briefly explain why.

[ Solution: The minimum-size subset is {x7}. In fact, if x7is made visible, then both d1,d2are made different from both b1,b2. ]

th

Riferimenti

Documenti correlati

Although the resolution of the 3D mesh created from mul- tiple paths dataset is still too low to perform reliable archae- ological inspections, exploiting a side-capability of a

Un unico ingresso, dalla profonda strombatura, si apriva in facciata, in corrispondenza della navata centrale; alla fine dell’Ottocento, delle finestre originali rimaneva aperta

Even with their coverage under the 1964 Voting Rights Act which, among other things, provided access to the ballot in native languages, Native Americans continue to experience

Partiendo del planteamiento de que la escritura académica es una práctica situada socioculturalmente, argumentamos que esta tendencia al monolingüismo en el ámbito

Considering, in particular, the need to provide a regulatory or convention-based framework for the processing for insurance purposes of health-related personal data, in

Recent comparable data on health expenditure points to challenging times for most EU Member States’ national health systems as growth in health expenditure per capita has slowed

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

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

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

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

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

StateTable(Tran const *table, unsigned nStates, unsigned nSignals) : myTable(table) myNsignals(nSignals), myNstates(nStates) {}.