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
55 lines
1.5 KiB
Markdown
55 lines
1.5 KiB
Markdown
# helm-0001: processDependencyEnabled — O(n²) nested dependency lookup
|
||
|
||
**Target:** helm/helm
|
||
**File:** `internal/chart/v3/util/dependencies.go`
|
||
**Severity:** MEDIUM
|
||
**Pattern:** CWE-407 — O(n) scan inside O(n) loop → O(n²)
|
||
|
||
## Description
|
||
|
||
`processDependencyEnabled` contains two O(n²) patterns:
|
||
|
||
### Pattern A — nested loop (lines 157-163)
|
||
|
||
```go
|
||
for _, existing := range c.Dependencies() { // O(E)
|
||
for _, req := range c.Metadata.Dependencies { // O(M) per existing
|
||
if existing.Name() == req.Name && ...
|
||
```
|
||
|
||
For each already-loaded chart it scans the full metadata dependency list to decide whether to
|
||
keep it. Complexity: O(E × M).
|
||
|
||
### Pattern B — getAliasDependency called per metadata dep (lines 166-176)
|
||
|
||
```go
|
||
for _, req := range c.Metadata.Dependencies { // O(M)
|
||
if chartDependency := getAliasDependency(c.Dependencies(), req) // O(C) each
|
||
```
|
||
|
||
`getAliasDependency` is itself a linear scan over `c.Dependencies()`. Complexity: O(M × C).
|
||
|
||
In a chart with D dependencies both patterns are O(D²). In umbrella charts or operator bundles
|
||
that embed dozens of sub-charts this shows up as O(D²) work on every `helm install` / `helm
|
||
upgrade`.
|
||
|
||
## Fix
|
||
|
||
Index `c.Dependencies()` by name before the loops:
|
||
|
||
```go
|
||
depsByName := make(map[string]*chart.Chart, len(c.Dependencies()))
|
||
for _, dep := range c.Dependencies() {
|
||
depsByName[dep.Name()] = dep
|
||
}
|
||
```
|
||
|
||
Then replace both inner scans with O(1) map lookups.
|
||
|
||
## Patch
|
||
|
||
`defects/helm/patch/helm-0001.patch`
|
||
|
||
## Unit test
|
||
|
||
`defects/helm/unit/HelmTest.java`
|