## 3 Message Format
### Full Message Format  
A number of efforts try to infer the whole structure of messages using iterative clustering. Others try to capture the order of the message fields in addition to their structures as a state machine. Discoverer [25] has been developed to automatically infer the protocol message formats of an application using tokenisation and iterative clustering methods. It starts with tokenisation and initial clustering of the messages based on their token patterns. Then, it \begin{table}
\begin{tabular}{c c c} \hline \hline
**Method** & **Specification** & **Remarks** \\ \hline \multirow{4}{*}{Catcher [17]} & \multirow{4}{*}{\begin{tabular}{c} Searching to find offset and length message \\ fields of interaction traces in the system \\ \end{tabular} } & \multicolumn{1}{c}{User is required to specify the semantic} \\  & & descriptions and contents Works with variable \\ \cline{1-1}  & & fields of interaction traces in the system \\ \cline{1-1}  & & \\ \cline{1-1}  & & \\ \hline \multirow{4}{*}{[PERSON] et al. [18]} & \multirow{4}{*}{\begin{tabular}{c} Extracting a few protocol message fields using \\ variance of the distribution of the \\ variances (VDV) \\ \end{tabular} } & Works on fixed-length binary protocol Tested \\  & & on ARP, DHCP, TCP, Kademlia \\ \hline \multirow{4}{*}{Roleplayer [19]} & \multirow{4}{*}{\begin{tabular}{c} Defining fields inside the protocol byte stream \\ by comparing two manually selected instances \\ of the same dialogue and align the bytes \\ \end{tabular} } & Works on fixed-length binary protocols, uses \\  & & heuristics to assign semantic values and \\  & & interpretation to the various fields. Tested on \\ \cline{1-1}  & & NFS, FTP and CIFS/SMB protocols \\ \hline \multirow{4}{*}{[PERSON] et al. [21]} & \multirow{4}{*}{\begin{tabular}{c} Finding message's structural fields using \\ position weighted entropy analysis \\ \end{tabular} } & Works on Binary and textual. Tested on IMS, \\  & & LDAP, SOAP, Twitter(REST) protocols \\ \hline \multirow{4}{*}{[PERSON] et al. [22]} & \multirow{4}{*}{\
\begin{tabular}{c} Extracting the request message format \\ Clustering messages using VAT and BEA \\ based on message types before using Clustalw \\ and position weighted entropy analysis \\ \end{tabular} } & Visual clustering by User Works in \\  & & variable-length, binary and text-based \\ \cline{1-1}  & & protocols.Tested on IMS, LDAP, SOAP, Twitter \\ \hline \multirow{4}{*}{[PERSON] [24]} & \multirow{4}{*}{
\begin{tabular}{c} Deriving a generalised message format for \\ each cluster in the form of a tree of fields \\ \end{tabular} } & Using message structure and the impact of \\ \cline{1-1}  & & each message on the server’s behaviour using \\ \cline{1-1}  & & execution traces using k Partitioning Around \\ \cline{1-1}  & & Medoids method. Tested on Agobot, SMTP, \\ \cline{1-1}  & & SMB, SIP \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Different approaches of partial message format extraction. utilises recursive clustering in a left-to-right scan and uses the identified values of format distinguisher fields (the value of this field serves to differentiate the format of the subsequent part of the message) to divide the clusters into sub-clusters automatically. Then, it uses a type-based sequence alignment method that compares the field structure of two inferred message formats to extract the message structures in each cluster and merge similar message formats. To mitigate over-classification, it also uses type-based sequence alignment to merge similar formats from different clusters into a single one. It can be applied to binary, text-based and variable-length protocols. ScriptGen [26] utilises iterative clustering and multiple alignment techniques to extract the format of protocols. It uses Protocol Informatics (PI) taken from [27] to perform multiple alignments on a set of protocol samples and automatically cluster messages to different types of semantically equivalent messages.