Complete Abstractions Everywhere

Complete Abstractions Everywhere

Francesco Ranzato

University of Padova, Italy

Claims

Ubiquityof completeness properties of static analyses Completeness can be abeneficial toolfor

designing new static analyses

understanding how existing static analyses work

Setting

Static analyses are designed inabstract interpretation Abstract domains

Abstract functions

Static analyses must besound

Static analyses may be (covertly)complete

Approximation

Static analysisJP K

]must be a soundapproximationof concrete semanticsJP K

Approximation bypartial orders JP K ranges in (D, ≤D) JP K

]ranges in some abstraction (A, ≤_A) x ≤ y : y approximates x

Soundness

Soundness #1 JP Kγ (input

]) ≤_Dγ JP K

]input^]
Concretization γ : A → D

Soundness #2 α JP Kinput ) ≤A JP K

]α(input) Abstraction α : D → A

Completeness

–JP K

]

1andJP K

]

2on a common abstraction A – “more precise than”: JP K

]

1input^]≤_A JP K

] 2input^] Completeness means “as precise as possible”

Completeness #1 ⇒Exactness JP Kγ (input

]) = γ JP K

]input^]

Completeness #2 ⇒Completeness α JP Kinput ) = JP K

]α(input)

Numerical Abstractions

Sign abstraction

x y

•

•

•

•

Int interval abstraction

x y

•

•

•

•

Oct octagon abstraction

x y

•

•

•

•

Polyhedra abstraction

x y

•

•

•

•

Example

Sign

0 Z≤0 Z≥0

Z P ≡if (∗) {x - -; y ++;}

input , {(x/1, y/3), (x/4, y/0)}

input^Sign, αSign(input) = (x /Z≥0,y /Z≥0)

Example

P ≡if (∗) {x - -; y ++;}

x y

•

•

input^Sign

⇒

x y

JP Kinput

Sign

⇓

x y

JP K

Signinput^Sign

Example

Sign

0 Z≤0 Z≥0

Z P ≡if (∗) {x - -; y ++;}

input , {(x/1, y/3), (x/4, y/0)}

input^Sign, αSign(input) = (x /Z≥0,y /Z≥0) Sign is not exact

JP Kinput

Sign = (x /Z≥−1,y /Z≥0) JP K

Signinput^Sign= (x /Z, y/Z≥0)

Example

P ≡if (∗) {x - -; y ++;}

x y

input

•

•

⇒

x y

•

•

•

•

αSign(JP Kinput )

⇓

x y

•

•

JP K

SignαSign(input)

Example

Sign

0 Z≤0 Z≥0

Z P ≡if (∗) {x - -; y ++;}

input , {(x/1, y/3), (x/4, y/0)}

input^Sign, αSign(input) = (x /Z≥0,y /Z≥0) Sign is not exact

JP Kinput

Sign = (x /Z≥−1,y /Z≥0) JP K

Signinput^Sign= (x /Z, y/Z≥0)

Sign is not complete

α_Sign(JP Kinput ) = (x /Z≥0,y /Z≥0) JP K

Signα_Sign(input) = (x /Z, y/Z≥0)

Example

Interval domain Int

P ≡if (∗) {x - -; y ++;}

input , {(x/1, y/3), (x/4, y/0)}

input^Int, αInt(input) = (x /[1, 4], y /[0, 3])

Example

P ≡if (∗) {x - -; y ++;}

x y

•

•

input^Int

⇒

x y

JP Kinput

Int

⇓

x y

JP K

Intinput^Int

Example

Interval domain Int

P ≡if (∗) {x - -; y ++;}

input , {(x/1, y/3), (x/4, y/0)}

input^Int, αInt(input) = (x /[1, 4], y /[0, 3]) Int is not exact

JP Kinput

Int = (x /[0, 4], y /[0, 4]) r {(x/0, y/0), (x/4, y/4)}

JP K

Intinput^Int = (x /[0, 4], y /[0, 4])

Example

P ≡if (∗) {x - -; y ++;}

x y

input

•

•

⇒

x y

•

•

•

•

αInt(JP Kinput )

⇓

x y

•

•

JP K

IntαInt(input)

Example

Interval domain Int

