# 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`

```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{}`:

```go
// 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

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

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