EDSM-Based Protocol State Machine Reverse For Binary Protocol

With the development of Internet,Protocol technique research in networ k application also increases rapidly. Understanding the protocols of computer network deeply has great influence of computer network security. However, more and more network protocols belong to personal protocols which lack public protocol specifications, so protocol reverse engineering has great value in protocol analyzing. Protocol reverse engineering consists of protocol message format, semantic reverse and protocol state machine reverse. The goal of message format reverse is to obtain the message structure of unknown protocol by analyzing packet data or instructions while protocol entities execute. Protocol state mac hine reverse is the process of inferring state migration while the protocol entities deal the packets with the help of prior knowledge of the message format and semantic information.Binary protocol message format is relatively fixed, however there are some variable length fields for complex protocol. In this paper, a method which combines multiple sequence alignment and message statistic to complete the extraction of state relevant field was proposed. Firstly we use multiple sequence alignment to find variable length fields, then remove variable length fields for each packets if variable length fields exist which make sure the left fields are aligned. Then we use message statistic to mine the state relevant field. We translate network protocol sessions which are obtained by network sniffing from the form of message streams to the form of message type streams. Once we get message type streams, we construct a APTA tree, then we leverage a heuristic state labeling algorithm to label each state. Finally we a pply EDSM algorithm to the state tree to complete state merge to get final minimized DFA with the help of a reasonable and effective scoring mechanism.To evaluate the performance of EDSM algorithm, we apply three binar y protocols:TCP?SMB and DHCP to our s ystem.We find that our system has a good recognition to variable length fields. We also test the precision and recall of the state machine we inferred, the result shows that it works very well. At the same time,by the comparison with EXBAR algorithm, we fi nd that EXBAR runs very long time in the case of initial protocol data is big while EDSM algorithm can still ensure run out in polynomial time.Besides,Bigger data can make EDSM more accurate which it can avoid some local merge errors relatively at the begi nning of state merge.