FAILURE MAP
← Case archive

FA-27551 / HTTP ranges / Open access

A range-set guard limits amplification before serving resolved byte ranges: overlap detection sweeps ranges in start order rather than request order · case 01

A range-set guard limits amplification before serving resolved byte ranges: overlap detection sweeps ranges in start order rather than request order.

Verified by executionVariant 1 · 19 checks per implementationDownload source bundle ↓JSON ↗

ROOT CAUSE

The range-abuse-guard-overlap-sorted-sweep decision uses L=x['length'] rs=x['ranges'] if not rs: return ['full',None] if len(rs)>x['max_ranges']: return ['full',None] total=0 for a,b in rs: total+=b-a+1 if total>2*L: return ['full',None] if sum(1 for a,b in rs if b-a+1<x['min_span'])>x['max_tiny']: return ['full',None] order=rs overlaps=0 end=-1 for a,b in order: if a<=end: overlaps+=1 end=max(end,b) if overlaps>x['max_overlaps']: return ['full',None] disorder=0 for i in range(1,len(rs)): if rs[i][0]<rs[i-1][0]: disorder+=1 if overlaps==0 and disorder<=x['max_disorder']: return ['ranges',[list(r) for r in rs]] merged=[] for lo,hi in order: if merged and lo<=merged[-1][1]+1: merged[-1][1]=max(merged[-1][1],hi) else: merged.append([lo,hi]) return ['ranges',merged].

THE FAILURE

The range-abuse-guard-overlap-sorted-sweep decision uses L=x['length'] rs=x['ranges'] if not rs: return ['full',None] if len(rs)>x['max_ranges']: return ['full',None] total=0 for a,b in rs: total+=b-a+1 if total>2*L: return ['full',None] if sum(1 for a,b in rs if b-a+1<x['min_span'])>x['max_tiny']: return ['full',None] order=rs overlaps=0 end=-1 for a,b in order: if a<=end: overlaps+=1 end=max(end,b) if overlaps>x['max_overlaps']: return ['full',None] disorder=0 for i in range(1,len(rs)): if rs[i][0]<rs[i-1][0]: disorder+=1 if overlaps==0 and disorder<=x['max_disorder']: return ['ranges',[list(r) for r in rs]] merged=[] for lo,hi in order: if merged and lo<=merged[-1][1]+1: merged[-1][1]=max(merged[-1][1],hi) else: merged.append([lo,hi]) return ['ranges',merged].

Unsuccessful approach: The partial repair uses L=x['length'] rs=x['ranges'] if not rs: return ['full',None] if len(rs)>x['max_ranges']: return ['full',None] total=0 for a,b in rs: total+=b-a+1 if total>2*L: return ['full',None] if sum(1 for a,b in rs if b-a+1<x['min_span'])>x['max_tiny']: return ['full',None] order=sorted(rs,key=lambda r:r[1]) overlaps=0 end=-1 for a,b in order: if a<=end: overlaps+=1 end=max(end,b) if overlaps>x['max_overlaps']: return ['full',None] disorder=0 for i in range(1,len(rs)): if rs[i][0]<rs[i-1][0]: disorder+=1 if overlaps==0 and disorder<=x['max_disorder']: return ['ranges',[list(r) for r in rs]] merged=[] for lo,hi in order: if merged and lo<=merged[-1][1]+1: merged[-1][1]=max(merged[-1][1],hi) else: merged.append([lo,hi]) return ['ranges',merged], which still violates the stated contract.

Case contract

x holds a representation length, already resolved satisfiable inclusive ranges in request order, and local policy limits. Serve ["full",null] for an empty list, more than max_ranges members, requested byte sum above twice the length (duplicates count every time), more than max_tiny members shorter than min_span, or more than max_overlaps overlaps. Overlaps are counted by a sweep over start-sorted ranges against the running maximum end; adjacent ranges do not overlap. Inversions count request neighbors whose start decreases. Without overlaps and with inversions within max_disorder, return ["ranges",request-order ranges]; otherwise return ["ranges",start-sorted ranges with overlapping or adjacent members coalesced].

Why this case matters

Range responses combine representation identity, conditional requests, framing, and partial-object state.

