Bounded Model Checking

(1)

Bounded Model Checking

Luca Geatti

University of Udine, Italy FBK, Trento, Italy

Automatic System Verification

(2)

Introduction

(3)

Introduction

• Automatic formal verification techniques: great progress in the last decades;

• big chip or software companies have integrated them in their development or quality assurance process;

• Intel: FDIV bug, error in the floating point division instruction on some Intel®Pentium® processors.

• it costed ≈ US $475 million;

• big investment in formal verification.

1

(4)

Introduction

(5)

Introduction

1

(6)

Introduction

(7)

Introduction

1

(8)

Model Checking

The most used formal verification technique isModel Checking (MC, for short).

• the system to verify is modeled as a finite-state machine (i.e., Kripke structure) and the specification is expressed by means of a temporal logic formula;

• distinctive features:

• fully automatic;

• exhaustive;

• it generates a counterexample trace if the specification does not hold.

(9)

Model Checking

• exhaustive;

2

(10)

Model Checking

• exhaustive;

(11)

Model Checking

• exhaustive;

2

(12)

Model Checking

• exhaustive;

(13)

Linear Temporal Logic

We considerLTL model checking.

• LTL syntax:

p | ¬φ | φ1∨ φ₂ | φ₁∧ φ₂

| X φ₁ | φ₁U φ₂

| φ₁R φ₂ | F φ₁ | G φ₁

• shortcuts:

• φ₁R φ₂≡ ¬(¬φ₁U ¬φ₂),

• F φ1≡ > U φ1

• G φ₁≡ ¬ F ¬φ1

3

(14)

We considerLTL model checking.

• LTL syntax:

p | ¬φ | φ1∨ φ₂ | φ₁∧ φ₂

| X φ₁ | φ₁U φ₂

| φ₁R φ₂ | F φ₁ | G φ₁

• shortcuts:

• φ₁R φ₂≡ ¬(¬φ₁U ¬φ₂),

• F φ1≡ > U φ1

• G φ1≡ ¬ F ¬φ1

(15)

• Semantics. LTL formulas are interpreted over infinitestate sequences σ = hσ₀, σ₁, . . .i ∈ (2^Σ)^ω of sets of propositions σi ∈ 2^Σ:

σ |=_i p iff p ∈ σ_i σ |=i X φ iff σ |=i +1 φ

σ |=_i φ₁U φ₂ iff there exists j ≥ i such that σ |=_j φ₂ and σ |=_k φ₁ for all i ≤ k < j

. . .

• LTL model checking:

• decide if M, s |= φ, where M = (S, I, T , L) is a Kripke structure, s ∈ I is an initial state and φ is an LTL formula; in many contexts, you may find the notation: M, s |= Aφ;

• PSPACE-complete.

4

(16)

Classical Approach to LTL MC In order to decide if M, s |= φ:

• build the Büchi automaton AM that accepts all and only the words corresponding to computations of M;

• build the Büchi automaton A¬φ that accepts all and only the words corresponding to models of ¬φ;

• check the (non-)emptiness of the product automaton A_M× A_¬φ.

MC=universal problem, EMPTINESS= existential problem

• if L(AM× A_¬φ) 6= ∅, then M, s

?

|= φ.

M, s 6|= φ

(17)

Classical Approach to LTL MC

In order to decide if M, s |= φ:

• if L(AM× A_¬φ) 6= ∅, then M, s

?

|= φ.

M, s 6|= φ

5

(18)

• if L(AM× A_¬φ) 6= ∅, then M, s

?

|= φ.

M, s 6|= φ

(19)

• if L(AM× A_¬φ) 6= ∅, then M, s

?

|= φ.

M, s 6|= φ

5

(20)

• if L(AM× A_¬φ) 6= ∅, then M, s

?

|= φ.

M, s 6|= φ

(21)

• if L(AM× A_¬φ) 6= ∅, then M, s

?

|= φ.

M, s 6|= φ

5

(22)

State-space Explosion Problem