P ≡if (∗) {x - -; y ++;}

input , {(x/1, y/3), (x/4, y/0)}

input^Int, αInt(input) = (x /[1, 4], y /[0, 3]) Int is not exact

JP Kinput

Int = (x /[0, 4], y /[0, 4]) r {(x/0, y/0), (x/4, y/4)}

JP K

Intinput^Int = (x /[0, 4], y /[0, 4]) Int is complete

α_Int(JP Kinput ) = (x /[0, 4], y /[0, 4]) JP K

Intα_Int(input) = (x /[0, 4], y /[0, 4])

Example

Octagon domain Oct

P ≡if (∗) {x - -; y ++;}

input , {(x/1, y/3), (x/4, y/0)}

input^Oct, αOct(input) = {x + y = 4, x ∈ [1, 4], y ∈ [0, 3]}

Example

P ≡if (∗) {x - -; y ++;}

x y

input^Oct

•

•

⇒

x y

•

•

•

•

JP Kinput

Oct

⇓

x y

•

•

•

•

JP K

Octinput^Oct

Example

Octagon domain Oct

P ≡if (∗) {x - -; y ++;}

input , {(x/1, y/3), (x/4, y/0)}

input^Oct, αOct(input) = {x + y = 4, x ∈ [1, 4], y ∈ [0, 3]}

Oct is exact JP Kinput

Oct= {x + y = 4, x ∈ [0, 4], y ∈ [0, 4]}

JP K

Octinput^Oct= {x + y = 4, x ∈ [0, 4], y ∈ [0, 4]}

Example

P ≡if (∗) {x - -; y ++;}

x y

input

•

•

⇒

x y

•

•

•

•

αOct(JP Kinput )

⇓

x y

•

•

•

•

JP K

OctαOct(input)

Example

Octagon domain Oct

P ≡if (∗) {x - -; y ++;}

input , {(x/1, y/3), (x/4, y/0)}

input^Oct, αOct(input) = {x + y = 4, x ∈ [1, 4], y ∈ [0, 3]}

Oct is exact JP Kinput

Oct= {x + y = 4, x ∈ [0, 4], y ∈ [0, 4]}

JP K

Octinput^Oct= {x + y = 4, x ∈ [0, 4], y ∈ [0, 4]}

Oct is complete

α_Oct(JP Kinput ) = {x + y = 4, x ∈ [0, 4], y ∈ [0, 4]}

JP K

Octα_Oct(input) = {x + y = 4, x ∈ [0, 4], y ∈ [0, 4]}

Questions and Claims

Why to care about completeness/exactness?

⇒ Completeness allow to understand abstractionsin depth

Is completeness/exactness a kind of incidental feature?

⇒ Complete abstractions areeverywhere

Why completeness/exactness shoud be a useful tool?

⇒ Completeness-drivendesignof abstractions

Definitions

Definition

Exactness: Sem ◦γ = γ ◦ Analysis

Definition

Completeness:α ◦Sem = Analysis ◦α

Assumption

Abstractions have both α and γ, i.e. are Galois connections

Completeness is a Property of Abstractions

Complete/exact abstractions are necessarily best correct approximations

Fact

Analysis isexacton A ⇔

1 Analysis =α ◦Sem ◦γ

2 Sem ◦γ = γ ◦ α Sem ◦γ Fact

Analysis iscompleteon A ⇔

1 Analysis =α ◦Sem ◦γ

2 α ◦Sem = α ◦ Sem ◦γ ◦ α

Completeness is a Property of Abstractions

Definition

Abstraction A is exact for Sem ⇔ Sem ◦γ = γ ◦ α Sem ◦γ

Definition

Abstraction A is complete for Sem ⇔ α ◦ Sem = α ◦ Sem ◦γ ◦ α

Scenario

Programs with n integer variables (n = 1, 2 in examples) Program states in Zⁿ

Program properties in h℘(Zⁿ), ⊆i

P₁is approximated by P₂: P₁⊆ P₂(i.e., P₁⇒ P₂) Standard transfer functions and collecting semantics

Scenario

Abstractions as Galois connections

Abstractions of program states in Abs(℘(Zⁿ))

