# Capturing Uncertainty Information and Categorical Characteristics for Network Payload Grouping in Protocol Reverse Engineering

Authors: Jian-Zhen Luo; Shun-Zheng Yu; Jun Cai
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

As a promising tool to recover the specifications of unknown protocols, protocol reverse engineering has drawn more and more attention in research over the last decade. It is a critical task of protocol reverse engineering to extract the protocol keywords from network trace. Since the messages of different types have different sets of protocol keywords, it is an effective method to improve the accuracy of protocol keyword extraction by clustering the network payload of unknown traffic into clusters and analyzing each clusters to extract the protocol keywords. Although the classic algorithms such asK-means and EM can be used for network payload clustering, the quality of resultant traffic clusters was far from satisfactory when these algorithms are applied to cluster application layer traffic with categorical attributes. In this paper, we propose a novel method to improve the accuracy of protocol reverse engineering by applying a rough set-based technique for clustering the application layer traffic. This technique analyze multidimension uncertain information in multiple categorical attributes based on rough sets theory to cluster network payload, and apply the Minimum Description Length criteria to determine the optimal number of clusters. The experiments show that our method outperforms the existing algorithms and improves the results of protocol keyword extraction.


---

## Body

## 1. Introduction

Network protocol reverse engineering [1–4] is a promising approach to address the problem of recovering detailed specifications of unpublished or undocumented network protocols from the network trace. The specifications of protocols play an important role in the network security and management oriented issues, such as intrusion detection, fuzzing test [5], recovering and understanding command-and-command (C&C) protocols [6], and building intelligent honeypot [7]. The specifications of open protocols such as HTTP are available from the published document. However, the specifications of some protocols (called proprietary protocols) used by enterprises or hackers are not open to public for the reason of commercial or security. Researchers deem that protocol reverse engineering is the only option available to build the understanding of proprietary protocol from network trace.The extraction of protocol keywords from network trace is a critical task of protocol reverse engineering. The protocol keywords [4] are referred to as the constant strings or command characters used by the protocol. For example, the HTTP protocol uses “GET” as the request method and the FTP protocol uses “QUIT” as the command to quit a session. If the messages are not grouped into clusters to make sure each cluster belongs to a unique message type, some protocol keywords (associated with a particular message type) with low occurrence probability will be missed due to the interference of miscellaneous types of messages. Thus, it is critical that the messages input to a protocol reverse engineering system belong to a single type. In practice, it is a challenge to cluster messages of unknown traffic according to message types, since we have no prior knowledge about the unknown protocols. An adapted solution to these issues is to apply unsupervised clustering methods to group messages of the unknown traffic.Clustering unlabeled data is also important for many other applications, such as building an automatic method to generate signatures for unknown or new network applications in network management. Such issues have been studied by many works [8–12] most of which are applicable for clustering data having attributes with numerical values. The reason why most clustering algorithms are focused on attributes with numerical value is that it is easy to define similarities of the numerical data using geometric concepts. However, much data contained in today’s databases and much information which is valuable for clustering is categorical in nature. Specifically, in our problem domain, the protocol messages analyzed by reverse engineering systems expose mainly categorical characteristics, such as message direction, transport layer number used by the protocol, words, or delimiters used by the messages. On the other hand, most clustering algorithms are crisp clustering algorithms and they are inclined to classify an object into one and only one cluster [13]. However, it is hard to define the crisp boundaries of clusters in many practical cases and the crisp clustering algorithms lack the ability to handle the uncertain information hidden in the data set [14]. The messages that belong to different types reflect different string patterns. For instance, some messages start with a string of “M-SEARCH,” while others start with “GET.” Hence, the remarkable characteristic is valuable for clustering application layer traffic. However, some attributes in different clusters have the same value. For example, the first 4 bytes of some messages of both HTTP and SSDP are “HTTP.” Thus, when we have a message whose first 4 bytes are “HTTP,” it is difficult to determine which of HTTP and SSDP dose the message belong to. In other words, each attribute of a message has different degree of confidence to indicate the message’s belonging to different types. We have to deal with the uncertain information of message attributes in the clustering process.In this paper, the main innovative contribution is to improve the accuracy of protocol reverse engineering by applying a rough sets theory- (RST-) [14–16] based method to tackle the problems of clustering application layer traffic and grouping the messages according to the message types. In the process of clustering, we propose to select cluster for further clustering according to the degree of uncertainty within the cluster instead of the number of objects within the cluster instead of selecting the subclusters with more objects for further splitting [17]. The approach is implemented on a system called RSCluster and applied to cluster real-world application layer network trace according to the protocols and group protocol messages according to the message types in order to improve accuracy of the protocol keyword extraction.Besides the application of improving accuracy of protocol reverse engineering, the RSCluster is supposed to be an efficient and accurate traffic clustering tool for classifying and identifying newly emergent applications which are most likely unknown to network administrators. Based on the clustering results, one can generate models or signatures to represent the profile of each unknown application so as to distinguish them from each other in the future.The remainder of this paper is arranged as follows. Section2 studies the related work. Section 3 presents an overview of rough sets theory and outlines some basic definitions. Section 4 presents our methodology of traffic clustering. Section 5 discusses the Minimum Description Length criteria for model selection. The computation complexity is discussed in Section 6 and the approach is evaluated in Section 7. Finally, a conclusion is made in Section 8.


## 2. Related Work

