Skip to content

Latest commit

 

History

History
256 lines (204 loc) · 17.8 KB

verification-roadmap.md

File metadata and controls

256 lines (204 loc) · 17.8 KB

Verification Roadmap: From Sealed Safety to Provable Properties

Status: Part A done. Part B is partly SHIPPED — see "What shipped" below; the rest of this doc is the original exploratory reasoning, kept because the tier argument still holds.

What shipped

milo prove discharges contracts with z3, the only solver (a runtime requirement: brew install z3 / apt install z3). The in-tree solver written in Milo (std/smt, Fourier-Motzkin over linear integers) was removed on 2026-11-04: z3 proves what it could not (bool-valued contracts, nonlinear arithmetic) and there is one less decision procedure to keep sound. The contract vocabulary is now:

Clause Meaning
requires precondition, proved at every call site
ensures postcondition, proved at every return
invariant on a loop induction across while and for in
invariant on a struct property of the type: assumed at use, owed at construction and at every &mut
decreases termination measure, on a function or a loop
old(e) the entry value of a scalar, inside ensures

That set is, near enough, SPARK's — Pre, Post, Loop_Invariant, Type_Invariant, Loop_Variant/Subprogram_Variant, 'Old. Two of SPARK's are absent by choice: Global/ Depends (Milo's ownership rules make most of it unnecessary) and quantifiers.

Where that lands us: user-written contracts, termination and simple data invariants, plus milo prove --rte, which generates the runtime-error conditions the program does not state: no overflow in fixed-width + - * (not under @wrapping), no zero divisor and no MIN / -1 in integer / %, and 0 <= i < len on every index of a Vec, string or array. Each is a overflow / division / bounds condition under the path conditions that reach it. Not yet covered: shifts, casts, unary minus, and any expression whose integer type is not known (never guessed). An unwrap gets a condition but there is no Option model yet, so it is always reported unknown. Silver means all of these proven, and we are not there: bun scripts/rte-census.ts (z3, examples/embedded + std, each source site counted once at its worst verdict) measured 2026-11-09:

kind proven failed unknown
overflow 904 282 1054
bounds 497 218 1015
division 18 17 51
total 1419 517 2120

That is 35% of 4056 sites proven, up from 8% (346 of 4119) on 2026-11-03. A site that is not proven is still safe at run time: it keeps its trap. What a proof buys is knowing the trap cannot fire.

Most unknowns are callees with no ensures (the result is unmodelled) and IndexAccess values, not the conditions themselves; most failures are real missing requires, since nothing in std states input ranges. Quantifiers are the step after silver, toward functional correctness ("gold").

The one structural gap: quantifiers. forall/exists over container contents, and the sequence theory to go with them. Without it, sortedness is not merely hard to prove, it is unstateable, and binary search cannot be specified at all. Deliberately not chased: trigger selection is where Dafny/Verus users actually burn their time, and it contradicts this doc's own "no annotation burden" principle. z3 can take quantifiers, but only with triggers. Revisit only with a concrete demand that nothing else answers.

Floats (2026-07-25). f32/f64 were declared as SMT Real all along, but exprToSmt had no FloatLit case, so the first constant in a float contract turned the whole VC into (UNSUPPORTED FloatLit) — 28 of the tree's unknowns, and the reason examples/embedded/flightController.milo scored 0 proven / 64 unknown. It is 11 / 55 now (the 55 are std postconditions outside the entry file, not solver limits), and the two failures the fix surfaced were real: pidNew checked outMin < outMax and pidUpdate had no way to know it, which is what invariant outMin < outMax on the struct now carries.

Translating floats also exposed a false proof in the since-removed std/smt solver: its integer tightenings (folding L < 0 into L + 1 <= 0) are nonsense over R, and requires x > 0.0 && x < 1.0 came out infeasible, so every postcondition of such a function "verified". z3 never had the problem, and the regression fixture (tests/prove/floatNoFalseProof.milo) keeps pinning the property: a false bound over a strict real interval must be refuted.

assert E as a proof cut (2026-08-16). The practical substitute for quantifiers, and it needed no new syntax at all: assert was already a builtin. Each one is now proven where it is written, under the path conditions that reach it, and then ASSUMED by everything downstream — so a user can hand the solver the single intermediate fact that reconnects a goal to its premises.

Assuming it is sound for a reason specific to assert and unavailable to a bare assume: codegen emits an unconditional abort on a false assert, in every build mode, so no execution reaches the next statement with E false. There is deliberately no assume form; an unchecked one is a false proof with a keyword.

A cut whose own VC is not discharged still feeds the assumption — ordinary assume-guarantee, the same deal a callee's ensures gets — so each cut carries an identity and every VC that leaned on it names it. Without that, assert(a >= 100) refuted with a counterexample and the postcondition it made trivial reported a clean tick.

Measured on the shape it is for: sumTo's ensures result >= 0 is refuted without a cut, because the walker havocs s at the loop and the postcondition becomes a claim about a free variable. With the cut it is proven, and the report says which fact it rests on until a loop invariant discharges the cut too (tests/prove/proofCut.milo: 7/7, unconditional).

