Error Localization, Certificates, and Hints for Probabilistic Program Verification via Slicing
- 10 April 2026
- book chapter
- Published by Springer Nature
- p. 210-240
Abstract
This paper focuses on effective user diagnostics generated during the deductive verification of probabilistic programs. Our key principle is based on providing slices for (1) error reporting, (2) proof simplification, and (3) preserving successful verification results. By formally defining these different notions on HeyVL, an existing quantitative intermediate verification language (IVL), our concepts (and implementation) can be used to obtain diagnostics for a range of probabilistic programming languages. Slicing for error reporting is a novel notion of error localization for quantitative assertions. We demonstrate slicing-based diagnostics on a variety of proof rules such as quantitative versions of the specification statement and invariant-based loop rules, and formally prove the correctness of specialized error messages and verification hints. We implemented our user diagnostics into the deductive verifier Caesar. Our novel implementation — called Brutus — can search for slices which do or do not verify, corresponding to each of the three diagnostic notions. For error reporting (1), it exploits a binary search-based algorithm that minimizes error-witnessing slices. To solve for slices that verify (2 and 3), we empirically compare different algorithms based on unsatisfiable cores, minimal unsatisfiable subset enumeration, and a direct SMT encoding of the slicing problem. Our empirical evaluation of Brutus on existing and new benchmarks shows that we can find slices that are both small and informative.Keywords
All Related Versions
This publication has 45 references indexed in Scilit:
- Static Slicing for Probabilistic Programs: An Overview2024
- The Prusti Project: Formal Verification for Rust2022
- Latticed k-Induction with an Application to Probabilistic Programs2021
- Deductive Software Verification – The KeY Book2016
- Fast Debugging of PRISM Models2014
- Counterexample Generation for Discrete-Time Markov Models: An Introductory Survey2014
- Enumerating Infeasibility: Finding Multiple MUSes Quickly2013
- Dafny: An Automatic Program Verifier for Functional Correctness2010
- Z3: An Efficient SMT Solver2008
- Counterexamples in Probabilistic Model Checking2007