1 / The failure

Exit 1
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(x):
    L=x['length']
    rs=x['ranges']
    if not rs: return ['full',None]
    if len(rs)>x['max_ranges']: return ['full',None]
    total=0
    for a,b in rs:
        total+=b-a+1
    if total>2*L: return ['full',None]
    if sum(1 for a,b in rs if b-a+1<x['min_span'])>x['max_tiny']: return ['full',None]
    order=rs
    overlaps=0
    end=-1
    for a,b in order:
        if a<=end: overlaps+=1
        end=max(end,b)
    if overlaps>x['max_overlaps']: return ['full',None]
    disorder=0
    for i in range(1,len(rs)):
        if rs[i][0]<rs[i-1][0]: disorder+=1
    if overlaps==0 and disorder<=x['max_disorder']: return ['ranges',[list(r) for r in rs]]
    merged=[]
    for lo,hi in order:
        if merged and lo<=merged[-1][1]+1:
            merged[-1][1]=max(merged[-1][1],hi)
        else:
            merged.append([lo,hi])
    return ['ranges',merged]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('overlap-sorted-sweep fixture 0', json.loads(json.dumps(solve({'length':100,'max_disorder':1,'max_overlaps':2,'max_ranges':8,'max_tiny':8,'min_span':1,'ranges':[]}))), json.loads(json.dumps(['full',None])))
