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 probertsat_private which may have no basis whatsoever in fact." probertsonat_private Director of Risk Assessment TruSecure Corporation _______________________________________________ firewall-wizards mailing list firewall-wizardsat_private http://honor.icsalabs.com/mailman/listinfo/firewall-wizards
This archive was generated by hypermail 2b30 : Wed Oct 16 2002 - 11:07:59 PDT