An Automated Framework for Input Alphabet Construction in Stateful Protocol Implementation Learning
2026-06-22 • Software Engineering
Software EngineeringCryptography and Security
AI summaryⓘ
The authors address a problem in state machine learning used to analyze communication protocols, where manually choosing inputs limits finding bugs. They use large language models to automatically generate input messages that better cover both normal and unusual cases without needing expert knowledge. To handle the large number of new inputs, they introduce a way to update their models efficiently. Their experiments show this method can find known and new bugs in real protocols, some of which developers have fixed, demonstrating the approach works well.
state machine learningprotocol analysisinput alphabetlarge language modelsmessage mutationincremental learningsemantic bugssecurity vulnerabilitiesautomata
Authors
JiongHan Wang, WenChao Huang
Abstract
As a prevalent analytical technique for stateful protocol implementations, state machine learning suffers from a core bottleneck stemming from handcrafted input alphabets. Manual alphabet definition inherently limits the completeness of input exploration, making it difficult to capture anomalous non-conformant messages and consequently missing latent semantic defects. In this paper, we target automatic input alphabet generation to break the above limitation for state machine learning. We adopt large language models to parse protocol message layouts and produce candidate input symbols following structured mutation rules, which automatically covers valid and invalid message spaces and eliminates reliance on manual protocol expertise. Considering the rising overhead brought by continuously growing alphabets, we introduce a mini-batch incremental learning strategy to reuse existing learned automata when incorporating new alphabet entries. Comprehensive experiments on practical protocol stacks indicate our approach can reproduce existing security vulnerabilities and identify novel semantic bugs. A subset of these newly discovered issues has been confirmed and patched by developers, proving the practicability and effectiveness of our proposed method.