httpd-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Dean Gaudet <dgau...@arctic.org>
Subject Re: [PATCH] DoS fix
Date Sun, 09 Aug 1998 02:59:40 GMT


On Sat, 8 Aug 1998, Roy T. Fielding wrote:

> >This replaces the O(n^2) space with O(n), and the O(n^2) cpu time stuff
> >with O(n*lg(n)).  The idea is simple -- read everything first, without
> >merging, then sort based on the keys, then merge the values if required. 
> 
> Cute hack, but the HTTP protocol is designed for efficient handling
> of header fields.  The problem is that our tables data structure sucks
> for HTTP header fields (we've talked about that in the past).
> If we are going to make any significant change to the parsing, then
> I'd start with replacing the data structure with something that
> doesn't require a copy on merge.
> 
> There are a bunch of ways to do this, but my guess (based on actual
> header fields used being a sparse subset of those defined by HTTP)
> is that a hash or tree-based tokenizer for reducing the field name

Trees are still O(n*lg(n)).  Hashes are O(n^2) with a possibly small
constant, and you figure that folks wouldn't waste all their time
manufacturing a bad hashing sequence... but you never know what these
r00t kiddies will do.  (If only they'd spend their time fixing things.)

> to an easy-to-compare number, combined with a balanced tree for holding
> the field table (logN access) and a linked list for holding the value(s)
> associated with each field table entry, is the way to go for solving
> all of these problems in the long term.

You still haven't dealt with O(n^2) string merges.  Even with realloc
it's trivial to send headers like:

h1: 1
h2: 1
h3: 1
...
hN: 1
h1: 2
h2: 2
...
hN: 2
...

repeat until you start to show the O(n^2) behaviour of realloc.

Dean


Mime
View raw message