A₁refines A₂: A₁E A2⇔ ∀ S.γ₁(α₁(S)) ⊆ γ₂(α₂(S)) hAbs(℘(Zⁿ)), Ei the lattice of abstractions

Trivial Abstraction

Abstracts each set in ℘(Z) to a unique abstract value A^> = {Z}

A^> isalwaystrivially exact and complete

Two-point Abstraction

{Z, K } for some K ∈ ℘(Z) Consider A⁰, {Z, {0}}

Consider the test (| x > 0? |) A⁰ is not complete

1 A⁰ (|x > 0? |){−1}
= A⁰(∅) = {0}

2 (|x > 0? |)^A0A⁰({−1}) = Z

Two-point Abstraction

A⁰ is not complete

A⁰ (|x > 0? |){−1}
= A⁰(∅) = {0}

(|x > 0? |)^A0A⁰({−1}) = Z

Where is the problem?

1 S = {−1} does not satisfy the test: (| x > 0? |)S = ∅

2 A⁰(∅) = {0}

3 A⁰(S) = Z

⇒ The abstract function on A⁰ can only tell: Z 7→ Z

Sign

Sign = {Z, Z≤0, Z≥0,0} refines A⁰

The previous problemdoes not happenwith Sign Sign is complete for the test

But...

...Sign istoo refined...

...for the specific goal of being complete for (| x > 0? |)

0 Z

0 Z≤0 Z≥0

Z

0 Z≤0

Z

Shells





 What we really need is aminimal refinementof A⁰

which is complete for (| x > 0? |)

These are calledcomplete shell refinements

Complete Shells

Minimal refinement of A which is complete for f

CShell_f(A) , t{A⁰ ∈ Abs(D) | A⁰ E A, A⁰is complete for f } Well Definedness

CShell_f(A) is complete for f Constructive Characterization

1 R_f(X ) , ∪a∈X max{d ∈ D | f (d ) ≤ a}

2 R_f^ω(A) = ∪_i∈NR_fⁱ(A)

⇒ CShell_f(A) = Glb-Closure of R_f^ω(A)

Exact Shells

Minimal refinement of A which is exact for f

EShell_f(A) , t {A⁰ ∈ Abs(D) | A⁰ E A, A⁰is exact for f } Well Definedness

EShell_f(A) is exact for f

Constructive Characterization

1 S_f(X ) , {f (x) ∈ D | x ∈ X }

2 S_f^ω(A) = ∪_i∈NS_fⁱ(A)

⇒ EShell_f(A) = Glb-Closure of S_f^ω(A)

Example

0 Z

=⇒

0 Z≤0

Z

1 max{S ∈ ℘(Z) | (| x > 0? |)S ⊆ Z} = Z

2 max{S ∈ ℘(Z) | (| x > 0? |)S ⊆ {0}} = Z≤0 3 max{S ∈ ℘(Z) | (| x > 0 |)S ⊆ Z≤0} = Z≤0

⇒ Complete shell: {Z, Z≤0, {0}}

Example

0 Z

=⇒

0 Z≤0 Z≥0

Z

Sign is the complete shell of A⁰ for (| x > 0? |) and (| x < 0? |)

Obvious?

Interesting?

⇒ Let’s go on...

Constant Propagation

∅

−1 0

· · · −2 1 2 · · ·

Z





 CP is a refinement of A⁰ 

Question

Is CP a complete shell of A⁰?

Constant Propagation

∅

−1 0

· · · −2 1 2 · · ·

Z

Observations

1 A⁰ is not complete for (| x := x ± 1 |)

2 CP is complete for any (| x := x ± k |)

3 Compositions of (| x := x ± 1 |) provide (| x := x ± k |)





 Let us compute the complete shell of A⁰ for (| x := x ± 1 |) 

Constant Propagation

∅

−1 0

· · · −2 1 2 · · ·

Z

1 maxS ∈ ℘(Z) | (|x := x + 1|)S ⊆ {0} = {−1}

2 maxS ∈ ℘(Z) | (|x := x − 1|)S ⊆ {0} = {+1}

3 maxS ∈ ℘(Z) | (|x := x ± 1|)S ⊆ {1} = {∓2}

· · · Fact

CP is the complete shell of A⁰ for additions

