# UNDF: UNDF-2026-000000428
# istio-0003: CWE-407 — O(FC×P×M×A) linear protocol scan in filterChainMatch during xDS push

## Severity: MEDIUM

## Repository
github.com/istio/istio
Commit: d9ada8a

## File
`pilot/pkg/networking/core/envoyfilter/listener_patch.go`

## Defective Lines
```go
685:  if match.ApplicationProtocols != "" {
686:      if fc.FilterChainMatch == nil {
687:          return false
688:      }
689:      for _, p := range strings.Split(match.ApplicationProtocols, ",") {  // O(M)
690:          if !slices.Contains(fc.FilterChainMatch.ApplicationProtocols, p) {  // O(A) linear scan
691:              return false
692:          }
693:      }
694:  }
```

Called from `patchFilterChain` and `patchNetworkFilters`, both of which iterate over
`patches[networking.EnvoyFilter_FILTER_CHAIN]` / `patches[networking.EnvoyFilter_NETWORK_FILTER]`.

Full call chain during xDS push:
```
buildListeners()
  → patchListeners()           // for each EnvoyFilterWrapper
    → patchListener()          // for each listener L
      → patchFilterChain()     // for each filter chain FC
        → for each patch P
          → filterChainMatch()
            → for each protocol in match.ApplicationProtocols (size M)
              → slices.Contains(fc.FilterChainMatch.ApplicationProtocols, p)   // O(A)
```

## Complexity
O(L × FC × P × M × A) per xDS push where:
- L = number of listeners (typically 1 per service port × sidecars)
- FC = number of filter chains per listener (2-10 per virtual listener)
- P = number of EnvoyFilter patches
- M = number of protocols in `match.ApplicationProtocols` comma-separated string
- A = number of application protocols in `fc.FilterChainMatch.ApplicationProtocols`

`fc.FilterChainMatch.ApplicationProtocols` is `[]string` (protobuf repeated string).
`slices.Contains` performs a sequential scan.

In a mesh with 200 listeners × 5 filter chains × 30 patches × 3 match protocols × 5
fc protocols, this is 200 × 5 × 30 × 3 × 5 = 450,000 string comparisons per
`patchListeners()` call. xDS pushes occur on every config change.

## Impact
Pilot push latency (measured as `pilot_xds_push_time`) grows with the product of
listeners × filter chains × EnvoyFilter patches. In installations with many
EnvoyFilters doing protocol-specific matching (common for gRPC, HTTP/2, ALPN-based
routing), each push pays quadratically more than necessary.

## Fix
Convert `fc.FilterChainMatch.ApplicationProtocols` to a `map[string]struct{}` (or
`sets.New[string]`) once per `filterChainMatch` call. Inner lookup becomes O(1).

```go
// Before (defective):
for _, p := range strings.Split(match.ApplicationProtocols, ",") {
    if !slices.Contains(fc.FilterChainMatch.ApplicationProtocols, p) {
        return false
    }
}

// After (fixed):
matchProtos := strings.Split(match.ApplicationProtocols, ",")
fcProtoSet := sets.New(fc.FilterChainMatch.ApplicationProtocols...)
for _, p := range matchProtos {
    if !fcProtoSet.Contains(p) {
        return false
    }
}
```

For the common case of M≤3 and A≤5, a sorted-slice binary search avoids the map
allocation while still reducing complexity from O(M×A) to O(M log A).

| L   | FC | P  | M | A | Slow ops  | Fast ops | Ratio |
|-----|----|----|---|---|-----------|----------|-------|
| 50  | 3  | 10 | 2 | 3 | 9,000     | 3,000    | 3x    |
| 100 | 5  | 20 | 3 | 5 | 150,000   | 30,000   | 5x    |
| 200 | 5  | 30 | 3 | 5 | 450,000   | 90,000   | 5x    |
| 500 | 8  | 50 | 4 | 8 | 6,400,000 | 200,000  | 32x   |

## References
- CWE-407: Inefficient Algorithmic Complexity
- `pilot/pkg/networking/core/envoyfilter/listener_patch.go` filterChainMatch() line 685-694
- `pilot/pkg/networking/core/envoyfilter/listener_patch.go` patchFilterChain() line 250-273
- `pilot/pkg/networking/core/envoyfilter/listener_patch.go` patchNetworkFilters() line 322-328
