UNDF: UNDF-2026-000000559

traefik-0003 — runtime PopulateUsedBy entryPoints slices.Contains O(R×M×E) config load

Ecosystem

traefik (Go)

Severity

MEDIUM — config reload path; scales poorly with many routers + entry points

Location

pkg/config/runtime/runtime_http.go function PopulateUsedBy
pkg/config/runtime/runtime_tcp.go function PopulateUsedBy
pkg/config/runtime/runtime_udp.go function PopulateUsedBy

Description

All three PopulateUsedBy functions have the same pattern:

for rtName, rt := range c.Routers {           // O(R) outer: R routers
    for _, entryPointName := range rt.EntryPoints { // O(M) middle: M EPs per router
        if !slices.Contains(entryPoints, entryPointName) { // O(E) inner scan
            ...
        }
    }
}

entryPoints is a []string passed in, containing all configured entry point names. The slices.Contains call does a linear scan of E names for every (router, entryPoint) pair.

Complexity: O(R × M × E) per config reload.

In large Kubernetes deployments: R=1000 routers, M=3 entry points each, E=20 entry points → 60,000 linear comparisons per reload.

Fix: pre-build entryPointsSet := make(map[string]bool) from the entryPoints slice before the outer loop. Each lookup becomes O(1).

CWE

CWE-407: Inefficient Algorithmic Complexity

Fix (all three files, same pattern)

// Pre-build O(1) lookup set before the loop.
entryPointsSet := make(map[string]bool, len(entryPoints))
for _, ep := range entryPoints {
    entryPointsSet[ep] = true
}

for rtName, rt := range c.Routers {
    for _, entryPointName := range rt.EntryPoints {
        if !entryPointsSet[entryPointName] {  // O(1)
            rt.AddError(...)
            continue
        }
        ...
    }
}

Speedup

E=20 entry points: 20x reduction in inner work per config reload.

Status

PATCHED (patch in this file)

1.9 KiB Raw Permalink Blame History Unescape Escape