# UNDF: UNDF-2026-000000391
# envoy-0003: CWE-407 — O(H×R) linear scan during EDS host batch merge

## Severity: MEDIUM

## Repository
github.com/envoyproxy/envoy
Commit: a2fe7fb

## File
`source/common/upstream/cluster_manager_impl.cc`

## Defective Lines
```cpp
1401:  for (const auto& update : update_params.per_priority_update_params_) {   // outer: O(U) priority updates
1421:    if (!update.hosts_removed_.empty()) {
1423:      auto& host_added = priority_state.hosts_added_;
1424:      auto removed_section = std::remove_if(
1425:          host_added.begin(), host_added.end(),
1426:          [hosts_removed = std::cref(update.hosts_removed_)](const HostSharedPtr& ptr) {
1427:            return std::find(hosts_removed.get().begin(), hosts_removed.get().end(), ptr) !=
1428:                   hosts_removed.get().end();            // inner: O(R) linear scan per host
1429:          });
```

## Type
`HostVector` = `std::vector<HostSharedPtr>` (defined in `envoy/upstream/upstream.h:343`).

Both `host_added` (size H) and `hosts_removed_` (size R) are plain vectors.
`std::remove_if` iterates over all H elements; for each element the lambda calls `std::find`
over the R-element `hosts_removed_` vector — total O(H × R) comparisons per priority.

The TODO comment at line 1418 explicitly acknowledges this:
```
// TODO(kbaichoo): replace with a more efficient algorithm.
```

## Complexity
O(H × R) per EDS update batch per priority, where:
- H = number of hosts currently in `hosts_added_` (accumulation from prior batches)
- R = number of hosts in `hosts_removed_` for this update

Called from `ClusterInitializationObject` constructor during EDS cluster updates.
For clusters with hundreds of endpoints undergoing rolling deploys (many adds + removes
in a single batch), H and R can each reach hundreds, giving O(10,000+) pointer comparisons
per priority level per update cycle.

## Impact
EDS update processing latency scales quadratically with cluster size during churning
scenarios: rolling restarts, blue-green deploys, canary rollouts. Clusters with 500
endpoints and overlapping add/remove batches see O(250,000) pointer comparisons per
update on this code path, adding measurable latency to the control-plane → data-plane
convergence loop. The existing TODO comment confirms the maintainers intended to fix this.

## Fix
Build an `absl::flat_hash_set<HostSharedPtr>` from `hosts_removed_` once before the
`remove_if` predicate. O(1) lookup per element instead of O(R) scan.

```cpp
// Before (defective):
auto removed_section = std::remove_if(
    host_added.begin(), host_added.end(),
    [hosts_removed = std::cref(update.hosts_removed_)](const HostSharedPtr& ptr) {
      return std::find(hosts_removed.get().begin(), hosts_removed.get().end(), ptr) !=
             hosts_removed.get().end();
    });

// After (fixed):
absl::flat_hash_set<HostSharedPtr> removed_set(
    update.hosts_removed_.begin(), update.hosts_removed_.end());
auto removed_section = std::remove_if(
    host_added.begin(), host_added.end(),
    [&removed_set](const HostSharedPtr& ptr) {
      return removed_set.contains(ptr);
    });
```

| Scenario       | H    | R   | Slow ops   | Fast ops | Ratio  |
|----------------|------|-----|------------|----------|--------|
| Small cluster  | 50   | 20  | 1,000      | 70       | ~14x   |
| Medium cluster | 200  | 100 | 20,000     | 300      | ~67x   |
| Large cluster  | 500  | 200 | 100,000    | 700      | ~143x  |
| Stress (canary)| 1000 | 500 | 500,000    | 1,500    | ~333x  |

## References
- CWE-407: Inefficient Algorithmic Complexity
- `source/common/upstream/cluster_manager_impl.cc` line 1418-1430
- `envoy/upstream/upstream.h` line 343: `using HostVector = std::vector<HostSharedPtr>`
- `absl/container/flat_hash_set.h`
