# UNDF: UNDF-2026-000000704
# istio-0004: CWE-407 — O(P²) linear dedup in BackendPolicy parents accumulation during Gateway API reconciliation

## Severity: MEDIUM

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

## File
`pilot/pkg/config/kube/gateway/backend_policies.go`

## Defective Lines
```go
// Line 178
parents := make([]string, 0, len(pols))
for _, pol := range pols {                              // outer: O(P)
    ...
    parentName := pol.Source.Kind.String() + "/" + pol.Source.Namespace + "." + pol.Source.Name
    if !slices.Contains(parents, parentName) {          // inner: O(P) linear scan
        parents = append(parents, parentName)           // grows parents each iteration
    }
}
```

## Complexity
O(P²) where P = number of BackendPolicy objects targeting the same host.
Called from a `krt.NewCollection` reconciler that fires on every BackendPolicy
add/update/delete event.

In a mesh with many BackendPolicy objects (TLS policies + traffic policies)
referencing the same backend service, each reconciliation iterates over all
policies and scans the growing `parents` slice for duplicates.

## Call Chain
```
krt.NewCollection(byTargetAndHost.AsCollection(...), func(ctx, IndexObject) *config.Config {
    pols := slices.SortFunc(i.Objects, ...)         // all BackendPolicies for target+host
    parents := make([]string, 0, len(pols))
    for _, pol := range pols {                      // O(P)
        ...
        if !slices.Contains(parents, parentName) {  // O(P) per iteration → O(P²)
            parents = append(parents, parentName)
        }
    }
    // parents used as: strings.Join(parents, ",") for annotation value
```

## Impact
- Called on every config change that touches BackendPolicy/BackendTLSPolicy
- In clusters with P=50 policies per backend: 1,250 string comparisons per event
- In large platform teams with many microservices × policies: multiplied by the
  number of distinct target+host combinations that receive updates

## Fix
Use a `sets.New[string]()` for O(1) dedup, then convert to slice for Join:

```go
parentSet := sets.New[string]()
for _, pol := range pols {
    ...
    parentName := pol.Source.Kind.String() + "/" + pol.Source.Namespace + "." + pol.Source.Name
    parentSet.Insert(parentName)   // O(1) hash set insert
}
parents := parentSet.UnsortedList()   // O(P) for conversion
```

Or maintain order by using a `seen` map + slice:

```go
parents := make([]string, 0, len(pols))
seenParents := make(map[string]struct{}, len(pols))
for _, pol := range pols {
    ...
    parentName := pol.Source.Kind.String() + "/" + pol.Source.Namespace + "." + pol.Source.Name
    if _, exists := seenParents[parentName]; !exists {
        seenParents[parentName] = struct{}{}
        parents = append(parents, parentName)
    }
}
```

## Benchmark
- P=50: 1,250 comparisons → 50 map lookups (25x)
- P=100: 5,000 comparisons → 100 map lookups (50x)
- Complexity: O(P²) → O(P)

## Unit Test
See `defects/istio/unit/Istio0004Test.java`

## Note
The same O(H²) pattern appears in:
- `pilot/pkg/config/kube/agentgateway/gateway_status.go:153` (`pending`/`addressesToReport` dedup)
- `pilot/pkg/config/kube/gateway/conversion.go:1787` (identical code, different gateway API impl)
Both use `slices.Contains(pending, svchost) && slices.Contains(addressesToReport, svchost)` in a
loop — the same pattern but with typically smaller slices (1-10 addresses).
