MASTA: A Feedback-Scheduled Multi-Agent System for End-to-End Tamarin Modeling and Analysis

Yongkang Xiao, Qiyi Deng, Jing Chen, Min Shi, Ju Ma, Ruiying DuarXiv 2026 · arXiv

TL;DR

MASTA is a multi-agent framework that automates the formal verification of security protocols by translating natural language descriptions into complex Tamarin models. By separating the roles of "authoring" and "evaluating" across specialized agents and using real-time feedback from the Tamarin prover, it outperforms much larger models like GPT-5.5 and Claude 4.7 in generating correct, verifiable security proofs.

What Problem Does This Paper Address?

Formal verification is the "gold standard" for ensuring security protocols (like TLS 1.3 or 5G authentication) are actually secure. The Tamarin prover is a leading tool for this, but it has a notoriously high barrier to entry. Users must translate informal prose into "multiset rewriting rules" and "temporal-logic lemmas"—a task that requires deep domain expertise.

While Large Language Models (LLMs) are great at coding, they struggle with Tamarin for two reasons:

  1. Compounding Errors: A small syntactic mistake in an early rule breaks reachability for the entire model, making it impossible to verify later properties.
  2. The Self-Evaluation Trap: A single LLM agent that both writes and checks its own formal logic often fails to "see" its own mistakes, leading to a "hallucination loop" where it insists a broken model is correct.

Methods

The authors introduce MASTA (Multi-Agent System for Tamarin-based Analysis), which breaks the modeling process into a structured, three-agent pipeline:

  • The Architect: Responsible for modeling the protocol behavior and adversary capabilities as multiset rewriting rules. It focuses on "executability"—ensuring the protocol can actually run from start to finish.
  • The Auditor: Extracts security requirements (like secrecy and authentication) from the text and encodes them as formal lemmas.
  • The Arbiter: The "manager" who holds no authoring duties. It monitors Tamarin’s output after every step. If the verifier returns an error, the Arbiter diagnoses the problem using a six-class taxonomy and dispatches a "fix-job" to the responsible agent.

Crucially, MASTA uses Action Blocks—a structured intermediate representation—to bridge the gap between messy natural language and rigid formal code. The system also features a deduplication check to prevent the agents from trying the same failed fix repeatedly.

Datasets

The researchers developed a robust new benchmark to test the system:

  • 10 Standard Protocols: Including well-known examples like the Needham-Schroeder and ISO-9798 protocols.
  • 139 Mutation Variants: They didn't just test the "correct" versions; they created variants with deliberate operational changes and injected vulnerabilities to see if the system could faithfully model and detect them.
  • Five Metrics ($M_1$–$M_5$): These measure everything from "process fidelity" (did it get the message flow right?) to "vulnerability detection" (did it catch the injected bugs?).

Key Insights and Ideas

  • Architecture Trumps Scale: One of the most striking findings is that MASTA, running on the mid-tier Qwen 3.5-plus backbone, outperformed "frontier" models like Codex (GPT-5.5) and Claude Code (Opus 4.7). This suggests that for highly specialized formal reasoning, a well-designed multi-agent workflow is more effective than simply using a larger model.
  • The Arbiter is Essential: Ablation studies showed that removing the Arbiter (the independent evaluator) caused the system's performance to collapse to zero on several metrics. You cannot trust a generator to be its own judge in formal logic.
  • Tool-Anchored Supervision: Instead of asking an LLM "is this right?", MASTA asks the Tamarin prover. By grounding the agent's "reasoning" in the objective verdicts of a symbolic verifier, the system eliminates the subjectivity that usually plagues LLM-based coding.

Key Results

  • Perfect Vulnerability Detection: MASTA achieved a 1.000 score on $M_5$, meaning it correctly identified every single security flaw injected into the benchmark protocols.
  • Superior Correctness: It improved over the baseline (OpenCode) on the same LLM backbone by up to +0.27 on individual metrics.
  • Efficiency: Despite the complex multi-agent loop, the median task took about 17 minutes—well within the one-hour budget—proving that automated formal verification is becoming computationally practical.

Limitations and Future Work

The authors acknowledge several hurdles:

  • Complexity Cap: The current benchmark is limited to protocols that Tamarin can verify within ten minutes. Massive, industrial-scale protocols might still exhaust the system's time or context-window limits.
  • Data Contamination: Because some protocols are famous, the LLMs might have seen their Tamarin models during pre-training.
  • Tool Specificity: MASTA is currently "hard-wired" for Tamarin. Adapting it to other tools like ProVerif or CryptoVerif would require significant changes to the prompt templates and error taxonomies.

In the future, the team aims to test MASTA against real-world CVEs (Common Vulnerabilities and Exposures) to see if it can reproduce known attacks on deployed systems.

Summary updated

Abstract

Tamarin-based formal verification of security protocols requires expert-authored multiset rewriting rules and temporal-logic lemmas. Translating a natural-language protocol description into a complete formal model with an LLM is hard because syntactic, reachability, and property-level errors compound across the multi-step modeling process, and a single agent that both authors and self-evaluates cannot reliably localize them. We present MASTA, a multi-agent system that addresses these difficulties through three innovations. First, an operational--evaluative role decomposition assigns rule modeling to an Architect, property modeling to an Auditor, and pure dispatch to a dedicated Arbiter that holds no authoring duties. Second, the Arbiter implements a Tamarin-anchored scheduler that dispatches the next agent based on the latest verifier verdict and routes problem-tagged fixes through a modification list, with a six-class problem taxonomy and an LLM deduplication check preventing routing deadlock. Third, we construct a benchmark of 10 protocols paired with 139 mutation variants and five fine-grained metrics that jointly assess model correctness ($M_1$--$M_3$) and completeness ($M_4$--$M_5$). On this benchmark, MASTA on Qwen 3.5-plus improves over OpenCode on the same backbone by up to $+0.27$ on individual metrics and ranks first on both the correctness and completeness averages, surpassing Codex (GPT-5.5) and Claude Code (Opus 4.7) despite using a weaker LLM. Ablations on five protocols confirm that removing the Arbiter collapses property and verification scores to zero.
BibTeX
@misc{xiao2026masta,
  author = {Yongkang Xiao and Qiyi Deng and Jing Chen and Min Shi and Ju Ma and Ruiying Du},
  title = {{MASTA: A Feedback-Scheduled Multi-Agent System for End-to-End Tamarin Modeling and Analysis}},
  year = {2026},
  eprint = {2611.20671},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.20671},
}
Figure