You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@httpd.apache.org by Dean Gaudet <dg...@arctic.org> on 1998/08/08 08:05:10 UTC
[PATCH] DoS fix
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.
Lightly tested. (i.e. I tested a few boundary conditions and basic
functionality).
Roy: I haven't looked at the standard yet, but does it mandate that
footers must be merged with headers? It should mention it if it doesn't
already.
Martin: I imagine the proxy is subject to a similar attack, I'm just
guessing though. This get_mime_headers thing should be generalized if so.
It sucks that we have to put all this crap into the normal path. Oh well.
At least with the flow front end we can ignore stupid requests and punt
them to this full, slow handler.
Dean
Index: main/http_protocol.c
===================================================================
RCS file: /export/home/cvs/apache-1.3/src/main/http_protocol.c,v
retrieving revision 1.229
diff -u -r1.229 http_protocol.c
--- http_protocol.c 1998/08/06 17:30:30 1.229
+++ http_protocol.c 1998/08/08 05:56:08
@@ -708,12 +708,76 @@
return 1;
}
+/* Curse libc and the fact that it doesn't guarantee a stable sort. We
+ * have to enforce stability ourselves by using the order field. -djg
+ */
+typedef struct {
+ char *key;
+ char *val;
+ unsigned order;
+} mime_key;
+
+static int sort_mime_headers(const void *va, const void *vb)
+{
+ const mime_key *a = va;
+ const mime_key *b = vb;
+ int r;
+
+ r = strcasecmp(a->key, b->key);
+ if (r) {
+ return r;
+ }
+ return (signed)a->order - (signed)b->order;
+}
+
static void get_mime_headers(request_rec *r)
{
conn_rec *c = r->connection;
int len;
char *value;
char field[MAX_STRING_LEN];
+ array_header *arr;
+ pool *tmp;
+ mime_key *new_key;
+ unsigned order;
+ mime_key *first;
+ mime_key *last;
+ mime_key *end;
+ char *strp;
+
+ /* The array will store the headers in a way that we can merge them
+ * later in O(n*lg(n))... rather than deal with various O(n^2)
+ * operations.
+ */
+ tmp = ap_make_sub_pool(r->pool);
+ arr = ap_make_array(tmp, 50, sizeof(mime_key));
+ order = 0;
+
+ /* If headers_in is non-empty (i.e. we're parsing a trailer) then
+ * we have to merge. Have I mentioned that I think this is a lame part
+ * of the HTTP standard? Anyhow, we'll cheat, and just pre-seed our
+ * array with the existing headers... and take advantage of the much
+ * faster merging here.
+ */
+ if (!ap_is_empty_table(r->headers_in)) {
+ array_header *t_arr;
+ table_entry *t;
+ table_entry *t_end;
+
+ t_arr = ap_table_elts(r->headers_in);
+ t = (table_entry *)t_arr->elts;
+ t_end = t + t_arr->nelts;
+ while (t < t_end) {
+ new_key = ap_push_array(arr);
+ new_key->order = order++;
+ new_key->key = t->key;
+ new_key->val = t->val;
+ ++t;
+ }
+ /* XXX: this doesn't follow the API, but it works. We want to empty
+ * out the table. */
+ t_arr->nelts = 0;
+ }
/*
* Read header lines until we get the empty separator line, a read error,
@@ -725,6 +789,7 @@
if (!(value = strchr(copy, ':'))) { /* Find the colon separator */
r->status = HTTP_BAD_REQUEST; /* or abort the bad request */
+ ap_destroy_pool(tmp);
return;
}
@@ -735,7 +800,17 @@
/* XXX: should strip trailing whitespace as well */
- ap_table_mergen(r->headers_in, copy, value);
+ /* Notice that key and val are actually in r->pool... this is a slight
+ * optimization to handle the normal case, where we don't have twits
+ * trying to exploit the server. In the abnormal case where twits are
+ * trying to exploit the server by causing it to do header merging
+ * and other such nonsense we consume twice as much memory as we
+ * could optimally. Oh well. -djg
+ */
+ new_key = ap_push_array(arr);
+ new_key->order = order++;
+ new_key->key = copy;
+ new_key->val = value;
/* the header was too long; at the least we should skip extra data */
if (len >= MAX_STRING_LEN - 1) {
@@ -747,6 +822,48 @@
break;
}
}
+
+ /* Now we have to merge headers. */
+ qsort(arr->elts, arr->nelts, sizeof(mime_key), sort_mime_headers);
+
+ /* Now iterate over the array and build r->headers_in. */
+ first = (mime_key *)arr->elts;
+ end = first + arr->nelts;
+ while (first < end) {
+ last = first + 1;
+ if (last == end
+ || strcasecmp(first->key, last->key)) {
+ ap_table_addn(r->headers_in, first->key, first->val);
+ first = last;
+ }
+ else {
+ /* Have to merge some headers. Let's re-use the order field,
+ * since it's handy... we'll store the length of val there.
+ */
+ first->order = strlen(first->val);
+ len = first->order;
+ do {
+ last->order = strlen(last->val);
+ len += 2 + last->order;
+ ++last;
+ } while (last < end
+ && !strcasecmp(first->key, last->key));
+ /* last points one past the last header to merge */
+ value = ap_palloc(r->pool, len + 1);
+ strp = value;
+ for (;;) {
+ memcpy(strp, first->val, first->order);
+ strp += first->order;
+ ++first;
+ if (first == last) break;
+ *strp++ = ',';
+ *strp++ = ' ';
+ }
+ *strp = 0;
+ ap_table_addn(r->headers_in, (first-1)->key, value);
+ }
+ }
+ ap_destroy_pool(tmp);
}
request_rec *ap_read_request(conn_rec *conn)
Re: [PATCH] DoS fix
Posted by Ben Laurie <be...@algroup.co.uk>.
Dean Gaudet wrote:
>
> On Sun, 9 Aug 1998, Ben Laurie wrote:
>
> > Dean Gaudet wrote:
> > > > But this should be provided as a general table thing, not just for
> > > > headers, no? And yeah, I will be doing the work if required, but not
> > > > right now - I've got a nuclear bunker to inspect (really)!
> > >
> > > Yup generalizing it would be good. Need to figure out the right
> > > generalization though...
> >
> > The simplest one is to take an unmerged table and merge it, surely?
>
> But it'd be slower than what I've got now... because it would mean we'd
> read and use ap_table_addn() in get_mime_headers() and then we'd have to
> copy all those key/val pairs to another array just to sort them (see rant
> about qsort and stability).
>
> You know me... that just bugs me :)
Yep, but:
a) then we have a solution that can be used everywhere
b) neither solution takes any noticable time for any reasonable request
(I claim)
Cheers,
Ben.
--
Ben Laurie |Phone: +44 (181) 735 0686| Apache Group member
Freelance Consultant |Fax: +44 (181) 735 0689|http://www.apache.org/
and Technical Director|Email: ben@algroup.co.uk |
A.L. Digital Ltd, |Apache-SSL author http://www.apache-ssl.org/
London, England. |"Apache: TDG" http://www.ora.com/catalog/apache/
WE'RE RECRUITING! http://www.aldigital.co.uk/recruit/
Re: [PATCH] DoS fix
Posted by Dean Gaudet <dg...@arctic.org>.
On Sun, 9 Aug 1998, Ben Laurie wrote:
> Dean Gaudet wrote:
> > > But this should be provided as a general table thing, not just for
> > > headers, no? And yeah, I will be doing the work if required, but not
> > > right now - I've got a nuclear bunker to inspect (really)!
> >
> > Yup generalizing it would be good. Need to figure out the right
> > generalization though...
>
> The simplest one is to take an unmerged table and merge it, surely?
But it'd be slower than what I've got now... because it would mean we'd
read and use ap_table_addn() in get_mime_headers() and then we'd have to
copy all those key/val pairs to another array just to sort them (see rant
about qsort and stability).
You know me... that just bugs me :)
Dean
Re: [PATCH] DoS fix
Posted by Ben Laurie <be...@algroup.co.uk>.
Dean Gaudet wrote:
> > But this should be provided as a general table thing, not just for
> > headers, no? And yeah, I will be doing the work if required, but not
> > right now - I've got a nuclear bunker to inspect (really)!
>
> Yup generalizing it would be good. Need to figure out the right
> generalization though...
The simplest one is to take an unmerged table and merge it, surely?
Cheers,
Ben.
--
Ben Laurie |Phone: +44 (181) 735 0686| Apache Group member
Freelance Consultant |Fax: +44 (181) 735 0689|http://www.apache.org/
and Technical Director|Email: ben@algroup.co.uk |
A.L. Digital Ltd, |Apache-SSL author http://www.apache-ssl.org/
London, England. |"Apache: TDG" http://www.ora.com/catalog/apache/
WE'RE RECRUITING! http://www.aldigital.co.uk/recruit/
Re: [PATCH] DoS fix
Posted by Dean Gaudet <dg...@arctic.org>.
On Sat, 8 Aug 1998, Ben Laurie wrote:
> Dean Gaudet 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.
>
> Heh! I should finish reading before writing.
:) Yeah the idea didn't quite gel until I sat down to implement it.
> But this should be provided as a general table thing, not just for
> headers, no? And yeah, I will be doing the work if required, but not
> right now - I've got a nuclear bunker to inspect (really)!
Yup generalizing it would be good. Need to figure out the right
generalization though...
I'm off to go hiking.
Dean
Re: [PATCH] DoS fix
Posted by Ben Laurie <be...@algroup.co.uk>.
Dean Gaudet 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.
Heh! I should finish reading before writing. But this should be provided
as a general table thing, not just for headers, no? And yeah, I will be
doing the work if required, but not right now - I've got a nuclear
bunker to inspect (really)!
Cheers,
Ben.
--
Ben Laurie |Phone: +44 (181) 735 0686| Apache Group member
Freelance Consultant |Fax: +44 (181) 735 0689|http://www.apache.org/
and Technical Director|Email: ben@algroup.co.uk |
A.L. Digital Ltd, |Apache-SSL author http://www.apache-ssl.org/
London, England. |"Apache: TDG" http://www.ora.com/catalog/apache/
WE'RE RECRUITING! http://www.aldigital.co.uk/recruit/
Re: [PATCH] DoS fix
Posted by Ben Laurie <be...@algroup.co.uk>.
Dean Gaudet wrote:
>
> On Sat, 8 Aug 1998, Ben Laurie wrote:
>
> > Dean Gaudet wrote:
> > > +/* Curse libc and the fact that it doesn't guarantee a stable sort. We
> > > + * have to enforce stability ourselves by using the order field. -djg
> > > + */
> >
> > Err? a) You are allowed to return 0 when they are equal
>
> If you pass qsort something like (a,1), (a,2), (b,3) (where the first
> value is the key, the second is some arbitrary data) it's not guaranteed
> to return (a,1), (a,2), (b,3) to you... it could return (a,2), (a,1),
> (b,3) -- it doesn't guarantee stability. A "stable" sort is a sort in
> which otherwise equal keys retain their original relative order in the
> output.
>
> qsort is not a stable sort in general (unlike heapsort), but it's like a
> trivial tweak to make it stable... and I'm just annoyed that it's not
> mandated as part of the standard ;)
Ah, OK. Are we required to preserve order?
> > and b) if you
> > really care, compare a->val to b->val (the address, not the content).
>
> If only that would work... unfortunately, the values are from an
> ap_palloc(), which could range all over memory... only when they fit
> within one chunk would this trick work.
Yeah, I was just trying to give _an_ ordering, not preserve the existing
ordering. I know from experience that qsort can go O(n^2) on equal
values if care isn't taken to avoid that (in the implementation), and
that was what I was attempting to cure.
In short, I'd forgotten what "stable sort" meant. :-)
Cheers,
Ben.
--
Ben Laurie |Phone: +44 (181) 735 0686| Apache Group member
Freelance Consultant |Fax: +44 (181) 735 0689|http://www.apache.org/
and Technical Director|Email: ben@algroup.co.uk |
A.L. Digital Ltd, |Apache-SSL author http://www.apache-ssl.org/
London, England. |"Apache: TDG" http://www.ora.com/catalog/apache/
WE'RE RECRUITING! http://www.aldigital.co.uk/recruit/
Re: [PATCH] DoS fix
Posted by Dean Gaudet <dg...@arctic.org>.
On Sat, 8 Aug 1998, Ben Laurie wrote:
> Dean Gaudet wrote:
> > +/* Curse libc and the fact that it doesn't guarantee a stable sort. We
> > + * have to enforce stability ourselves by using the order field. -djg
> > + */
>
> Err? a) You are allowed to return 0 when they are equal
If you pass qsort something like (a,1), (a,2), (b,3) (where the first
value is the key, the second is some arbitrary data) it's not guaranteed
to return (a,1), (a,2), (b,3) to you... it could return (a,2), (a,1),
(b,3) -- it doesn't guarantee stability. A "stable" sort is a sort in
which otherwise equal keys retain their original relative order in the
output.
qsort is not a stable sort in general (unlike heapsort), but it's like a
trivial tweak to make it stable... and I'm just annoyed that it's not
mandated as part of the standard ;)
> and b) if you
> really care, compare a->val to b->val (the address, not the content).
If only that would work... unfortunately, the values are from an
ap_palloc(), which could range all over memory... only when they fit
within one chunk would this trick work.
Dean
Re: [PATCH] DoS fix
Posted by Ben Laurie <be...@algroup.co.uk>.
Dean Gaudet 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.
>
> Lightly tested. (i.e. I tested a few boundary conditions and basic
> functionality).
>
> Roy: I haven't looked at the standard yet, but does it mandate that
> footers must be merged with headers? It should mention it if it doesn't
> already.
>
> Martin: I imagine the proxy is subject to a similar attack, I'm just
> guessing though. This get_mime_headers thing should be generalized if so.
>
> It sucks that we have to put all this crap into the normal path. Oh well.
> At least with the flow front end we can ignore stupid requests and punt
> them to this full, slow handler.
>
> Dean
>
> Index: main/http_protocol.c
> ===================================================================
> RCS file: /export/home/cvs/apache-1.3/src/main/http_protocol.c,v
> retrieving revision 1.229
> diff -u -r1.229 http_protocol.c
> --- http_protocol.c 1998/08/06 17:30:30 1.229
> +++ http_protocol.c 1998/08/08 05:56:08
> @@ -708,12 +708,76 @@
> return 1;
> }
>
> +/* Curse libc and the fact that it doesn't guarantee a stable sort. We
> + * have to enforce stability ourselves by using the order field. -djg
> + */
Err? a) You are allowed to return 0 when they are equal and b) if you
really care, compare a->val to b->val (the address, not the content).
Or are you saying that if you return 0 a lot it may become O(n^2) (in
which case use b)?
Cheers,
Ben.
--
Ben Laurie |Phone: +44 (181) 735 0686| Apache Group member
Freelance Consultant |Fax: +44 (181) 735 0689|http://www.apache.org/
and Technical Director|Email: ben@algroup.co.uk |
A.L. Digital Ltd, |Apache-SSL author http://www.apache-ssl.org/
London, England. |"Apache: TDG" http://www.ora.com/catalog/apache/
WE'RE RECRUITING! http://www.aldigital.co.uk/recruit/
Re: [PATCH] DoS fix
Posted by Dean Gaudet <dg...@arctic.org>.
There's still O(n^2) cpu-time crap in ap_add_common_vars because it
combines headers_in with subprocess_env.
Similarly, ap_scan_script_header_err_core is O(n^2) space -- abusive CGIs
can also cause the httpd to blow up in the same way that get_mime_headers
is broken.
The construction of "Content-Language" in http_protocol.c is O(n^2) space.
Probably not worth worrying about.
merge_string_array in mod_negotiation.c is O(n^2) space. I don't know how
easy it is to abuse. The construction of Alternates is also O(n^2)
space... I suspect both of these aren't worth worrying about.
There are undoubtedly numerous .htaccess attacks involving many duplicate
directives... i.e. lots of AddTypes with different types causes O(n^2)
cpu. ... or abuse mod_headers or mod_rewrite because they both use
ap_table_merge for various things, which means O(n^2) space.
Ho hum.
Dean