dean gaudet wrote: > On Sat, 17 Nov 2001, Brian Pane wrote: > >> * A rewrite of apr_table_overlap() that uses a hash >> table (sort of) instead of qsort > > > i'm not sure this part of the patch is a good idea. the reason > apr_table_overlap() uses qsort is to prevent various O(n^2) DoS attacks > (both time & space). with your hash i think it's possible for attackers > to carefully construct headers such that they all hash the same, which > would result in an O(n^2) time attack.
Good point--it's possible to construct an O(n^2) attack with this patch. The same is true of qsort, which is O(n^2) in the worst case, but it's admittedly a lot harder to construct the worst-case data set with qsort. The most straightforward solution that I can think of is to build a balanced tree, rather than a chained hash table, out of the "overlap_key" nodes. I'll post a revised patch once I get a tree implementation working. --Brian
