Formal Methods Module II: Model Checking Ch. 10: SMT-Based Model Checking

(1)

Formal Methods Module II: Model Checking

Ch. 10: SMT-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: Tuesday 1^stJune, 2021, 11:34

Copyright notice: some material (text, figures) displayed in these slides is courtesy of R. Alur, M. Benerecetti, A. Cimatti,

(2)

Outline

1 Motivations & Context

2 Background

3 SMT-Based Bounded Model Checking of Timed Systems Basic Ideas

Basic Encoding

Improved & Extended Encoding A Case-Study

4 Exercises

(3)

Outline

2 Background

Basic Encoding

4 Exercises

(4)

Motivations

Model Checking for Timed Systems:

relevant improvements and results over the last decades historically, “explicit-state” search style, based on DBMs

notable examples: Kronos,Uppaal

More recently, symbolic verification techniques:

extensions of decision diagrams CDD,DDD,RED, ...

Key problem: potential blow up in size

A more recent and viable alternative to Binary Decision Diagrams: SAT-based MC

Bounded Model Checking (BMC), K-induction, IC3/PDR, ...

(5)

Motivations

(6)

Motivations

(7)

Motivations

(8)

Context

First Idea: SMT-based BMC of Timed Systems

[Audemard et al. 2002],[Sorea, MTCS’02],[Niebert et al.,FTRTFT’02]

Leverage the SAT-based BMC approach to Timed Systems by means ofSMT Solvers

Extensions

SMT eventually applied to other SAT-based MC techniques K-Induction

interpolant-based IC3/PDR

SMT applied to a variety of domains:

hybrid systems

verification of SW (loop invariants/proof obbligations, ...) hardware verification

Nowadays SMT leading backend technology for FV

(9)

Context

Extensions

hybrid systems

(10)

Context

Extensions

hybrid systems

(11)

Context

Extensions

hybrid systems

(12)

Context

Extensions

hybrid systems

(13)

Outline

2 Background

Basic Encoding

4 Exercises

(14)

Bounded Model Checking

[Biere et al., TACAS’99]

Given a Kripke Structure M, an LTL property f and an integer bound k , is there an execution path of M of length (up to) k satisfying f ? (M |=_k Ef)

Problem converted into the satisfiability of the Boolean formula:

[[M]]^f_k :=I(s⁽⁰⁾) ∧

k −1

^

i=0

R(s⁽ⁱ⁾,s⁽ⁱ⁺¹⁾) ∧ (¬L_k ∧ [[f ]]⁰_k) ∨

k

_

l=0

(lL_k ∧ _l[[f ]]⁰_k)

s.t. _lL_k =^defR(s^{(k )},s^(l)), L_k ^def=Wk l=0 lL_k

A satisfying assignment represents a satisfying execution path.

Test repeated for increasing values of k Incomplete

Very effective for debugging, alternative to OBDDs Complemented withK-Induction[Sheeran et al. 2000]

Further developments: IC3/PDR[Bradley, VMCAI 2011]

(15)

General Encoding for LTL Formulae

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

p p⁽ⁱ⁾ p⁽ⁱ⁾

¬p ¬p⁽ⁱ⁾ ¬p⁽ⁱ⁾

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

[[h]]^j ∧Vk

[[g]]ⁿ∧Vj

[[g]]ⁿ

(16)

Timed Automata

[Alur and Dill, TCS’94; Alur, CAV’99]

T12

T21 x<=3 x>=1

x:=0 x <= 2

a

b

l1 l2

Clocks: real variables (ex. x) Locations:

label: (ex.l1),

invariants: (conjunctive) constraints on clocks values (ex.x ≤ 2) Switches:

event labels(ex.a),

clock constraints(ex.x ≥ 1), reset statements(ex. x := 0)

Time elapse: all clocks are increased by the same amount

(17)

LRA-Formulae

[Audemard et al., CADE’02]; [Sorea, MTCS’02]; [Niebert et al.,FTRTFT’02]

LRA-formulaeare Boolean combinations of Boolean variables and

linear constraints over real variables (equalities and differences) e.g.,(x − 2 · y ≥ 4) ∧ ((x = y ) ∨ ¬A)

Aninterpretation I for a LRA formula assigns truth values to Boolean variables

real values to numerical variables and constants e.g.,I(x) = 3, I(y ) = −1, I(A) = ⊥

I satisfiesa LRA-formula φ, written “I |= φ”, iff

I(φ) evaluates to true under the standard semantics of Boolean and mathematical operators.

E.g.,I((x − 2 · y ≥ 4) ∧ ((x = y ) ∨ ¬A)) = >