In the last decade, numbers of techniques have been applied to cluster Internet traffic. The simplest approach is to cluster flows according to the well-known ports assigned by IANA [18]. However, more and more applications exceedingly use dynamic port numbers during the communication in the Internet. Furthermore, considerable applications were exposed to hide their traffic behind some well-known traffic (e.g., HTTP) to be transmitted over well-known port so as to bypass the detection of firewalls. Therefore, the port based approaches are insufficient in many cases.Recently, a number of algorithms have been proposed to apply the classic clustering methods such asK-means and EM methods to address these issues. These techniques assume that traffic has statistical attributes (e.g., packet lengths, average length of packets, and packet interarrival time) which are unique for certain classes of applications. Hence, one could distinguish different kinds of applications from each other by leveraging the flow’s statistical characteristics. Erman et al. [8] propose two unsupervised clustering algorithms (i.e., K-means and DBSCAN) to classify traffic by exploiting the distinctive characteristics of applications when they communicate on a network. In [9], Erman et al. apply unsupervised EM clustering technique for the Internet traffic classification problem. The unsupervised clustering approach uses an EM algorithm to classify unlabeled training data into groups based on similarity. Although these techniques have improved the accuracy in a certain extent, the reported results were still far from satisfactory.The difference between ours and [8, 9] is that we cluster traffic by considering categorical value attributes and analyzing the multidimension of uncertainty between attributes, instead of quantifying flow attributes into numerical value attributes and applying geometric similarity. As we know, inaccurate or inappropriate quantification will lose some valuable information of data or distort the substantial truth. As a result, it is very important to keep the data as it is as far as possible in order to preserve more information.In order to build up the categorical data clustering, Mahmood et al. [19] develop a framework to deal with mixed type attributes including numerical, categorical, and hierarchical attributes for a one-pass hierarchical clustering algorithm. However, they focus on analyzing network flow feature such as protocols (UDP, TCP, and ICMP) to identify interesting traffic patterns from network traffic data, while we aim to analyze the categorical features in application layer to cluster network traffic according to protocols and group protocol messages according to message types. Other researchers propose to take advantage of RST to cluster qualitative-value data [20]. Mazlack et al. [21] propose RST-based technique to choose effective attributes for data partitioning in the procedure of clustering. Parmar et al. propose an novel algorithm, namely, Min-Min-Roughness (MMR) [17], for categorical data clustering. They show that MMR performs well in handling the uncertainty of multidimension categorical attributes of data. In each iteration of the clustering process, the MMR algorithm selects a subcluster with more objects for further splitting. However, our approach chooses cluster for further splitting according to the degree of uncertainty instead of the number of objects within the cluster. The rationality of this alternative will be explained in the next section.Wang et al. [22, 23] demonstrate an approach to cluster unknown traffic and determine the number of clusters. Since the exact number of classes is unknown in advance, they apply the X-means algorithm to efficiently estimate the best value of cluster number K by integrating Bayesian information criterion with basic K-means. Georgieva et al. [24] propose an approach to determine the number of cluster based on the Minimum Description Length (MDL) criteria [25, 26]. Toward the number of clusters, we also explore MDL criteria to capture the optimal number of clusters. We determine the cluster number by choosing the clustering model which minimizes the total description lengths of describing the model and encoding the data set with the help of the model.


## 3. Traffic Clustering Using Rough Sets Theory

The concept of rough sets theory (RST) [15] was developed by Pawlak in 1982. To date, RST has received considerable attention of research in the computational intelligence literature for its excellent capability of handling imprecision, vagueness, and uncertainty in data analysis [14, 16, 17, 21]. Parmar et al. [17] show that the RST-based algorithm is appropriate to cluster categorical data and handle uncertainty in the clustering process. In what follows, we will introduce the basic concepts of rough sets theory.


### 3.1. Information System for Clustering

In order to formulate the problem of traffic clustering or message grouping, an information systemS is defined as an ordered quadruple S=(U,Q,V,ρ). The universe U={x1,x2,…,xn} contains all objects (sessions or messages) in the network trace. The attribute set is denoted by Q={a1,a2,…,am}, where every ai is an attribute of the objects in U. Vai∈Q stands for the domain of ai, whereas V=∪∀ai∈QVai. Finally, the description function f:U×Q→V maps an object x∈U and an attribute ai∈Q to the value domain V.


### 3.2. Indiscernibility Relation

For any two objectsxi,xj∈U, they are indiscernible with respect to attribute a (denoted by ~a) in S if and only if f(xi,a)=f(xj,a). More generally, given a subset A⊂Q, if xi and xj are indiscernible with respect to every a′∈A, then xi and xj are defined to be indiscernible by the set of A; that is, ∀a′∈A,f(xi,a′)=f(xj,a′). The indiscernibility relation on the set A in S, in symbols ~A, is defined as follows: xi~Axj if and only if xi and xj are indiscernible by the set of A.Importantly, the elementary set, denoted byE, in U with respect to A, is defined as the equivalence class of relation ~A. The family of all elementary sets with respect to A is denoted by U/A={E1,E2,…,E|U/A|}. For any element xi of U, the equivalence class of xi of relation ~A is represented as [xi]~A.


### 3.3. Lower and Upper Approximation

In what follows, we introduce two important concepts in rough sets-based approach for data analysis, namely, the lower approximation and upper approximation.LetA⊂Q be a set of attributes, and let X be a subset of objects in universe U (i.e., X⊂U). The lower approximation of X with respect to A in U, denoted by Δ_A(X), is defined as the union of all those elementary sets which are contained in X. That is, given U/A={E1,E2,…,E|U/A|}, we have(1)Δ_AX=⋃Ei⊆XEi=x∣x∈U∧x~A⊆X.By this notation, it is easy to have that an objectx∈U belongs to X doubtlessly, if x∈Δ_A(X).On the other hand, the upper approximation ofX with respect to A in U, denoted by ∇¯A(X), is defined as the union of all those elementary sets which have a nonempty intersection with X. More formally, given U/A={E1,E2,…,E|U/A|}, we have(2)∇¯AX=⋃Ei∩X≠ϕEi=x∣x∈U∧x~A∩X≠ϕ.We note that if an objectx∈∇¯A(X), it implies that x possibly belong to X.Anaccuracy measure of the set X in A⊆Q is defined as(3)μAX=card⁡Δ_AXcard⁡∇¯AX,where card(Δ_A(X)) or card(∇¯A(X)) is the number of objects contained in the lower or upper approximation of the set X with respect to A. Obviously, 0≤μA(X)≤1.IfμA(X)=1, then the set X is asserted to be definable in U with respect to A. Otherwise, X is undefinable in U.For ease of exposition, we define the notion ofroughness as follows:(4)RAX=1-μAX=1-card⁡Δ_AXcard⁡∇¯AX.IfRA(X)=0, X is crisp with respect to A. If 0<RA(X)≤1, X is rough with respect to A.


