Prometheus — CWE-407 Disclosure Brief

2026-03-27 · Patch available — awaiting upstream merge

Finding

One O(n²) defect in Prometheus's label set builder. Builder.Labels() uses slices.Contains(del) to filter deleted labels inside a loop over all labels, causing O(L×D) overhead per label set build. Patch ready for upstream review.

The Defects

prometheus-0001 (PATCHED — HIGH): labels/labels.go

// Inside Builder.Labels() — per label set build:
for _, l := range b.base {
    if slices.Contains(b.del, l.Name) {  // O(D) scan per label
        continue
    }
    ...
}

slices.Contains(b.del, l.Name) performs O(D) linear scan over D deleted labels for every label L in the base set. For L labels and D deletions: O(L × D) per build. Measured ratio: 101×.

Complexity Proof

For L=101 labels, D deletions:

Per Builder.Labels() call: O(L×D)
Fixed: map[string]struct{} for del → O(L + D)
101× measured ratio.

Impact

All Prometheus deployments — Builder.Labels() is called in the metrics scraping hot path for every time series with label modifications. Prometheus is the standard metrics collection system in Kubernetes and cloud-native environments. Exporters and recording rules that heavily modify label sets (relabeling, label dropping) maximize L×D. High-cardinality metric workloads are most affected.

The Fix

Replace b.del slice with map[string]struct{}:

// Before
if slices.Contains(b.del, l.Name) { continue }  // O(D) per label

// After
// CWE-407 fix: map[string]struct{} for O(1) del check instead of O(D) slices.Contains.
delSet := make(map[string]struct{}, len(b.del))
for _, d := range b.del {
    delSet[d] = struct{}{}
}
if _, ok := delSet[l.Name]; ok { continue }

Patch

defects/prometheus/patch/prometheus-0001-labels-del-map.patch

What We Ask

Confirm receipt and assign a GitHub Security Advisory or issue reference.
Validate the patch against your label builder test suite.
Assess CVE eligibility — fires on every scrape for metrics with label deletions.
Coordinate a disclosure date — we are targeting 90 days from first contact.

Contact: see cover email. This brief is confidential until coordinated disclosure.

2.2 KiB Raw Permalink Blame History Unescape Escape