check('overlap-sorted-sweep fixture 1', json.loads(json.dumps(solve({'length':0,'max_disorder':1,'max_overlaps':2,'max_ranges':8,'max_tiny':8,'min_span':1,'ranges':[]}))), json.loads(json.dumps(['full',None])))
check('overlap-sorted-sweep fixture 2', json.loads(json.dumps(solve({'length':10,'max_disorder':1,'max_overlaps':5,'max_ranges':8,'max_tiny':8,'min_span':1,'ranges':[[0,9],[0,9],[0,9]]}))), json.loads(json.dumps(['full',None])))
check('overlap-sorted-sweep fixture 3', json.loads(json.dumps(solve({'length':100,'max_disorder':1,'max_overlaps':2,'max_ranges':8,'max_tiny':8,'min_span':1,'ranges':[[0,9],[20,29]]}))), json.loads(json.dumps(['ranges',[[0,9],[20,29]]])))
check('overlap-sorted-sweep fixture 4', json.loads(json.dumps(solve({'length':100,'max_disorder':1,'max_overlaps':2,'max_ranges':8,'max_tiny':8,'min_span':1,'ranges':[[50,59],[0,9]]}))), json.loads(json.dumps(['ranges',[[50,59],[0,9]]])))
check('overlap-sorted-sweep fixture 5', json.loads(json.dumps(solve({'length':100,'max_disorder':1,'max_overlaps':2,'max_ranges':8,'max_tiny':8,'min_span':1,'ranges':[[50,59],[20,29],[0,9]]}))), json.loads(json.dumps(['ranges',[[0,9],[20,29],[50,59]]])))
check('overlap-sorted-sweep fixture 6', json.loads(json.dumps(solve({'length':100,'max_disorder':0,'max_overlaps':2,'max_ranges':8,'max_tiny':8,'min_span':1,'ranges':[[10,19],[30,39],[20,29]]}))), json.loads(json.dumps(['ranges',[[10,39]]])))
check('overlap-sorted-sweep fixture 7', json.loads(json.dumps(solve({'length':100,'max_disorder':1,'max_overlaps':2,'max_ranges':8,'max_tiny':8,'min_span':1,'ranges':[[50,59],[20,29],[30,39]]}))), json.loads(json.dumps(['ranges',[[50,59],[20,29],[30,39]]])))
check('overlap-sorted-sweep fixture 8', json.loads(json.dumps(solve({'length':100,'max_disorder':1,'max_overlaps':2,'max_ranges':8,'max_tiny':8,'min_span':1,'ranges':[[0,9],[5,14]]}))), json.loads(json.dumps(['ranges',[[0,14]]])))
check('overlap-sorted-sweep fixture 9', json.loads(json.dumps(solve({'length':100,'max_disorder':1,'max_overlaps':2,'max_ranges':8,'max_tiny':8,'min_span':1,'ranges':[[0,20],[5,9]]}))), json.loads(json.dumps(['ranges',[[0,20]]])))
check('overlap-sorted-sweep fixture 10', json.loads(json.dumps(solve({'length':100,'max_disorder':1,'max_overlaps':2,'max_ranges':8,'max_tiny':8,'min_span':1,'ranges':[[0,9],[1,9],[2,9],[3,9]]}))), json.loads(json.dumps(['full',None])))
check('overlap-sorted-sweep fixture 11', json.loads(json.dumps(solve({'length':100,'max_disorder':1,'max_overlaps':1,'max_ranges':8,'max_tiny':8,'min_span':1,'ranges':[[20,29],[0,5],[40,49],[30,35]]}))), json.loads(json.dumps(['ranges',[[0,5],[20,35],[40,49]]])))
check('overlap-sorted-sweep fixture 12', json.loads(json.dumps(solve({'length':100,'max_disorder':1,'max_overlaps':1,'max_ranges':8,'max_tiny':8,'min_span':1,'ranges':[[0,50],[10,20],[30,40]]}))), json.loads(json.dumps(['full',None])))
check('overlap-sorted-sweep fixture 13', json.loads(json.dumps(solve({'length':100,'max_disorder':1,'max_overlaps':1,'max_ranges':8,'max_tiny':8,'min_span':1,'ranges':[[0,9],[10,19],[20,29]]}))), json.loads(json.dumps(['ranges',[[0,9],[10,19],[20,29]]])))
check('overlap-sorted-sweep fixture 14', json.loads(json.dumps(solve({'length':100,'max_disorder':1,'max_overlaps':0,'max_ranges':8,'max_tiny':8,'min_span':1,'ranges':[[0,9],[9,19]]}))), json.loads(json.dumps(['full',None])))
check('overlap-sorted-sweep fixture 15', json.loads(json.dumps(solve({'length':100,'max_disorder':1,'max_overlaps':2,'max_ranges':8,'max_tiny':1,'min_span':4,'ranges':[[0,0],[10,10],[20,29]]}))), json.loads(json.dumps(['full',None])))
check('overlap-sorted-sweep fixture 16', json.loads(json.dumps(solve({'length':100,'max_disorder':1,'max_overlaps':2,'max_ranges':8,'max_tiny':8,'min_span':1,'ranges':[[0,1],[10,11],[20,21],[30,31],[40,41],[50,51],[60,61],[70,71],[80,81]]}))), json.loads(json.dumps(['full',None])))
check('overlap-sorted-sweep fixture 17', json.loads(json.dumps(solve({'length':10*N,'max_disorder':1,'max_overlaps':2,'max_ranges':8,'max_tiny':8,'min_span':1,'ranges':[[0,N-1],[N,2*N-1]]}))), json.loads(json.dumps(['ranges',[[0,N-1],[N,2*N-1]]])))
check('overlap-sorted-sweep fixture 18', json.loads(json.dumps(solve({'length':5*N+1,'max_disorder':1,'max_overlaps':2,'max_ranges':8,'max_tiny':8,'min_span':1,'ranges':[[0,5*N],[0,5*N]]}))), json.loads(json.dumps(['ranges',[[0,5*N]]])))
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
Boundary fixtureActualExpectedOutcome
overlap-sorted-sweep fixture 0['full', None]['full', None]Passed
overlap-sorted-sweep fixture 1['full', None]['full', None]Passed
overlap-sorted-sweep fixture 2['full', None]['full', None]Passed
overlap-sorted-sweep fixture 3['ranges', [[0, 9], [20, 29]]]['ranges', [[0, 9], [20, 29]]]Passed
overlap-sorted-sweep fixture 4['ranges', [[50, 59]]]['ranges', [[50, 59], [0, 9]]]Failed
overlap-sorted-sweep fixture 5['ranges', [[50, 59]]]['ranges', [[0, 9], [20, 29], [50, 59]]]Failed
overlap-sorted-sweep fixture 6['ranges', [[10, 19], [30, 39]]]['ranges', [[10, 39]]]Failed
overlap-sorted-sweep fixture 7['ranges', [[50, 59]]]['ranges', [[50, 59], [20, 29], [30, 39]]]Failed
overlap-sorted-sweep fixture 8['ranges', [[0, 14]]]['ranges', [[0, 14]]]Passed
overlap-sorted-sweep fixture 9['ranges', [[0, 20]]]['ranges', [[0, 20]]]Passed
overlap-sorted-sweep fixture 10['full', None]['full', None]Passed
overlap-sorted-sweep fixture 11['full', None]['ranges', [[0, 5], [20, 35], [40, 49]]]Failed
overlap-sorted-sweep fixture 12['full', None]['full', None]Passed
overlap-sorted-sweep fixture 13['ranges', [[0, 9], [10, 19], [20, 29]]]['ranges', [[0, 9], [10, 19], [20, 29]]]Passed
overlap-sorted-sweep fixture 14['full', None]['full', None]Passed
overlap-sorted-sweep fixture 15['full', None]['full', None]Passed
overlap-sorted-sweep fixture 16['full', None]['full', None]Passed
overlap-sorted-sweep fixture 17['ranges', [[0, 0], [1, 1]]]['ranges', [[0, 0], [1, 1]]]Passed
overlap-sorted-sweep fixture 18['ranges', [[0, 5]]]['ranges', [[0, 5]]]Passed

