A Monadic Framework for Relational Verification (Functional Pearl)

Niklas Grimm, Kenji Maillard, Cédric Fournet, Catalin Hritcu, Matteo Maffei, Jonathan Protzenko, Aseem Rastogi, Nikhil Swamy, Santiago Zanella Béguelin

Abstract

Relational properties describe multiple runs of one or more programs. They characterize many useful notions of security, program refinement, and equivalence for programs with diverse computational effects, and they have received much attention in the recent literature. Rather than developing separate tools for special classes of effects and relational properties, we advocate using a general purpose proof assistant as a unifying framework for the relational verification of effectful programs. The essence of our approach is to model effectful computations using monads and to prove relational properties on their monadic representations, making the most of existing support for reasoning about pure programs. We apply this method in F and evaluate it by encoding a variety of relational program analyses, including information flow control, program equivalence and refinement at higher order, correctness of program optimizations and game-based cryptographic security. By relying on SMT-based automation, unary weakest preconditions, user-defined effects, and monadic reification, we show that, compared to unary properties, verifying relational properties requires little additional effort from the F programmer.

Introduction

Most formal verification tools are designed to check "unary" properties—questions about a single execution of a program, such as whether it crashes or returns a specific type. However, many of the most critical properties in computer science are relational. These properties compare multiple runs of one or more programs. Examples include program equivalence (ensuring an optimization doesn't change behavior), information flow control (ensuring secrets don't leak to public outputs), and cryptographic security (ensuring outputs are indistinguishable from noise).

Traditionally, these problems required specialized, "one-off" tools or complex relational logics that struggle with higher-order code or diverse computational effects like state and randomness. This paper introduces a unified framework in the F programming language that addresses these challenges by transforming complex, effectful programs into pure mathematical functions through monadic reification*.

Methodology

The framework is built upon three primary pillars within the F* ecosystem:

  1. Monads for Effects: Computational effects, such as memory manipulation or exceptions, are modeled using monads. This provides a structured mathematical foundation for handling side effects.
  2. Monadic Reification: This is the core technical innovation. Reification is a mechanism that exposes the underlying pure representation of an effectful computation. For instance, a stateful function is reified into a pure function that explicitly maps an initial state to a result and a final state.
  3. Extrinsic Reasoning: Instead of embedding complex relational properties directly into function types (intrinsic), the authors write code naturally and then prove lemmas about the reified versions of those programs (extrinsic).

By converting effectful code into pure functions, the framework leverages F*’s powerful SMT-based automation (via the Z3 solver) to handle the mechanical parts of the proof, while the developer focuses on high-level inductive insights.

Evaluation and Case Studies

As a "Functional Pearl," the paper evaluates the framework through a diverse suite of benchmarks totaling approximately 4,363 lines of code. These case studies demonstrate the framework's versatility across different domains:

  • Algorithmic Optimizations: Proving the correctness of a Union-Find data structure with path compression and rank-based merging.
  • Information Flow Control (IFC): Encoding classic static and dynamic IFC monitors to ensure non-interference.
  • Cryptography: Proving the "perfect secrecy" of a One-Time Pad and verifying steps of ElGamal encryption.
  • Compiler Transformations: Verifying loop hoisting and deriving Benton’s Relational Hoare Logic (RHL).
Verification performance and code size across various benchmarks.

The empirical results, summarized in the table above, highlight the efficiency of the SMT-based approach. While initial verification (1st run) can take several minutes for complex proofs, the use of SMT "hints" (unsat cores) allows for rapid re-verification. For example, the complex Union-Find proof drops from approximately 90 seconds to 33 seconds on replay. Across all benchmarks, the total replay time is less than 10% of the initial run time.

Key Insights

  • Self-Specifying Reification: Because reification reveals the pure logic of an effectful program, the code effectively becomes its own specification, removing the need to rewrite logic in a separate modeling language.
  • Beyond Syntactic Similarity: Unlike many prior relational logics that required programs to have nearly identical structures, this framework can reason about entirely different algorithms (e.g., comparing memoization to recursion) because it focuses on the underlying mathematical mapping.
  • Arity Independence: While most tools are limited to binary relations (comparing two runs), this framework naturally scales to $n$-ary relations. This was essential for the Union-Find example, which required comparing four different execution states simultaneously.

Conclusion and Future Work

The framework successfully unifies disparate fields under a single proof methodology, making relational verification feel nearly as accessible as standard unary verification. However, some challenges remain. The current framework is best suited for programs that are intrinsically proved to terminate; handling potentially diverging programs requires additional complexity like step-indexing. Future work aims to leverage F’s "Meta-F" tactics system to further automate lemma application and to implement "observational purity" to hide stateful optimizations from the rest of the system.

Summary updated

Abstract

Relational properties describe multiple runs of one or more programs. They characterize many useful notions of security, program refinement, and equivalence for programs with diverse computational effects, and they have received much attention in the recent literature. Rather than developing separate tools for special classes of effects and relational properties, we advocate using a general purpose proof assistant as a unifying framework for the relational verification of effectful programs. The essence of our approach is to model effectful computations using monads and to prove relational properties on their monadic representations, making the most of existing support for reasoning about pure programs. We apply this method in F* and evaluate it by encoding a variety of relational program analyses, including information flow control, program equivalence and refinement at higher order, correctness of program optimizations and game-based cryptographic security. By relying on SMT-based automation, unary weakest preconditions, user-defined effects, and monadic reification, we show that, compared to unary properties, verifying relational properties requires little additional effort from the F* programmer.
BibTeX
@inproceedings{grimm2018monadic,
  author = {Niklas Grimm and Kenji Maillard and Cédric Fournet and Catalin Hritcu and Matteo Maffei and Jonathan Protzenko and Aseem Rastogi and Nikhil Swamy and Santiago Zanella Béguelin},
  title = {{A Monadic Framework for Relational Verification (Functional Pearl)}},
  booktitle = {CPP},
  year = {2018},
  url = {https://openreview.net/forum?id=YL3hcyLn_1},
}
Figure