💻 computer science

State-inferer: LLM-Driven State Machine Extraction and Formal Verification for Secure Protocol Implementations

This paper introduces State-inferer, a white-box framework that integrates program slicing, large language models, and formal model checking to accurately extract and verify protocol state machines from source code, achieving superior transition-level accuracy and uncovering four previously unknown security vulnerabilities in TLS, IKEv2, and SSH implementations.

Original authors: MengCheng Ju, Xi Chen, XieLi Zhang, Mingliang Zhu, Guanping Zhang, Dongliang Zhao, ChunXiang Gu

Published 2026-11-09

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: MengCheng Ju, Xi Chen, XieLi Zhang, Mingliang Zhu, Guanping Zhang, Dongliang Zhao, ChunXiang Gu

Original paper licensed under CC BY 4.0 (https://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 security of the digital world relies heavily on the invisible rules that govern how computers talk to one another. These rules, known as network protocols, are designed to ensure that data travels safely from a sender to a receiver, verifying identities and keeping secrets. At their heart, these protocols function like a strict script: a computer must be in a specific condition, receive a specific message, and then move to a new condition before it can proceed. If a computer skips a step or accepts a message while in the wrong condition, the entire system can be compromised, allowing attackers to bypass security checks or steal sensitive information. For decades, security experts have tried to verify that the actual code running on servers follows this script perfectly. However, the code is often messy, filled with hidden variables and complex logic that standard testing tools struggle to map. When the real behavior of a program diverges from its written design, dangerous flaws can hide in plain sight, waiting to be exploited.

A team of researchers at the PLA Information Engineering University has developed a new method to solve this problem, creating a tool called State-inferer that acts as a translator between complex computer code and the logical rules it is supposed to follow. Instead of trying to read the entire codebase at once or guessing how a program behaves by sending it random messages, this tool breaks the code down into tiny, manageable pieces. It uses a technique called program slicing to trace exactly how a specific piece of data changes as it moves through the software, isolating the precise logic that causes a computer to switch from one state to another. This process is like tracing a single thread through a tangled ball of yarn to see exactly where it leads, ignoring the rest of the mess. By focusing on these specific threads, the system can reconstruct the exact sequence of events a program follows, including the hidden internal conditions that standard tools often miss.

The researchers then fed these reconstructed sequences into a large language model, a type of artificial intelligence trained to understand and reason about code. Unlike previous attempts that simply asked the AI to read large chunks of text, this system provided the AI with one small, focused fragment of code for every single transition in the protocol. This allowed the AI to see the full context of a state change without getting overwhelmed by irrelevant information. The AI then built a complete map of the program's behavior, noting not just what messages triggered a change, but also the internal variables that had to be true for that change to happen. Finally, the researchers used a formal verification engine to check this map against the official security rules. This engine acts like a rigorous auditor, systematically testing every possible path the program could take to see if it ever violates the rules, such as sending data before a secure connection is fully established.

When tested on seven different open-source implementations of major security protocols, including TLS, IKEv2, and SSH, the new method proved to be remarkably accurate. It correctly identified the behavior of the code with a precision of 95.2 percent, significantly outperforming the best existing tools, which managed only about 78.9 percent. The difference was not just a matter of minor errors; the new tool successfully captured complex internal logic that other methods completely missed, such as transitions driven by internal timers or resource checks rather than external messages. In fact, the researchers found that older methods often failed to see nearly half of the critical transitions because they relied on a simplified view of the program that ignored these internal details. By capturing the full picture, the new tool was able to uncover four previously unknown vulnerabilities in the software. These flaws, which had never been discovered before, were serious enough to be assigned official security identifiers and reported to the software maintainers for fixing.

One of the most significant findings was that the flaws were not just theoretical possibilities but real, exploitable weaknesses. In one instance, the tool discovered that a server could be tricked into accepting a critical security message before it had finished the necessary key exchange, effectively bypassing authentication. In another case, a missing check allowed a server to process an endless stream of messages, potentially exhausting its resources. These discoveries highlight a critical gap in how software is currently analyzed: looking only at the input and output is not enough to understand how a program truly works. The researchers demonstrated that by combining precise code analysis with the reasoning power of artificial intelligence, it is possible to build a complete and accurate model of a program's internal logic. This approach does not require the software to be modified or the researchers to manually trace every line of code, making it a scalable way to audit the complex systems that protect our digital infrastructure.

The study also addressed the limitations of previous approaches that relied on retrieving code based on text similarity. Those methods often failed because they could not connect the dots between different functions that worked together to change a program's state. The new system, by contrast, follows the actual flow of data and control, ensuring that the context provided to the artificial intelligence is complete and connected. This allowed the system to generate security checks that were tailored specifically to the variables and logic of each unique implementation, rather than applying a generic template that might miss the mark. The result is a framework that can adapt to the quirks of different coding styles and still produce a reliable model of the system's behavior.

Ultimately, this work represents a shift in how we approach software security. It moves away from the idea that we must either manually inspect every line of code or rely on black-box testing that can only see the surface. Instead, it offers a way to see inside the machine, understanding exactly how it thinks and reacts. The researchers found that by treating the code as a set of logical steps that can be sliced, analyzed, and verified, they could find errors that had been hiding for years. While the tool was tested on open-source projects, the method suggests a path forward for securing the vast array of proprietary systems that run the internet. The ability to automatically extract and verify the state machines of complex protocols means that security can be checked more thoroughly and more quickly than ever before, potentially preventing the kinds of breaches that have plagued the digital world for decades. The findings confirm that the gap between what a protocol is supposed to do and what it actually does is where the danger lies, and that closing this gap requires a deeper, more precise look at the code itself.

Technical Summary: State-inferer

Problem Statement

The security of network protocol implementations relies on the correctness of the finite-state machines (FSMs) realized by their code. However, real-world implementations often deviate from their RFC specifications due to misinterpreted requirements or vendor-specific logic, leading to state-machine vulnerabilities such as authentication bypass. Recovering the actual FSM from source code is challenging due to three primary limitations in existing approaches:

Semantic Misalignment (C1): Existing methods often build message-driven state machines that abstract away internal implementation details. Real protocol states depend on internal variables (e.g., flags, counters) and control-flow conditions which, when ignored, result in coarse models that cannot express implementation-level behaviors necessary for verification.
Context Constraints (C2): Protocol codebases are too large for the context windows of current Large Language Models (LLMs). Retrieval-Augmented Generation (RAG) approaches typically rely on textual similarity, which fails to retrieve the complete cross-function and cross-file call chains required to understand a state transition as a unified unit. This leads to missing preconditions and incorrect reachability analysis.
Property Specialization (C3): RFC security properties are stated at a semantic level without reference to specific implementation variables. Translating these generic properties into Linear Temporal Logic (LTL) formulas for model checking requires mapping abstract concepts to specific code variables, a step that existing tools leave to manual analyst intervention.

Methodology: State-inferer

State-inferer is a white-box framework designed to extract and verify protocol state machines by combining program slicing, LLMs, and model checking. Its architecture consists of three main components:

1. Related Code Extractor (RCE)

To address the context constraint (C2) and avoid hallucination from irrelevant code, the RCE does not use similarity-based retrieval. Instead, it employs program slicing on the System Dependence Graph (SDG).

State Variable Identification: An LLM is prompted to identify key state variables and their enumeration values from header and core source files.
Depth-Bounded Slicing: Starting from assignments to state variables, the system performs forward and backward searches on the SDG bounded by data-flow ( $k_d$ ) and control-flow ( $k_c$ ) depths. This extracts a compact code fragment ("gadget") for each state transition that spans function boundaries but excludes unrelated low-level code. This ensures the LLM receives the complete call chain and preconditions for a transition.

2. Model Constructor

This component transforms the sliced code fragments into a formal State Transition System (STS), $M = (V, S, s_0, \delta, A)$ .

State Space ( $S$ ) and Initial State ( $s_0$ ): The LLM extracts the discrete state space from enumeration types and infers the initial state constants based on startup routines.
Transition Function ( $\delta$ ) and Variables ( $V$ ): For each code gadget, the LLM identifies the source and target states, extracts control-flow conditions, and translates them into formal Boolean expressions. It also collects the involved internal variables.
Action Set ( $A$ ): Transitions are labeled with external actions (e.g., message receipt) and internal actions (e.g., timer expiry, key derivation).
Output: The result is an STS where transitions carry explicit guards over internal variables, addressing the semantic misalignment (C1).

3. Security Property Generator

To solve the property specialization problem (C3), this module converts RFC meta-properties into implementation-specific LTL formulas.

The LLM takes the extracted STS and an RFC security property as input.
It maps abstract security concepts to the concrete state variables and transition predicates of the specific implementation.
It generates the corresponding LTL formula tailored to the codebase.

4. Verification

The extracted STS and LTL properties are translated into the SMV language and verified using nuXmv. If a property is violated, nuXmv generates a counterexample trace, which is manually reviewed to identify vulnerabilities.

Key Contributions

Slicing-Based Context Construction: A method for recovering protocol state transitions by performing depth-bounded forward and backward searches on the SDG. This extracts one compact code fragment per transition, ensuring the LLM sees the complete cross-function logic rather than isolated snippets.
Guarded State Transition System: A pipeline that constructs an implementation-level STS where transitions carry guards over internal variables, enabling the modeling of behaviors that depend on internal configurations rather than just external messages.
Model-Aware Property Specialization: An automated approach to specialize RFC security properties into LTL formulas over the extracted model, bridging the gap between specification semantics and implementation variables.
Empirical Evaluation: A comprehensive evaluation on seven open-source implementations of TLS, IKEv2, and SSH, demonstrating high accuracy in transition recovery and the discovery of previously unknown vulnerabilities.

Results

The framework was evaluated on seven implementations (OpenSSL, WolfSSL, TLSE, strongSwan, Libreswan, OpenSSH, tinySSH) against a reference model constructed by domain experts.

Accuracy: State-inferer achieved a macro-average strict transition-level F-score of 95.2%. This significantly outperformed the strongest baseline, ProtocolGPT (46.2%), and general-purpose coding agents (Codex: 78.9%, Claude Code: 77.1%).
Representation Power: Unlike Mealy-style representations used by baselines, State-inferer's STS could express all reference transitions. Baseline methods missed approximately 22% of transitions due to representational limitations (e.g., inability to distinguish states based on internal guards or internal events).
Vulnerability Discovery: State-inferer uncovered four previously unknown vulnerabilities in unmodified implementations:
1. WolfSSL (CVE-2026-2645): An authentication bypass in TLS 1.2 where a CertificateVerify message could be processed before key exchange completion.
2. TLSE (CNVD-2026-27960): A protocol version confusion caused by empty key share extensions in TLS 1.3.
3. TLSE (CNVD-2026-27959): Unbounded processing of ChangeCipherSpec messages due to a missing state variable.
4. TLSE (CNVD-2026-27957): Desynchronization between TLS alert handling and transport-layer state, allowing data transmission after a close notification.
  All findings were responsibly disclosed and assigned CVE or CNVD identifiers.

Significance and Claims

The paper claims that State-inferer addresses the fundamental limitations of current state-machine extraction methods by integrating static analysis (slicing) with the reasoning capabilities of LLMs. By constructing the context via dependency slicing rather than textual retrieval, the framework ensures that the LLM receives the necessary cross-function logic to accurately infer transition guards and reachability. Furthermore, by automating the specialization of RFC properties into LTL formulas, it enables formal verification of implementation-specific security properties without manual mapping.

The authors assert that their approach provides a more faithful representation of implementation-level behavior compared to black-box learning or specification-based modeling, directly enabling the discovery of vulnerabilities that depend on internal state configurations. The high F-score and successful discovery of real-world vulnerabilities demonstrate the practical efficacy of combining program slicing, LLMs, and model checking for secure protocol analysis.