💻 computer science

A Sound Translation from Tamarin to ProVerif: Enabling Comparative Analysis

This paper presents a sound translation from Tamarin to ProVerif that enables rigorous comparative analysis of security protocol verification tools by encoding Tamarin's multiset rewrite semantics into ProVerif's applied-pi calculus, achieving high coverage and significant performance gains while formally characterizing the limits of faithful translation.

Original authors: Kevin Morio, Yavor Ivanov, Robert Künnemann

Published 2026-08-07

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Kevin Morio, Yavor Ivanov, Robert Künnemann

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

Imagine you are a detective trying to solve a mystery, but instead of a crime scene, your "crime" is a secret code that might be broken by a sneaky hacker. In the world of computer security, these codes are called protocols—the rules that let your phone talk to a bank, or your game console talk to a server. The problem is, these rules are so complicated that even the smartest human detectives can miss a tiny loophole where a hacker could sneak in. So, scientists built "automated detectives," which are super-smart computer programs designed to check these rules for holes.

Two of the most famous automated detectives are named Tamarin and ProVerif. Think of them as two different types of investigators with very different styles. Tamarin is like a meticulous, slow-moving librarian who checks every single book on the shelf, one by one, to make sure nothing is missing. It is incredibly thorough and rarely makes mistakes, but it can take a long time to finish its work. ProVerif, on the other hand, is like a lightning-fast speed-reader who skims the shelves. It can check a massive library in seconds, but because it skims, it might sometimes think it found a problem where there isn't one (a "false alarm").

For years, these two detectives worked in separate offices. Because they spoke different "languages" and used different methods, it was nearly impossible to compare them directly. You couldn't easily ask, "Is ProVerif's speed worth the risk of missing a real problem?" or "Does Tamarin's slowness actually catch things ProVerif misses?" This paper is about building a magical translator that lets these two detectives talk to each other, allowing them to solve the same cases side-by-side to see who is faster, who is more accurate, and where their strengths lie.

The Great Detective Translator

The authors of this paper, Kevin Morio, Yavor Ivanov, and Robert Künnemann, built a sound translation tool. In the world of science, "sound" is a fancy way of saying "trustworthy." They created a system that takes a security protocol written in Tamarin's slow-but-precise language and automatically rewrites it into ProVerif's fast-but-skimming language.

But here's the tricky part: you can't just translate a book word-for-word if the two languages have different grammar rules. Tamarin uses a method called multiset rewrite rules, which is like having a pile of physical cards where you can only use a card once before it disappears. ProVerif uses something called the applied-π calculus, which is more like a digital database where entries can be copied and reused. To make the translation work, the authors invented new techniques to force ProVerif to act like it's using physical cards that disappear, ensuring it doesn't accidentally reuse a "card" and create a fake problem. They also figured out how to handle "simultaneous events"—moments where Tamarin says two things happen at the exact same time, while ProVerif insists everything happens one after another. They solved this by giving every event a unique ID tag, so ProVerif knows which events belong to the same moment.

What They Found: Speed vs. Accuracy

The team didn't just build the translator; they put it to the test. They took 121 different security models (think of these as 121 different lock-and-key systems) and ran them through both Tamarin and the new ProVerif translation.

The results were fascinating:

The Agreement: Out of 562 specific security checks (called "lemma tasks") that both tools could successfully run, 246 out of 247 of the non-tricky cases agreed perfectly. If Tamarin said "Safe," ProVerif said "Safe." If Tamarin found a "Hacker," ProVerif found the same "Hacker." The one case where they disagreed was flagged because the translation was incomplete for that specific model, not because the tools are fundamentally broken.
The Speed Gap: This is where ProVerif shines. When both tools finished a task, ProVerif was 6.74 times faster on average. In terms of memory (how much computer brainpower it used), ProVerif was 6.24 times more efficient.
- To put this in perspective: For a specific famous case study (the Lowe fix for the Andrew Secure RPC protocol), Tamarin took about 30 seconds to check five different security rules. ProVerif did the exact same job in just 0.46 seconds. That's a speedup of nearly 65 times for that specific test!
The "Best Effort" Warning: The authors were very careful to note that some features, like a specific math trick called XOR, couldn't be translated perfectly. For these cases, ProVerif's results are "best effort" approximations. In these tricky XOR cases, the tools disagreed more often (31 times out of 65), so the authors warn users not to trust those specific results as absolute proof.

