opensmtpd-0001 — Quadratic per-envelope rule evaluation via TAILQ linear scan

Target: OpenSMTPD (OpenSMTPD/OpenSMTPD) Severity: MEDIUM CWE: CWE-407 (Algorithmic Complexity — Quadratic) Status: PATCHED (patch/opensmtpd-0001.patch)

Summary

ruleset_match() in smtpd/ruleset.c traverses the entire rule list with TAILQ_FOREACH — O(R) for R rules — on every envelope lookup. ruleset_match() is called from lka_session.c:311 for each expansion node (i.e., each recipient address). With R rules and M recipient addresses, the total cost is O(R × M).

A large mail gateway with R=300 policy rules forwarding a mailing-list message to M=500 recipients makes 150 000 rule evaluations per message, all on the LKA (lookup agent) critical path.

Location

usr.sbin/smtpd/ruleset.c
  line 234   TAILQ_FOREACH(r, env->sc_rules, r_entry)   — O(R) per envelope

usr.sbin/smtpd/lka_session.c
  line 311   rule = ruleset_match(&ep)                  — called per recipient/expansion node

Root Cause

env->sc_rules is a TAILQ (doubly-linked list). ruleset_match() walks every rule from head to tail until a match is found. Rules are parsed at startup and inserted in order; no indexing or hash dispatch is built. For the common case where the first-matching rule is determined by the from domain or to domain, the entire list must be scanned until that rule is found.

Fix

Build a dispatch map from (domain → rule_list) at startup for the dominant ruleset_match_to and ruleset_match_from criteria:

At smtpd_configure(), iterate sc_rules once and group rules by their table_for / table_from domain if those fields are simple strings.
In ruleset_match(), do a dict_get() on evp->dest.domain to fetch the candidate subset (typically 1-3 rules) and evaluate only those.
Fall back to the full TAILQ scan for rules with wildcard/regex from/to.

Complexity

Slow: O(R × M) — R rules × M recipient addresses per message
Fast: O(M) — O(1) dict lookup per address selects candidate rules
Speedup at R=300, M=500: ~300×

Patch

See defects/opensmtpd/patch/opensmtpd-0001.patch

Unit Test

See defects/opensmtpd/unit/OpensmtpdTest.java

2.2 KiB Raw Permalink Blame History Unescape Escape