# UNDF: UNDF-2026-000000368
# containerd-0001: filterCaps + WithAddedCapabilities O(n²) — capsContain inside loop

## Severity
MEDIUM — called during container spec construction on every container start

## File
`pkg/oci/spec_opts.go:1069` — `filterCaps`, `1080` — `WithAddedCapabilities`

## CWE
CWE-407: Algorithmic Complexity

## Description
Two independent O(n²) patterns:

**1. `filterCaps`** (line 1069): iterates over `caps` slice, calls `capsContain(filters, c)` on each
element. `capsContain` wraps `slices.Contains` — O(|filters|) per element → O(|caps| × |filters|).
Called from `WithCapabilities` when `Inheritable` caps need filtering.

**2. `WithAddedCapabilities`** (line 1080): for each capability in the `caps` arg, iterates over 3
capability lists (Bounding, Effective, Permitted), calling `capsContain(*cl, c)` — O(|cl|) each.
Total: O(|caps| × 3 × |cl|).

With Linux having ~41 capabilities, this is 41×41×3 = ~5,043 comparisons per container start.

## Defective code
```go
// spec_opts.go:1069-1077
func filterCaps(caps *[]string, filters []string) {
    var newcaps []string
    for _, c := range *caps {
        if capsContain(filters, c) {   // O(|filters|) per element → O(n²) total
            newcaps = append(newcaps, c)
        }
    }
    *caps = newcaps
}

// spec_opts.go:1083-1096
for _, c := range caps {
    for _, cl := range [...Bounding, Effective, Permitted] {
        if !capsContain(*cl, c) {      // O(|cl|) per cap → O(n²)
            *cl = append(*cl, c)
        }
    }
}
```

## Fix
Convert `filters` / `*cl` to map before the loop.

```go
func filterCaps(caps *[]string, filters []string) {
    filterSet := make(map[string]struct{}, len(filters))
    for _, f := range filters { filterSet[f] = struct{}{} }
    var newcaps []string
    for _, c := range *caps {
        if _, ok := filterSet[c]; ok {
            newcaps = append(newcaps, c)
        }
    }
    *caps = newcaps
}
```

For `WithAddedCapabilities`, build a set from each `*cl` slice before the inner check.
