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
60 lines
2 KiB
Markdown
60 lines
2 KiB
Markdown
# redis-0002: getUpcomingChannelList O(S×C²) quadratic channel membership
|
||
|
||
**Target:** redis/redis
|
||
**Severity:** MEDIUM
|
||
**CWE:** CWE-407 (Inefficient Algorithmic Complexity)
|
||
**File:** `src/acl.c:1952` (`getUpcomingChannelList`)
|
||
**Status:** PATCHED
|
||
|
||
## Description
|
||
|
||
`getUpcomingChannelList(user *new, user *original)` builds a flat linked list
|
||
(`upcoming`) of all channel patterns from `new`'s selectors, then for each
|
||
channel pattern in `original`'s selectors calls `listSearchKey(upcoming, ...)`.
|
||
|
||
`listSearchKey` is an O(n) walk of the `upcoming` list. With S selectors and C
|
||
channel patterns per selector the `upcoming` list grows to S×C entries.
|
||
The outer loop also iterates S×C patterns.
|
||
|
||
Result: O((S×C)²) in the worst case — quadratic in total channel-pattern count.
|
||
|
||
In practice, heavily compartmentalized users (many selectors, many channel ACL
|
||
rules) hit this during `ACL SETUSER` and at any `SUBSCRIBE`/`PSUBSCRIBE` event
|
||
that triggers client-kill evaluation.
|
||
|
||
## Hot paths
|
||
|
||
- `ACL SETUSER` — triggers `killPubsubClientsIfNeeded`, which calls
|
||
`getUpcomingChannelList` for each affected client.
|
||
- `SUBSCRIBE` / `PSUBSCRIBE` evaluation when ACL rules restrict channels.
|
||
|
||
## Root cause
|
||
|
||
`src/acl.c:1935–1960`:
|
||
```c
|
||
list *upcoming = listCreate(); // O(S×C) entries
|
||
...
|
||
while((lpn = listNext(&lpi)) && match) {
|
||
if (!listSearchKey(upcoming, listNodeValue(lpn))) { // O(S×C) per call
|
||
match = 0;
|
||
```
|
||
|
||
## Fix
|
||
|
||
Replace the `upcoming` linked list with a hash table (`dictCreate` with
|
||
`dictTypeSds` or a simple `rax`). Build the set from `new`'s selectors, then
|
||
check each of `original`'s channel patterns with O(1) lookup. Total cost
|
||
becomes O(S×C) instead of O((S×C)²).
|
||
|
||
See patch: `defects/redis/patch/0002-acl-upcoming-channels-dict.patch`
|
||
|
||
## Also affects
|
||
|
||
- valkey/valkey — identical `getUpcomingChannelList` code path.
|
||
|
||
## Ops ratio (unit test)
|
||
|
||
S=4 selectors, C=50 channels each (200 total):
|
||
- slow ops: 200 × 200 = 40,000
|
||
- fast ops: 200 (one pass build) + 200 (O(1) lookups) = 400
|
||
- speedup: **100×**
|