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

From: Mike Frantzen (frantzen@w4g.org)
Date: 10/17/02


From: Mike Frantzen <frantzen@w4g.org>
To: Carson Gaspar <carson@taltos.org>
Date: Thu Oct 17 19:34:01 2002


> >Hi Carson,
> >State entry lookups don't actually occur in constant time.
> Yes they do, if you have enough memory, and a good enough hash function,
> such that collisions are low. The paper you mentioned argued that for the
> hash functions they tried, Khash > log(n)*Ktree, for reasonable values of
> n. It never said that the hash function time wasn't invariant with n.

The problem with a hashed state table is that hash tables are very easy
to attack. The use of collision chains (linked lists) would let an
attack totally blow out the D$ and TLB. I've make a sun U10 440mhz w/
2MB L2 grind to a halt w/ 5 packets a second after a long series of
collisions.

Rehash paths aren't so bad if it is an array of state objects instead of
an array of pointers since you'll get good D$ and TLB performance. But
that has a much higher initial memory cost (and you may not have space
in the kernel map to accomodate it).

This is why PF uses a state tree. Optimal case is worse that hash
tables. But worst case is O(log n) as opposed to O(n). Alright, it
uses redblack trees so it is technically 2*log n worst case.

.mike
frantzen@(nfr.com | cvs.openbsd.org | w4g.org)