• the previous algorithm belongs to the class of explicit model checking algorithms:

• the Kripke Structure M is represented as a set of memory locations, pointers ecc...

• MC suffers from the state-space explosion problem: the number of states of

M = M₁× M₂× · · · × M_n is exponential in n;

• the size of system that could be verified by explicit model checkers was restricted to ≈ 10⁶ states.

(23)

6

(24)

(25)

Tackling the explosion...

Three main techniques have been proposed:

• BDD-based symbolic model checking, next lessons

• partial order reduction, next lessons :-)

• SAT-based symbolic model checking, akaBounded Model Checking.

They allowed for the verification of systems with > 10²⁰ states.

7

(26)

Tackling the explosion...

Three main techniques have been proposed:

• BDD-based symbolic model checking, next lessons

• partial order reduction, next lessons :-)

• SAT-based symbolic model checking, akaBounded Model Checking.

They allowed for the verification of systems with > 10²⁰ states.

(27)

Symbolic Transition Systems

(28)

The SAT problem

• given a Boolean formula f , establish if f is satisfiable;

• f is normally given in CNF:

f := (L_1,1∨ · · · ∨ L_1,k) ∧ · · · ∧ (L_n,1∨ · · · ∨ L_n,m) where each literal L_{i ,j} is either a variable or a negation of a variable.

• why not in DNF?

f := (L1,1∧ · · · ∧ L_1,k) ∨ · · · ∨ (Ln,1∧ · · · ∧ L_n,m)

(29)

The SAT problem

• why not in DNF?

f := (L1,1∧ · · · ∧ L_1,k) ∨ · · · ∨ (Ln,1∧ · · · ∧ L_n,m)

8

(30)

The SAT problem

• why not in DNF?

f := (L1,1∧ · · · ∧ L_1,k) ∨ · · · ∨ (Ln,1∧ · · · ∧ L_n,m)

(31)

The SAT problem

• first NP-completeproblem, but ...

• there are several efficient algorithms for solving SAT (e.g., DPLL, CDCL...) along with many heuristics (e.g., 2 watching literals, glue clauses...)

• some numbers:

• > 100^·000 variables;

• > 1^·000^·000 clauses;

9

(32)

The SAT problem

• some numbers:

• > 100^·000 variables;

• > 1^·000^·000 clauses;

(33)

The SAT problem

• some numbers:

• > 100^·000 variables;

• > 1^·000^·000 clauses;

9

(34)

Symbolic Transition Systems

Consider a (explicit) Kripke structure M = (S, I, T , L). We can give aBoolean encoding of it:

• let ¯s := {s(0), . . . , s(n)} be a set of state (Boolean) variables;

• S = {0, 1}ⁿ, i.e., a state is an assignmentto all the state variables;

with n variables we represent 2ⁿ states

• m |= f_I(s) is true iff m ∈ I

• m, m⁰ |= f_T(s, s⁰) is true iff (m, m⁰) ∈ T

• m |= f_p(s) is true iff p ∈ L(m), for all labels p ∈ RANGE (L) The corresponing symbolicKripke structure is the tuple

(¯s, f_I, f_T, {f_p₁, . . . , f_p_k}).

(35)

(¯s, f_I, f_T, {f_p₁, . . . , f_p_k}).

10

(36)

(¯s, f_I, f_T, {f_p₁, . . . , f_p_k}).

(37)

(¯s, f_I, f_T, {f_p₁, . . . , f_p_k}).

10

(38)

(¯s, f_I, f_T, {f_p₁, . . . , f_p_k}).

(39)

• m |= f_p(s) is true iff p ∈ L(m), for all labels p ∈ RANGE (L)

The corresponing symbolicKripke structure is the tuple (¯s, f_I, f_T, {f_p₁, . . . , f_p_k}).

10

(40)

(¯s, f_I, f_T, {f_p₁, . . . , f_p_k}).

(41)

• we will write simply M = (S, I, T , L), meaning asymbolic transition system