Why This Matters

This paper doesn't claim that ProVerif is now "better" than Tamarin, or that Tamarin is obsolete. Instead, it proves that for a huge chunk of security problems (the "common core"), you can use the fast tool (ProVerif) with confidence, knowing that if it says a system is safe, the slow, meticulous tool (Tamarin) would agree.

The authors showed that by using their translation, security researchers can now use ProVerif as a "fast backend" to quickly check many ideas, while still having the option to use Tamarin for the final, most critical checks. It's like having a speed-reader who can scan a library in seconds to find the books you need, while knowing that the librarian is there to double-check the most important ones if you need 100% certainty.

In short, the paper successfully bridges the gap between two giants of computer security, proving that they can work together to make our digital world safer, faster, and more reliable.

Technical Summary: A Sound Translation from Tamarin to ProVerif

Problem Statement

Protocol verification tools like Tamarin and ProVerif are prominent in the formal analysis of security protocols, yet they operate on fundamentally different formalisms, hindering systematic comparison and the leveraging of their complementary strengths.

Tamarin utilizes Multiset Rewrite Rules (MSRs) with constraint solving. It offers sound and complete verification, eliminating spurious attacks, but can suffer from efficiency issues and non-termination.
ProVerif employs the applied- $\pi$ calculus with Horn clause abstraction. It is typically faster and avoids backtracking but may produce spurious attacks (incomplete results) due to over-approximation.

The lack of a translation mechanism between these tools makes it difficult to determine which properties are verifiable in both, to compare their performance on semantically equivalent models, or to use ProVerif as a fast backend for Tamarin models. Previous work has focused on translating from applied- $\pi$ to MSRs (e.g., SAPiC+ to Tamarin) or theoretical connections with limited scope, but a comprehensive, sound translation from Tamarin to ProVerif was missing.

Methodology

The authors present a sound translation from Tamarin to ProVerif that bridges the gap between MSRs and the applied- $\pi$ calculus. The translation is composed of three main components:

1. Rule Translation (Process Generation)

Tamarin rules are translated into parallel ProVerif processes.

State Management: Tamarin's multiset of facts is emulated using ProVerif's tables. Since ProVerif tables are monotonic (entries cannot be deleted), this initially over-approximates Tamarin's linear consumption of facts.
Multiset Semantics: To preserve the "consume once" semantics of linear facts, the translation introduces fresh rule-instance identifiers. For every linear storage fact, a unique identifier is generated and stored. A restriction is added to ensure that no two events with the same identifier and arguments occur, effectively enforcing linear consumption.
Pattern Matching: Tamarin allows pattern matching on facts (e.g., extracting variables from encrypted terms). ProVerif inputs only support tuple patterns. The translation introduces private auxiliary destructors to extract variables from complex patterns, ensuring these capabilities are not exposed to the attacker.
Communication: Network inputs (In) and outputs (Out) are mapped to ProVerif's in and out on a global public channel. Fresh names (Fr) map to new.

2. Lemma Translation (Property Rewriting)

Tamarin lemmas are translated into ProVerif queries. The translation handles the logical differences between Tamarin's two-sorted first-order logic and ProVerif's SA-QBF (Single-Alternation Quantified Boolean Formulas) fragment.