Uhm...

Obvious?

Maybe not at first sight!

Interesting?

Show me more!

Incompleteness of Sign

0 Z≤0 Z≥0

Z





 Sign is not complete for additions 

1 Sign((| x := x + 1 |){−1}) = Sign({0}) ={0}

2 (|x := x + 1 |)^SignSign({−1}) = (| x := x + 1 |)^Sign(Z≤0) =Z

Incompleteness of Sign

Question

What is the complete shell of Sign for additions?

Uhm...

1 I should stretch/restrict Z≥0on the left/right

2 I should restrict/stretch Z≤0on the left/right

3 If I have Z≥m and Z≤nthen I also have [m, n]

Answer Intervals!

Intervals





 Let us compute the complete shell of Sign for (| x := x ± 1 |) 

1 maxS ∈ ℘(Z) | (|x := x ± 1|)S ⊆ Z≤0 = Z≤∓1 2 maxS ∈ ℘(Z) | (|x := x ± 1|)S ⊆ Z≥0 = Z≥∓1 3 maxS ∈ ℘(Z) | (|x := x ± 1|)S ⊆ Z≤−1 = Z≤∓2

· · ·

4 Glb-closure of {Z≥n, Z≤m | n, m ∈ Z}

Fact

Int is the complete shell of Sign for additions

Uhm...

Obvious?

Probably not!

Interesting?

Not bad!

That’s the whole story?

Remark

Completeness is not monotone for abstraction refinements A1complete, A2E A16⇒ A₂complete

⇒ Completeness can be lost through shell refinements

Fact

1 Sign was designed as complete shell for (| x > 0? |) and (|x < 0? |)

2 Int was designed as complete shell of Sign for additions

⇒ Int lost completeness for (| x > 0? |) and (| x < 0? |)

Remark

Fact

Complete shell of Int for all (| x > k ? |) leads to the concrete domain

Fact

Complete shell of Int for (| x > 0? |) and (| x < 0? |) is

Int^6=±1 , Int ∪I r {+1} | I ∈ Int ∪ I r {−1} | I ∈ Int

Genesis of Octagons

Intervals are not “relational”

Need for relational abstractions Fully relational⇒ Polyhedra

Precise but expensive

Weakly relational⇒ Octagons and the like Tractable and still practically precise

Genesis of Octagons

Standard Example

{x = 4, y = 0} while x 6= 0 do {x – –; y ++} {x = 0, y = 4}

Int is not enough for deriving that y = 4 at the exit of P i.e. Int is not complete

Genesis of Octagons

Standard Example

{x = 4, y = 0} while x 6= 0 do {x – –; y ++} {x = 0, y = 4}

x y

•

•

•

widening

u

x y

=

x y

Genesis of Octagons

Standard Example

{x = 4, y = 0} while x 6= 0 do {x – –; y ++} {x = 0, y = 4}

1 Int(JP Khx /{4}, y /{0}i) = hx /[0, 0],y /[4, 4]i

2 JP K

IntInthx /{4}, y /{0}i = hx /[0, 0],y /[0, +∞)i

Genesis of Octagons

Problem

Int is not able to represent the loop invariant x + y = 4

(Logical) Solution

Oct represents sets {hx , y i ∈ Z² | x ± y = k }

Genesis of Octagons

Question

Int is already complete for (| x – – |) and (| y ++ |).

⇒ Why this is not enough?

Answer

What we really need is an abstraction that represents precisely the loop invariant x + y = 4

⇒ We needexactnessfor λ S.S ∪ (| x – –; y ++ |)S

Genesis of Octagons

Int iscompletefor λ S.S ∪ (| x – –; y ++ |)S

x y

• •

• • •

•

=

x y

• •

•

Genesis of Octagons

Int isnot exactfor λ S.S ∪ (| x – –; y ++ |)S

1 {hx/4, y /0i} ∪ (| x– –; y ++ |){hx/4, y /0i} = {hx/4, y /0i, hx/3, y /1i}

2 Int

{hx/4, y /0i} ∪ (| x– –; y ++ |){hx/4, y /0i}

3hx/4, y /1i

Octagons

Let us compute theexact shellof Int for λS.S ∪ (| x – –; y ++ |)S

