Fixing Ranges

[Nick Kew]

AFAICS[1], we've discussed an advisory and some protections
users can deploy.  For the future we should be looking at
a robust solution that prevents Range requests only when
they're likely to present a problem.

Most obviously, we should be able to serve arbitrary ranges
from any static or cached file without sweat to support
apps such as JPEG2000 or PDF streaming.  That can be done
much more efficiently at source than in a ranges filter.

Does this look like a plan?

1. Add Ranges capability into the default handler and mod_cache.
   They could then set a "ranges-handled" flag in r->notes.
2. Insert the Ranges filter according to the logic that's
   been discussed here today.
3. The Ranges filter then checks ranges-handled, and removes
   itself if set, to avoid returning recursive ranges.

I guess implementing that would imply factoring out the
multipart encoding stuff from the range filter into an API.


[1] that is, returning to an overflowing mailbox after
a tiring day in offline chores, so I could easily have
missed something!

-- 
Nick Kew

Re: Fixing Ranges

[William A. Rowe Jr.]

On 8/24/2011 4:06 PM, Nick Kew wrote:
> AFAICS[1], we've discussed an advisory and some protections
> users can deploy.  For the future we should be looking at
> a robust solution that prevents Range requests only when
> they're likely to present a problem.
> 
> Most obviously, we should be able to serve arbitrary ranges
> from any static or cached file without sweat to support
> apps such as JPEG2000 or PDF streaming.  That can be done
> much more efficiently at source than in a ranges filter.
> 
> Does this look like a plan?
> 
> 1. Add Ranges capability into the default handler and mod_cache.
>They could then set a "ranges-handled" flag in r->notes.

Fails if the default handler has been filtered into a differently
sized document, e.g. code page conversion.

> 2. Insert the Ranges filter according to the logic that's
>been discussed here today.
> 3. The Ranges filter then checks ranges-handled, and removes
>itself if set, to avoid returning recursive ranges.

You are now requiring all filters which change the document's
geometry to not only discard C-L, but also reset ranges-handled.
Not a reasonable path forward for 2.[02].x.

Re: Fixing Ranges

[Stefan Fritsch]

On Wednesday 24 August 2011, Nick Kew wrote:
> AFAICS[1], we've discussed an advisory and some protections
> users can deploy.  For the future we should be looking at
> a robust solution that prevents Range requests only when
> they're likely to present a problem.
> 
> Most obviously, we should be able to serve arbitrary ranges
> from any static or cached file without sweat to support
> apps such as JPEG2000 or PDF streaming.  That can be done
> much more efficiently at source than in a ranges filter.
> 
> Does this look like a plan?
> 
> 1. Add Ranges capability into the default handler and mod_cache.
>They could then set a "ranges-handled" flag in r->notes.
> 2. Insert the Ranges filter according to the logic that's
>been discussed here today.
> 3. The Ranges filter then checks ranges-handled, and removes
>itself if set, to avoid returning recursive ranges.
> 
> I guess implementing that would imply factoring out the
> multipart encoding stuff from the range filter into an API.

This looks like an awful lot of work for me to fix something that 
should be a simple issue. And it is definitely too intrusive for 2.2.

I have another idea: Instead of using apr_brigade_partition write a 
new function ap_brigade_copy_part that leaves the original brigade 
untouched. It would copy the necessary buckets to a new brigade and 
then split the first and last of those copied buckets as necessary and 
destroy the excess buckets. AFAICS, this would reduce the quadratic 
growth into linear. Do you think that would solve our problems?

Re: Fixing Ranges

[Greg Ames]

On Wed, Aug 24, 2011 at 5:16 PM, Stefan Fritsch  wrote:

>
> I have another idea: Instead of using apr_brigade_partition write a
> new function ap_brigade_copy_part that leaves the original brigade
> untouched. It would copy the necessary buckets to a new brigade and
> then split the first and last of those copied buckets as necessary and
> destroy the excess buckets. AFAICS, this would reduce the quadratic
> growth into linear. Do you think that would solve our problems?
>

How does apr_brigade_partition contribute to quadratic growth?  Does the
original brigade end up with a lot of one byte buckets?

Greg

Re: Fixing Ranges

[Stefan Fritsch]

On Thursday 25 August 2011, Greg Ames wrote:
> On Wed, Aug 24, 2011 at 5:16 PM, Stefan Fritsch  
wrote:
> > I have another idea: Instead of using apr_brigade_partition write
> > a new function ap_brigade_copy_part that leaves the original
> > brigade untouched. It would copy the necessary buckets to a new
> > brigade and then split the first and last of those copied
> > buckets as necessary and destroy the excess buckets. AFAICS,
> > this would reduce the quadratic growth into linear. Do you think
> > that would solve our problems?
> 
> How does apr_brigade_partition contribute to quadratic growth? 
> Does the original brigade end up with a lot of one byte buckets?

