Floyd/Hoare Logic

1 2G1516/2G1521 Formal Methods2004 Mads Dam IMIT, KTH

Floyd/Hoare Logic

Literature: peled ch. 7 – 7.5

Mads Dam


Transition DiagramsTransition system specs, with explicit underlying control graph

Labelled directed graph (S,,R,si,sf):– s2 S: Control states

– = ! (x1,...,xn) := (e1,...,en) 2 : Transition specification

– Rµ S £ £ S: (Control) transition relation– s! s’: Means R(s,,s’)– s0 2 S: Initial state– sf 2 S: Final state

sf should not have outgoing edges

Generated state space has states (s,x1=v1,...,xn=vn)

ranges over data vectors (v1,...,vn)

s0

s3

s1 s2

sf

1! f1

3! f3

4! f4

2! f2

5! f5

6! f6


Floyd Inductive Assertions

Assume transition diagram P = (S,,R,si,sf)Assertion network:

Assignment N: s s of total predicates to control states in S

N is inductive if whenever

then if ² s() and ² () then ² s’[e1/x1,...,en/xn]()

Formally: ² s Æ ! (s’[e1/x1,...,en/xn])

s s’

s s’! (x1,...,xn) := (e1,...,en)


An assertion network N is invariant if for all computation paths

(s0,0) ! ... ! (si,i) ! ...

such that ² s0(0), also ² si

(i) , for any i ¸ 0

An assertion network N is consistent, or correct, w.r.t. precondition pre and postcondition post, if:

– ² pre ! s0 , and

– ² sf ! post

A transition diagram P is partially correct w.r.t. precondition pre and postcondition post if whenever ² pre(0) and

(s0,0) ! ... ! (si,i) ! ... ! (sf,f)

then ² post(f)

Partial correctness of P w.r.t. pre and post is written {pre}P{post}


Floyd’s Inductive Assertion Method

1. Give assertion network N for P

2. Prove that N is inductive, i.e. prove that whenever

then ² s Æ ! s’[e1/x1,...,en/xn]

3. Prove that N is consistent w.r.t. pre and post, i.e. that

– ² pre ! s0

– ² sf ! post

Then P is partially correct w.r.t. pre and post

s s’! (x1,...,xn) := (e1,...,en)


Inductive Assertion Method: Soundness

Theorem:If N is an inductive assertion network for P which is

consistent w.r.t. pre and post then P is partially correct w.r.t. pre and post

Lemma:If N is an inductive assertion network for P then N is

invariant for P

Proof: Induction on length of prefix (s0,0) ! ... ! (si,i)

Lemma:

If N is invariant for P and consistent w.r.t. pre and post then {pre}P{post}


Example

Procedure for computing integer square root of nonnegative integer y1, with result in y2

Integer square root: y2 s.t. y22 · y1 < (y2+1)2

(y2,y3,y4) := (0,0,1)

y3 := y3 + y4

y3 > y1

(y3 · y1) ! (y2,y4) := (y2 + 1, y4 + 2)

s0

s1

s2 sf


Example

(y2,y3,y4) := (0,0,1)

y3 := y3 + y4

y3 > y1

(y3 · y1) ! (y2,y4) := (y2 + 1, y4 + 2)

s0

s1

s2 sf

s0: y1 ¸ 0

s1: y2

2 · y1 Æ y3 = y22 Æ y4 = 2*y2 + 1

s2: y2

2 · y1 Æ y3 = (y2 + 1)2 Æ y4 = 2*y2 + 1 sf: y2

2 · y1 < (y2 + 1)2


Semantic CompletenessSoundness: Whenever {pre} P {post} is proved using the inductive

assertion method then {pre} P {post} is validCompleteness: The inductive assertion method is sufficient to derive

any valid partial correctness property {pre} P {post}

For completeness prove the existence of network N such that

² pre ! N,s0 and ² N,sf

! post

Obs: Doesn’t prove that the s are expressible in any given logic

The derived ass’n network N is minimal in the sense that if M is some other ass’n network which establishes partial correctness of P w.r.t. pre and post then N,s ! M,s for all s 2 S

In other words, {N,sj s2 S} is the set of strongest = least inclusive predicates such that {pre} P {post}

Notation: N,s = SPs(pre,P), SPsf(pre,P) = SP(pre,P)


Proof of Semantic CompletenessSuppose {pre} P {post}Define:

