java-topology/docs/tickets/cilium-0001-requirement-hasvalue-linear-scan-identity-matching.md

cilium-0001: Requirement.hasValue slices.Contains O(n) called per identity in selector cache → O(n²)

Target: cilium/cilium Severity: HIGH CWE: CWE-407 (Inefficient Algorithmic Complexity) File: pkg/k8s/slim/k8s/apis/labels/selector.go Status: PATCHED

Description

Requirement.hasValue(value string) calls slices.Contains(r.strValues, value) where r.strValues is a []string. This is O(V) where V = number of values in the requirement's value set (e.g. a In selector with many values).

hasValue is called from Requirement.Matches(), which is called from internalSelector.Matches(), which is called from selectorcache.go inside a loop over every security identity in the cache (for nid, id := range c.ids).

Total complexity: O(I × R × V) where I = identities, R = requirements per selector, V = values per requirement. In large clusters with thousands of endpoints and label selectors with many values (e.g. namespace In [ns1, ns2, ..., nsN]), this becomes quadratic.

Location	Pattern
selector.go:217	slices.Contains(r.strValues, value) — O(V) membership test
selector.go:238	r.hasValue(val) in Matches() hot path
selectorcache.go:118	sel.source.Matches(id.lbls) — called per identity in namespace loop
selectorcache.go:728	sel.source.Matches(identity.lbls) — called per identity in full scan

Root cause

// selector.go:160 — strValues stored as plain slice
type Requirement struct {
    key       string
    operator  selection.Operator
    strValues []string   // ← slice, O(n) membership
}

// selector.go:216 — O(V) scan on every label match check
func (r *Requirement) hasValue(value string) bool {
    return slices.Contains(r.strValues, value)
}

Caller in selectorcache.go:100 (selections — iterates all identities):

for nid, id := range c.ids {
    if sel.source.Matches(id.lbls) {   // O(R × V) per identity
        ...
    }
}

In a cluster with I=10,000 identities, R=3 requirements, V=50 values each: 1,500,000 string comparisons per selector evaluation.

Fix

Change strValues from []string to sets.String (or map[string]struct{}). The hasValue call becomes an O(1) map lookup. The existing Values() accessor already returns a sets.String, so the change is straightforward.

// After fix
type Requirement struct {
    key          string
    operator     selection.Operator
    strValues    sets.String   // O(1) lookup
    strValueList []string      // keep for ordering/serialization only
}

func (r *Requirement) hasValue(value string) bool {
    return r.strValues.Has(value)   // O(1)
}

Ops/ns numbers (Java benchmark)

See defects/cilium/unit/CiliumTest.java. At I=10,000 identities, V=50 values: slow ~500,000 ops, fast ~10,000 ops → >50× speedup.