## 3 Message Format
### Full Message Format
Then, ScriptGen uses a Region Analysis algorithm to search for frequent values and types in the messages of each cluster on a byte-by-byte basis to identify regions with frequent values and create new microclusters. PRISMA [28] is another method that uses tokenisation, two-step clustering and statistical analysis to extract message templates. A template is described as the structure of a message comprising of tokens and fields sequence. Part-based and position-based clustering is used to cluster messages into different message types. For the clustering purpose, it considers each message as a vector of n-grams (text-based protocols) or tokens (binary protocols) and keeps tokens which are statistically significant and independent. To extract the templates of each message type, it leverages all the tokens and groups the messages in each cluster based on their number of tokens. Next, in each group, it looks for recurring tokens, identifies constant and variable tokens, and records them as the message template. [PERSON] et al. [29] presented a method to improve clustering the messages, which later leads to better message format extraction using Latent Dirichlet Allocation. This approach considers a message as a mixture of n-grams. Then, it removes the unimportant n-grams in defining message types using term frequency-inverse document frequency (TF-IDF). score. Later, it describes each type as a different distribution of n-grams. The method applies the n-gram distributions to measure the similarity of messages. Based on the similarity values, it clusters messages and further extracts message formats. P-token [30] has been proposed by [PERSON] et al. to extract protocol message formats from raw network traces. It improves the format extraction by considering keywords' positions as meta-information in tokenising the messages. Then, it clusters messages based on their extracted keywords and later extracts a format per cluster. However that P-token outperforms the existing methods significantly, but it cannot cope with protocols with complex structure formats. [PERSON] et al. [31] presented a method to improve the P-token technique. The new method aims to better extract the message format of protocols relative to the previous naive P-token [30]. It consists of three main steps; (1) keyword identification, (2) message clustering, and (3) format extraction. In the first step, it uses two criteria to identify the keywords. The same type of messages have common keywords that can be identified through frequency analysis of tokens. The keyword appearance position in the messages is relatively fixed. In the second step, the method separates the messages that have similar keyword sequence homogeneity and puts them into a cluster. It starts with vectorising messages based on the frequency of appearing the identified positional keywords and then clustering the message vectors based on a two-level hierarchical clustering method using the density peaks clustering algorithm. In the third step, in each cluster, they infer common keyword patterns as message formats in the form of regular expressions from each cluster. A number of further research efforts extract message formats in the form of finite state machines. Predator [32] uses iterative clustering to build language models in the form of a Markov model from the network traces. It splits samples into pairs of requests and corresponding responses. Then, it clusters request messages using iterative k-medoids and TF-IDF features and uses cosine similarity as a distance metric [33]. It then infers k responses Markov models for the corresponding clusters. The proposed technique operates for variable-length field binary protocols. [PERSON] et al. [34] used tokenisation and filtering to infer a finite state machine (FSM) representation of the protocol language for binary, text-based and variable-length protocols. After tokenisation of the messages, it uses the Jaccard Index to filter infrequent tokens and identify frequent tokens as keywords.