(18)

The M

ATH

SAT Solver

[Audemard et al., CADE’02]

Bottom level:a T -Solver for sets of LRA constraints

E.g. {..., z₁− x₁≤ 6, z₂− x₂≥ 8, x₁=x₂,z₁=z₂, ...}=⇒unsat.

Combination of symbolic and numerical algorithms (equivalence class building, Belman-Ford, Simplex) Top level: a CDCL procedure for propositional satisfiability

mathematical predicates treated as propositional atoms invokes T -Solver on every assignment found

used as an enumerator of assignments lots of enhancements

(see chapter on SMT)

(19)

Outline

2 Background

Basic Encoding

4 Exercises

(20)

Outline

2 Background

Basic Encoding

4 Exercises

(21)

SMT-Based BMC for Timed Systems

Independently developed approaches (2002):

[Audemard et al. FORTE’02]: encoding into LRA all LTL properties

[Sorea, MTCS’02]: encoding into LRA

based on automata-theoretic approach for LTL [Niebert et al.,FTRTFT’02]: encoding into DL

limited to reachability

Disclaimer

These slides are adapted from[Audemard et al. FORTE’02]: G. Audemard, A. Cimatti, A. Kornilowicz, R. Sebastiani Bounded Model Checking for Timed Systems,

proc. FORTE 2002, Springer

(22)

SMT-Based BMC for Timed Systems

Independently developed approaches (2002):

[Audemard et al. FORTE’02]: encoding into LRA all LTL properties

[Sorea, MTCS’02]: encoding into LRA

based on automata-theoretic approach for LTL [Niebert et al.,FTRTFT’02]: encoding into DL

limited to reachability

Disclaimer

These slides are adapted from[Audemard et al. FORTE’02]: G. Audemard, A. Cimatti, A. Kornilowicz, R. Sebastiani Bounded Model Checking for Timed Systems,

proc. FORTE 2002, Springer

freely available as http://eprints.biblio.unitn.it/124/

(23)

BMC for Timed Systems

Basic ingredients:

An extension of propositional logic expressive enough to represent timed information: “LRA-formulae”

ASMT(LRA) solverfor deciding LRA-formulae

=⇒e.g., theMATHSATsolver

Anencodingfrom timed BMC problems into LRA-formulae LRA-satisfiable iff an execution path within the bound exists

(24)

BMC for Timed Systems

Basic ingredients:

(25)

BMC for Timed Systems

Basic ingredients:

(26)

Outline

2 Background

Basic Encoding

4 Exercises

(27)

The encoding

Given atimed automaton Aand aLTL formula f:

The encoding [[A, f ]]_k is obtained following the same schema as in propositional BMC:

[[A, f ]]_k :=I(s⁽⁰⁾) ∧

k −1

^

i=0

R(s⁽ⁱ⁾,s⁽ⁱ⁺¹⁾) ∧ (¬L_k∧ [[f ]]⁰_k) ∨

k

_

l=0

(_lL_k∧ _l[[f ]]⁰_k)

[[M, f ]]_k is a LRA-formula, where

Boolean variables encode thediscrete partof the state of the automaton

constraints on real variables represent thetemporal partof the state

(28)

Encoding: Boolean Variables

Locations:an arraylof n^def= dlog₂(|L|)e Boolean variables li holds iff the system is in the location li

ex: “¬l_i[3] ∧ li[2] ∧ ¬li[1] ∧ li[0]” means “the system is in location l3”

“(li =lj)” stands for “V

n(li[n] ↔ lj[n])”,

“primed” variables l_i⁰ to represent location after transition Events: for each event a ∈ Σ, a Boolean variablea

a holds iff the system executes a switch with event a.

Switches: for each switch hl_i,a, ϕ, λ, l_ji ∈ E, a Boolean variableT,

T holds iff the system executes the corresponding switch Time elapse and null transitions: two variablesT_δ andT_null^j

Tδ holds iff time elapses by some δ > 0

T_null^j holds if and only A_j does nothing (specific for automaton A_j) Note: also for events, switches&transitions it is possible to use arrays of Boolean variables of size dlog (|Σ|)e, dlog (|E | + 2)e respectively

(29)

Encoding: Boolean Variables

n(li[n] ↔ lj[n])”,

T_null^j holds if and only A_j does nothing (specific for automaton A_j)

(30)

Encoding: Boolean Variables

n(li[n] ↔ lj[n])”,

(31)

Encoding: Boolean Variables

n(li[n] ↔ lj[n])”,

T_null^j holds if and only A_j does nothing (specific for automaton A_j)

(32)

Encoding: Boolean Variables