### 3.4. Classification of Information System

LetF={C1,C2,…,Cn}, Ci⊂U, be a family of subsets of the universe U. If F is a partition of U, that is,(5)Ci∩Cj=ϕ∀i,j,1≤i,j≤n,i≠j,⋃i=1nCi=Uthen F is aclassification of U, whereas Cis are called classes of F.Suppose thatA is subset of Q, the lower and upper approximation of F with respect to A in S are defined as(6)Δ_AF=Δ_AC1,Δ_AC2,…,Δ_ACn,∇¯AF=∇¯AC1,∇¯AC2,…,∇¯ACn,respectively.With these notations, thequality of the classification with respect to A is given as(7)ηAF=card⁡⋃i=1nΔ_ACicard⁡U,and theaccuracy of the classification with respect to A is given as(8)μAF=card⁡⋃i=1nΔ_ACicard⁡⋃i=1n∇¯ACi.


## 3.1. Information System for Clustering

In order to formulate the problem of traffic clustering or message grouping, an information systemS is defined as an ordered quadruple S=(U,Q,V,ρ). The universe U={x1,x2,…,xn} contains all objects (sessions or messages) in the network trace. The attribute set is denoted by Q={a1,a2,…,am}, where every ai is an attribute of the objects in U. Vai∈Q stands for the domain of ai, whereas V=∪∀ai∈QVai. Finally, the description function f:U×Q→V maps an object x∈U and an attribute ai∈Q to the value domain V.


## 3.2. Indiscernibility Relation

For any two objectsxi,xj∈U, they are indiscernible with respect to attribute a (denoted by ~a) in S if and only if f(xi,a)=f(xj,a). More generally, given a subset A⊂Q, if xi and xj are indiscernible with respect to every a′∈A, then xi and xj are defined to be indiscernible by the set of A; that is, ∀a′∈A,f(xi,a′)=f(xj,a′). The indiscernibility relation on the set A in S, in symbols ~A, is defined as follows: xi~Axj if and only if xi and xj are indiscernible by the set of A.Importantly, the elementary set, denoted byE, in U with respect to A, is defined as the equivalence class of relation ~A. The family of all elementary sets with respect to A is denoted by U/A={E1,E2,…,E|U/A|}. For any element xi of U, the equivalence class of xi of relation ~A is represented as [xi]~A.


## 3.3. Lower and Upper Approximation

In what follows, we introduce two important concepts in rough sets-based approach for data analysis, namely, the lower approximation and upper approximation.LetA⊂Q be a set of attributes, and let X be a subset of objects in universe U (i.e., X⊂U). The lower approximation of X with respect to A in U, denoted by Δ_A(X), is defined as the union of all those elementary sets which are contained in X. That is, given U/A={E1,E2,…,E|U/A|}, we have(1)Δ_AX=⋃Ei⊆XEi=x∣x∈U∧x~A⊆X.By this notation, it is easy to have that an objectx∈U belongs to X doubtlessly, if x∈Δ_A(X).On the other hand, the upper approximation ofX with respect to A in U, denoted by ∇¯A(X), is defined as the union of all those elementary sets which have a nonempty intersection with X. More formally, given U/A={E1,E2,…,E|U/A|}, we have(2)∇¯AX=⋃Ei∩X≠ϕEi=x∣x∈U∧x~A∩X≠ϕ.We note that if an objectx∈∇¯A(X), it implies that x possibly belong to X.Anaccuracy measure of the set X in A⊆Q is defined as(3)μAX=card⁡Δ_AXcard⁡∇¯AX,where card(Δ_A(X)) or card(∇¯A(X)) is the number of objects contained in the lower or upper approximation of the set X with respect to A. Obviously, 0≤μA(X)≤1.IfμA(X)=1, then the set X is asserted to be definable in U with respect to A. Otherwise, X is undefinable in U.For ease of exposition, we define the notion ofroughness as follows:(4)RAX=1-μAX=1-card⁡Δ_AXcard⁡∇¯AX.IfRA(X)=0, X is crisp with respect to A. If 0<RA(X)≤1, X is rough with respect to A.


## 3.4. Classification of Information System

LetF={C1,C2,…,Cn}, Ci⊂U, be a family of subsets of the universe U. If F is a partition of U, that is,(5)Ci∩Cj=ϕ∀i,j,1≤i,j≤n,i≠j,⋃i=1nCi=Uthen F is aclassification of U, whereas Cis are called classes of F.Suppose thatA is subset of Q, the lower and upper approximation of F with respect to A in S are defined as(6)Δ_AF=Δ_AC1,Δ_AC2,…,Δ_ACn,∇¯AF=∇¯AC1,∇¯AC2,…,∇¯ACn,respectively.With these notations, thequality of the classification with respect to A is given as(7)ηAF=card⁡⋃i=1nΔ_ACicard⁡U,and theaccuracy of the classification with respect to A is given as(8)μAF=card⁡⋃i=1nΔ_ACicard⁡⋃i=1n∇¯ACi.


## 4. Traffic Clustering Using Rough Sets Theory

