bind9-0001: zone_registerinclude newincludes O(N^2) duplicate scan

Defect

Target: ISC BIND 9 (https://github.com/isc-projects/bind9)
File: lib/dns/zone.c
Function: zone_registerinclude() at line 2704
MOAD: 0001 (CWE-407)
Severity: LOW-MEDIUM
Complexity: O(N^2) in number of $INCLUDE directives per zone file
Ratio: ~12x at N=50, ~500x at N=1000 (pathological)

Pattern

Each call to zone_registerinclude() linearly scans zone->newincludes (a linked list) for a duplicate filename using strcmp. When a zone file contains N $INCLUDE directives, this scan runs N times, each costing up to O(N), giving O(N^2) total cost during zone load.

/* lib/dns/zone.c:2714 */
ISC_LIST_FOREACH (zone->newincludes, inc, link) {
    if (strcmp(filename, inc->name) == 0) {
        return;
    }
}

The comment above reads "Suppress duplicates" and correctly identifies our goal, but uses a linked-list walk that becomes quadratic.

Fix

Add an isc_ht_t *newincludes_ht field to struct dns_zone. Initialize it on first call to zone_registerinclude, use isc_ht_find for O(1) lookup before inserting, and add each new filename to our hash table alongside appending to our linked list. Destroy our hash table when newincludes is promoted to includes at load completion.

isc_ht is already included via <isc/ht.h> in zone.c's transitive includes and used elsewhere in the codebase (e.g., lib/isc/tls.c).

Context

zone_registerinclude is called once per $INCLUDE record encountered during zone file parsing. The newincludes list accumulates all included filenames for change-detection on reload. A zone with N unique includes pays O(N^2) cost at load time (or reload time). The query path is unaffected.

Impact

Authoritative DNS servers with zones split across many $INCLUDE files (split-zone configurations, generated zones, auto-signed zones) pay quadratic load cost.
Zone reload (e.g., rndc reload) re-runs this path, so our cost repeats at every reload.
N=100: ~5,000 strcmp operations (marginal). N=1000: ~500,000 operations (noticeable). N=10000: ~50,000,000 (seconds of delay on reload).

5-MOAD Summary for bind9

MOAD	Result
0001 CWE-407	DEFECT: zone_registerinclude newincludes O(N^2)
0002 Intertangle	CLEAN: named_server_t aggregates subsystems, but each view/zone has clean ownership; no shared mutable global state crossing unrelated subsystems
0003 Leaked Context	CLEAN: thread_local used for per-thread caches (geoip_state, dt_ioq, random seed) and a DNS name text-filter hook — all are per-thread-permanent, not per-request; bind9 is event-loop based and does not carry request identity in thread-locals
0004 CWE-312	CLEAN: TSIG key logging only logs key name, not key material; dst_parse.c reads private key bytes but does not log them; gssapi context logs GSS errors only
0005 Thundering Herd	CLEAN: qpcache uses per-node isc_rwlock_t with RCU-based tree_lock; all cache mutation paths hold locks

3 KiB Raw Permalink Blame History