MASTA: A Feedback-Scheduled Multi-Agent System for End-to-End Tamarin Modeling and Analysis
Organizations: School of Cyber Science and Engineering, Wuhan University
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 (--) and completeness (--). On this benchmark, MASTA on Qwen 3.5-plus improves over OpenCode on the same backbone by up to 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.
Figures & tables
| Job | Owner | Input | Output |
|---|---|---|---|
| J1 Action serialization | Architect | Protocol document | Structured action blocks |
| J2 Security-requirement extraction | Auditor | Protocol document | Structured security requirements |
| J3 Rule modeling | Architect | Action blocks | Tamarin rules + exec. verdicts |
| J4 Property modeling | Auditor | Security requirements | Tamarin lemmas + lemma verdicts |
| J5 Workflow scheduling | Arbiter | State + verdicts | Dispatch instruction |
| System | LLM | Avg(Corr) | Avg(Comp) | |||||
|---|---|---|---|---|---|---|---|---|
| Codex | GPT-5.5 | 0.615 | 0.586 | 0.534 | 0.578 | 0.757 | 0.961 | 0.859 |
| Claude Code | Opus 4.7 | 0.724 | 0.643 | 0.594 | 0.654 | 0.758 | 0.753 | 0.756 |
| OpenCode | Qwen 3.5-plus | 0.762 | 0.430 | 0.526 | 0.573 | 0.668 | 0.866 | 0.767 |
| Masta (Ours) | Qwen 3.5-plus | 0.829 | 0.699 | 0.567 | 0.698 | 0.745 | 1.000 | 0.873 |
| Variant | Avg(Corr) | Avg(Comp) | |||||
|---|---|---|---|---|---|---|---|
| Masta (Ours) | 0.898 | 0.553 | 0.363 | 0.605 | 0.811 | 1.000 | 0.905 |
| w/o Role Specialization | 0.580 | 0.339 | 0.167 | 0.362 | 0.511 | 0.571 | 0.541 |
| w/o Arbiter | 0.358 | 0.000 | 0.000 | 0.119 | 0.321 | 0.000 | 0.161 |
| System | Tamarin calls | Wall-clock time | API tokens |
|---|---|---|---|
| Masta | 1,567 | 52.3 h | 111.1 M |
| Codex | 863 | 8.7 h | 81.5 M |
| Claude Code | 966 | 55.4 h | 184.0 M |
| OpenCode | 3,728 | 39.6 h | 424.5 M |
Appendix figures & tables4 assets
Supplementary material from the paper’s appendix.
Appendix
| Type | Semantics |
|---|---|
| Receive | Receive a message from the network; bind its subterms to local variables. |
| GenerateNonces | Sample fresh random values (nonces, session keys). |
| Compute | Apply cryptographic functions (encryption, hash, signature, MAC, DH exponentiation) to produce new terms. |
| Assertion | Check a condition on local state (e.g., signature verification, equality test); abort the block if the check fails. |
| Send | Transmit a term over the network (or if no message is sent). |
| Backbone | Avg(Corr) | Avg(Comp) | |||||
|---|---|---|---|---|---|---|---|
| Sonnet 4.6 | 0.816 | 0.703 | 0.723 | 0.747 | 0.839 | 1.000 | 0.920 |
| Qwen 3.5-plus | 0.967 | 0.643 | 0.604 | 0.738 | 0.956 | 1.000 | 0.978 |
| SAPIC [ 14 ] | AutoSM [ 20 ] | Masta | |
|---|---|---|---|
| Input | applied-pi process written by the user | natural-language document | natural-language document |
| Modeling | done by the user; SAPIC only translates it | generated, with user interaction in the Repairer stage | generated, no human involvement |
| Repair signal | not applicable | static analysis and user interaction | Tamarin verdicts |
| Security properties | supplied by the user | taken from the reference model | generated, then verified |
| Evaluation | not applicable | 18 protocols; a model is correct when the properties verified on the reference still hold on it | 149 tasks; 5 metrics covering process structure, properties, verdicts, and mutation completeness |
| Measure | Value |
|---|---|
| Total Tamarin calls | 1,567 ( verify_executable 744 / verify_lemma 795 / well_formed 28) |
| Timeouts | 29 (1.85%) |
| Tasks with at least one timeout | 14 / 149 (9.4%) |
| Tasks terminated by the 3,600 s budget | 0 / 149 |
Formal Verification
Formal verification uses mathematical models and machine-checked proofs to establish whether software and systems satisfy precise specifications.
See all 385 papers