Formal Methods: Module II: Model Checking Ch. 07: SAT-Based Model Checking

(1)

Formal Methods:

Module II: Model Checking

Ch. 07: SAT-Based Model Checking

Roberto Sebastiani

DISI, Università di Trento, Italy – roberto.sebastiani@unitn.it URL: http://disi.unitn.it/rseba/DIDATTICA/fm2021/

Teaching assistant:Giuseppe Spallitta– giuseppe.spallitta@unitn.it

M.S. in Computer Science, Mathematics, & Artificial Intelligence Systems Academic year 2020-2021

last update: Thursday 6^thMay, 2021, 11:31

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, C. Tinelli, 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

(2)

Outline

1 SAT-based Model Checking: Generalities

2 Bounded Model Checking Intuitions

General Encoding Relevant Subcases An Example

Computing Upper Bounds Discussion

3 Inductive reasoning on invariants (aka “K-Induction”) K-Induction

An Example

4 Exercises

(3)

Outline

An Example

4 Exercises

(4)

SAT-based Model Checking

Key problems with BDD’s:

they can explode in space A possible alternative:

Propositional Satisfiability Checking (SAT) SAT technology is very advanced

Advantages:

reduced memory requirements

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

techniques

Various techniques:Bounded Model Checking (BMC), K-induction, Interpolant-based, IC3/PDR,...

(5)

SAT-based Model Checking

Advantages:

techniques

(6)

SAT-based Model Checking

Advantages:

techniques

(7)

SAT-based Model Checking

Advantages:

techniques

(8)

SAT-based Bounded Model Checking & K-Induction

Key Ideas:

BMC:look for counter-example paths of increasing length k

=⇒ oriented to finding bugs

K-Induction: look for an induction proofs of increasing length k

=⇒ oriented to prove correctness

BMC [resp. K-induction]: for each k , build a Boolean formula that is satisfiable [resp. unsatisfiable] iff there is a counter-example [resp. proof] of length k

can be expressed using k · |s| variables

formula construction is not subject to state explosion

satisfiability of the Boolean formulas is checked by aSAT solver can manage complex formulae on several 100K variables returns satisfying assignment (i.e., a counter-example) exploit incrementality

(9)

SAT-based Bounded Model Checking & K-Induction

Key Ideas:

(10)

SAT-based Bounded Model Checking & K-Induction

Key Ideas:

(11)

SAT-based Bounded Model Checking & K-Induction

Key Ideas:

(12)

Outline

An Example

4 Exercises

(13)

Outline

An Example

4 Exercises

(14)

Bounded Model Checking: Example

p q

1

2 3 4

p

LTL Formula: G(p → Fq)

Negated Formula (violation): F(p ∧ G¬q) k = 0:

1

p

No counter-example found.

(15)

Bounded Model Checking: Example

p q

1

2 3 4

p

1 2

p q

(16)

Bounded Model Checking: Example

p q

1

2 3 4

p

1 2 3

p q p

(17)

Bounded Model Checking: Example

p q

1

2 3 4

p

1 2 3 4

p q p

1 2 3 4

p q p

The 2nd trace is a counter-example!

(18)

Outline

An Example

4 Exercises

(19)

The problem [Biere et al, 1999]

Ingredients:

Assume states represented by an array s of n Boolean variables asystemwritten as a Kripke structureM := hI(s), R(s, s⁰)i aproperty f written as aLTL formula

an integerk ≥ 0(bound) Problem

Is there an execution path π of M of length k satisfying the temporal property f ?

M |=_k Ef

Note: f is the negation of the property in the LTL model checking problem M |= ¬f , and π is a counter-example of length k (bug).

The check is repeated for increasing values of k = 0, 1, 2, 3, ...

(20)

The problem [Biere et al, 1999]

Ingredients:

M |=_k Ef

(21)

The problem [Biere et al, 1999]

Ingredients:

M |=_k Ef

(22)

The problem [Biere et al, 1999]

Ingredients:

M |=_k Ef

(23)

The encoding

Equivalent to the satisfiability problem of a Boolean formula [[M, f ]]_k defined as follows:

[[M, f ]]_k := [[M]]_k ∧ [[f ]]_k

[[M]]_k := I(s⁰) ∧

k −1

^

i=0

R(sⁱ,sⁱ⁺¹),

[[f ]]_k := (¬

k

_

l=0

R(s^k,s^l) ∧ [[f ]]⁰_k) ∨

k

_

l=0

(R(s^k,s^l) ∧ _l[[f ]]⁰_k),

The vectors of propositional variables is replicated k+1 times s⁰, s¹, ..., s^k

[[M]]_k encodes the fact that the k -path is an execution of M [[f ]]_k encodes the fact that the k -path satisfies f

(24)

The encoding

[[M, f ]]_k := [[M]]_k ∧ [[f ]]_k