As suggested by Mazlack et al. [21], data clustering is a series of procedures to discover the intraitem dissonance of data and eliminate it within the resulting subpartitions by progressively partitioning the data set. Inspired by this rationale, traffic clustering could be achieved by recursively partitioning the data set to reduce the dissonance (uncertainty) within the resulting partitions. Obviously, the crisp partitioning is the most desired situation because there is no dissonance inside the partitions. However, it cannot always be achieved in real world. Thus, our proposed algorithm considers the partitioning leading to less uncertainty.Following this heuristic thought, the procedure of traffic clustering should be performed in the following way: we firstly choose an effective partitioning attribute, then split the data set by searching for a partitioning point of the selected attribute so as to maximize the coherence of resulting partitions. These procedures are repeated until either the coherence is no longer changed or a predefined termination condition is satisfied.


### 4.1. Roughness and Average Roughness

In order to deal with the uncertain information in data set and quantify the degree of the uncertainty, we define the some related concepts based on roughness [17, 21] as follows.Given an attributeai∈A and the domain of its possible values Vai={α1,α2,…,α|Vai|}, the family of all elementary sets with respect to ai in S is denoted by U/ai={Eai(α1),Eai(α2),…,Eai(α|Vai|)}, where Eai(αk) refers to a specific elementary set (with respect to ai) whose value of ai is αk (k=1,2,…,|Vai|). In essence, U/ai is indeed an n-partitioning (n=|Vai|) on U towards attribute ai and Eai(αk) is the kth partition.Theroughness of ai with respect to another attribute aj∈A on kth partition is defined as(9)RajEaiαk=1-Δ_ajEaiαk∇¯ajEaiαk.The average roughness ofai with respect to aj is defined as the mean of roughnesses of ai with respect to aj on all partitions towards ai. That is,(10)R¯ajai∣X=∑k=1VaiRajEaiαkVai.Note that, the average roughnessR¯aj(ai∣X) ranges from 0 to 1. When R¯aj∣X(ai)=0, it implies a crisp partitioning on attribute ai. When R¯aj(ai)=1, it implies a maximum rough partitioning on attribute ai. The smaller is R¯aj(ai∣X), the crisper is the partitioning on attribute ai [17, 21].Furthermore, theattribute roughness of ai, in symbols R¯(ai∣X), is the mean of average roughness of ai with respect to other attributes in Q:(11)R¯ai∣X=∑∀aj∈Q,aj≠aiR¯ajai∣XQ-1.Obviously,R¯(ai∣X) measures the effect of the partitioning using attribute ai toward all other attributes. It ranges from 0 to 1. The smaller is the R¯(ai∣X), the crisper is the partition [21].


### 4.2. Splitting a Cluster

Recall that it cannot always achieve the crisp partitioning in real world clustering cases, so we have to consider the partitioning scheme that leads to minimum uncertainty. Following this key, the goal of our algorithm is to minimize the roughness of data set.Given a specific subset ofC⊆U, we firstly search for the attribute that should be selected to conduct the splitting of C. Recall that the attribute roughness R¯(ai∣C) measures the effect of the partitioning using attribute ai. So, the attribute whose attribute roughness is minimal should be selected for splitting. Hence, the objective attribute is(12)a∗=arg⁡minai∈Q⁡R¯ai∣C.In what follows, we illustrate how to splitC into two partitions of C1 and C2 with the help of a∗, where C1∩C2=ϕ and C1∪C2=C.First of all, we define the summation of roughness ofai on partition Eai(α) as(13)γaiα=∑aj∈Q,aj≠aiRajEaiα.Secondly, we rankγa∗(αk) in ascending order. Suppose that the rank result is given as(14)γa∗α1≤γa∗α2≤⋯≤γa∗αVa∗.Given1≤r≤s≤Va∗, we define the following symbols:(15)Vr:s∗=⋃k=rsαk,Cr:s=x∣∀x∈C,fx,a∗∈Vr:s∗.Using these notations, the splitting ofC can be denoted by(16)FkC=C1:k,Ck:Va∗.The attribute roughness ofa∗ in C1:k and Ck:Va∗ is R¯C1:k(ai∣C1:k) and R¯Ck:|Va∗|(ai∣Ck:Va∗), respectively. Hence, the problem of determining the optimal splitting of C becomes the problem of finding a splitting point k to minimize the total roughness of the two subclusters. In other words, the optimal splitting point should be determined by finding out the optimal value of k∗ as(17)k∗=arg⁡mink⁡R¯C1:kai∣C1:k+R¯Ck:Va∗ai∣Ck:Va∗.


### 4.3.  Selecting Subclusters for Further Splitting

In the previous work, the Min-Min-Roughness [17] algorithm selects the subclusters having more objects for further splitting at subsequent iterations. However, if the uncertainty of a cluster having more objects is much smaller than that of another one which has less objects, it is rational to split the latter cluster for it contains much more intraitem dissonance than that of the former one. Therefore, we should choose the cluster for further clustering according to the degree of uncertainty within the cluster instead of the number of objects within the cluster.Thecluster roughness of a cluster C is defined as the summation of all attribute roughness in cluster C. That is,(18)RC=∑iR¯ai∣C.In this paper, we choose the clusters with the largest cluster roughness for further splitting. We also constrain that the size of selected cluster must be larger than a predefined threshold (minimum cluster size) so as to avoid the overclustering.We apply our method firstly on the universeU to split it into two subclusters. Then, we choose subclusters whose cluster roughness is the largest to repeat the procedures of splitting to obtain further partitions. We apply our algorithm recursively until the predefined termination condition is satisfied or no cluster is selected to be further splitting. The predefined termination condition is that either the passes of iteration or the number of clusters reaches their corresponding upper bound.


## 4.1. Roughness and Average Roughness

