A new method of constructing classifiers from huge volume of temporal data is proposed in the paper. The novelty of introduced method lies in a multi-stage approach to constructing hierarchical classifiers that combines process mining, feature extraction based on temporal patterns and constructing classifiers based on a decision tree. Such an approach seems to be practical when dealing with huge volume of temporal data. As a proof of concept a system has been constructed for packet-based network traffic anomaly detection, where anomalies are represented by spatio-temporal complex concepts and called by behavioral patterns. Hierarchical classifiers constructed with the new approach turned out to be better than ”flat” classifiers based directly on captured network traffic data.
Classifiers (decision algorithms) constitute the kernel of decision systems that are
ubiquitous in many areas of IT systems like data mining, knowledge discovery, expert
systems etc. [
Making progress in this field is extremely crucial, among other things, for the development of intelligent systems processing huge volume of data. Therefore, developing methods of detecting process models and their properties from data and proving their effectiveness in different applications are of particular importance for further development of decision supporting systems in many domains such as medicine, finance, industry, transport, telecommunication, and others.
The paper deals with a problem of process mining and constructing classifiers from huge volume of temporal data. The presented approach combines automatic methods of detecting processes and their properties with domain knowledge obtained from experts. Interaction with domain experts facilitates guiding the process of discovering patterns and models of processes and makes the process computationally feasible. The novelty of introduced method lies in a multi-stage approach to constructing hierarchical classifiers that incorporates: – a process mining – during the learning stage data are grouped and represented as a state graph, which reduces the data size significantly; – a features extraction based on temporal patterns – which takes the form of LTL temporal logic formulas, may be defined by experts or discovered from the learning data; – a classifier construction – a classifier is constructed with temporal patterns identified from the learning data i.e. it is based on information about presence or absence of individual behavioral patterns in the analyzed data.
The paper is organized as follows. Section 2 presents an overview of the considered approach to classifiers construction. Classifiers based on decision trees are described shortly in Section 3. Section 4 deals with a system for packet-based network traffic anomaly detection implemented with the new approach introduced in the paper. A short summary is given in the final section. 2
The general scheme of constructing of hierarchical classifiers is given in Fig. 1. Let A = fa1; : : : ; akg denote a set of attributes selected to describe important features of the system under consideration. The starting point of the presented approach are data describing values of the attributes in a sequence of time points t1; t2; : : : . These learning data can be presented in a table as shown in Fig. 2. The data are considered from two points of view. In the first stage the whole input data are used to construct the so-called state graph. This is the process mining stage. In the consecutive stages, we use the learning data sliced into pieces called time windows. In the network traffic anomaly detection system presented in Section 4 a constant length of time windows has been used. However, this limitation can be omitted and in general changeable time window length can be used.
The process mining stage concerns building a state graph. However, before the process mining is started, rows from the learning data table (called here time points) are grouped with a metric that describes the similarity (distance) between time points. In this paper we use a well-known in literature k-means method of clustering. The learning data t a1 a2 . . . ak tt12 vv1121 vv2221 .. .. .. vvkk21 . . . . . . . . . . . . . . . tn v1n v2n . . . vkn . . . . . . . . . . . . . . . sliced data (time windows) s1 s5
s2
time window path
s3
process discovery
experts knowledge
metric is based on time point attributes. Our method of process mining works on the
data after clustering, i.e., on the data that can be represented by a sequence of groups
(clusters). For such data we use the method from [
Temporal patterns take the form of temporal logic formulas. LTL [
The hierarchical classifier considered in the paper is based on the high level learning
data described in the previous section. We consider the classifier that is based on the
so-called decision tree of the local discretization (see, e.g., [
Meanwhile, for symbolic attributes the first one is a set of objects for which the value of the attribute a is equal to v, and the second set is a set of objects for which the a attribute value is different from v. Moreover, any cut (a; v) defines two templates, where by a template we understand a description of some set of objects. In case of numerical attributes, the first template defined by a cut (a; v) is a formula T(a;v) = (a(u) < v) and the second template defined by a cut (a; v) is a formula :T(a;v) = (a(u) v). In case of symbolical attributes, the first template defined by a cut (a; v) is a formula = (a(u) = v) and the second template defined by a cut (a; v) is a formula As a measure of the binary partition quality the number of pairs of objects distinguishable by partition and having different values of the decision attribute can be used. For example, if a partition (a; v) divides objects into two sets of sizes M and N , and the first of these collections have M0 and M1 objects from the class C0 and C1 respectively, and in the second one we have N0 and N1 objects from the decision class C0 and C1, then the number of pairs of objects discerned by the partition is given by: N1 M0 + M1 N0. If we determine the value of this measure for all possible cuts, then we can choose one of the cuts and divide the entire set of objects into two parts on its basis. Of course, this approach can be easily generalized to the case of more than two decision classes.
It should be noted that this measure of the quality of the binary partition of set of
objects can be calculated for the given cut in time O(n), where n is the number of
objects in the decision table (see, e.g., [
The quality of cuts may be computed for any subset of a given set of objects. In the local strategy of discretization, after finding the best cut and dividing the objects set into two subsets of objects (matching both templates mentioned above for a given cut), this procedure is repeated for each object from the set separately until a stop condition holds. At the beginning of the procedure we have the whole set of objects at the root of the tree. Then, we recursively apply the same splitting procedure to the emerging parts that we assign to tree nodes at higher and higher levels. Stop condition of partition is designed so that the given part is not divided (becomes a leaf tree) if it contains only objects from one decision class (optionally the objects from the given class constitute a certain percentage, which is treated as a parameter of the method) or the considered cut does not have any effect, i.e., there are no new pairs of objects from different decision classes separated by the cut.
In this paper, we assume that the partition stops when all objects from the current set of objects belong to the same decision class. Hence, the local strategy can be realized by using decision tree (see Fig. 3).
u a; c a(u) c
a(u) < c
Besides the number of pairs of objects distinguishable by partition, in our
experiments we also use two other measures of the quality of cuts well known in literature
that were used in other methods of decision trees construction. It is a measure called
a Gini index (used in the algorithm CART [
The decision tree computed during local discretization can be treated as a classifier for the concept C represented by decision attribute from a given decision table A. Let u be a new object and A(T ) be a subtable containing all objects matching the template T defined by the cut from the current node of a given decision tree (at the beginning of algorithm run T is the template defined by the cut from the root). We classify object u starting from the root of the tree as shown in the algorithm presented in Fig. 4. 1: Step 1 2: if u matches template T found for A then 3: go to subtree related to A(T ) 4: else 5: go to subtree related to A(:T ) 6: end if 7: Step 2 8: if u is at the leaf of the tree then 9: go to Step 3 10: else 11: repeat 1–2 substituting A(T )) or A(:T )) for A 12: end if 13: Step 3 14: Classify u using the decision value attached to the leaf
Note that the above decision tree can be treated directly as a classifier, as test objects can be classified by stating to which leaf of the tree they belong. This is possible because, thanks to the designated partitions, one can trace membership of an object in the path from the root to the leaf, and then classify the object to the decision class whose objects dominate in the leaf.
As a proof of concept for the approach considered in the paper a system for
packetbased network traffic anomaly detection has been constructed. Network anomaly
detection is becoming an essential area of research. The growing number of IP networks
threats and the growing volume of transmitted data require new methods of network
traffic data analysis [
22 items ...
INTERNET router with
NAT watchdog computer AD server
auxiliary server
For the purpose of this work, a part of the university network was selected to capture data for analysis. The network topology is given in Fig. 5. The experiment environment consists of 22 work stations with Windows 7 operating system, Active Directory server, a watchdog computer (Windows 7) and auxiliary server with Windows Server 2008 R2 operating system. The NAT router has been used to separate the network from the whole university network and to provide an access to the Internet. The router is equipped with a mirror port used to send copies of all packets to the watchdog computer. The auxiliary server provides FTP (port 21), RDP (port 3389) and MySQL (port 3306) services.
The Wireshark 1.10.7 software was used to monitor the network traffic. It provides the possibility of real time observing of sending and receiving packets for the given interface and to backup them to pcapng files. The network traffic was monitored from May 26 to 28 using one of laboratories of the Interdisciplinary Centre for Computational Modelling at University of Rzeszow. The typical network traffic generated by students lessons was captured as the legitimate traffic. Further to that, each day we generated four different network traffic anomalies including network scan, IP-spoofed scanning and brute force. The result of network traffic capturing was three 24-hours data sets in the form of pcapng files presented in Table 1.
Captured data were converted into csv files. Received time points were described with attributes presented in Table 2. where D 2 [0; 1] and dp(ai; aj ) = dq(ai; aj ) = 0 : p(ai) = p(aj ); 1 : p(ai) 6= p(aj ); 0 : q(ai) 2 Xj ^ q(aj ) 2 Xj ; 1 : q(ai) 2 Xj ^ q(aj ) 2 Xk ^ j 6= j; (1) (2) (3)
Cluster15 dec=[0 (229)] 40 21 Fig. 6. Part of th9e state grap7h Classifiers for Behavioral Patterns Identification . . .
3 2 9 where equation (2) is us1ed fo2r attributes ipFlags, tcpFlags and icmpType, while equation (3) is used for attributes length, ttl and udpLength using ranges presented in Table 3. 2
Fc0 Fc2 Fc3 Fc4 Fc5 Fc6 Fc7 Fc9 Fc11 Fc12 Fc13 Fc15 Fc18 Fc19 F(c1 , Xc8)
F(c7 , Xc10) F(c7 , Xc14) F(c7 , Xc16) F(c7 , Xc17) F(c8 , Xc1) F(c10 , Xc7) F(c10 , Xc14) F(c10 , Xc16) F(c10 , Xc17) F(c14 , Xc7) F(c14 , Xc10) F(c14 , Xc17) F(c16 , Xc7) F(c16 , Xc14) F(c16 , Xc17)
F(c17 , Xc7) F(c17 , Xc10) F(c17 , Xc14) G(c1 ) Xc8) G(c7 ) Xc16) G(c7 ) X(c14 _ c16)) G(c7 ) X(c10 _ c14 _ c16 _ c17)) G(c8 ) Xc1) G(c10 ) X(c7 _ c14 _ c16 _ c17)) G(c14 ) Xc7) G(c14 ) X(c7 _ c10 _ c17)) G(c16 ) Xc7) G(c16 ) X(c7 _ c14)) G(c16 ) X(c7 _ c14 _ c17))
G(c17 ) X(c7 _ c19 _ c14))
Finally, we received the state graph with 20 nodes. The graph is stored in the dot
format and can be visualized automatically with xdot or similar software. Part of the
state graph for the considered system is presented in Fig. 6. Let ci denote the i-th node
(cluster) in the graph. Based on the expert knowledge the temporal patterns presented
in Fig. 7 were used in the system. After a few experiments the time windows length
equal to 15 was chosen. Data captured May 26 were used as the learning data, while
data captured May 27 were used to check the hierarchical classifier accuracy. The
hierarchical classifier was compared with a ”flat” classifier built for learning data without
using grouping, state graphs and temporal patterns. Both classifiers (hierarchical and
flat) are based on binary trees described in Section 3, but three measures of cut quality
were used: pair indiscernibility, entropy and Gini index (see Section 3). The decision
attribute takes one of five values 0–4, where 0 denotes the legitimate traffic, while
values from 1 to 4 denote four types of network traffic anomalies. It is worth noticing
that each of these decision values represents certain spatio-temporal complex concept,
which describes the specific behavior of a network user in a certain period of time. This
behavior we call here as a behavioral pattern. Besides, the prediction of such a decision
value we call an identification of a behavioral pattern. Note that each behavioral pattern
can be represented as a subgraph of the state graph (see [
The results of experiments are given in Table 4, where class stands for the anomaly type and cov for coverage. A new approach for constructing classifiers from huge volume of temporal data has been presented in the paper. Hierarchical classifiers considered in the paper combine process mining, extraction of attributes on the basis of temporal patterns and constructing classifiers based on decision trees methods. A system for network traffic anomaly detection has been constructed as a proof of concept. The hierarchical classifier constructed for the anomaly detection system turned out to be better than a classifier built for learning data without using grouping, state graph and temporal patterns. Omitting traffic anomalies classes 1 and 2, where both approaches failed to identify the anomalies, for remaining classes our method was even 30% better. The approach can be used in many domains such as medicine, finance, industry, transport, telecommunication, and others. The network traffic was chosen due to the possibility of capturing huge volume of learning data.
This work was partially supported by the Polish National Science Centre grant DEC2013/09/B/ ST6/01568 and by the Centre for Innovation and Transfer of Natural Sciences and Engineering Knowledge of University of Rzeszów, Poland.