Yes, it splits the buckets in the original brigade, creating up to two 
new buckets for every range. These split one-byte buckets are then 
copied again for each of the subsequent ranges.

The attached PoC patch does not change the original brigade and seems 
to fix the DoS for me. It needs some more work and some review for 
integer overflows, though. (apr_brigade_partition does some 
interesting things there).
diff --git a/modules/http/byterange_filter.c b/modules/http/byterange_filter.c
index 13bf0a1..f363239 100644
--- a/modules/http/byterange_filter.c
+++ b/modules/http/byterange_filter.c
@@ -140,6 +140,98 @@ static int use_range_x(request_rec *r)
 #define PARTITION_ERR_FMT "apr_brigade_partition() failed " \
   "[%" APR_OFF_T_FMT ",%" APR_OFF_T_FMT "]"
 
+static apr_status_t copy_brigade_range(apr_bucket_brigade *bb,
+   apr_bucket_brigade *bbout,
+   apr_off_t start,
+   apr_off_t end)
+{
+apr_bucket *first = NULL, *last = NULL, *out_first = NULL, *e;
+apr_off_t pos = 0, off_first = 0, off_last = 0;
+apr_status_t rv;
+const char *s;
+apr_size_t len;
+
+if (start < 0 || start > end)
+return APR_EINVAL;
+
+for (e = APR_BRIGADE_FIRST(bb);
+ e != APR_BRIGADE_SENTINEL(bb);
+ e = APR_BUCKET_NEXT(e))
+{
+/* we know that no bucket has undefined length (-1) */
+AP_DEBUG_ASSERT(e->length != (apr_size_t)(-1));
+if (!first && (e->length > start || e->length + pos > start)) {
+first = e;
+off_first = pos;
+}
+if (!last && (e->length >= end || e->length + pos >= end)) {
+last = e;
+off_last = pos;
+break;
+}
+pos += e->length;
+}
+if (!first || !last)
+return APR_EINVAL;
+
+e = first;
+for (; ; )
+{
+apr_bucket *copy;
+AP_DEBUG_ASSERT(e != APR_BRIGADE_SENTINEL(bb));
+rv = apr_bucket_copy(e, ©);
+if (rv != APR_SUCCESS)
+goto err; /* XXX try apr_bucket_read */
+
+APR_BRIGADE_INSERT_TAIL(bbout, copy);
+if (e == first) {
+if (off_first != start) {
+rv = apr_bucket_split(copy, start - off_first);
+if (rv == APR_ENOTIMPL) {
+rv = apr_bucket_read(copy, &s, &len, APR_BLOCK_READ);
+if (rv != APR_SUCCESS)
+goto err;
+rv = apr_bucket_split(copy, start - off_first);
+if (rv != APR_SUCCESS)
+goto err;
+}
+out_first = APR_BUCKET_NEXT(copy);
+APR_BUCKET_REMOVE(copy);
+apr_bucket_destroy(copy);
+}
+else {
+out_first = copy;
+}
+}
+if (e == last) {
+if (e == first) {
+off_last += start - off_first;
+copy = out_first;
+}
+else {
+APR_BRIGADE_INSERT_TAIL(bbout, copy);
+}
+if (end - off_last != e->length) {
+rv = apr_bucket_split(copy, end + 1 - off_last);
+if (rv != APR_SUCCESS)
+goto err;
+copy = APR_BUCKET_NEXT(copy);
+APR_BUCKET_REMOVE(copy);
+apr_bucket_destroy(copy);
+}
+break;
+}
+e = APR_BUCKET_NEXT(e);
+}
+
+AP_DEBUG_ASSERT(APR_SUCCESS == apr_brigade_length(bbout, 1, &pos));
+AP_DEBUG_ASSERT(pos == end - start + 1);
+return APR_SUCCESS;
+err:
+apr_brigade_cleanup(bbout);
+return rv;
+}
+
 AP_CORE_DECLARE_NONSTD(apr_status_t) ap_byterange_filter(ap_filter_t *f,
  apr_bucket_brigade *bb)
 {
@@ -149,6 +241,7 @@ AP_CORE_DECLARE_NONSTD(apr_status_t) ap_byterange_filter(ap_filter_t *f,
 byterange_ctx *ctx;
 apr_bucket *e;
 apr_bucket_brigade *bsend;
+apr_bucket_brigade *tmpbb;
 apr_off_t range_start;
 apr_off_t range_end;
 char *current;
@@ -219,31 +312,24 @@ AP_CORE_DECLARE_NONSTD(apr_status_t) ap_byterange_filter(ap_filter_t *f,
 
   

Re: Fixing Ranges

[Dirk-Willem van Gulik]

On 24 Aug 2011, at 22:16, Stefan Fritsch wrote:

> I have another idea: Instead of using apr_brigade_partition write a
> new function ap_brigade_copy_part that leaves the original brigade
> untouched. It would copy the necessary buckets to a new brigade and
> then split the first and last of those copied buckets as necessary and
> destroy the excess buckets. AFAICS, this would reduce the quadratic
> growth into linear. Do you think that would solve our problems?

This looks really rather need - it seems to tackle the core issue - that of 
memory; and it also makes it better for legitimate request with many ranges in 
it (while I never noticed before - going back and looking at them - them PDF 
requests do take a lot of memory).

Dw.

Re: Fixing Ranges

[Jim Jagielski]

Tested and this does appear to both address the DoS as well as
reduce memory usage for "excessive" range requests…

+1 for adding this no matter what.

On Aug 24, 2011, at 7:38 PM, Stefan Fritsch wrote:

> On Thursday 25 August 2011, Greg Ames wrote:
>> On Wed, Aug 24, 2011 at 5:16 PM, Stefan Fritsch  
> wrote:
>>> I have another idea: Instead of using apr_brigade_partition write
>>> a new function ap_brigade_copy_part that leaves the original
>>> brigade untouched. It would copy the necessary buckets to a new
>>> brigade and then split the first and last of those copied
>>> buckets as necessary and destroy the excess buckets. AFAICS,
>>> this would reduce the quadratic growth into linear. Do you think
>>> that would solve our problems?
>> 
>> How does apr_brigade_partition contribute to quadratic growth? 
>> Does the original brigade end up with a lot of one byte buckets?
> 
> Yes, it splits the buckets in the original brigade, creating up to two 
> new buckets for every range. These split one-byte buckets are then 
> copied again for each of the subsequent ranges.
> 
> The attached PoC patch does not change the original brigade and seems 
> to fix the DoS for me. It needs some more work and some review for 
> integer overflows, though. (apr_brigade_partition does some 
> interesting things there).
> 

Re: Fixing Ranges

[Dirk-Willem van Gulik]

On 25 Aug 2011, at 12:40, Jim Jagielski wrote:

> Tested and this does appear to both address the DoS as well as
> reduce memory usage for "excessive" range requests…
> 
> +1 for adding this no matter what.

Yup - same here. Makes PDF serving a heck of a lot better too.

Dw.

> 
> On Aug 24, 2011, at 7:38 PM, Stefan Fritsch wrote:
> 
> > On Thursday 25 August 2011, Greg Ames wrote:
> >> On Wed, Aug 24, 2011 at 5:16 PM, Stefan Fritsch 
> > wrote:
> >>> I have another idea: Instead of using apr_brigade_partition write
> >>> a new function ap_brigade_copy_part that leaves the original
> >>> brigade untouched. It would copy the necessary buckets to a new
> >>> brigade and then split the first and last of those copied
> >>> buckets as necessary and destroy the excess buckets. AFAICS,
> >>> this would reduce the quadratic growth into linear. Do you think
> >>> that would solve our problems?
> >>
> >> How does apr_brigade_partition contribute to quadratic growth?
> >> Does the original brigade end up with a lot of one byte buckets?
> >
> > Yes, it splits the buckets in the original brigade, creating up to two
> > new buckets for every range. These split one-byte buckets are then
> > copied again for each of the subsequent ranges.
> >
> > The attached PoC patch does not change the original brigade and seems
> > to fix the DoS for me. It needs some more work and some review for
> > integer overflows, though. (apr_brigade_partition does some
> > interesting things there).
> > 
> 
> 

RE: Fixing Ranges

[Plüm, Rüdiger, VF-Group]

 

> -Original Message-
> From: Stefan Fritsch  
> Sent: Donnerstag, 25. August 2011 01:39
> To: dev@httpd.apache.org
> Subject: Re: Fixing Ranges
> 
> On Thursday 25 August 2011, Greg Ames wrote:
> > On Wed, Aug 24, 2011 at 5:16 PM, Stefan Fritsch  
> wrote:
> > > I have another idea: Instead of using apr_brigade_partition write
> > > a new function ap_brigade_copy_part that leaves the original
> > > brigade untouched. It would copy the necessary buckets to a new
> > > brigade and then split the first and last of those copied
> > > buckets as necessary and destroy the excess buckets. AFAICS,
> > > this would reduce the quadratic growth into linear. Do you think
> > > that would solve our problems?
> > 
> > How does apr_brigade_partition contribute to quadratic growth? 
> > Does the original brigade end up with a lot of one byte buckets?
> 
> Yes, it splits the buckets in the original brigade, creating 
> up to two 
> new buckets for every range. These split one-byte buckets are then 
> copied again for each of the subsequent ranges.
> 
> The attached PoC patch does not change the original brigade and seems 
> to fix the DoS for me. It needs some more work and some review for 
> integer overflows, though. (apr_brigade_partition does some 
> interesting things there).
> 

I guess the following should be adjusted with this patch:

1. Do the same integer casting thing apr_brigade_partition does. So
   convert everything to apr_uint64_t and work with this.

2. Doing a read on a bucket can change its length. So we need to check
   afterwards if we still can split the bucket and if not might do a read
   on the next bucket until we are fine.

3. We should do the read bucket thing for the last bucket as well.

I think it would be best if you could commit this PoC patch as is (or with 
adjustments
according to the comments above) to trunk and we polish it up in trunk
until it is fine.

Regards

Rüdiger

RE: Fixing Ranges

[Stefan Fritsch]

On Thu, 25 Aug 2011, "Plüm, Rüdiger, VF-Group" wrote:
I think it would be best if you could commit this PoC patch as is (or 
with adjustments according to the comments above) to trunk and we polish 
it up in trunk until it is fine.


Somebody else go ahead and commit it, please. I won't have time until this 
evening, at least.


Cheers,
Stefan

Re: Fixing Ranges

[Jim Jagielski]

PoC folded into trunk… Let's go ;)

On Aug 25, 2011, at 8:16 AM, Plüm, Rüdiger, VF-Group wrote:

> 
> 
>> -Original Message-
>> From: Stefan Fritsch  
>> Sent: Donnerstag, 25. August 2011 01:39
>> To: dev@httpd.apache.org
>> Subject: Re: Fixing Ranges
>> 
>> On Thursday 25 August 2011, Greg Ames wrote:
>>> On Wed, Aug 24, 2011 at 5:16 PM, Stefan Fritsch  
>> wrote:
>>>> I have another idea: Instead of using apr_brigade_partition write
>>>> a new function ap_brigade_copy_part that leaves the original
>>>> brigade untouched. It would copy the necessary buckets to a new
>>>> brigade and then split the first and last of those copied
>>>> buckets as necessary and destroy the excess buckets. AFAICS,
>>>> this would reduce the quadratic growth into linear. Do you think
>>>> that would solve our problems?
>>> 
>>> How does apr_brigade_partition contribute to quadratic growth? 
>>> Does the original brigade end up with a lot of one byte buckets?
>> 
>> Yes, it splits the buckets in the original brigade, creating 
>> up to two 
>> new buckets for every range. These split one-byte buckets are then 
>> copied again for each of the subsequent ranges.
>> 
>> The attached PoC patch does not change the original brigade and seems 
>> to fix the DoS for me. It needs some more work and some review for 
>> integer overflows, though. (apr_brigade_partition does some 
>> interesting things there).
>> 
> 
> I guess the following should be adjusted with this patch:
> 
> 1. Do the same integer casting thing apr_brigade_partition does. So
>   convert everything to apr_uint64_t and work with this.
> 
> 2. Doing a read on a bucket can change its length. So we need to check
>   afterwards if we still can split the bucket and if not might do a read
>   on the next bucket until we are fine.
> 
> 3. We should do the read bucket thing for the last bucket as well.
> 
> I think it would be best if you could commit this PoC patch as is (or with 
> adjustments
> according to the comments above) to trunk and we polish it up in trunk
> until it is fine.
> 
> Regards
> 
> Rüdiger
> 

Re: Fixing Ranges

[Jim Jagielski]

Now that the memory utilz is being fixed, we need to determine
what sort of usage we want to allow… I'm guessing that people
are ok with http://trac.tools.ietf.org/wg/httpbis/trac/ticket/311
as the guiding spec?

RE: Fixing Ranges

[Plüm, Rüdiger, VF-Group]

+1 for 2.3, -0 for 2.2. I guess for 2.2 we should only detect "misuse" (the 
definition of misuse
needs to configurable) and reply with a 200 if misuse is detected.

misuse would be

- too much ranges [Let the number be configurable with a sane default e.g. 100 
and a possible setting of 0 for unlimited]
- overlapping ranges (after sorting) [Let this detector be configurable with a 
default to on]

For 2.3 the last one could be 3 state:

off - Don't do anything about that
on - reply with 200 if misuse is detected.
optimize - Do sorts and merges and fill too small chunks between the ranges.

Default for 2.3 would be optimize.


Regards

Rüdiger 

> -Original Message-
> From: Jim Jagielski [mailto:j...@jagunet.com] 
> Sent: Donnerstag, 25. August 2011 16:25
> To: dev@httpd.apache.org
> Subject: Re: Fixing Ranges
> 
> Now that the memory utilz is being fixed, we need to determine
> what sort of usage we want to allow... I'm guessing that people
> are ok with http://trac.tools.ietf.org/wg/httpbis/trac/ticket/311
> as the guiding spec?
> 

Re: Fixing Ranges

[Jim Jagielski]

I'm playing around w/ ap_set_byterange() for the merging and
detection part, but that should not hold up release with the
optimized code…

I can do a 2.2.10 release with the byte range stuff once we
agree on the back port and confirm it fixes the problem...

Re: Fixing Ranges

[Greg Ames]

On Thu, Aug 25, 2011 at 10:25 AM, Jim Jagielski  wrote:

> Now that the memory utilz is being fixed, we need to determine
> what sort of usage we want to allow… I'm guessing that people
> are ok with http://trac.tools.ietf.org/wg/httpbis/trac/ticket/311
> as the guiding spec?


I'm no longer convinced that we *need* to merge/optimize the Range header.
Stefan's fix to the brigade plumbing has converted O(N^2) memory + CPU use
into something scalable.

Think about the effect of this attack on the CPU cache.  My laptop has a
Core i7 with a 64kB L1 data cache.  The cache lines are 64 bytes, so I have
1024 of them per core.  The Range header I'm using has ~1300 byterange
specifiers.  apr_brigade_partition in this case will fragment the brigade
into ~1300 buckets with length 1 plus one or two for the remainder of the
file.  Each of those has to be read into the L1 cache somewhere as
apr_bucket_split walks thru the bucket structures.  That fills the cache
with junk and throws out the useful information, like the request_req,
conn_req, the filter structures, and most of the stack.  So not only will
the apr_brigade_partition calls perform like a dog but the mainline code
will suffer too.

Greg

Re: Fixing Ranges

[William A. Rowe Jr.]

On 8/25/2011 11:45 AM, Greg Ames wrote:
> On Thu, Aug 25, 2011 at 10:25 AM, Jim Jagielski  >
> wrote:
> 
> Now that the memory utilz is being fixed, we need to determine
> what sort of usage we want to allow… I'm guessing that people
> are ok with http://trac.tools.ietf.org/wg/httpbis/trac/ticket/311
> as the guiding spec?
> 
> 
> I'm no longer convinced that we *need* to merge/optimize the Range header.  
> Stefan's fix
> to the brigade plumbing has converted O(N^2) memory + CPU use into something 
> scalable. 
> 
> Think about the effect of this attack on the CPU cache.  My laptop has a Core 
> i7 with a
> 64kB L1 data cache.  The cache lines are 64 bytes, so I have 1024 of them per 
> core.  The
> Range header I'm using has ~1300 byterange specifiers.  apr_brigade_partition 
> in this case
> will fragment the brigade into ~1300 buckets with length 1 plus one or two 
> for the
> remainder of the file.  Each of those has to be read into the L1 cache 
> somewhere as
> apr_bucket_split walks thru the bucket structures.  That fills the cache with 
> junk and
> throws out the useful information, like the request_req, conn_req, the filter 
> structures,
> and most of the stack.  So not only will the apr_brigade_partition calls 
> perform like a
> dog but the mainline code will suffer too.

For the raw data you are right... but this is insignificant compared to the
CPU and network cost of assembling and transmitting all of the individual
range delimiters/headers.

Re: Fixing Ranges

[William A. Rowe Jr.]

On 8/25/2011 11:24 AM, Jim Jagielski wrote:
> I'm playing around w/ ap_set_byterange() for the merging and
> detection part, but that should not hold up release with the
> optimized code…
> 
> I can do a 2.2.10 release with the byte range stuff once we
> agree on the back port and confirm it fixes the problem...

I guess I'm a bit confused... so the net brigade/range patch should
be something reasonable anybody can apply to 2.0 / 2.2.  Let's get
that net patch published as a fresh advisory by the end of the day?

There doesn't seem to be a really good reason to release half of
the solution, if many of us agree that 'something more' should be
done, but it will take not only our consensus, but the http-wg group
server authors to find consensus on how servers will react to extra
quirky range requests starting at least in August '11.

I'd rather see 2.2.10 implement that entire solution, even if this
takes us a week.  Allowing 1-100,900-999,1-100,900-999 remains a
DoS, even if this is a trivial one, because the resources returned
exceed the reasonable resources required in bandwidth, cpu, even if
we never wasted memory.

Re: Fixing Ranges

[Jim Jagielski]

I agree we don't *need* to, but we should… 

And we do (now)

On Aug 25, 2011, at 12:45 PM, Greg Ames wrote:

> On Thu, Aug 25, 2011 at 10:25 AM, Jim Jagielski  wrote:
> Now that the memory utilz is being fixed, we need to determine
> what sort of usage we want to allow… I'm guessing that people
> are ok with http://trac.tools.ietf.org/wg/httpbis/trac/ticket/311
> as the guiding spec?
> 
> I'm no longer convinced that we *need* to merge/optimize the Range header.  
> Stefan's fix to the brigade plumbing has converted O(N^2) memory + CPU use 
> into something scalable.  
> 
> Think about the effect of this attack on the CPU cache.  My laptop has a Core 
> i7 with a 64kB L1 data cache.  The cache lines are 64 bytes, so I have 1024 
> of them per core.  The Range header I'm using has ~1300 byterange specifiers. 
>  apr_brigade_partition in this case will fragment the brigade into ~1300 
> buckets with length 1 plus one or two for the remainder of the file.  Each of 
> those has to be read into the L1 cache somewhere as apr_bucket_split walks 
> thru the bucket structures.  That fills the cache with junk and throws out 
> the useful information, like the request_req, conn_req, the filter 
> structures, and most of the stack.  So not only will the 
> apr_brigade_partition calls perform like a dog but the mainline code will 
> suffer too.
> 
> Greg

Re: Fixing Ranges

[Jim Jagielski]

On Aug 25, 2011, at 1:45 PM, William A. Rowe Jr. wrote:

> On 8/25/2011 11:24 AM, Jim Jagielski wrote:
>> I'm playing around w/ ap_set_byterange() for the merging and
>> detection part, but that should not hold up release with the
>> optimized code…
>> 
>> I can do a 2.2.10 release with the byte range stuff once we
>> agree on the back port and confirm it fixes the problem...
> 
> I guess I'm a bit confused... so the net brigade/range patch should
> be something reasonable anybody can apply to 2.0 / 2.2.  Let's get
> that net patch published as a fresh advisory by the end of the day?
> 
> There doesn't seem to be a really good reason to release half of
> the solution, if many of us agree that 'something more' should be
> done, but it will take not only our consensus, but the http-wg group
> server authors to find consensus on how servers will react to extra
> quirky range requests starting at least in August '11.
> 
> I'd rather see 2.2.10 implement that entire solution, even if this
> takes us a week.  Allowing 1-100,900-999,1-100,900-999 remains a
> DoS, even if this is a trivial one, because the resources returned
> exceed the reasonable resources required in bandwidth, cpu, even if
> we never wasted memory.
> 

Right now, all adjacent overlaps are merged, and it is
trivial to add counting the number of merges done (will
add soonish) as well as the number of "direction changes"
(100-200,20-30 for eg)…

We can then place limits on them, expose/log them, etc...

Re: Fixing Ranges

[Dirk-Willem van Gulik]

On 25 Aug 2011, at 15:48, Plüm, Rüdiger, VF-Group wrote:

> +1 for 2.3, -0 for 2.2. I guess for 2.2 we should only detect "misuse" (the 
> definition of misuse
> needs to configurable) and reply with a 200 if misuse is detected.

Ok - given the patch a good test - and actually - am not sure we need even that 
(much) abuse detection. 

I find it darn hard to kill the server now; and would almost say that we can 
leave it as is. And PERHAPS have an optional cap on the number of ranges (Set 
at unlimited by default -leaving it to LimitRequestFieldSize to cap it off at 
effectively some 1200-1500).

Thanks

Dw

Re: Fixing Ranges

[Dirk-Willem van Gulik]

On 25 Aug 2011, at 17:45, Greg Ames wrote:

> On Thu, Aug 25, 2011 at 10:25 AM, Jim Jagielski  wrote:
> Now that the memory utilz is being fixed, we need to determine
> what sort of usage we want to allow… I'm guessing that people
> are ok with http://trac.tools.ietf.org/wg/httpbis/trac/ticket/311
> as the guiding spec?
> 
> I'm no longer convinced that we *need* to merge/optimize the Range header.  
> Stefan's fix to the brigade plumbing has converted O(N^2) memory + CPU use 
> into something scalable.  

Same feeling here. BUT that is based on the FreeBSD platform I care about. And 
we have noticed earlier that Ubuntu (which its default commit pattern in the 
vm) behaves very differently. 

So is it fair to assume this reasoning holds across the board -- or should we 
get some very explicit +1's on this appraoch from key linux, windows and what 
not users ?

Dw

Re: Fixing Ranges

[Tim Bannister]

On 25 Aug 2011, at 15:48, Plüm, Rüdiger, VF-Group wrote:

> For 2.3 the last one could be 3 state:
> 
> off - Don't do anything about that
> on - reply with 200 if misuse is detected.
> optimize - Do sorts and merges and fill too small chunks between the ranges.
> 
> Default for 2.3 would be optimize.

I don't know exactly how the PDF plugins work, but we might expect requests 
like:

HEAD /foo HTTP/1.1
Host: xxx.example

to learn the content length, followed by:

GET /foo HTTP/1.1
Host: xxx.example
If-Range: "bar"
Range: bytes=0-4095,8384511-8388607,4096-8384510,8384512-

(hoping to read the indexes at the start and end of the document first, then 
fill in the rest).


A default that forces the clients back to seeing only the whole entity seems 
too strong, especially if httpd will now have better code to handle this case. 
Detecting misuse and handling that with a 200 still fine though.

I expect that clients exist which would get confused at having small chunks 
filled in.
For example, a client that expects either a multipart/byte-ranges response or a 
whole-entity 200 (because the server doesn't accept ranges). With the above 
“optimize”, the client instead gets a sorted and merged single-range response. 
Naive coding could have the client believe that it is seeing the whole entity 
rather than just a range.

…yes, such a client is badly written but badly written clients can and do 
exist. If httpd punishes their users unduly, httpd itself may attract some 
blame.

-- 
Tim Bannister – is...@jellybaby.net

Re: Fixing Ranges

[Jim Jagielski]

On Aug 25, 2011, at 2:27 PM, Dirk-Willem van Gulik wrote:

> 
> On 25 Aug 2011, at 17:45, Greg Ames wrote:
> 
>> On Thu, Aug 25, 2011 at 10:25 AM, Jim Jagielski  wrote:
>> Now that the memory utilz is being fixed, we need to determine
>> what sort of usage we want to allow… I'm guessing that people
>> are ok with http://trac.tools.ietf.org/wg/httpbis/trac/ticket/311
>> as the guiding spec?
>> 
>> I'm no longer convinced that we *need* to merge/optimize the Range header.  
>> Stefan's fix to the brigade plumbing has converted O(N^2) memory + CPU use 
>> into something scalable.  
> 
> Same feeling here. BUT that is based on the FreeBSD platform I care about. 
> And we have noticed earlier that Ubuntu (which its default commit pattern in 
> the vm) behaves very differently. 
> 
> So is it fair to assume this reasoning holds across the board -- or should we 
> get some very explicit +1's on this appraoch from key linux, windows and what 
> not users ?
> 

I just need to create and connect some runtime config directives
for the Range stuff and I think we should be mostly complete ;)

Re: Fixing Ranges

[Jim Jagielski]

For us to be able to control the number of overlaps, ranges,
etc will require an API bump to add an entry to server_rec.

Are we sure we want to do that for 2.2 or save that for trunk?

On Aug 25, 2011, at 3:12 PM, Jim Jagielski wrote:
> 
> I just need to create and connect some runtime config directives
> for the Range stuff and I think we should be mostly complete ;)
> 

Re: Fixing Ranges

[William A. Rowe Jr.]

On 8/25/2011 3:05 PM, Jim Jagielski wrote:
> For us to be able to control the number of overlaps, ranges,
> etc will require an API bump to add an entry to server_rec.
> 
> Are we sure we want to do that for 2.2 or save that for trunk?

Let's -not- overload server_rec.

First, it's per-dir... it would be entirely sensible for us to
allow backwards-broken clients to access particular sorts of docs
in bizzaro ways (.pdf for example), denying stupid ranges on all
other documents (particularly generated/proxied content).

And there are probably going to be few overrides... set it up
globally and forget it, except for the edge cases.

But I suggest instead of abusing core config, let's create one
config section for byterange, which will not break binary ABI,
and should be infrequently merged.

Re: Fixing Ranges

[Jim Jagielski]

Using stef's byterange4 test, I'm seeing:

apr_brigade_length (bb=0x7feb00a23200, read_all=1, length=0x7fff6e03e8b0) at 
apr_brigade.c:201
201 if (bkt->length == (apr_size_t)(-1)) {
(gdb) where
#0  apr_brigade_length (bb=0x7feb00a23200, read_all=1, length=0x7fff6e03e8b0) 
at apr_brigade.c:201
#1  0x00010e500851 in copy_brigade_range (bb=0x7feb00a24d90, 
bbout=0x7feb00a23200, start=0, end=200) at byterange_filter.c:306
#2  0x00010e500d1b in ap_byterange_filter (f=0x7feb00a291b0, 
bb=0x7feb00a24d90) at byterange_filter.c:401
#3  0x00010e46a67e in ap_pass_brigade (next=0x7feb00a291b0, 
bb=0x7feb00a24d90) at util_filter.c:533
#4  0x00010e556681 in session_output_filter (f=0x7feb00a24a98, 
in=0x7feb00a24d90) at mod_session.c:453
#5  0x00010e46a67e in ap_pass_brigade (next=0x7feb00a24a98, 
bb=0x7feb00a24d90) at util_filter.c:533
#6  0x00010e4cb387 in bucketeer_out_filter (f=0x7feb00a24ad0, 
bb=0x7feb00a24d48) at mod_bucketeer.c:98
#7  0x00010e46a67e in ap_pass_brigade (next=0x7feb00a24ad0, 
bb=0x7feb00a24d48) at util_filter.c:533
#8  0x00010e47e36f in default_handler (r=0x7feb00a27ea0) at core.c:4208

