Skip to content
Tutorials Center
My learning

Topics

Lesson 29 of 36 ยท SPARK and Safety

Proving Absence of Run-Time Errors

Prove that Ada code never overflows or indexes out of range with SPARK: run-time check obligations, loop invariants, assertions, ghost code and how to read unproved checks.

Ada inserts checks at run time: arithmetic overflow, range violations, array index errors, division by zero. SPARK's silver goal is to prove that none of those checks can ever fail. Then the checks become redundant and may even be removed from production code with confidence. This lesson shows how proof obligations arise, how contracts and loop invariants help the prover, and how to read results.

SPARK tools are not available on this site, so the Ada code is read-only and tool results are described in words. Runnable C stand-ins check the same properties by brute force on small ranges.

Every check is an obligation

For each operation that could fail, GNATprove generates a goal. Take this function:

ADA
function Average (A, B : Integer) return Integer
  with SPARK_Mode
is
begin
   return (A + B) / 2;
end Average;

The tool tries to prove: A + B does not overflow Integer, and the division is fine (the divisor is the literal 2). The first goal cannot be proved: with A and B both near Integer'Last the sum overflows. The tool reports an unproved overflow check and, in recent versions, may show a counterexample. You have three choices:

  1. Narrow the types. subtype Small is Integer range -1_000 .. 1_000; with A, B : Small makes the sum fit.
  2. Add a precondition, for example Pre => A in -1_000_000 .. 1_000_000 and B in -1_000_000 .. 1_000_000.
  3. Rewrite, for example A / 2 + B / 2 + (A rem 2 + B rem 2) / 2, which cannot overflow (for mixed signs it can differ from the exact average by one, so the contract must allow that).

All three make the obligation provable; they differ in how much they restrict callers. A good design puts the limits in the types so every use site benefits.

Proof workflow

Run GNATprove checks every operation
Unproved read the message
Fix types, Pre, invariant
Proved no run-time error

Repeat until the report is clean.

1 / 2

Loops need invariants

The prover reasons about a loop without running it. Between iterations it knows only what the loop invariant tells it, plus what the loop does not touch. Consider summing an array of bounded numbers:

ADA
subtype Reading is Integer range 0 .. 1_000;
type Readings is array (1 .. 100) of Reading;

function Total (R : Readings) return Natural
  with SPARK_Mode,
       Post => Total'Result <= 100_000
is
   Sum : Natural := 0;
begin
   for I in R'Range loop
      pragma Loop_Invariant (Sum <= (I - 1) * 1_000);
      Sum := Sum + R (I);
   end loop;
   return Sum;
end Total;

The invariant says that before the body runs for index I, Sum is at most (I - 1) * 1000. Together with R (I) <= 1000, the prover shows Sum + R (I) <= I * 1000 which keeps the sum below 100_000 and in range, and the invariant holds again for the next iteration. At the end Sum <= 100_000, the postcondition. Without the invariant, the prover forgets everything about Sum after the first iteration and cannot show that the addition is safe.

A good invariant (1) holds on entry, (2) is preserved by the body, and (3) together with the exit condition implies what you need afterwards. These three conditions are what the tool checks.

Assertions and ghost code

pragma Assert (Condition); states a fact you expect at that point. The prover must prove it, and then can use it, so intermediate assertions guide a difficult proof step by step. Ghost code is code that exists only for proof: with Ghost on a variable, function or procedure means it may appear in contracts and assertions but never in the executable program, and the compiler erases it.

ADA
function Is_Sorted (A : Int_Array) return Boolean is
  (for all I in A'First .. A'Last - 1 => A (I) <= A (I + 1))
  with Ghost;

Ghost functions let you write rich specifications ("the result is a permutation of the input") without adding any run-time cost.

Reading the result

Each check ends in one of three states: proved, unproved or justified (you accepted it with pragma Annotate (GNATprove, Intentional, ...) and a reason). An unproved check does not always mean the code is wrong. It can mean the contract is too weak, an invariant is missing, or the prover timed out. Strategy: try a higher proof level, add an intermediate assertion, or restructure the code into smaller subprograms with their own contracts.

Stand-in: a bounded check you can run (C, runnable)

We cannot run the prover, but we can show the obligation for Total on a small version. With 4 readings of at most 10, we enumerate every combination and confirm the invariant at each step and the bound at the end. The loop checks the invariant just as the prover would, and counts how many assignments were examined.

C C stand-in: enumerate a loop invariant over all inputs

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

The result is 14641 arrays and 0 violations. The prover achieves the same conclusion for 100 readings of up to 1000 (a space far too large to enumerate) by induction on the loop.

Stand-in: an unprovable average (C, runnable)

This program demonstrates the overflow in the Average example on a 16-bit type, where the failing inputs can be listed, and shows that the rewrite never fails.

C C stand-in: find where (A + B) / 2 overflows

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

Many sample pairs overflow a 16-bit sum, while the rewrite never overflows and stays within one of the exact average for every sampled pair (zero pairs are further away).

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What must a loop invariant allow the prover to do?

    The invariant summarizes what is known at each iteration; the prover uses it instead of executing the loop.
  2. 2. What is ghost code?

    Ghost entities support specification without run-time cost.
  3. 3. A run-time check is reported as unproved. What does that necessarily mean?

    Unproved means unknown: strengthen contracts, add assertions or fix the code.
  4. 4. Which is the best first way to make (A + B) / 2 provable?

    Constraining the types helps every use of the data, not only this function.

Summary

  • Each possible run-time check becomes a proof obligation; goal: all proved.
  • Fix unproved checks by tightening types, adding preconditions, or rewriting.
  • Loops need invariants that hold on entry, are preserved, and imply the postcondition.
  • pragma Assert guides the prover; ghost code supports specifications without run-time cost.
  • Results are proved, unproved or justified; unproved is not automatically a bug.

Next: Representation Clauses and Bit Layout