Re: CERT vulnerability note VU# 539363 (fwd)

["Stephen Gill" <gillsr () yahoo com>]

Hi Carson,
State entry lookups don't actually occur in constant time.  Daniel
posted a very interesting paper on PF architecture and performance.  

http://www.benzedrine.cx/pf-paper.html

Or for a quick summary of his on PF of a hash v. red-black tree here:

http://www.qorbit.net/nn/Oct-2002/0092.html

Cheers,
-- steve

------------------------

Date: Thu, 17 Oct 2002 02:26:12 -0400
From: Carson Gaspar <carson () taltos org>
To: firewall-wizards () honor icsalabs com
Subject: Re: [fw-wiz] CERT vulnerability note VU# 539363 (fwd)


[ Discussion of state table performance vs. ruleset performance ]

<Warning: lecture ahead>

It is not at all surprising that state table lookups are faster. Given 
enough memory, it is trivial to implement a state table match as a hash 
lookup, which occurs in constant time, invariant with the number of
state 
entries. After all, the entire logic is matching a 
Protocol:SourceIP:SourcePort:DestIP:DestPort 5-tuple. Of course, then
you 
have to do some more checking to determine if the packet is valid, but
the 
lookup is cheap.

God, do I feel old (and I'm only 31 ;-). Does anyone else remember 
Drawbridge from TAMU? It could do packet filtering in constant time, due
to 
the design of its filtering engine. There was a significant memory /
speed 
tradeoff being made, as well as a limited ruleset grammar, but it was 
_blazingly_ fast.

I also recall Lucent having a router capable of stateless filtering of
an 
OC-12 (back when that was more impressive) in constant time, assuming
the 
number of rules was less than about 255. They used some obscure math to 
convert the ruleset into an equation that could be evaluated in
hardware, 
given the appropriate parts of the test packet as input.

Most firewalls, however, implement a linear rule traversal. In some
cases, 
they allow grouping, so it's better than linear, but I know of no
firewall 
currently in  production that claims constant time.

So, at some point:
Frule(n)*Krule > Kstate

The exact value of n varies depending on the constants, and what (if
any) 
ruleset optimization is performed (manually or automatically) by the
rule 
search algorithm.

-- 
Carson Gaspar


_______________________________________________
firewall-wizards mailing list
firewall-wizards () honor icsalabs com
http://honor.icsalabs.com/mailman/listinfo/firewall-wizards