The Base-Rate Fallacy and the Difficulty of Intrusion Detection

The Base-Rate Fallacy and the Difficulty of Intrusion Detection

STEFAN AXELSSON Ericsson Mobile Data Design AB

Many different demands can be made of intrusion detection systems. An important requirement is that an intrusion detection system be effective; that is, it should detect a substantial percentage of intrusions into the supervised system, while still keeping the false alarm rate at an acceptable level. This article demonstrates that, for a reasonable set of assumptions, the false alarm rate is the limiting factor for the performance of an intrusion detection system. This is due to the base-rate fallacy phenomenon, that in order to achieve substantial values of the Bayesian detection rate PIntrusionAlarm, we have to achieve a (perhaps in some cases unattainably) low false alarm rate. A selection of reports of intrusion detection performance are reviewed, and the conclusion is reached that there are indications that at least some types of intrusion detection have far to go before they can attain such low false alarm rates. Categories and Subject Descriptors: D.4.6 [Operating Systems]: Security and Protection General Terms: Performance, Security, Theory Additional Key Words and Phrases: Base-rate fallacy, detection rate, false alarm rate, intrusion detection

1. INTRODUCTION Many demands can be made of an intrusion detection system (IDS for short) such as effectiveness, efficiency, ease of use, security, interoperability,

This work was funded in part by the Swedish National Board for Industrial and Technical Development (NUTEK) under project P10435. An earlier version of this article appeared as "The base-rate fallacy and its implications for the difficulty of intrusion detection" in the Proceedings of the Sixth ACM Conference on Computer and Communications Security (Nov. 1?9). ACM Press, New York, 1999, pp. 1?7. Most of this work was done while the author was at the Department of Computer Engineering at Chalmers University of Technology. He is presently at Ericsson Mobile Data Design AB. The author's homepage (and all self-referenced papers) can be found at . Author's address: Ericsson Mobile Data Design AB, S:t Sigfridsgatan 89, SE-412 66, G?teborg, Sweden; email: Stefan.Axelsson@erv.ericsson.se. Permission to make digital / hard copy of part or all of this work for personal or classroom use is granted without fee provided that the copies are not made or distributed for profit or commercial advantage, the copyright notice, the title of the publication, and its date appear, and notice is given that copying is by permission of the ACM, Inc. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and / or a fee. ? 2000 ACM 1094-9224/00/0800 ?0186 $5.00

ACM Transactions on Information and System Security, Vol. 3, No. 3, August 2000, Pages 186 ?205.

Base-Rate Fallacy

? 187

transparency, and so on. Although much research has been done in the field in the past 10 years, the theoretical limits of many of these parameters have not been studied to any significant degree. This article discusses one serious problem with regard to the effectiveness parameter, especially how the base-rate fallacy may affect the operational effectiveness of an intrusion detection system.

2. INTRUSION DETECTION

The field of automated computer intrusion detection (intrusion detection for short) is currently about 20 years old [Anderson 1980], with interest gathering pace during the past 10 years.

Intrusion detection systems are intended to help detect a number of important types of computer security violations, such as:

--attackers using prepacked "exploit scripts"; primarily outsiders;

--attackers operating under the identity of a legitimate user, for example, by having stolen that user's authentication information (password); outsiders and insiders;

--insiders abusing legitimate privileges, and so on.

Early work (see Anderson [1980], Denning and Neumann [1985], Denning [1987], and Sebring et al. [1988]) identified two major types of intrusion detection strategies.

Anomaly Detection. The strategy of declaring everything that is unusual for the subject (computer, user, etc.) suspect, and worthy of further investigation. The early anomaly detection systems were all self-learning, that is, they automatically formed an opinion of what the subject's normal behavior was. Anomaly detection promises to detect abuses of legitimate privileges that cannot easily be codified into security policy, and to detect attacks that are "novel" to the intrusion detection system. Problems include a tendency to take up data processing resources, and the possibility of an attacker teaching the system that his illegitimate activities are nothing out of the ordinary.

Signature detection The detection strategy of deciding in advance what type of behavior is undesirable, and through the use of predetermined signatures of such behavior, detecting intrusions. Signature-based detection systems promise to detect known attacks and violations easily codified into security policies in a timely and efficient manner. Problems include a difficulty in detecting previously unknown intrusions. If a database containing intrusion signatures is employed, it must be updated frequently.

Early in the research it was suggested in Halme and Kahn [1988] and Lunt [1988] that the two main methods ought to be combined to provide a

ACM Transactions on Information and System Security, Vol. 3, No. 3, August 2000.

188 ? S. Axelsson

complete intrusion detection system capable of detecting a wide array of different computer security violations, including the ones listed above.

For a more in-depth review of these and other intrusion detection concepts, the interested reader is referred to a survey of intrusion detection systems [Axelsson 1998] and a taxonomy of intrusion detection systems and principles [Axelsson 2000a], previously written by us.

We wish to at least make the above division between the different principles of detection, since it is easy to conjecture that these fundamentally different modes of detection will exhibit different characteristics with regard to detection and false alarm rates. They probably also show different performance in other characteristics as well, such as run-time efficiency, but a discussion of these parameters falls outside the scope of this article.

3. PROBLEMS IN INTRUSION DETECTION

