- 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|-------------------------------------------------------------------------|