A Deductive Verification Infrastructure for Probabilistic Programs
summary
A deductive verification infrastructure implements an IVL (HAV/Halo) and a real-valued logic that encodes expectation-based specs, encodings for 12 loop proof rules, and automatic VC generation; it verifies >40 benchmark programs (expected values, termination probabilities, expected runtimes, conditional expectations) and handles recursion and user data. The Rust tool Caesar emits Halo VCs solved by Z3, yielding concrete results (e.g. geometric loop expected runtime = 2). Key ideas are quantitative assertions and SMT-backed verification.
AI-written summary · about