IA159 Formal Verification Methods
Abstraction
Jan Strejˇcek
Department of Computer Science
Faculty of Informatics
Masaryk University
Focus and sources
Focus
principle of abstraction
exact abstractions and non-exact abstractions
predicate abstraction
CEGAR: counterexample-guided abstraction refinement
Sources
Chapter 13 of E. M. Clarke, O. Grumberg, and D. A. Peled:
Model Checking, MIT, 1999.
R. Pelánek: Reduction and Abstraction Techniques for
Model Checking, PhD thesis, FI MU, 2002.
E. M. Clarke, O. Grumberg, S. Jha, Y. Lu, H. Veith:
Counterexample-guided Abstraction Refinement, CAV
2000, LNCS 1855, Springer, 2000.
IA159 Formal Verification Methods: Abstraction 2/76
Motivation
Abstraction is probably the most important technique
for reducing the state explosion problem.
[CGP99]
Original
system
oo Verification impossible
//___________________ Properties
IA159 Formal Verification Methods: Abstraction 3/76
Motivation
Abstraction is probably the most important technique
for reducing the state explosion problem.
[CGP99]
Original
system
oo ///o/o/o/o/o/o/o/o/o Abstract
model
oo Verification // Properties
IA159 Formal Verification Methods: Abstraction 4/76
Motivation
Abstraction is probably the most important technique
for reducing the state explosion problem.
[CGP99]
Original
system
oo ///o/o/o/o/o/o/o/o/o Abstract
model
oo Verification // Properties
large finite systems −→ smaller finite systems
infinite-state systems −→ finite systems
IA159 Formal Verification Methods: Abstraction 5/76
Intuition

