Merge "Reject overly-taxing ranged-GET requests"

4 files changed, 126 insertions, 8 deletions

diff --git a/swift/common/swob.py b/swift/common/swob.py
index c83856f95..d8281d210 100644
--- a/swift/common/swob.py
+++ b/swift/common/swob.py
@@ -49,7 +49,7 @@ import random
 import functools
 import inspect
 
-from swift.common.utils import reiterate, split_path, Timestamp
+from swift.common.utils import reiterate, split_path, Timestamp, pairs
 from swift.common.exceptions import InvalidTimestamp
 
 
@@ -110,6 +110,10 @@ RESPONSE_REASONS = {
           'resource. Drive: %(drive)s'),
 }
 
+MAX_RANGE_OVERLAPS = 2
+MAX_NONASCENDING_RANGES = 8
+MAX_RANGES = 50
+
 
 class _UTC(tzinfo):
     """
@@ -584,6 +588,43 @@ class Range(object):
                 # the total length of the content
                 all_ranges.append((begin, min(end + 1, length)))
 
+        # RFC 7233 section 6.1 ("Denial-of-Service Attacks Using Range") says:
+        #
+        # Unconstrained multiple range requests are susceptible to denial-of-
+        # service attacks because the effort required to request many
+        # overlapping ranges of the same data is tiny compared to the time,
+        # memory, and bandwidth consumed by attempting to serve the requested
+        # data in many parts.  Servers ought to ignore, coalesce, or reject
+        # egregious range requests, such as requests for more than two
+        # overlapping ranges or for many small ranges in a single set,
+        # particularly when the ranges are requested out of order for no
+        # apparent reason.  Multipart range requests are not designed to
+        # support random access.
+        #
+        # We're defining "egregious" here as:
+        #
+        # * more than 100 requested ranges OR
+        # * more than 2 overlapping ranges OR
+        # * more than 8 non-ascending-order ranges
+        if len(all_ranges) > MAX_RANGES:
+            return []
+
+        overlaps = 0
+        for ((start1, end1), (start2, end2)) in pairs(all_ranges):
+            if ((start1 < start2 < end1) or (start1 < end2 < end1) or
+               (start2 < start1 < end2) or (start2 < end1 < end2)):
+                overlaps += 1
+                if overlaps > MAX_RANGE_OVERLAPS:
+                    return []
+
+        ascending = True
+        for start1, start2 in zip(all_ranges, all_ranges[1:]):
+            if start1 > start2:
+                ascending = False
+                break
+        if not ascending and len(all_ranges) >= MAX_NONASCENDING_RANGES:
+            return []
+
         return all_ranges
 
 
diff --git a/swift/common/utils.py b/swift/common/utils.py
index e37dc34c6..4a7c2075b 100644
--- a/swift/common/utils.py
+++ b/swift/common/utils.py
@@ -2424,6 +2424,17 @@ def streq_const_time(s1, s2):
     return result == 0
 
 
+def pairs(item_list):
+    """
+    Returns an iterator of all pairs of elements from item_list.
+
+    :param items: items (no duplicates allowed)
+    """
+    for i, item1 in enumerate(item_list):
+        for item2 in item_list[(i + 1):]:
+            yield (item1, item2)
+
+
 def replication(func):
     """
     Decorator to declare which methods are accessible for different
diff --git a/test/unit/common/test_swob.py b/test/unit/common/test_swob.py
index 7a070b188..7df039103 100644
--- a/test/unit/common/test_swob.py
+++ b/test/unit/common/test_swob.py
@@ -179,17 +179,21 @@ class TestRange(unittest.TestCase):
         self.assertEquals(range.ranges_for_length(5), [(4, 5), (0, 5)])
 
     def test_ranges_for_length_multi(self):
-        range = swift.common.swob.Range('bytes=-20,4-,30-150,-10')
-        # the length of the ranges should be 4
-        self.assertEquals(len(range.ranges_for_length(200)), 4)
+        range = swift.common.swob.Range('bytes=-20,4-')
+        self.assertEquals(len(range.ranges_for_length(200)), 2)
 
