Related work on attack correlation

In a situation where there are intensive attacks, not only will actual alerts be mixed with false alerts, but the amount of alerts will also become unmanageable [3]. The actual experience of intrusion detection practitioners indicates, “Encountering 10–20,000 alarms per sensor per day is common” [4]. Therefore, it is challenging to analyze intrusion alerts without the help of an alert correlation process, particularly due to the large amount of alerts produced by IDSs. Some previous methods are limited, in that they are restricted to known attack scenarios or those that can be generalized from known scenarios. While the authors in [3] propose to correlate the alerts generated by IDSs using prerequisites and consequences of the corresponding attacks, intuitively, the prerequisite of an attack is the necessary condition for the attack to be successful. The results show that their correlation method not only correlates related alerts and uncovers the attack strategies, but also provides a way to differentiate between alerts.

Other research suggests using appropriate attack correlation techniques to handle large collections of alerts, such as in [1], where the authors have developed a two-layered PA-based (primitive attack-based) correlation approach to tackle the problem. The first layer does PA construction by integrating related alerts into proper PAs. The second layer is the attack subplan-based correlation layer, which attacks a scenario correlation from recognized PAs by employing attack subplan templates to guide the correlation process. In [5], the authors indicate that alert correlation techniques effectively improve the quality of alerts reported by intrusion detection systems and are sufficient to support rapid identification of ongoing attacks. The research focuses on ways to develop the intrusion alerts correlation system according to the authors’ XSWRL ontology-based alert correlation approach.

Related work on semantic networks

A semantic network or net is a graphic notation for representing knowledge in patterns of interconnected nodes and arcs. Computer implementations of semantic networks were first developed for artificial intelligence and machine translation, but earlier versions have long been used in philosophy, psychology, and linguistics. Sowa gives a descriptive outline on the types and use of semantic networks in different disciplines in [6,7]. Semantic networks have long been used to represent relationships [8]. Pearl used probabilities in semantic networks and performed extensive work in applying statistics and probability in causal semantic networks [9,10] to derive such networks from observed data. What is common to all semantic networks is a declarative graphic representation that can be used to either represent knowledge or support automated systems for reasoning about knowledge. Some versions are highly informal, while other versions are formally defined systems of logic.

There are some applications on applying semantic networks in different domains. The work in [11] describes a new metadata approach to elicit semantic information from environmental data and implement semantics-based techniques to assist users in integrating, navigating, and mining multiple environmental data sources. Another paper [12] has applied semantics in the domain of software engineering and provided methods to discover relevant software artifacts to increase software reuse and reduce the cost of software development and maintenance. It proposes a metadata approach with Semantic Networks that convey existing relationships between software artifacts. This approach reveals additional relevant artifacts that the user might have not been aware of. In this chapter, we discuss how to apply semantic networks in identifying related network attacks in the cyber-security domain and how it is used to increase the precision in detecting probable attacks with probability of occurrence.

Related work on the Bayesian probability model

Bayesian networks have been established as a ubiquitous tool for modeling and reasoning under uncertainty [13], and there are several existing applications in which the Bayesian probability model has been applied to intrusion detection systems [14–16].

One recent paper [17] presents work on justifying uncertainty modeling for cyber-security, with initial evidence indicating that it is a useful approach. The authors report their current efforts on identifying the important types of uncertainty and on using Bayesian networks to capture them for enhanced security analysis. They also build an example Bayesian network based on a current security graph model and justify their modeling approach through attack semantics. Experimental study shows that the resulting Bayesian network is not sensitive to parameter perturbation. Their work serves as a good foundation for us to apply the Bayesian network as our probability model on a cyber-security dataset, and use it to find out initial attacks located in our semantic network with a high probability of occurrence. In other words, the Bayesian probability model is used to predict the starting node in our semantic network, and then we can identify other relevant attacks with a high probability of occurrence in the current network situation.

Similarity-based semantic network

Let X={x₁,....x_n} be the set of network attacks, where each x_i X is associated with a set of characterizing attributes a₁={a_i1,.... a_im}. These attributes may be mixed with numeric values and categorical values. By applying discretization, the numeric values of these features can be transformed into categorical values (binary) and form a feature vector f₁={f_i1,.... f_im}. In order to automatically create a similarity-based network, we first need to generate the feature vector associated with each attack. These feature vectors are used to determine how similar the attacks are in terms of the attributes characterizing them; they are then utilized to generate the semantic network. Especially in this research, the weighted frequency feature values in attack feature vectors are used to prepare for the binary feature vector, and the absolute cutoff data transformation [18] has been used to convert weighted frequency feature values into binary values of 0 and 1. Since each attack has more than one attribute that formed as one feature vector, in order to determine the similarity between attacks by taking consideration of different attributes, the union of all feature vectors creates a universal vector (V) that containing all attack attributes, which is V= {a_i1 a_21,... a_im}. And then V will be used for the similarity-based semantic network creation.

