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)



Relevant Pages

  • Re: What are my options for dictionary hashing?
    ... which is that symtab is as good or better than the hash table ... hashing you can let the load go well over 100%. ... The amount of memory used in a hash table is the sum of N (the link ... Assuming that there aren't any collisions, S=N/L, so the total memory ...
    (comp.lang.forth)
  • Re: What are my options for dictionary hashing?
    ... So 1.3k extra memory for the ANS wordset. ... which is that symtab is as good or better than the hash table ... hashing you can let the load go well over 100%. ... Assuming that there aren't any collisions, S=N/L, so the total memory ...
    (comp.lang.forth)
  • Re: item access time: sets v. lists
    ... Random access to item in list/set when item does not exist ... A set, on the other hand, uses a hash table so finding an element takes ... constant time (it's one hash lookup, independent of the size of the ... set)--and determining an item isn't there is likewise constant time. ...
    (comp.lang.python)
  • Re: What are my options for dictionary hashing?
    ... The Wikipedia article says that they can go up to a load factor ... me offering other types of hash tables that don't have ... collisions (and the amount of memory used). ...
    (comp.lang.forth)
  • Re: Hashtables?
    ... Add, Removeand Lookupis strongly dependent on the hash ... For synchronization purposes see the static Synchronized method of ...
    (microsoft.public.dotnet.csharp.general)