Quantifier Handling: Tamarin's explicit quantifiers are mapped to ProVerif's implicit quantification (universally quantified premise variables, existentially quantified conclusion variables).
Logical Rewriting:
- Disjunctions/Conjunctions: Top-level disjunctions in exists-trace lemmas and conjunctions in all-trace lemmas are split into multiple ProVerif queries. Results are recombined logically (e.g., the lemma holds if any split query holds for existence, or all for universality).
- Negation: ProVerif does not support negation in queries. The translation uses logical equivalences to move negations, often converting all-trace properties into reachability queries with inverted results.
Simultaneous Events: Tamarin allows multiple action facts at the same timepoint. The translation assigns a shared rule-instance identifier to events from the same rule, allowing ProVerif (which assumes a total order) to simulate simultaneity.
Knowledge Facts: Tamarin's K(m) (attacker explicitly derived m) is translated to ProVerif's attacker(m) under specific polarity constraints (positive atoms in the hypothesis of all-trace properties).

3. Bridging Semantic Gaps

Simultaneity: Handled via rule-instance identifiers to tie events together.
Implication Semantics: The translation accounts for subtle differences in how Tamarin and ProVerif interpret implication (=>) regarding temporal ordering, using progress restrictions where necessary.
Unsupported Features: Features like Tamarin's multiset built-ins, bilinear pairings, and Diffie-Hellman with inverse are excluded. XOR is translated as a "best-effort" approximation outside the soundness guarantees due to ProVerif's lack of associative symbols.

Key Contributions

Sound Translation: A formal translation from Tamarin to ProVerif that ensures any property verified in ProVerif (within the faithful fragment) also holds in the original Tamarin model.
Novel Encodings: Techniques for encoding multiset rewrite semantics (using identifiers and restrictions) and handling simultaneous events in a calculus that assumes total ordering.
Logic Fragment Characterization: Identification of the common core logic fragment (TSA-QBF) shared by both tools, defining exactly which properties can be faithfully translated.
Large-Scale Empirical Study: Evaluation on 121 Tamarin models containing 566 lemma tasks, providing the first large-scale comparative analysis of these tools on semantically equivalent models.

Results

The evaluation was conducted on 121 models (566 lemma tasks).

Translation Coverage: The translation successfully generated queries for 562 of 566 tasks (99.3%).
Agreement: Among non-XOR tasks with definitive results from both tools, 246 of 247 pairs agreed. The single disagreement was flagged as an incomplete model translation.
Performance:
- Speed: ProVerif was faster in 334 of 362 comparable cases (92.3%). The median runtime ratio was 6.74× in favor of ProVerif.
- Memory: ProVerif used significantly less memory, with a median peak memory ratio of 6.24× lower than Tamarin.
Case Study: In the Lowe's fix of the Andrew Secure RPC protocol, ProVerif was 64.7× faster across five agreeing lemmas, with the most complex injective agreement lemma being 129.6× faster.
Soundness Guarantees: The translation is sound for the faithful fragment. For exists-trace properties without attacker knowledge facts, the translation is also complete (if Tamarin finds a trace, ProVerif will find one).

Significance and Claims

The paper claims to provide a rigorous foundation for comparative analysis between Tamarin and ProVerif. By enabling the translation of Tamarin models to ProVerif, the authors demonstrate:

A substantial common core logic fragment exists between the two tools.
ProVerif's performance advantages (speed and memory efficiency) can be leveraged for Tamarin models without sacrificing soundness, provided the model stays within the faithful translation fragment.
The translation serves as a fast backend for Tamarin, allowing users to verify non-injective and injective agreement properties rapidly.
The work highlights semantic gaps (e.g., handling of XOR, multiset semantics, and negation) and precisely characterizes where translations are possible versus where they are best-effort approximations or impossible.

The authors emphasize that while the translation is not complete for all Tamarin features (specifically excluding multiset built-ins and certain DH models), it covers an extensive subset of practical security properties, enabling systematic empirical studies that were previously infeasible. The results suggest that for many standard protocols, ProVerif can serve as a highly efficient alternative or complement to Tamarin when used within the defined fragment boundaries.