SPs(pre,P) = {’|9 .(s0,)!*(s,’) and ² pre()}

The assertion network N determined by

s = SPs(pre,P) is inductive:

– If ² s(), s !! f s’, and ² (s) then ² s’(f())

N is also consistent w.r.t. pre and post:– SPs0

(pre,P) = pre, so ² pre ! s0

– N is inductive, hence invariant. We assumed {pre} P {post}. But then ² SPsf

(pre,P) ! post

Since N is inductive and consistent w.r.t. pre and post the inductive assertions method applies


Strongest Postconditions

SP(,P)

= SPsf(,P)

= {’ | 9 .(s0,) !* (sf,’) and ² ()}

Lemma:1. ² {} P {SP(,P)}

2. If ² {} P {} then ² SP(,P) !

2. explains why SP(,P) is called strongest


Incompleteness

By Gödel’s incompleteness theorem no complete proof system can exist for FOL + (Peano) arithmetic

It follows that the inductive assertion method is incomplete too:

Consider P:

with specification {true} P {} such that ² Completeness would require us to prove which is not

generally possible

s0 sf

true! Id


Total CorrectnessTotal correctness = partial correctness + termination

– This terminology is from the days when programs were by default sequential and terminating

A transition diagram P is totally correct w.r.t. precondition pre and postcondition post if whenever ² pre(0) and

(s0,0) ! ... ! (si,i) 9

then si = sf for some i, and ² post(i)

Termination is about progressing towards a terminal state

Termination is proved using induction

For termination proofs need general induction principle called well-founded induction but here ordinary induction suffices


Strict Partial Orders

Strict partial order (W,Â):– Irreflexivity: For no u 2 W is u Â u– Asymmetry: For each u,v 2 W is u Â v then v ¨ u– Transitivity: For each u,v,w2 W, if u Â v Â w then u Â w

Examples:– Natural numbers (N,>) or (N,<)– Set of finite sets of integers under ¾– String under “superstring” ordering

u Â v iff v substring of u

iff exists strings v1, v2 such that u = v1.v.v2

– Strings under lexicographic ordering– Tuples under lexicographic ordering


Well-founded OrderingsStrictly decreasing chain:

– Finite or infinite sequence u1 Â u2 Â ... Â un Â ...

Well-founded ordering: Strict partial order (W,Â) such that all strictly decreasing chains are finite

Examples:– Natural numbers (N,>) is WFO– Natural numbers (N,<) is NOT WFO– Set of finite sets of integers under ¾ is WFO– String under “superstring” ordering is WFO– Strings under lexicographic ordering is NOT WFO– Tuples under lexicographic ordering is WFO


Deadlock-free NetworksTo avoid states (s,) such that (s,)9 but s sf we assume that if

are all control transitions emanating from control state s then

² 1 Ç 2 Ç ... Ç n

. . . .

s

s1 s2 sn

1! f1 2! f2

n! fn


Extended Inductive AssertionsExtended assertion network:

In addition to assertion network N:Associate to each control state s an expression w(s) s.t. whenever

then1. ²

s! w(s) 2 W

2. ² s Æ ! w(s) º w(s’)[e1/x1,...,en/xn]

3. For each cycle (= strongly connected subset) there is at least one transition as above such that ² s Æ ! w(s) Â w(s’)[e1/x1,...,en/xn]

Say N is progressing if an assignment w satisfying 1.-3. exists

s w(s) s’ w(s’)

s s’! f = (x1,...,xn) := (e1,...,en)


Extended Inductive Assertion Method

1. Give assertion network N for P

2. Prove that the network is inductive

3. Prove that N is consistent w.r.t. pre and post

4. Prove that N is deadlock-free

5. Determine WFO (W,Â) and assignment w

6. Prove that N with this assignment is progressing

Then P is totally correct w.r.t. pre and post

Theorem

The extended inductive assertion method is sound


Example

(y2,y3,y4) := (0,0,1)

y3 := y3 + y4

y3 > y1

(y3 · y1) ! (y2,y4) := (y2 + 1, y4 + 2)

s0

s1

s2 sf

s0: y1 ¸ 0

s1: y2

2 · y1 Æ y3 = y22 Æ y4 = 2*y2 + 1

s2: y2

2 · y1 Æ y3 = (y2 + 1)2 Æ y4 = 2*y2 + 1 sf: y2

