A Kleene algebra with tests for union bound reasoning on probabilistic programs

Leandro Gomes (1, 2, 3) , Patrick Baillot (1, 2, 3) , Marco Gaboardi (4)

1 CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189
2 Université de Lille
3 SYCOMORES - Analyse symbolique et conception orientée composants pour des systèmes embarqués temps-réel modulaires
4 BU - Boston University [Boston]

Kleene Algebra with Tests (KAT) provides a framework for algebraic equational reasoning on imperative programs. The recent variant Guarded KAT (GKAT) allows to reason on non-probabilistic properties of probabilistic programs. Here we introduce an extension of this framework called aGKAT (approximate GKAT), a form of graded GKAT over a partially ordered monoid (real numbers) which enables to express satisfaction of (deterministic) properties except with a probability up to a certain bound. This allows to represent in equational reasoning 'à la KAT' proofs of probabilistic programs based on the union bound, a technique from basic probability theory. We show how a propositional variant of approximate Hoare Logic (aHL), a program logic for union bound, can be soundly encoded in our system aGKAT. We then illustrate the use of aGKAT on an example of accuracy analysis from the field of differential privacy.

Keywords: Kleene algebras with tests Hoare logic equational reasoning probabilistic programs union bound formal verification; Kleene algebras with tests; Hoare logic; equational reasoning; probabilistic programs; union bound; formal verification

Domains: Computer Science [cs]

Leandro Gomes, Patrick Baillot, Marco Gaboardi. A Kleene algebra with tests for union bound reasoning on probabilistic programs. 2023. ⟨hal-04196675⟩