λS.S ∪ (| x – –; y – – |)S λS.S ∪ (| x ++; y ++ |)S λS.S ∪ (| x ++; y – – |)S

Octagons

Let us compute theexact shellof Int for F , λ S.S ∪ (| x– –; y++ |)S Consider a generic point ha, bi:

1 F⁰({ha, bi}) = {ha, bi}

2 F¹({ha, bi}) = {ha, bi, ha − 1, b + 1i}

3 F²({ha, bi}) = {ha, bi, ha − 1, b + 1i, ha − 2, b + 2i}

· · ·

⇒ F^ω({ha, bi}) = {hx , y i | x + y = a + b, x ≤ a, y ≥ b}

Octagons

Let us compute theexact shellof Int for G , λ S.S ∪ (| x++; y++ |)S Consider a generic point ha, bi:

1 G⁰({ha, bi}) = {ha, bi}

2 G¹({ha, bi}) = {ha, bi, ha + 1, b + 1i}

3 G²({ha, bi}) = {ha, bi, ha + 1, b + 1i, ha + 2, b + 2i}

· · ·

⇒ G^ω({ha, bi}) = {hx , y i | x − y = a + b, x ≥ a, y ≥ b}

Octagons

Closure under intersections of...

1 Intervals

2 {hx, y i | x + y = a + b, x ≤ a, y ≥ b}

3 {hx, y i | x − y = a + b, x ≥ a, y ≥ b}

4 {hx, y i | x + y = a + b, x ≥ a, y ≤ b}

5 {hx, y i | x − y = a + b, x ≤ a, y ≤ b}

...generates all the octagons!

Uhm...

Obvious?

Nice observation!

Interesting?

Nice story!

And Polyhedra?

The whole story shifts from Intervals ⇒ Octagons

to

Octagons ⇒ Polyhedra

Example Program

x := x₀;y := y₀; while (∗) do {x := x + k_x; y := y + k_y} Loop invariant:k_xy − k_yx = k_xy₀− kyx₀

And Polyhedra?

Example Program

x := x₀;y := y₀; while (∗) do {x := x + kx; y := y + ky} Loop invariant:k_xy − k_yx = k_xy₀− kyx₀

Fact

Polyhedra are theexact shellof Octagons for the functions in F = {λ S.S ∪ (| x := x + k_x; y := y + k_y|)S}_hkx,kyi∈Z²

Lessons

1 Lack of precisionin analyzing P on A meanslack of completenessof A for some functions of P

2 Abstractions are designed toremedyto some (hidden)lack of completenessof a simpler abstraction

3 Complete shellsas a systematic tool for driving the design of abstractions

Model Checking

Let’s change static analysis paradigm...

Abstract Transition Systems

Concrete Model K

1

2 3

4

5 6

7

Abstract Model A

1

2 3

4

5 6

7

Preservation

Some temporal specification language L e.g., CTL, ACTL, µ-calculus

A preserves L

∀ ϕ ∈ L, ∀ s ∈ State, P(s) |=^A ϕ ⇒ s |=^Kϕ

A strongly preserves L

∀ ϕ ∈ L, ∀ s ∈ State, P(s) |=^A ϕ ⇔ s |=^Kϕ

State Space Reduction

Problem

Compute the smallest abstract space State^]_Lwhere to define an abstract model A_L = (State^]_L,

])that strongly preserves L

Reduction Algorithms

1 CTL ⇒bisimulationalgorithms

2 ACTL ⇒simulationalgorithms

3 CTL-X ⇒stuttering bisimulationalgorithms

4 ACTL-X ⇒stuttering simulationalgorithms

· · ·

Coarsest Partition Refinement

These arecoarsest partition refinementalgorithms

1

2 3

4

5 6

7

1

2 3

4

5 6

7

1

2 3

4

5 6

7

1

2 3

4

5 6

7

Bisimulation

A state partition P is a bisimulation

⇔ the abstract model hP,

∃i strongly preserves CTL

1

2 3

4

5 6

7

B₁

∃B₂iff ∃ s_i ∈ B_i s.t. s₁
s2

Partition Abstractions

State partitions can be viewed as abstractions of ℘(State) that are exact for the complementation State rS