In order to deal with the uncertain information in data set and quantify the degree of the uncertainty, we define the some related concepts based on roughness [17, 21] as follows.Given an attributeai∈A and the domain of its possible values Vai={α1,α2,…,α|Vai|}, the family of all elementary sets with respect to ai in S is denoted by U/ai={Eai(α1),Eai(α2),…,Eai(α|Vai|)}, where Eai(αk) refers to a specific elementary set (with respect to ai) whose value of ai is αk (k=1,2,…,|Vai|). In essence, U/ai is indeed an n-partitioning (n=|Vai|) on U towards attribute ai and Eai(αk) is the kth partition.Theroughness of ai with respect to another attribute aj∈A on kth partition is defined as(9)RajEaiαk=1-Δ_ajEaiαk∇¯ajEaiαk.The average roughness ofai with respect to aj is defined as the mean of roughnesses of ai with respect to aj on all partitions towards ai. That is,(10)R¯ajai∣X=∑k=1VaiRajEaiαkVai.Note that, the average roughnessR¯aj(ai∣X) ranges from 0 to 1. When R¯aj∣X(ai)=0, it implies a crisp partitioning on attribute ai. When R¯aj(ai)=1, it implies a maximum rough partitioning on attribute ai. The smaller is R¯aj(ai∣X), the crisper is the partitioning on attribute ai [17, 21].Furthermore, theattribute roughness of ai, in symbols R¯(ai∣X), is the mean of average roughness of ai with respect to other attributes in Q:(11)R¯ai∣X=∑∀aj∈Q,aj≠aiR¯ajai∣XQ-1.Obviously,R¯(ai∣X) measures the effect of the partitioning using attribute ai toward all other attributes. It ranges from 0 to 1. The smaller is the R¯(ai∣X), the crisper is the partition [21].


## 4.2. Splitting a Cluster

Recall that it cannot always achieve the crisp partitioning in real world clustering cases, so we have to consider the partitioning scheme that leads to minimum uncertainty. Following this key, the goal of our algorithm is to minimize the roughness of data set.Given a specific subset ofC⊆U, we firstly search for the attribute that should be selected to conduct the splitting of C. Recall that the attribute roughness R¯(ai∣C) measures the effect of the partitioning using attribute ai. So, the attribute whose attribute roughness is minimal should be selected for splitting. Hence, the objective attribute is(12)a∗=arg⁡minai∈Q⁡R¯ai∣C.In what follows, we illustrate how to splitC into two partitions of C1 and C2 with the help of a∗, where C1∩C2=ϕ and C1∪C2=C.First of all, we define the summation of roughness ofai on partition Eai(α) as(13)γaiα=∑aj∈Q,aj≠aiRajEaiα.Secondly, we rankγa∗(αk) in ascending order. Suppose that the rank result is given as(14)γa∗α1≤γa∗α2≤⋯≤γa∗αVa∗.Given1≤r≤s≤Va∗, we define the following symbols:(15)Vr:s∗=⋃k=rsαk,Cr:s=x∣∀x∈C,fx,a∗∈Vr:s∗.Using these notations, the splitting ofC can be denoted by(16)FkC=C1:k,Ck:Va∗.The attribute roughness ofa∗ in C1:k and Ck:Va∗ is R¯C1:k(ai∣C1:k) and R¯Ck:|Va∗|(ai∣Ck:Va∗), respectively. Hence, the problem of determining the optimal splitting of C becomes the problem of finding a splitting point k to minimize the total roughness of the two subclusters. In other words, the optimal splitting point should be determined by finding out the optimal value of k∗ as(17)k∗=arg⁡mink⁡R¯C1:kai∣C1:k+R¯Ck:Va∗ai∣Ck:Va∗.


## 4.3.  Selecting Subclusters for Further Splitting

In the previous work, the Min-Min-Roughness [17] algorithm selects the subclusters having more objects for further splitting at subsequent iterations. However, if the uncertainty of a cluster having more objects is much smaller than that of another one which has less objects, it is rational to split the latter cluster for it contains much more intraitem dissonance than that of the former one. Therefore, we should choose the cluster for further clustering according to the degree of uncertainty within the cluster instead of the number of objects within the cluster.Thecluster roughness of a cluster C is defined as the summation of all attribute roughness in cluster C. That is,(18)RC=∑iR¯ai∣C.In this paper, we choose the clusters with the largest cluster roughness for further splitting. We also constrain that the size of selected cluster must be larger than a predefined threshold (minimum cluster size) so as to avoid the overclustering.We apply our method firstly on the universeU to split it into two subclusters. Then, we choose subclusters whose cluster roughness is the largest to repeat the procedures of splitting to obtain further partitions. We apply our algorithm recursively until the predefined termination condition is satisfied or no cluster is selected to be further splitting. The predefined termination condition is that either the passes of iteration or the number of clusters reaches their corresponding upper bound.


## 5. Determining Number of Clusters Based on MDL Principle

### 5.1. The Minimum Description Length Principle

The Minimum Description Length (MDL) principle which is proposed by Rissanen [25, 26] has been successfully applied to select the optimal model from a set of given stochastic models. The MDL principle asserts that the best model inferred from a given set of data is the one which minimizes the total description lengths of both the model and the encoding for the data with the help of the model.More specifically, when a set of models{θ(i)∣i=1,2,…,I} is given, the description length of an observation X={x1,x2,…,xN} using the ith model is given as(19)LiX=-log⁡PX∣θi+αi2log⁡N+log⁡I,where αi is the number of free parameters in the ith model.We note thatP(X∣θ(i)) denotes the likelihood of data X with respect to model θ(i). This term can also be viewed as the description length of the encoding of data X with the help of model θ(i). The second term in (19) is related to the complexity of model θ(i) and the size of observation data X. The third term is the code length representing the number of models for selection.


### 5.2. Determine the Number of Clusters Based on MDL

