Abstract
Intrusion Detection Systems (IDS) are widely deployed in computer networks. As modern attacks are getting more sophisticated and the number of sensors and network nodes grows, the problem of false positives and alert analysis becomes more difficult to solve. Alert correlation was proposed to analyze alerts and to decrease false positives. Knowledge about the target system or environment is usually necessary for efficient alert correlation. For representing the environment information as well as potential exploits, the existing vulnerabilities and their Attack Graph (AG) is used. It is useful for networks to generate an AG and to organize certain vulnerabilities in a reasonable way. In this paper, we design a correlation algorithm based on AGs that is capable of detecting multiple attack scenarios for forensic analysis. It can be parameterized to adjust the robustness and accuracy. A formal model of the algorithm is presented and an implementation is tested to analyze the different parameters on a real set of alerts from a local network.
Keywords: Correlation, Attack Graph, IDS.
Introduction
Intrusion Detection Systems (IDS) have been proposed for years as an efficient security measure and is nowadays widely deployed for securing critical IT-Infrastructures. The problem of false positive alerts is a well known problem for many IDS implementations [1]. Suboptimal patterns or insufficient thresholds for pattern-based and anomaly-based IDS approaches are the main reasons for a huge number of false-positive alerts. By deploying the IDS sensors in a distributed environment, the number of false positive alerts increases as a single event may be detected and reported multiple times by different involved sensors. The popular solution to address this problem is correlation and clustering of relative or similar alerts[2]. Modern algorithms for alert correlation are using environment information, e.g., attack graphs (AG) [3,4], to improve their performance. The approach proposed in [5] correlates IDS alerts in a memory-efficient way by using an AG and a matching function. The algorithm works with implicit alert correlations, considering only the last alert of a certain type per node in the attack graph. While it is memory-efficient, the approach can not easily be used for forensic analysis. It takes many additional efforts to identify similar attack scenarios having the same anatomy, i.e., using the same exploits on the same hosts at different times. Furthermore, the approach does not consider different mapping functions and aggregation of alerts in detail.
In this paper, we design an AG based correlation algorithm to overcome the above mentioned drawbacks of the algorithm proposed in [5]. By running the algorithm on hardware[6] with 2 TB of main memory on a single machine, we can make all the correlations between alerts explicit. Therefore, the algorithm is capable of identifying multiple attack scenarios of the same anatomy using an attack graph. The algorithm consists of a mapping of alerts to nodes in the attack graph, an alert aggregation, a building of an alert dependency graph, and a function for finding suspicious alert subsets. Apart from the formal model of the correlation algorithm, we analyze multiple possibilities for AG node matching and aggregation by parameterizing the algorithm. A proof-of-concept implementation is tested using a real data set with alerts from our university network.
The rest of the paper is organized as follows. Section 2 provides an overview on different approaches of alert correlation. In Section 3, the proposed correlation algorithm is described by a formal model. Its capabilities for detecting multiple attack scenarios is discussed. Section 4 presents some experiments and discusses the influence of selected parameters for the algorithm. Section 5 provides a short summary of the contributions and future works.
Alert Correlation
The alerts created by the distributed sensors are usually gathered by a central management system and processed by correlation algorithms. The quality of a correlation depends on accuracy and speed. The speed depicts how many correlations can be found in a certain amount of time. The accuracy depicts how many of the identified correlations represent real existing relations between these alerts. Due to more complex attacks and large scale networks, the amount of alerts increases significantly which yields the requirement for improved quality of the correlation. The correlation accuracy depends on the used correlation algorithm. It is obvious that using environmental information can help to improve the quality of alert correlation. Environmental information can be host addresses, running services, active users, network configurations, existing policies, known vulnerabilities in general, and existing vulnerabilities on hosts. To represent the listed information, AG are usually constructed for further processing and analysis. Attack Graphs have been proposed as a formal way to simplify the modeling of complex attacking scenarios. Based on the interconnection of single attack steps, they describe multi-step attacks. Attack Graphs not only describe one possible attack, but many potential ways for an attacker to reach a goal. In an attack graph, each node represents a single attack step in a sequence of steps. Each step may require a number of previous attack steps before it can be executed, denoted by incoming edges, and on the other hand may lead to several possible next steps, denoted by outgoing edges. With the help of attack graphs most of possible ways for an attacker to reach a goal can be computed. This takes the burden from security experts to evaluate hundreds and thousands of possible options. At the same time, representing attack graphs visually allows security personal a faster understanding of the problematic pieces of a network [7,4].
The alert correlation framework usually consists of several components [8]: Normalization, Aggregation (Clustering), Correlation, False Alert Reduction, Attack Strategy Analysis, and Prioritization. Over the last years, alert correlation research focused on new methods and technologies of these components. IDMEF [9] and CVE [10] are important efforts in the field of Normalization. Approaches of aggregation are mostly based on similarity of alerts [11] or generalization hierarchies [12]. The correlation algorithms [8] can be classified as: Scenario-based correlation [13,14], Rule-based correlation [15], Statistical correlation [16], and Temporal correlation [17,18]. The proposed approach can be classified as Scenario-based correlation: attack scenarios are specified by a formal language and alerts are correlated, if they can be combined to one of the known scenarios, i.e., alerts are matched in a specific path of the graph which can be considered as attack scenario (e.g., [5]). False alert reduction can be done by using such techniques as data mining [19] or fuzzy techniques [20]. Attack strategy analysis often depends on reasoning and prediction of attacks missed by the IDS [21]. In terms of Prioritization, the alerts are categorized based on their severity, e.g., using attack ranks [22]. To solve problems of alert correlation, a variety of disciplines are used, e.g., machine learning, data mining [19], or fuzzy techniques [20].
An Attack graph based correlation has been introduced in [5]. This approach maps alerts into the AG for correlation, and provides possibilities for hypothesizing and prediction of alerts. It uses a matching function which maps the alerts by comparing the alert type, the source, and the target address of each alert. Furthermore, this approach distinguishes between implicit and explicit correlation. It significantly reduces the number of explicit correlations by considering only the last alert in a set of similar alerts, i.e., the alert type, the source, as well as the target are identical. The explicitly correlated alerts are stored in a data structure called Queue Graph (QG) which tries to reduce the memory consumption.
Towards High-Quality Attack-Graph-Based Correlation
In this paper, a modified AG based correlation algorithm is proposed which only creates explicit correlations. Implicit correlations as described in [5] make it difficult to use the correlated alerts in the graph for forensic analysis of similar attack scenarios. Furthermore, the hardware environment used for the In-Memory databases provides machines with huge amounts of main memory which downgrades the priority of memory efficiency for this work. The algorithms consists of five steps, while each step can be parameterized to fine tune the results: 1) preparation, 2) alert mapping, 3) aggregation of alerts, 4) building of an alert dependency graph, and 5) searching for alert subsets that are related. In the preparation phase, all necessary information is loaded, i.e., the system and network information is gathered, the database with alert classifications is imported, and the AG for the network is loaded. We use the MulVAL [3] tool to generate an AG which describes the corresponding system and network information for the target network. The algorithm is based on a set of basic definitions.
Definitions
Let T be the set of all timestamps, H be the set of possible hosts, and C be the set of classifications. A can be defined as:
Let a single alert
be a tuple a = (t, s, d, c) while the following functions are defined:
- ts(a) = t – returns
the timestamp of the alert
- src(a) = s – returns
the source host of the alerts
- dst(a) = d – returns
the destination host of the alert
- class(a) = c – returns
the classification of the alert
Let I be the set of impacts described by MulVAL [3] and VR be the set of known vulnerabilities. Let V be a set of vertices defined as:
the following functions are defined:
For each triple
the following functions are defined:
- imp(v) = im – returns
the impact of the vertex
- host(v) = h – returns
the host if the vertex
- ref (v) = r – returns
, the vulnerability reference of the vertex
Let AG = (V, E) be an AG with vertices V and edges E. An edge
is an ordered tuple of vertices (v, v’) with
. PAG defines all the paths in the AG. The path
is defined as a set of edges.
defines the number of edges in the path P. in(v, P) depicts whether a vertex lies in the path: 
Mapping
The mapping function mapi maps matching alerts to specific nodes in the AG and is defined as:
There are different kinds of
defined in (5), (6), (7), (8), and (9) to parameterize the mapping function.
We will refer to match modes when using a specific
The match modes are named as follows:
Aggregation
Let
be the set of alert that is supposed to be aggregated. Let th be a threshold and
two alerts, then the relation RA is defined as: 
R*a defines an equivalence relation on the transitive closure of RA. The alert aggregation combines alerts that are similar but where created together in a short time, i.e., the difference of the timestamps is below a certain threshold th. It defines a set of equivalence classes A/r*a over the equivalence relation R*A.
Alert Dependencies
Let
be the set of alerts that have been matched to a node in an AG:
The alert dependencies are represented by a graph
as defined in (12).
The set
can be parameterized by the functions
as shown in (13), (14), and (15).
The dependency graph DG is defined by the matched and aggregated alerts Am as vertices and the relations between these alerts as edges Em,k. There are three possible ways to define these relations using Psik. Psi1 defines two alerts as related, if they are mapped to neighboring vertices in AG. Psi2 defines two alerts as related, if they are mapped to two vertices in AG that are connected by the path P with the length of n. Psi3 defines two alerts as related, if they are mapped to two vertices in AG that are part of the same path P.
Searching
Each path in the alert dependency graph DG identifies a subset of alerts that might be part of an attack scenario. DG is used in the last step to determine the most interesting subsets of alerts, respectively the most interesting path in the alert dependency graph. The last step of searching alert subsets is done by performing a Floyd Warshall algorithm [24,25] to find all the shortest paths. Furthermore, the diameter dia (i.e. the value of the longest instance of the shortest paths) is determined and each path DPi that has the length ord(DP) = dia is converted in subsets of alerts. All the subsets Sx are defined as:
With a simple optimization, the algorithm allows to identify multiple different attack scenarios of the same anatomy. By sorting the suspicious alert subsets according to the smallest difference between alert ai and an, the algorithm will identify the alerts that are near each other on the time-line as related to one attack scenario. Let as1 = {a1,.., an} and as2 = {b1, …,bn} be two alert sets where the only difference between ai and bi is the times-tamp
. There are three different combinations how these alerts
can be located on a time-line:
The modified algorithm can identify both suspicious alert sets in case 1, which is impossible for the algorithm in [5]. Due to the memory limitation, this algorithm only considers the last matching alert for each node in the AG.
Experiment and Discussion
The algorithm is implemented on a modularized correlation platform which is designed based on in-memory techniques and a multi-core hardware [6]. For testing the correlation algorithm, we created a data set of IDMEF alerts by running a Snort[23] sensor in our university network. The sensor gathered 43485 alerts in 6 days of runtime. Meanwhile, we had a Snort sensor running in several vulnerable subnets of our university network which include several vulnerable hosts. The AG for this subnet is constructed accordingly. We performed a multi-step attack covering multiple hosts in the existing subnets. This provides us with a set of alerts we consider as attack trace in the following work. By injecting this attack trace into the clean data set of the whole university network, we can simulate alert sets without running the real attacks over the production network of our university. The attack is done by compromising 5 hosts in the vulnerable network spread over 4 subnets. We conducted multiple experiments using the data set and the attack trace.
For this set of experiments, we injected one attack trace into the clean data set to test if it can be found in a real set of alerts. Furthermore, we analyzed selected parameters of the algorithm and their influence on the actual result, such as the match mode, the aggregation threshold, the dependency build mode, and the searching algorithm for alert subsets. We fixed the parameters for defining dependencies between alerts and searching for suspicious subsets of alerts. A dependency between two alerts is defined by Ea,\ using i.e., alerts that are mapped to adjacent nodes fulfilling the timing constraint are dependent. The dependency graph DG = (Da, Ea^) is used to find all the shortest paths by performing a Floyd-Warshall algorithm and defining the diameter. As shown in Table 1, the match modes using the CVE[10] as criteria work precisely and can identify attacks that follow the AG.
With the alert set from our experiment, this match mode filters about 99.98% of the alerts. The match modes that ignore CVE and are based on the source and destination address are less accurate in terms of the vulnerability used. In our experiments it still showed a filtering rate of 95.58%. The advantage of this match mode is that an attacker can use different vulnerabilities to compromise a host covered in the AG and can still be recognized by the correlation. In the CVE based matching, there is only one suspicious alert set found, basically the one which is supposed to be found. The matching without CVE identifies much more suspicious alert sets. By looking at these alert sets, we recognized that most of the alert sets are using similar alerts and that the high number of the alert sets is due to the fact that there are two hosts which seem to be frequently used and that the Snort sensor produces more false positives for them. To improve it, we can try to filter more alerts in the matching by using a matching mode that is based on alert categories, e.g., we do not need to match alerts that are related to an attacks categorized as Denial-of-Service (DoS).
Table 1. Experiment results – match modes with fixed aggregation threshold of 2s
|
Matched alerts |
% filtered |
Suspicious alert sets |
|
|
cvesrcdst |
5 |
99.99 |
1 |
|
cvedst |
5 |
99.99 |
1 |
|
eve |
8 |
99.98 |
1 |
|
sredst |
1836 |
95.78 |
1010 |
|
dst |
1923 |
95.58 |
1010 |
Fig. 1. Experiment results – aggregated alerts and suspicious alert sets for different aggregation thresholds with match mode srcdst
As shown in Figure 1, the aggregation threshold influences the number of suspicious subsets, as a lot of matched alerts can be filtered. The diagram shows the amount of aggregated/filtered alerts as blocks and the amount of identified suspicious alert subsets as line. The overall positive effect of aggregation seen in the diagram is due to the high similarity of consecutive alerts in our data set. We realized multiple alerts in a row that are pretty similar and most likely belong to the same communication. These alert clusters can be aggregated without loosing accuracy of correlation result. An aggregation threshold of 60s or larger filters 1246 out of 1836 alerts, i.e., 67.86% of the matched alerts can be filtered in the best case. The algorithm determined 398 suspicious alert sets for this case, which is a significant improvement over the 1010 suspicious alert sets for the threshold of 2 seconds. Thresholds smaller than 2 seconds do not show reasonable effect.
Conclusion
In this paper, an AG based correlation algorithm is proposed that overcomes the drawbacks of the algorithm described in [5]. It creates only explicit correlations and enables the identification of multiple attack scenarios of the same anatomy. The algorithm consists of a mapping of alerts to AG nodes, the alert aggregation function, a function for building an alert dependency graph, and a function for finding suspicious subsets using the Floyd-Warshall algorithm and the diameter value. In addition to the formal model of the correlation algorithm, we analyzed multiple possibilities for the node matching and aggregation function in detail to parameterize the algorithm. Finally, we tested the capabilities and analyzed the influence of the parameters by using a real data set of alerts generated from our university network.
The algorithm is implemented and tested based on real data. As this data set is still small, we want to conduct more experiments using larger data sets. Running multiple attacks against the secured network that (partially) cover the AG is also useful to analyze the efficiency and performance of the algorithm. Although the srcdst based matching filters about 95% of the alerts, it might still be possible to improve this matching by using attack categories or ontologies. This can improve the filtering without getting inaccurate in the results. Furthermore, the algorithm needs some computing power to consume, especially the Floyd-Warschall algorithm. This can be improved by providing a multi-core-compliant version of the algorithm. Apart from IDMEF alerts, there are additional data sources (e.g., log files) that can be used for AG-based correlation. It should be supported by a more flexible mapping function.
