Rule optimization scheme openbsd-like

Rule optimization scheme openbsd-like

[Maciej Soltysiak]

Hi,

someone on LKML writing in 'thoughts for 2.7' about netfilter development,
handed me a fistful of links related to openbsd's pf.

Out of them I only read one document so far:
http://www.benzedrine.cx/pf-paper.html

This document explains some pf's features, one of them is:

[... exerpt from the document ...]

2.8. Transparent rule set evaluation optimization

pf automatically optimizes the evaluation of the rule set. If a group of
consecutive rules all contain the same parameter, e.g., ``source address
equals 10.1.2.3,'' and a packet does not match this parameter when the
first rule of the group is evaluated, the whole group of rules is skipped,
as the packet can not possibly match any of the rules in the group.

[... exerpt from the document ...]

This feature would be really nice to have in Netfilter, any ruleset would
benefit from this without loss of performance against normal rule-by-rule
evaluation.

What do you think? Is anyone working on this

Also, I noticed that personally I am actually using an optimization like
this just by using a good ruleset. Consider a ruleset that would be
designed like so:

iptables -N tcpcheck
iptables -A tcpcheck -p tcp --syn --dport 80 -j ACCEPT
...
iptables -A tcpcheck -j REJECT

iptables -A INPUT -m state --state ESTABLISHED,RELATED -j ACCEPT
iptables -A INPUT -p tcp -j tcpcheck
iptables -A INPUT -p icmp -j icmpcheck
iptables -A INPUT -p udp -j udpcheck
iptables -A INPUT -j LOG

This ruleset actually works similarily to 'skip-steps' mentioned in
the document thanks to the -p tcp -j tcpcheck rules. This sorts the rules
evalution into groups, and skips the rules that would not be matched for
sure. The parameter used is the protocol type.

It might be a good rule writing technique to add to the HOWTO or to write
a HOWTO on rule writing technique.


Regards,
Maciej

Re: Rule optimization scheme openbsd-like

[Jozsef Kadlecsik]

Hi,

On Mon, 13 Oct 2003, Maciej Soltysiak wrote:

> 2.8. Transparent rule set evaluation optimization
>
> pf automatically optimizes the evaluation of the rule set. If a group of
> consecutive rules all contain the same parameter, e.g., ``source address
> equals 10.1.2.3,'' and a packet does not match this parameter when the
> first rule of the group is evaluated, the whole group of rules is skipped,
> as the packet can not possibly match any of the rules in the group.
[...]
> What do you think? Is anyone working on this

nf-hipac is already available and it's more superior than the pf approach.

Best regards,
Jozsef
-
E-mail  : kadlec@blackhole.kfki.hu, kadlec@sunserv.kfki.hu
PGP key : http://www.kfki.hu/~kadlec/pgp_public_key.txt
Address : KFKI Research Institute for Particle and Nuclear Physics
          H-1525 Budapest 114, POB. 49, Hungary

Re: Rule optimization scheme openbsd-like

[Maciej Soltysiak]

> nf-hipac is already available and it's more superior than the pf approach.
A-ha! Thanks, I'll check it out.

Regards,
Maciej

Re: Rule optimization scheme openbsd-like

[Harald Welte]

[-- Attachment #1: Type: text/plain, Size: 1739 bytes --]

On Mon, Oct 13, 2003 at 10:25:00AM +0200, Maciej Soltysiak wrote:
> Hi,
> 
> someone on LKML writing in 'thoughts for 2.7' about netfilter development,
> handed me a fistful of links related to openbsd's pf.
> 
> Out of them I only read one document so far:
> http://www.benzedrine.cx/pf-paper.html
> 
> This document explains some pf's features, one of them is:

Please read the proceedings of the netfilter workshop (can be found in
the documentation directory of the CVS tree).

> 2.8. Transparent rule set evaluation optimization

Iptables (or pkttables as its successor) will stay a linked list with no
optimizations.  If you need an optimized ruleset, you will use nf-hipac
- which will be most likely using the same userspace configuration tool.

> What do you think? Is anyone working on this

no, I think it is just a waste of time.  If you are interested in high
performance, especially with medium to large sized rulesets, nf-hipac is
the way to go.

> It might be a good rule writing technique to add to the HOWTO or to write
> a HOWTO on rule writing technique.

yes, that was something I always wanted to do but never got around
doing.  Actually I started it once, but didn't get very far.

When I'm back home next weekend, I'll see if I can find that old piece
of document and send it to you.

> Regards,
> Maciej

-- 
- Harald Welte <laforge@netfilter.org>             http://www.netfilter.org/
============================================================================
  "Fragmentation is like classful addressing -- an interesting early
   architectural error that shows how much experimentation was going
   on while IP was being designed."                    -- Paul Vixie

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]

Re: Rule optimization scheme openbsd-like

[Maciej Soltysiak]

> > It might be a good rule writing technique to add to the HOWTO or to write
> > a HOWTO on rule writing technique.
>
> yes, that was something I always wanted to do but never got around
> doing.  Actually I started it once, but didn't get very far.
>
> When I'm back home next weekend, I'll see if I can find that old piece
> of document and send it to you.
Ok, I could try to finish it.

Maciej

Re: Rule optimization scheme openbsd-like

[Maciej Soltysiak]

> yes, that was something I always wanted to do but never got around
> doing.  Actually I started it once, but didn't get very far.
>
> When I'm back home next weekend, I'll see if I can find that old piece
> of document and send it to you.
A long weekend :)
Could you send me the document in free time ?

Maciej

Re: Rule optimization scheme openbsd-like

[Harald Welte]

[-- Attachment #1: Type: text/plain, Size: 1632 bytes --]

On Thu, Oct 30, 2003 at 01:57:44PM +0100, Maciej Soltysiak wrote:
> > yes, that was something I always wanted to do but never got around
> > doing.  Actually I started it once, but didn't get very far.
> >
> > When I'm back home next weekend, I'll see if I can find that old piece
> > of document and send it to you.
> A long weekend :)
> Could you send me the document in free time ?

I didn't find it, unfortunately :(

but it would be great if you'd write one. the general rules are simple.
You major goal is:

- reduce number of rule iterations necessarry for every packet

everything else is just explaining the practical consequences of this to
the user, giving examples, ...

so you should try to branch into userdefined chains whenever possible
(usually one for every host in your dmz, one for related packets, etc.)

another good advice is:  don't replicate unneccessary matches. something
like:

iptables -A FORWARD -m state --state ESTABLISHED -j my_estab_chain
iptables -A my_estab_chain -m state --state ESTABLISHED -p tcp -j ACCEPT

in this case you have already matched against 'ESTABLISHED' before
jumping to the chain.  So every rule in the chain should _not_ have that
match replicated.

thanks!

> Maciej

-- 
- Harald Welte <laforge@netfilter.org>             http://www.netfilter.org/
============================================================================
  "Fragmentation is like classful addressing -- an interesting early
   architectural error that shows how much experimentation was going
   on while IP was being designed."                    -- Paul Vixie

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]