## 3 Message Format
### Full Message Format
Then, the protocol language FSM is inferred, which at this stage accepts all types of input messages. The Moore reduction procedure is employed to generalise the inferred FSM by removing nodes with a frequency lower than a threshold and merging nodes with the same message type. To complement or update a protocol specification, [PERSON] et al. [35] try to identify new message formats and add them to the protocol language FSM. First, they utilise a set of predefined regular expressions in the protocol specification to derive the FSM of message formats. Then, they consider each text-based message as a sequence of tokens and identify new messages not covered by the given protocol specification, i.e., those that the existing FSM fail to parse, then adding them as an extension to the FSM and finally minimise the extensions using the ReverX technique. The method proposed by [PERSON] et al. [36] is fully automatic, which extracts syntax, semantics, and FSM of a chosen protocol. To get clear protocol syntax, they introduced three format types as field formats, message format, and flow format plus four field format types to obtain protocol syntax clearly. To derive such formats, they presented a method called hierarchical CSP and recursive CSP. To start with, it infers well-trimmed message formats and then maps the input messages into a limited number of message formats. Table 2 shows a summary of different methods introduced to extract full message format. \begin{table}
\begin{tabular}{c c c} \hline \hline
**Method** & **Specification** & **Remarks** \\ \hline \multirow{3}{*}{Discoverer [25]} & Infer the protocol message formats of an & Works on binary, text-based and variable-length \\  & application using tokenisation and recursive & protocols. Tested on HTTP,RPC, \\  & clustering and type-based sequence & CIFS/SMB protocols \\  & alignment methods & \\ \hline \multirow{2}{*}{ScriptGen [26]} & Iterative clustering and multiple & \multirow{2}{*}{Tested on SMB, IM protocols} \\  & alignment techniques & \\ \hline \multirow{2}{*}{PRISMA [28]} & Tokenisation, two-step clustering and & Works on binary and textual protocols. Tested on \\  & statistical analysis & SIP, DNS and FTP \\ \hline \multirow{2}{*}{[PERSON] et al. [29]} & Latent Dirichlet Allocation to improve clustering & \multirow{2}{*}{Tested on FTP, CoAP, XMPP} \\  & considers a message as a mixture of n-grams & \\ \hline \multirow{3}{*}{P-token [30]} & \multirow{3}{*}{Clustering messages based on their extracted keywords and later extracts a format per cluster} & Considering keywords’ positions as \\  & & meta-information tokenising the \\ \cline{1-1}  & & \\ \cline{1-1}  & & messages/cannot cope with protocols with \\ \cline{1-1}  & & complex structure formats Tested on SOAP, \\ \cline{1-1}  & & LDAP, IMS and RESTful \\ \hline \multirow{3}{*}{Predator [32]} & \multirow{3}{*}{Keyword identification, message clustering, format extraction} & Tested on SOAP, LDAP, IMS and RESTful \\  & & \\ \cline{1-1}  & Iterative clustering to build language models in & \multirow{3}{*}{Works on stateless protocols} \\ \cline{1-1}  & the form of a Markov model from the & \\ \cline{1-1}  & network traces & \\ \hline \multirow{2}{*}{[PERSON] et al. [34]} & Tokenisation and filtering to infer a finite state & Works on binary, text-based and variable-length \\  & machine (FSM) & protocols. Tested on ARP, SMTP \\ \hline \multirow{3}{*}{[PERSON] et al. [35]} & \multirow{3}{*}{To complement or update a protocol specification} & Utilising a set of predefined regular expressions \\ \cline{1-1}  & & in the protocol specification to derive the FSM of \\ \cline{1-1}  & & message formats. Tested on IETF(FTP) protocol \\ \hline \multirow{2}{*}{[PERSON] et al. [36]} & Extracting syntax, semantics, and FSM of a & Works on binary and textual Tested on \\ \cline{1-1}  & chosen protocol & HTTP, DNS \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Different approaches of full message format extraction.