UNDF: UNDF-2026-000000471

nginx-0003 — ngx_http_variables_init_vars O(V×K) startup nested scan

Ecosystem

nginx (C)

Severity

LOW — startup/config-init only, not per-request

Locations

src/http/ngx_http_variables.c function ngx_http_variables_init_vars lines ~2802–2860
src/stream/ngx_stream_variables.c function ngx_stream_variables_init_vars lines ~1253–1309

Description

During startup, nginx resolves indexed variable names to their handlers by walking all indexed variables (V) and for each one scanning the full variables_keys hash-keys array (K) with ngx_strncmp:

for (i = 0; i < cmcf->variables.nelts; i++) {         // outer: V indexed vars
    for (n = 0; n < cmcf->variables_keys->keys.nelts; n++) {  // inner: K key entries
        if (v[i].name.len == key[n].key.len
            && ngx_strncmp(v[i].name.data, key[n].key.data, v[i].name.len) == 0)
        {
            // found — set handler
            goto next;
        }
    }
    // also scans prefix_variables O(P) per indexed var
}

variables_keys contains all registered variable names from all compiled-in modules (core ~50, plus upstream, SSL, geo, map, gzip, etc.) plus any user- defined variables. variables (indexed) grows with the number of distinct $var references in the config file. Both V and K are O(N) in the number of variable references, giving O(V×K) = O(N²) total startup cost.

The identical defect is copy-pasted into ngx_stream_variables_init_vars in the stream subsystem.

Complexity

Dimension	Variable
V	indexed variables (`cmcf->variables.nelts`)
K	registered variable keys (`variables_keys->keys.nelts`)
Complexity	O(V × K) ≈ O(V²) since K ≥ V

Typical production configs: V=50–200, K=80–300. At V=200, K=300: 60,000 string comparisons at startup vs ~200 with a hash lookup.

Fix

Build a temporary ngx_hash_t or eb_root from variables_keys first, then resolve each indexed variable with a single O(1) hash lookup:

// Build temporary name→handler map
ngx_hash_init_t tmp_hash;
// ... init and build from variables_keys ...

for (i = 0; i < cmcf->variables.nelts; i++) {
    av = ngx_hash_find(&tmp_variables_hash,
                       ngx_hash_strlow(v[i].name.data, v[i].name.len),
                       v[i].name.data, v[i].name.len);
    if (av) {
        v[i].get_handler = av->get_handler;
        // ...
    }
}

nginx already has variables_hash built later in the same function — the temporary hash can reuse the same infrastructure.

CWE

CWE-407: Inefficient Algorithmic Complexity

Speedup

At V=200, K=300: 300x reduction (60,000 → 200 comparisons).

Status

PATCHED (patch in this file)

2.7 KiB Raw Permalink Blame History Unescape Escape