n(li[n] ↔ lj[n])”,

(33)

Encoding: Clock Values and Constraints

Clocks valuesx are “normalized” wrt absolute time(x − z):

a clock value is written as difference x − z z represents (the negation of)the absolute time

“offset” variable x represents (the negation of)the absolute time when the clock was reset

Clock constraintsreduce to(x − z ./ c), ./ ∈ {≤, ≥, <, >}, c ∈ Z Clock reset conditionsreduce to(x := z)

Clock equalities like(x_k =x_l)reduce to(x_k− zk =x_l− zl) appear only in loops

only place where full LRA is needed (rather than DL)

=⇒ for invariant checking (no loops) DL suffices Encoding theeffect of transitions:

with a time elapse transition z⁰<z, andx⁰=x otherwise:

(34)

Encoding: Clock Values and Constraints

z⁰=z, absolute time does not elapse x⁰=z⁰, if the clock is reset

(35)

Encoding: Clock Values and Constraints

(36)

Encoding: Clock Values and Constraints

(37)

Encoding: Clock Values and Constraints

(38)

Encoding: Clock Values and Constraints

(39)

Encoding: Clock Values and Constraints

(40)

Encoding: Clock Values and Constraints

(41)

Encoding: Clock Values and Constraints

(42)

Encoding: Initial Conditions

Initial condition I(s):

Initially, the automaton is in an initial location:

_

l_i∈L⁰

l_i

Initially, clocks have a null value:

^

x ∈X

(x = z)

(43)

Encoding: Initial Conditions

_

l_i∈L⁰

l_i

^

x ∈X

(x = z)

(44)

Encoding: Initial Conditions

_

l_i∈L⁰

l_i

^

x ∈X

(x = z)

(45)

Encoding: Invariants

Transition relation R(s, s⁰): Invariants

Always, being in a location implies the corresponding

constraints: ^

l_i∈L

(l_i → ^

ψ∈I(li)

ψ),

(46)

Encoding: Transitions

Transition relation T (s, s⁰):

Switches:

^

T^def= hl_i,a,ϕ,λ,l_ji∈E

T →



l_i∧ a ∧ ϕ ∧ l_j⁰∧ ^

x ∈λ

(x⁰ =z⁰) ∧ ^

x 6∈λ

(x⁰=x ) ∧ (z⁰=z)





Time elapse:

T_δ→ (z⁰− z < 0) ∧ (l⁰ =l) ∧ ^

x ∈X

(x⁰ =x ) ∧ ^

a∈Σ

¬a

!

Null transition:

T_null^j → (z⁰ =z) ∧ (l⁰ =l) ∧ ^

x ∈X

(x⁰ =x ) ∧ ^

a∈Σ

¬a

!

(47)

Encoding: Transitions

Switches:

^

T →



l_i∧ a ∧ ϕ ∧ l_j⁰∧ ^

x ∈λ

(x⁰ =z⁰) ∧ ^

x 6∈λ

(x⁰=x ) ∧ (z⁰=z)





Time elapse:

T_δ→ (z⁰− z < 0) ∧ (l⁰ =l) ∧ ^

x ∈X

(x⁰ =x ) ∧ ^

a∈Σ

¬a

!

Null transition:

T_null^j → (z⁰ =z) ∧ (l⁰ =l) ∧ ^

(x⁰ =x ) ∧ ^

¬a

!

(48)

Encoding: Transitions

Switches:

^

T →



l_i∧ a ∧ ϕ ∧ l_j⁰∧ ^

x ∈λ

(x⁰ =z⁰) ∧ ^

x 6∈λ

(x⁰=x ) ∧ (z⁰=z)





Time elapse:

T_δ→ (z⁰− z < 0) ∧ (l⁰ =l) ∧ ^

x ∈X

(x⁰ =x ) ∧ ^

a∈Σ

¬a

!

Null transition:

T_null^j → (z⁰ =z) ∧ (l⁰ =l) ∧ ^

x ∈X

(x⁰ =x ) ∧ ^

a∈Σ

¬a

!

(49)

Encoding: Transitions

Switches:

^

T →



l_i∧ a ∧ ϕ ∧ l_j⁰∧ ^

x ∈λ

(x⁰ =z⁰) ∧ ^

x 6∈λ

(x⁰=x ) ∧ (z⁰=z)





Time elapse:

T_δ→ (z⁰− z < 0) ∧ (l⁰ =l) ∧ ^

x ∈X

(x⁰ =x ) ∧ ^

a∈Σ

¬a

!

Null transition:

T_null^j → (z⁰ =z) ∧ (l⁰ =l) ∧ ^

