Automatic Generation of Moment-Based Invariants for Prob-Solvable Loops
Authors:
Preprint
Abstract
One of the main challenges in the analysis of probabilistic programs is to compute invariant properties that summarise loop behaviours. Automation of invariant generation is still at its infancy and most of the times targets only expected values of the program variables, which is insufficient to recover the full probabilistic program behaviour. We present a method to automatically generate moment-based invariants of a subclass of probabilistic programs, called Prob-Solvable loops, with polynomial assignments over random variables and parametrised distributions. We combine methods from symbolic summation and statistics to derive invariants as valid properties over higher-order moments, such as expected values or variances, of program variables. We successfully evaluated our work on several examples where full automation for computing higher-order moments and invariants over program variables was not yet possible.Keywords
All Related Versions
This publication has 16 references indexed in Scilit:
- Tail Probabilities for Randomized Program Runtimes via Martingales for Higher Moments2019
- Termination of Nondeterministic Probabilistic Programs2019
- Aligator.jl – A Julia Package for Loop Invariant Generation2018
- Finding Polynomial Loop Invariants for Probabilistic Programs2017
- A Storm is Coming: A Modern Probabilistic Model Checker2017
- Counterexample-Guided Polynomial Loop Invariant Generation by Lagrange Interpolation2015
- Expectation Invariants for Probabilistic Program Loops as Fixed Points2014
- Prinsys—On a Quest for Probabilistic Loop Invariants2013
- PRISM 4.0: Verification of Probabilistic Real-Time Systems2011
- Reasoning Algebraically About P-Solvable Loops2008