Re: No quadratic allocators (was Re: [RELEASE CANDIDATE] libapreq 1.34-RC2)

Joe Schaefer wrote:
> Joe Schaefer <[email protected]> writes:
>
>   
>> Issac Goldstand <[email protected]> writes:
>>
>>     
>>> The apreq developers are planning a maintenance release of
>>> libapreq1.  This version primarily addresses an issue noted
>>> with FireFox 2.0 truncating file uploads in SSL mode.
>>>
>>> Please give the tarball at
>>>
>>> http://people.apache.org/~issac/libapreq-1.34-RC2.tar.gz
>>>
>>> a try and report comments/problems/etc. to the apreq-dev list
>>> at [email protected].
>>>       
>> +1, tested on Debian stable i386.
>>     
>
> Having looked over some recent literature on memory allocation
> attacks, I'm changing my vote to -1.  We need to fix the 
> crappy quadratic allocator in multipart_buffer_read_body.
>
>   
Argh.  I'll try to compile this in and review later today.

> Here's a first stab at it- completely untested (I didn't even
> bother trying to compile it).  The strategy here though is to
> allocate (more than) twice the amount last allocated, so the
> total amount allocated will sum (as a geometric series) to
> no more than 2 times the final allocation, which is O(n).
>
>   
Maybe I'm missing something in the math behind this, but the current
code [I'll mention now that I don't have the current source at hand as
of the time of writing this, so maybe I'm missing some context]
shouldn't be allocating n^2, but rather n + n-1 + n-2 + ... + 1, where n
is the number of packets received...  And just a reminder that we've got
a high chance of "slack" memory at the end of the buffer with the new
code; I don't think it should matter, but I thought I'd mention it anyway.

> The problem with the current code is that the total amount
> allocated is O(n^2), where n is basically the number of packets
> received. This is entirely unsafe nowadays, so we should not bless
> a new release which contains such code.
>
> Index: c/apache_multipart_buffer.c
> ===================================================================
> --- c/apache_multipart_buffer.c	(revision 531273)
> +++ c/apache_multipart_buffer.c	(working copy)
> @@ -273,17 +273,25 @@
>      return len;
>  }
>  
> -/*
> -  XXX: this is horrible memory-usage-wise, but we only expect
> -  to do this on small pieces of form data.
> -*/
>  char *multipart_buffer_read_body(multipart_buffer *self)
>  {
>      char buf[FILLUNIT], *out = "";
> +    size_t nalloc = 1, cur_len = 0;
>  
> -    while(multipart_buffer_read(self, buf, sizeof(buf)))
> -	out = ap_pstrcat(self->r->pool, out, buf, NULL);
> +    while(multipart_buffer_read(self, buf, sizeof(buf))) {
> +        size_t len = strlen(buf);
> +        if (len + cur_len + 1 > nalloc) {
> +            char *tmp;
> +            nalloc = 2 * (nalloc + len + 1);
> +            tmp = ap_palloc(self->r->pool, nalloc);
> +            strcpy(tmp, out);
> +            out = tmp;
> +        }
>  
> +        strcpy(out + cur_len, buf);
> +        cur_len += len;
> +    }
> +
>  #ifdef DEBUG
>      ap_log_rerror(MPB_ERROR, "multipart_buffer_read_body: '%s'", out);
>  #endif
>
>
>