At present, many fundamental questions regarding intrusion detection remain unanswered. They include, but are by no means limited to, the following:

Effectiveness. How effective is the intrusion detection? To what degree does it detect intrusions into the target system, and how good is it at rejecting false positives, so-called false alarms?

Efficiency. What is the run-time efficiency of the intrusion detection system, how many computing resources and how much storage does it consume, can it make its detections in real-time, and so on?

Ease of use. How easy is it to field and operate for a user who is not a security expert, and can such a user add new intrusion scenarios to the system? An important issue in ease of use is the question of what demands can be made of the person responding to the intrusion alarm. How high a false alarm rate can he/she realistically be expected to cope with, and under what circumstances is he/she likely to ignore an alarm? (It has long been known in security circles that, if you are an attacker, you should attempt to circumvent an ordinary electronic alarm system during normal operation of the facility, since if you happened to trigger the alarm, the supervisory staff would more likely be lax because they would be more accustomed to false alarms [Pierce 1948].)

Security. Whenever more intrusion detection systems are fielded, one would expect ever more attacks directed at the intrusion detection system itself, to circumvent it or otherwise render the detection ineffective. What is the nature of these attacks, and how resilient is the intrusion detection system to them?

Interoperability. As the number of different intrusion detection systems increase, to what degree can they interoperate and how do we ensure this?

ACM Transactions on Information and System Security, Vol. 3, No. 3, August 2000.

Base-Rate Fallacy

? 189

Transparency. How intrusive is the fielding of the intrusion detection system to the organization employing it? How many resources will it consume in terms of manpower, and the like?

Collaboration. The best effect is often achieved when several security measures are brought to bear together. How should intrusion detection collaborate with other security mechanisms to achieve this synergy effect? How do we ensure that the combination of security measures provides at least the same level of security as each applied singly would provide, or that the combination does not in fact lower the overall security of the protected system?

Although interest is being shown in some of these issues, with a few notable exceptions (mainly Helman and Liepins [1993]), they remain largely unaddressed by the research community. This is perhaps not surprising, since many of these questions are difficult to formulate and answer.

This article is concerned with one aspect of one of the questions above, that of effectiveness. More specifically, it addresses the way in which the base-rate fallacy affects the required performance of the intrusion detection system with regard to false alarm rejection.

In what follows, Section 4 gives a description of the base-rate fallacy. Section 5 then continues with an application of the base-rate fallacy to the intrusion detection problem, given a set of reasonable assumptions. Section 6 describes the impact the results presented in the previous section would have on intrusion detection systems. Section 7 considers future work, with Section 8 concluding the article. Appendix A reproduces a base-rate fallacy example in diagram form.

4. THE BASE-RATE FALLACY

The base-rate fallacy1 is one of the cornerstones of Bayesian statistics, stemming as it does directly from Bayes' famous theorem that states the relationship between a conditional probability and its opposite, that is, with the condition transposed:

PA PBA

PAB

.

(1)

PB

Expanding the probability PB for the set of all n possible, mutually exclusive outcomes A, we arrive at Eq. (2),

n

PB PAi PBAi.

(2)

i1

1The idea behind this approach stems from Matthews [1996; 1997]. ACM Transactions on Information and System Security, Vol. 3, No. 3, August 2000.

190 ? S. Axelsson

Combining Eqs. (1) and (2), we arrive at a generally more useful statement of Bayes' theorem:

PA PBA

PAB in1PAi PBAi

(3)

The base-rate fallacy is best described through example.2 Suppose that your doctor performs a test that is 99% accurate; that is, when the test was administered to a test population all of whom had the disease, 99% of the tests indicated disease, and likewise, when the test population was known to be 100% free of the disease, 99% of the test results were negative. Upon visiting your doctor to learn the results, he tells you he has good news and bad news. The bad news is that indeed you tested positive for the disease. The good news however, is that, out of the entire population, the rate of

incidence is only 1 10000; that is, only 1 in 10000 people have this

ailment. What, given this information, is the probability of your having the disease? The reader is encouraged to make a quick "guesstimate" of the answer at this point.

Let us start by naming the different outcomes. Let S denote sick, and

?S, that is, not S, denote healthy. Likewise, let R denote a positive test result and ?R denote a negative test result. Restating the information

above: given: PRS 0.99, P?R?S 0.99, and PS 1 10000,

what is the probability PSR? A direct application of Eq. (3) gives:

PS PRS

PSR

.

(4)

PS PRS P?S PR ?S

The only probability above that we do not immediately know is

PR?S. This is easily found though, since it is merely 1 P?R?S 1% (likewise, P?S 1 PS). Substituting the stated values for the different quantities in Eq. (4) gives:

1/10000 0.99

PSR

0.00980. . . 1%. (5)

1/10000 0.99 1 1/10000 0.01

That is, even though the test is 99% certain, your chance of actually

having the disease is only 1 100, because the population of healthy people

is much larger than the population with the disease. (For a graphical representation, in the form of a Venn diagram, depicting the different outcomes, see the Appendix). This result often surprises people, ourselves included, and it is this phenomenon--that humans in general do not take the basic rate of incidence, the base-rate, into account when intuitively

2This example is hinted at in Russel and Norvig [1995]. ACM Transactions on Information and System Security, Vol. 3, No. 3, August 2000.

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download