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
mysql-0001 — SHOW GRANTS USING: O(R²) role membership scan
Target: mysql/mysql-server
Severity: HIGH
CWE: CWE-407 (Inefficient Algorithmic Complexity)
File: sql/auth/sql_authorization.cc
Lines: 4875–4898
Status: PATCHED
Defect
mysql_show_grants() validates a SHOW GRANTS ... USING <role_list> statement
by iterating every role in using_roles (outer loop, line 4880) and for each
calling std::find on granted_roles — a std::vector<std::pair<Role_id,bool>>
(line 4882) — and then std::find_if on mandatory_roles — also a std::vector
(line 4884).
Both inner searches are O(G) and O(M) respectively, giving a total complexity of
O(U × (G + M)) where U = |using_roles|, G = |granted_roles|, M =
|mandatory_roles|.
When a user has many granted roles (e.g. in an RBAC-heavy application with
hundreds of roles, or the mandatory-roles list is long), every
SHOW GRANTS ... USING call burns O(n²) CPU inside the privilege validator.
This path is also reached on every SET ROLE + implicit SHOW which means
application-tier connection pooling can trigger it on every checkout.
Root Cause
List_of_granted_roles is std::vector<std::pair<Role_id, bool>> (defined in
sql/auth/auth_internal.h:268). No hash index is built before the loop.
Fix
Build an unordered_set of the authid strings from granted_roles and a
parallel unordered_set from mandatory_roles before the outer loop.
Membership is then O(1) per lookup.
See: defects/mysql/patch/mysql-0001.patch
Benchmark
defects/mysql/unit/MysqlTest.java — SHOW GRANTS USING quadratic test case:
- Slow (vector find): ~O(n²), confirmed by ops count
- Fast (unordered_set): ~O(n), speedup ≥ 10× at n=500