Caesar 4.2: HeyVL Examples, Loop Proofs, and Soundness Fixes
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
- Soundness Fixes
- HeyVL Example Zoo
- Required Migration for
@pastProofs - More Flexible Optional Stopping
- Optional
elseBranches - Website and Documentation
- Other Improvements
@pastIf you use @past, put the annotated loop in a coproc and update its specification.
Soundness Fixes
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
procto call acoprocor 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.
- A call in a declaration could bypass the direction check, allowing a
- 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
validateandcovalidateon positive finite expectations when translating these statements on their own. The corrected translations map those values to forvalidateand forcovalidate, as specified for validation statements. - Optional transformations
--explain-core-vccould replace with . The simplifier now leaves the subtraction intact when it cannot fold it correctly.--explain-core-vccould simplify to zero even when could be zero, allowing an invalid proof to pass. The simplifier now preserves the division in that case.--explain-core-vccould crash when simplifying multiplication of aRealvalue by zero. The simplifier now produces a zero of typeReal.--opt-relapplied 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
- Browse new proofs of uniform sampling from a stream in Reservoir Sampling and from a range of any positive size in Fast Dice Roller.
- See how two separate bounds limit the expected number of rounds given that a queue empties before its server fails in Conditioning on Queue Completion.
- Compare upper and lower bounds on the expected number of tails before the first heads in Geometric Loop, or see how
@pastbounds the expected number of flips in Countdown with Pauses. - Explore proofs that bound the probability of delivering all packets and the expected number of transmission attempts for one packet in the Bounded Retransmission Protocol.
- Find Boolean correctness proofs for Selection Sort and Binary Search Trees.
Required Migration for @past Proofs
The @past annotation now uses the ranking expression to bound the loop's expected reward in the enclosing procedure.
- Declare the enclosing procedure as a
coproc. Write@ertto make the expected-runtime calculus explicit. If thecoprocomits its calculus annotation,@pastselects least-fixed-point semantics for the loop. Put any lower-bound claim in a separate proof. - If the procedure consists of the loop, use its ranking expression as
preand setpost 0.
Keep @past(I, epsilon, K) on the loop.
Caesar now rejects , checks in every state, and enforces the loop-body restrictions.
The expected decrease in must cover the iteration's expected reward plus .
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 for the invariant and for the loop's postexpectation.
- On exit. Caesar previously required . Now suffices.
- Finiteness. The old check required a finite expected value of after one iteration and a finite value of at exit. Caesar now checks that itself is finite in every state, and can be infinite even at exit.
- Change per iteration. Caesar previously checked the expected absolute change of even in states where the loop would stop immediately. It now applies the bound 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 must cover the expected sum of the rewards and the absolute change of 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
- The docs add a first-proof walkthrough, expand the HeyVL statement reference, and explain the guarantees of each proof rule.
- The Publications page links to the open-access CAV tool paper. The About page offers BibTeX, logos, and a QR code for the website.
Other Improvements
- Proof diagnostics
- Counterexamples from
@unrollhave clearer diagnostics. - Caesar handles unchanged parameters correctly in
@ostand@pastobligations. --explain-core-vcsupportsconegate.
- Counterexamples from
- 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
--egraphoption. Remove the flag from scripts that pass it. - On Linux,
--memnow reads resident memory from/proc/self/statm, which works under QEMU user-mode emulation.
- Caesar has removed the experimental