• a path (or trace) π = m0, m1, . . . is an infinite sequence of assignment to the state variables such that:

• m0|= I(s);

• mi, m⁰_{i +1}|= T (s, s⁰) holds, for all i ≥ 0.

where ¯s⁰ := {s⁰(0), . . . , s⁰(n)}.

11

(42)

Example 1

simple-example.smv

¬s(0) s(0)

(43)

Example 1 - SMV

1 MODULE main 2 VAR

3 s0 : boolean ; 4 INIT

5 ! s0 ; 6 TRANS

7 s0 <−> next ( ! s0 ) ;

13

(44)

Example - 2

modulo-4-counter.smv

¬s(1)

¬s(0)

¬s(1) s(0)

s(1)

¬s(0)

s(1) s(0)

(45)

Example 2 - SMV

1 MODULE main 2 VAR

3 s0 : boolean ; 4 s1 : boolean ; 5 INIT

6 ! s0 & ! s1 ; 7 TRANS

8 ( next ( s0 ) <−> ! s0 ) 9 &

10 ( next ( s1 ) <−> ( ( s0 & ! s1 ) | ( ! s0 & s1 ) ) ) ;

15

(46)

Bounded Model Checking

(47)

Bounded Model Checking

• recall that we can reduce M, s |= ψ to checking the emptiness of M × A¬ψ;

• the universal problem M, s |= Aψ is reduced to the existential problem M, s |= E φ, whereφ := ¬ψ;

• Bounded Model Checking(BMC) solves the problem M, s |= E φ by proceeding incrementally:

• we start with k = 0;

• check ifthere existsand execution π of M of length k that satisfies φ; encode this problem into a SAT instance and call a SAT-solver;

• if so, we have found a counterexample to ψ; if not, k++.

16

(48)

(49)

16

(50)

Loop-backs

• BMC checks only bounded/finite traces of the system;

• ...but LTL formulas are defined over infinitestate sequences;

Crucial observation:

• a finite trace can still represent an infinite state sequence, if it contains aloop-back.

k l

(51)

Loop-backs

• BMC checks only bounded/finite traces of the system;

• ...but LTL formulas are defined over infinitestate sequences;

Crucial observation:

• a finite trace can still represent an infinite state sequence, if it contains aloop-back.

k l

17

(52)

BMC

Given a finite trace π of the system M, BMC distinguishes between two cases:

• either π contains a loop-back (π is lasso-shaped): apply standard LTL semantics to check if π |= φ;

• or π is loop-free: apply bounded semantics.

(53)

k-loop, aka Lasso-Shaped Models

k l

Definition (k-loop)

A path π is a (k, l )-loop, with l ≤ k, if T (π(k), π(l )) holds and π = u · v^ω, where:

• u = π(1) . . . π(l − 1);

• v = π(l ) . . . π(k).

We call π ak-loopif there exists l ≤ k for which π is a (k, l )-loop.

If a path π is a k-loop, then we can check if π |= φ with the standard LTL semantics.

19

(54)

Bounded Semantics for LTL

k i

If π isnota k-loop, we introduce bounded semantics for LTL.

Definition (Bounded semantics for LTL)

Let k ≥ 0 and π a path that is not a k-loop. An LTL formula φ is valid along π with bound k, written π |=⁰_k φ, iff:

• π |=ⁱ_k p iff p ∈ L(π(i ))

• π |=ⁱ_k ¬p iff p 6∈ L(π(i ))

(55)

k i

• π |=ⁱ_k φ1∨ φ₂ iff π |=ⁱ_k φ1 or π |=ⁱ_k φ2

• π |=ⁱ_k φ1∧ φ₂ iff π |=ⁱ_k φ1 and π |=ⁱ_k φ2

20

(56)

i k

• π |=ⁱ_k X φ₁ iff i < k and π |=^{i +1}_k φ₁

• π |=ⁱ_k φ₁U φ₂ iff ∃i ≤ j ≤ k such that π |=^j_k φ₂ and

∀i ≤ n < j it holds that π |=ⁿ_k φ₁

