# Synthesizing Precise Protocol Specs from Natural Language for Effective Test Generation

arXiv: https://arxiv.org/abs/2511.17977 · HTML: https://mlsanity.com/paper/2511.17977/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 57 references that are in the map.
- First posted on arXiv 22 Nov 2025.

## Builds on (most cited first, 16 of 16)

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [PaLM: Scaling Language Modeling with Pathways](https://mlsanity.com/paper/2204.02311/) (2022)
- [Survey of Hallucination in Natural Language Generation](https://mlsanity.com/paper/2202.03629/) (2022)
- [A Survey on Hallucination in Large Language Models: Principles, Taxonomy, Challenges, and Open Questions](https://mlsanity.com/paper/2311.05232/) (2023)
- [Software Engineering for AI-Based Systems: A Survey](https://mlsanity.com/paper/2105.01984/) (2021)
- [nl2spec: Interactively Translating Unstructured Natural Language to Temporal Logics with Large Language Models](https://mlsanity.com/paper/2303.04864/) (2023)
- [Grounding Complex Natural Language Commands for Temporal Tasks in Unseen Environments](https://mlsanity.com/paper/2302.11649/) (2023)
- [Superion: Grammar-Aware Greybox Fuzzing](https://mlsanity.com/paper/1812.01197/) (2018)
- [Semi-Automated Protocol Disambiguation and Code Generation](https://mlsanity.com/paper/2010.04801/) (2020)
- [Automated Attack Synthesis by Extracting Finite State Machines from Protocol Specification Documents](https://mlsanity.com/paper/2202.09470/) (2022)
- [Validating Network Protocol Parsers with Traceable RFC Document Interpretation](https://mlsanity.com/paper/2504.18050/) (2025)
- [RFCAudit: An LLM Agent for Functional Bug Detection in Network Protocols](https://mlsanity.com/paper/2506.00714/) (2025)
- [Smart Greybox Fuzzing](https://mlsanity.com/paper/1811.09447/) (2018)
- [NLP-assisted software testing: A systematic mapping of the literature](https://mlsanity.com/paper/1806.00696/) (2018)
- [Language-Based Protocol Testing](https://mlsanity.com/paper/2509.20308/) (2025)

## Built on by (most cited first, 2 of 2)

- [SecretFan: Synthesizing Realistic Data without Breaking Privacy](https://mlsanity.com/paper/2602.05833/) (2026)
- [SPECA: Specification-to-Checklist Agentic Auditing for Multi-Implementation Systems -- A Case Study on Ethereum Clients](https://mlsanity.com/paper/2602.07513/) (2026)

## Abstract (arXiv)

Safety- and security-critical systems have to be thoroughly tested against their specifications. The state of practice is to have _natural language_ specifications, from which test cases are derived manually - a process that is slow, error-prone, and difficult to scale. _Formal_ specifications, on the other hand, are well-suited for automated test generation, but are tedious to write and maintain. In this work, we propose a two-stage pipeline that uses large language models (LLMs) to bridge the gap: First, we extract _protocol elements_ from natural-language specifications; second, leveraging a protocol implementation, we synthesize and refine a formal _protocol specification_ from these elements, which we can then use to massively test further implementations. We see this two-stage approach to be superior to end-to-end LLM-based test generation, as 1. it produces an _inspectable specification_ that preserves traceability to the original text; 2. the generation of actual test cases _no longer requires an LLM_; 3. the resulting formal specs are _human-readable_, and can be reviewed, version-controlled, and incrementally refined; and 4. over time, we can build a _corpus_ of natural-language-to-formal-specification mappings that can be used to further train and refine LLMs for more automatic translations. Our prototype, AUTOSPEC, successfully demonstrated the feasibility of our approach on five widely used _internet protocols_ (SMTP, POP3, IMAP, FTP, and ManageSieve) by applying its methods on their _RFC specifications_ written in natural-language, and the recent _I/O grammar_ formalism for protocol specification and fuzzing. In its evaluation, AUTOSPEC recovers on average 92.8% of client and 80.2% of server message types, and achieves 81.5% message acceptance across diverse, real-world systems.