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