We seem to be spinning at:

AP_DEBUG_ASSERT(APR_SUCCESS == apr_brigade_length(bbout, 1, &pofft));

Cannot recreate in the real world...

Re: Fixing Ranges

[Roy T. Fielding]

On Aug 25, 2011, at 2:02 PM, Jim Jagielski wrote:

> Using stef's byterange4 test, I'm seeing:
> 
> apr_brigade_length (bb=0x7feb00a23200, read_all=1, length=0x7fff6e03e8b0) at 
> apr_brigade.c:201
> 201   if (bkt->length == (apr_size_t)(-1)) {

apr_size_t is unsigned.  That's borked.

Roy

Re: Fixing Ranges

[Stefan Fritsch]

On Thursday 25 August 2011, Roy T. Fielding wrote:
> On Aug 25, 2011, at 2:02 PM, Jim Jagielski wrote:
> > Using stef's byterange4 test, I'm seeing:
> > 
> > apr_brigade_length (bb=0x7feb00a23200, read_all=1,
> > length=0x7fff6e03e8b0) at apr_brigade.c:201 201 if
> > (bkt->length == (apr_size_t)(-1)) {
> 
> apr_size_t is unsigned.  That's borked.

Still, that's how it's implemented in apr-util:

/** The length of the data in the bucket.  This could have been 
implemented
 *  with a function, but this is an optimization, because the most
 *  common thing to do will be to get the length.  If the length 
is unknown,
 *  the value of this field will be (apr_size_t)(-1).
 */
apr_size_t length;

Maybe it should actually be APR_SIZE_T_MAX...

Re: Fixing Ranges

[Stefan Fritsch]

On Thursday 25 August 2011, Jim Jagielski wrote:
> We seem to be spinning at:
> 
>   AP_DEBUG_ASSERT(APR_SUCCESS == apr_brigade_length(bbout, 1,
> &pofft));
> 
> Cannot recreate in the real world...

I have managed to fix that one. The key to recreating is having 
mod_bucketeer configured and requesting 
t/htdocs/apache/chunked/byteranges.txt.

But there are still more failures in byterange4.t. Yesterday's trunk 
passes, so these are new bugs, too. Investigating.

Re: Fixing Ranges

[William A. Rowe Jr.]

On 8/25/2011 1:27 PM, Dirk-Willem van Gulik wrote:
> 
> On 25 Aug 2011, at 17:45, Greg Ames wrote:
> 
>> On Thu, Aug 25, 2011 at 10:25 AM, Jim Jagielski  wrote:
>> Now that the memory utilz is being fixed, we need to determine
>> what sort of usage we want to allow… I'm guessing that people
>> are ok with http://trac.tools.ietf.org/wg/httpbis/trac/ticket/311
>> as the guiding spec?
>>
>> I'm no longer convinced that we *need* to merge/optimize the Range header.  
>> Stefan's fix to the brigade plumbing has converted O(N^2) memory + CPU use 
>> into something scalable.  
> 
> Same feeling here. BUT that is based on the FreeBSD platform I care about. 
> And we have noticed earlier that Ubuntu (which its default commit pattern in 
> the vm) behaves very differently. 
> 
> So is it fair to assume this reasoning holds across the board -- or should we 
> get some very explicit +1's on this appraoch from key linux, windows and what 
> not users ?

I'm convinced we must do both, inhibit all redundant range requests,
and coalesce ranges as illustrated by the spec, particularly on the
assumption that any redundant ranges are likely malicious.  And due
to the memory consumption, rewinding should simply be eliminated.
The user agent is always free to pipeline multiple requests for
specific subranges.

At this point, should we publish the most conservative flavor of our
provisional patch *** with a pointer to a specific page on our wiki ***
so that we can collect feedback of any clients/applications which are
impacted by the most conservative patch?

That will help us not only skip coding bypass options for things which
apparently need to bypass, but guide users in applying those options.

The wiki page/patch could even offer suggestions on disabling certain
restrictions (e.g. ALLOW_BYTERANGE_REWIND) which can later be turned
into configuration flags.

I'd suggest getting something into compiler-literate administrators'
hands beats some rush to a fragile/unstable/incomplete 2.2.20.