You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@httpd.apache.org by Ed Korthof <ed...@bitmechanic.com> on 1998/08/08 05:43:25 UTC

Re: more O(n^2)

On Fri, 7 Aug 1998, Dean Gaudet wrote:

> If you send hundreds of different named headers you can tweak an O(n^2) 
> cpu time attack in the table scanning. 
> 
> Personally I don't see the problem with limiting the total length of all
> headers to 16k (run-time configurable).  Didn't we come to this same
> conclusion during the last round of DoS attacks?

When I originally did the patch which improved 414 handling (thanks for
fixing the remaining problems, Roy :), I also limited the total number of
headers (to a compiler define, I seem to remember).  Somewhere, that
change was lost (possibly before I submitted it, as I thought the improved
414 handling more important).

Unfortunately, a limit to the total length of data read from the client
leaves you open to the DoS which was posted -- if you limit it to 16k, you
can still get in about 4k headers ("a:a\n"), which will blow up the
footprint quite significantly.  I tried this, on

Linux crankshaft 2.0.33 #1 Sun Apr 26 22:00:21 PDT 1998 i686 unknown

Here is the resulting size:

  PID USER     PRI  NI  SIZE  RSS SHARE STAT  LIB %CPU %MEM   TIME COMMAND
18854 ed        18   0 35260  34M   704 S       0  7.5 22.0   0:01 httpd.1.3
18860 ed        16   0   592  592   456 R       0  4.7  0.3   0:00 top

You can't get much more than 3.2k headers if you want distinct headers
(for the O(n^2) attack you're talking about, Dean) -- that may or may not
be enough headers for the time to be significant.  But putting a
configurable limit on the total number of headers is (IMO, of course) the
best way to protect against this kind of DoS attack... 

Ed