# UNDF: UNDF-2026-000000172
# moby-0001: TweakCapabilities O(n²) — slices.Contains inside loop on every container start

## Severity
HIGH — called on every `docker run` / container start via `WithCapabilities` in `daemon/oci_linux.go:162`

## File
`daemon/pkg/oci/caps/utils.go` — `TweakCapabilities`

## CWE
CWE-407: Algorithmic Complexity (Inefficient Algorithmic Complexity)

## Description
`TweakCapabilities` iterates over `GetAllCapabilities()` (~41 caps on modern Linux) or `basics`
(14 default caps) and calls `slices.Contains(capDrop, c)` on each iteration. `slices.Contains`
performs a linear scan of `capDrop`, making the overall loop O(|capabilities| × |capDrop|).

With `capAdd = ["ALL"]` (privileged-style grants): 41 × 41 = 1,681 comparisons per container start.
With the default path: 14 × |capDrop| comparisons.

At Docker-in-Kubernetes scale (thousands of container starts per second), this accumulates.

## Defective code
```go
// daemon/pkg/oci/caps/utils.go:99-103
case slices.Contains(capAdd, allCapabilities):
    for _, c := range GetAllCapabilities() {
        if !slices.Contains(capDrop, c) {   // O(n) scan per iteration → O(n²) total
            caps = append(caps, c)
        }
    }
// and line 109-113 (default case):
for _, c := range basics {
    if !slices.Contains(capDrop, c) {       // O(n) scan per iteration → O(n²) total
        caps = append(caps, c)
    }
}
```

## Fix
Convert `capDrop` to a `map[string]struct{}` before the loop. O(n) build, O(1) lookup.

```go
// Build a set from capDrop for O(1) membership test
dropSet := make(map[string]struct{}, len(capDrop))
for _, c := range capDrop {
    dropSet[c] = struct{}{}
}

case slices.Contains(capAdd, allCapabilities):
    for _, c := range GetAllCapabilities() {
        if _, dropped := dropSet[c]; !dropped {
            caps = append(caps, c)
        }
    }
// default case:
for _, c := range basics {
    if _, dropped := dropSet[c]; !dropped {
        caps = append(caps, c)
    }
}
```

## Speedup
N=41 (all caps): ~41× fewer comparisons in the inner membership test.
N=14 (default): linear improvement proportional to len(capDrop).

## Call chain
`docker run` → `daemon/oci_linux.go:WithCapabilities` → `caps.TweakCapabilities`
