5. Proving it: SPARK and GNATprove¶
So far, contracts have been checks that run. This chapter is about proving them instead: showing, before the program runs, that no check can ever fail, for any input.
What SPARK is¶
SPARK is a subset of Ada, chosen so that programs written in it can be analysed mathematically. Most of Ada is in it. The main things left out are those that make reasoning hard:
- functions with side effects (a SPARK function may not change anything outside itself);
- aliasing, where two names refer to the same variable (pointers are allowed only under strict ownership rules, much like Rust's);
- handling exceptions (SPARK code is meant never to raise them).
with SPARK_Mode on a unit says it is in the subset. The engine is all
SPARK; the server around it is not, and chapter 12 looks at that boundary.
What GNATprove does¶
GNATprove reads the program and generates a verification condition for every check that could fail: every range constraint, every array index, every division, every overflow, every predicate, precondition, postcondition and assertion. Each verification condition is a logical formula that is true exactly when that check always passes. Automatic provers (Alt-Ergo, CVC5 and Z3) then try to prove each formula.
What a prover knows at each point is what the code says: the types of the variables, the preconditions of the current subprogram, the postconditions of anything it has called, and the bodies of expression functions. That last part is why the engine uses so many expression functions.
Each check ends one of two ways:
- proved: it can never fail, for any input that meets the preconditions;
- not proved: the provers could not show it. That does not always mean
the check can fail. The provers may have run out of time, or lacked a fact
they needed. GNATprove marks a message high when it is confident the check
really fails, medium when it is not sure, and often offers a
counterexample after
e.g..
Levels of assurance¶
AdaCore describes SPARK use in levels, each building on the last:
| Level | What it establishes |
|---|---|
| Stone | The code is valid SPARK. |
| Bronze | Flow analysis passes: no variable is read before it is set, and data flows only where the contracts say. |
| Silver | No run-time errors: no overflow, no range violation, no index out of bounds, no failed precondition, ever. |
| Gold | Key properties hold, stated as contracts and proved. |
| Platinum | Full functional correctness against a complete specification. |
Every unit of the engine reaches at least Silver, and most reach Gold. Each
spec says which in its header comment, and PROOFS.md at the repository
root records what is proved for each. For example:
-- Proof level: Silver. Detects is the definition of detection, so there is
-- nothing further to prove about it; the guidance and view contracts are
-- stated in terms of it.
Silver: no run-time errors¶
Silver sounds modest. It is not: it means the program cannot crash, for any input, ever. Here is the sensor cone test, which decides whether one thing can see another:
-- Products of metre offsets and ratios need more than 32 bits.
type Wide is range -2**62 .. 2**62;
-- Whether Target lies within the cone, which is whether the angle
-- between the heading and the offset d to Target has a cosine of at
-- least cos (Half_Cone): u . d >= |d| cos (Half_Cone), with u the unit
-- heading. Both sides are squared so that no square root is needed.
function In_Cone (S : Sensor; From : Point; Heading : Angle; Target : Point)
return Boolean
is
(S.Half_Cone = Half_Turn
or else
(declare
Dot : constant Wide :=
Wide (DX (From, Target)) * Wide (Cos (Heading))
+ Wide (DY (From, Target)) * Wide (Sin (Heading));
D2 : constant Wide := Wide (Distance_Squared (From, Target));
C : constant Wide := Wide (Cos (S.Half_Cone));
begin
(if C >= 0 then Dot >= 0 and then Dot * Dot >= D2 * C * C
else Dot >= 0 or else Dot * Dot <= D2 * C * C)));
A declare expression introduces local constants inside an expression.
The products here are big. An offset of up to 6000 metres, times a ratio of
up to 16384, then squared, is around 10¹⁶: far beyond 32 bits. In C, this
would silently wrap and a jet on the far side of the arena would appear right
in front of you. In Ada it would raise Constraint_Error. In SPARK, the
prover checks every product against the range of Wide and proves none
overflows. The type was chosen to be wide enough, and the proof confirms it.
Try it: make it overflow¶
Use 32-bit arithmetic instead:
- type Wide is range -2**62 .. 2**62;
+ type Wide is range -2**31 .. 2**31 - 1;
GNATprove finds every product that can now overflow, and suggests a precondition that would rule out the inputs that cause it. Here the right fix is the type, not a precondition.
overflow check might fail, cannot prove upper bound for Dot * Dot
overflow check might fail, cannot prove upper bound for D2 * C
possible fix: add precondition
Bronze: flow analysis¶
Before proving anything, GNATprove runs flow analysis. It checks that
every variable is set before it is read, and that every subprogram touches
only the global data its contract allows. The Global aspect states that:
Global => null says the lemma reads and writes no global state. Most of the
engine needs no Global aspects at all, because its packages have no state
to touch: they are Pure, or contain only constants and functions.
Proving termination¶
One more thing GNATprove checks: that every function returns. A function that might loop forever has no meaningful result to reason about. For a function with no loops or recursion this is automatic. For loops, the next chapter shows how to prove it.
Reading the results¶
After a run, GNATprove prints a summary and says where it logged the full
results (a gnatprove directory under engine/obj/). When everything passes, it says
all checks proved. When something fails, each message gives:
- the file, line and column of the check;
- what kind of check it is (range, overflow, postcondition, ...);
- what it could not prove (
cannot prove upper bound for Dot * Dot); - often, a counterexample and a possible fix.
The habit to form is to read the message as a question: why does the prover think this can fail? Usually the answer is that it is missing a fact, and the fix is to state the fact somewhere it can use: a type, a precondition, a postcondition on something called, or an assertion. The rest of this course is about stating facts the prover can use.
Recap¶
- SPARK is the analysable subset of Ada; GNATprove proves things about it.
- Every check that could fail becomes a verification condition for the provers.
- The provers know what the types, contracts and expression functions say, and nothing else.
- Silver means no run-time errors; Gold means key properties are proved too.
- An unproved check is a question to answer, usually by stating a missing fact.