-        # the actual length less than any of the range
-        self.assertEquals(range.ranges_for_length(90),
-                          [(70, 90), (4, 90), (30, 90), (80, 90)])
+        # the actual length greater than each range element
+        self.assertEquals(range.ranges_for_length(200), [(180, 200), (4, 200)])
+
+        range = swift.common.swob.Range('bytes=30-150,-10')
+        self.assertEquals(len(range.ranges_for_length(200)), 2)
+
+        # the actual length lands in the middle of a range
+        self.assertEquals(range.ranges_for_length(90), [(30, 90), (80, 90)])
 
         # the actual length greater than any of the range
         self.assertEquals(range.ranges_for_length(200),
-                          [(180, 200), (4, 200), (30, 151), (190, 200)])
+                          [(30, 151), (190, 200)])
 
         self.assertEquals(range.ranges_for_length(None), None)
 
@@ -206,6 +210,56 @@ class TestRange(unittest.TestCase):
         self.assertEquals(range.ranges_for_length(5),
                           [(0, 5), (0, 2)])
 
+    def test_ranges_for_length_overlapping(self):
+        # Fewer than 3 overlaps is okay
+        range = swift.common.swob.Range('bytes=10-19,15-24')
+        self.assertEquals(range.ranges_for_length(100),
+                          [(10, 20), (15, 25)])
+        range = swift.common.swob.Range('bytes=10-19,15-24,20-29')
+        self.assertEquals(range.ranges_for_length(100),
+                          [(10, 20), (15, 25), (20, 30)])
+
+        # Adjacent ranges, though suboptimal, don't overlap
+        range = swift.common.swob.Range('bytes=10-19,20-29,30-39')
+        self.assertEquals(range.ranges_for_length(100),
+                          [(10, 20), (20, 30), (30, 40)])
+
+        # Ranges that share a byte do overlap
+        range = swift.common.swob.Range('bytes=10-20,20-30,30-40,40-50')
+        self.assertEquals(range.ranges_for_length(100), [])
+
+        # With suffix byte range specs (e.g. bytes=-2), make sure that we
+        # correctly determine overlapping-ness based on the entity length
+        range = swift.common.swob.Range('bytes=10-15,15-20,30-39,-9')
+        self.assertEquals(range.ranges_for_length(100),
+                          [(10, 16), (15, 21), (30, 40), (91, 100)])
+        self.assertEquals(range.ranges_for_length(20), [])
+
+    def test_ranges_for_length_nonascending(self):
+        few_ranges = ("bytes=100-109,200-209,300-309,500-509,"
+                      "400-409,600-609,700-709")
+        many_ranges = few_ranges + ",800-809"
+
+        range = swift.common.swob.Range(few_ranges)
+        self.assertEquals(range.ranges_for_length(100000),
+                          [(100, 110), (200, 210), (300, 310), (500, 510),
+                           (400, 410), (600, 610), (700, 710)])
+
+        range = swift.common.swob.Range(many_ranges)
+        self.assertEquals(range.ranges_for_length(100000), [])
+
+    def test_ranges_for_length_too_many(self):
+        at_the_limit_ranges = (
+            "bytes=" + ",".join("%d-%d" % (x * 1000, x * 1000 + 10)
+                                for x in range(50)))
+        too_many_ranges = at_the_limit_ranges + ",10000000-10000009"
+
+        rng = swift.common.swob.Range(at_the_limit_ranges)
+        self.assertEquals(len(rng.ranges_for_length(1000000000)), 50)
+
+        rng = swift.common.swob.Range(too_many_ranges)
+        self.assertEquals(rng.ranges_for_length(1000000000), [])
+
     def test_range_invalid_syntax(self):
 
         def _check_invalid_range(range_value):
diff --git a/test/unit/common/test_utils.py b/test/unit/common/test_utils.py
index 6f91477d4..a60f1420d 100644
--- a/test/unit/common/test_utils.py
+++ b/test/unit/common/test_utils.py
@@ -4329,5 +4329,17 @@ class TestIterMultipartMimeDocuments(unittest.TestCase):
         self.assertTrue(exc is not None)
 
 
+class TestPairs(unittest.TestCase):
+    def test_pairs(self):
+        items = [10, 20, 30, 40, 50, 60]
+        got_pairs = set(utils.pairs(items))
+        self.assertEqual(got_pairs,
+                         set([(10, 20), (10, 30), (10, 40), (10, 50), (10, 60),
+                              (20, 30), (20, 40), (20, 50), (20, 60),
+                              (30, 40), (30, 50), (30, 60),
+                              (40, 50), (40, 60),
+                              (50, 60)]))
+
+
 if __name__ == '__main__':
     unittest.main()