Where a cut does NOT help. A cut buys something only where the connection was lost (a loop havoc, a branch), not where the term is untranslatable to SMT-LIB (UNSUPPORTED markers): asserting a fact about such a term leaves both the cut and its consumer unknown.

Next, in order of leverage per unit of syntax:

  1. Range subtypes. MiloType already carries rangeMin/rangeMax (i32(0..50000)). Propagating those into intRangeAssumption retires the pidStep baseline, whose whole problem is that only parameters carry range facts, so setpoint - measured escapes to ±2^32 in the unbounded-Int model. Mostly plumbing over an existing representation.
  2. @pure. modelCall deliberately refuses to share a constant between two identical call sites, because a Milo function may read mutable global state. Purity unlocks that.
  3. old at loop entry (SPARK's 'Loop_Entry).

Original exploratory notes follow.

Context: comparison against proof-oriented languages (Bend2 et al.) raised the question of how far Milo should go on formal verification. Milo today is a sealed safety contract — its checker mechanically proves a fixed property set (memory, null, race, overflow, coercion safety) via sound static analysis. It is not a theorem prover: you cannot state and prove your own program properties.

This doc lays out (A) finishing the sealed contract, then (B) optionally letting users assert custom properties — and argues for the SMT-refinement tier, not dependent types.

Guiding principle (unchanged from safety-roadmap.md): static analysis first, no annotation burden, false positives unacceptable, dynamic checks only as fallback. Verification must not turn Milo into a proof-obligation grind.

Part A: Close the Sealed Contract First

This is committed work already specced in safety-roadmap.md Phases 2–3. Do it before any new verification theory. It reuses the move checker's existing dataflow framework — no solver, no new surface.

Order of operations:

  1. Phase 2a — ref-while-frozen. A collection is frozen while a &/&var into it is live; mutation is a compile error. Same taint-tracking as the move checker.
  2. Phase 2b — use-after-invalidate. .push() (may realloc), .clear(), reassignment taint live refs. Stdlib methods annotated @invalidates_refs.
  3. Phase 3a — call-site exclusivity. A variable cannot appear as both a &var argument and the source of a & argument at one call site. Pure argument-origin check — no interprocedural dataflow.

Status (done): 2a (ref-while-frozen) already held — reassigning a frozen var errors. 2b (use-after-invalidate) is largely N/A today: the only into-collection borrows are string slices (Vec has no slice API), and reassign-while-sliced is already caught. 3a (call-site exclusivity) was the one real hole — f(&mut v, &v[0]) compiled and silently corrupted after a reallocating push; now rejected (checker.ts checkCallSiteExclusivity, fixture tests/errors/callSiteExclusivity.milo). The sealed contract is sound for the patterns expressible today.

Payoff: the existing contract becomes genuinely sound. Highest ROI verification work available. No reason to leap to custom proofs before this lands.

Part B: User-Asserted Properties

Goal: let users state properties (bounds, ranges, invariants) and have the compiler prove them — without writing manual proof terms.

The tier decision

Tier Mechanism Proves Cost Prior art
1 Contracts, runtime-checked requires/ensures/assert, debug traps Low Eiffel (Design by Contract)
2 Refinement types + SMT (Z3) bounds, ranges, non-null, simple invariants — auto-discharged Med Dafny, Liquid Haskell, F*, Flux (Rust)
3 Dependent types + proof terms arbitrary theorems, hand-written proofs Very high Bend2, Lean, Agda, Coq

Recommendation: Tier 2.

  • Tier 3 (dependent types) is a different language identity — manual proofs, enormous surface, directly contradicts "no annotation burden." That's the Bend2 lane; not Milo's.
  • Tier 2 is the systems-language sweet spot: user writes a predicate, the SMT solver proves it, zero proof terms. And it pays for itself — proven-safe indexing lets codegen delete runtime bounds checks, tying verification straight into the "fast like C" goal.
  • Tier 1 is the cheap on-ramp and should be how Tier 2 ships first (dynamic before static).

Tier 2 concrete path

  1. Syntax. Refinement predicates on types and functions. Predicates are pure boolean Milo expressions.
    fn get(v: &Vec<T>, i: usize{i < v.len()}) -> &T
    fn divide(a: i32, b: i32{b != 0}) -> i32
    
    fn push(v: &mut Vec<T>, x: T)
        ensures v.len() == old(v.len()) + 1
    
  2. Dynamic-first. Lower predicates to debug-mode assert traps. Ships value immediately with no solver. Deliberately NOT the overflow-safety pattern: overflow traps in every build mode, because an overflow is the machine doing something other than the arithmetic says. A contract is a claim the author wrote down, so it defaults to debug and --contract-checks forces it on at any optimization level.
  3. Static discharge. Checker emits verification conditions → Z3. Pass = compile-time proof. Fail = diagnostic with the solver's counterexample (Elm-style, via diagnostics.ts). SMT integration options below.
  4. Payoff pass. When an index is proven in-bounds, codegen skips the bounds check. Verification becomes a perf feature, not just a safety feature.
  5. Stdlib first. Annotate Vec indexing, integer ranges, slice ops. User types opt in — same rollout as the @invalidates_refs plan.

