FA-73741 / Rate limiter algorithms / Open access
Rate limiter with a bounded per-key state table: throttled key evicted · case 01
An attacker cycles through new keys to evict its own throttled entry and receive a full bucket.
ROOT CAUSE
The least recently used key is evicted regardless of its bucket state.
VERIFIED REPAIR
Only evict keys whose bucket would be full after refilling to now.
Unsuccessful approach: Checking the stored balance without refilling treats recovered keys as still busy.
Case contract
Input {max_keys, capacity, rate, requests [[t_s, key]]} with nondecreasing whole seconds. Each key has a token bucket (starts full, cost 1). The table holds at most max_keys keys; a new key may only evict the least recently used key whose bucket would be full after refill at the current time (so eviction cannot reset anyone's limit); if no key is idle the request is "overflow" and nothing changes. Every admitted or denied request refreshes the key's recency. Return [results, keys in LRU order].
Why this case matters
Edge limiters cap memory with a fixed-size key table; evicting a key that is still being throttled hands an attacker a fresh bucket.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
maxk = x['max_keys']
cap = x['capacity']
rate = x['rate']
table = {}
order = []
out = []
for t, key in x['requests']:
if key not in table:
if len(table) >= maxk:
idle = list(order)
if not idle:
out.append('overflow')
continue
del table[idle[0]]
order.remove(idle[0])
table[key] = [cap, t]
else:
order.remove(key)
order.append(key)
st = table[key]
st[0] = min(cap, st[0] + (t - st[1]) * rate)
st[1] = t
if st[0] >= 1:
st[0] -= 1
out.append('allow')
else:
out.append('deny')
return [out, order]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['busy key not evicted',
{'capacity': 2,
'max_keys': 2,
'rate': 1,
'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [4, 'c']]},
[['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],
['lru order refreshed',
{'capacity': 1,
'max_keys': 2,
'rate': 1,
'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [10, 'b']]},
[['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],
['refilled key is idle',
{'capacity': 3,
'max_keys': 1,
'rate': 1,
'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [3, 'b'], [4, 'a']]},
[['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],
['new key starts full',
{'capacity': 2,
'max_keys': 2,
'rate': 1,
'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [7, 'c']]},
[['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],
['partially refilled not idle',
{'capacity': 4,
'max_keys': 1,
'rate': 1,
'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [4, 'b']]},
[['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],
['random keys',
{'capacity': 2,
'max_keys': 2,
'rate': 1,
'requests': [[2, 'a'],
[3, 'a'],
[4, 'a'],
[6, 'd'],
[7, 'a'],
[7, 'c'],
[9, 'a'],
[9, 'd'],
[10, 'a'],
[10, 'c'],
[10, 'c'],
[10, 'd']]},
[['allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'overflow'],
['a', 'c']]]],
[['busy key not evicted',
{'capacity': 2,
'max_keys': 2,
'rate': 1,
'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [5, 'c']]},
[['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],
['lru order refreshed',
{'capacity': 1,
'max_keys': 2,
'rate': 1,
'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [11, 'b']]},
[['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],
['refilled key is idle',
{'capacity': 3,
'max_keys': 1,
'rate': 1,
'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [4, 'b'], [5, 'a']]},
[['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],
['new key starts full',
{'capacity': 2,
'max_keys': 2,
'rate': 1,
'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [8, 'c']]},
[['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],
['partially refilled not idle',
{'capacity': 4,
'max_keys': 1,
'rate': 1,
'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [5, 'b']]},
[['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],
['random keys',
{'capacity': 2,
'max_keys': 2,
'rate': 1,
'requests': [[0, 'b'],
[1, 'd'],
[2, 'a'],
[3, 'c'],
[3, 'd'],
[4, 'a'],
[5, 'b'],
[5, 'b'],
[8, 'a'],
[9, 'b'],
[9, 'd'],
[10, 'c']]},
[['allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow'],
['d', 'c']]]],
[['busy key not evicted',
{'capacity': 2,
'max_keys': 2,
'rate': 1,
'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [6, 'c']]},
[['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],
['lru order refreshed',
{'capacity': 1,
'max_keys': 2,
'rate': 1,
'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [12, 'b']]},
[['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],
['refilled key is idle',
{'capacity': 3,
'max_keys': 1,
'rate': 1,
'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [5, 'b'], [6, 'a']]},
[['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],
['new key starts full',
{'capacity': 2,
'max_keys': 2,
'rate': 1,
'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [9, 'c']]},
[['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],
['partially refilled not idle',
{'capacity': 4,
'max_keys': 1,
'rate': 1,
'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [6, 'b']]},
[['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],
['random keys',
{'capacity': 2,
'max_keys': 2,
'rate': 1,
'requests': [[1, 'a'],
[4, 'c'],
[5, 'a'],
[5, 'c'],
[6, 'c'],
[7, 'b'],
[7, 'b'],
[7, 'c'],
[7, 'd'],
[7, 'd'],
[9, 'b'],
[10, 'd']]},
[['allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'overflow',
'overflow',
'allow',
'allow'],
['b', 'd']]]],
[['busy key not evicted',
{'capacity': 2,
'max_keys': 2,
'rate': 1,
'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [7, 'c']]},
[['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],
['lru order refreshed',
{'capacity': 1,
'max_keys': 2,
'rate': 1,
'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [13, 'b']]},
[['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],
['refilled key is idle',
{'capacity': 3,
'max_keys': 1,
'rate': 1,
'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [6, 'b'], [7, 'a']]},
[['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],
['new key starts full',
{'capacity': 2,
'max_keys': 2,
'rate': 1,
'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [10, 'c']]},
[['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],
['partially refilled not idle',
{'capacity': 4,
'max_keys': 1,
'rate': 1,
'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [7, 'b']]},
[['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],
['random keys',
{'capacity': 2,
'max_keys': 2,
'rate': 1,
'requests': [[0, 'c'],
[2, 'a'],
[3, 'd'],
[5, 'b'],
[6, 'b'],
[6, 'd'],
[7, 'a'],
[7, 'a'],
[7, 'd'],
[8, 'c'],
[9, 'd'],
[10, 'b']]},
[['allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow'],
['d', 'b']]]],
[['busy key not evicted',
{'capacity': 2,
'max_keys': 2,
'rate': 1,
'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [8, 'c']]},
[['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],
['lru order refreshed',
{'capacity': 1,
'max_keys': 2,
'rate': 1,
'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [14, 'b']]},
[['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],
['refilled key is idle',
{'capacity': 3,
'max_keys': 1,
'rate': 1,
'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [7, 'b'], [8, 'a']]},
[['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],
['new key starts full',
{'capacity': 2,
'max_keys': 2,
'rate': 1,
'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [11, 'c']]},
[['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],
['partially refilled not idle',
{'capacity': 4,
'max_keys': 1,
'rate': 1,
'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [8, 'b']]},
[['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],
['random keys',
{'capacity': 2,
'max_keys': 2,
'rate': 1,
'requests': [[0, 'a'],
[1, 'a'],
[1, 'c'],
[2, 'd'],
[3, 'c'],
[4, 'd'],
[6, 'a'],
[8, 'b'],
[8, 'd'],
[9, 'b'],
[10, 'b'],
[10, 'b']]},
[['allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow'],
['d', 'b']]]]]
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 |
|---|---|---|---|
| busy key not evicted | [['allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']] | [['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']] | Failed |
| lru order refreshed | [['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']] | [['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']] | Passed |
| refilled key is idle | [['allow', 'allow', 'allow', 'allow', 'allow'], ['a']] | [['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']] | Failed |
| new key starts full | [['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']] | [['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']] | Passed |
| partially refilled not idle | [['allow', 'allow', 'allow', 'allow', 'allow'], ['b']] | [['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']] | Failed |
| random keys | [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'd']] | [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'overflow'], ['a', 'c']] | Failed |
SHA-256 / 29b64fa8c8eec2ac992d88435b92795c7cd735883115a18c2955964f8ddf6a25
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
maxk = x['max_keys']
cap = x['capacity']
rate = x['rate']
table = {}
order = []
out = []
for t, key in x['requests']:
if key not in table:
if len(table) >= maxk:
idle = [k for k in order if table[k][0] >= cap]
if not idle:
out.append('overflow')
continue
del table[idle[0]]
order.remove(idle[0])
table[key] = [cap, t]
else:
order.remove(key)
order.append(key)
st = table[key]
st[0] = min(cap, st[0] + (t - st[1]) * rate)
st[1] = t
if st[0] >= 1:
st[0] -= 1
out.append('allow')
else:
out.append('deny')
return [out, order]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['busy key not evicted',
{'capacity': 2,
'max_keys': 2,
'rate': 1,
'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [4, 'c']]},
[['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],
['lru order refreshed',
{'capacity': 1,
'max_keys': 2,
'rate': 1,
'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [10, 'b']]},
[['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],
['refilled key is idle',
{'capacity': 3,
'max_keys': 1,
'rate': 1,
'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [3, 'b'], [4, 'a']]},
[['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],
['new key starts full',
{'capacity': 2,
'max_keys': 2,
'rate': 1,
'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [7, 'c']]},
[['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],
['partially refilled not idle',
{'capacity': 4,
'max_keys': 1,
'rate': 1,
'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [4, 'b']]},
[['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],
['random keys',
{'capacity': 2,
'max_keys': 2,
'rate': 1,
'requests': [[2, 'a'],
[3, 'a'],
[4, 'a'],
[6, 'd'],
[7, 'a'],
[7, 'c'],
[9, 'a'],
[9, 'd'],
[10, 'a'],
[10, 'c'],
[10, 'c'],
[10, 'd']]},
[['allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'overflow'],
['a', 'c']]]],
[['busy key not evicted',
{'capacity': 2,
'max_keys': 2,
'rate': 1,
'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [5, 'c']]},
[['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],
['lru order refreshed',
{'capacity': 1,
'max_keys': 2,
'rate': 1,
'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [11, 'b']]},
[['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],
['refilled key is idle',
{'capacity': 3,
'max_keys': 1,
'rate': 1,
'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [4, 'b'], [5, 'a']]},
[['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],
['new key starts full',
{'capacity': 2,
'max_keys': 2,
'rate': 1,
'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [8, 'c']]},
[['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],
['partially refilled not idle',
{'capacity': 4,
'max_keys': 1,
'rate': 1,
'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [5, 'b']]},
[['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],
['random keys',
{'capacity': 2,
'max_keys': 2,
'rate': 1,
'requests': [[0, 'b'],
[1, 'd'],
[2, 'a'],
[3, 'c'],
[3, 'd'],
[4, 'a'],
[5, 'b'],
[5, 'b'],
[8, 'a'],
[9, 'b'],
[9, 'd'],
[10, 'c']]},
[['allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow'],
['d', 'c']]]],
[['busy key not evicted',
{'capacity': 2,
'max_keys': 2,
'rate': 1,
'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [6, 'c']]},
[['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],
['lru order refreshed',
{'capacity': 1,
'max_keys': 2,
'rate': 1,
'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [12, 'b']]},
[['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],
['refilled key is idle',
{'capacity': 3,
'max_keys': 1,
'rate': 1,
'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [5, 'b'], [6, 'a']]},
[['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],
['new key starts full',
{'capacity': 2,
'max_keys': 2,
'rate': 1,
'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [9, 'c']]},
[['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],
['partially refilled not idle',
{'capacity': 4,
'max_keys': 1,
'rate': 1,
'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [6, 'b']]},
[['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],
['random keys',
{'capacity': 2,
'max_keys': 2,
'rate': 1,
'requests': [[1, 'a'],
[4, 'c'],
[5, 'a'],
[5, 'c'],
[6, 'c'],
[7, 'b'],
[7, 'b'],
[7, 'c'],
[7, 'd'],
[7, 'd'],
[9, 'b'],
[10, 'd']]},
[['allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'overflow',
'overflow',
'allow',
'allow'],
['b', 'd']]]],
[['busy key not evicted',
{'capacity': 2,
'max_keys': 2,
'rate': 1,
'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [7, 'c']]},
[['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],
['lru order refreshed',
{'capacity': 1,
'max_keys': 2,
'rate': 1,
'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [13, 'b']]},
[['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],
['refilled key is idle',
{'capacity': 3,
'max_keys': 1,
'rate': 1,
'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [6, 'b'], [7, 'a']]},
[['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],
['new key starts full',
{'capacity': 2,
'max_keys': 2,
'rate': 1,
'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [10, 'c']]},
[['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],
['partially refilled not idle',
{'capacity': 4,
'max_keys': 1,
'rate': 1,
'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [7, 'b']]},
[['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],
['random keys',
{'capacity': 2,
'max_keys': 2,
'rate': 1,
'requests': [[0, 'c'],
[2, 'a'],
[3, 'd'],
[5, 'b'],
[6, 'b'],
[6, 'd'],
[7, 'a'],
[7, 'a'],
[7, 'd'],
[8, 'c'],
[9, 'd'],
[10, 'b']]},
[['allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow'],
['d', 'b']]]],
[['busy key not evicted',
{'capacity': 2,
'max_keys': 2,
'rate': 1,
'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [8, 'c']]},
[['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],
['lru order refreshed',
{'capacity': 1,
'max_keys': 2,
'rate': 1,
'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [14, 'b']]},
[['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],
['refilled key is idle',
{'capacity': 3,
'max_keys': 1,
'rate': 1,
'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [7, 'b'], [8, 'a']]},
[['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],
['new key starts full',
{'capacity': 2,
'max_keys': 2,
'rate': 1,
'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [11, 'c']]},
[['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],
['partially refilled not idle',
{'capacity': 4,
'max_keys': 1,
'rate': 1,
'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [8, 'b']]},
[['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],
['random keys',
{'capacity': 2,
'max_keys': 2,
'rate': 1,
'requests': [[0, 'a'],
[1, 'a'],
[1, 'c'],
[2, 'd'],
[3, 'c'],
[4, 'd'],
[6, 'a'],
[8, 'b'],
[8, 'd'],
[9, 'b'],
[10, 'b'],
[10, 'b']]},
[['allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow'],
['d', 'b']]]]]
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 |
|---|---|---|---|
| busy key not evicted | [['allow', 'allow', 'allow', 'overflow', 'overflow'], ['a', 'b']] | [['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']] | Failed |
| lru order refreshed | [['allow', 'allow', 'allow', 'overflow', 'allow'], ['a', 'b']] | [['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']] | Failed |
| refilled key is idle | [['allow', 'allow', 'overflow', 'overflow', 'allow'], ['a']] | [['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']] | Failed |
| new key starts full | [['allow', 'allow', 'allow', 'overflow', 'overflow', 'overflow'], ['a', 'b']] | [['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']] | Failed |
| partially refilled not idle | [['allow', 'allow', 'allow', 'overflow', 'overflow'], ['a']] | [['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']] | Failed |
| random keys | [['allow', 'allow', 'allow', 'allow', 'allow', 'overflow', 'allow', 'allow', 'allow', 'overflow', 'overflow', 'allow'], ['a', 'd']] | [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'overflow'], ['a', 'c']] | Failed |
SHA-256 / 14bbda80cf45f814a29da4097d29f77bef1b28d5cbc69f5640eccdf033e3dde0
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
maxk = x['max_keys']
cap = x['capacity']
rate = x['rate']
table = {}
order = []
out = []
for t, key in x['requests']:
if key not in table:
if len(table) >= maxk:
idle = [k for k in order if min(cap, table[k][0] + (t - table[k][1]) * rate) >= cap]
if not idle:
out.append('overflow')
continue
del table[idle[0]]
order.remove(idle[0])
table[key] = [cap, t]
else:
order.remove(key)
order.append(key)
st = table[key]
st[0] = min(cap, st[0] + (t - st[1]) * rate)
st[1] = t
if st[0] >= 1:
st[0] -= 1
out.append('allow')
else:
out.append('deny')
return [out, order]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['busy key not evicted',
{'capacity': 2,
'max_keys': 2,
'rate': 1,
'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [4, 'c']]},
[['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],
['lru order refreshed',
{'capacity': 1,
'max_keys': 2,
'rate': 1,
'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [10, 'b']]},
[['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],
['refilled key is idle',
{'capacity': 3,
'max_keys': 1,
'rate': 1,
'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [3, 'b'], [4, 'a']]},
[['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],
['new key starts full',
{'capacity': 2,
'max_keys': 2,
'rate': 1,
'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [7, 'c']]},
[['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],
['partially refilled not idle',
{'capacity': 4,
'max_keys': 1,
'rate': 1,
'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [4, 'b']]},
[['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],
['random keys',
{'capacity': 2,
'max_keys': 2,
'rate': 1,
'requests': [[2, 'a'],
[3, 'a'],
[4, 'a'],
[6, 'd'],
[7, 'a'],
[7, 'c'],
[9, 'a'],
[9, 'd'],
[10, 'a'],
[10, 'c'],
[10, 'c'],
[10, 'd']]},
[['allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'overflow'],
['a', 'c']]]],
[['busy key not evicted',
{'capacity': 2,
'max_keys': 2,
'rate': 1,
'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [5, 'c']]},
[['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],
['lru order refreshed',
{'capacity': 1,
'max_keys': 2,
'rate': 1,
'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [11, 'b']]},
[['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],
['refilled key is idle',
{'capacity': 3,
'max_keys': 1,
'rate': 1,
'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [4, 'b'], [5, 'a']]},
[['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],
['new key starts full',
{'capacity': 2,
'max_keys': 2,
'rate': 1,
'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [8, 'c']]},
[['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],
['partially refilled not idle',
{'capacity': 4,
'max_keys': 1,
'rate': 1,
'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [5, 'b']]},
[['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],
['random keys',
{'capacity': 2,
'max_keys': 2,
'rate': 1,
'requests': [[0, 'b'],
[1, 'd'],
[2, 'a'],
[3, 'c'],
[3, 'd'],
[4, 'a'],
[5, 'b'],
[5, 'b'],
[8, 'a'],
[9, 'b'],
[9, 'd'],
[10, 'c']]},
[['allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow'],
['d', 'c']]]],
[['busy key not evicted',
{'capacity': 2,
'max_keys': 2,
'rate': 1,
'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [6, 'c']]},
[['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],
['lru order refreshed',
{'capacity': 1,
'max_keys': 2,
'rate': 1,
'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [12, 'b']]},
[['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],
['refilled key is idle',
{'capacity': 3,
'max_keys': 1,
'rate': 1,
'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [5, 'b'], [6, 'a']]},
[['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],
['new key starts full',
{'capacity': 2,
'max_keys': 2,
'rate': 1,
'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [9, 'c']]},
[['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],
['partially refilled not idle',
{'capacity': 4,
'max_keys': 1,
'rate': 1,
'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [6, 'b']]},
[['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],
['random keys',
{'capacity': 2,
'max_keys': 2,
'rate': 1,
'requests': [[1, 'a'],
[4, 'c'],
[5, 'a'],
[5, 'c'],
[6, 'c'],
[7, 'b'],
[7, 'b'],
[7, 'c'],
[7, 'd'],
[7, 'd'],
[9, 'b'],
[10, 'd']]},
[['allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'overflow',
'overflow',
'allow',
'allow'],
['b', 'd']]]],
[['busy key not evicted',
{'capacity': 2,
'max_keys': 2,
'rate': 1,
'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [7, 'c']]},
[['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],
['lru order refreshed',
{'capacity': 1,
'max_keys': 2,
'rate': 1,
'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [13, 'b']]},
[['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],
['refilled key is idle',
{'capacity': 3,
'max_keys': 1,
'rate': 1,
'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [6, 'b'], [7, 'a']]},
[['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],
['new key starts full',
{'capacity': 2,
'max_keys': 2,
'rate': 1,
'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [10, 'c']]},
[['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],
['partially refilled not idle',
{'capacity': 4,
'max_keys': 1,
'rate': 1,
'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [7, 'b']]},
[['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],
['random keys',
{'capacity': 2,
'max_keys': 2,
'rate': 1,
'requests': [[0, 'c'],
[2, 'a'],
[3, 'd'],
[5, 'b'],
[6, 'b'],
[6, 'd'],
[7, 'a'],
[7, 'a'],
[7, 'd'],
[8, 'c'],
[9, 'd'],
[10, 'b']]},
[['allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow'],
['d', 'b']]]],
[['busy key not evicted',
{'capacity': 2,
'max_keys': 2,
'rate': 1,
'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [8, 'c']]},
[['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],
['lru order refreshed',
{'capacity': 1,
'max_keys': 2,
'rate': 1,
'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [14, 'b']]},
[['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],
['refilled key is idle',
{'capacity': 3,
'max_keys': 1,
'rate': 1,
'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [7, 'b'], [8, 'a']]},
[['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],
['new key starts full',
{'capacity': 2,
'max_keys': 2,
'rate': 1,
'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [11, 'c']]},
[['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],
['partially refilled not idle',
{'capacity': 4,
'max_keys': 1,
'rate': 1,
'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [8, 'b']]},
[['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],
['random keys',
{'capacity': 2,
'max_keys': 2,
'rate': 1,
'requests': [[0, 'a'],
[1, 'a'],
[1, 'c'],
[2, 'd'],
[3, 'c'],
[4, 'd'],
[6, 'a'],
[8, 'b'],
[8, 'd'],
[9, 'b'],
[10, 'b'],
[10, 'b']]},
[['allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow'],
['d', 'b']]]]]
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 |
|---|---|---|---|
| busy key not evicted | [['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']] | [['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']] | Passed |
| lru order refreshed | [['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']] | [['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']] | Passed |
| refilled key is idle | [['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']] | [['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']] | Passed |
| new key starts full | [['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']] | [['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']] | Passed |
| partially refilled not idle | [['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']] | [['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']] | Passed |
| random keys | [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'overflow'], ['a', 'c']] | [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'overflow'], ['a', 'c']] | Passed |
SHA-256 / ef1b25325a55e006b262f045d88040d491bb705d0bb92c784302dab7b3e8c38e
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:50.373544+00:00.
Case digest / 0760b5110e115e2474c8a48f2ff43519064612d7c23c7761bc9816da3249fe2c