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; }