# UNDF: UNDF-2026-000000557
# traefik-0001 — XForwarded.removeConnectionHeaders slices.Contains O(H×F) per request

## Ecosystem
traefik (Go)

## Severity
HIGH — triggered on every proxied HTTP request

## Location
`pkg/middlewares/forwardedheaders/forwarded_header.go`
Function: `removeConnectionHeaders`

## Description
Every HTTP request processed by the XForwarded middleware calls
`removeConnectionHeaders`.  Inside that function, for each value in the
`Connection` header (H values), the code calls `slices.Contains` twice:

```go
for _, f := range req.Header[connection] {          // outer: H Connection values
    for sf := range strings.SplitSeq(f, ",") {       // outer: split tokens
        key := http.CanonicalHeaderKey(sf)
        if slices.Contains(xHeaders, key) {          // O(11) linear scan
            continue
        }
        if slices.Contains(x.connectionHeaders, key) { // O(C) linear scan
            ...
        }
    }
}
```

- `xHeaders` is a package-level `[]string` of 11 fixed header names.
- `x.connectionHeaders` is a user-configured `[]string` of allowed headers
  (can be many entries in large deployments).

Complexity: O(H × (11 + C)) per request where H = Connection header token
count and C = len(connectionHeaders).

The fix converts both slices to `map[string]struct{}` at construction time,
making each lookup O(1).

## CWE
CWE-407: Inefficient Algorithmic Complexity (linear membership test inside loop)

## Fix

### forwarded_header.go — struct change
```go
type XForwarded struct {
    ...
    // was: connectionHeaders []string
    xHeadersSet        map[string]struct{}  // pre-built from package xHeaders slice
    connectionHeadersSet map[string]struct{}
    ...
}
```

### NewXForwarded — build maps at construction
```go
xHeadersSet := make(map[string]struct{}, len(xHeaders))
for _, h := range xHeaders {
    xHeadersSet[h] = struct{}{}
}
connectionHeadersSet := make(map[string]struct{}, len(connectionHeaders))
for _, h := range canonicalConnectionHeaders {
    connectionHeadersSet[h] = struct{}{}
}
```

### removeConnectionHeaders — O(1) lookups
```go
if _, ok := x.xHeadersSet[key]; ok {
    continue
}
if _, ok := x.connectionHeadersSet[key]; ok {
    connectionHopByHopHeaders = append(connectionHopByHopHeaders, key)
    continue
}
```

## Speedup
xHeaders scan: 11x (constant), connectionHeaders scan: O(C) → O(1).
At C=100 user-configured headers, 100x reduction in inner work per
Connection token.

## Status
PATCHED (patch in this file)
