UNDF: UNDF-2026-000000501

podman-0001: determineCapAddDropFromCapabilities O(n²) — slices.Contains inside loop

Severity

MEDIUM — called during podman generate kube to diff capability sets

File

libpod/kube.go:1280 — determineCapAddDropFromCapabilities

CWE

CWE-407: Algorithmic Complexity

Description

Two nested O(n²) loops: for each capability in defaultCaps, calls slices.Contains(containerCaps, …); for each capability in containerCaps, calls slices.Contains(defaultCaps, …).

With ~41 capabilities per set: 41×41 = 1,681 comparisons × 2 passes = 3,362 comparisons per call. Called once per container during kube YAML generation — bounded, but wasteful and grows O(n²) if capability sets grow.

Defective code

// libpod/kube.go:1289-1305
for _, capability := range defaultCaps {
    if !slices.Contains(containerCaps, capability) {   // O(n) per iteration
        ...
    }
}
for _, capability := range containerCaps {
    if !slices.Contains(defaultCaps, capability) {      // O(n) per iteration
        ...
    }
}

Fix

Build maps for both slices before the loops.

defaultSet := make(map[string]struct{}, len(defaultCaps))
for _, c := range defaultCaps { defaultSet[c] = struct{}{} }
containerSet := make(map[string]struct{}, len(containerCaps))
for _, c := range containerCaps { containerSet[c] = struct{}{} }

for _, capability := range defaultCaps {
    if _, ok := containerSet[capability]; !ok { ... }
}
for _, capability := range containerCaps {
    if _, ok := defaultSet[capability]; !ok { ... }
}

1.5 KiB Raw Permalink Blame History Unescape Escape