Error Localization, Certificates, and Hints for Probabilistic Program Verification via Slicing (Extended Version)
Authors:
- Darion HaaseDHDarion Haase
- Joost-Pieter KatoenJKJoost-Pieter Katoen
Preprint
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 \emph{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 39 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
- A Theory of Slicing for Probabilistic Control Flow Graphs2016
- Viper: A Verification Infrastructure for Permission-Based Reasoning2015
- On the Hardness of Almost–Sure Termination2015
- Counterexample Generation for Discrete-Time Markov Models: An Introductory Survey2014
- Probabilistic Program Analysis with Martingales2013
- Enumerating Infeasibility: Finding Multiple MUSes Quickly2013
- Dafny: An Automatic Program Verifier for Functional Correctness2010