# UNDF: UNDF-2026-000000699
# envoy-0004: CWE-407 — O(S²) linear dedup in HTTP/2 sendSettingsHelper per connection

## Severity: MEDIUM

## Repository
github.com/envoyproxy/envoy
Commit: HEAD (main branch)

## File
`source/common/http/http2/codec_impl.cc`

## Defective Lines
```cpp
// Line 1733-1744
void ConnectionImpl::sendSettingsHelper(...) {
  absl::InlinedVector<http2::adapter::Http2Setting, 10> settings;
  auto insertParameter = [&settings](const http2::adapter::Http2Setting& entry) mutable -> bool {
    // Consider using a set as an intermediate data structure, rather than this ad-hoc
    // deduplication.                                              ^^^ developer TODO
    const auto it = std::find_if(
        settings.cbegin(), settings.cend(),
        [&entry](const http2::adapter::Http2Setting& existing) { return entry.id == existing.id; });
    if (it != settings.end()) {
      return false;
    }
    settings.push_back(entry);
    return true;
  };
  ...
  for (const auto& it : http2_options.custom_settings_parameters()) {  // outer: O(S)
    insertParameter({...});                                              // inner: O(S) scan
  }
```

## Complexity
O(S²) where S = number of `custom_settings_parameters` entries configured in
the HTTP/2 protocol options.  Called once per HTTP/2 connection establishment,
on both client and server sides.

The developer left a comment explicitly acknowledging the issue:
```cpp
// Consider using a set as an intermediate data structure, rather than this
// ad-hoc deduplication.
```

This is triggered at connection setup for every H2 connection: downstream
(listener accept path) and upstream (cluster connect path).

At S=50 custom settings, each connection setup performs ~1,250 comparisons
in `std::find_if` — 50× the O(S) cost with a hash map.

## Impact
- Per-connection cost on H2 connection establishment
- In high-connection-churn deployments (connection pooling disabled, or short
  connections) this executes O(C × S²) where C is connection rate
- In default configs S is small (0-5), but enterprise deployments with custom
  H2 tuning parameters (flow control, stream limits, etc.) can have large S

## Fix
Replace the `InlinedVector` + `std::find_if` dedup with `absl::flat_hash_map`
for O(1) per-insertion duplicate detection:

```cpp
void ConnectionImpl::sendSettingsHelper(
    const envoy::config::core::v3::Http2ProtocolOptions& http2_options, bool disable_push) {
  // Use flat_hash_map for O(1) duplicate detection instead of O(S) std::find_if.
  absl::flat_hash_map<http2::adapter::Http2SettingsId, uint32_t> settings_map;

  auto insertParameter = [&settings_map](const http2::adapter::Http2Setting& entry) -> bool {
    return settings_map.emplace(entry.id, entry.value).second;
  };
  ...
  // Convert map to vector for SubmitSettings
  absl::InlinedVector<http2::adapter::Http2Setting, 10> settings;
  settings.reserve(settings_map.size());
  for (const auto& [id, value] : settings_map) {
    settings.push_back({id, value});
  }
  adapter_->SubmitSettings(settings);
}
```

## Benchmark
- S=50 custom settings: 1,250 comparisons → 50 hash insertions (~25x)
- S=100 custom settings: 5,000 comparisons → 100 hash insertions (~50x)
- Complexity: O(S²) → O(S)

## Unit Test
See `defects/envoy/unit/Envoy0004Test.java`
