Re: CERT vulnerability note VU# 539363 (fwd)

[Carson Gaspar <carson () taltos org>]

[ 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