💻 computer science

Misquoted No More: Securely Extracting F* Programs with IO

This paper introduces SEIO*, a framework that combines relational quotation with verified syntax generation to securely extract shallowly embedded F* programs with IO and refinement types into a deeply embedded calculus, providing machine-checked proofs of Robust Relational Hyperproperty Preservation (RrHP) to guarantee security against arbitrary adversarial linking.

Original authors: Cezar-Constantin Andrici, Abigail Pribisova, Danel Ahman, Catalin Hritcu, Exequiel Rivas, Théo Winterhalter

Published 2026-07-20

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Cezar-Constantin Andrici, Abigail Pribisova, Danel Ahman, Catalin Hritcu, Exequiel Rivas, Théo Winterhalter

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Invisible Safety Net

Imagine you are a master architect who has designed a magnificent, self-driving car in a perfect, imaginary world where physics always behaves exactly as you predict. You have written the blueprints in a special, super-precise language that allows you to mathematically prove the car will never crash, never brake when it shouldn't, and always follow the rules of the road. This is what computer scientists call "formal verification." It's like building a car in a dream where you can be 100% sure of every bolt and wire.

But here's the catch: that dream world doesn't exist on the real road. To actually drive the car, you have to translate your perfect blueprints into a language that real engines and tires understand, like C or OCaml. This translation process is called "extraction." The problem is, the translator (the computer program that does the conversion) isn't perfect. It might drop a bolt, twist a wire, or misunderstand a rule. If the real-world car is built on a mistake made during translation, your perfect proof of safety becomes useless. The car might look safe on paper but crash in reality.

For years, scientists have tried to fix this by checking the translator's work after the fact, kind of like a mechanic inspecting a car after it's built to see if it matches the plans. But this paper introduces a smarter way: instead of just checking the finished car, they build a "safety certificate" during the translation that proves, mathematically, that the real car is a perfect twin of the dream car, even if the translator makes a mistake. They call this a "secure extraction" framework, and it's designed to keep your digital creations safe even when they are mixed with messy, unverified code from the outside world.

The Paper's Big Idea: The "Relational Quotation" Magic Trick

The authors of this paper, a team of computer scientists, have built a new framework called SEIO★ (Secure Extraction of IO-star). Their goal was to solve the "translation problem" for programs written in F★, a language used to write highly secure software like cryptographic tools. These F★ programs are often "shallowly embedded," which is a fancy way of saying they are written in a high-level, abstract style that's great for proving things but hard for computers to turn into real code.

Usually, when you turn these abstract programs into real code, you have to use a "metaprogram" (a program that writes other programs) to do the heavy lifting. The old way of doing this was risky: the metaprogram would write the new code and then try to write a proof that the new code was correct. If the proof failed, you'd have to start over. If the proof passed, you still had to trust that the metaprogram didn't sneak in a bug while writing the proof. It was like asking a student to grade their own homework and hoping they didn't cheat.

The authors' breakthrough is a technique they call Relational Quotation. Instead of asking the metaprogram to write the final code and the proof, they ask it to do something much simpler: write a typing derivation. Think of this as a step-by-step recipe card that says, "Step 1: Take this ingredient. Step 2: Mix it with that." This recipe card doesn't actually cook the meal; it just proves that the ingredients could be cooked into a specific dish.

Here is the clever part:

The Metaprogram (The Recipe Writer): The unverified metaprogram looks at the original abstract program and generates this "recipe card" (the typing derivation). Because the recipe card follows the exact structure of the original program, it's very easy to write.
The Check (The Inspector): The F★ language itself checks this recipe card. It asks, "Does this recipe actually describe the original program?" If the metaprogram made a mistake and wrote a recipe for a cake when the original was a soup, the check fails. But if the recipe matches, the F★ language is 100% sure that the recipe is valid.
The Verified Step (The Master Chef): Once the recipe card is verified, a different, fully verified function (a "Master Chef" that has been mathematically proven to be perfect) takes that recipe and cooks the final dish (the real code). Because the recipe was proven to match the original, and the chef is proven to cook exactly what the recipe says, the final dish is guaranteed to be a perfect twin of the original.