We then use different similarity coefficients to quantify the similarity among universal feature vectors of the attacks. Based on the similarity coefficients, we connect similar nodes using edges and start creating the first mode semantic network.

Given a pair of nodes x_p and x_q, such that there exists a similarity between the two nodes, the probability w_pq of traversing from node x_p to x_q is:

S_pq is one of the similarity coefficients between the feature vectors of attacks (nodes) x_p and x_q. S_pj is the weighted degree of the node p, and k is the number of incident edges on p. Thus, based on the similarity and probability computations, we automatically construct a first mode semantic network, as shown in Figure 27.1(a), which we refer to as a Similarity Based Semantic Network.

Below, we formally define the first mode semantic network as follows:

Definition 1 [Similarity Based Semantic Network]: Let X={x₁,... x_n} be the set of attacks, where each x_i X has a feature vector f₁={f_i1,…. f_im}, then a first mode similarity based network N^sn(V^sn, E^sn) is a directed graph where V^sn is a set of nodes and E^sn is a set of edges, such that V^sn X and |V^sn| |X|, and each edge links two relevant attacks <v_i, v_j> and has a probability score w(v_i,v_j) where 0<w(v_i,v_j)1.Definition 2 [Similarity Coefficient]: Similarity coefficients serve as an effective tool for measuring the similarity among objects in a dataset. In [19], the authors surveyed 35 different coefficients composed of four variables: a, b, c, and d. When objects o_i and o_j are evaluated for similarity, each object is associated with features f₁, …, f_n having values 0 or 1. The concept is illustrated in Figure 27.2.

In Figure 27.2, (a) represents the number of positive matches such that o_i and o_j both have a value of 1, (b) indicates the number of mismatches such that o_i has a value of 1 and o_j has a value of 0, (c) represents the number of mismatches such that o_i has a value of 0 and o_j has a value of 1, and (d) represents the number of negative matches such as o_i and o_j both have a value of 0.

Based on the empirical evaluation results from [19], we select three similarity coefficients that have high accuracy, precision, and recall: Anderberg, Jaccard/Tanimoto, and Simple Matching. These are used in creating different similarity based semantic networks in order to compare the performance of the similarity coefficients methods applied in cyber-security field. Their calculation formulas are defined as following (the symbols a, b, c, and d refer to those described in Figure 27.2):

Pearson’s correlation coefficient is also chosen to create another kind of Semantic Networks in our research, since it has been widely used in the cyber-security domain. Pearson’s correlation coefficient between two objects is defined as the covariance of the two objects “cov (X, Y)” divided by the product of their standard deviations “σ_X•σ_Y.” The formula is shown as:

We next describe how to generate a relevance score “rs,” based on one of above similarity coefficients.

Definition 3 [Relevance Score]: If v_i and v_j are two nodes in a semantic network N (E, V), there are k paths p₁,…, p_k between v_i and v_j, where path p_l (1l k) consists of nodes v_l1,…, v_l|pl|+1 (|p_l| is the length of path p_l). The relevance score rs, defined between v_i and v_j, is

This formula computes the relevance score between v_i and v_j as the maximum relevance score of all paths connecting v_i and v_j. For each such path, the relevance score between the two endpoints is computed as the product of relevance scores for all edges along the path.

Here we give a concrete example to explain how we generate relevance score “rs” based on one of similarity coefficients, “Jaccard.” Suppose we have six objects, and according to Jaccard’s coefficient calculation, we get pair-wise similarity scores stored, as shown in Table 27.1. One example pair of the objects’ relevance score in a semantic network computed between object 1 and object 2 is the maximum relevance score of all paths connecting object 1 and object 2. Thus, a relevance score of 0.81 by object 1 and object 2 in Table 27.2 indicates that rs (1, 2)=rs (1, 6) * rs (6, 2)=0.9 * 0.9=0.81.

Rule enforced semantic network

The automatically created first mode semantic networks—by using only similarity measures—do not include any of the semantic information that domain experts usually expect. Particularly in the cyber-security domain, this type of additional semantic information can be described as semantic rules. Semantic rules explicitly identify the connectivity relationship between two network attacks, which can be extracted from domain knowledge and represented as taxonomy and ontology. Some connectivity relationships described by semantic rules among attack nodes may not be the same as the results by similarity measures in the first mode semantic network, so we use semantic rules to adjust our previous attack correlation results to generate a rule-enforced semantic network.

Definition 4 [Semantic Rule]: Given two attack nodes x_p and x_q, a semantic rule “s” is defined as: x_p, x_q, where s_pq is the semantic score associated with these two attacks, extracted from domain expertise such as taxonomy. If two attack nodes x_p and x_q fall into same category of network attacks defined by taxonomy, we set the value of s_pq equal to 1. Otherwise, when x_p and x_q do not belong to the same attack category, the value of s_pq is set to 0.

