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

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

TL;DR

This paper introduces a unified framework for relational verification—the art of proving properties that compare multiple executions of programs (e.g., "Do these two versions of a compiler produce equivalent code?"). By using monads to model program effects and a technique called reification to turn those effects into pure mathematical functions, the authors demonstrate that complex relational proofs in security, cryptography, and optimization can be handled efficiently within the F* proof assistant with high levels of SMT-based automation.

What Problem Does This Paper Address?

Most formal verification focuses on "unary" properties: "Does this single run of a program satisfy a specification?" However, many of the most important properties in computer science are relational. For example:

  • Program Equivalence: Does an optimized version of a function behave exactly like the original?
  • Information Flow: Does changing a "secret" input leave the "public" output unchanged (Non-interference)?
  • Cryptography: Is the output of an encryption algorithm indistinguishable from random noise?

Historically, researchers built specialized, "siloed" tools for each of these domains. These tools often struggle with "effectful" code—programs that use state, throw exceptions, or generate randomness. The authors aim to break these silos by providing a single, general-purpose methodology that handles diverse effects and relational properties in one place.

Methods

The authors leverage the F* programming language, which combines a functional language with an automated theorem prover (SMT solver). Their approach rests on three pillars:

  1. Monadic Modeling: They represent computational effects (like state or randomness) using monads. This is standard in functional programming, but here it serves as the foundation for formal reasoning.
  2. Monadic Reification: This is the "secret sauce." Reification is a mechanism that "peeks under the hood" of an effectful computation to reveal its underlying pure representation. For instance, a stateful command is reified into a pure function that takes an initial heap and returns a pair of (result, new heap).
  3. Relational Reasoning on Pure Terms: Once a program is reified into a pure function, the authors can use standard mathematical logic to compare two different reified programs. Because these are now just pure functions, F*’s SMT-based automation (Z3) can often prove their equivalence or relationship automatically.

This allows the programmer to write code in a natural, "direct" style while proving complex properties about that code "extrinsically" (after the fact).

Datasets

As a paper on formal verification and programming languages, it does not use traditional machine learning datasets. Instead, it evaluates the framework on a benchmark suite of case studies totaling approximately 4,300 lines of verified F* code. These include:

  • Relational Hoare Logic (RHL): Proving the soundness of a classic logic for program equivalence.
  • Information Flow Control: Implementing and verifying both static type systems and dynamic monitors for security.
  • Cryptographic Proofs: Verifying the "perfect secrecy" of a One-Time Pad and steps of the ElGamal encryption scheme.
  • Algorithmic Optimizations: Proving the correctness of complex data structures like Union-Find (with path compression and union-by-rank) and function memoization.

Key Insights and Ideas

  • The "Self-Specifying" Nature of Reification: Because reification exposes the actual implementation as a pure function, the code effectively becomes its own specification. You don't have to rewrite your logic in a separate modeling language to reason about it.
  • Arity is Just a Number: While many tools are hard-coded for "binary" relations (comparing 2 runs), this framework naturally scales to n-ary relations. The authors demonstrate this by using 4-ary and 6-ary relations to prove the correctness of the Union-Find algorithm.
  • Unified Security: The paper shows that "language-based security" (like type systems) and "cryptographic security" (probabilistic reasoning) can coexist in the same framework, allowing for "hybrid" proofs that were previously difficult to compose.

Key Results

  • Efficiency: The authors show that verifying relational properties requires "little additional effort" compared to standard unary properties.
  • Performance: The total verification time for the entire 4,300-line suite is about 23 minutes from scratch. However, using F's "proof caching" (hints), re-verifying the suite takes only about 2 minutes*, making it practical for interactive development.
  • Generality: They successfully encoded Benton’s 2004 Relational Hoare Logic and proved all its rules sound in about 1,500 lines of F*, proving the framework can act as a "meta-logic" for other verification systems.

Limitations and Future Work

  • Termination: The current framework primarily handles programs that are already proven to terminate. The authors want to extend "reification" to handle divergent (potentially infinite) computations, which is crucial for reasoning about interactive systems or servers.
  • Tactics: While SMT automation is powerful, it can sometimes be a "black box." The authors suggest using F's newer Meta-F tactics** system to give users more manual control over how proofs are structured, which could further reduce verification times.
  • Observational Purity: They aim to develop a way to "hide" effects that are used internally for performance (like a local state used for memoization) so the rest of the system sees the function as purely functional without needing to see the "reified" state.

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 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},
}

Loading related content...

Figure