Re: [fw-wiz] CERT vulnerability note VU# 539363 (fwd)

From: Paul Robertson (proberts@patriot.net)
Date: 10/16/02 

From: Paul Robertson <proberts@patriot.net>
To: Daniel Hartmeier <daniel@benzedrine.cx>
Date: Wed Oct 16 13:52:01 2002

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

Relevant Pages

  • Re: Why dont people use computers when annotating games? Flawed analysis of Kramnik-Anand game #
    ... position to a depth of seven more ply and the evaluation to six ply ... worked it out at the last level of iterative deepening. ... Alpha-beta and its friends don't search the entire tree but they ... No. Iterative deepening involves using something like alpha-beta at ...
    (rec.games.chess.computer)
  • Re: How is Python designed?
    ... > interpreter first scans the source script, ... describe seems to resemble continuation passing style. ... I have to admit that I don't know if continuation-based evaluation has ... > represented as tree. ...
    (comp.lang.python)
  • Re: Interesting math problem
    ... Now the puzzle is to place parentheses in such a way ... evaluation would probably complicate things. ... manipulate a tree representing the expression. ... so any tree you build will be a binary tree. ...
    (comp.lang.c)