# UNDF: UNDF-2026-000000363
# cilium-0001: CWE-407 — Quadratic L7 rule deduplication during network policy merge

## Severity: MEDIUM

## Repository
github.com/cilium/cilium
Commit: 0b72c000

## File
`pkg/policy/rule.go`

## Defective Lines
```
310:    for _, newRule := range newPolicy.HTTP {                      // outer: O(N) new rules
311:        if !newRule.Exists(existingPolicy.L7Rules) {             // inner: O(M) linear scan
312:            existingPolicy.HTTP = append(existingPolicy.HTTP, newRule)
313:        }
314:    }
315:    for _, newRule := range newPolicy.DNS {                      // outer: O(N) new DNS rules
316:        if !newRule.Exists(existingPolicy.L7Rules) {             // inner: O(M) linear scan
317:            existingPolicy.DNS = append(existingPolicy.DNS, newRule)
318:        }
319:    }
```

## Call Chain
`Exists()` → `pkg/policy/api/utils.go:15` → `slices.ContainsFunc(rules.HTTP, h.Equal)`

`slices.ContainsFunc` is a linear scan over the existing rules list.

## Outer Loop Context
This code is called from `mergeL4Filter()` which is invoked for every
`(port, selector)` combination when reconciling network policies:
```
addFilter() → mergeL4Filter() → for each selector in PerSelectorPolicies:
    for _, newRule := range newPolicy.HTTP { ... Exists() ... }
```

Policy reconciliation runs on every CiliumNetworkPolicy create/update/delete.

## Complexity
O(S × N × M) where:
- S = number of selectors in the L4Filter
- N = number of new HTTP/DNS rules being merged
- M = number of existing HTTP/DNS rules already in the policy

## Impact
In clusters with complex CNP/CCNP policies (100+ selectors, each with 20+ L7 rules),
policy reconciliation latency grows quadratically. This manifests as elevated
`cilium_policy_regeneration_time_stats` metrics and endpoint regeneration delays
that block traffic during policy updates.

## Fix
Build a hash set from `existingPolicy.L7Rules.HTTP` before the merge loop.
The `PortRuleHTTP` struct can be hashed via its exported fields.

```go
// Before (defective):
for _, newRule := range newPolicy.HTTP {
    if !newRule.Exists(existingPolicy.L7Rules) {
        existingPolicy.HTTP = append(existingPolicy.HTTP, newRule)
    }
}

// After (fixed): pre-index existing rules
type httpRuleKey struct{ Path, Method, Host string }
existingHTTPSet := make(map[httpRuleKey]struct{}, len(existingPolicy.HTTP))
for _, r := range existingPolicy.HTTP {
    existingHTTPSet[httpRuleKey{r.Path, r.Method, r.Host}] = struct{}{}
}
for _, newRule := range newPolicy.HTTP {
    key := httpRuleKey{newRule.Path, newRule.Method, newRule.Host}
    if _, found := existingHTTPSet[key]; !found {
        existingPolicy.HTTP = append(existingPolicy.HTTP, newRule)
        existingHTTPSet[key] = struct{}{}
    }
}
```

Note: Headers and HeaderMatches require a stable canonical form (sorted, joined)
as part of the key, or the full Equal() check as a fallback for exact dedup.

## References
- CWE-407: Inefficient Algorithmic Complexity
- `pkg/policy/rule.go` mergeL4Filter() lines 310-318
- `pkg/policy/api/utils.go` Exists() / slices.ContainsFunc line 15