(57)

k i

• π |=ⁱ_k G φ1 iff ???

• π |=ⁱ_k F φ1 iff ???

20

(58)

k i

• π |=ⁱ_k G φ1 is always false

• π |=ⁱ_k F φ1 iff ∃i ≤ j ≤ k such that π |=^j_k φ1

(59)

SAT-based encoding of BMC

Now we see how to reduce BMC to SAT.

• the first thing to do is to define a Boolean formula that encodes all the paths of M of length k.

Definition (Unfolding of the Transition Relation) For a Kripke structure M and k ≥ 0, we define:

JMKk := I(s₀) ∧

k−1

^

i =0

T (si, si +1)

What does a model of JMKk represent?

21

(60)

JMKk := I(s₀) ∧

k−1

^

i =0

T (si, si +1)

(61)

JMKk := I(s₀) ∧

k−1

^

i =0

T (si, si +1)

21

(62)

Encoding of the LTL formula

So far, we have seen how to encode paths of length k of the model M.

• intuitively, this corresponds to the left-hand side of the automaton AM× A_¬ψ

• now we see how to encode the right-hand side.

We have seen that BMC distinguishes between lasso-shaped (k-loop) and loop-free paths:

• we start with the encoding in case of k-loops.

(63)

22

(64)

(65)

Encoding of a loop

k l

i i

Definition (Loop Encoding) Let l ≤ k. We define:

• _lL_k := T (s_k, s_l)

• Lk := ^W^k

l =0 lLk

Definition (Successor in a Loop)

Let l , i ≤ k and π be a (k, l )-loop. We define the successor succ(i ) of i in π as:

• succ(i ) := i + 1 if i < k;

• succ(i ) := l if i = k.

23

(66)

Encoding of a loop

k l

i i

Definition (Loop Encoding) Let l ≤ k. We define:

• _lL_k := T (s_k, s_l)

• Lk := ^W^k

l =0 lLk

Definition (Successor in a Loop)

Let l , i ≤ k and π be a (k, l )-loop. We define the successor succ(i ) of i in π as:

• succ(i ) := i + 1 if i < k;

(67)

Encoding in case of Loop

k

i l i

Definition (Encoding of an LTL formula for a (k, l )-loop) Let φ be an LTL formula and l , i , k ≥ 0 such that l , i ≤ k. We define _lJφK

i

k recursively as follows:

• _lJpK

i

k := p(s_i)

• lJ¬pK

i

k := ¬p(s_i)

24

(68)

k

i l i

i

• _lJφ¹∨ φ₂K

i

k :=_lJφ¹K

i

k ∨_lJφ²K

i k

• lJφ1∧ φ₂K

i

k :=_lJφ1K

i

k ∧_lJφ2K

i k

(69)

k

i l i

i

• lJX φ1K

i

k :=_lJφ1K

succ(i ) k

• lJφ1U φ₂K

ik :=_lJφ2K

ik ∨ (_lJφ1K

ik ∧_lJφ1U φ₂K

succ(i )

k )

24

(70)

k

i l i

i

• lJG φ1K

i

k :=_lJφ1K

i

k∧_lJG φ1K

succ(i ) k

• lJF φ1K

ik :=_lJφ1K

ik ∨_lJF φ1K

succ(i ) k

(71)

Encoding in case of NO Loops

i k

Definition (Encoding of an LTL formula for a loop-free path) Let φ be an LTL formula and i , k ≥ 0. We define JφK

i

k recursively as follows:

• JφK

k+1

k := ⊥

with i ≤ k

25

(72)

i k

i

• JpK

i

k := p(s_i)

• J¬pK

i

k := ¬p(s_i) with i ≤ k

(73)

i k

i

• Jφ1∨ φ₂K

i

k :=Jφ1K

i

k∨_lJφ2K

i k

• Jφ1∧ φ₂K

i

k :=Jφ1K

i

k∧_lJφ2K

i k

with i ≤ k

25

(74)

i k

i

