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

[Issac Goldstand]

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


   

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

[Joe Schaefer]

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