russell@unturf.com
9934133dcf
Add 88 new defect entries to HIGH and MEDIUM tables:
HIGH: mysql-0001/0002, mariadb-0001, redis-0001/0002, valkey-0001/0002, openvpn-0001,
vlc-0001, prometheus-0001, otel-collector-0001, cockroachdb-0001..0004,
tidb-0001..0008, kubernetes-0001/0002, go-0001, kotlin-0002, scala-0001,
allegro5-0001, sdl2-0001, grafana-0001, clickhouse-0001, duckdb-0001,
mongodb-0001, envoy-0001, istio-0001, cilium-0001, linkerd2-0001,
linux-0001/0002/0003, tor-0002/0003, curl-0001, julia-0001, lua-0001,
perl5-0001, nats-0001, spring-0003/0004, tomcat-0001, onos-0002, odl-0002
MEDIUM: helm-0001, mariadb-0002, openssl-0001/0002, memcached-0001,
cassandra-0001..0004, flink-0001, storm-0001/0002, zookeeper-0001..0003,
pip-0001, gradle-0001, nginx-0001, haproxy-0001, caddy-0001, varnish-0001,
ffmpeg-0001, gstreamer-0001, raylib-0001, love2d-0001, php-0001/0002,
r-source-0001, cpython-0002, ruby-0001, rabbitmq-0003/0004, activemq-0001,
ovs-0001, onos-0003, odl-0002, jetty-0001
PDF: 976K
1.7 KiB
prometheus-0001: Builder.Labels() del-slice membership — slices.Contains O(n²)
Target: Prometheus (model/labels — slicelabels build tag)
File: model/labels/labels_slicelabels.go
CWE: CWE-407 — Inefficient Algorithmic Complexity
Severity: HIGH
Status: PATCHED
Description
Builder.Labels() in the slicelabels implementation iterates every base label
and calls slices.Contains(b.del, l.Name) for each one. b.del is a []string;
slices.Contains is O(D) where D = number of deleted labels. The outer loop is
O(L) where L = total base labels. Combined cost: O(L × D).
The same path also calls contains(b.add, l.Name) (a hand-written linear scan of
[]Label), adding another O(L × A) term for A = added labels.
This function is the exit of every relabel rule application. The relabeling hot
path — ProcessBuilder in model/relabel/relabel.go — is called for every scrape
target on every scrape interval. For a LabelDrop/LabelKeep rule that deletes
K labels, D grows to K and the total cost per target per scrape is O(L²).
// labels_slicelabels.go line 424-428
for _, l := range b.base {
if slices.Contains(b.del, l.Name) || contains(b.add, l.Name) {
continue // slices.Contains = O(D), called O(L) times → O(L×D)
}
res = append(res, l)
}
Fix
Convert b.del to map[string]struct{} at construction (or lazily when first used)
so membership tests are O(1). The contains(b.add, l.Name) helper should similarly
use a map[string]int index into b.add. Total cost of Builder.Labels() drops to
O(L + D + A).
Patch
defects/prometheus/patch/prometheus-0001.patch
Unit Test
defects/prometheus/unit/PrometheusTest.java