RE: Comparing the performance of two IDS products with different architectures

From: robert_david_graham (robert_david_graham@yahoo.com)
Date: 10/23/01 

From: "robert_david_graham" <robert_david_graham@yahoo.com>
To: <iheagwarac@aol.com>, <focus-ids@securityfocus.com>
Subject: RE: Comparing the performance of two IDS products with different architectures
Date: Tue, 23 Oct 2001 15:03:07 -0400
Message-ID: <000f01c15bf5$5b031b90$89a486d1@computer11111111111111111111111111111111>

> -----Original Message-----
> From: iheagwarac@aol.com [mailto:iheagwarac@aol.com]
> Does anyone know if there is justification to compare the
> performance of IDS
> products with pattern-matching technique with those IDS
> products that use
> the state-based (protocol analysis)technique in the same
> network environments?
>
> What will be the strenght of the arguments?

I assume you are asking for some of the theory behind IDS performance,
comparing "state-based protocol-analysis" vs "pattern-search" techniques.

There are two fundamental advantages that state-based protocol-analysis has
over pattern-search in regards to performance:
1. more efficient processing of traffic
2. scales better as you add more signatures

A good example would be to compare how an IDS looks for RPC exploits. A
pattern-search system looks for patterns on ranges of ports where RPC
programs typically run. For example, it might look on ports in the range 634
through 1400 for the AMD exploit. In contrast, a state-based system can
remember which ports the AMD service is running on, and only test the AMD
signatures on those ports that are actually running AMD. If no system on the
network is running AMD, then a state-based system will never test network
traffic for those signatures.

The theory behind this is that a pattern-search system doesn't know the
contents of the packets, and must search that packet for many different
patterns. In contrast, a protocol-analysis system knows the contents of the
packet, and only tests signatures that apply to those contents.

Given an average packet, a pattern-search system might have to search for 10
different patterns within that packet. In contrast, on average, a
state-based protocol-analysis system tests less than 0.1 signatures per
packet.

This doesn't come for free: the state-based protocol-analysis that knows
whether or not it should test for signatures itself costs the same as
testing for a couple of signatures. Thus, the per-packet cost for
pattern-search might be 10 signatures, and the per-packet cost for
state-based protocol analysis might be 2 signatures.

The second part of the theory is that for pattern-search systems, the more
signatures you add to the system, the slower the system becomes. If you look
in the documentation for the average sensor, it will have a comprehensive
discussion on how to remove signatures in order to improve performance. This
isn't applicable to a state-based protocol-analysis system.

A good example is to consider looking for Telnet login strings. There are
many well-known login names that rootkits will leave behind on the system. A
pattern-search system must scan all Telnet traffic for all these patterns --
the more patterns you add, the slower it becomes.

In contrast, a protocol-analysis system will decode Telnet and extract the
login name. It can then lookup the name in a binary-search tree or a
hashtable. The difference is that a pattern-search system must search for
patterns within network traffic, which scales poorly. In contrast, a
protocol-analysis system pulls out a field from network traffic, and
searches for that field within an internal table, which scales very well
[O(c) or O(logn)].

[Again, not in the Telnet example that a username signature is only tested
against the username field -- another demonstration of the first point that
a packet is only tested for a signature when needed, and not when it isn't
needed.]

This is the theory behind the comparison. In practice, there are a lot of
issues that can become more important. For example, CPU speeds are doubling
every year.

Robert Graham

Disclaimer: I'm the architect of BlackICE and RealSecure 7 intrusion
detection systems from ISS, which are state-based protocol-analysis based
and seem to be running extremely fast. Note that even protocol-analysis
systems sometimes match patterns, so I prefer using the term
"pattern-search" -- BlackICE/RealSecure essentially does no "search", only
exact "matches".


_________________________________________________________
Do You Yahoo!?
Get your free @yahoo.com address at http://mail.yahoo.com