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
78 lines
2.9 KiB
Markdown
78 lines
2.9 KiB
Markdown
# istio-0001: virtualHostMatch slices.Contains(vh.Domains) O(n) inside VH×patch nested loop → O(n²)
|
||
|
||
**Target:** istio/istio
|
||
**Severity:** HIGH
|
||
**CWE:** CWE-407 (Inefficient Algorithmic Complexity)
|
||
**File:** `pilot/pkg/networking/core/envoyfilter/rc_patch.go`
|
||
**Status:** PATCHED
|
||
|
||
## Description
|
||
|
||
`virtualHostMatch()` calls `slices.Contains(vh.Domains, match.DomainName)` to
|
||
test whether a VirtualHost serves a given domain. This function is called from
|
||
`patchVirtualHost()`, which is invoked in a loop over every VirtualHost in a
|
||
route configuration. For each VirtualHost there is an inner loop over all
|
||
applicable EnvoyFilter patches. Each `slices.Contains` call is O(D) where D =
|
||
number of domains on the VirtualHost. The overall complexity is O(VH × P × D)
|
||
— cubic in the worst case.
|
||
|
||
In a large Istio mesh with many services and EnvoyFilter rules, VirtualHosts
|
||
routinely have dozens of domain aliases (service name, FQDN, short name,
|
||
wildcard variants). A single xDS push iterates this product for every
|
||
listener/route-config pair.
|
||
|
||
| Location | Pattern |
|
||
|----------|---------|
|
||
| `rc_patch.go:346` | `slices.Contains(vh.Domains, match.DomainName)` — O(D) membership test |
|
||
| `rc_patch.go:116` | `virtualHostMatch(virtualHosts[idx], rp)` called per VH per patch |
|
||
| `rc_patch.go:79` | outer loop: `for i := range routeConfiguration.VirtualHosts` |
|
||
|
||
## Root cause
|
||
|
||
```go
|
||
// rc_patch.go:327 — O(D) per call
|
||
func virtualHostMatch(vh *route.VirtualHost, rp *model.EnvoyFilterConfigPatchWrapper) bool {
|
||
match := rp.Match.GetRouteConfiguration().GetVhost()
|
||
if match == nil { return true }
|
||
return (match.Name == "" || match.Name == vh.Name) &&
|
||
(match.DomainName == "" || slices.Contains(vh.Domains, match.DomainName))
|
||
}
|
||
|
||
// rc_patch.go:112 — called in O(VH × P) loop
|
||
for i := range routeConfiguration.VirtualHosts {
|
||
...
|
||
virtualHostMatch(virtualHosts[idx], rp) // O(D) inside
|
||
```
|
||
|
||
With 500 VirtualHosts × 20 patches × 15 domains each: 150,000 string
|
||
comparisons per route-config push.
|
||
|
||
## Fix
|
||
|
||
Build a `map[string]*route.VirtualHost` keyed by domain before the patch loop,
|
||
so each domain lookup is O(1).
|
||
|
||
```go
|
||
// Build domain→VH index once, outside the patch loop
|
||
domainIndex := make(map[string]*route.VirtualHost, len(routeConfiguration.VirtualHosts))
|
||
for _, vh := range routeConfiguration.VirtualHosts {
|
||
for _, d := range vh.Domains {
|
||
domainIndex[d] = vh
|
||
}
|
||
}
|
||
|
||
// virtualHostMatch: O(1)
|
||
func virtualHostMatchFast(vh *route.VirtualHost, rp *model.EnvoyFilterConfigPatchWrapper,
|
||
domainIndex map[string]*route.VirtualHost) bool {
|
||
match := rp.Match.GetRouteConfiguration().GetVhost()
|
||
if match == nil { return true }
|
||
if match.Name != "" && match.Name != vh.Name { return false }
|
||
if match.DomainName == "" { return true }
|
||
return domainIndex[match.DomainName] == vh
|
||
}
|
||
```
|
||
|
||
## Ops/ns numbers (Java benchmark)
|
||
|
||
See `defects/istio/unit/IstioTest.java`.
|
||
At VH=500, P=20, D=15: slow ~150,000 ops, fast ~10,000 ops → >10× speedup.
|