maxKeys: Capping a Rate-Limiter Map Before It OOMs

Conclusion

When a fixed-window rate limiter keeps state in a Map keyed directly by a spoofable value, the defense itself becomes a memory-exhaustion DoS vector. Three public or semi-public endpoints — /api/sensors/switchbot/webhook, /api/guide/feedback, and student-qa — shared a FixedWindowRateLimiter whose windows Map, keyed by client IP, was never evicted. A flood that sent a different key on every request could grow that Map without limit. The fix was to put a hard cap, maxKeys (default 50,000), on the Map’s own size, and run a two-stage evictToBound before any new key is added.

Symptom

This was found during the F13 unauthenticated public webhook security review of verification phase #243. Before the fix, FixedWindowRateLimiter looked like this, with windows as a Map that had no cap on its number of keys.

// rate-limit.ts (pre-fix, abridged)
export class FixedWindowRateLimiter {
  private readonly windows = new Map<string, { windowStart: number; count: number }>();

  constructor(
    private readonly limit: number,
    private readonly windowMs: number,
  ) {}

  tryAcquire(key: string, nowMs: number): boolean {
    const state = this.windows.get(key);
    if (state !== undefined && nowMs - state.windowStart < this.windowMs) {
      if (state.count >= this.limit) return false;
      state.count += 1;
      return true;
    }
    this.windows.set(key, { windowStart: nowMs, count: 1 });
    return true;
  }
}

The key is whatever clientKeyFromHeaders returns: the leftmost entry of x-forwarded-for, or x-real-ip. Both are values a client can write freely, and spoofing was an acknowledged premise from the start — the module’s own docstring states that XFF can be spoofed by the client. But guarding against the spoofing itself is a different problem from guarding against the Map growth that a spoofed value can cause, and the latter had been left untouched. If an attacker kept sending a unique key on every request, each call to windows.set(key, ...) stacked a new entry, and expired entries weren’t reclaimed on their own unless the same key happened to come back. Exhaust per-instance memory and the Cloud Run instance crashes with OOM. The rate limiter — the defense itself — had become a low-cost DoS vector.

Cause

This rate limiter was built around a single idea: count how many times the same key has tried. The design never accounted for the possibility that the set of keys itself could be controlled by the attacker. Per-IP limiting is meant to restrain one malicious client, but the windows Map, as actually implemented, just remembers every key it has ever seen — it checks neither how trustworthy a key is nor how many distinct keys exist in total. The moment a spoofable value is adopted as the key, the Map’s size can grow in proportion to how many times the attacker chooses to send a request, as a side effect. No amount of tightening limit or windowMs touches that side effect, because those thresholds govern frequency per key, not the number of keys itself. That was the blind spot: the thing being bounded was never the right thing.

The fix

A cap on the number of entries, maxKeys (DEFAULT_MAX_KEYS = 50_000), was added, and before adding a new key the code now checks whether that cap has already been reached. If so, it calls evictToBound.

// rate-limit.ts (post-fix, abridged)
export const DEFAULT_MAX_KEYS = 50_000;

export class FixedWindowRateLimiter {
  private readonly windows = new Map<string, { windowStart: number; count: number }>();

  constructor(
    private readonly limit: number,
    private readonly windowMs: number,
    private readonly maxKeys: number = DEFAULT_MAX_KEYS,
  ) {}

  tryAcquire(key: string, nowMs: number): boolean {
    const state = this.windows.get(key);
    if (state !== undefined && nowMs - state.windowStart < this.windowMs) {
      if (state.count >= this.limit) return false;
      state.count += 1;
      return true;
    }
    if (state === undefined && this.windows.size >= this.maxKeys) {
      this.evictToBound(nowMs);
    }
    this.windows.set(key, { windowStart: nowMs, count: 1 });
    return true;
  }

  private evictToBound(nowMs: number): void {
    for (const [k, s] of this.windows) {
      if (nowMs - s.windowStart >= this.windowMs) this.windows.delete(k);
    }
    if (this.windows.size < this.maxKeys) return;
    const oldestFirst = Array.from(this.windows.entries()).sort(
      (a, b) => a[1].windowStart - b[1].windowStart,
    );
    const removeCount = this.windows.size - this.maxKeys + 1;
    for (const [k] of oldestFirst.slice(0, removeCount)) {
      this.windows.delete(k);
    }
  }
}

evictToBound works in two stages. First, it sweeps out every window that has already expired (past windowMs) across the whole Map. Most of a flood’s keys are one-shot — the same key never comes back for a second request — so this stage alone reclaims the bulk of it. If the Map is still at the cap after that sweep (meaning more unique keys than maxKeys arrived within a single window), entries are evicted oldest-windowStart-first, just until there’s room for one new entry.

There were three existing call sites (/api/sensors/switchbot/webhook, /api/guide/feedback, student-qa). Because maxKeys was added as an optional constructor parameter with a default, all three were hardened with zero changes to the call sites themselves. The existing behavior of limit, windowMs, per-key independence, and reset() is unchanged. The added unit tests confirm that feeding more unique keys than maxKeys into the same window keeps size() within maxKeys, that expired windows get swept once the cap is hit, and that normal limit enforcement (exceeding the limit on the same key) still works after eviction was introduced.

Note that this fix doesn’t aim to stop the volume itself. It only closes off the per-instance memory-exhaustion side effect; stopping the sheer amount of traffic is left to a front layer such as a WAF or Cloud Armor.

Preventing a repeat

evictToBound’s unit tests deterministically exercise both a flood within a single window (more unique keys than maxKeys) and adding a new key after expiry, using a fixed nowMs, so a change that breaks this boundary fails immediately. size() was also made public for operational monitoring, so the Map’s actual size can now be tracked in production.