# UNDF: UNDF-2026-000000364
# cilium-0003: CWE-407 — Quadratic IP address deduplication in node manager

## Severity: HIGH

## Repository
github.com/cilium/cilium
Commit: (depth-1 clone, branch main)

## File
`pkg/node/manager/manager.go`

## Defective Lines
```
965:    func (m *manager) removeNodeFromIPCache(oldNode nodeTypes.Node, resource ipcacheTypes.ResourceID,
966:        ipsetEntries, nodeIPsAdded, healthIPsAdded, ingressIPsAdded, podCIDRsAdded []netip.Prefix,
967:    ) {
977:        for _, address := range oldNode.IPAddresses {          // O(A) addresses
978:            prefix := ip.IPToNetPrefix(address.IP)
979:            if slices.Contains(nodeIPsAdded, prefix) {        // O(A) linear scan
980:                continue
981:            }
...
990:            if address.Type == addressing.NodeInternalIP &&
991:                !slices.Contains(ipsetEntries, oldPrefixCluster.AsPrefix()) { // O(A) scan
...
1041:        for entry := range m.podCIDREntries(...) {            // O(CIDR) entries
1041:            if slices.Contains(podCIDRsAdded, entry.Prefix.AsPrefix()) { // O(CIDR) scan
...
1058:        if !prefix.IsValid() || slices.Contains(healthIPsAdded, prefix) { // O(H) scan
...
1073:        if !prefix.IsValid() || slices.Contains(ingressIPsAdded, prefix) { // O(I) scan
```

## Call Chain
```
NodeUpdated(oldNode, newNode) →
    NodeUpdated() [line 883] →
        removeNodeFromIPCache(oldNode, ..., nodeIPsAdded, ...) →
            for _, address := range oldNode.IPAddresses {
                slices.Contains(nodeIPsAdded, prefix)          // O(A) per address
```

`nodeIPsAdded` is built just before this call by appending one prefix per address
in `n.IPAddresses` (line 771). The same addresses that were appended to the slice
are then scanned with `slices.Contains` once per address removal — O(A²) total.

Five separate slices (`nodeIPsAdded`, `ipsetEntries`, `healthIPsAdded`,
`ingressIPsAdded`, `podCIDRsAdded`) are each scanned linearly.

## Complexity
O(A²) per node update event where:
- A = number of IP addresses on a node

In dual-stack clusters with multiple CIDRs, nodes can carry 10-30 addresses.
In large multi-cluster setups (ClusterMesh), every remote node update triggers
this path. With N remote nodes and A addresses each, reconciliation is O(N × A²).

## Impact
Every `NodeUpdated` call (triggered by any node label/address change in k8s) runs
`removeNodeFromIPCache` which performs five O(A) linear scans per address in a loop.
In large ClusterMesh deployments (500+ nodes, dual-stack) this causes measurable
ipcache update latency and CPU overhead in the node manager goroutine.

## Fix
Convert each `[]netip.Prefix` slice to `map[netip.Prefix]struct{}` before the removal loop.

```go
// Before (defective):
for _, address := range oldNode.IPAddresses {
    prefix := ip.IPToNetPrefix(address.IP)
    if slices.Contains(nodeIPsAdded, prefix) {  // O(A) scan per iteration
        continue
    }
    ...
}

// After (fixed): pre-index all five slice parameters
nodeIPsSet := make(map[netip.Prefix]struct{}, len(nodeIPsAdded))
for _, p := range nodeIPsAdded { nodeIPsSet[p] = struct{}{} }
ipsetSet := make(map[netip.Prefix]struct{}, len(ipsetEntries))
for _, p := range ipsetEntries { ipsetSet[p] = struct{}{} }
// ... same for healthIPsAdded, ingressIPsAdded, podCIDRsAdded

for _, address := range oldNode.IPAddresses {
    prefix := ip.IPToNetPrefix(address.IP)
    if _, ok := nodeIPsSet[prefix]; ok {        // O(1)
        continue
    }
    ...
}
```

## References
- CWE-407: Inefficient Algorithmic Complexity
- `pkg/node/manager/manager.go` lines 965-1080
- `removeNodeFromIPCache()` called from `NodeUpdated()` line 883
