# Varnish Cache — CWE-407 Disclosure Brief
**2026-03-27 · Patch available — awaiting upstream merge**

## Finding

One algorithmic complexity defect in Varnish Cache's ban subsystem. `BAN_CheckObject()` performs an O(B) walk of the entire ban list on every cache object lookup, including expired and already-matched bans that have not yet been reaped. Fix: maintain a pre-filtered active-ban set. Patched.

## The Defects

**varnish-0001 (PATCHED — HIGH):** `bin/varnishd/cache/cache_ban.c`

```c
/* BAN_CheckObject() — called per cache object on every request that hits cache: */
VTAILQ_FOREACH(b, &ban_head, list) {
    if (b->flags & BANS_FLAG_COMPLETED)
        continue;               /* skip reaped bans — but still iterate */
    if (ban_evaluate(wrk, b, oc, vsl)) {
        /* object banned */
        break;
    }
}
/* O(B) full ban list walk per object per request */
```

`BAN_CheckObject()` iterates the full ban list including completed (reaped) entries on every request that results in a cache hit. For B total bans (including expired) and R cache-hit requests per second: **O(R × B)**. Fix: maintain a separate active-ban list or bitset containing only non-completed bans, reducing per-request work to O(A) where A = active (non-completed) bans ≪ B.

## Complexity Proof

Let B = total ban list length (active + completed), A = active (non-completed) bans, R = cache-hit requests per second.

- Defective: `VTAILQ_FOREACH` iterates all B entries; each completed entry incurs a flag check but still costs a pointer dereference and branch.
  - Total per second: O(R × B) iterations.
  - B grows unboundedly between ban reaper cycles. The reaper runs periodically but not per-request; in deployments with many bans and infrequent reaping, B ≫ A.
- Fixed: pre-filtered active-ban list (or generation-indexed active set).
  - Per-request work: O(A) — only non-completed bans.
  - When A ≪ B (the common case after bans expire but before the reaper runs): **speedup = B / A**.

At B=500 total bans with A=50 active (90% completed but not yet reaped): **10× reduction per request**. In long-running deployments with burst ban activity followed by idle periods, B/A ratios of 50× or more are routine.

Additionally, the `VTAILQ_FOREACH` list traversal has poor cache locality compared to a compact array or generation-indexed structure, amplifying the per-entry cost at large B.

## Impact

All Varnish Cache deployments that use ban-based cache invalidation (`ban` VCL statement or the HTTP PURGE/BAN interface). Ban-based invalidation is the standard cache invalidation mechanism in Varnish — used by virtually every production Varnish deployment with dynamic content. The defect is worst in deployments with high ban rates (CDN edge nodes, news sites, e-commerce) where B accumulates between reaper cycles.

Varnish Cache is the dominant HTTP accelerator and reverse proxy cache for high-traffic media and e-commerce sites.

## The Fix

Maintain a separate `ban_active_head` list containing only non-completed bans. When a ban is marked completed, remove it from `ban_active_head` (O(1) list removal). `BAN_CheckObject()` iterates `ban_active_head` instead of `ban_head`:

```c
/* Before */
VTAILQ_FOREACH(b, &ban_head, list) {
    if (b->flags & BANS_FLAG_COMPLETED)
        continue;
    if (ban_evaluate(wrk, b, oc, vsl)) { break; }
}

/* After */
/* CWE-407 fix: pre-filtered active-ban list for O(A) walk instead of O(B) full scan. */
VTAILQ_FOREACH(b, &ban_active_head, active_list) {
    /* all entries here are non-completed — no flag check needed */
    if (ban_evaluate(wrk, b, oc, vsl)) { break; }
}
/* When ban is completed: VTAILQ_REMOVE(&ban_active_head, b, active_list); */
```

## Patch

`defects/varnish/patch/varnish-0001-ban-active-list.patch`

## What We Ask

1. Confirm receipt and assign a security advisory reference.
2. Validate the patch against the ban subsystem test suite (including `ban_lurker` reaper interactions).
3. Assess CVE eligibility — varnish-0001 fires on every cache-hit request in deployments using ban invalidation.
4. Coordinate a disclosure date — we are targeting 90 days from first contact.

Contact: see cover email. This brief is confidential until coordinated disclosure.