SHA-256 / efd63c364eed908acd127790e82c6c0a9bd39ef29517b8e840f7c86b6e571b3a

2 / The unsuccessful fix

Exit 1
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(x):
    L=x['length']
    rs=x['ranges']
    if not rs: return ['full',None]
    if len(rs)>x['max_ranges']: return ['full',None]
    total=0
    for a,b in rs:
        total+=b-a+1
    if total>2*L: return ['full',None]
    if sum(1 for a,b in rs if b-a+1<x['min_span'])>x['max_tiny']: return ['full',None]
    order=sorted(rs,key=lambda r:r[1])
    overlaps=0
    end=-1
    for a,b in order:
        if a<=end: overlaps+=1
        end=max(end,b)
    if overlaps>x['max_overlaps']: return ['full',None]
    disorder=0
    for i in range(1,len(rs)):
        if rs[i][0]<rs[i-1][0]: disorder+=1
    if overlaps==0 and disorder<=x['max_disorder']: return ['ranges',[list(r) for r in rs]]
    merged=[]
    for lo,hi in order:
        if merged and lo<=merged[-1][1]+1:
            merged[-1][1]=max(merged[-1][1],hi)
        else:
            merged.append([lo,hi])
    return ['ranges',merged]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('overlap-sorted-sweep fixture 0', json.loads(json.dumps(solve({'length':100,'max_disorder':1,'max_overlaps':2,'max_ranges':8,'max_tiny':8,'min_span':1,'ranges':[]}))), json.loads(json.dumps(['full',None])))
