A monadic framework for relational verification: applied to information security, program equivalence, and optimizations

Niklas Grimm, Kenji Maillard, Cédric Fournet, Cătălin Hriţcu, Matteo Maffei, Jonathan Protzenko, Tahina Ramananandro, 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 focuses on "unary" properties—determining if a single run of a program satisfies a given specification. However, many critical properties in computer science are inherently relational, comparing multiple executions. Examples include program equivalence (ensuring an optimization doesn't change behavior), information flow (ensuring secret inputs don't leak to public outputs), and cryptographic security (ensuring an algorithm's output is indistinguishable from random noise).

Historically, researchers have built specialized, siloed tools for these domains, which often struggle with "effectful" code involving state, exceptions, or randomness. This paper introduces a unified framework within the F* proof assistant to handle diverse effects and relational properties in a single, automated environment.

The Monadic Approach

The authors' methodology rests on three technical pillars:

  1. Monadic Modeling: Computational effects like state or randomness are represented using monads, providing a foundation for formal reasoning.
  2. Monadic Reification: This mechanism "peeks under the hood" of effectful computations to reveal their underlying pure representations. For example, a stateful command is reified into a pure function that maps an initial heap to a result and a new heap.
  3. Relational Reasoning on Pure Terms: Once reified, programs become pure mathematical functions. This allows the use of standard logic and F*’s SMT-based automation (Z3) to prove relationships between different executions.

This approach allows developers to write code in a natural style while proving complex properties "extrinsically" after the fact. Notably, the framework naturally scales to n-ary relations, demonstrated by using 4-ary and 6-ary relations to prove the correctness of the Union-Find algorithm.

Evaluation and Performance

The framework was evaluated against a benchmark suite of case studies totaling approximately 4,363 lines of verified F* code. These benchmarks cover a wide range of applications, from proving the soundness of Benton’s 2004 Relational Hoare Logic to verifying complex algorithmic optimizations like Union-Find with path compression.

Verification performance and code size for various relational verification case studies.

As shown in the performance data, the total verification time for the entire suite is approximately 23.5 minutes from scratch. However, by utilizing F*’s proof caching (hints), re-verification (replay) takes only about 2.17 minutes. This efficiency suggests that verifying relational properties requires little additional effort compared to standard unary properties, making it practical for interactive development.

Insights and Future Work

A key insight of this work is the "self-specifying" nature of reification: because it exposes the implementation as a pure function, the code effectively becomes its own specification. Furthermore, the framework allows "hybrid" proofs where language-based security (type systems) and cryptographic security (probabilistic reasoning) can coexist.

Future work aims to extend reification to handle divergent (potentially infinite) computations and to utilize Meta-F* tactics for finer control over proof structures. The authors also intend to explore "observational purity" to hide internal effects used for performance, such as local state in memoization, 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 Cătălin Hriţcu and Matteo Maffei and Jonathan Protzenko and Tahina Ramananandro and Aseem Rastogi and Nikhil Swamy and Santiago Zanella-Béguelin},
  title = {{A monadic framework for relational verification: applied to information security, program equivalence, and optimizations}},
  booktitle = {CPP},
  year = {2018},
  url = {https://openreview.net/forum?id=YL3hcyLn_1},
}
Figure