_^]\XYZ[x = 0
???????
_^]\XYZ[x = 3
??
_^]\XYZ[x = 1

_^]\XYZ[x = 2
__???????
IA159 Formal Verification Methods: Abstraction 6/76
Intuition

_^]\XYZ[x = 0
???????
_^]\XYZ[x = 3
??
_^]\XYZ[x = 1

_^]\XYZ[x = 2
__???????
IA159 Formal Verification Methods: Abstraction 7/76
Intuition

_^]\XYZ[x = 0
???????
_^]\XYZ[x = 3
??
_^]\XYZ[x = 1

_^]\XYZ[x = 2
__???????

_^]\XYZ[x = 0


_^]\XYZ[x > 0
MM
edbc`aMM
IA159 Formal Verification Methods: Abstraction 8/76
Intuition

_^]\XYZ[x = 0
???????
_^]\XYZ[x = 3
??
_^]\XYZ[x = 1

_^]\XYZ[x = 2
__???????

_^]\XYZ[x = 0


_^]\XYZ[x > 0
MM
edbc`aMM
equivalent with respect to F(x > 0)
nonequivalent with respect to GF(x = 0)
IA159 Formal Verification Methods: Abstraction 9/76
Simulation
Given two Kripke structures M = (S, →, S0, L) and
M = (S , → , S0, L ), we say that M simulates M, written
M ≤ M , if there exists a relation R ⊆ S × S such that:
∀s0 ∈ S0 . ∃s0 ∈ S0 : (s0, s0) ∈ R
(s, s ) ∈ R =⇒ L(s) = L (s )
(s, s ) ∈ R ∧ s → p =⇒ ∃p ∈ S : s → p ∧ (p, p ) ∈ R
IA159 Formal Verification Methods: Abstraction 10/76
Simulation
Given two Kripke structures M = (S, →, S0, L) and
M = (S , → , S0, L ), we say that M simulates M, written
M ≤ M , if there exists a relation R ⊆ S × S such that:
∀s0 ∈ S0 . ∃s0 ∈ S0 : (s0, s0) ∈ R
(s, s ) ∈ R =⇒ L(s) = L (s )
(s, s ) ∈ R ∧ s → p =⇒ ∃p ∈ S : s → p ∧ (p, p ) ∈ R
Lemma
If M ≤ M , then for every path σ = s1s2 . . . of M starting in an
initial state there is a run σ = s1s2 . . . of M starting in an initial
state and satisfying
L(s1)L(s2) . . . = L (s1)L (s2) . . . .
IA159 Formal Verification Methods: Abstraction 11/76
Relations between original and abstract systems
Original
system
M
oo M ≤ A ///o/o/o/o/o/o/o/o/o
Abstract
model
A
oo
A |= ϕ
// Property
ϕ ∈ LTL66
M |= ϕ
hh
M ≤ A =⇒ all behaviours of M are also in A
(but not vice versa)
IA159 Formal Verification Methods: Abstraction 12/76
Relations between original and abstract systems
Original
system
M
oo M ≤ A ///o/o/o/o/o/o/o/o/o
Abstract
model
A
oo
A |= ϕ
// Property
ϕ ∈ LTL66
M |= ϕ
hh
M ≤ A =⇒ all behaviours of M are also in A
(but not vice versa)
IA159 Formal Verification Methods: Abstraction 13/76
Relations between original and abstract systems
Original
system
M
oo M ≤ A ///o/o/o/o/o/o/o/o/o
Abstract
model
A
oo
A |= ϕ
// Property
ϕ ∈ LTL66
M |= ϕ
hh
M ≤ A =⇒ all behaviours of M are also in A
(but not vice versa)
IA159 Formal Verification Methods: Abstraction 14/76
Relations between original and abstract systems
Original
system
M
oo M ≤ A ///o/o/o/o/o/o/o/o/o
Abstract
model
A
oo
A |= ϕ
// Property
ϕ ∈ LTL66
???
hh
M ≤ A =⇒ all behaviours of M are also in A
(but not vice versa)
IA159 Formal Verification Methods: Abstraction 15/76
Relations between original and abstract systems
Original
system
M
oo M ≤ A ///o/o/o/o/o/o/o/o/o
Abstract
model
A
oo
A |= ϕ
// Property
ϕ ∈ LTL66
???
hh
If A has a behaviour violating ϕ (i.e. A |= ϕ), then either
1 M has this behaviour as well (i.e. M |= ϕ), or
2 M does not have this behaviour, which is then called
false positive or spurious counterexample
(M |= ϕ or M |= ϕ due to another behaviour violating ϕ).
IA159 Formal Verification Methods: Abstraction 16/76
Relations between original and abstract systems
Original
system
M
oo M ≥ A ///o/o/o/o/o/o/o/o/o
Abstract
model
A
oo
A |= ϕ
// Property
ϕ ∈ LTL66
M |= ϕ
hh
M ≥ A =⇒ all behaviours of A are also in M
(but not vice versa)
IA159 Formal Verification Methods: Abstraction 17/76
Relations between original and abstract systems
Original
system
M
oo M ≥ A ///o/o/o/o/o/o/o/o/o
Abstract
model
A
oo
A |= ϕ
// Property
ϕ ∈ LTL66
M |= ϕ
hh
M ≥ A =⇒ all behaviours of A are also in M
(but not vice versa)
IA159 Formal Verification Methods: Abstraction 18/76
Relations between original and abstract systems
Original
system
M
oo M ≥ A ///o/o/o/o/o/o/o/o/o
Abstract
model
A
oo
A |= ϕ
// Property
ϕ ∈ LTL66
M |= ϕ
hh
M ≥ A =⇒ all behaviours of A are also in M
(but not vice versa)
IA159 Formal Verification Methods: Abstraction 19/76
Relations between original and abstract systems
Original
system
M
oo M ≥ A ///o/o/o/o/o/o/o/o/o
Abstract
model
A
oo
A |= ϕ
// Property
ϕ ∈ LTL66
M |= ϕ
hh
M ≥ A =⇒ all behaviours of A are also in M
(but not vice versa)
IA159 Formal Verification Methods: Abstraction 20/76
Relations between original and abstract systems
Original
system
M
oo M ≥ A ///o/o/o/o/o/o/o/o/o
Abstract
model
A
oo
A |= ϕ
// Property
ϕ ∈ LTL66
???
hh
M ≥ A =⇒ all behaviours of A are also in M
(but not vice versa)
IA159 Formal Verification Methods: Abstraction 21/76
Relations between original and abstract systems
Original
system
M
oo M ≤ A
M ≥ A
///o/o/o/o/o/o/o/o/o
Abstract
model
A
oo
A |= ϕ
// Property
ϕ ∈ LTL66
M |= ϕ
hh
M ≤ A ≤ M =⇒ A and M have tha same behaviours
A is an exact abstraction of M
Note: A and M are bisimilar =⇒ M ≤ A ≤ M
⇐=
IA159 Formal Verification Methods: Abstraction 22/76
Relations between original and abstract systems
Original
system
M
oo M ≤ A
M ≥ A
///o/o/o/o/o/o/o/o/o
Abstract
model
A
oo
A |= ϕ
// Property
ϕ ∈ LTL66
M |= ϕ
hh
M ≤ A ≤ M =⇒ A and M have tha same behaviours
A is an exact abstraction of M
Note: A and M are bisimilar =⇒ M ≤ A ≤ M
⇐=
IA159 Formal Verification Methods: Abstraction 23/76
Relations between original and abstract systems
Original
system
M
oo M ≤ A
M ≥ A
///o/o/o/o/o/o/o/o/o
Abstract
model
A
oo
A |= ϕ
// Property
ϕ ∈ LTL66
M |= ϕ
hh
M ≤ A ≤ M =⇒ A and M have tha same behaviours
A is an exact abstraction of M
Note: A and M are bisimilar =⇒ M ≤ A ≤ M
⇐=
IA159 Formal Verification Methods: Abstraction 24/76
Relations between original and abstract systems
Original
system
M
oo M ≤ A
M ≥ A
///o/o/o/o/o/o/o/o/o
Abstract
model
A
oo
A |= ϕ
// Property
ϕ ∈ LTL66
M |= ϕ
hh
M ≤ A ≤ M =⇒ A and M have tha same behaviours
A is an exact abstraction of M
Note: A and M are bisimilar =⇒ M ≤ A ≤ M
⇐=
IA159 Formal Verification Methods: Abstraction 25/76
Relations between original and abstract systems
Original
system
M
oo M ≤ A
M ≥ A
///o/o/o/o/o/o/o/o/o
Abstract
model
A
oo
A |= ϕ
// Property
ϕ ∈ LTL66
M |= ϕ
hh
M ≤ A ≤ M =⇒ A and M have tha same behaviours
A is an exact abstraction of M
Note: A and M are bisimilar =⇒ M ≤ A ≤ M
⇐=
IA159 Formal Verification Methods: Abstraction 26/76
Relations between original and abstract systems
Original
system
M
oo M ≤ A
M ≥ A
///o/o/o/o/o/o/o/o/o
Abstract
model
A
oo
A |= ϕ
// Property
ϕ ∈ LTL66
M |= ϕ
hh
All these relations hold even for ϕ ∈ CTL∗
.
IA159 Formal Verification Methods: Abstraction 27/76
Abstraction
Exact abstractions
IA159 Formal Verification Methods: Abstraction 28/76
Cone of influence (aka dead variables)
Idea
We eliminate the variables that do not influence the variables in
the specification.
IA159 Formal Verification Methods: Abstraction 29/76
Cone of influence (aka dead variables)
let V be the set of variables appearing in specification
cone of influence C of V is the minimal set of variables
such that
V ⊆ C
if v occurs in a test affecting the control flow, then v ∈ C
if there is an assignment v := e for some v ∈ C, then all
variables occurring in the expression e are also in C
C can be computed by the source code analysis
variables that are not in C can be eliminated from the code
together with all commands they participate in
IA159 Formal Verification Methods: Abstraction 30/76
Cone of influence: example
S: v := getinput();
x := getinput();
y := 1;
z := 1;
while v > 0 do
z := z ∗ x;
x := x − 1;
y := y ∗ v;
v := v − 1;
z := z ∗ y;
E:
Specification: F(pc = E)
IA159 Formal Verification Methods: Abstraction 31/76
Cone of influence: example
S: v := getinput();
x := getinput();
y := 1;
z := 1;
while v > 0 do
z := z ∗ x;
x := x − 1;
y := y ∗ v;
v := v − 1;
z := z ∗ y;
E:
Specification: F(pc = E)
V = ∅, C = {v}
IA159 Formal Verification Methods: Abstraction 32/76
Cone of influence: example
S: v := getinput(); S: v := getinput();
x := getinput(); skip;
y := 1; skip;
z := 1; skip;
while v > 0 do while v > 0 do
z := z ∗ x; skip;
x := x − 1; skip;
y := y ∗ v; skip;
v := v − 1; v := v − 1;
z := z ∗ y; skip;
E: E:
Specification: F(pc = E)
V = ∅, C = {v}
IA159 Formal Verification Methods: Abstraction 33/76
Other exact abstractions
Symmetry reduction
in systems with more identical parallel components, their
order is not important
Equivalent values
if the set of behaviours starting in a state s is the same for
values a, b of a variable v, then the two values can be
replaced by one
applicable to larger sets of values as well
used in timed automata for timer values
IA159 Formal Verification Methods: Abstraction 34/76
Abstraction
Non-exact abstractions
IA159 Formal Verification Methods: Abstraction 35/76
Concept
We face two problems
1 to find a suitable abstract domain (i.e. a set of abstract
states) and a mapping between the original states and the
abstract ones
2 to compute a transition relation on abstract states
IA159 Formal Verification Methods: Abstraction 36/76
Finding abstract states
Abstract states are usually defined in one of the following ways:
1 for each variable x, we replace the original variable domain
Dx by an abstract domain Ax and we define a total function
hx : Dx → Ax
a state s = (v1, . . . , vm) ∈ Dx1
× . . . × Dxm given by values
of all variables corresponds to an abstract state
h(s) = (hx1
(v1), . . . , hxm (vm)) ∈ Ax1
× . . . × Axm
2 predicate abstraction - we choose a finite set
Φ = {φ1, . . . , φn} of predicates over the set of variables;
we have several choices of abstract domains
The first approach can be seen as a special case the latter one.
IA159 Formal Verification Methods: Abstraction 37/76
Popular abstract domains for integers
Sign abstraction
Ax = {a+, a−, a0}
hx (v) =



a− if v < 0
a0 if v = 0
a+ if v > 0
Parity abstraction
Ax = {ae, ao}
hx (v) =
ae if v is even
ao if v is odd
good for verification of properties related to the last bit of
binary representation
IA159 Formal Verification Methods: Abstraction 38/76
Popular abstract domains for integers
Congruence modulo an integer
hx (v) = v (mod m) for some m
nice properties:
((x mod m) + (y mod m)) mod m = x + y (mod m)
((x mod m) − (y mod m)) mod m = x − y (mod m)
((x mod m) · (y mod m)) mod m = x · y (mod m)
Representation by logarithm
hx (v) = log2(v + 1)
the number of bits needed for representation of v
good for verification of properties related to overflow
problems
IA159 Formal Verification Methods: Abstraction 39/76
Popular abstract domains for integers
Single bit abstraction
Ax = {0, 1}
hx (v) =the i-th bit of v for a fixed i
Single value abstraction
Ax = {0, 1}
hx (v) =
1 if v = c
0 otherwise
...and others
IA159 Formal Verification Methods: Abstraction 40/76
Predicate abstraction
Let Φ = {φ1, . . . , φn} be a set of predicates over the set of
variables.
Abstract domain {0, 1}n
a state s = (v1, . . . , vm) corresponds to an abstract state
given by a vector of truth values of {φ1, . . . , φn}, i.e.
h(s) = (φ1(v1, . . . , vm), . . . , φn(v1, . . . , vm)) ∈ {0, 1}n
example: φ1 = (x1 > 3) φ2 = (x1 < x2) φ3 = (x2 > 10)
s = (5, 7)
h(s) = (1, 1, 0)
not used in practice (too many transitions) =⇒ it is better
to assign a single abstract state to a set of original states
IA159 Formal Verification Methods: Abstraction 41/76
Predicate abstraction: abstracting sets of states
let b = b1, . . . , bn be a vector of bi ∈ {0, 1, ∗}
we set [b, Φ] = b1 · φ1 ∧ . . . ∧ bn · φn,
where 0 · φi = ¬φi, 1 · φi = φi, and ∗ · φi =
let X denotes the set of original states
Abstract domain 2{0,1}n
h(X) = {b ∈ {0, 1}n | ∃s ∈ X : s |= [b, Φ]}
example: φ1 = (x1 > 3) φ2 = (x1 < x2) φ3 = (x2 > 10)
X = {(5, 7), (4, 5), (2, 9)}
h(X) = {(1, 1, 0), (0, 1, 0)}
nice theoretical properties
not used in practice (this abstract domain grows too fast)
IA159 Formal Verification Methods: Abstraction 42/76
Predicate abstraction: abstracting sets of states
Abstract domain {0, 1, ∗}n (predicate-cartesian abstraction)
h(X) = min{b | ∀s ∈ X : s |= [b, Φ]},
where min means “the most specific”
example: φ1 = (x1 > 3) φ2 = (x1 < x2) φ3 = (x2 > 10)
X = {(5, 7), (4, 5), (2, 9)}
h(X) = (∗, 1, 0)
this one is used in practice
IA159 Formal Verification Methods: Abstraction 43/76
Abstract structures
Assume that
we have a Kripke structure M = (S, →, S0, L)
we have an abstract domain A and a mapping h : S → A
it holds that A = {L(s) | s ∈ S} and L = h
To achieve the last condition, we set AP to contain only
1 abstraction based on variable domains
an atomic proposition (x = a) for each a ∈ Ax
2 predicate abstraction
an atomic proposition (φi holds) for every φi
This abstraction is useful if and only if each abstract state determines
validity of AP(ϕ).
IA159 Formal Verification Methods: Abstraction 44/76
Abstract structures
Assume that
we have a Kripke structure M = (S, →, S0, L)
we have an abstract domain A and a mapping h : S → A
it holds that A = {L(s) | s ∈ S} and L = h
We define two abstract models:
Mmay = (A, →may , A0, LA), where
A0 = {L(s0) | s0 ∈ S0}
LA : A → A such that LA(a) = a
a1 →may a2 iff there exist s1, s2 ∈ S such that
L(s1) = a1, L(s2) = a2, and s1 → s2
IA159 Formal Verification Methods: Abstraction 45/76
Example Mmay
x=0
b
FF
a // x=1
a //
c
cc x=2
a //
c
aa x=3
a //
d
xx
x=4
a //
d
xx
x=5
a //
d · · ·
xx
. . .
Mmay with abstract domain {0, 1}2 generated by predicate
abstraction with predicates φ1 = (x > 0) and φ2 = (x > 2).
IA159 Formal Verification Methods: Abstraction 46/76
Example Mmay
x=0
b
FF
a // x=1
a //
c
cc x=2
a //
c
aa x=3
a //
d
xx
x=4
a //
d
xx
x=5
a //
d · · ·
xx
. . .
Mmay with abstract domain {0, 1}2 generated by predicate
abstraction with predicates φ1 = (x > 0) and φ2 = (x > 2).
(0, 0)
b
HH
a // (1, 0)
a
VV
a //
c
ff
(1, 1)
a
VV
d
vv
IA159 Formal Verification Methods: Abstraction 47/76
Abstract structures
Assume that
we have a Kripke structure M = (S, →, S0, L)
we have an abstract domain A and a mapping h : S → A
it holds that A = {L(s) | s ∈ S} and L = h
We define two abstract models:
Mmust = (A, →must , A0, LA), where
A0 = {L(s0) | s0 ∈ S0}
LA : A → A such that LA(a) = a
a1 →must a2 iff for each s1 ∈ S satisfying L(s1) = a1
there exists s2 ∈ S such that L(s2) = a2
and s1 → s2
IA159 Formal Verification Methods: Abstraction 48/76
Example Mmust
x=0
b
FF
a // x=1
a //
c
cc x=2
a //
c
aa x=3
a //
d
xx
x=4
a //
d
xx
x=5
a //
d · · ·
xx
. . .
Mmust with abstract domain {0, 1}2 generated by predicate
abstraction with predicates φ1 = (x > 0) and φ2 = (x > 2).
IA159 Formal Verification Methods: Abstraction 49/76
Example Mmust
x=0
b
FF
a // x=1
a //
c
cc x=2
a //
c
aa x=3
a //
d
xx
x=4
a //
d
xx
x=5
a //
d · · ·
xx
. . .
Mmust with abstract domain {0, 1}2 generated by predicate
abstraction with predicates φ1 = (x > 0) and φ2 = (x > 2).
(0, 0)
b
HH
a // (1, 0)
c
ff
(1, 1)
a
VV
d
vv
IA159 Formal Verification Methods: Abstraction 50/76
Relations between M, Mmust, and Mmay
Lemma
For every Kripke structure M, abstract domain A with a
mapping function h it holds:
Mmust ≤ M ≤ Mmay
IA159 Formal Verification Methods: Abstraction 51/76
Relations between M, Mmust, and Mmay
Lemma
For every Kripke structure M, abstract domain A with a
mapping function h it holds:
Mmust ≤ M ≤ Mmay
computing Mmust and Mmay requires constructing M first
(recall that M can be very large or even infinite)
we compute an under-approximation Mmust of Mmust and
an over-approximation Mmay of Mmay directly from an
implicit representation of M
it holds that Mmust ≤ Mmust ≤ M ≤ Mmay ≤ Mmay
IA159 Formal Verification Methods: Abstraction 52/76
Abstraction
Abstraction in practice
IA159 Formal Verification Methods: Abstraction 53/76
Guarded command language
Syntax
let V be a finite set of integer variable
expressions over V use standard boolean (=, <, >) and
binary (+, −, ·, . . .) operations
Act is a set of action names
model is a pair M = (V, E), where E = {t1, . . . , tm} is a
finite set of transitions of the form ti = (ai, gi, ui), where
ai ∈ Act
gi is a boolean expression over V
ui is a sequence of assignments over V
IA159 Formal Verification Methods: Abstraction 54/76
Guarded command language
Syntax
let V be a finite set of integer variable
expressions over V use standard boolean (=, <, >) and
binary (+, −, ·, . . .) operations
Act is a set of action names
model is a pair M = (V, E), where E = {t1, . . . , tm} is a
finite set of transitions of the form ti = (ai, gi, ui), where
ai ∈ Act
gi is a boolean expression over V
ui is a sequence of assignments over V
Semantics
M defines a labelled transition system where
states are valuations of variables S = 2V→Z
initial state is the zero valuation s0(v) = 0 for all v ∈ V
s
ai
→ s whenever s |= gi and s = ui (s)
IA159 Formal Verification Methods: Abstraction 55/76
Example
x=0
b
FF
a // x=1
a //
c
cc x=2
a //
c
aa x=3
a //
d
xx
x=4
a //
d
xx
x=5
a //
d · · ·
xx
. . .
implicit description in guarded command language:
V = {x}
(a, , x := x + 1)
(b, ¬(x > 0), x := 0)
(c, (x > 0) ∧ (x ≤ 2), x := 0)
(d, (x > 2), x := 0)
IA159 Formal Verification Methods: Abstraction 56/76
Abstraction in practice
we use predicate abstraction with domain {0, 1, ∗}n
given a formula ϕ with free variables from V, we set
pre(ai, ϕ) = (gi =⇒ ϕ[x/ui(x)])
we use a sound decision procedure is_valid, i.e.
is_valid(ϕ) = =⇒ ϕ is a tautology
(the procedure is_valid does not have to be complete)
IA159 Formal Verification Methods: Abstraction 57/76
Abstraction in practice
for every abstract state b ∈ {0, 1, ∗}n and for every transition
ti = (ai, gi, ui), we compute an over-approximation of a
may-successor of b under ti as
if is_valid([b, Φ] =⇒ ¬gi) then there is no successor
otherwise, the successor b is given by
bj =



1 if is_valid([b, Φ] =⇒ pre(ai, φj))
0 if is_valid([b, Φ] =⇒ pre(ai, ¬φj))
∗ otherwise
IA159 Formal Verification Methods: Abstraction 58/76
Example
bj =



1 if is_valid([b, Φ] =⇒ pre(ai, φj))
0 if is_valid([b, Φ] =⇒ pre(ai, ¬φj))
∗ otherwise
(a, , x := x + 1)
using the predicates φ1 = (x > 0), φ2 = (x > 2), we compute
the transition
(1, 0)
a
→may (1, ∗)
IA159 Formal Verification Methods: Abstraction 59/76
Example
bj =



1 if is_valid([b, Φ] =⇒ pre(ai, φj))
0 if is_valid([b, Φ] =⇒ pre(ai, ¬φj))
∗ otherwise
(a, , x := x + 1)
using the predicates φ1 = (x > 0), φ2 = (x > 2), we compute
the transition
(1, 0)
a
→may (1, ∗)
(x > 0) ∧ (x ≤ 2) =⇒ ( =⇒ (x + 1 > 0)) is true
IA159 Formal Verification Methods: Abstraction 60/76
Example
bj =



1 if is_valid([b, Φ] =⇒ pre(ai, φj))
0 if is_valid([b, Φ] =⇒ pre(ai, ¬φj))
∗ otherwise
(a, , x := x + 1)
using the predicates φ1 = (x > 0), φ2 = (x > 2), we compute
the transition
(1, 0)
a
→may (1, ∗)
(x > 0) ∧ (x ≤ 2) =⇒ ( =⇒ (x + 1 > 0)) is true
(x > 0) ∧ (x ≤ 2) =⇒ ( =⇒ (x + 1 > 2)) is not true
(x > 0) ∧ (x ≤ 2) =⇒ ( =⇒ (x + 1 ≤ 2)) is not true
IA159 Formal Verification Methods: Abstraction 61/76
Abstraction in practice
for every transition, we compute successors of all abstract
states
based on the successors, we transform the original implicit
representation of a system into a boolean program
boolean program is an implicit representation of an
over-approximation of Mmay
it uses only boolean variables b representing the validity of
abstraction predicates Φ
boolean program can be used as an input for a suitable
model checker (of finite-state systems)
IA159 Formal Verification Methods: Abstraction 62/76
Example
V = {x}
(a, , x := x + 1)
(b, ¬(x > 0), x := 0)
(c, (x > 0) ∧ (x ≤ 2), x := 0)
(d, (x > 2), x := 0)
using the predicates φ1 = (x > 0), φ2 = (x > 2), we get the
boolean program (defining an over-approximation) of Mmay
V = {b1, b2}, where b1, b2 represents validity of φ1, φ2
(a, , b1 := if b1 then 1 else ∗
b2 := if b2 then 1 else if b1 then ∗ else 0)
(b, ¬b1, b1 := 0, b2 := 0)
(c, b1 ∧ ¬b2, b1 := 0, b2 := 0)
(d, b2, b1 := 0, b2 := 0)
IA159 Formal Verification Methods: Abstraction 63/76
Example of a real NQC code and its absraction
task light_sensor_control() { task A_light_sensor_control() {
int x = 0; bool b = false;
while (true) { while (true) {
if (LIGHT > LIGHT_THRESHOLD) { if (*) {
PlaySound(SOUND_CLICK);
Wait(30);
x = x + 1; b = b ? true : * ;
} else { } else {
if (x > 2) { if (b) {
PlaySound(SOUND_UP);
ClearTimer(0);
brick = LONG; brick = LONG;
} else if (x > 0) { } else if (b ? true : *) {
PlaySound(SOUND_DOUBLE_BEEP);
ClearTimer(0);
brick = SHORT; brick = SHORT;
} }
x = 0; b = false;
} }
} }
} }
IA159 Formal Verification Methods: Abstraction 64/76
Abstraction
CEGAR: counterexample-guided abstraction refinement
IA159 Formal Verification Methods: Abstraction 65/76
Motivation
it is hard to find a small and valuable abstraction
abstraction predicates are usually provided by a user
CEGAR tries to find a suitable abstraction automatically
implemented in SLAM, BLAST, and Static Driver Verifier
(SDV)
incomplete method, but very successfull in practice
IA159 Formal Verification Methods: Abstraction 66/76
Principle
system M
((QQQQQQQ specification ϕ
AP(ϕ)vvmmmmmmm

build a new
abstract model
M (M ≤ M )

add new
abstraction
predicates
22
model check
M |= ϕ?
NO
ss YES

analyze
counterexamplespurious
VV
real

BUG!
M |= ϕ
NO BUG!
M |= ϕ
IA159 Formal Verification Methods: Abstraction 67/76
Principle
system M
((QQQQQQQ specification ϕ
AP(ϕ)vvmmmmmmm

build a new
abstract model
M (M ≤ M )

add new
abstraction
predicates
22
model check
M |= ϕ?
NO
ss YES

analyze
counterexamplespurious
VV
real

BUG!
M |= ϕ
NO BUG!
M |= ϕ
IA159 Formal Verification Methods: Abstraction 68/76
Principle
system M
((QQQQQQQ specification ϕ
AP(ϕ)vvmmmmmmm

build a new
abstract model
M (M ≤ M )

add new
abstraction
predicates
22
model check
M |= ϕ?
NO
ss YES

analyze
counterexamplespurious
VV
real

BUG!
M |= ϕ
NO BUG!
M |= ϕ
IA159 Formal Verification Methods: Abstraction 69/76
Principle
system M
((QQQQQQQ specification ϕ
AP(ϕ)vvmmmmmmm

build a new
abstract model
M (M ≤ M )

add new
abstraction
predicates
22
model check
M |= ϕ?
NO
ss YES

analyze
counterexamplespurious
VV
real

BUG!
M |= ϕ
NO BUG!
M |= ϕ
IA159 Formal Verification Methods: Abstraction 70/76
Principle
system M
((QQQQQQQ specification ϕ
AP(ϕ)vvmmmmmmm

build a new
abstract model
M (M ≤ M )

add new
abstraction
predicates
22
model check
M |= ϕ?
NO
ss YES

analyze
counterexamplespurious
VV
real

BUG!
M |= ϕ
NO BUG!
M |= ϕ
IA159 Formal Verification Methods: Abstraction 71/76
Principle
system M
((QQQQQQQ specification ϕ
AP(ϕ)vvmmmmmmm

build a new
abstract model
M (M ≤ M )

add new
abstraction
predicates
22
model check
M |= ϕ?
NO
ss YES

analyze
counterexamplespurious
VV
real

BUG!
M |= ϕ
NO BUG!
M |= ϕ
IA159 Formal Verification Methods: Abstraction 72/76
Principle
system M
((QQQQQQQ specification ϕ
AP(ϕ)vvmmmmmmm

build a new
abstract model
M (M ≤ M )

add new
abstraction
predicates
22
model check
M |= ϕ?
NO
ss YES

analyze
counterexamplespurious
VV
real

BUG!
M |= ϕ
NO BUG!
M |= ϕ
IA159 Formal Verification Methods: Abstraction 73/76
Principle
system M
((QQQQQQQ specification ϕ
AP(ϕ)vvmmmmmmm

build a new
abstract model
M (M ≤ M )

add new
abstraction
predicates
22
model check
M |= ϕ?
NO
ss YES

analyze
counterexamplespurious
VV
real

BUG!
M |= ϕ
NO BUG!
M |= ϕ
IA159 Formal Verification Methods: Abstraction 74/76
Notes
added abstraction predicates ensure that the new abstract
model M does not have the behaviour corresponding to
the spurious counterexample of the previous M
the analysis of an abstract counterexample and finding
new abstract predicates are nontrivial tasks
the method is sound but incomplete
(the algorithm can run in the cycle forever)
IA159 Formal Verification Methods: Abstraction 75/76
Coming next week
Symbolic execution
Can we perform more executions simultaneously?
Can we perform all possible executions?
Are there any modern applications of symbolic execution?
IA159 Formal Verification Methods: Abstraction 76/76