On Automated Verification of Probabilistic Programs

Axel Legay, Andrzej S. Murawski, Joël Ouaknine, James Worrell

Abstract

Randomized algorithms and cryptographic protocols are essential to modern computing but remain notoriously difficult to verify. Traditional model checking often fails to handle modular "open" programs or complex properties like anonymity. This paper introduces APEX, a tool that leverages game semantics and probabilistic automata to verify contextual equivalence in probabilistic programs. APEX demonstrates significant performance gains, achieving linear scaling on benchmarks where state-of-the-art tools exhibit exponential growth.

Introduction

Proving the correctness of randomized systems is a significant challenge in formal methods. While traditional model checking evaluates whether a system satisfies a specific logic formula, it often struggles with two critical areas: open programs (modular code with undefined external components) and contextual equivalence. The latter is particularly vital for verifying anonymity; for instance, a protocol is anonymous if an observer cannot distinguish between different users performing the same action.

Existing models, such as Markov chains, frequently suffer from "state-space explosion," rendering them impractical for large-scale protocols. APEX addresses these limitations by shifting the focus to game-theoretic modeling and automata-based equivalence checking.

Methodology: Game Semantics and Automata

APEX operates on a procedural probabilistic programming language. Its core innovation lies in its verification pipeline:

  1. Game Semantics: Instead of tracking internal states, APEX models programs as "strategies" in a game against an environment. This allows the tool to represent open programs by capturing interactions with external components.
  2. Probabilistic Automata: These strategies are translated into probabilistic automata. The problem of contextual equivalence is then reduced to checking if two automata accept the same "language."
  3. Decidability: The researchers proved that for programs with finite datatypes and no recursion, equivalence checking is decidable and can be solved in polynomial time.
  4. Optimization: The tool employs reachability analysis and probabilistic bisimulation to merge redundant states, significantly simplifying the resulting automata.
Probabilistic automata representing program strategies for equivalence checking.

Case Studies and Key Insights

The authors evaluated APEX using classic benchmarks, including Herman’s self-stabilization algorithm and Hibbard’s binary search tree algorithm. However, the most notable application was the Dining Cryptographers Protocol, a standard benchmark for anonymity.

Anonymity as Equivalence

The key insight provided by the authors is that anonymity is best modeled as an equivalence. If the observable output of a protocol remains identical regardless of which participant is the "payer," the protocol is mathematically anonymous. By using bisimulation reduction, APEX factors out symmetries in the protocol. While the raw state space grows exponentially with the number of participants, the optimized probabilistic automata grow only linearly.

Performance Results

APEX was compared against PRISM, a leading probabilistic model checker. The results highlight a dramatic difference in scalability:

# Cryptographers PRISM (seconds) APEX (seconds)
3 4 7
10 > 1 hour 11
15 Out of Memory (OOM) 13
100 OOM 125

While PRISM hits a performance "brick wall" at 15 participants, APEX successfully verifies 100 participants in approximately two minutes. This exponential speed-up demonstrates the power of game-theoretic abstraction in handling symmetric, probabilistic systems.

Conclusion and Future Work

APEX represents a significant step forward in the automated verification of probabilistic software. By focusing on contextual equivalence and leveraging game semantics, it enables the modular verification of complex protocols that were previously unreachable.

Future work aims to expand the language's capabilities by adding support for pointers, dynamic data structures, and recursion. Additionally, the researchers plan to extend the framework to handle nondeterminism and concurrent distributed systems, further broadening the tool's applicability to real-world cryptographic software.

Summary updated

Abstract

We introduce a simple procedural probabilistic programming language which is suitable for coding a wide variety of randomised algorithms and protocols. This language is interpreted over finite datatypes and has a decidable equivalence problem. We have implemented an automated equivalence checker, which we call apex, for this language, based on game semantics. We illustrate our approach with three non-trivial case studies: (i) Herman’s self-stabilisation algorithm; (ii) an analysis of the average shape of binary search trees obtained by certain sequences of random insertions and deletions; and (iii) the problem of anonymity in the Dining Cryptographers protocol. In particular, we record an exponential speed-up in the latter over state-of-the-art competing approaches.
BibTeX
@inproceedings{legay2008automated,
  author = {Axel Legay and Andrzej S. Murawski and Joël Ouaknine and James Worrell},
  title = {{On Automated Verification of Probabilistic Programs}},
  booktitle = {TACAS},
  year = {2008},
  doi = {10.1007/978-3-540-78800-3\_13},
}
Figure