GivenS=(U,Q,V,ρ), let F(k)={C1(k),C2(k),…,Cnk(k)} be the classification of U in the kth iteration and let αai be a variable standing for the value of ai. For each class Cj(k), we calculate the entropy of ai with respect to Cj(k)∈Fk as follows:(20)HCjkαai=-∑αk∈VaiPCjkαklog⁡PCjkαk,where PCj(k)(αk)=P(ρ(x∈Cj(k),ai)=αk).For the sake of simplicity, we also denote the description length of universeU as follows:(21)HCjkU=∑∀ai∈QHCjkαai.The total description length of the information systemS in kth iteration is given by(22)Lk=∑jHCjkU︸Lk,1+k2log⁡C︸Lk,2+logI︸Lk,3,where the first term, L(k,1), in (22) is the description length of encoding data set U using the kth clustering scenario of F(k), the second term, L(k,2), is the length describing the complexity of F(k), and the last term, L(k,3), is the code length of representing the number of models for selection.Recall that, in each iteration, we select an optimal attribute for each candidate nodes to perform splitting procedure so as to minimize the roughness in the information systemS, so the uncertain information in S decreases. Therefore, as the recursive procedure of clustering goes further, the term of L(k,1) in (22) will decrease constantly. On the other hand, as the number of clusters in F increases, the classification F will become more and more complex and computational cost will increase. So, the second term of L(k,2) in (22) will increase. In particular, L(k,3) is a constant. In summary, the total description length of S will firstly decrease until it reaches the minimum value point and then increase.Thus, we can search for ak0 to minimize the value of Lk in (22):(23)k0=arg⁡mink⁡Lk.As a result, the number of clusters ink0th iteration is optimal.


## 5.1. The Minimum Description Length Principle

The Minimum Description Length (MDL) principle which is proposed by Rissanen [25, 26] has been successfully applied to select the optimal model from a set of given stochastic models. The MDL principle asserts that the best model inferred from a given set of data is the one which minimizes the total description lengths of both the model and the encoding for the data with the help of the model.More specifically, when a set of models{θ(i)∣i=1,2,…,I} is given, the description length of an observation X={x1,x2,…,xN} using the ith model is given as(19)LiX=-log⁡PX∣θi+αi2log⁡N+log⁡I,where αi is the number of free parameters in the ith model.We note thatP(X∣θ(i)) denotes the likelihood of data X with respect to model θ(i). This term can also be viewed as the description length of the encoding of data X with the help of model θ(i). The second term in (19) is related to the complexity of model θ(i) and the size of observation data X. The third term is the code length representing the number of models for selection.


## 5.2. Determine the Number of Clusters Based on MDL

GivenS=(U,Q,V,ρ), let F(k)={C1(k),C2(k),…,Cnk(k)} be the classification of U in the kth iteration and let αai be a variable standing for the value of ai. For each class Cj(k), we calculate the entropy of ai with respect to Cj(k)∈Fk as follows:(20)HCjkαai=-∑αk∈VaiPCjkαklog⁡PCjkαk,where PCj(k)(αk)=P(ρ(x∈Cj(k),ai)=αk).For the sake of simplicity, we also denote the description length of universeU as follows:(21)HCjkU=∑∀ai∈QHCjkαai.The total description length of the information systemS in kth iteration is given by(22)Lk=∑jHCjkU︸Lk,1+k2log⁡C︸Lk,2+logI︸Lk,3,where the first term, L(k,1), in (22) is the description length of encoding data set U using the kth clustering scenario of F(k), the second term, L(k,2), is the length describing the complexity of F(k), and the last term, L(k,3), is the code length of representing the number of models for selection.Recall that, in each iteration, we select an optimal attribute for each candidate nodes to perform splitting procedure so as to minimize the roughness in the information systemS, so the uncertain information in S decreases. Therefore, as the recursive procedure of clustering goes further, the term of L(k,1) in (22) will decrease constantly. On the other hand, as the number of clusters in F increases, the classification F will become more and more complex and computational cost will increase. So, the second term of L(k,2) in (22) will increase. In particular, L(k,3) is a constant. In summary, the total description length of S will firstly decrease until it reaches the minimum value point and then increase.Thus, we can search for ak0 to minimize the value of Lk in (22):(23)k0=arg⁡mink⁡Lk.As a result, the number of clusters ink0th iteration is optimal.


## 6. Computation Complexity

In this section, we discuss the complexity of our algorithm. Suppose that there are totallyn objects and m attributes are considered. The worst-case condition is that each attribute has distinct values for each object. That is, for each attribute ai, the cardinality of Vai is exactly equal to n (|Vai|=n) and the cardinality of the family of elementary sets with respect to this attribute is also equal to n (|U/{ai}|=n). Therefore, we need at most n comparisons for each object to judge whether it belongs to one elementary set. In the worst situation, we have to perform the n-comparison judgement for totally n elementary. So, the complexity of calculating the average roughness of ai to another attribute aj is n2. Since there are totally m attributes, the complexity of computing the attribute roughness of a specific attribute is m×n2. In the procedure of finding the partitioning attribute, we have to do m passes of attribute roughness calculations, so the complexity is m2×n2.On the other hand, in the worst case, the complexity forγai(α) in (13) is m×n, the complexity of sorting γai(α) is n, and the complexity for finding optimal splitting point in (17) is m×n2.In a summary, the total complexity of our algorithm isO(m2×n2+m×n+n+m×n2). For a large data set, the value of n is very large so the value of m could be considered as a constant comparatively. Thus, the complexity of our algorithm is O(n2).


## 7. Evaluation

