You are viewing a plain text version of this content. The canonical link for it is here.
Posted to cvs@httpd.apache.org by dg...@hyperreal.org on 1998/08/14 04:49:58 UTC
cvs commit: apache-1.3/src/modules/standard mod_cern_meta.c
dgaudet 98/08/13 19:49:57
Modified: src CHANGES
src/include alloc.h
src/main alloc.c http_protocol.c util_script.c
src/modules/standard mod_cern_meta.c
Log:
Add ap_overlap_tables. Fix various O(n^2) attacks using it.
Revision Changes Path
1.1024 +3 -1 apache-1.3/src/CHANGES
Index: CHANGES
===================================================================
RCS file: /export/home/cvs/apache-1.3/src/CHANGES,v
retrieving revision 1.1023
retrieving revision 1.1024
diff -u -r1.1023 -r1.1024
--- CHANGES 1998/08/13 01:54:59 1.1023
+++ CHANGES 1998/08/14 02:49:42 1.1024
@@ -22,7 +22,9 @@
[Jim Jagielski]
*) SECURITY: Eliminate O(n^2) space DoS attacks (and other O(n^2)
- cpu time attacks) in header parsing. [Dean Gaudet]
+ cpu time attacks) in header parsing. Add ap_overlap_tables(),
+ a function which can be used to perform bulk update operations
+ on tables in a more efficient manner. [Dean Gaudet]
*) SECURITY: Added compile-time and configurable limits for
various aspects of reading a client request to avoid some simple
1.63 +4 -2 apache-1.3/src/include/alloc.h
Index: alloc.h
===================================================================
RCS file: /export/home/cvs/apache-1.3/src/include/alloc.h,v
retrieving revision 1.62
retrieving revision 1.63
diff -u -r1.62 -r1.63
--- alloc.h 1998/08/09 17:36:24 1.62
+++ alloc.h 1998/08/14 02:49:45 1.63
@@ -199,7 +199,7 @@
int i;
for (i = 0; i < barr->nelts; ++i) {
- if (merge) {
+ if (flags & AP_OVERLAP_TABLES_MERGE) {
ap_table_mergen(a, belt[i].key, belt[i].val);
}
else {
@@ -214,7 +214,9 @@
in an ancestor of a's pool. In practice b and a are usually from
the same pool.
*/
-API_EXPORT(void) ap_overlap_tables(table *a, const table *b, int merge);
+#define AP_OVERLAP_TABLES_SET (0)
+#define AP_OVERLAP_TABLES_MERGE (1)
+API_EXPORT(void) ap_overlap_tables(table *a, const table *b, unsigned flags);
/* XXX: these know about the definition of struct table in alloc.c. That
* definition is not here because it is supposed to be private, and by not
1.99 +157 -0 apache-1.3/src/main/alloc.c
Index: alloc.c
===================================================================
RCS file: /export/home/cvs/apache-1.3/src/main/alloc.c,v
retrieving revision 1.98
retrieving revision 1.99
diff -u -r1.98 -r1.99
--- alloc.c 1998/08/03 09:14:51 1.98
+++ alloc.c 1998/08/14 02:49:47 1.99
@@ -1386,6 +1386,163 @@
va_end(vp);
}
+/* Curse libc and the fact that it doesn't guarantee a stable sort. We
+ * have to enforce stability ourselves by using the order field. If it
+ * provided a stable sort then we wouldn't even need temporary storage to
+ * do the work below. -djg
+ *
+ * ("stable sort" means that equal keys retain their original relative
+ * ordering in the output.)
+ */
+typedef struct {
+ char *key;
+ char *val;
+ int order;
+} overlap_key;
+
+static int sort_overlap(const void *va, const void *vb)
+{
+ const overlap_key *a = va;
+ const overlap_key *b = vb;
+ int r;
+
+ r = strcasecmp(a->key, b->key);
+ if (r) {
+ return r;
+ }
+ return a->order - b->order;
+}
+
+/* prefer to use the stack for temp storage for overlaps smaller than this */
+#ifndef AP_OVERLAP_TABLES_ON_STACK
+#define AP_OVERLAP_TABLES_ON_STACK (512)
+#endif
+
+API_EXPORT(void) ap_overlap_tables(table *a, const table *b, unsigned flags)
+{
+ overlap_key cat_keys_buf[AP_OVERLAP_TABLES_ON_STACK];
+ overlap_key *cat_keys;
+ int nkeys;
+ table_entry *e;
+ table_entry *last_e;
+ overlap_key *left;
+ overlap_key *right;
+ overlap_key *last;
+
+ nkeys = a->a.nelts + b->a.nelts;
+ if (nkeys < AP_OVERLAP_TABLES_ON_STACK) {
+ cat_keys = cat_keys_buf;
+ }
+ else {
+ /* XXX: could use scratch free space in a or b's pool instead...
+ * which could save an allocation in b's pool.
+ */
+ cat_keys = ap_palloc(b->a.pool, sizeof(overlap_key) * nkeys);
+ }
+
+ nkeys = 0;
+
+ /* Create a list of the entries from a concatenated with the entries
+ * from b.
+ */
+ e = (table_entry *)a->a.elts;
+ last_e = e + a->a.nelts;
+ while (e < last_e) {
+ cat_keys[nkeys].key = e->key;
+ cat_keys[nkeys].val = e->val;
+ cat_keys[nkeys].order = nkeys;
+ ++nkeys;
+ ++e;
+ }
+
+ e = (table_entry *)b->a.elts;
+ last_e = e + b->a.nelts;
+ while (e < last_e) {
+ cat_keys[nkeys].key = e->key;
+ cat_keys[nkeys].val = e->val;
+ cat_keys[nkeys].order = nkeys;
+ ++nkeys;
+ ++e;
+ }
+
+ qsort(cat_keys, nkeys, sizeof(overlap_key), sort_overlap);
+
+ /* Now iterate over the sorted list and rebuild a.
+ * Start by making sure it has enough space.
+ */
+ a->a.nelts = 0;
+ if (a->a.nalloc < nkeys) {
+ a->a.elts = ap_palloc(a->a.pool, a->a.elt_size * nkeys * 2);
+ a->a.nalloc = nkeys * 2;
+ }
+
+ /*
+ * In both the merge and set cases we retain the invariant:
+ *
+ * left->key, (left+1)->key, (left+2)->key, ..., (right-1)->key
+ * are all equal keys. (i.e. strcasecmp returns 0)
+ *
+ * We essentially need to find the maximal
+ * right for each key, then we can do a quick merge or set as
+ * appropriate.
+ */
+
+ if (flags & AP_OVERLAP_TABLES_MERGE) {
+ left = cat_keys;
+ last = left + nkeys;
+ while (left < last) {
+ right = left + 1;
+ if (right == last
+ || strcasecmp(left->key, right->key)) {
+ ap_table_addn(a, left->key, left->val);
+ left = right;
+ }
+ else {
+ char *strp;
+ char *value;
+ size_t len;
+
+ /* Have to merge some headers. Let's re-use the order field,
+ * since it's handy... we'll store the length of val there.
+ */
+ left->order = strlen(left->val);
+ len = left->order;
+ do {
+ right->order = strlen(right->val);
+ len += 2 + right->order;
+ ++right;
+ } while (right < last
+ && !strcasecmp(left->key, right->key));
+ /* right points one past the last header to merge */
+ value = ap_palloc(a->a.pool, len + 1);
+ strp = value;
+ for (;;) {
+ memcpy(strp, left->val, left->order);
+ strp += left->order;
+ ++left;
+ if (left == right) break;
+ *strp++ = ',';
+ *strp++ = ' ';
+ }
+ *strp = 0;
+ ap_table_addn(a, (left-1)->key, value);
+ }
+ }
+ }
+ else {
+ left = cat_keys;
+ last = left + nkeys;
+ while (left < last) {
+ right = left + 1;
+ while (right < last && !strcasecmp(left->key, right->key)) {
+ ++right;
+ }
+ ap_table_addn(a, (right-1)->key, (right-1)->val);
+ left = right;
+ }
+ }
+}
+
/*****************************************************************
*
* Managing generic cleanups.
1.238 +5 -117 apache-1.3/src/main/http_protocol.c
Index: http_protocol.c
===================================================================
RCS file: /export/home/cvs/apache-1.3/src/main/http_protocol.c,v
retrieving revision 1.237
retrieving revision 1.238
diff -u -r1.237 -r1.238
--- http_protocol.c 1998/08/11 09:26:24 1.237
+++ http_protocol.c 1998/08/14 02:49:50 1.238
@@ -713,77 +713,18 @@
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;
-}
-
-/* XXX: could use ap_overlap_tables here... which generalizes this code */
static void get_mime_headers(request_rec *r)
{
char field[DEFAULT_LIMIT_REQUEST_FIELDSIZE + 2]; /* getline's two extra */
conn_rec *c = r->connection;
char *value;
char *copy;
- pool *tmp;
- array_header *arr;
- mime_key *new_key;
- mime_key *first;
- mime_key *last;
- mime_key *end;
- char *strp;
- unsigned order;
int len;
unsigned int fields_read = 0;
+ table *tmp_headers;
- /* 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. -djg
- */
- 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;
- }
- ap_clear_table(r->headers_in);
- }
+ /* We'll use ap_overlap_tables later to merge these into r->headers_in. */
+ tmp_headers = ap_make_table(r->pool, 50);
/*
* Read header lines until we get the empty separator line, a read error,
@@ -797,7 +738,6 @@
ap_table_setn(r->notes, "error-notes",
"The number of request header fields exceeds "
"this server's limit.<P>\n");
- ap_destroy_pool(tmp);
return;
}
/* getline returns (size of max buffer - 1) if it fills up the
@@ -809,7 +749,6 @@
ap_table_setn(r->notes, "error-notes", ap_pstrcat(r->pool,
"Size of a request header field exceeds server limit.<P>\n"
"<PRE>\n", field, "</PRE>\n", NULL));
- ap_destroy_pool(tmp);
return;
}
copy = ap_palloc(r->pool, len + 1);
@@ -820,7 +759,6 @@
ap_table_setn(r->notes, "error-notes", ap_pstrcat(r->pool,
"Request header field is missing colon separator.<P>\n"
"<PRE>\n", copy, "</PRE>\n", NULL));
- ap_destroy_pool(tmp);
return;
}
@@ -831,60 +769,10 @@
/* XXX: should strip trailing whitespace as well */
- /* 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;
+ ap_table_addn(tmp_headers, copy, value);
}
- /* 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);
+ ap_overlap_tables(r->headers_in, tmp_headers, AP_OVERLAP_TABLES_MERGE);
}
request_rec *ap_read_request(conn_rec *conn)
1.129 +57 -32 apache-1.3/src/main/util_script.c
Index: util_script.c
===================================================================
RCS file: /export/home/cvs/apache-1.3/src/main/util_script.c,v
retrieving revision 1.128
retrieving revision 1.129
diff -u -r1.128 -r1.129
--- util_script.c 1998/08/09 17:36:26 1.128
+++ util_script.c 1998/08/14 02:49:51 1.129
@@ -188,10 +188,9 @@
return env;
}
-/* XXX: this could use ap_overlap_tables */
API_EXPORT(void) ap_add_common_vars(request_rec *r)
{
- table *e = r->subprocess_env;
+ table *e;
server_rec *s = r->server;
conn_rec *c = r->connection;
const char *rem_logname;
@@ -200,11 +199,15 @@
char *env_temp;
#endif
const char *host;
-
array_header *hdrs_arr = ap_table_elts(r->headers_in);
table_entry *hdrs = (table_entry *) hdrs_arr->elts;
int i;
+ /* use a temporary table which we'll overlap onto
+ * r->subprocess_env later
+ */
+ e = ap_make_table(r->pool, 25 + hdrs_arr->nelts);
+
/* First, add environment vars from headers... this is as per
* CGI specs, though other sorts of scripting interfaces see
* the same vars...
@@ -221,10 +224,10 @@
*/
if (!strcasecmp(hdrs[i].key, "Content-type")) {
- ap_table_setn(e, "CONTENT_TYPE", hdrs[i].val);
+ ap_table_addn(e, "CONTENT_TYPE", hdrs[i].val);
}
else if (!strcasecmp(hdrs[i].key, "Content-length")) {
- ap_table_setn(e, "CONTENT_LENGTH", hdrs[i].val);
+ ap_table_addn(e, "CONTENT_LENGTH", hdrs[i].val);
}
/*
* You really don't want to disable this check, since it leaves you
@@ -238,7 +241,7 @@
}
#endif
else {
- ap_table_setn(e, http2env(r->pool, hdrs[i].key), hdrs[i].val);
+ ap_table_addn(e, http2env(r->pool, hdrs[i].key), hdrs[i].val);
}
}
@@ -248,54 +251,56 @@
#ifdef WIN32
if (env_temp = getenv("SystemRoot")) {
- ap_table_setn(e, "SystemRoot", env_temp);
+ ap_table_addn(e, "SystemRoot", env_temp);
}
if (env_temp = getenv("COMSPEC")) {
- ap_table_setn(e, "COMSPEC", env_temp);
+ ap_table_addn(e, "COMSPEC", env_temp);
}
if (env_temp = getenv("WINDIR")) {
- ap_table_setn(e, "WINDIR", env_temp);
+ ap_table_addn(e, "WINDIR", env_temp);
}
#endif
- ap_table_setn(e, "PATH", env_path);
- ap_table_setn(e, "SERVER_SOFTWARE", ap_get_server_version());
- ap_table_setn(e, "SERVER_NAME", ap_get_server_name(r));
- ap_table_setn(e, "SERVER_PORT",
+ ap_table_addn(e, "PATH", env_path);
+ ap_table_addn(e, "SERVER_SOFTWARE", ap_get_server_version());
+ ap_table_addn(e, "SERVER_NAME", ap_get_server_name(r));
+ ap_table_addn(e, "SERVER_PORT",
ap_psprintf(r->pool, "%u", ap_get_server_port(r)));
host = ap_get_remote_host(c, r->per_dir_config, REMOTE_HOST);
if (host) {
- ap_table_setn(e, "REMOTE_HOST", host);
+ ap_table_addn(e, "REMOTE_HOST", host);
}
- ap_table_setn(e, "REMOTE_ADDR", c->remote_ip);
- ap_table_setn(e, "DOCUMENT_ROOT", ap_document_root(r)); /* Apache */
- ap_table_setn(e, "SERVER_ADMIN", s->server_admin); /* Apache */
- ap_table_setn(e, "SCRIPT_FILENAME", r->filename); /* Apache */
+ ap_table_addn(e, "REMOTE_ADDR", c->remote_ip);
+ ap_table_addn(e, "DOCUMENT_ROOT", ap_document_root(r)); /* Apache */
+ ap_table_addn(e, "SERVER_ADMIN", s->server_admin); /* Apache */
+ ap_table_addn(e, "SCRIPT_FILENAME", r->filename); /* Apache */
- ap_table_setn(e, "REMOTE_PORT",
+ ap_table_addn(e, "REMOTE_PORT",
ap_psprintf(r->pool, "%d", ntohs(c->remote_addr.sin_port)));
if (c->user) {
- ap_table_setn(e, "REMOTE_USER", c->user);
+ ap_table_addn(e, "REMOTE_USER", c->user);
}
if (c->ap_auth_type) {
- ap_table_setn(e, "AUTH_TYPE", c->ap_auth_type);
+ ap_table_addn(e, "AUTH_TYPE", c->ap_auth_type);
}
rem_logname = ap_get_remote_logname(r);
if (rem_logname) {
- ap_table_setn(e, "REMOTE_IDENT", ap_pstrdup(r->pool, rem_logname));
+ ap_table_addn(e, "REMOTE_IDENT", ap_pstrdup(r->pool, rem_logname));
}
/* Apache custom error responses. If we have redirected set two new vars */
if (r->prev) {
if (r->prev->args) {
- ap_table_setn(e, "REDIRECT_QUERY_STRING", r->prev->args);
+ ap_table_addn(e, "REDIRECT_QUERY_STRING", r->prev->args);
}
if (r->prev->uri) {
- ap_table_setn(e, "REDIRECT_URL", r->prev->uri);
+ ap_table_addn(e, "REDIRECT_URL", r->prev->uri);
}
}
+
+ ap_overlap_tables(r->subprocess_env, e, AP_OVERLAP_TABLES_SET);
}
/* This "cute" little function comes about because the path info on
@@ -411,6 +416,12 @@
}
+static int set_cookie_doo_doo(void *v, const char *key, const char *val)
+{
+ ap_table_addn(v, key, val);
+ return 1;
+}
+
API_EXPORT(int) ap_scan_script_header_err_core(request_rec *r, char *buffer,
int (*getsfunc) (char *, int, void *),
void *getsfunc_data)
@@ -419,6 +430,8 @@
char *w, *l;
int p;
int cgi_status = HTTP_OK;
+ table *merge;
+ table *cookie_table;
if (buffer) {
*buffer = '\0';
@@ -427,6 +440,18 @@
ap_hard_timeout("read script header", r);
+ /* temporary place to hold headers to merge in later */
+ merge = ap_make_table(r->pool, 10);
+
+ /* The HTTP specification says that it is legal to merge duplicate
+ * headers into one. Some browsers that support Cookies don't like
+ * merged headers and prefer that each Set-Cookie header is sent
+ * separately. Lets humour those browsers by not merging.
+ * Oh what a pain it is.
+ */
+ cookie_table = ap_make_table(r->pool, 2);
+ ap_table_do(set_cookie_doo_doo, cookie_table, r->err_headers_out, "Set-Cookie", NULL);
+
while (1) {
if ((*getsfunc) (w, MAX_STRING_LEN - 1, getsfunc_data) == 0) {
@@ -467,6 +492,12 @@
if ((cgi_status == HTTP_OK) && (r->method_number == M_GET)) {
cond_status = ap_meets_conditions(r);
}
+ ap_overlap_tables(r->err_headers_out, merge,
+ AP_OVERLAP_TABLES_MERGE);
+ if (!ap_is_empty_table(cookie_table)) {
+ r->err_headers_out = ap_overlay_tables(r->pool,
+ r->err_headers_out, cookie_table);
+ }
return cond_status;
}
@@ -538,17 +569,11 @@
ap_update_mtime(r, mtime);
ap_set_last_modified(r);
}
- /* The HTTP specification says that it is legal to merge duplicate
- * headers into one. Some browsers that support Cookies don't like
- * merged headers and prefer that each Set-Cookie header is sent
- * separately. Lets humour those browsers.
- */
else if (!strcasecmp(w, "Set-Cookie")) {
- ap_table_add(r->err_headers_out, w, l);
+ ap_table_add(cookie_table, w, l);
}
else {
- /* XXX: there is an O(n^2) space attack possible here */
- ap_table_merge(r->err_headers_out, w, l);
+ ap_table_add(merge, w, l);
}
}
}
1.35 +7 -2 apache-1.3/src/modules/standard/mod_cern_meta.c
Index: mod_cern_meta.c
===================================================================
RCS file: /export/home/cvs/apache-1.3/src/modules/standard/mod_cern_meta.c,v
retrieving revision 1.34
retrieving revision 1.35
diff -u -r1.34 -r1.35
--- mod_cern_meta.c 1998/08/09 17:36:29 1.34
+++ mod_cern_meta.c 1998/08/14 02:49:56 1.35
@@ -226,13 +226,17 @@
{NULL}
};
-/* XXX: another O(n^2) attack here */
+/* XXX: this is very similar to ap_scan_script_header_err_core...
+ * are the differences deliberate, or just a result of bit rot?
+ */
static int scan_meta_file(request_rec *r, FILE *f)
{
char w[MAX_STRING_LEN];
char *l;
int p;
+ table *tmp_headers;
+ tmp_headers = ap_make_table(r->pool, 5);
while (fgets(w, MAX_STRING_LEN - 1, f) != NULL) {
/* Delete terminal (CR?)LF */
@@ -278,9 +282,10 @@
r->status_line = ap_pstrdup(r->pool, l);
}
else {
- ap_table_set(r->headers_out, w, l);
+ ap_table_set(tmp_headers, w, l);
}
}
+ ap_overlap_tables(r->headers_out, tmp_headers, AP_OVERLAP_TABLES_SET);
return OK;
}