- P H R A C K M A G A Z I N E - Volume 0xa Issue 0x38 05.01.2000 0x0b[0x10] |----------------- A STRICT ANOMOLY DETECTION MODEL FOR IDS ------------------| |-----------------------------------------------------------------------------| |------------------------------ sasha / beetle -------------------------------| "The three main problems we try to solve to achieve security are: hiding data, ensuring that systems run effectively, and keeping data from being modified or destroyed. In fact you could argue that most of computer security - more so than any other field in computer science - is simply the analysis of imperfection in these areas. Imperfection rather than perfection, because people seem to have a tendency to find what they seek; and (for the secular) finding insecurity (e.g. imperfections), alas, is nearly always more correct than stumbling upon security (e.g. perfection). Obviously computers are indefatigable, not invulnerable." - Dan Farmer "Central to this type of thinking is the underlying notion of 'truth'. By means of argument which maneuvers matter into a contradictory position, something can be shown to be false. Even if something is not completely false, the garbage has to be chipped away by the skilled exercise of critical thinking in order to lay bare the contained truth." - Edward De Bono ----| 1. Introduction IDS (Intrusion Detection Systems) seem to currently be one of the most fashionable computer security technologies. The goal of IDS technology - to detect misuse, must be considered a genuinely 'hard problem', and indeed there exists several areas of difficulty associated with implementing an NIDS (network-based IDS) such that the results it generates are genuinely useful, and can also be trusted. This article focuses predominantly on issues associated with NIDS although many of the issues are equally applicable to host-based and application-based IDS also. This article is split into two; firstly, issues of concern regarding NIDS are discussed - generally one or more research papers are referenced and then the implication for the validity of current NIDS implementation models is presented; secondly, a proposal for a new implementation model for NIDS is described which attempts to mitigate some of the identified problems. ----| 2. Issues of Concern for NIDS 2.1 False Alarm Rate "If you call everything with a large red nose a clown, you'll spot all the clowns, but also Santa's reindeer, Rudolph, and vice versa." - Stefan Axelsson At the RAID 99 Conference (Recent Advances in Intrusion Detection) [1], Stefan Axelsson presented his white paper: 'The Base-Rate Fallacy and its Implications for the Difficulty of Intrusion Detection' [2]. The base-rate fallacy is one of the cornerstones of Bayesian statistics, stemming from Bayes theorem that describes the relationship between a conditional probability and its opposite, i.e. with the condition transposed. The base-rate fallacy is best described through example. Suppose that your doctor performs a test on you that is 99% accurate, i.e. 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 that you have tested positive for the disease; the good news however, is that out of the entire population the rate of incidence is only 1/10,000, i.e. only one in 10,000 people have the disease. What, given this information, is the probability of you having the disease? 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. This result often surprise a lot of people, and it is this phenomenon - that humans in general do not take the basic rate of incidence (the base-rate) into account when intuitively solving such problems of probability, that is aptly named "the base rate fallacy". The implication, is that intrusion detection in a realistic setting is therefore harder than previously thought. This is due to the base-rate fallacy problem, because of which the factor limiting the performance of an intrusion detection system is not the ability to correctly identify intrusions, but rather its ability to suppress false alarms. 2.2 Anomalous Network Behavior In 1993, Steven Bellovin published the classic white paper 'Packets Found on an Internet' [3], in which he describes anomalous network traffic detected at the AT&T firewall. He identifies anomalous broadcast traffic, requests to connect to "inexplicable" ports, and packets addresses to random, non-existent machines. Bellovin concludes: "To some, our observations can be summarized succinctly as 'bugs happen'. But dismissing our results so cavalierly misses the point. Yes, bugs happen but the very success of the Internet makes some bugs invisible; the underlying problems they are symptomatic of have not gone away." As the techniques for network information gathering (host, service, and network topology detection - see [4]) become more esoteric, they stray increasingly into the 'gray areas', the ambiguities, of the TCP/IP network protocol definitions (consequently, the results of such techniques may be more stealthy, but they are often also less dependable). These same ambiguities in the definition of the protocols result in TCP/IP stack implementations that behave differently per OS type, or even per OS release (in fact, this enables TCP/IP stack fingerprinting [5]). The implication, is that the detection of anomalous behavior which may have a security implication, is made considerably more complex since anomalous behavior exists in the network environment by default. 2.3 Complexity "Thinking in terms of 'typical' is a lethal pitfall. But how else do we develop intuition and understanding?" - Vern Paxson In 1999, Vern Paxson (author of the 'Bro' NIDS [6]), published a presentation titled 'Why Understanding Anything About The Internet Is Painfully Hard' [7]. In his presentation, he concludes that to even begin to enable network traffic modeling, invariants are required: properties of the network which do not change; but, the Internet is by it's very nature a sea of change - a moving target. The majority of NIDS utilize a 'misuse-detection' model - traditionally implemented by comparing live network traffic to a database of signatures which represent known attacks. A second NIDS model also exists: 'anomaly-detection' - in which an IDS attempts to 'learn' to differentiate between legal and illegal behavior; anomaly-detection NIDS have not yet been proven, and exist at present largely only in the academic research domain. Vern Paxson describes the Internet as: "ubiquitous diversity and change: over time, across sites, how the network is used, and by whom", and this implies that much work is yet to be done before NIDS which attempt to utilize a traditional anomaly-detection model can add significant value in a complex, real-world, enterprise environment. 2.4 Susceptibility to Attack In 1998, Thomas Ptacek and Timothy Newsham published their seminal work on NIDS subversion - 'Insertion, Evasion, and Denial of Service: Eluding Network Intrusion Detection' [8]; an implementation followed in P54-10 [9], and the scripting language originally used by Ptacek and Newsham to perform their testing is also now available [10]. Since then, anti-IDS techniques have been built into network interrogation tools, such as whisker [11]. A presentation by Vern Paxson - 'Defending Against NIDS Evasion using Traffic Normalizers' [12] describes a 'bump in the wire' network traffic normalizer which defeats the majority of published NIDS subversion attacks. However, until Cisco implement this technology in IOS or Checkpoint do likewise with FW-1, etc., both unlikely prospects in the short to medium term, the implication is that this suite of NIDS subversion techniques will continue to call into question the reliability of NIDS. 2.5 The Evolving Network Infrastructure The physical network infrastructure is rapidly evolving; in the future - encryption, high wire speeds, and switched networks will practically kill those NIDS which utilize promiscuous-mode passive protocol analysis. When (...or if) the IP security protocol [13] becomes ubiquitous, NIDS will be unable to perform pattern-matching-style signature analysis against the data portion of network packets; those NIDS signatures which relate to IP, TCP, and other protocol headers will still be valid, but signatures for attacks against applications will become useless because the application data will be encrypted. Current NIDS based upon passive protocol analysis can barely monitor 100 Mb/s Ethernet, and it is somewhat doubtful that they will be able to monitor ATM, FDDI, etc. Lastly, the increasing use of switches in the modern network environment largely foils the monitoring of multiple hosts concurrently (such as with broadcast Ethernet). The use of a spanning/spy port to monitor multiple ports on a switch should be viewed as a short-term novelty at best. ----| 3. The Evolution of NIDS In an attempt to 'evolve around' the described issues, vendors of NIDS products are moving towards a model in which an NIDS agent is installed on each host - monitoring network traffic addressed to that host alone (i.e. non promiscuously); this would seem to be the most sensible way to perform NIDS monitoring in switched environments. Also, if a host-based NIDS agent can be 'built into' the hosts TCP/IP stack, it can perform security analysis both before data enters the stack (i.e. between the NIC and the stack), and before it enters an application (i.e. between the stack and the application), thereby hypothetically protecting both the OS stack and the application. In a multiple host-based model as described above, NIDS subterfuge attacks (section 2.4) are much less dangerous, since a host-based NIDS agent receives all the packets addressed to the host on which it is installed; issues associated with the ambiguity in interpreting network traffic, such as with forward or backwards fragmentation reassembly (and so on) are reduced - assuming of course that the NIDS agent has visibility into the operation of the host OS stack. A transition from network-based NIDS to host-based NIDS is a logical evolutionary step - it eases the problems with susceptibility to attack and the underlying evolving network infrastructure, but it is not, however, a panacea for the other issues identified. ----| 4. A Proposal: Strict Anomaly Detection We approached the task of inventing a new NIDS operational model with two axiomatic beliefs: Firstly, an IDS should not view the task of detecting misuse as a binary decision problem, i.e. "saw an attack" vs. "did not see an attack". It should be recognized that different forms of attack technique are not equally complex and consequently not equally complex to detect; succinctly, the intrusion detection problem is not a binary (discrete), but rather an n-valued (variable) problem. Secondly, NIDS can detect many simplistic attacks, but those same simplistic attacks can be made much harder to detect if the correct delivery mechanism and philosophy is employed. Many attack techniques are increasingly dependent on ambiguity, which forces an IDS to use much more simplistic logic if it is to perform correctly. By definition, NIDS which employ a misuse detection heuristic cannot detect new, novel attacks; more crucially, a small variation in the form/structure of an attack can often easily invalidate a NIDS signature. Our proposal, is that an IDS should not function by using definitions of misuse (signatures) to detect attacks, but instead by searching for deviation from a rigid definition of use. We call this model "not use" detection, or alternatively "strict anomaly detection". It is important to distinguish between misuse-detection and "not use" detection: traditional misuse detection involves defining a set of events (signatures) that represent attacks - "misuse", and attempting to detect that activity in the environment. Strict anomaly detection ("not use" detection) involves defining a set of permitted events - "use", and detecting activity which represents exceptions to those events, hence "not use". The key advantage in employing a strict anomaly detection model is that the number of attacks within the "misuse" set can never be greater than the number of attacks within the "not use" set; by definition, all current and future attacks reside in the "not use" set! Assuming a host-based model, the remaining current issues of concern with IDS identified in section 2, are: 4.1 False Alarm Rate An IDS which implements a strict anomaly detection model can never enter a false-positive state, i.e. can never generate a false alarm, because activity which occurs outside the definition of "use", by definition, has security relevance. 4.2 Anomalous Network Behaviour We must assume that anomalous behavior exists in the target environment by default; therefore, a mechanism must exist to create 'exceptions' to the rule set used to implement strict anomaly detection within an IDS, for example - to except (accept) the idiosyncratic behavior of a particular flavor of host TCP/IP stack. Such a system would be analogous in functionality to the ability to except certain instances of mis-configuration detected by host-based security state monitoring software. 4.3 Complexity The use of strict anomaly detection does not necessarily require a complete model of acceptable use to be constructed - a subset may be acceptable. For example, to detect novel network attacks that involve TCP connection establishment, the acceptable use model could initially simply comprise the three-way TCP connection handshake, plus termination conditions; it may not be necessary to construct an acceptable use model which comprises the entire TCP state transition diagram. How can strict anomaly detection be applied to the problem of detecting anomalous (i.e. security relevant) network traffic? We present two initial implementation ideas, below. Firstly, the TCP state-transition diagram could be modeled within an IDS as a set of rules; these rules represent the valid use of TCP as per the TCP specification. Exceptions (i.e. "not use") which occur would be alerted upon. Some analysis has already been done on exceptions which occur to the classical TCP state transition diagram, see [14]. Alternatively, an entirely stateless approach could be taken by defining the allowable variation in each field of the TCP header and in its construction/format; analysis could then be performed without reference to previous or future network traffic. Exceptions which occur would be flagged. A more broad example of strict anomaly detection is in the scenario in which a NIDS is deployed on the 'inside' of a firewall; the "not use" set can be constructed using the inverse of the firewall rule set. If the NIDS detects traffic which it knows the firewall should reject, an alert would be generated. ----| 5. Summary The difficulty in constructing an IDS which utilizes a strict anomaly detection model, is in being able to define allowable "use". It may be that strict anomaly detection is best employed in an environment in which "use" can be (or is already) well defined, such as in the firewall example above, or in a 'trusted system' - such as Trusted Solaris [15] for example. In this article we have introduced the concept of strict anomaly detection, a.k.a "not use" detection. Strict anomaly detection is an alternative to misuse-detection and anomaly-detection for the attack detection heuristic component of intrusion detection systems, which attempts to negate some of the critical issues of concern with the existing approaches to IDS. ----| 6. References [1] International Workshop on Recent Advances in Intrusion Detection http://www.zurich.ibm.com/pub/Other/RAID [2] The Base-Rate Fallacy and its Implications for the Difficulty of Intrusion Detection, Stefan Axelsson, Proceedings of the 6th ACM Conference on Computer and Communications Security, November 1-4, 1999 [3] Packets Found on an Internet, Steven M. Bellovin, August 23, 1993, Computer Communications Review, July 1993, Vol. 23, No. 3, pp. 26-31, http://www.research.att.com/~smb/papers/packets.ps [4] Distributed Metastasis: A Computer Network Penetration Methodology, Andrew J. Stewart, Phrack Magazine, Vol 9, Issue 55, File 16 of 19. 09.09.99, http://www.phrack.com/search.phtml?view&article=p55-16 [5] Remote OS detection via TCP/IP Stack Fingerprinting', Fyodor, Phrack Magazine, Volume 8, Issue 54, Article 09 of 12, Dec 25th, 1998, http://www.phrack.com/search.phtml?view&article=p54-9 [6] Bro: A System for Detecting Network Intruders in Real-Time, Vern Paxson, Network Research Group, Lawrence Berkeley National Laboratory, Berkley, CA, Revised January 14, 1998, Proceedings of the 7th USENIX Security Symposium, San Antonio, TX, January 1998, ftp://ftp.ee.lbnl.gov/papers/bro-usenix98-revised.ps.Z [7] Why Understanding Anything About The Internet Is Painfully Hard, Vern Paxson, AT&T Center for Internet Research at ICSI, International Computer Science Institute, Berkeley, CA, April 28, 1999, http://www.aciri.org/vern/talks/vp-painfully-hard.UCB-mig.99.ps.gz [8] Insertion, Evasion, and Denial of Service: Eluding Network Intrusion Detection, Thomas H. Ptacek & Timothy N. Newsham, Secure Networks, Inc, January, 1998, http://www.securityfocus.com/data/library/ids.pdf [9] Defeating Sniffers and Intrusion Detection Systems, horizon, Phrack Magazine, Volume 8, Issue 54, article 10 of 12, Dec 25th, 1998, http://www.phrack.com/search.phtml?view&article=p54-10 [10] CASL (Custom Audit Scripting Language) for Linux Red Hat 5.x, Programming Guide, Version 2.0, ftp://ftp.nai.com/pub/security/casl/casl20.tgz [11] A look at whisker's anti-IDS tactics, Rain Forest Puppy, http://www.wiretrip.net/rfp/pages/whitepapers/whiskerids.html [12] Defending Against NIDS Evasion using Traffic Normalizers, Vern Paxson, Mark Handley, ACIRI, RAID, Sept '99 [13] IP Security Protocol (ipsec), http://www.ietf.org/html.charters/ipsec-charter.html [14] Network Security Via Reverse Engineering of TCP Code: Vulnerability Analysis and Proposed Solutions, Biswaroop Gua, Biswanath Mukherjee, Biswanath Mukherjee, Department of Computer Science, University of California, Davis, CA 95616, U.S.A, November 7, 1995 [15] Trusted Solaris 7 http://www.sun.com/software/solaris/trustedsolaris/ [16] I Am Right - You Are Wrong, Edward De Bono, Penguin, 1992 edition, ISBN 0140126783 |EOF|-------------------------------------------------------------------------|