2 · y1 < (y2 + 1)2

w(s0) = y1

w(s1) = w(s2) = w(sf) = y1 – y2


While programsPrimitive:

– x2 X: set of identifiers– e2 E: set of expressions – v2 V: set of values

Command syntax in BNF:c ::= skip | x := e | c ; c | if e then c else c | while e do c

Exercise: Cast the command syntax as first-order structure

= {.} (will remain so for a while)


Stores

Stores are assignments : x v of values to identifiers

e(): value of e in store

Store update:

[x v](y) = if x=y then v else (y)

States are either– Intermediate: Pairs of commands and stores (c,), or– Final: A state


While ProgramsTransitions inductively defined by inference system:

- -

(skip,) ! (x:=e,) ! [x e()]

(c1,) ! ’ (c1,)! (c’,’)

(c;c,) ! (c,’) (c1,c,) ! (c’;c,’)

e() 0

(if e then c else c,) ! (c,)

e() 0

(if e then c else c,) ! (c,)


While Programs, IIe() 0

(while e do c,) ! (c ; while e do c,)

e() 0(while e do c,) !

Exercise: Let c1 = x:=1;while x>0 do x:=x-1. Pick an arbitrary 1. Compute a sequence (c1,1)!(c2,2)! ... ! n

Exercise: Prove that ! is deterministic, i.e that for any c, there is at most one c’,’ such that (c,)!(c’,’)

Exercise (more advanced): Try to add some new language construction, like choice, cobegin/coend, or variable declarations. Add new components to the state if you want.


Hoare Logic

Hoare triple {} c {}:– Starting in state satisfying , if and when c terminates, holds– Or: Whenever ² () and

(c,) = (c0,0) ! (c1,1) ! ... ! i

then ² (i)

– I.e. c is partially correct w.r.t. and


Inference Rules

Assignment:

-

{[e/v]} v := e {}

Skip:

-

{} skip {}

Rule of consequence:

² ! ’ {’} c {’} ² ’ ! {} c {}


Inference Rules, II

Sequential composition

{} c1 {} {} c2 {}

{} c1;c2 {}

Conditional

{ Æ e 0} c1 {} { Æ e = 0} c2 {}

{} if e then c1 else c2 {}

While

{ Æ e 0} c {}

{} while e do c od { Æ e=0}


ExampleThe integer square root example again:

P: y2 := 0 ;y3 := 1 ;y4 := 1 ;while y3 <= y1 do

y2 := y2 + 1 ;y4 := y4 + 2 ;y3 := y3 + y4

od

Proof goal: {y1 >= 0} P {y22 <= y1 < (y2 + 1)2}


Proof Outlines

State predicates inserted into program text such that each statement (simple or compound) has pre- and postcondition

Proof outline is valid, if each embedded triple if valid and adjacent state predicates related by implication


Proof Outlines, ExampleP: {y1>=0}

y2 := 0 ;{y1>=0 Æ y2=0}y3 := 1 ;{y1>=0 Æ y2=0 Æ y3=1}y4 := 1 ;{y1>=0 Æ y2=0 Æ y3=1 Æ y4=1}{y22<=y1 Æ y3=(y2+1)2 Æ y4=2*y2+1}while y3 <= y1 do

{y22<=y1 Æ y3=(y2+1)2 Æ y4=2*y2+1 Æ y3<=y1}y2 := y2 + 1 ;{y22<=y1 Æ y3=y22 Æ y4=2*y2–1}y4 := y4 + 2 ;

{y22<=y1 Æ y3=y22 Æ y4=2*y2+1}y3 := y3 + y4{y22<=y1 Æ y3=(y2+1)2 Æ y4=2*y2+1}

od{y2

2 <= y1 < (y2+1)2 } /* Postcondition */


Soundness and CompletenessTheorem (soundness):

If {} c {} is provable then c is partially correct w.r.t. and

For the case of sequential composition and while, let

(c,) !n ’ if (c,)! ! ’ in ”n steps”

Lemma: If (c1;c2,) !n ’ then there are n1,n2, ’’ such that (c1,) !n1 ’’, (c2,’’) !n2 ’ and n = n1 + n2

Completeness:

Can obtain relative completeness, completeness relative to oracle answering true statements in FOL + arithmetic

Documents

Floyd/Hoare Logic