Prioritizing Intrusion Analysis Using Dempster-Shafer Theory

Abstract--Intrusion analysis, i.e. the process of combing through IDS alerts and audit logs to identify true successful and attempted attacks, remains a difficult problem in practical network security defense. The major root cause of this problem is the large rate of false positives in the sensors used by IDS systems to detect malicious activities. This work presents an approach to handling such uncertainty through the Dempster- Shafer (DS) theory that uses a generalization of probabilities called beliefs to characterize confidence in evidence in support of a given hypothesis. We address a number of practical but fundamental issues in applying DS to intrusion analysis, including how to model sensors' trustworthiness, where to obtain such parameters, and how to address the lack of independence among alerts. We present an efficient algorithm for computing a belief score for a given hypothesis, e.g. a specific machine is compromised. The belief strength can be used to prioritize further analysis by a human analyst of the hypotheses and the associated evidence. We have implemented our method on top of SnIPS (open source intrusion analysis framework) and evaluated its effectiveness on a number of data sets as well as a production network. The verification of belief scores showed that it can be effective in taming the high false positive rate problem in intrusion analysis.

I. INTRODUCTION
Intrusion analysis is the process of examining real-time events such

as IDS alerts and audit logs to identify and confirm successful attacks and attack attempts into computer systems. The IDS sensors that we have to rely on for this purpose often suffer from a large false positive rate. It then becomes the responsibility of a human monitoring the IDS system to distinguish the true alarms from the enormous number of false ones. How to deal with the prevalence of false positives is the primary challenge in making IDS sensors useful, as pointed out by Axelsson [1] more than 10 years ago. Due to the lack of effective techniques to handle the false-positive problem, it has become a common practice to altogether disable IDS signatures that tend to trigger large amount of false positive. Turning off IDS signatures is like turning a blind eye to attack possibilities, which we believe is a dilemma due to the lack of effective techniques to prioritize investigating intrusions from the large amount of IDS alerts and audit logs.

There have been past attempts [7, 8] at prioritizing IDS alerts based on their trustworthiness - Bayesian analysis [2] has been the standard and there have been some approaches using alternative theories such as Dempster-Shafer theory [4, 5]. However, a number of fundamental issues in applying these mathematical theories to intrusion analysis remain to be addressed. For Bayesian analysis, it seems difficult to establish adequate priors or determine the probability parameters in a robust manner. For Dempster-Shafer theory, it is not clear how to model sensor quality, where to obtain such parameters, and how to handle non-independent sources of evidence.

Our investigation reveals that Dempster-Shafer theory has its unique advantages in handling uncertainty in intrusion analysis, namely, the lack of need for specifying prior probabilities of all events and the ability to combine beliefs from multiple sources of evidence. In this work [9], we present an extended Dempster-Shafer model that addresses the fundamental issues in applying DS in intrusion analysis. We have implemented our method on top of SnIPS (open source intrusion analysis framework) [3, 6], so that one can calculate a numeric confidence score for each derived hypothesis and prioritize the results based on the scores.

II. BACKGROUND ON DEMPSTER-SHAFER THEORY
A common example to illustrate the difference between probability theory and Dempster-Shafer theory is that if we toss a coin with an unknown bias, probability will still assign 50% for Head and 50% for Tail by the principle of indifference. Dempster-Shafer theory, on the other hand, handles this by assigning 0% belief to {Head} and {Tail} and assigning 100% belief to the set {Head, Tail}, meaning "either Head or Tail". More generally, the DS approach allows for three kinds of answers: Yes, No, or Don't know, the last option of allowing ignorance makes a big difference in evidential reasoning. In DS theory, a set of disjoint hypotheses of interest, e.g., {attack, no-attack}, is called a frame of discernment. The basic probability assignment (bpa function), distributes the belief over the power set of the frame of discernment and is defined as:

practice. This is especially a problem in IDS alerts since many alerts are triggered by the same or similar signatures. In combining these alerts to derive the overall belief on the attack status, it is important that such non-independence be appropriately accounted for so that the result is not skewed by over-counting. To the best of our knowledge, our method is the first in applying sound non-independent DS belief combination in IDS alerts.

We adopt an idea proposed by Shafer which interprets combined bpa's as joint probabilities. Based on this, we develop a set of cus- tomized combination formulas to correctly account for the dependence in evidence when combining beliefs in the alert correlation graph. For non-independent evidence, multiplication of bpa's from two sources is no longer valid. Instead of m1(h1) * m2(h2), we use ps[h1, h2] to denote the joint bpa of the two sources. We obtain the following new formula for combining possibly non-independent evidence.

C. Efficient calculation

A direct application of DS formulas can result in exponential (in the number of hypotheses - in our case, IP addresses) blow-up of belief combinations. We adopt a "translate-then-combine" approach so that beliefs are propagated in a correlation graph and only combined at join points in the graph. This produces an efficient algorithm with worst- case running time quadratic in the number of IP addresses in the input alerts.

D. Linking to practical IDS tools