Divergences on Monads for Relational Program Logics
arXiv:2206.05716 · doi:10.1017/S0960129523000245
Abstract
Several relational program logics have been introduced for integrating reasoning about relational properties of programs and measurement of quantitative difference between computational effects. Towards a general framework for such logics, in this paper, we formalize quantitative difference between computational effects as divergence on monad, then develop a relational program logic acRL that supports generic computational effects and divergences on them. To give a categorical semantics of acRL supporting divergences, we give a method to obtain graded strong relational liftings from divergences on monads. We derive two instantiations of acRL for the verification of 1) various differential privacy of higher-order functional probabilistic programs and 2) difference of distribution of costs between higher-order functional programs with probabilistic choice and cost counting operations.
arXiv commentPreprint
References in corpus (11)
- Renyi Differential Privacy
- Proving Differential Privacy via Probabilistic Couplings
- A Convenient Category for Higher-Order Probability Theory
- Monads need not be endofunctors
- Higher-Order Approximate Relational Refinement Types for Mechanism Design and Differential Privacy
- Proving differential privacy in Hoare logic
- Coupling proofs are probabilistic product programs
- Approximate Relational Hoare Logic for Continuous Random Samplings
- Hypothesis Testing Interpretations and Renyi Differential Privacy
- Approximate Span Liftings
- Coalgebraic Behavioral Metrics