Without unwinding, translate a simple while loop iteration into SMT-LIB formula to prove correctness

Question

Consider proving correctness of the following while loop, i.e. I want show that given the loop condition holds to start with, it will eventually terminate and result in the final assertion being true.

int x = 0;
while(x>=0 && x<10){
   x = x + 1;
}
assert x==10;

What would be the correct translation into SMT-LIB for checking the correctness, without using loop unwinding?

Answer 1

Hoare logic and loop-invariants

Typical proof of such a statement would be done via the classic Hoare logic, which I assume you're already familiar with. If not, see: https://en.wikipedia.org/wiki/Hoare_logic

The idea is to come up with an invariant for your loop. This invariant must be true before the loop starts, it must be maintained by the loop body, and it must imply the final result when the loop condition is no longer true. Additionally, you also need to prove that the loop will eventually terminate, by means of a measure function. (More on that later.)

You can convince yourself why this would be sufficient: An invariant is something that's "always" true. And if it implies your final result, then your proof is complete. The proof steps I outlined above ensure that the invariant is indeed an invariant, i.e., its truth is always maintained by your program.

Coming up with the invariant

What would be a good invariant for your loop here? Let's give this invariant the name I. A moment of thinking reveals a good choice for I is:

I = x >= 0 && x <= 10

Note how similar (but not exactly the same!) this is to your loop-condition, and this is not by accident. Loop-invariants are not unique, and coming up with a good one can be really difficult. It's an active area of research (since 60's) to synthesize loop-invariants automatically. See the plethora of research out there. https://en.wikipedia.org/wiki/Loop_invariant is a good starting point.

Proof using SMT

Now that we "magically" came up with the loop invariant, let's use SMT to prove that it is indeed correct. Instead of writing SMTLib (which is verbose and mostly intended for machines only), I'll use z3-python interface as a close enough substitute. To finish the proof, I need to show 4 things:

1. The invariant holds before the loop starts
2. The invariant is maintained by the loop body
3. The invariant and the negation of the loop-condition implies the desired post-condition
4. The loop terminates

Let's look at each in turn.

(0) Preliminaries

Since we'll use z3's python interface, we'll have to do a little bit of leg-work to get us started. Here's the skeleton we need:

from z3 import *

def C(p):
  return And(p >= 0, p < 10)

def I(p):
  return And(p >= 0, p <= 10)

x = Int('x')

Note that we parameterized the loop-condition (C) and the invariant (I) with a parameter so it's easy to call them with different arguments. This is a common trick in programming, abstracting away the control from the data. This way of coding will simplify our life later on.

(1) The invariant holds before the loop starts

This one is easy. Right before the loop, we know that x = 0. So we need to ask the SMT solver if x == 0 implies our invariant:

>>> prove (Implies(x == 0, I(x)))
proved

Voila! If you want to see the SMTLib for the proof obligation, you can ask z3 to print it for you:

>>> print(Implies(x == 0, I(x)).sexpr())
(=> (= x 0) (and (>= x 0) (<= x 10)))

(2) The invariant is maintained by the loop-body

The loop body is only run when the loop condition (C) is true. The body increments x by one. So, what we need to show is that if our invariant (I) is true, if the loop condition (C) is true, and if I increment x by one, then I remains true. Let's ask z3 exactly that:

>>> prove(Implies(And(I(x), C(x)), I(x+1)))
proved

Almost too easy!

(3) The invariant implies the result when loop condition is false

This time, all we need to ask the solver is to prove the required conclusion when I holds, but C doesn't:

>>> prove(Implies(And(I(x), Not(C(x))), x == 10))
proved

And we have now completed what's known as the partial-correctness claim. That is, if the loop terminates, then x will indeed be 10 at the end. This is what you were trying to prove to start with.

(4) The loop terminates

What we've done so far is known as partial-correctness. It says if the loop terminates, then your post-condition (i.e., x == 10) holds. But it does not make any guarantees that the loop will always terminate.

