Henning Brauer a écrit :

>* Matthias Scheler <tron@zhadum.de> [2005-08-20 13:59]:
>  
>
>>I'm considering to reconfigure my firewall (NetBSD 3.0_BETA, PF) to use
>>stateful packet filtering. But I'm concerned about the overhead caused
>>by that.
>>    
>>
>
>there is no overhead - it is faster than stateless filtering, since 
>state lookups are way faster than ruleset evaluations.
>  
>
hmmmm? this can't be true in the general case. Let's do simple computations:
assume N active states and K rules.
for a new connection,
- the cost of stateful is: a*log(N)+b*K
- the cost of stateless is: b*K
for a new connection with M packets, the numbers are
stateful: M*a*log(N)+b*K
stateless: M*b*K

Whatever are the values of a, b, and K, if N gets high enough, stateless 
will outperform stateful.

here an extreme example is
- stateless: if inbound, allow if and only if it has ACK. if outbound, 
always allow.
- stateful: same config but using states.

in the stateless case, we have 1 rule for each iface (the optimal case 
for any search algorithm!)
in the stateful case, you'll still lookup the states.

sure, the stateless case must still guard against tcp flags attacks, but 
that wasn't the subject here.