russell@unturf.com
decacb5dbd
systemd-0004: seccomp_load_syscall_filter_set() in src/shared/seccomp-util.c uses strv_contains(added, name) — O(|added|) linear scan — inside NULSTR_FOREACH over ~537 KNOWN syscalls. On x86_64 (3 arches): ~484,000 string comparisons per service start with SeccompFilter=. Sibling function seccomp_load_syscall_filter_set_raw() already uses hashmap_contains for O(1); this function was left behind. Fix: build Set* from added strv before the NULSTR_FOREACH loop. MEDIUM severity. dbus-0001: bus_client_policy_optimize() in bus/policy.c iterates R rules and for each blanket deny/allow calls remove_rules_by_type_up_to() which scans backward from current position to head — O(R^2) total per new connection creation. At R=100 rules (realistic system bus): ~10,000 comparisons per connect. Fix: single O(R) reverse pass tracking last-seen blanket per rule type. MEDIUM. dbus 5-MOAD summary: MOAD-0001: dbus-0001 DEFECT (policy optimize O(R^2)) MOAD-0002: CLEAN (BusContext is standard daemon context, not a god object) MOAD-0003: CLEAN (single-threaded event loop, no thread-local state) MOAD-0004: CLEAN (_dbus_verbose is no-op in production builds) MOAD-0005: CLEAN (pending_activations hash table coalesces duplicate requests)
2.8 KiB
dbus-0001: bus_client_policy_optimize O(R^2) rule cleanup per connection
MOAD: MOAD-0001 (CWE-407) Severity: MEDIUM Speedup: ~50x at R=100 rules (per new connection creation) Language: C File: bus/policy.c:783-858 (bus_client_policy_optimize)
Description
Every time a new client connects to dbus-daemon, bus_policy_create_client_policy()
builds a per-connection rule list from default + UID + GID + mandatory policy
rules, then calls bus_client_policy_optimize() to remove rules that are
guaranteed to never fire because a later blanket deny/allow supersedes them.
The optimization iterates over all R rules and, for each blanket rule, calls
remove_rules_by_type_up_to() which walks backward from the current position
to the start of the list, removing earlier rules of the same type:
void bus_client_policy_optimize(BusClientPolicy *policy) {
DBusList *link = _dbus_list_get_first_link(&policy->rules);
while (link != NULL) { /* O(R) outer */
BusPolicyRule *rule = link->data;
...
if (remove_preceding)
remove_rules_by_type_up_to(policy, /* O(R) inner */
rule->type, link);
link = next;
}
}
remove_rules_by_type_up_to() scans from the head of the list to link,
comparing each rule type. In the worst case (many blanket rules), this is
O(R^2) total per connection.
A system bus with 100 default+uid+gid rules produces ~10,000 comparisons per new connection. A session bus serving a desktop environment with many services (GNOME, KDE) accumulates significant overhead as applications connect and reconnect.
The code itself notes this as a known issue — the FIXME comment in
bus_matchmaker_disconnected() acknowledges similar O(N) scan issues.
Fix
The optimize pass can be done in a single O(R) pass by processing rules in reverse order (from tail to head). When a blanket rule is encountered, mark all preceding same-type rules as removable in one forward scan, then do one cleanup pass. Alternatively, group rules by type during construction and apply "last blanket wins" logic without backward scanning.
A simpler fix: instead of walking backward to remove preceding rules, iterate from the tail of the list forward. Since "last rule wins", the first blanket encountered from the tail supersedes everything before it of the same type — so rules before the blanket can be dropped in O(1) by truncating the list up to that point.
Complexity drops from O(R^2) to O(R) per connection.
Speedup estimate
At R=100 rules (realistic system bus configuration):
- Defect: ~5,000 comparisons worst case
- Fix: ~100 comparisons
- Speedup: ~50x
At R=300 rules (large desktop session bus with many UID-specific rules):
- Defect: ~45,000 comparisons
- Fix: ~300 comparisons
- Speedup: ~150x