[[M]]_k := I(s⁰) ∧

k −1

^

i=0

R(sⁱ,sⁱ⁺¹),

[[f ]]_k := (¬

k

_

l=0

R(s^k,s^l) ∧ [[f ]]⁰_k) ∨

k

_

l=0

(R(s^k,s^l) ∧ _l[[f ]]⁰_k),

(25)

The encoding

[[M, f ]]_k := [[M]]_k ∧ [[f ]]_k

[[M]]_k := I(s⁰) ∧

k −1

^

i=0

R(sⁱ,sⁱ⁺¹),

[[f ]]_k := (¬

k

_

l=0

R(s^k,s^l) ∧ [[f ]]⁰_k) ∨

k

_

l=0

(R(s^k,s^l) ∧ _l[[f ]]⁰_k),

(26)

The encoding

[[M, f ]]_k := [[M]]_k ∧ [[f ]]_k

[[M]]_k := I(s⁰) ∧

k −1

^

i=0

R(sⁱ,sⁱ⁺¹),

[[f ]]_k := (¬

k

_

l=0

R(s^k,s^l) ∧ [[f ]]⁰_k) ∨

k

_

l=0

(R(s^k,s^l) ∧ _l[[f ]]⁰_k),

(27)

The Encoding [cont.]

The encoding for a formula f with k steps, [[f ]]_k is the disjunction of The constraints needed to express a model without loopback:

(¬(Wk

l=0R(s^k,s^l)) ∧ [[f ]]⁰_k)

S₀ S₁ S_l S_k−1 S_k

[[f ]]ⁱ_k, i ∈ [0, k ]: encodes the fact that f holds in sⁱ under the assumption that s⁰, ...,s^k is a no-loopback path

The constraints needed to express a given loopback, for all possible points of loopback:

Wk

l=0(R(s^k,s^l) ∧ _l[[f ]]⁰_k)

l[[f ]]ⁱ_k, i ∈ [0, k ]: encodes the fact that f holds in sⁱ under the assumption that s⁰, ...,s^k is a path with a loopback from s^k to s^l

(28)

The Encoding [cont.]

(¬(Wk

l=0R(s^k,s^l)) ∧ [[f ]]⁰_k)

Wk

l=0(R(s^k,s^l) ∧ _l[[f ]]⁰_k)

(29)

The Encoding [cont.]

(¬(Wk

l=0R(s^k,s^l)) ∧ [[f ]]⁰_k)

Wk

l=0(R(s^k,s^l) ∧ _l[[f ]]⁰_k)

(30)

The Encoding of [[f ]]

ⁱ_k

and

_l

[[f ]]

ⁱ_k

f [[f ]]ⁱ_k l[[f ]]ⁱ_k

p pi pi

¬p ¬pi ¬pi

h ∧ g [[h]]ⁱ_k∧ [[g]]ⁱ_k l[[h]]ⁱ_k∧ l[[g]]ⁱ_k h ∨ g [[h]]ⁱ_k∨ [[g]]ⁱk l[[h]]ⁱ_k∨ l[[g]]ⁱ_k Xg [[g]]ⁱ⁺¹_k if i < k

⊥ otherwise.

l[[g]]ⁱ⁺¹_k if i < k

l[[g]]^l_k otherwise.

Gg ⊥ Vk

j=min(i,l) l[[g]]^j_k Fg Wk

j=i [[g]]^j_k Wk

j=min(i,l) l[[g]]^j_k hUg Wk

j=i

[[g]]^j_k∧Vj−1 n=i [[h]]ⁿ_k

Wk j=i

l[[g]]^j_k∧Vj−1 n=i l[[h]]ⁿ_k

∨ Wi−1

j=l

l[[g]]^j_k∧Vk

n=i l[[h]]ⁿ_k∧Vj−1 n=l l[[h]]ⁿ_k hRg Wk

j=i

[[h]]^j_k∧Vj

n=i [[g]]ⁿ_k Vk

j=min(i,l) l[[g]]^j_k ∨ Wk

j=i

l[[h]]^j_k∧Vj

n=i l[[g]]ⁿ_k

∨ Wi−1

j=l

l[[h]]^j_k ∧Vk

n=i l[[g]]ⁿ_k∧Vj

n=l l[[g]]ⁿ_k

(31)

Outline

An Example

4 Exercises

(32)

Relevant Subcase: Fp (reachability)

f :=Fp, s.t. p Boolean:

is there a reachable state in which p holds?

a finite path can show that the property holds [[M, f ]]_k is:

I(s⁰) ∧

k −1

^

i=0

R(sⁱ,sⁱ⁺¹) ∧

k

_

j=0

p^j

s

₀

s

₁

s

_k−1

s

_k

−p −p −p p

Important: incremental encoding

if done for increasing value of k , then it suffices that [[M, f ]]_k is:

I(s⁰) ∧Vk −1