This approach minimizes the "trust" we have to place in the unverified metaprogram. We only trust it to write the recipe, not to cook the food or grade the homework. The hard part—proving the food is safe—is done by the verified Master Chef.

The "Secure Compilation" Superpower

The paper doesn't just stop at making sure the code is correct; it goes a step further to ensure it is secure. In the real world, your verified program might get linked with other code that is not verified—maybe code written by a hacker, or just sloppy code from a different team. This "adversarial" code tries to break your program's rules.

The authors prove that their SEIO★ framework satisfies a super-strong security rule called Robust Relational Hyperproperty Preservation (RrHP). To understand this, imagine your verified program is a fortress.

Old methods might say, "The fortress walls are strong, so it's safe."
This paper says, "Even if a hacker tries to sneak in through the back door, or if they try to trick the guards, or if they try to change the rules of the game, your fortress will still behave exactly as you designed it."

They prove this using two "logical relations," which are like two-way mirrors. One mirror checks if the real code does everything the abstract code could do. The other checks if the real code doesn't do anything the abstract code couldn't do. By proving both, they show that the real code is a perfect, secure shadow of the original, no matter what messy code it gets linked with.

What They Actually Did (and Didn't Do)

The team built this framework entirely inside the F★ language and used a computer to check every single step of their proof. They didn't just guess or simulate; they proved it mathematically.

What works: They successfully extracted programs that handle file Input/Output (reading and writing files) and use "refinement types" (types with extra rules, like "this number must be positive"). They showed that even with these complex features, the extraction remains secure.
What's still a work in progress: The paper admits that their current system doesn't handle recursive functions (functions that call themselves) or full "dependent types" (where types can depend on values) in the most natural way. They had to use a workaround involving iterators (loops) for recursion. They also note that their metaprogram sometimes has to guess where to put certain safety checks, which can be a bit clunky.
The Bottom Line: They haven't solved every problem in the universe of programming, but they have built a new, much safer bridge between the world of perfect proofs and the messy world of real code. They proved that by splitting the job into a "recipe writing" phase and a "cooking" phase, you can get strong security guarantees without having to trust the recipe writer completely.

In short, SEIO★ is a new tool that lets programmers take their perfect, verified ideas and turn them into real-world software with a mathematically guaranteed safety net, ensuring that even if the translation process is imperfect, the final result is still safe from the chaos of the outside world.

Technical Summary: Misquoted No More: Securely Extracting F★Programs with IO

1. Problem Statement

The F★ proof-oriented language is widely used for writing and verifying programs that are shallowly embedded using monads to represent effects (e.g., I/O). Once verified, these programs are typically extracted to mainstream languages like OCaml or C for execution. However, this extraction process is currently unverified and constitutes part of the trusted computing base (TCB).

The core challenge lies in the "quotation" step required to extract shallowly embedded programs. Quotation involves translating a shallowly embedded program (where effects are represented by monadic types) into a deeply embedded syntax tree (a concrete representation of the target language). Verifying this quotation metaprogram is a major open challenge because it requires a mechanized meta-theory for the source language, and even for mature systems like Rocq, verifying quotation remains unsolved.

Prior approaches to certifying extraction rely heavily on translation validation, where a metaprogram generates both the extracted code and a proof of correctness, which is then type-checked. While this reduces the TCB compared to verifying the metaprogram, it still relies on the metaprogram to generate valid proofs, which can fail or be incorrect. Furthermore, existing work focuses primarily on correctness (preserving functional behavior) rather than security. When extracted code is linked with unverified adversarial code, the formal guarantees of the original verified program can be compromised, leading to unsoundness or security breaches.

2. Methodology

The authors introduce SEIO★, a framework for extracting shallowly embedded F★ programs with I/O and refinement types to a deeply embedded simply typed $\lambda$ -calculus ( $\lambda_{io}$ ). The methodology splits the extraction process into two distinct phases to minimize reliance on translation validation:

Phase 1: Relational Quotation (Translation Validation)
Instead of directly generating the target code, the framework uses a metaprogram to generate a typing derivation for the original shallowly embedded program.

Relational Typing Relation: The authors define a typing relation that characterizes the subset of F★ (called IO★) being extracted. This relation operates on "open F★ values" (functions from evaluation environments to values) rather than syntactic expressions, allowing it to handle free variables in a shallow embedding.
Metaprogram: A simple metaprogram traverses the structure of the source program and constructs a corresponding typing derivation.
Validation: The generated derivation is type-checked by F★. Because the typing relation uses dependent types, the type-checker verifies that the derivation corresponds syntactically and semantically to the original program. This step is the only part relying on translation validation.

Phase 2: Verified Syntax Generation
Once a valid typing derivation is obtained, a pure, verified F★ function recursively traverses the derivation to generate the target $\lambda_{io}$ syntax.

Since the typing derivation is structurally linked to the source program via dependent types, the syntax generation function is guaranteed to produce code semantically related to the original.
This step is fully verified within F★, eliminating the need for translation validation in the code generation phase.

Security Guarantees via Logical Relations
To prove security, the authors define two cross-language logical relations between the source (IO★) and target ( $\lambda_{io}$ ) languages:

Target-to-Source: Relates a target program to a source program, ensuring every target behavior has a corresponding source behavior.
Source-to-Target: Relates a source program to a target program, ensuring every source behavior has a corresponding target behavior.

These relations are defined over trace-producing semantics, where I/O operations generate events (traces). The authors prove that SEIO★ satisfies Robust Relational Hyperproperty Preservation (RrHP), the strongest secure compilation criterion defined by Abate et al. [1]. RrHP implies full abstraction (preservation of observational equivalence) and the preservation of trace properties and hyperproperties (e.g., noninterference) against arbitrary adversarial contexts.

Handling Refinement Types
The framework is extended to support refinement types (logical constraints on types). Since F★ discharges refinement proofs using SMT solvers without producing explicit proof terms, the relational quotation metaprogram must recompute the weakest preconditions from scratch during quotation and re-prove them to ensure the typing derivation remains valid.

3. Key Contributions

Relational Quotation: A novel translation validation technique that uses dependent types to define a typing relation for shallowly embedded programs. It allows a metaprogram to generate a typing derivation that is type-checked to ensure it corresponds to the source program, avoiding the need to verify the metaprogram itself.
SEIO★ Framework: A complete extraction framework for F★ programs with I/O and refinement types, extracting them to a deeply embedded $\lambda$ -calculus.
Formal Secure Compilation: A machine-checked proof in F★ that SEIO★ satisfies RrHP. This is the first extraction framework for a proof-oriented language to provide such strong security guarantees against arbitrary linked adversarial code.
Cross-Language Logical Relations: The definition and proof of two asymmetric logical relations that bridge the gap between a shallowly embedded language with trace-producing semantics and a deeply embedded language with standard operational semantics.
Refinement Type Support: An extension of the framework to handle refinement types by recomputing and re-verifying preconditions during quotation.

4. Results

The authors implemented SEIO★ in F★, including over 900 top-level definitions.
They successfully extracted a running example: a validation wrapper for unverified AI agents that reads a file, calls an agent, and verifies the result.
The framework was tested with various agents (both correct and malicious) written directly in the target $\lambda_{io}$ language.
The machine-checked proof confirms that the extraction preserves safety properties even when linked with arbitrary unverified code, satisfying RrHP.
The artifact includes a pipeline to compile the extracted $\lambda_{io}$ code to OCaml using the Peregrine framework and Malfunction, allowing for practical execution.

5. Significance and Claims

The paper claims to advance the state of the art in two key ways:

Minimizing Translation Validation: By confining translation validation to the generation of a typing derivation (relational quotation) and verifying the subsequent syntax generation step, the framework reduces the reliance on unverified metaprograms compared to prior certifying extraction work.
Security over Correctness: Unlike previous work that focused on functional correctness, SEIO★ provides formal secure compilation guarantees. It ensures that verified F★ programs retain their security properties (such as noninterference and trace properties) even when linked with arbitrary, unverified, or adversarial code.

The authors note that this work goes beyond the current state of the art, which has not yet provided such strong secure compilation guarantees for extraction from proof-oriented languages. They acknowledge limitations, such as the current lack of support for general recursive functions and full dependent types, which are left as future work. The paper emphasizes that while the relational quotation metaprogram is unverified, its simplicity and the rigorous verification of the subsequent steps make the overall approach robust.