check('overlap-sorted-sweep fixture 1', json.loads(json.dumps(solve({'length':0,'max_disorder':1,'max_overlaps':2,'max_ranges':8,'max_tiny':8,'min_span':1,'ranges':[]}))), json.loads(json.dumps(['full',None])))
check('overlap-sorted-sweep fixture 2', json.loads(json.dumps(solve({'length':10,'max_disorder':1,'max_overlaps':5,'max_ranges':8,'max_tiny':8,'min_span':1,'ranges':[[0,9],[0,9],[0,9]]}))), json.loads(json.dumps(['full',None])))
check('overlap-sorted-sweep fixture 3', json.loads(json.dumps(solve({'length':100,'max_disorder':1,'max_overlaps':2,'max_ranges':8,'max_tiny':8,'min_span':1,'ranges':[[0,9],[20,29]]}))), json.loads(json.dumps(['ranges',[[0,9],[20,29]]])))
check('overlap-sorted-sweep fixture 4', json.loads(json.dumps(solve({'length':100,'max_disorder':1,'max_overlaps':2,'max_ranges':8,'max_tiny':8,'min_span':1,'ranges':[[50,59],[0,9]]}))), json.loads(json.dumps(['ranges',[[50,59],[0,9]]])))
check('overlap-sorted-sweep fixture 5', json.loads(json.dumps(solve({'length':100,'max_disorder':1,'max_overlaps':2,'max_ranges':8,'max_tiny':8,'min_span':1,'ranges':[[50,59],[20,29],[0,9]]}))), json.loads(json.dumps(['ranges',[[0,9],[20,29],[50,59]]])))
check('overlap-sorted-sweep fixture 6', json.loads(json.dumps(solve({'length':100,'max_disorder':0,'max_overlaps':2,'max_ranges':8,'max_tiny':8,'min_span':1,'ranges':[[10,19],[30,39],[20,29]]}))), json.loads(json.dumps(['ranges',[[10,39]]])))
check('overlap-sorted-sweep fixture 7', json.loads(json.dumps(solve({'length':100,'max_disorder':1,'max_overlaps':2,'max_ranges':8,'max_tiny':8,'min_span':1,'ranges':[[50,59],[20,29],[30,39]]}))), json.loads(json.dumps(['ranges',[[50,59],[20,29],[30,39]]])))
check('overlap-sorted-sweep fixture 8', json.loads(json.dumps(solve({'length':100,'max_disorder':1,'max_overlaps':2,'max_ranges':8,'max_tiny':8,'min_span':1,'ranges':[[0,9],[5,14]]}))), json.loads(json.dumps(['ranges',[[0,14]]])))
check('overlap-sorted-sweep fixture 9', json.loads(json.dumps(solve({'length':100,'max_disorder':1,'max_overlaps':2,'max_ranges':8,'max_tiny':8,'min_span':1,'ranges':[[0,20],[5,9]]}))), json.loads(json.dumps(['ranges',[[0,20]]])))
check('overlap-sorted-sweep fixture 10', json.loads(json.dumps(solve({'length':100,'max_disorder':1,'max_overlaps':2,'max_ranges':8,'max_tiny':8,'min_span':1,'ranges':[[0,9],[1,9],[2,9],[3,9]]}))), json.loads(json.dumps(['full',None])))
check('overlap-sorted-sweep fixture 11', json.loads(json.dumps(solve({'length':100,'max_disorder':1,'max_overlaps':1,'max_ranges':8,'max_tiny':8,'min_span':1,'ranges':[[20,29],[0,5],[40,49],[30,35]]}))), json.loads(json.dumps(['ranges',[[0,5],[20,35],[40,49]]])))
check('overlap-sorted-sweep fixture 12', json.loads(json.dumps(solve({'length':100,'max_disorder':1,'max_overlaps':1,'max_ranges':8,'max_tiny':8,'min_span':1,'ranges':[[0,50],[10,20],[30,40]]}))), json.loads(json.dumps(['full',None])))
check('overlap-sorted-sweep fixture 13', json.loads(json.dumps(solve({'length':100,'max_disorder':1,'max_overlaps':1,'max_ranges':8,'max_tiny':8,'min_span':1,'ranges':[[0,9],[10,19],[20,29]]}))), json.loads(json.dumps(['ranges',[[0,9],[10,19],[20,29]]])))
check('overlap-sorted-sweep fixture 14', json.loads(json.dumps(solve({'length':100,'max_disorder':1,'max_overlaps':0,'max_ranges':8,'max_tiny':8,'min_span':1,'ranges':[[0,9],[9,19]]}))), json.loads(json.dumps(['full',None])))
check('overlap-sorted-sweep fixture 15', json.loads(json.dumps(solve({'length':100,'max_disorder':1,'max_overlaps':2,'max_ranges':8,'max_tiny':1,'min_span':4,'ranges':[[0,0],[10,10],[20,29]]}))), json.loads(json.dumps(['full',None])))
check('overlap-sorted-sweep fixture 16', json.loads(json.dumps(solve({'length':100,'max_disorder':1,'max_overlaps':2,'max_ranges':8,'max_tiny':8,'min_span':1,'ranges':[[0,1],[10,11],[20,21],[30,31],[40,41],[50,51],[60,61],[70,71],[80,81]]}))), json.loads(json.dumps(['full',None])))
check('overlap-sorted-sweep fixture 17', json.loads(json.dumps(solve({'length':10*N,'max_disorder':1,'max_overlaps':2,'max_ranges':8,'max_tiny':8,'min_span':1,'ranges':[[0,N-1],[N,2*N-1]]}))), json.loads(json.dumps(['ranges',[[0,N-1],[N,2*N-1]]])))
check('overlap-sorted-sweep fixture 18', json.loads(json.dumps(solve({'length':5*N+1,'max_disorder':1,'max_overlaps':2,'max_ranges':8,'max_tiny':8,'min_span':1,'ranges':[[0,5*N],[0,5*N]]}))), json.loads(json.dumps(['ranges',[[0,5*N]]])))
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
Boundary fixtureActualExpectedOutcome
overlap-sorted-sweep fixture 0['full', None]['full', None]Passed
overlap-sorted-sweep fixture 1['full', None]['full', None]Passed
overlap-sorted-sweep fixture 2['full', None]['full', None]Passed
overlap-sorted-sweep fixture 3['ranges', [[0, 9], [20, 29]]]['ranges', [[0, 9], [20, 29]]]Passed
overlap-sorted-sweep fixture 4['ranges', [[50, 59], [0, 9]]]['ranges', [[50, 59], [0, 9]]]Passed
overlap-sorted-sweep fixture 5['ranges', [[0, 9], [20, 29], [50, 59]]]['ranges', [[0, 9], [20, 29], [50, 59]]]Passed
overlap-sorted-sweep fixture 6['ranges', [[10, 39]]]['ranges', [[10, 39]]]Passed
overlap-sorted-sweep fixture 7['ranges', [[50, 59], [20, 29], [30, 39]]]['ranges', [[50, 59], [20, 29], [30, 39]]]Passed
overlap-sorted-sweep fixture 8['ranges', [[0, 14]]]['ranges', [[0, 14]]]Passed
overlap-sorted-sweep fixture 9['ranges', [[5, 20]]]['ranges', [[0, 20]]]Failed
overlap-sorted-sweep fixture 10['full', None]['full', None]Passed
overlap-sorted-sweep fixture 11['ranges', [[0, 5], [20, 35], [40, 49]]]['ranges', [[0, 5], [20, 35], [40, 49]]]Passed
overlap-sorted-sweep fixture 12['ranges', [[10, 20], [30, 50]]]['full', None]Failed
overlap-sorted-sweep fixture 13['ranges', [[0, 9], [10, 19], [20, 29]]]['ranges', [[0, 9], [10, 19], [20, 29]]]Passed
overlap-sorted-sweep fixture 14['full', None]['full', None]Passed
overlap-sorted-sweep fixture 15['full', None]['full', None]Passed
overlap-sorted-sweep fixture 16['full', None]['full', None]Passed
overlap-sorted-sweep fixture 17['ranges', [[0, 0], [1, 1]]]['ranges', [[0, 0], [1, 1]]]Passed
overlap-sorted-sweep fixture 18['ranges', [[0, 5]]]['ranges', [[0, 5]]]Passed

SHA-256 / 88179cc8b3eaffb6a32039a5699199c665e0c6677032ecf4ac84fd001df3bb4f

HELD IN THE MEMBER ARCHIVE

The verified repair and its recorded checks are member-only.

This mechanism has 19 recorded checks per implementation. The open-access tier publishes the failure and the unsuccessful fix; the repaired source that passes every check, and the observations that prove it, are available to members.

Every case sharing this mechanism uses the same contract and the same repair, so this one record is held back for all of them.

Member access is invitation-based. Sign in with your invited account to inspect the repair.

Sign in to the archive ↗

Verification & scope

Deterministic simplified range service, with stipulated local policies and already parsed trusted inputs; not a complete HTTP implementation. This reproducer isolates one failure mechanism. Results cover the supplied fixtures. Variants within a family share a test contract and should remain grouped when constructing evaluation splits. Related mechanisms with a shared evaluation_group must also remain together; these controlled models are not independent production incidents.

Observations recorded using Python 3.12.14 at 2026-09-29T14:41:26.084227+00:00.

Case digest / 5655ae94276beb5dbfceb3e7638f5619d698d2251213d69304ab94a92c6b4b76