Firewall Wizards mailing list archives
Re: CERT vulnerability note VU# 539363 (fwd)
From: "Stephen Gill" <gillsr () yahoo com>
Date: Thu, 17 Oct 2002 09:25:15 -0500
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
Current thread:
- Re: CERT vulnerability note VU# 539363 (fwd) Paul D. Robertson (Oct 16)
- Re: CERT vulnerability note VU# 539363 (fwd) Mikael Olsson (Oct 16)
- Re: CERT vulnerability note VU# 539363 (fwd) Paul Robertson (Oct 16)
- Re: CERT vulnerability note VU# 539363 (fwd) Daniel Hartmeier (Oct 16)
- Re: CERT vulnerability note VU# 539363 (fwd) Paul Robertson (Oct 16)
- Re: CERT vulnerability note VU# 539363 (fwd) Carson Gaspar (Oct 17)
- Re: CERT vulnerability note VU# 539363 (fwd) Paul Robertson (Oct 16)
- Re: CERT vulnerability note VU# 539363 (fwd) Mikael Olsson (Oct 16)
- Re: CERT vulnerability note VU# 539363 (fwd) Mikael Olsson (Oct 16)
- <Possible follow-ups>
- RE: CERT vulnerability note VU# 539363 (fwd) Schouten, Diederik (Diederik) (Oct 17)
- Re: CERT vulnerability note VU# 539363 (fwd) Stephen Gill (Oct 17)
- Re: CERT vulnerability note VU# 539363 (fwd) Carson Gaspar (Oct 17)
- Re: CERT vulnerability note VU# 539363 (fwd) Mike Frantzen (Oct 17)
- Re: CERT vulnerability note VU# 539363 (fwd) Miles Sabin (Oct 18)
- Re: CERT vulnerability note VU# 539363 (fwd) Darren Reed (Oct 22)
- Re: CERT vulnerability note VU# 539363 (fwd) Mike Frantzen (Oct 22)
- Re: CERT vulnerability note VU# 539363 (fwd) Carson Gaspar (Oct 17)
- Re: CERT vulnerability note VU# 539363 (fwd) David Wagner (Oct 18)
- RE: Re: CERT vulnerability note VU# 539363 (fwd) Ben Nagy (Oct 19)
- RE: Re: CERT vulnerability note VU# 539363 (fwd) Bill Royds (Oct 19)
- RE: Re: CERT vulnerability note VU# 539363 (fwd) Ben Nagy (Oct 19)