Mailing-List: contact dev-help@apr.apache.org; run by ezmlm
Precedence: bulk
Date: Sun, 18 Nov 2001 22:07:32 -0800
From: Brian Pane <bpane@pacbell.net>
Subject: Re: [PATCH 2] speedup for apr_table_t
To: dev@httpd.apache.org
Cc: dev@apr.apache.org
Message-id: <3BF8A1A4.8020209@pacbell.net>
MIME-version: 1.0
Content-type: text/plain; charset=us-ascii; format=flowed
Content-transfer-encoding: 7BIT
User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:0.9.5) Gecko/20011012
References: <Pine.LNX.4.33.0111182013550.7050-100000@twinlark.arctic.org>

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