To get a full-proof, we have to prove termination. This is done by coming up with a measure function: A measure function is a function that assigns (typically) a numeric value to the set of program variables, which is bounded from below. Then we show that it goes down in each iteration and has an initial value that's above its lower-bound. Then we know that the loop cannot continue forever: The measure has to go down in each iteration, but it cannot do so since it's bounded below.

Termination proofs are usually harder, and coming up with a good measure can be tricky. But in this case, it's easy to come up with it:

def M(x):
  return 10-x

The claim is that the measure is always non-negative in this case. Let's prove that before the loop starts, i.e., when x == 0:

>>> prove (Implies(x == 0, M(x) >= 0))
proved

It goes down in each iteration:

>>> prove (Implies(C(x), M(x) > M(x+1)))
proved

And finally, it's always positive if the loop executes:

>>> prove (Implies(C(x), M(x) >= 0))
proved

Now we know that the loop will terminate, so our proof is complete.

But wait!

You might wonder if I pulled a rabbit out of a hat here. How do we know that the above steps are sufficient? Or that I didn't make a mistake in my coding as I waved my hand over your program and magically translated it to z3-python?

For the first question: There's established research that for traditional imperative program semantics, Hoare-logic style reasoning is sound. Here's a good slide deck to start with: https://www.cl.cam.ac.uk/teaching/1617/HLog+ModC/slides/lecture2.pdf

For the second question: This is where the rubber hits the road. You have to put my argument to peer-review, possibly using an established theorem prover to code the whole thing up and trust that the mechanization is correct. Why3 (https://why3.lri.fr) is a good-platform to get started for this style of reasoning.

Picking the invariant

The trickiest part of this proof is coming up with the right invariant. A "good" invariant is one that's not only true, but one that allows you to prove the result you want. For instance, consider the following invariant:

def I(p):
  return True

This invariant is manifestly true for all programs as well! But if you attempt to run the proofs we had with this version of I, you'll see that it won't go through and you'll get a counter-example. (It's quite instructive to do so.) In general, you can:

• Pick an "invariant" that's not really enforced by your program, i.e., it doesn't stay true at all times as described above. Hopefully the counter-example you get from the solver will be helpful to identify what goes wrong.

• Or, and this is way more likely, the invariant you picked is indeed an invariant of the program, but it is not strong enough to prove the result you want. In this case the counter-example will be less useful, and for complicated programs it can be hard to track down the reason why.

An invariant that allows you to prove the final result is called an "inductive invariant." The process of "improving" the invariant to get to a proof is known as "strengthening the invariant." There's a plethora of research in all of these topics, especially in the realm of model-checking. A good paper to read in these topics is Bradley's "Understanding IC3:" https://theory.stanford.edu/~arbrad/papers/Understanding_IC3.pdf.

Summary

The strategy outlined here is a "meta"-level proof: It's equivalent to a paper-proof which identified the proof goals, and shipped them to an SMT solver (z3 in this case), to finish the job. This is common practice in modern day proofs, i.e., coming up with sub-goals and using an automated-solver to discharge them. Theorem-provers like ACL2, Isabelle, Coq, etc. mechanize the "coming up with subgoals" part to a large extent, making sure the whole proof is sound with respect to a trusted (but typically very small) set of core-axioms. (This is the so called LCF methodology, see https://www.cl.cam.ac.uk/~jrh13/slides/manchester-12sep01/slides.pdf for a nice slide-deck on it.)

Hopefully this is a detailed-enough level answer for you to get you started in program verification with SMT-solvers. Perhaps it's more than what you asked for; but the rule-of-thumb is there is no free lunch in verification. It is a lot of work! However, you get pretty close to push-button reasoning these days (at least for certain kinds of programs) with the advances in automated theorem provers, SMT-solvers, and other frameworks that many people built over the years. Best of luck, but be warned that program-verification remains the holy-grail of computer science after almost 7-decades of work on it. Things always get better/easier, but there's much more work to be done in the field.