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
2.2 KiB
tor-0002: nodelist_add_node_and_family family-ID scan — O(N·F²) smartlist_contains_string
Target: Tor
File: src/feature/nodelist/nodelist.c
Function: nodelist_add_node_and_family / nodes_have_common_family_id
CWE: CWE-407 — Inefficient Algorithmic Complexity
Severity: HIGH
Status: PATCHED
Description
nodelist_add_node_and_family() adds all relays that share a verified family ID
with a given node. The implementation iterates over every node in the consensus
(all_nodes, size N) and for each pair calls nodes_have_common_family_id():
// nodelist.c line 2337-2340
SMARTLIST_FOREACH(all_nodes, const node_t *, node2, {
if (nodes_have_common_family_id(node, node2)) {
smartlist_add(sl, (void *)node2);
}
});
nodes_have_common_family_id() itself is:
// nodelist.c line 2190-2200
static bool
nodes_have_common_family_id(const node_t *a, const node_t *b)
{
const smartlist_t *ids_a = node_get_family_ids(a);
const smartlist_t *ids_b = node_get_family_ids(b);
if (ids_a == NULL || ids_b == NULL)
return false;
SMARTLIST_FOREACH(ids_a, const char *, id, {
if (smartlist_contains_string(ids_b, id)) // O(|ids_b|) linear scan
return true;
});
return false;
}
smartlist_contains_string() performs a full linear scan of ids_b.
Total cost: O(N × |ids_a| × |ids_b|) — equivalently O(N·F²) where N is the consensus size (~7 000 relays) and F is family IDs per node. The function is called from path selection during circuit building, which is latency-critical.
Fix
Before the outer SMARTLIST_FOREACH(all_nodes) loop, build a string-keyed set
from node's own family IDs (the fixed ids_a). Then for each node2, iterate
node2's ids_b and perform O(1) lookups against the set. This reduces the
per-pair check to O(|ids_b|) and the total to O(N·F).
The patch uses Tor's existing strmap_t (string-keyed hash map) as the set:
insert each id from ids_a once before the outer loop, then call
strmap_get(id_set, id) inside the inner loop.
Patch
defects/tor/patch/tor-0002-nodelist-family-id-strmap.patch
Unit Test
defects/tor/unit/TorNodelistFamilyTest.java