Search papers, labs, and topics across Lattice.
This paper introduces a program transformation technique for probabilistic programs that enables reasoning about a wide range of objectives, including higher moments, threshold probabilities, and expected excess, using a single verification approach. The core idea involves adding reward statements to the language and applying a monotone function to the cumulative reward via incremental differences. By leveraging this transformation, diverse objectives can be analyzed using existing probabilistic weakest precondition (wp) reasoning techniques.
A single program transformation unlocks a unified approach to analyze diverse objectives on probabilistic programs, including higher moments and threshold probabilities, using existing wp-reasoning techniques.
We present a one-fits-all programmatic approach to reason about a plethora of objectives on probabilistic programs. The first ingredient is to add a reward-statement to the language. We then define a program transformation applying a monotone function to the cumulative reward of the program. The key idea is that this transformation uses incremental differences in the reward. This simple, elegant approach enables to express e.g., higher moments, threshold probabilities of rewards, the expected excess over a budget, and moment-generating functions. All these objectives can now be analyzed using a single existing approach: probabilistic wp-reasoning. We automated verification using the Caesar deductive verifier and report on the application of the transformation to some examples.
