Re: CERT vulnerability note VU# 539363 (fwd)

[Daniel Hartmeier <daniel () benzedrine cx>]

On Wed, Oct 16, 2002 at 12:24:11PM -0400, Paul Robertson wrote:

> > In my experience (our stuff), ruleset lookup hits on stateless packet 
> > forwarding rules at the _very top_ of the ruleset is comparable to 
> > keeping state.
>
> Hmmm, is this because "normal" rules aren't optimized or hashed, but state 
> tables were kind of pre-assumed to be a performance issue, and therefore 
> given performance attention at the design stage?  Maybe it's just because 
> the state information is easy to do a boolean comparison on?

In case of pf, it's because states are stored in a binary search tree,
which means you find a matching state entry in O(log n) (n being the
number of state entries), since you can skip half of the non-matching
entries in each comparison (like searching for a name in a phone book).

Rule sets, on the other hand, are usually evaluated linearly (or in tree
form), but you can't generally find the relevant/deciding rule as
efficiently as in a binary search.

Rule sets can be as complex as a programming language, and evaluation
actually 'executes' the rules from start to end (or until the 'program'
aborts, returning the decision), and you can't just jump to the last
instruction to get the result (because the results depends on how
previous rules applied).

There are simpler forms of rules which _can_ be hashed, and those are
of course faster than even a state lookup. But they only allow to
specify address and port combinations to block or drop.

So, while the number of entries is relevant in both data structures, the
alogrithm used to access it defines how it scales. Of course, the
constant cost of a state lookup and a rule evaluation may shift the
point where keeping state starts to pay off.

> Have any kind of feel for where the line is?  Daniel's 5000 to 100 mention 
> has me wondering if we can codify the sorts of places where this can be an 
> easy performance win for folks who are in high utilization scenerios.

I think it depends largely on the product and rules you have, so I
wouldn't speculate about a general number for the break-even point. But
I recommend to anyone with a (stateful) firewall busy filtering
statelessy to try and keep state and compare.

If you're running a packet filter on a BSD system, for instance, you can
easily find the bottlenecks running kernel profiling. If the function
doing rule evaluation uses up 95% cpu while the state lookup one is
rarely called, keeping state is worth a try. :)

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