FA-73461 / Rate limiter algorithms / Open access
Sliding-window counter approximation: previous window weighted by elapsed time · case 01
Right after a boundary the previous window counts for nothing, allowing a double burst.
ROOT CAUSE
The previous count is weighted by elapsed/W instead of the overlap (W - elapsed)/W.
VERIFIED REPAIR
Weight the previous count by (W - elapsed)/W.
Unsuccessful approach: Weighting the current count instead leaves the previous window fully counted.
Case contract
Input {limit, window_ms, requests [t]} with nondecreasing t. Keep counts for the current and previous epoch windows; moving to the next window rotates cur into prev, skipping more than one window clears both. The estimate is prev * (W - elapsed)/W + cur with elapsed = t - window start, exactly. Allow when est + 1 <= limit (reporting est + 1), else deny (reporting est). Return [[decision, estimate as fraction string]], [window, prev, cur]].
Why this case matters
Edge proxies approximate a rolling window with two counters; the weighting and rotation rules determine whether boundary bursts are smoothed or doubled.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
import math
from fractions import Fraction
N = 1
observations = []
def solve(x):
L = x['limit']
W = x['window_ms']
idx, prev, cur = 0, 0, 0
out = []
for t in x['requests']:
ci = t // W
if ci == idx + 1:
prev, cur = cur, 0
elif ci > idx + 1:
prev, cur = 0, 0
idx = ci
elapsed = t - idx * W
est = prev * Fraction(elapsed, W) + cur
if est + 1 <= L:
cur += 1
out.append(['allow', str(est + 1)])
else:
out.append(['deny', str(est)])
return [out, [idx, prev, cur]]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['previous window weighting',
{'limit': 4, 'requests': [100, 200, 300, 400, 1251, 1500, 1750, 1800], 'window_ms': 1000},
[[['allow', '1'],
['allow', '2'],
['allow', '3'],
['allow', '4'],
['allow', '999/250'],
['allow', '4'],
['allow', '4'],
['deny', '19/5']],
[1, 4, 3]]],
['gap clears history',
{'limit': 3, 'requests': [0, 1, 2, 2601, 2700, 2800, 2900], 'window_ms': 1000},
[[['allow', '1'],
['allow', '2'],
['allow', '3'],
['allow', '1'],
['allow', '2'],
['allow', '3'],
['deny', '3']],
[2, 0, 3]]],
['stale previous after gap',
{'limit': 3, 'requests': [100, 200, 1100, 1200, 3501, 3600, 3700], 'window_ms': 1000},
[[['allow', '1'],
['allow', '2'],
['allow', '14/5'],
['deny', '13/5'],
['allow', '1'],
['allow', '2'],
['allow', '3']],
[3, 0, 3]]],
['fractional estimate boundary',
{'limit': 3, 'requests': [0, 10, 20, 1500, 1601, 1700], 'window_ms': 1000},
[[['allow', '1'],
['allow', '2'],
['allow', '3'],
['allow', '5/2'],
['deny', '2197/1000'],
['allow', '29/10']],
[1, 3, 2]]],
['early in window',
{'limit': 5, 'requests': [0, 50, 100, 150, 200, 401, 410, 420, 800, 801], 'window_ms': 400},
[[['allow', '1'],
['allow', '2'],
['allow', '3'],
['allow', '4'],
['allow', '5'],
['deny', '399/80'],
['deny', '39/8'],
['deny', '19/4'],
['allow', '1'],
['allow', '2']],
[2, 0, 2]]],
['random traffic',
{'limit': 4,
'requests': [762, 1183, 1614, 1772, 2334, 2411, 2425, 2509, 2551, 2560, 2651, 2748, 2860, 2881],
'window_ms': 1000},
[[['allow', '1'],
['allow', '1817/1000'],
['allow', '1193/500'],
['allow', '807/250'],
['allow', '1499/500'],
['allow', '3767/1000'],
['deny', '149/40'],
['deny', '3473/1000'],
['deny', '3347/1000'],
['deny', '83/25'],
['deny', '3047/1000'],
['allow', '939/250'],
['deny', '171/50'],
['deny', '3357/1000']],
[2, 3, 3]]],
['single window',
{'limit': 2, 'requests': [10, 20, 31], 'window_ms': 1000},
[[['allow', '1'], ['allow', '2'], ['deny', '2']], [0, 0, 2]]]],
[['previous window weighting',
{'limit': 4, 'requests': [100, 200, 300, 400, 1252, 1500, 1750, 1800], 'window_ms': 1000},
[[['allow', '1'],
['allow', '2'],
['allow', '3'],
['allow', '4'],
['allow', '499/125'],
['allow', '4'],
['allow', '4'],
['deny', '19/5']],
[1, 4, 3]]],
['gap clears history',
{'limit': 3, 'requests': [0, 1, 2, 2602, 2700, 2800, 2900], 'window_ms': 1000},
[[['allow', '1'],
['allow', '2'],
['allow', '3'],
['allow', '1'],
['allow', '2'],
['allow', '3'],
['deny', '3']],
[2, 0, 3]]],
['stale previous after gap',
{'limit': 3, 'requests': [100, 200, 1100, 1200, 3502, 3600, 3700], 'window_ms': 1000},
[[['allow', '1'],
['allow', '2'],
['allow', '14/5'],
['deny', '13/5'],
['allow', '1'],
['allow', '2'],
['allow', '3']],
[3, 0, 3]]],
['fractional estimate boundary',
{'limit': 3, 'requests': [0, 10, 20, 1500, 1602, 1700], 'window_ms': 1000},
[[['allow', '1'],
['allow', '2'],
['allow', '3'],
['allow', '5/2'],
['deny', '1097/500'],
['allow', '29/10']],
[1, 3, 2]]],
['early in window',
{'limit': 5, 'requests': [0, 50, 100, 150, 200, 402, 410, 420, 800, 801], 'window_ms': 400},
[[['allow', '1'],
['allow', '2'],
['allow', '3'],
['allow', '4'],
['allow', '5'],
['deny', '199/40'],
['deny', '39/8'],
['deny', '19/4'],
['allow', '1'],
['allow', '2']],
[2, 0, 2]]],
['random traffic',
{'limit': 4,
'requests': [2, 284, 685, 716, 946, 1419, 1442, 1550, 1788, 1900, 2219, 2384, 2628, 2704],
'window_ms': 1000},
[[['allow', '1'],
['allow', '2'],
['allow', '3'],
['allow', '4'],
['deny', '4'],
['allow', '831/250'],
['deny', '404/125'],
['allow', '19/5'],
['allow', '481/125'],
['deny', '17/5'],
['allow', '3343/1000'],
['allow', '481/125'],
['deny', '779/250'],
['allow', '486/125']],
[2, 3, 3]]],
['single window',
{'limit': 2, 'requests': [10, 20, 32], 'window_ms': 1000},
[[['allow', '1'], ['allow', '2'], ['deny', '2']], [0, 0, 2]]]],
[['previous window weighting',
{'limit': 4, 'requests': [100, 200, 300, 400, 1253, 1500, 1750, 1800], 'window_ms': 1000},
[[['allow', '1'],
['allow', '2'],
['allow', '3'],
['allow', '4'],
['allow', '997/250'],
['allow', '4'],
['allow', '4'],
['deny', '19/5']],
[1, 4, 3]]],
['gap clears history',
{'limit': 3, 'requests': [0, 1, 2, 2603, 2700, 2800, 2900], 'window_ms': 1000},
[[['allow', '1'],
['allow', '2'],
['allow', '3'],
['allow', '1'],
['allow', '2'],
['allow', '3'],
['deny', '3']],
[2, 0, 3]]],
['stale previous after gap',
{'limit': 3, 'requests': [100, 200, 1100, 1200, 3503, 3600, 3700], 'window_ms': 1000},
[[['allow', '1'],
['allow', '2'],
['allow', '14/5'],
['deny', '13/5'],
['allow', '1'],
['allow', '2'],
['allow', '3']],
[3, 0, 3]]],
['fractional estimate boundary',
{'limit': 3, 'requests': [0, 10, 20, 1500, 1603, 1700], 'window_ms': 1000},
[[['allow', '1'],
['allow', '2'],
['allow', '3'],
['allow', '5/2'],
['deny', '2191/1000'],
['allow', '29/10']],
[1, 3, 2]]],
['early in window',
{'limit': 5, 'requests': [0, 50, 100, 150, 200, 403, 410, 420, 800, 801], 'window_ms': 400},
[[['allow', '1'],
['allow', '2'],
['allow', '3'],
['allow', '4'],
['allow', '5'],
['deny', '397/80'],
['deny', '39/8'],
['deny', '19/4'],
['allow', '1'],
['allow', '2']],
[2, 0, 2]]],
['random traffic',
{'limit': 4,
'requests': [88, 165, 511, 523, 538, 1193, 1202, 1389, 1722, 1826, 2373, 2548, 2774, 2968],
'window_ms': 1000},
[[['allow', '1'],
['allow', '2'],
['allow', '3'],
['allow', '4'],
['deny', '4'],
['deny', '807/250'],
['deny', '399/125'],
['allow', '861/250'],
['allow', '389/125'],
['allow', '462/125'],
['allow', '2881/1000'],
['allow', '839/250'],
['allow', '1839/500'],
['deny', '387/125']],
[2, 3, 3]]],
['single window',
{'limit': 2, 'requests': [10, 20, 33], 'window_ms': 1000},
[[['allow', '1'], ['allow', '2'], ['deny', '2']], [0, 0, 2]]]],
[['previous window weighting',
{'limit': 4, 'requests': [100, 200, 300, 400, 1254, 1500, 1750, 1800], 'window_ms': 1000},
[[['allow', '1'],
['allow', '2'],
['allow', '3'],
['allow', '4'],
['allow', '498/125'],
['allow', '4'],
['allow', '4'],
['deny', '19/5']],
[1, 4, 3]]],
['gap clears history',
{'limit': 3, 'requests': [0, 1, 2, 2604, 2700, 2800, 2900], 'window_ms': 1000},
[[['allow', '1'],
['allow', '2'],
['allow', '3'],
['allow', '1'],
['allow', '2'],
['allow', '3'],
['deny', '3']],
[2, 0, 3]]],
['stale previous after gap',
{'limit': 3, 'requests': [100, 200, 1100, 1200, 3504, 3600, 3700], 'window_ms': 1000},
[[['allow', '1'],
['allow', '2'],
['allow', '14/5'],
['deny', '13/5'],
['allow', '1'],
['allow', '2'],
['allow', '3']],
[3, 0, 3]]],
['fractional estimate boundary',
{'limit': 3, 'requests': [0, 10, 20, 1500, 1604, 1700], 'window_ms': 1000},
[[['allow', '1'],
['allow', '2'],
['allow', '3'],
['allow', '5/2'],
['deny', '547/250'],
['allow', '29/10']],
[1, 3, 2]]],
['early in window',
{'limit': 5, 'requests': [0, 50, 100, 150, 200, 404, 410, 420, 800, 801], 'window_ms': 400},
[[['allow', '1'],
['allow', '2'],
['allow', '3'],
['allow', '4'],
['allow', '5'],
['deny', '99/20'],
['deny', '39/8'],
['deny', '19/4'],
['allow', '1'],
['allow', '2']],
[2, 0, 2]]],
['random traffic',
{'limit': 4,
'requests': [113, 180, 253, 634, 1224, 1448, 1496, 1722, 1887, 2254, 2425, 2792, 2877, 2945],
'window_ms': 1000},
[[['allow', '1'],
['allow', '2'],
['allow', '3'],
['allow', '4'],
['deny', '388/125'],
['allow', '401/125'],
['deny', '377/125'],
['allow', '389/125'],
['allow', '863/250'],
['allow', '1619/500'],
['allow', '149/40'],
['allow', '453/125'],
['deny', '3369/1000'],
['deny', '633/200']],
[2, 3, 3]]],
['single window',
{'limit': 2, 'requests': [10, 20, 34], 'window_ms': 1000},
[[['allow', '1'], ['allow', '2'], ['deny', '2']], [0, 0, 2]]]],
[['previous window weighting',
{'limit': 4, 'requests': [100, 200, 300, 400, 1255, 1500, 1750, 1800], 'window_ms': 1000},
[[['allow', '1'],
['allow', '2'],
['allow', '3'],
['allow', '4'],
['allow', '199/50'],
['allow', '4'],
['allow', '4'],
['deny', '19/5']],
[1, 4, 3]]],
['gap clears history',
{'limit': 3, 'requests': [0, 1, 2, 2605, 2700, 2800, 2900], 'window_ms': 1000},
[[['allow', '1'],
['allow', '2'],
['allow', '3'],
['allow', '1'],
['allow', '2'],
['allow', '3'],
['deny', '3']],
[2, 0, 3]]],
['stale previous after gap',
{'limit': 3, 'requests': [100, 200, 1100, 1200, 3505, 3600, 3700], 'window_ms': 1000},
[[['allow', '1'],
['allow', '2'],
['allow', '14/5'],
['deny', '13/5'],
['allow', '1'],
['allow', '2'],
['allow', '3']],
[3, 0, 3]]],
['fractional estimate boundary',
{'limit': 3, 'requests': [0, 10, 20, 1500, 1605, 1700], 'window_ms': 1000},
[[['allow', '1'],
['allow', '2'],
['allow', '3'],
['allow', '5/2'],
['deny', '437/200'],
['allow', '29/10']],
[1, 3, 2]]],
['early in window',
{'limit': 5, 'requests': [0, 50, 100, 150, 200, 405, 410, 420, 800, 801], 'window_ms': 400},
[[['allow', '1'],
['allow', '2'],
['allow', '3'],
['allow', '4'],
['allow', '5'],
['deny', '79/16'],
['deny', '39/8'],
['deny', '19/4'],
['allow', '1'],
['allow', '2']],
[2, 0, 2]]],
['random traffic',
{'limit': 4,
'requests': [237, 850, 1324, 1370, 1559, 1744, 1852, 2112, 2117, 2141, 2288, 2346, 2510, 2979],
'window_ms': 1000},
[[['allow', '1'],
['allow', '2'],
['allow', '294/125'],
['allow', '163/50'],
['allow', '1941/500'],
['deny', '439/125'],
['deny', '412/125'],
['allow', '458/125'],
['deny', '3649/1000'],
['deny', '3577/1000'],
['deny', '392/125'],
['allow', '1981/500'],
['deny', '347/100'],
['allow', '3063/1000']],
[2, 3, 3]]],
['single window',
{'limit': 2, 'requests': [10, 20, 35], 'window_ms': 1000},
[[['allow', '1'], ['allow', '2'], ['deny', '2']], [0, 0, 2]]]]]
for label, args, expected in cases[N - 1]:
check(label, solve(args), expected)
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 fixture | Actual | Expected | Outcome |
|---|---|---|---|
| previous window weighting | [[['allow', '1'], ['allow', '2'], ['allow', '3'], ['allow', '4'], ['allow', '501/250'], ['allow', '4'], ['deny', '5'], ['deny', '26/5']], [1, 4, 2]] | [[['allow', '1'], ['allow', '2'], ['allow', '3'], ['allow', '4'], ['allow', '999/250'], ['allow', '4'], ['allow', '4'], ['deny', '19/5']], [1, 4, 3]] | Failed |
| gap clears history | [[['allow', '1'], ['allow', '2'], ['allow', '3'], ['allow', '1'], ['allow', '2'], ['allow', '3'], ['deny', '3']], [2, 0, 3]] | [[['allow', '1'], ['allow', '2'], ['allow', '3'], ['allow', '1'], ['allow', '2'], ['allow', '3'], ['deny', '3']], [2, 0, 3]] | Passed |
| stale previous after gap | [[['allow', '1'], ['allow', '2'], ['allow', '6/5'], ['allow', '12/5'], ['allow', '1'], ['allow', '2'], ['allow', '3']], [3, 0, 3]] | [[['allow', '1'], ['allow', '2'], ['allow', '14/5'], ['deny', '13/5'], ['allow', '1'], ['allow', '2'], ['allow', '3']], [3, 0, 3]] | Failed |
| fractional estimate boundary | [[['allow', '1'], ['allow', '2'], ['allow', '3'], ['allow', '5/2'], ['deny', '2803/1000'], ['deny', '31/10']], [1, 3, 1]] | [[['allow', '1'], ['allow', '2'], ['allow', '3'], ['allow', '5/2'], ['deny', '2197/1000'], ['allow', '29/10']], [1, 3, 2]] | Failed |
| early in window | [[['allow', '1'], ['allow', '2'], ['allow', '3'], ['allow', '4'], ['allow', '5'], ['allow', '81/80'], ['allow', '17/8'], ['allow', '13/4'], ['allow', '1'], ['allow', '803/400']], [2, 3, 2]] | [[['allow', '1'], ['allow', '2'], ['allow', '3'], ['allow', '4'], ['allow', '5'], ['deny', '399/80'], ['deny', '39/8'], ['deny', '19/4'], ['allow', '1'], ['allow', '2']], [2, 0, 2]] | Failed |
| random traffic | [[['allow', '1'], ['allow', '1183/1000'], ['allow', '1307/500'], ['allow', '943/250'], ['allow', '1001/500'], ['allow', '3233/1000'], ['deny', '131/40'], ['deny', '3527/1000'], ['deny', '3653/1000'], ['deny', '92/25'], ['deny', '3953/1000'], ['deny', '1061/250'], ['deny', '229/50'], ['deny', '4643/1000']], [2, 3, 2]] | [[['allow', '1'], ['allow', '1817/1000'], ['allow', '1193/500'], ['allow', '807/250'], ['allow', '1499/500'], ['allow', '3767/1000'], ['deny', '149/40'], ['deny', '3473/1000'], ['deny', '3347/1000'], ['deny', '83/25'], ['deny', '3047/1000'], ['allow', '939/250'], ['deny', '171/50'], ['deny', '3357/1000']], [2, 3, 3]] | Failed |
| single window | [[['allow', '1'], ['allow', '2'], ['deny', '2']], [0, 0, 2]] | [[['allow', '1'], ['allow', '2'], ['deny', '2']], [0, 0, 2]] | Passed |
SHA-256 / 36efc693ad141b0599ce2283dc00999914d70906a6a246cd8602494201e6e58d
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
import math
from fractions import Fraction
N = 1
observations = []
def solve(x):
L = x['limit']
W = x['window_ms']
idx, prev, cur = 0, 0, 0
out = []
for t in x['requests']:
ci = t // W
if ci == idx + 1:
prev, cur = cur, 0
elif ci > idx + 1:
prev, cur = 0, 0
idx = ci
elapsed = t - idx * W
est = prev + cur * Fraction(W - elapsed, W)
if est + 1 <= L:
cur += 1
out.append(['allow', str(est + 1)])
else:
out.append(['deny', str(est)])
return [out, [idx, prev, cur]]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['previous window weighting',
{'limit': 4, 'requests': [100, 200, 300, 400, 1251, 1500, 1750, 1800], 'window_ms': 1000},
[[['allow', '1'],
['allow', '2'],
['allow', '3'],
['allow', '4'],
['allow', '999/250'],
['allow', '4'],
['allow', '4'],
['deny', '19/5']],
[1, 4, 3]]],
['gap clears history',
{'limit': 3, 'requests': [0, 1, 2, 2601, 2700, 2800, 2900], 'window_ms': 1000},
[[['allow', '1'],
['allow', '2'],
['allow', '3'],
['allow', '1'],
['allow', '2'],
['allow', '3'],
['deny', '3']],
[2, 0, 3]]],
['stale previous after gap',
{'limit': 3, 'requests': [100, 200, 1100, 1200, 3501, 3600, 3700], 'window_ms': 1000},
[[['allow', '1'],
['allow', '2'],
['allow', '14/5'],
['deny', '13/5'],
['allow', '1'],
['allow', '2'],
['allow', '3']],
[3, 0, 3]]],
['fractional estimate boundary',
{'limit': 3, 'requests': [0, 10, 20, 1500, 1601, 1700], 'window_ms': 1000},
[[['allow', '1'],
['allow', '2'],
['allow', '3'],
['allow', '5/2'],
['deny', '2197/1000'],
['allow', '29/10']],
[1, 3, 2]]],
['early in window',
{'limit': 5, 'requests': [0, 50, 100, 150, 200, 401, 410, 420, 800, 801], 'window_ms': 400},
[[['allow', '1'],
['allow', '2'],
['allow', '3'],
['allow', '4'],
['allow', '5'],
['deny', '399/80'],
['deny', '39/8'],
['deny', '19/4'],
['allow', '1'],
['allow', '2']],
[2, 0, 2]]],
['random traffic',
{'limit': 4,
'requests': [762, 1183, 1614, 1772, 2334, 2411, 2425, 2509, 2551, 2560, 2651, 2748, 2860, 2881],
'window_ms': 1000},
[[['allow', '1'],
['allow', '1817/1000'],
['allow', '1193/500'],
['allow', '807/250'],
['allow', '1499/500'],
['allow', '3767/1000'],
['deny', '149/40'],
['deny', '3473/1000'],
['deny', '3347/1000'],
['deny', '83/25'],
['deny', '3047/1000'],
['allow', '939/250'],
['deny', '171/50'],
['deny', '3357/1000']],
[2, 3, 3]]],
['single window',
{'limit': 2, 'requests': [10, 20, 31], 'window_ms': 1000},
[[['allow', '1'], ['allow', '2'], ['deny', '2']], [0, 0, 2]]]],
[['previous window weighting',
{'limit': 4, 'requests': [100, 200, 300, 400, 1252, 1500, 1750, 1800], 'window_ms': 1000},
[[['allow', '1'],
['allow', '2'],
['allow', '3'],
['allow', '4'],
['allow', '499/125'],
['allow', '4'],
['allow', '4'],
['deny', '19/5']],
[1, 4, 3]]],
['gap clears history',
{'limit': 3, 'requests': [0, 1, 2, 2602, 2700, 2800, 2900], 'window_ms': 1000},
[[['allow', '1'],
['allow', '2'],
['allow', '3'],
['allow', '1'],
['allow', '2'],
['allow', '3'],
['deny', '3']],
[2, 0, 3]]],
['stale previous after gap',
{'limit': 3, 'requests': [100, 200, 1100, 1200, 3502, 3600, 3700], 'window_ms': 1000},
[[['allow', '1'],
['allow', '2'],
['allow', '14/5'],
['deny', '13/5'],
['allow', '1'],
['allow', '2'],
['allow', '3']],
[3, 0, 3]]],
['fractional estimate boundary',
{'limit': 3, 'requests': [0, 10, 20, 1500, 1602, 1700], 'window_ms': 1000},
[[['allow', '1'],
['allow', '2'],
['allow', '3'],
['allow', '5/2'],
['deny', '1097/500'],
['allow', '29/10']],
[1, 3, 2]]],
['early in window',
{'limit': 5, 'requests': [0, 50, 100, 150, 200, 402, 410, 420, 800, 801], 'window_ms': 400},
[[['allow', '1'],
['allow', '2'],
['allow', '3'],
['allow', '4'],
['allow', '5'],
['deny', '199/40'],
['deny', '39/8'],
['deny', '19/4'],
['allow', '1'],
['allow', '2']],
[2, 0, 2]]],
['random traffic',
{'limit': 4,
'requests': [2, 284, 685, 716, 946, 1419, 1442, 1550, 1788, 1900, 2219, 2384, 2628, 2704],
'window_ms': 1000},
[[['allow', '1'],
['allow', '2'],
['allow', '3'],
['allow', '4'],
['deny', '4'],
['allow', '831/250'],
['deny', '404/125'],
['allow', '19/5'],
['allow', '481/125'],
['deny', '17/5'],
['allow', '3343/1000'],
['allow', '481/125'],
['deny', '779/250'],
['allow', '486/125']],
[2, 3, 3]]],
['single window',
{'limit': 2, 'requests': [10, 20, 32], 'window_ms': 1000},
[[['allow', '1'], ['allow', '2'], ['deny', '2']], [0, 0, 2]]]],
[['previous window weighting',
{'limit': 4, 'requests': [100, 200, 300, 400, 1253, 1500, 1750, 1800], 'window_ms': 1000},
[[['allow', '1'],
['allow', '2'],
['allow', '3'],
['allow', '4'],
['allow', '997/250'],
['allow', '4'],
['allow', '4'],
['deny', '19/5']],
[1, 4, 3]]],
['gap clears history',
{'limit': 3, 'requests': [0, 1, 2, 2603, 2700, 2800, 2900], 'window_ms': 1000},
[[['allow', '1'],
['allow', '2'],
['allow', '3'],
['allow', '1'],
['allow', '2'],
['allow', '3'],
['deny', '3']],
[2, 0, 3]]],
['stale previous after gap',
{'limit': 3, 'requests': [100, 200, 1100, 1200, 3503, 3600, 3700], 'window_ms': 1000},
[[['allow', '1'],
['allow', '2'],
['allow', '14/5'],
['deny', '13/5'],
['allow', '1'],
['allow', '2'],
['allow', '3']],
[3, 0, 3]]],
['fractional estimate boundary',
{'limit': 3, 'requests': [0, 10, 20, 1500, 1603, 1700], 'window_ms': 1000},
[[['allow', '1'],
['allow', '2'],
['allow', '3'],
['allow', '5/2'],
['deny', '2191/1000'],
['allow', '29/10']],
[1, 3, 2]]],
['early in window',
{'limit': 5, 'requests': [0, 50, 100, 150, 200, 403, 410, 420, 800, 801], 'window_ms': 400},
[[['allow', '1'],
['allow', '2'],
['allow', '3'],
['allow', '4'],
['allow', '5'],
['deny', '397/80'],
['deny', '39/8'],
['deny', '19/4'],
['allow', '1'],
['allow', '2']],
[2, 0, 2]]],
['random traffic',
{'limit': 4,
'requests': [88, 165, 511, 523, 538, 1193, 1202, 1389, 1722, 1826, 2373, 2548, 2774, 2968],
'window_ms': 1000},
[[['allow', '1'],
['allow', '2'],
['allow', '3'],
['allow', '4'],
['deny', '4'],
['deny', '807/250'],
['deny', '399/125'],
['allow', '861/250'],
['allow', '389/125'],
['allow', '462/125'],
['allow', '2881/1000'],
['allow', '839/250'],
['allow', '1839/500'],
['deny', '387/125']],
[2, 3, 3]]],
['single window',
{'limit': 2, 'requests': [10, 20, 33], 'window_ms': 1000},
[[['allow', '1'], ['allow', '2'], ['deny', '2']], [0, 0, 2]]]],
[['previous window weighting',
{'limit': 4, 'requests': [100, 200, 300, 400, 1254, 1500, 1750, 1800], 'window_ms': 1000},
[[['allow', '1'],
['allow', '2'],
['allow', '3'],
['allow', '4'],
['allow', '498/125'],
['allow', '4'],
['allow', '4'],
['deny', '19/5']],
[1, 4, 3]]],
['gap clears history',
{'limit': 3, 'requests': [0, 1, 2, 2604, 2700, 2800, 2900], 'window_ms': 1000},
[[['allow', '1'],
['allow', '2'],
['allow', '3'],
['allow', '1'],
['allow', '2'],
['allow', '3'],
['deny', '3']],
[2, 0, 3]]],
['stale previous after gap',
{'limit': 3, 'requests': [100, 200, 1100, 1200, 3504, 3600, 3700], 'window_ms': 1000},
[[['allow', '1'],
['allow', '2'],
['allow', '14/5'],
['deny', '13/5'],
['allow', '1'],
['allow', '2'],
['allow', '3']],
[3, 0, 3]]],
['fractional estimate boundary',
{'limit': 3, 'requests': [0, 10, 20, 1500, 1604, 1700], 'window_ms': 1000},
[[['allow', '1'],
['allow', '2'],
['allow', '3'],
['allow', '5/2'],
['deny', '547/250'],
['allow', '29/10']],
[1, 3, 2]]],
['early in window',
{'limit': 5, 'requests': [0, 50, 100, 150, 200, 404, 410, 420, 800, 801], 'window_ms': 400},
[[['allow', '1'],
['allow', '2'],
['allow', '3'],
['allow', '4'],
['allow', '5'],
['deny', '99/20'],
['deny', '39/8'],
['deny', '19/4'],
['allow', '1'],
['allow', '2']],
[2, 0, 2]]],
['random traffic',
{'limit': 4,
'requests': [113, 180, 253, 634, 1224, 1448, 1496, 1722, 1887, 2254, 2425, 2792, 2877, 2945],
'window_ms': 1000},
[[['allow', '1'],
['allow', '2'],
['allow', '3'],
['allow', '4'],
['deny', '388/125'],
['allow', '401/125'],
['deny', '377/125'],
['allow', '389/125'],
['allow', '863/250'],
['allow', '1619/500'],
['allow', '149/40'],
['allow', '453/125'],
['deny', '3369/1000'],
['deny', '633/200']],
[2, 3, 3]]],
['single window',
{'limit': 2, 'requests': [10, 20, 34], 'window_ms': 1000},
[[['allow', '1'], ['allow', '2'], ['deny', '2']], [0, 0, 2]]]],
[['previous window weighting',
{'limit': 4, 'requests': [100, 200, 300, 400, 1255, 1500, 1750, 1800], 'window_ms': 1000},
[[['allow', '1'],
['allow', '2'],
['allow', '3'],
['allow', '4'],
['allow', '199/50'],
['allow', '4'],
['allow', '4'],
['deny', '19/5']],
[1, 4, 3]]],
['gap clears history',
{'limit': 3, 'requests': [0, 1, 2, 2605, 2700, 2800, 2900], 'window_ms': 1000},
[[['allow', '1'],
['allow', '2'],
['allow', '3'],
['allow', '1'],
['allow', '2'],
['allow', '3'],
['deny', '3']],
[2, 0, 3]]],
['stale previous after gap',
{'limit': 3, 'requests': [100, 200, 1100, 1200, 3505, 3600, 3700], 'window_ms': 1000},
[[['allow', '1'],
['allow', '2'],
['allow', '14/5'],
['deny', '13/5'],
['allow', '1'],
['allow', '2'],
['allow', '3']],
[3, 0, 3]]],
['fractional estimate boundary',
{'limit': 3, 'requests': [0, 10, 20, 1500, 1605, 1700], 'window_ms': 1000},
[[['allow', '1'],
['allow', '2'],
['allow', '3'],
['allow', '5/2'],
['deny', '437/200'],
['allow', '29/10']],
[1, 3, 2]]],
['early in window',
{'limit': 5, 'requests': [0, 50, 100, 150, 200, 405, 410, 420, 800, 801], 'window_ms': 400},
[[['allow', '1'],
['allow', '2'],
['allow', '3'],
['allow', '4'],
['allow', '5'],
['deny', '79/16'],
['deny', '39/8'],
['deny', '19/4'],
['allow', '1'],
['allow', '2']],
[2, 0, 2]]],
['random traffic',
{'limit': 4,
'requests': [237, 850, 1324, 1370, 1559, 1744, 1852, 2112, 2117, 2141, 2288, 2346, 2510, 2979],
'window_ms': 1000},
[[['allow', '1'],
['allow', '2'],
['allow', '294/125'],
['allow', '163/50'],
['allow', '1941/500'],
['deny', '439/125'],
['deny', '412/125'],
['allow', '458/125'],
['deny', '3649/1000'],
['deny', '3577/1000'],
['deny', '392/125'],
['allow', '1981/500'],
['deny', '347/100'],
['allow', '3063/1000']],
[2, 3, 3]]],
['single window',
{'limit': 2, 'requests': [10, 20, 35], 'window_ms': 1000},
[[['allow', '1'], ['allow', '2'], ['deny', '2']], [0, 0, 2]]]]]
for label, args, expected in cases[N - 1]:
check(label, solve(args), expected)
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 fixture | Actual | Expected | Outcome |
|---|---|---|---|
| previous window weighting | [[['allow', '1'], ['allow', '9/5'], ['allow', '12/5'], ['allow', '14/5'], ['deny', '4'], ['deny', '4'], ['deny', '4'], ['deny', '4']], [1, 4, 0]] | [[['allow', '1'], ['allow', '2'], ['allow', '3'], ['allow', '4'], ['allow', '999/250'], ['allow', '4'], ['allow', '4'], ['deny', '19/5']], [1, 4, 3]] | Failed |
| gap clears history | [[['allow', '1'], ['allow', '1999/1000'], ['allow', '749/250'], ['allow', '1'], ['allow', '13/10'], ['allow', '7/5'], ['allow', '13/10']], [2, 0, 4]] | [[['allow', '1'], ['allow', '2'], ['allow', '3'], ['allow', '1'], ['allow', '2'], ['allow', '3'], ['deny', '3']], [2, 0, 3]] | Failed |
| stale previous after gap | [[['allow', '1'], ['allow', '9/5'], ['allow', '3'], ['deny', '14/5'], ['allow', '1'], ['allow', '7/5'], ['allow', '8/5']], [3, 0, 3]] | [[['allow', '1'], ['allow', '2'], ['allow', '14/5'], ['deny', '13/5'], ['allow', '1'], ['allow', '2'], ['allow', '3']], [3, 0, 3]] | Failed |
| fractional estimate boundary | [[['allow', '1'], ['allow', '199/100'], ['allow', '74/25'], ['deny', '3'], ['deny', '3'], ['deny', '3']], [1, 3, 0]] | [[['allow', '1'], ['allow', '2'], ['allow', '3'], ['allow', '5/2'], ['deny', '2197/1000'], ['allow', '29/10']], [1, 3, 2]] | Failed |
| early in window | [[['allow', '1'], ['allow', '15/8'], ['allow', '5/2'], ['allow', '23/8'], ['allow', '3'], ['deny', '5'], ['deny', '5'], ['deny', '5'], ['allow', '1'], ['allow', '799/400']], [2, 0, 2]] | [[['allow', '1'], ['allow', '2'], ['allow', '3'], ['allow', '4'], ['allow', '5'], ['deny', '399/80'], ['deny', '39/8'], ['deny', '19/4'], ['allow', '1'], ['allow', '2']], [2, 0, 2]] | Failed |
| random traffic | [[['allow', '1'], ['allow', '2'], ['allow', '1193/500'], ['allow', '307/125'], ['allow', '4'], ['deny', '3589/1000'], ['deny', '143/40'], ['deny', '3491/1000'], ['deny', '3449/1000'], ['deny', '86/25'], ['deny', '3349/1000'], ['deny', '813/250'], ['deny', '157/50'], ['deny', '3119/1000']], [2, 3, 1]] | [[['allow', '1'], ['allow', '1817/1000'], ['allow', '1193/500'], ['allow', '807/250'], ['allow', '1499/500'], ['allow', '3767/1000'], ['deny', '149/40'], ['deny', '3473/1000'], ['deny', '3347/1000'], ['deny', '83/25'], ['deny', '3047/1000'], ['allow', '939/250'], ['deny', '171/50'], ['deny', '3357/1000']], [2, 3, 3]] | Failed |
| single window | [[['allow', '1'], ['allow', '99/50'], ['deny', '969/500']], [0, 0, 2]] | [[['allow', '1'], ['allow', '2'], ['deny', '2']], [0, 0, 2]] | Failed |
SHA-256 / 78bbd2863de56a6c526a983adc4950c65f1c652b30b2507f138cb4dc2dda9610
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
import math
from fractions import Fraction
N = 1
observations = []
def solve(x):
L = x['limit']
W = x['window_ms']
idx, prev, cur = 0, 0, 0
out = []
for t in x['requests']:
ci = t // W
if ci == idx + 1:
prev, cur = cur, 0
elif ci > idx + 1:
prev, cur = 0, 0
idx = ci
elapsed = t - idx * W
est = prev * Fraction(W - elapsed, W) + cur
if est + 1 <= L:
cur += 1
out.append(['allow', str(est + 1)])
else:
out.append(['deny', str(est)])
return [out, [idx, prev, cur]]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['previous window weighting',
{'limit': 4, 'requests': [100, 200, 300, 400, 1251, 1500, 1750, 1800], 'window_ms': 1000},
[[['allow', '1'],
['allow', '2'],
['allow', '3'],
['allow', '4'],
['allow', '999/250'],
['allow', '4'],
['allow', '4'],
['deny', '19/5']],
[1, 4, 3]]],
['gap clears history',
{'limit': 3, 'requests': [0, 1, 2, 2601, 2700, 2800, 2900], 'window_ms': 1000},
[[['allow', '1'],
['allow', '2'],
['allow', '3'],
['allow', '1'],
['allow', '2'],
['allow', '3'],
['deny', '3']],
[2, 0, 3]]],
['stale previous after gap',
{'limit': 3, 'requests': [100, 200, 1100, 1200, 3501, 3600, 3700], 'window_ms': 1000},
[[['allow', '1'],
['allow', '2'],
['allow', '14/5'],
['deny', '13/5'],
['allow', '1'],
['allow', '2'],
['allow', '3']],
[3, 0, 3]]],
['fractional estimate boundary',
{'limit': 3, 'requests': [0, 10, 20, 1500, 1601, 1700], 'window_ms': 1000},
[[['allow', '1'],
['allow', '2'],
['allow', '3'],
['allow', '5/2'],
['deny', '2197/1000'],
['allow', '29/10']],
[1, 3, 2]]],
['early in window',
{'limit': 5, 'requests': [0, 50, 100, 150, 200, 401, 410, 420, 800, 801], 'window_ms': 400},
[[['allow', '1'],
['allow', '2'],
['allow', '3'],
['allow', '4'],
['allow', '5'],
['deny', '399/80'],
['deny', '39/8'],
['deny', '19/4'],
['allow', '1'],
['allow', '2']],
[2, 0, 2]]],
['random traffic',
{'limit': 4,
'requests': [762, 1183, 1614, 1772, 2334, 2411, 2425, 2509, 2551, 2560, 2651, 2748, 2860, 2881],
'window_ms': 1000},
[[['allow', '1'],
['allow', '1817/1000'],
['allow', '1193/500'],
['allow', '807/250'],
['allow', '1499/500'],
['allow', '3767/1000'],
['deny', '149/40'],
['deny', '3473/1000'],
['deny', '3347/1000'],
['deny', '83/25'],
['deny', '3047/1000'],
['allow', '939/250'],
['deny', '171/50'],
['deny', '3357/1000']],
[2, 3, 3]]],
['single window',
{'limit': 2, 'requests': [10, 20, 31], 'window_ms': 1000},
[[['allow', '1'], ['allow', '2'], ['deny', '2']], [0, 0, 2]]]],
[['previous window weighting',
{'limit': 4, 'requests': [100, 200, 300, 400, 1252, 1500, 1750, 1800], 'window_ms': 1000},
[[['allow', '1'],
['allow', '2'],
['allow', '3'],
['allow', '4'],
['allow', '499/125'],
['allow', '4'],
['allow', '4'],
['deny', '19/5']],
[1, 4, 3]]],
['gap clears history',
{'limit': 3, 'requests': [0, 1, 2, 2602, 2700, 2800, 2900], 'window_ms': 1000},
[[['allow', '1'],
['allow', '2'],
['allow', '3'],
['allow', '1'],
['allow', '2'],
['allow', '3'],
['deny', '3']],
[2, 0, 3]]],
['stale previous after gap',
{'limit': 3, 'requests': [100, 200, 1100, 1200, 3502, 3600, 3700], 'window_ms': 1000},
[[['allow', '1'],
['allow', '2'],
['allow', '14/5'],
['deny', '13/5'],
['allow', '1'],
['allow', '2'],
['allow', '3']],
[3, 0, 3]]],
['fractional estimate boundary',
{'limit': 3, 'requests': [0, 10, 20, 1500, 1602, 1700], 'window_ms': 1000},
[[['allow', '1'],
['allow', '2'],
['allow', '3'],
['allow', '5/2'],
['deny', '1097/500'],
['allow', '29/10']],
[1, 3, 2]]],
['early in window',
{'limit': 5, 'requests': [0, 50, 100, 150, 200, 402, 410, 420, 800, 801], 'window_ms': 400},
[[['allow', '1'],
['allow', '2'],
['allow', '3'],
['allow', '4'],
['allow', '5'],
['deny', '199/40'],
['deny', '39/8'],
['deny', '19/4'],
['allow', '1'],
['allow', '2']],
[2, 0, 2]]],
['random traffic',
{'limit': 4,
'requests': [2, 284, 685, 716, 946, 1419, 1442, 1550, 1788, 1900, 2219, 2384, 2628, 2704],
'window_ms': 1000},
[[['allow', '1'],
['allow', '2'],
['allow', '3'],
['allow', '4'],
['deny', '4'],
['allow', '831/250'],
['deny', '404/125'],
['allow', '19/5'],
['allow', '481/125'],
['deny', '17/5'],
['allow', '3343/1000'],
['allow', '481/125'],
['deny', '779/250'],
['allow', '486/125']],
[2, 3, 3]]],
['single window',
{'limit': 2, 'requests': [10, 20, 32], 'window_ms': 1000},
[[['allow', '1'], ['allow', '2'], ['deny', '2']], [0, 0, 2]]]],
[['previous window weighting',
{'limit': 4, 'requests': [100, 200, 300, 400, 1253, 1500, 1750, 1800], 'window_ms': 1000},
[[['allow', '1'],
['allow', '2'],
['allow', '3'],
['allow', '4'],
['allow', '997/250'],
['allow', '4'],
['allow', '4'],
['deny', '19/5']],
[1, 4, 3]]],
['gap clears history',
{'limit': 3, 'requests': [0, 1, 2, 2603, 2700, 2800, 2900], 'window_ms': 1000},
[[['allow', '1'],
['allow', '2'],
['allow', '3'],
['allow', '1'],
['allow', '2'],
['allow', '3'],
['deny', '3']],
[2, 0, 3]]],
['stale previous after gap',
{'limit': 3, 'requests': [100, 200, 1100, 1200, 3503, 3600, 3700], 'window_ms': 1000},
[[['allow', '1'],
['allow', '2'],
['allow', '14/5'],
['deny', '13/5'],
['allow', '1'],
['allow', '2'],
['allow', '3']],
[3, 0, 3]]],
['fractional estimate boundary',
{'limit': 3, 'requests': [0, 10, 20, 1500, 1603, 1700], 'window_ms': 1000},
[[['allow', '1'],
['allow', '2'],
['allow', '3'],
['allow', '5/2'],
['deny', '2191/1000'],
['allow', '29/10']],
[1, 3, 2]]],
['early in window',
{'limit': 5, 'requests': [0, 50, 100, 150, 200, 403, 410, 420, 800, 801], 'window_ms': 400},
[[['allow', '1'],
['allow', '2'],
['allow', '3'],
['allow', '4'],
['allow', '5'],
['deny', '397/80'],
['deny', '39/8'],
['deny', '19/4'],
['allow', '1'],
['allow', '2']],
[2, 0, 2]]],
['random traffic',
{'limit': 4,
'requests': [88, 165, 511, 523, 538, 1193, 1202, 1389, 1722, 1826, 2373, 2548, 2774, 2968],
'window_ms': 1000},
[[['allow', '1'],
['allow', '2'],
['allow', '3'],
['allow', '4'],
['deny', '4'],
['deny', '807/250'],
['deny', '399/125'],
['allow', '861/250'],
['allow', '389/125'],
['allow', '462/125'],
['allow', '2881/1000'],
['allow', '839/250'],
['allow', '1839/500'],
['deny', '387/125']],
[2, 3, 3]]],
['single window',
{'limit': 2, 'requests': [10, 20, 33], 'window_ms': 1000},
[[['allow', '1'], ['allow', '2'], ['deny', '2']], [0, 0, 2]]]],
[['previous window weighting',
{'limit': 4, 'requests': [100, 200, 300, 400, 1254, 1500, 1750, 1800], 'window_ms': 1000},
[[['allow', '1'],
['allow', '2'],
['allow', '3'],
['allow', '4'],
['allow', '498/125'],
['allow', '4'],
['allow', '4'],
['deny', '19/5']],
[1, 4, 3]]],
['gap clears history',
{'limit': 3, 'requests': [0, 1, 2, 2604, 2700, 2800, 2900], 'window_ms': 1000},
[[['allow', '1'],
['allow', '2'],
['allow', '3'],
['allow', '1'],
['allow', '2'],
['allow', '3'],
['deny', '3']],
[2, 0, 3]]],
['stale previous after gap',
{'limit': 3, 'requests': [100, 200, 1100, 1200, 3504, 3600, 3700], 'window_ms': 1000},
[[['allow', '1'],
['allow', '2'],
['allow', '14/5'],
['deny', '13/5'],
['allow', '1'],
['allow', '2'],
['allow', '3']],
[3, 0, 3]]],
['fractional estimate boundary',
{'limit': 3, 'requests': [0, 10, 20, 1500, 1604, 1700], 'window_ms': 1000},
[[['allow', '1'],
['allow', '2'],
['allow', '3'],
['allow', '5/2'],
['deny', '547/250'],
['allow', '29/10']],
[1, 3, 2]]],
['early in window',
{'limit': 5, 'requests': [0, 50, 100, 150, 200, 404, 410, 420, 800, 801], 'window_ms': 400},
[[['allow', '1'],
['allow', '2'],
['allow', '3'],
['allow', '4'],
['allow', '5'],
['deny', '99/20'],
['deny', '39/8'],
['deny', '19/4'],
['allow', '1'],
['allow', '2']],
[2, 0, 2]]],
['random traffic',
{'limit': 4,
'requests': [113, 180, 253, 634, 1224, 1448, 1496, 1722, 1887, 2254, 2425, 2792, 2877, 2945],
'window_ms': 1000},
[[['allow', '1'],
['allow', '2'],
['allow', '3'],
['allow', '4'],
['deny', '388/125'],
['allow', '401/125'],
['deny', '377/125'],
['allow', '389/125'],
['allow', '863/250'],
['allow', '1619/500'],
['allow', '149/40'],
['allow', '453/125'],
['deny', '3369/1000'],
['deny', '633/200']],
[2, 3, 3]]],
['single window',
{'limit': 2, 'requests': [10, 20, 34], 'window_ms': 1000},
[[['allow', '1'], ['allow', '2'], ['deny', '2']], [0, 0, 2]]]],
[['previous window weighting',
{'limit': 4, 'requests': [100, 200, 300, 400, 1255, 1500, 1750, 1800], 'window_ms': 1000},
[[['allow', '1'],
['allow', '2'],
['allow', '3'],
['allow', '4'],
['allow', '199/50'],
['allow', '4'],
['allow', '4'],
['deny', '19/5']],
[1, 4, 3]]],
['gap clears history',
{'limit': 3, 'requests': [0, 1, 2, 2605, 2700, 2800, 2900], 'window_ms': 1000},
[[['allow', '1'],
['allow', '2'],
['allow', '3'],
['allow', '1'],
['allow', '2'],
['allow', '3'],
['deny', '3']],
[2, 0, 3]]],
['stale previous after gap',
{'limit': 3, 'requests': [100, 200, 1100, 1200, 3505, 3600, 3700], 'window_ms': 1000},
[[['allow', '1'],
['allow', '2'],
['allow', '14/5'],
['deny', '13/5'],
['allow', '1'],
['allow', '2'],
['allow', '3']],
[3, 0, 3]]],
['fractional estimate boundary',
{'limit': 3, 'requests': [0, 10, 20, 1500, 1605, 1700], 'window_ms': 1000},
[[['allow', '1'],
['allow', '2'],
['allow', '3'],
['allow', '5/2'],
['deny', '437/200'],
['allow', '29/10']],
[1, 3, 2]]],
['early in window',
{'limit': 5, 'requests': [0, 50, 100, 150, 200, 405, 410, 420, 800, 801], 'window_ms': 400},
[[['allow', '1'],
['allow', '2'],
['allow', '3'],
['allow', '4'],
['allow', '5'],
['deny', '79/16'],
['deny', '39/8'],
['deny', '19/4'],
['allow', '1'],
['allow', '2']],
[2, 0, 2]]],
['random traffic',
{'limit': 4,
'requests': [237, 850, 1324, 1370, 1559, 1744, 1852, 2112, 2117, 2141, 2288, 2346, 2510, 2979],
'window_ms': 1000},
[[['allow', '1'],
['allow', '2'],
['allow', '294/125'],
['allow', '163/50'],
['allow', '1941/500'],
['deny', '439/125'],
['deny', '412/125'],
['allow', '458/125'],
['deny', '3649/1000'],
['deny', '3577/1000'],
['deny', '392/125'],
['allow', '1981/500'],
['deny', '347/100'],
['allow', '3063/1000']],
[2, 3, 3]]],
['single window',
{'limit': 2, 'requests': [10, 20, 35], 'window_ms': 1000},
[[['allow', '1'], ['allow', '2'], ['deny', '2']], [0, 0, 2]]]]]
for label, args, expected in cases[N - 1]:
check(label, solve(args), expected)
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 fixture | Actual | Expected | Outcome |
|---|---|---|---|
| previous window weighting | [[['allow', '1'], ['allow', '2'], ['allow', '3'], ['allow', '4'], ['allow', '999/250'], ['allow', '4'], ['allow', '4'], ['deny', '19/5']], [1, 4, 3]] | [[['allow', '1'], ['allow', '2'], ['allow', '3'], ['allow', '4'], ['allow', '999/250'], ['allow', '4'], ['allow', '4'], ['deny', '19/5']], [1, 4, 3]] | Passed |
| gap clears history | [[['allow', '1'], ['allow', '2'], ['allow', '3'], ['allow', '1'], ['allow', '2'], ['allow', '3'], ['deny', '3']], [2, 0, 3]] | [[['allow', '1'], ['allow', '2'], ['allow', '3'], ['allow', '1'], ['allow', '2'], ['allow', '3'], ['deny', '3']], [2, 0, 3]] | Passed |
| stale previous after gap | [[['allow', '1'], ['allow', '2'], ['allow', '14/5'], ['deny', '13/5'], ['allow', '1'], ['allow', '2'], ['allow', '3']], [3, 0, 3]] | [[['allow', '1'], ['allow', '2'], ['allow', '14/5'], ['deny', '13/5'], ['allow', '1'], ['allow', '2'], ['allow', '3']], [3, 0, 3]] | Passed |
| fractional estimate boundary | [[['allow', '1'], ['allow', '2'], ['allow', '3'], ['allow', '5/2'], ['deny', '2197/1000'], ['allow', '29/10']], [1, 3, 2]] | [[['allow', '1'], ['allow', '2'], ['allow', '3'], ['allow', '5/2'], ['deny', '2197/1000'], ['allow', '29/10']], [1, 3, 2]] | Passed |
| early in window | [[['allow', '1'], ['allow', '2'], ['allow', '3'], ['allow', '4'], ['allow', '5'], ['deny', '399/80'], ['deny', '39/8'], ['deny', '19/4'], ['allow', '1'], ['allow', '2']], [2, 0, 2]] | [[['allow', '1'], ['allow', '2'], ['allow', '3'], ['allow', '4'], ['allow', '5'], ['deny', '399/80'], ['deny', '39/8'], ['deny', '19/4'], ['allow', '1'], ['allow', '2']], [2, 0, 2]] | Passed |
| random traffic | [[['allow', '1'], ['allow', '1817/1000'], ['allow', '1193/500'], ['allow', '807/250'], ['allow', '1499/500'], ['allow', '3767/1000'], ['deny', '149/40'], ['deny', '3473/1000'], ['deny', '3347/1000'], ['deny', '83/25'], ['deny', '3047/1000'], ['allow', '939/250'], ['deny', '171/50'], ['deny', '3357/1000']], [2, 3, 3]] | [[['allow', '1'], ['allow', '1817/1000'], ['allow', '1193/500'], ['allow', '807/250'], ['allow', '1499/500'], ['allow', '3767/1000'], ['deny', '149/40'], ['deny', '3473/1000'], ['deny', '3347/1000'], ['deny', '83/25'], ['deny', '3047/1000'], ['allow', '939/250'], ['deny', '171/50'], ['deny', '3357/1000']], [2, 3, 3]] | Passed |
| single window | [[['allow', '1'], ['allow', '2'], ['deny', '2']], [0, 0, 2]] | [[['allow', '1'], ['allow', '2'], ['deny', '2']], [0, 0, 2]] | Passed |
SHA-256 / 836e3d4e88b6b27cc6a242453cebbd413e62be8681b93adfe4a3252b4baa041e
Verification & scope
A deterministic, bounded teaching model with stipulated constants and pre-hashed or explicitly hashed inputs; it is not a production implementation and makes no claim of conformance to any library or paper beyond the stated contract. 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:48:47.799713+00:00.
Case digest / 7d38ea553b3e7885e080bfd25eda603fb376f4f490c96fa604e21541db8e8a29