• JX φ1K

i

k :=Jφ1K

i +1 k

• _lJφ1U φ₂K

i

k :=_lJφ2K

i

k ∨ (_lJφ1K

i

k ∧_lJφ1U φ₂K

i +1

k )

with i ≤ k

(75)

i k

i

• _lJG φ1K

i

k :=_lJφ1K

i

k∧_lJG φ1K

i +1 k

• _lJF φ1K

i

k :=_lJφ1K

i

k ∨_lJF φ1K

i +1 k

with i ≤ k

25

(76)

Overall encoding

Definition (Overall encoding)

Let φ be an LTL formula, M be a Kripke structure and k ≥ 0:

JM , φKk := JMKk

| {z }

encoding of the machine

∧

(¬L_k ∧JφK

0k

| {z }

loop-free models

) ∨

k

_

l =0

(_lL_k ∧_lJφK

0k)

| {z }

lasso-shaped models

Theorem (Soundness)

JM, φKk is satisfiable iff M |=_k E φ.

(77)

Overall encoding

Definition (Overall encoding)

Let φ be an LTL formula, M be a Kripke structure and k ≥ 0:

JM , φKk := JMKk

| {z }

encoding of the machine

∧

(¬L_k ∧JφK

0k

| {z }

loop-free models

) ∨

k

_

l =0

(_lL_k ∧_lJφK

0k)

| {z }

lasso-shaped models

Theorem (Soundness)

JM, φKk is satisfiable iff M |=k E φ.

26

(78)

Completeness

Algorithm:

• start with k = 0

• call a SAT-solver on JM, φKk

• if it is SAT,stop; otherwise, k++.

What happens if M 6|= φ?

• the procedure doesnotterminate: BMC is not complete;

• BMC is mainly used as a bug finder, rather than as a prover.

• several techniques have been proposed to make BMC complete:

• recurrence diameter

• Simple Bounded Model Checking (SBMC)

(79)

Completeness

Algorithm:

27

(80)

Completeness

Algorithm:

(81)

Completeness

Algorithm:

27

(82)

Completeness

Algorithm:

(83)

Example

modulo-4-counter.smv

¬s(1)

¬s(0)

¬s(1) s(0)

s(1)

¬s(0)

s(1) s(0)

• φ1 := G F(s(0) ∧ s(1)) 3

• φ₂ := F G(¬s(0) ∧ ¬s(1)) 7

28

(84)

Solving LTL-SAT with BMC

LTL-SAT is the problem of establishing if, given an LTL formula φ, there exists an infinite state sequence σ such that σ |= φ.

• how can one solve LTL-SAT with BMC?

• model checking:

JMKk∧

(¬L_k ∧JφK

0k) ∨

k

_

l =0

(_lL_k∧_lJφK

0k)

• satisfiability checking

> ∧

(¬Lk ∧JφK

0 k) ∨

k

_

l =0

(lLk∧_lJφK

0 k)

(85)

• model checking:

JMKk∧

(¬L_k ∧JφK

0k) ∨

k

_

l =0

(_lL_k∧_lJφK

0k)

> ∧

(¬Lk ∧JφK

0 k) ∨

k

_

l =0

(lLk∧_lJφK

0 k)

29

(86)

• model checking:

JMKk∧

(¬L_k ∧JφK

0k) ∨

k

_

l =0

(_lL_k∧_lJφK

0k)

> ∧

(¬Lk ∧JφK

0 k) ∨

k

_

l =0

(lLk∧_lJφK

0 k)

(87)

• model checking:

JMKk∧

(¬L_k ∧JφK

0k) ∨

k

_

l =0

(_lL_k∧_lJφK

0k)

> ∧

(¬Lk ∧JφK

0 k) ∨

k

_

l =0

(lLk∧_lJφK

0 k)

29

(88)

BLACK

• we developed this tool based on the idea of bounded satisfiability checking

• BLACK = Bounded Ltl sAtisfiabilityChecKer¹

1 https://github.com/black-sat/black