Re: No quadratic allocators (was Re: [RELEASE CANDIDATE] libapreq 1.34-RC2)
After going too long without any tuits, I've gotten around to properly
testing this. Looks ok, although I didn't really do anything
in-depth. - I'm going to commit and roll another RC.
Issac
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.
>
> 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).
>
> 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
>
>
>
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
>
>
>
No quadratic allocators (was Re: [RELEASE CANDIDATE] libapreq 1.34-RC2)
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.
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).
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
--
Joe Schaefer
Re: [RELEASE CANDIDATE] libapreq 1.34-RC2
On Mon, 30 Apr 2007, 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. We need a few votes from pmc members before Issac can release. I'm away for the next several days, but will give it a try on Win32 when I return. -- best regards, Randy
Re: [RELEASE CANDIDATE] libapreq 1.34-RC2
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. We need a few votes from pmc members before Issac can release. -- Joe Schaefer
Re: [RELEASE CANDIDATE] libapreq 1.34-RC2
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. -- Joe Schaefer
Re: [RELEASE CANDIDATE] libapreq 1.34-RC2
Issac Goldstand wrote: 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] All still OK on WinXP/VC6 with perl-5.8.8, apache-1.3.34, mod_perl-1.29. --