i=0 R(sⁱ,sⁱ⁺¹) ∧ ¬pⁱ ∧ p^k

(33)

Relevant Subcase: Fp (reachability)

I(s⁰) ∧

k −1

^

i=0

k

_

j=0

p^j

s

₀

s

₁

s

_k−1

s

_k

−p −p −p p

I(s⁰) ∧Vk −1

i=0 R(sⁱ,sⁱ⁺¹) ∧ ¬pⁱ ∧ p^k

(34)

Relevant Subcase: Fp (reachability)

I(s⁰) ∧

k −1

^

i=0

k

_

j=0

p^j

s

₀

s

₁

s

_k−1

s

_k

−p −p −p p

I(s⁰) ∧Vk −1

i=0 R(sⁱ,sⁱ⁺¹) ∧ ¬pⁱ ∧ p^k

(35)

Relevant Subcase: Fp (reachability)

I(s⁰) ∧

k −1

^

i=0

k

_

j=0

p^j

s

₀

s

₁

s

_k−1

s

_k

−p −p −p p

I(s⁰) ∧Vk −1

i=0 R(sⁱ,sⁱ⁺¹) ∧ ¬pⁱ ∧ p^k

(36)

Relevant Subcase: Gp

f :=Gp, s.t. p Boolean: is there a path where p holds forever?

We need to produce an infinite behaviour, with a finite number of transitions

We can do it by imposing that the path loops back

s₀ s₁ s_k−1 s_k

p p p p

[[M, f ]]_k is:

I(s⁰) ∧

k −1

^

i=0

k

_

l=0

R(s^k,s^l) ∧

k

^

j=0

p^j

(37)

Relevant Subcase: Gp

p p p p

[[M, f ]]_k is:

I(s⁰) ∧

k −1

^

i=0

k

_

l=0

R(s^k,s^l) ∧

k

^

j=0

p^j

(38)

Relevant Subcase: Gp

p p p p

[[M, f ]]_k is:

I(s⁰) ∧

k −1

^

i=0

k

_

l=0

R(s^k,s^l) ∧

k

^

j=0

p^j

(39)

Relevant Subcase: Gp

p p p p

[[M, f ]]_k is:

I(s⁰) ∧

k −1

^

i=0

k

_

l=0

R(s^k,s^l) ∧

k

^

j=0

p^j

(40)

Relevant Subcase: GFq (fair states)

f :=GFq, s.t. q Boolean: does q hold infinitely often?

Again, we need to produce an infinite behaviour, with a finite number of transitions

q p

[[M, f ]]_k is:

I(s⁰) ∧

k −1

^

i=0

k

_

l=0



R(s^k,s^l) ∧

k

_

j=l

q^j





(41)

Relevant Subcase: GFq (fair states)

q p

[[M, f ]]_k is:

I(s⁰) ∧

k −1

^

i=0

k

_

l=0



R(s^k,s^l) ∧

k

_

j=l

q^j





(42)

Relevant Subcase: GFq (fair states)

q p

[[M, f ]]_k is:

I(s⁰) ∧

k −1

^

i=0

k

_

l=0



R(s^k,s^l) ∧

k

_

j=l

q^j





(43)

Subcase Combination: GFq ∧ Fp (fair reachability)

f :=GFq ∧ Fp, s.t. p, q Boolean:provided that q holds infinitely often, is there a reachable state in which p holds?

q p

[[M, f ]]_k is:

I(s⁰) ∧

k −1

^

i=0

k

_

j=0

p_j∧

k

_

l=0



R(s^k,s^l) ∧

k

_

j=l

q^j





(44)

Subcase Combination: GFq ∧ Fp (fair reachability)

q p

[[M, f ]]_k is:

I(s⁰) ∧

k −1

^

i=0

k

_

j=0

p_j∧

k

_

l=0



R(s^k,s^l) ∧

k

_

j=l

q^j





(45)

Subcase Combination: GFq ∧ Fp (fair reachability)

q p

[[M, f ]]_k is:

I(s⁰) ∧

k −1

^

i=0

k

_

j=0

p_j∧

k

_

l=0



R(s^k,s^l) ∧

k

_

j=l

q^j





(46)

Outline

An Example

4 Exercises

(47)

Example: a bugged 3-bit shift register

System M:

I(x ) := ¬x [0] ∧ ¬x [1] ∧ x [2]

Correct R:R(x , x⁰) := (x⁰[0] ↔ x [1]) ∧ (x⁰[1] ↔ x [2]) ∧ (x⁰[2] ↔ 0) Bugged R:R(x , x⁰) := (x⁰[0] ↔ x [1]) ∧ (x⁰[1] ↔ x [2]) ∧ (x⁰[2] ↔1) Property: F(¬x [0] ∧ ¬x [1] ∧ ¬x [2])

BMC Problem: is there an execution π of M of length k s.t.