Skip to main content

Caesar 4.2: HeyVL Examples, Loop Proofs, and Soundness Fixes

· 8 min read
Philipp Schroer
Caesar Developer

Caesar 4.2 adds new ways to bound expected rewards and a filterable gallery of programs and proofs written in HeyVL, Caesar's verification language. The release also fixes soundness bugs involving @past loops, procedure calls in variable initializers, and model exports for loops with local declarations.

Overview

  1. Soundness Fixes
  2. HeyVL Example Zoo
  3. Required Migration for @past Proofs
  4. More Flexible Optional Stopping
  5. Optional else Branches
  6. Website and Documentation
  7. Other Improvements
Migration Required for @past

If you use @past, put the annotated loop in a coproc and update its specification.

Soundness Fixes​

Earlier Verification and Model-Checking Results

Earlier versions could accept invalid proofs or export models that gave incorrect results in the cases below. After upgrading, rerun proofs that use @past, procedure calls in variable initializers, standalone validate or covalidate, --explain-core-vc, or --opt-rel. Regenerate JANI models exported from loops with literal initializers inside the body, then rerun model checking.

  • Loops annotated with @past. Caesar checked the ranking proof separately and could accept a procedure specification that left out rewards accumulated in the loop. Caesar now accounts for the loop's rewards and possible exit states when checking the procedure.
  • Procedure calls in variable initializers, such as var x: UInt = p().
    • A call in a declaration could bypass the direction check, allowing a proc to call a coproc or vice versa. Caesar now checks calls in declarations as well as in assignments.
    • Proof rules that copy loop bodies, such as @unroll, could drop an initializer call from a copy and verify a false postcondition. Caesar now preserves and checks the call in each copy.
  • JANI export. A literal initializer inside a loop, such as var x: UInt = 0, only ran at model startup, so later iterations could reuse a stale value and give the wrong result. The exported model now runs the initializer every time it reaches the declaration.
  • Standalone validation statements. Caesar swapped the effects of validate and covalidate on positive finite expectations when translating these statements on their own. The corrected translations map those values to 00 for validate and ∞\infty for covalidate, as specified for validation statements.
  • Optional transformations
    • --explain-core-vc could replace 0−x0 - x with xx. The simplifier now leaves the subtraction intact when it cannot fold it correctly.
    • --explain-core-vc could simplify 0/x0 / x to zero even when xx could be zero, allowing an invalid proof to pass. The simplifier now preserves the division in that case.
    • --explain-core-vc could crash when simplifying multiplication of a Real value by zero. The simplifier now produces a zero of type Real.
    • --opt-rel applied lattice rewrites to types where they can change an expression's value. It now applies those rewrites only to extended nonnegative reals.

HeyVL Example Zoo​

The expanded HeyVL Example Zoo collects 22 examples, from coin flips and sampling algorithms to communication protocols and data structures. You can filter by topic or proof technique and download the HeyVL source. Seventeen examples have walkthroughs that explain the program, what Caesar verifies, and how to run the proof yourself.

New and Updated Proofs​

Required Migration for @past Proofs​

The @past annotation now uses the ranking expression II to bound the loop's expected reward in the enclosing procedure.

  1. Declare the enclosing procedure as a coproc. Write @ert to make the expected-runtime calculus explicit. If the coproc omits its calculus annotation, @past selects least-fixed-point semantics for the loop. Put any lower-bound claim in a separate proof.
  2. If the procedure consists of the loop, use its ranking expression II as pre and set post 0.

Keep @past(I, epsilon, K) on the loop. Caesar now rejects ϵ=0\epsilon = 0, checks I<∞I < \infty in every state, and enforces the loop-body restrictions. The expected decrease in II must cover the iteration's expected reward plus ϵ\epsilon.

Example Migration for a Countdown

The countdown initializes x to n, so the ranking expression 2 * x + 1 at loop entry gives pre 2 * n + 1. With one reward per iteration, Caesar verifies this as an upper bound on the expected number of iterations.

-proc count(n: UInt) -> ()
+@ert
+coproc count(n: UInt) -> ()
+ pre 2 * n + 1
+ post 0
{
var x: UInt = n
@past(2 * x + 1, 1, 2)
while x > 0 {
reward 1
x = x - 1
}
}

More Flexible Optional Stopping​

The optional stopping rule (@ost) accepts more invariants in @wp proofs and now supports lower bounds on expected rewards in @ert proofs. Existing @wp proofs that meet the rule's assumptions need no changes. Write II for the invariant and ff for the loop's postexpectation.

  • On exit. Caesar previously required I=fI = f. Now I≤fI \leq f suffices.
  • Finiteness. The old check required a finite expected value of II after one iteration and a finite value of ff at exit. Caesar now checks that II itself is finite in every state, and ff can be infinite even at exit.
  • Change per iteration. Caesar previously checked the expected absolute change of II even in states where the loop would stop immediately. It now applies the bound cc only in states where the loop guard holds. The bound includes the iteration that exits the loop.

To prove a lower bound on accumulated rewards, put @ost(I, PAST_I, c, 0) in an @ert proc with post 0. The bound cc must cover the expected sum of the rewards and the absolute change of II in one iteration, as described in the expected runtime rule.

Optional else Branches​

This one took us a while for a change that saves seven characters. You can finally leave out else {} in a HeyVL conditional.

// Before
if x > 0 {
x = x - 1
} else {}

// Now
if x > 0 {
x = x - 1
}

Website and Documentation​

Other Improvements​

  • Proof diagnostics
    • Counterexamples from @unroll have clearer diagnostics.
    • Caesar handles unchanged parameters correctly in @ost and @past obligations.
    • --explain-core-vc supports conegate.
  • Storm
    • Caesar reads the new command-line result format and displays the solution bounds reported by Storm 2.0. With a state limit, Caesar labels these as bounds for the truncated model.
    • If Storm omitted a property's result, Caesar could display the next property's result in its place. Caesar now reports the result as missing.
  • SMT. Caesar handles more Boolean operators during verification and avoids repeatedly simplifying the same subexpressions in nested implications.
  • VS Code. Installation and updates handle multiple open windows, and the walkthrough links to the example zoo.
  • Command line
    • Caesar has removed the experimental --egraph option. Remove the flag from scripts that pass it.
    • On Linux, --mem now reads resident memory from /proc/self/statm, which works under QEMU user-mode emulation.