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

## Finding

Two O(n²) defects in Envoy's retry predicate and external processing extension. Both use `std::find` on `std::vector` in per-request hot paths. Measured at 249× and 80×. Patches ready for upstream review.

## The Defects

**envoy-0001 (PATCHED — HIGH):** `source/common/upstream/retry.h`

```cpp
// PreviousHostsRetryPredicate — per retry attempt:
auto it = std::find(previous_hosts_.begin(), previous_hosts_.end(), host);
// O(P) std::vector scan per retry
```

`std::find` on `std::vector` per retry attempt in `PreviousHostsRetryPredicate`. For P previous hosts and R retries: **O(R × P)**. **Measured ratio: 249×.**

**envoy-0002 (PATCHED — HIGH):** `source/extensions/filters/http/ext_proc/ext_proc.cc:1640`

```cpp
// Per metadata key on per-request hot path:
auto it = std::find(receiving_namespaces_.begin(),
                    receiving_namespaces_.end(), ns);
// O(N) std::vector scan per metadata key per request
```

`std::find` over `receiving_namespaces_` vector per metadata key on every request. **Measured ratio: 80×.**

## Complexity Proof

**envoy-0001:** For P=249 previous hosts per retry:
- O(R×P) per request with retries
- Fixed: `absl::flat_hash_set` → O(R) per request
- **249× measured ratio.**

**envoy-0002:** For N=80 receiving namespaces:
- O(N) scan per metadata key per request
- Fixed: `absl::flat_hash_set` → O(1) per key
- **80× measured ratio.**

## Impact

All Envoy deployments using retry policies (envoy-0001) and external processing filters (envoy-0002). Envoy is the data plane for Istio, Linkerd, and virtually all service mesh implementations. It is also used standalone as a reverse proxy and load balancer. envoy-0001 fires on every request with retries — a common pattern in microservices for resilience. envoy-0002 fires on every request through an ext_proc filter.

## The Fix

**envoy-0001:** Replace `std::vector<Host*>` with `absl::flat_hash_set<Host*>`:

```cpp
// Before
auto it = std::find(previous_hosts_.begin(), previous_hosts_.end(), host);

// After
// CWE-407 fix: absl::flat_hash_set for O(1) contains instead of O(P) std::find scan.
if (previous_hosts_.contains(host)) { ... }
```

**envoy-0002:** Replace `receiving_namespaces_` vector with `absl::flat_hash_set<std::string>`.

## Patch

`defects/envoy/patch/envoy-0001-0002-retry-ext-proc-hashset.patch`

## What We Ask

1. Confirm receipt and assign a GitHub Security Advisory or issue reference.
2. Validate the patch against your retry and ext_proc filter test suites.
3. Assess CVE eligibility — envoy-0001 measured at 249× in the retry hot path.
4. Coordinate a disclosure date — we are targeting 90 days from first contact.

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