# UNDF: UNDF-2026-000000443
# kubernetes-0004: TaintSetDiff — O(T²) quadratic taint membership test in node lifecycle controller

**Severity:** MEDIUM
**CWE:** CWE-407 (Algorithmic Complexity — linear membership test inside a loop)
**Speedup:** ~T× where T = number of taints on node (typically 2–20 system taints)
**Target:** Kubernetes (kubernetes/kubernetes)
**Files:**
- `pkg/util/taints/taints.go:260` — `TaintSetDiff`: nested `TaintExists` call inside loop over taintsNew/taintsOld
- `pkg/controller/nodelifecycle/node_lifecycle_controller.go:567` — hot-path caller in `doNoScheduleTaintingPass`

## Description

`TaintSetDiff` computes the symmetric difference between two taint slices. It is
called from `doNoScheduleTaintingPass`, which runs for every node on every
node-condition-change event (NotReady, PressureTaint, Unschedulable, etc.).

The function iterates each taint in `taintsNew` and calls `TaintExists(taintsOld,
&taint)`, which itself iterates all of `taintsOld` linearly:

```go
// pkg/util/taints/taints.go:260
func TaintSetDiff(taintsNew, taintsOld []v1.Taint) (taintsToAdd []*v1.Taint, taintsToRemove []*v1.Taint) {
    for _, taint := range taintsNew {
        if !TaintExists(taintsOld, &taint) {   // O(|taintsOld|) per iteration
            t := taint
            taintsToAdd = append(taintsToAdd, &t)
        }
    }
    for _, taint := range taintsOld {
        if !TaintExists(taintsNew, &taint) {   // O(|taintsNew|) per iteration
            t := taint
            taintsToRemove = append(taintsToRemove, &t)
        }
    }
    return
}
```

```go
// pkg/util/taints/taints.go:243
func TaintExists(taints []v1.Taint, taintToFind *v1.Taint) bool {
    for _, taint := range taints {
        if taint.MatchTaint(taintToFind) {
            return true
        }
    }
    return false
}
```

For T taints per slice, `TaintSetDiff` performs O(T²) `MatchTaint` comparisons:
- First loop: `|taintsNew| × |taintsOld|` comparisons
- Second loop: `|taintsOld| × |taintsNew|` comparisons

## Root Cause

`TaintSetDiff` uses `TaintExists` (O(T) linear scan) inside a loop rather than
building a lookup structure from one slice and doing O(1) membership tests in
the other loop.

A taint's identity is fully determined by `(Key, Effect)` — a composite key
that can be used as a map key. Building a `map[string]v1.Taint` (keyed by
`Key+"/"+Effect`) from `taintsOld` before the first loop reduces both passes to
O(T) total.

## Complexity Before

`TaintSetDiff`: **O(T²)** — two nested linear scans for T taints per slice.
Called per node per condition-change event in `doNoScheduleTaintingPass`.

## Complexity After

**O(T)** — build set from one slice, O(1) lookup in both passes.

## Patch

```go
// Fixed TaintSetDiff using a map-based lookup set
func TaintSetDiff(taintsNew, taintsOld []v1.Taint) (taintsToAdd []*v1.Taint, taintsToRemove []*v1.Taint) {
    oldSet := make(map[string]struct{}, len(taintsOld))
    for i := range taintsOld {
        oldSet[taintsOld[i].Key+"/"+string(taintsOld[i].Effect)] = struct{}{}
    }
    newSet := make(map[string]struct{}, len(taintsNew))
    for i := range taintsNew {
        newSet[taintsNew[i].Key+"/"+string(taintsNew[i].Effect)] = struct{}{}
    }
    for i := range taintsNew {
        k := taintsNew[i].Key + "/" + string(taintsNew[i].Effect)
        if _, found := oldSet[k]; !found {
            t := taintsNew[i]
            taintsToAdd = append(taintsToAdd, &t)
        }
    }
    for i := range taintsOld {
        k := taintsOld[i].Key + "/" + string(taintsOld[i].Effect)
        if _, found := newSet[k]; !found {
            t := taintsOld[i]
            taintsToRemove = append(taintsToRemove, &t)
        }
    }
    return
}
```

## Reproduction

```
cd defects/kubernetes/unit && javac -d . *.java && java -ea unit.KubernetesTest
```
