Extracting Protocol Format as State Machine via Controlled Static Loop Analysis

Qingkai Shi, Xiangzhe Xu, Xiangyu Zhang

Abstract

Reverse-engineering network protocols is a critical task for security auditing and interoperability. While dynamic analysis is commonly used, it suffers from limited code coverage. Static analysis offers a comprehensive alternative but is often hindered by path explosion in loop-heavy parser code. This paper presents StateLifter, a static analysis tool that extracts protocol formats as finite state machines (FSMs) by treating loop iterations as states. Using a novel "controlled loop analysis" with specific merging and splitting rules, StateLifter achieves high precision and efficiency. Our evaluation shows a 70x speedup over existing static tools and the discovery of 12 zero-day vulnerabilities in mature protocol implementations.

Introduction

Securing network-connected devices requires a deep understanding of the protocols they use to communicate. Traditionally, researchers rely on dynamic analysis—observing live traffic or instrumenting running programs—to infer message formats. However, dynamic methods are fundamentally limited by the "coverage problem": they can only learn about protocol features present in the observed data. Rare or complex message types often remain hidden.

Static analysis, which examines source code without execution, theoretically provides 100% coverage. However, protocol parsers are typically structured around complex loops that process input byte-by-byte. Traditional static tools like symbolic executors often fail here, either succumbing to "path explosion" or losing critical context through over-approximation.

Methodology: StateLifter and Controlled Loop Analysis

StateLifter addresses these challenges by viewing protocol inference as a state machine extraction task. The core of the system is Controlled Static Loop Analysis, which models the parser's behavior across loop iterations.

From Code to State Machine

The analysis begins by identifying the main parsing loop. StateLifter treats each iteration of this loop as a potential state and the data dependencies between iterations as transitions. It uses abstract interpretation and the Z3 SMT solver to track how internal variables—specifically those acting as state indicators in switch or if-else blocks—evolve.

Figure 2: The StateLifter pipeline, showing (a) source code, (b) the raw state transition graph, and (c-e) the process of abstracting states into a final FSM.

Controlled Splitting and Merging

To manage complexity, StateLifter employs six dedicated rules (SR1-3 and MR1-3) to decide when to merge program paths into "super states" or split them to preserve precision. For instance, paths representing the same logical protocol state are merged, while states are split when recursive variable definitions or loop-exiting paths are detected. This prevents the astronomical growth of the state space while maintaining the fidelity of the protocol logic.

Figure 3: Incremental construction of the abstract state machine through state merging and splitting.

Handling Repetitive Fields

For variable-length fields or arrays, StateLifter uses mathematical induction. It "guesses" a summarized transition for repetitive patterns and then uses symbolic execution to "check" if the guess holds for all subsequent iterations. This "widening" technique ensures the analysis terminates quickly even for complex, nested message structures.

Evaluation and Results

The researchers evaluated StateLifter on ten real-world open-source protocols, including MAVLINK (drones), MQTT (IoT), and various utility protocols like MIDI and KISS.

Performance and Fidelity

StateLifter demonstrated remarkable efficiency, running approximately 70x faster than Proteus, the previous state-of-the-art static tool. While Proteus timed out on several protocols after three hours, StateLifter completed all analyses in under five minutes. Furthermore, it achieved over 90% precision and recall in identifying protocol fields, significantly outperforming dynamic tools that often missed half of the protocol structure due to incomplete traces.

Security Impact

The practical utility of the extracted FSMs was tested by using them to "seed" protocol fuzzers like AFLNet and BooFuzz. By providing the fuzzer with a high-fidelity map of the protocol, code coverage improved by 20% to 230%. Most importantly, this approach led to the discovery of 12 zero-day vulnerabilities, including critical buffer overflows and logic bugs, in mature implementations where baseline fuzzers found only two.

Discussion and Limitations

StateLifter's success stems from the insight that protocol transitions are directly implemented as loop dependencies in parser code. By compressing these dependencies into "super states," the tool creates human-readable and machine-actionable models.

However, limitations remain. The current prototype is tailored for C and does not support C++ features like virtual tables. Additionally, it cannot analyze black-box libraries or inline assembly. The authors also noted that static analysis struggles with high-entropy mathematical functions like CRCs or encryption, which currently require manual modeling.

Conclusion

StateLifter represents a significant advancement in automated protocol reverse-engineering. By intelligently managing the trade-off between path coverage and state-space complexity through controlled loop analysis, it provides a fast, precise, and highly effective tool for security researchers. Its ability to uncover hidden protocol features and zero-day vulnerabilities underscores the power of static analysis when applied with domain-specific optimizations.

Summary updated

BibTeX
@inproceedings{shi2023extracting,
  author = {Qingkai Shi and Xiangzhe Xu and Xiangyu Zhang},
  title = {{Extracting Protocol Format as State Machine via Controlled Static Loop Analysis}},
  booktitle = {USENIX Security},
  year = {2023},
  url = {https://openreview.net/forum?id=0LeDsrGRwG},
}
Figure