## 3 Message Format
### Partial Message Format  
Methods in this category try to find the most relevant, dynamic and structural parts of the messages. Catcher [17] can be considered as one of the elementary methods that works as a search engine, looking in system interaction traces for the message fields with the semantic descriptions and contents specified by the user. It finds their offsets and lengths and generates scripts using an entropy weighted sequence alignment algorithm. It was tested on text-based message protocols and could work with variable length protocols.  
The basic idea presented by [PERSON] et al. [18] is that a few protocol message fields capture the protocol's logic. To extract these parts, the proposed method used the variance of the distribution of the variances (VDV) to identify and extract all related features in a fixed-length binary protocol message format. Others such as Roleplayer [19] compares two manually selected instances of the same dialogue and aligns the bytes using Needleman-Wunsch sequence alignment algorithm [20] and defining fields inside the protocol byte stream. The method uses heuristics to assign semantic values and interpretation to the various fields such as IP addresses and hostnames adopted in the message exchange and works on fixed-length binary protocols.  
[PERSON] et al. [21] and [PERSON] et al. [22] use position weighted entropy analysis as an extension to the Needleman-Wunsch sequence alignment algorithm to identify parts of the request messages containing the operation type and some other structural information. While [PERSON] et al. [22] extracted the message format by comparing all recorded request messages, [PERSON] et al. [12; 21; 23] used the visual assessment of (cluster) Tendency or VAT and Bond Energy Algorithm or BEA for visually clustering algorithms to first separate different types of requests and then extract request prototypes using Clustalw and entropy-based positional weighting in each cluster, to improve the accuracy of extracted formats. Clustalw utilises a progressive multiple sequence alignment technique to improve their format extraction by first aligning the most similar sequences out of two messages which have the  
Figure 2: Message and its structural format.  
best alignment score. Their method semi-automatically clusters similar messages in the same cluster and can be applied to variable-length, binary and text-based protocols.  
Prospex [24] automatically identifies and clusters different message types, not merely on the basis of their structure, but also in regard to the impact of each message on the server's behaviour. To study the application while processing arriving messages, the method used dynamic data tainting. The resulted execution traces uncover the activities conducted on data that was received from the network. It clusters messages to different types using k Partitioning Around Medoids (PAM) method (estimate k with Dunn index) [24] and derives a generalised message format for each cluster in the form of a tree of fields with attached semantics through merging the format of the messages in each cluster. It uses three types of similarity features in this process. Input similarity captures similarity in the order and values of the fields in the messages by using the Needleman-Wunsch sequence alignment algorithm. Application execution similarity collects information regarding the executed code fragments, libraries, and system calls of the server while processing a message. Impact similarity captures the actions such as the output and file system activity of the server in response to the incoming message. It can be applied to both binary and text-based protocols but needs access to the server's system calls and execution logs. Table 1 shows a summary of different methods in partial messages format extraction.