1

2 3

4

5 6

7 1

2 3

4

5 6

7 1

2 3

4

5 6

7 1

2 3

4

5 6

7 1

2 3

4

5 6

7

Bisimulation

1 A state partition P is a bisimulation ⇔ the abstract model hP,

∃i strongly preserves CTL

2 State partitions are abstractions of ℘(State)

3 Predecessor pre : ℘(State) → ℘(State) is defined as pre(T ) , {s ∈ State | s
t , t ∈ T }

Exactness

P is a bisimulation ⇔ P isexactfor pre

1

2 3

4

5 6

7

P is exact for pre:

for any block B, pre(B) is a union of blocks of P

Exactness

P is a bisimulation ⇔ P as abstraction isexactfor pre

1

2 3

4

5 6

7

P is not exact for pre:

pre([5, 7]) ={2, 3, 4, 5, 7}is not a union of blocks of P

Exact Shell

Fact

Bisimulation algorithms are exact shells of abstractions for:

1 complementation ⇒ ensures that abstractions are partitions

2 predecessor ⇒ ensures that partitions are bisimulations

Exact Shell

1

2 3

4

5 6

7

P ⇒ Glb-Closure of P ∪ {pre([6])}

1

2 3

4

5 6

7

P ⇒ Glb-Closure of P ∪ {pre([3, 4])}

1

2 3

4

5 6

7

P ⇒ Glb-Closure of P ∪ {pre([5, 7])}

1

2 3

4

5 6

7

Fixpoint ⇒ Exact Shell

Uhm...

Obvious?

Nice observation!

Interesting?

Nice story!

Tell me more!

More...

The whole story shifts from bisimulation to

1 simulation

2 stuttering bisimulation/simulation

3 generic temporal languages

4 bisimulation/simulation inprobabilisticautomata

Simulation

A state preorder R is a simulation

⇔

∀ s ∈ State, pre(R(s)) is a union of some R(t)

1

2 3

4

5 6

7

R(1) = {1, 2}

R(2) = {1, 2}

R(3) = {3, 4}

R(4) = {3, 4}

R(5) = {1, 2, 3, 4, 5, 7}

R(6) = {6}

R(7) = {1, 2, 3, 4, 5, 7}

1

2 3

4

5 6

7

pre(R(1)) = pre(R(2)) = ∅ pre(R(3)) = pre(R(4)) = {1, 2}

pre(R(5)) = pre(R(7)) = {1, 2, 3, 4, 5, 7}

pre(R(6)) = {3, 4}

Preorder Abstractions

State preorders can be viewed as abstractions of ℘(State) that are exact for the union, i.e., closed under unions

1

2 3

4

5 6

7

1

2 3

4

5 6

7

1

2 3

4

5 6

7

1

2 3

4

5 6

7

1

2 3

4

5 6

7

Exactness

R is a simulation ⇔ R as abstraction isexactfor pre

1

2 3

4

5 6

7

R is exact for pre:

for any R(s), pre(R(s)) is a union of some R(t)

Exactness

R is a simulation ⇔ R as abstraction isexactfor pre

1

2 3

4

5 6

7 1

2

R is not exact for pre:

pre({3, 4}) ={1, 2}is not a union of R(t)

Exact Shell

Fact

Simulation algorithms are exact shells of abstractions for:

1 union ⇒ ensures that abstractions are preorders

2 predecessor ⇒ ensures that preorders are simulations

Exact Shell

1

2 3

4

5 6

7

R ⇒ Glb-Closure of R ∪ {pre({6})}

1

2 3

4

5 6

7

R ⇒ Glb-Closure of R ∪ {pre([3, 4])}

1

2 3

4

5 6

7

Fixpoint ⇒ Exact Shell

Conclusions

Initial claims:

1 Ubiquityof completeness properties of static analyses Numerical abstractions

Abstract model checking Probabilistic systems

...interpolation, non-interference, obfuscation,...

Just ask and you get it!

2 Completeness as a tool fordesigningnew static analyses When designing an abstraction, thinka prioriabout its completeness properties

3 Completeness as a tool forunderstandinghow existing static analyses work

Otherwise, completeness can explaina posteriorithe genesis of your abstraction