Re: CERT vulnerability note VU# 539363 (fwd)

[Paul Robertson <proberts () patriot net>]

On Wed, 16 Oct 2002, Daniel Hartmeier wrote:

> 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.

Yeah, I'm most familiar with the green router stuff, and remember being 
farily impressed with the "push the rule down to the card" stuff in how it 
optomized rules for runtime evaluation.

> 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).

Right, but "first match" provides a quick out (hence the care and feeding 
of ruleset ordering by those who really spend time doing them properly.)
I was just thinking that you *could* do mostly the same thing with a 
permit-type rule, even if you had to go 2 or 3 more layers down the tree.

> 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.

You could do this on a permit too though, but I can see the difficult part 
is normalizing out the dependencies.

> 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.

Yep, the state engine only has to walk the full rule tree once for each 
"flow," so that makes sense- the payoff would be pretty good for anything 
with lots of traffic.

> > 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.

I was thinking more generically of being able to figure out a set of 
metrics that would give a ratio for a particular product, then perhaps 
that would be an interesting performance benchmark.

I was also thinking that a hybrid solution might be interesting- where you 
do static rules, then make the state table sort of the cache, and if you 
hit resource starvation on the state table, you can go back to analyzing 
every packet- might be an interesting approach to address the 
vulnerability note's concerns.

> 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. :)

I'm definitely re-evaluating my original biases, and kicking myself for 
never having actually _measured_ this in either a test or operational 
environment.

Paul
-----------------------------------------------------------------------------
Paul D. Robertson      "My statements in this message are personal opinions
proberts () patriot net      which may have no basis whatsoever in fact."
probertson () trusecure com Director of Risk Assessment TruSecure Corporation

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