Why SMT and not a homegrown checker

Refinement discharge is undecidable in general; SMT solvers (Z3) are the proven pragmatic answer (Dafny, F*, Flux all do this). Building a bespoke theory solver is a research project with worse coverage. Reuse the solver.

Next: silver, gold, then whole-program invariants (decided 2026-11-03)

The order, each step building on the last:

  1. Silver, default on. --rte already generates overflow, bounds and division obligations (the census above has the proven count; unwrap waits on an Option model). It becomes the default once its unknowns stop dominating the report. Triage of the first run on real code is in plans/rte-triage-2026-11.md.
  2. Check z3's proof output. An unsat verdict is currently taken on z3's word. Ask z3 for a proof ((get-proof)) and check it with a small independent checker, so trust rests on that checker rather than on the solver. Until then z3 answers are marked provisional.
  3. Gold: functional correctness. forall/exists, ghost sequence and map types for specifications, and lemma functions (ghost, erased before codegen, with decreases). Quantified obligations go to z3. This reverses the "no quantifiers" call above: agents now write the triggers and lemmas, so the annotation-burden argument against them is gone. Proof terms stay a non-goal (see proofs-vs-contracts.md).
  4. Whole-program invariants. A module-level invariant (reusing the existing keyword) over many values, and temporal forms for concurrent code:
    invariant noOverdraft: forall a in bank.accounts: a.balance >= 0
    invariant always(queue.len <= CAPACITY)
    invariant eventually(job.done)
    
    Single-lock invariants are proved by induction over critical sections (see plans/parallelism.md). always/eventually are checked first by exploring task schedules in the reference interpreter (milo interp, whose scheduler choice is one function for this reason), then proved by inductive invariants where it matters. The exploration exists: milo interp --explore finds deadlocks, panics, assertion and contract failures and output differences, with replayable schedules (R-EXPLORE-* in semantics/milo.md); checking always/eventually on top of it is next.
  5. Spec lock. For each changed contract, the solver checks whether the new one only strengthens the old (old requires implies new, new ensures implies old). A strengthening merges on its own; a weakening needs a human. milo spec --diff <base> prints the intent surface a reviewer reads.

Shipped alongside: requirements traceability (2026-11-04)

@req(ID) on fns, contract clauses and tests, requirements.json, and milo trace <entry.milo> (src/requirements.ts): the matrix pairs each requirement with its implementing fns, the milo prove verdict of each formalizing clause (a requires is judged per call site) and its tests. --strict, or a --safety profile whose traceability field is strict (on verify --profile, or build --strict), fails on gaps. Worked example: examples/assured/pid. --coverage reports line coverage of the implementing fns by the verifying tests (strict fails on an uncovered line). Not yet: branch and MC/DC coverage, and a requirements.json importer.

Prior art

Design by contract comes from Eiffel; temporal invariants and always/eventually from TLA+; proving the absence of runtime errors from SPARK and Astrée; reference interpreters as oracles from the WebAssembly spec and Rust's Miri; executable semantics from the K framework. The framing of invariants as rules an AI agent can't break comes from Bend's LAWS.bend.

Open Questions

  • Sequencing: A fully before B? (Assumed yes.)
  • B tier: lock Tier 2? Or ship Tier 1 contracts standalone first as a product in their own right?
  • SMT integration: shell out to the z3 binary, libz3 via FFI (Milo has FFI now), or vendored? Build-time dependency story for users?
  • Refinement scope: ... also user-defined struct invariants? Resolved: yes. Written after the closing brace over bare field names. Two-sided — assumed at every use, owed at every literal and every &mut function — because the assume half alone is an unchecked hole.
  • Dynamic fallback location: debug builds only, or a --verify opt-in? How does --deny-unsafe (aircraft-grade) interact — does it imply --verify?
  • old() / ghost state: support ensures referencing pre-state? Resolved: yes, scalars only. The VC-generator cost was real but bounded: postconditions had to move from being lowered against entry symbols to being lowered per exit path, and call sites needed a frame assumption relating the post-call havoc symbols back to the pre-call ones. That last piece is what makes it useful to a CALLER rather than only provable at the definition. Builtin Vec/string methods get the same frame from a contract table written in Milo (BUILTIN_CONTRACTS_SRC, src/verify.ts), and a havoc that NO contract, guard or invariant describes can no longer be reported as failed: the verdict is unknown, naming the free value. See roadmap.md §Contracts & Proving for the table and the rule.
  • Termination: ... need a termination checker? Resolved: yes, and it was not optional. A self-recursive call is modelled by assuming the function's own ensures; without a measure that is induction over a possibly-non-terminating recursion, which proves anything. decreases supplies it, and a proof that leaned on recursion without a discharged measure is now reported as conditional rather than clean.

Non-Goals

  • Dependent types / hand-written proof terms (Tier 3). Out of scope by design, and re-examined with evidence on 2026-09-01: see proofs-vs-contracts.md for what was measured, the one-sentence rule for users, and the four triggers that would reopen it.
  • Full functional-correctness specs: reversed on 2026-11-03, see "Next" above (gold).
  • Proving the compiler itself correct.