(x⁰ =x ) ∧ ^

¬a

!

(50)

Encoding: Relations between Transitions

Mutual exclusion between events:

^

a_k,ar∈Σ,ak6=ar

(¬a_k∨ ¬a_r)

At least one transition takes place:

T_null^j ∨ T_δ∨ _

T ∈E

T

Mutual exclusion between transitions:

^

Tk,Tr ∈ E∪{T_null^j }∪{Tδ},Tk6=Tr

(¬T_k∨ ¬Tr)

If events and transitions are encoded via arrays of Booleans, mutual exclusion constraints are not needed

(51)

Encoding: Relations between Transitions

^

a_k,ar∈Σ,ak6=ar

(¬a_k∨ ¬a_r)

T ∈E

T

^

(¬T_k∨ ¬Tr)

If events and transitions are encoded via arrays of Booleans, mutual

(52)

Encoding: Relations between Transitions

^

a_k,ar∈Σ,ak6=ar

(¬a_k∨ ¬a_r)

T ∈E

T

^

(¬T_k∨ ¬Tr)

(53)

Encoding: Relations between Transitions

^

a_k,ar∈Σ,ak6=ar

(¬a_k∨ ¬a_r)

T ∈E

T

^

(¬T_k∨ ¬Tr)

If events and transitions are encoded via arrays of Booleans, mutual

(54)

Encoding: Relations between Transitions

^

a_k,ar∈Σ,ak6=ar

(¬a_k∨ ¬a_r)

T ∈E

T

^

(¬T_k∨ ¬Tr)

(55)

Automata Product Construction

The encoding is compositional wrt. product of automata The encoding of A = A₁||A₂is given by theconjunction of the encodings of A₁and A₂, plus a few extra axioms

Mutual exclusion between events that are local

^ a₁∈ Σ₁\Σ₂ a₂∈ Σ₂\Σ₁

(¬a₁∨ ¬a₂)

Forcing system activity:

N−1

_

j=0

¬T_null^j

j

(56)

Automata Product Construction

^ a₁∈ Σ₁\Σ₂ a₂∈ Σ₂\Σ₁

(¬a₁∨ ¬a₂)

N−1

_

j=0

¬T_null^j

one distinct T_null^j for each automaton Aj

Tδ is common to all automata Aj

(57)

Automata Product Construction

^ a₁∈ Σ₁\Σ₂ a₂∈ Σ₂\Σ₁

(¬a₁∨ ¬a₂)

N−1

_

j=0

¬T_null^j

j

(58)

Automata Product Construction

^ a₁∈ Σ₁\Σ₂ a₂∈ Σ₂\Σ₁

(¬a₁∨ ¬a₂)

N−1

_

j=0

¬T_null^j

one distinct T_null^j for each automaton Aj

Tδ is common to all automata Aj

(59)

A Simple Example

T12

T21 a

b

l1 l2

x:=z

x−z <= 2 x−z<=3

x−z>=1

T

z T 0

T F F

F 0.0

−1.0 T 1

F

F 0.0

−1.0 F 2

F F F T

F

−1.0

0.0 3

F F T

F −1.0

−1.0 4

0.0

0.0 STEP:

l1

x

T T T T 12 21 null δ

(60)

Outline

2 Background

Basic Encoding

4 Exercises

(61)

Encoding: Extension

Adding Global Variables

Dealing with some global variable v on discrete domain:

A switch T ^def= hl_i,a, ϕ, λ, l_ji can be subject to a condition ψ(v )

=⇒ addT → ψ(v )

assign v to some value n or keep its value

=⇒ addT → (v⁰=n)or addT → (v⁰=v ) T_δmantains the value of v :

=⇒ addTδ → (v⁰=v )

T_null^j imposes no constraint on v :

=⇒ add nothing (for Aj)

(62)

Encoding: Extension

=⇒ addTδ → (v⁰=v )

(63)

Encoding: Extension

=⇒ addTδ → (v⁰=v )

(64)

Encoding: Extension

=⇒ addTδ → (v⁰=v )

(65)

Encoding: Extension

=⇒ addTδ → (v⁰=v )

(66)

Encoding: Extension

=⇒ addTδ → (v⁰=v )

(67)

Encoding: Extension

=⇒ addTδ → (v⁰=v )

(68)

Encoding: Extension

=⇒ addTδ → (v⁰=v )

(69)

Encoding: Extension

=⇒ addTδ → (v⁰=v )

(70)

M

ATH

SAT: Optimizations

Customization of MATHSAT

Limit Boolean variable-selection heuristic to picktransition variables, in forward order