Mining Protocol State Machines by Interactive Grammar Inference

Protocol state machine is very essential in network security and implementation fields, however, improper management of software evolution, compounded by changing and imprecise requirements, along with "short time to market" phenomenon, often leads to a lack of up-to-date specifications and they are often characterized by bugs, anomalies and even threads. How to mine the accurate protocol state machine under investigation is still an open problem. We address this problem by using an interactive grammar inference technique as it could generate queries to the protocol implementation in learning process. This paper describes: (1) a flexible method to construct and parse real packet according to the packet format, (2) how to generate packet queries to explore protocol state machine space, (3) applies the QSM technology to mine protocol state machine from network traces. To access the usefulness of our approach, several experiments for different protocols are performed and we could get more objective and accurate results compared with other protocol specification mining methods.