The proposed algorithm is implemented in a system called RSCluster. In the first phase, the RSCluster is applied to clustering application layer traffic. Three data sets (i.e. data sets I, II and III, as shown in Table1) are collected from School of Information and Science Technology in Sun Yat-Sen University on August 8, 10, and 11, in 2012. Table 2 shows the detail information of our data sets.Table 1
Data sets for evaluation.
Data set
Collecting date
Total flows
Data set I
Aug 08, 2012
385
Data set II
Aug 10, 2012
1334
Data set III
Aug 11, 2012
683Table 2
Traffic class breakdown for data sets.
Application
Data set I
Data set II
Data  set III
Flows
Percent
Flows
Percent
Flows
Percent
FTP
82
21
.
%
1
0.1
%
1
0.1
%
SMTP
21
5.5
%
720
54.0
%
350
51.2
%
DNS
22
5.7
%
156
11.7
%
102
14.9
%
POP3
26
6.8
%
0
0.0
%
0
0.0
%
HTTPS
38
9.9
%
334
25.0
%
155
22.7
%
XunLei
11
2.9
%
1
0.1
%
1
0.1
%
MSSQL
0
0.0
%
1
0.1
%
0
0.0
%
eMule
44
11
.
%
34
2.5
%
14
2.0
%
BiTorrent
7
1.8
%
71
5.3
%
50
7.3
%
Kugoo
134
34.8
%
4
0.3
%
3
0.4
%
QQ
0
0.0
%
3
0.2
%
2
0.3
%
PPTV
0
0.0
%
1
0.1
%
0
0.0
%
BitSpirit
0
0.0
%
8
0.6
%
5
0.7
%
Total
385
1334
685The overall accuracy is used to evaluate the overall effectiveness of the proposed algorithm based on rough sets theory. The dominating application in a cluster is used to label the cluster. Thus, the overall accuracy of clustering is defined as the ratio from the number of flows labeled correctly in all clusters to the total number of flows in the data set.Suppose that the number of flows labeled correctly in a cluster ofci is referred to as the True Positives (TP), denoted by Ti. Thus, the overall accuracy is given as θ=∑i‍Ti/N, where N is the total number of sessions in data set.Other metrics are listed as follows.False negative (FN) is the number of sessions which are incorrectly classified as not belonging to a cluster.False positive (FP) is the number of sessions that are incorrectly classified as belonging to a cluster.True negative (TN) is the number of sessions that are correctly classified as not belonging to a cluster.There are a total of 26 features used in our experiments, including the transport layer protocol type (TCP or UDP), transport layer port number, and the 4-byte fields occurring in the messages.In the domain of traffic classification, Moore and Papagiannaki [27] and Ye et al. [28] show that effective application signatures with high accuracy can be generated using the first N bytes of each flow. Haffner et al. [29] present three main motivations for limiting the data size to first N bytes. (1) It is helpful for identifying traffic as early as possible. (2) Most application layer headers at the beginning of a data exchange are easy to be identified. (3) It allows the proposed algorithm to process less amount of data.Therefore, it is enough to capture sufficient information about the class characteristic of message by considering the first 4-byte field (field 1), the second 4-byte field (field 2), the last 4-byte field (field 3), and the last but second 4-byte field (field 4) in each message as shown in Figure1.Figure 1
Four-byte fields in application layer messages.Previous researches [27–30] also indicate that concrete signature usually exists in the first few packets of a connection. So, for each session, it is sufficient to consider the first 6 messages as shown in Figure 2. If the corresponding feature does not exist, a special string “NULL” would be used in that position.Figure 2
Messages exchanged between two hosts. “m1,” “m2,”… stand for messages exchanged between host A and host B. Only the first 6 messages are considered in the experiments.Since RSCluster has no prior information about data set, the exact number of clusters is totally unknown to our system. In order to determine an appropriate number of clusters, the MDL criteria are applied to choose a clustering model whose description length is the minimum. The candidate models are the mediate results in each pass of the clustering process. Figure3 illustrates the description length for the three data sets. For example, in data set I, the minimum value of total description length is taken in 21st iteration.Figure 3
Description lengths.Figure4 shows the overall accuracy as the iterations increase. As we see, the overall accuracy of RSCluster increases at first until it reaches an upper bound. The reason for this upper bound is that there is no longer cluster selected by RSCluster for further splitting so the number of cluster no longer changes. Recall that, RSCluster chooses the cluster whose cluster roughness is largest as the candidates for further splitting. Thus, if all cluster roughness is 0 or the cluster size of each candidate is smaller than the minimum cluster size, no cluster will be chosen to split any more.Figure 4
The overall accuracy of clustering. “RST” stands for the proposed RST-based algorithm, “KMs” stands forK-means algorithm and “EM” stands for the Expectation-Maximization algorithm.We also implement EM andK-means algorithm to cluster the same data sets. We repeat the two clustering algorithms for 200 iterations. In the kth iteration, we set the expected number of clusters to k. As shown in Figure 4, the proposed RST-based clustering algorithm excellently outperforms EM andK-means algorithms.


### 7.1. Message Grouping for Improving Protocol Reverse Engineering