Next, s_pq will be used to adjust the previous relevance score rs_pq given by a predefined threshold σ from domain experts. When the absolute value of | s_pq-rs_pq |>σ, it indicates that rs_pq needs to be updated by semantic rules, and the degree of the adjustment noted as ad_Degree, below, will also be customized by domain experts in order to reflect the most appropriate relevance score among attacks in the current network environment. Hence, there are two possible ways to update the previous relevance score:

(a) If the value of (s_pq-rs_pq)>0, the updated relevance score is RS’_pq=rs_pq+|s_pq-rs_pq|× ad_Degree.

(b) If the value of (s_pq-rs_pq)<0, the updated relevance score is RS’_pq=rs_pq–|s_pq-rs_pq|× ad_Degree.

Experiment data

We selected the KDD CUP 99 data set [20] that was made available at the Third International Knowledge Discovery and Data Mining Tools Competition. This training dataset was originally prepared and managed by MIT Lincoln Labs [21], and the objective was to survey and evaluate research in intrusion detection. There are 494,021 network connection events in this dataset and among them, 75 percent of the data is used to build our semantic network and train our Bayesian probability model, and the other 25 percent of the data is used to evaluate the performance of our approach. In addition, a set of 41 different features is used to decide whether a selected sequence of events is an attack or a normal behavior. Twenty-three attack types were used in this data set. Among these network connection records, 20 percent of them represent normal patterns.

We next give some sample sequences of network connection events in the dataset we used in our research, as shown in Table 27.3:

The seven columns represent features that describe these network connection events. We only show a random seven features out of a total 41 features in the entire dataset. The labels in the last column indicate whether the sequence of events is a normal behavior or a kind of network attack, such as Guess_password or Load Module. These labels are also used to verify the performance of our four different similarity-based semantic networks.

Experiment process

We create four different semantic networks using the same network connection dataset through a two-step approach mentioned in the section titled “Methodology”: (1) Four different similarity based semantic networks were created based on four kinds of similarity measures, including Anderberg, Jaccard, Simple Matching, and Correlation Coefficient. (2) We use domain expertise from a well-known attack taxonomy as semantic rules in our research. This attack taxonomy defined attack categories by consequence at MIT Lincoln Lab [22], as shown in Table 27.4. We next use it to adjust each similarity based semantic network from step 1, and finally, we generate four-rule enforced semantic networks, respectively.

The Bayesian probability model is also applied to sequences of the network connection event dataset to calculate the probability of occurrence for all attacks. In our experiments, we utilize the Bayesian probability model to identify attacks with a high probability of occurrence for every sequence. After we get these initial attack prediction results, we can locate them as initial nodes in our semantic networks to find other relevant attacks. Figure 27.3 shows the steps of initial attack predicted by the Bayesian probability model in our research process.

Next we give a concrete example of how our semantic network can be used to identify relevant attacks with a high probability of occurrence in the current network situation. We see in Table 27.5, for the ID=73727 sequence of events, a Bayesian prediction model is first used to identify the attack type “Rootkit” as the highest probability of occurrence in the network. We then locate “Rootkit” as an initial node in our rule-enforced semantic network shown in Figure 27.1(b). Our approach automatically indicates other attack types relevant with “Rootkit” and connects them with corresponding relevance scores. The second column, “Actual Label” is used to verify the performance of the semantic network. In this case, the attack “Perl” is predicted by the semantic network with the highest relevance score, and it is just the right attack label for sequence ID=73727. Thus, for this case, the semantic network performs very well to increase the precision in detecting probable attacks with a high probability of occurrence.

Performance measures

Three metrics—precision, recall, and F-measure—have been applied to evaluate our approach as follows:

Experiment results

We evaluate the four different semantic networks based on four various similarity measures, including Anderberg, Jaccard, Simple Matching, and Correlation Coefficient.

One important parameter in our approach is the user-defined threshold t for the relevance score in the semantic network. Only these attacks, which are relevant with a relevance score above t, are included in the semantic network recommendation results. We did experiments by varying threshold t in the range from 0 to 1; the observed values of Precision, Recall, and F-measure are presented in Figures 27.4, 27.5 and 27.6 as follows:

The evaluation results of average precisions for four different semantic networks based on four various similarity measures are shown in Figure 27.4. Among these, an Anderberg-based semantic network performs best in terms of precision when we vary the threshold t determined by the relevance score. The average precision for a Jaccard-based semantic network is in the second place, while the results of other two, Simple Matching and Correlation based semantic networks, are close, but they are lower than the Anderberg and Jaccard results.

At the same time, we drew average recall graphs for these four different semantic networks. We found that their average recall results perform similarly, and they are all in the range of 60 percent to 100 percent when we vary the threshold t.

We also discovered that 0.8 is the optimal threshold value as a relevance score for the best performance of all the semantic networks. We used the F-measure, which is a metric combining precision and recall results, shown in Figure 27.6. Our experiment results shown in the graphs also clearly indicate that the performance of Anderberg is superior to other similarity measures, including the traditional correlation coefficient in the cyber-security domain.