In the second phase, the RSCluster is used to cluster application layer messages to improve the protocol reverse engineering accuracy. The traffic is captured from School of Information and Science Technology in Sun Yat-Sen University during April, 2011. The traffic has been classified into 4 classes of protocols (i.e., HTTP, POP, SMTP, and FTP) using the well-known network traffic analysis tool named Wireshark. In this experiment, the RSCluster is used to cluster messages for each protocol to improve the results of reverse engineering. The features used in this experiment include message direction (i.e., from the initiator to responder or from the responder to initiator) and the 4-byte fields in the messages as shown in Figure1. The parameters and procedures are the same as Section 7.1. The grouped messages are taken as input into AutoReEngine [4] to extract protocol keywords. The protocol keywords extracted by AutoReEngine are shown in Table 3. The keywords in italic (e.g.,POST, Origin:, Cache-Control:, ITYPE:,andOTYPE:) are those keywords with low occurrence probability.Table 3
Protocol keywords extracted by AutoReEngine.
Protocol
Results without message grouping
Results with message grouping
HTTP
GET /,  Referer: http://,  Date:,  HTTP/1.1,  Keep-Alive,  Accept:,  Content-Length:, Last-Modified:,  Accept-Encoding: gzip,  Server:,  Content-Type:,  Connection:,  Accept-Language: zh-cn,  Host:,  200 OK,  User-Agent: Mozilla/
GET /,  Referer: http://,  Date:,  HTTP/1.1,  Keep-Alive,  Accept:,  Content-Length:, Last-Modified:,  Accept-Encoding: gzip,  Server:,  Content-Type:,  Connection:,  Accept-Language: zh-cn,  Host:,  200 OK,  User-Agent: Mozilla/,Origin:, Cache-Control:,  POST,  ITYPE:,  OTYPE:
POP
USER,  PASS,  STAT,  DATA,  +OK Welcome to coremail Mail Pop3 Server,  +OK core mail,  message(s) [,  +OK,  byte(s)]
USER,  PASS,  STAT,  DATA,  +OK Welcome to coremail Mail Pop3 Server,  +OK core mail,  message(s) [,  +OK,  byte(s)]LIST,  UIDL,  CAPA
SMTP
EHLO,  250-PIPELINING,  220,  250-SIZE,  250-AUTH=LOGIN,  250 8BITMIME,  334,  DATA,  250-AUTH LOGIN PLAIN,
EHLO,  250-PIPELINING,  220,  250-SIZE,  250-AUTH=LOGIN,  250 8BITMIME,  334,  DATA,  250-AUTH LOGIN PLAIN,QUIT,  RCPT TO,  MAIL FROM
FTP
USER,  PASS,  331,  30,  220,  ready…,  User,  logged in.
USER,  PASS,  331,  30,  220,  ready…,  User,  logged in. QUIT,  PSAV,  SIZE,  CMD,  150,  530


## 7.1. Message Grouping for Improving Protocol Reverse Engineering

In the second phase, the RSCluster is used to cluster application layer messages to improve the protocol reverse engineering accuracy. The traffic is captured from School of Information and Science Technology in Sun Yat-Sen University during April, 2011. The traffic has been classified into 4 classes of protocols (i.e., HTTP, POP, SMTP, and FTP) using the well-known network traffic analysis tool named Wireshark. In this experiment, the RSCluster is used to cluster messages for each protocol to improve the results of reverse engineering. The features used in this experiment include message direction (i.e., from the initiator to responder or from the responder to initiator) and the 4-byte fields in the messages as shown in Figure1. The parameters and procedures are the same as Section 7.1. The grouped messages are taken as input into AutoReEngine [4] to extract protocol keywords. The protocol keywords extracted by AutoReEngine are shown in Table 3. The keywords in italic (e.g.,POST, Origin:, Cache-Control:, ITYPE:,andOTYPE:) are those keywords with low occurrence probability.Table 3
Protocol keywords extracted by AutoReEngine.
Protocol
Results without message grouping
Results with message grouping
HTTP
GET /,  Referer: http://,  Date:,  HTTP/1.1,  Keep-Alive,  Accept:,  Content-Length:, Last-Modified:,  Accept-Encoding: gzip,  Server:,  Content-Type:,  Connection:,  Accept-Language: zh-cn,  Host:,  200 OK,  User-Agent: Mozilla/
GET /,  Referer: http://,  Date:,  HTTP/1.1,  Keep-Alive,  Accept:,  Content-Length:, Last-Modified:,  Accept-Encoding: gzip,  Server:,  Content-Type:,  Connection:,  Accept-Language: zh-cn,  Host:,  200 OK,  User-Agent: Mozilla/,Origin:, Cache-Control:,  POST,  ITYPE:,  OTYPE:
POP
USER,  PASS,  STAT,  DATA,  +OK Welcome to coremail Mail Pop3 Server,  +OK core mail,  message(s) [,  +OK,  byte(s)]
USER,  PASS,  STAT,  DATA,  +OK Welcome to coremail Mail Pop3 Server,  +OK core mail,  message(s) [,  +OK,  byte(s)]LIST,  UIDL,  CAPA
SMTP
EHLO,  250-PIPELINING,  220,  250-SIZE,  250-AUTH=LOGIN,  250 8BITMIME,  334,  DATA,  250-AUTH LOGIN PLAIN,
EHLO,  250-PIPELINING,  220,  250-SIZE,  250-AUTH=LOGIN,  250 8BITMIME,  334,  DATA,  250-AUTH LOGIN PLAIN,QUIT,  RCPT TO,  MAIL FROM
FTP
USER,  PASS,  331,  30,  220,  ready…,  User,  logged in.
USER,  PASS,  331,  30,  220,  ready…,  User,  logged in. QUIT,  PSAV,  SIZE,  CMD,  150,  530


## 8. Conclusion

The RST is a powerful mathematical tool for dealing with categorical data and uncertain information. We propose to apply a RST-based approach to cluster application layer network traffic and group protocol messages according to message types. The key of our approach is to consider multidimension categorical attributes based on rough sets theory and diminish the dissonance hidden in the data set. With the concepts introduced from the field of rough sets theory, the dissonance hidden in the data set can be quantified by the notion of roughness. The proposed approach aims to minimize the total roughness in the data set by selecting the clusters with the largest cluster roughness for further splitting in each iteration of clustering. The proposed approach is also unsupervised and the optimal number of clusters is determined by the Minimum Description Length principle. The experimental results show that our method can cluster the application layer payload with a high accuracy and group the protocol messages effectively to improve the accuracy of protocol keyword extraction. Some protocol keywords with low occurrence probability can be found with the help of message grouping by our method. In the future work, we will apply the hierarchical data structure and semantic information in the traffic to further improve the accuracy of traffic clustering.



---

*Source: 962974-2015-06-02.xml*