UNDF: UNDF-2026-000000470

nginx-0002 — ngx_http_upstream_hide_headers_hash dedup O(H²) config init

Ecosystem

nginx (C)

Severity

LOW — configuration init only, not per-request

Location

src/http/ngx_http_upstream.c Function: ngx_http_upstream_hide_headers_hash Lines ~7101–7152

Description

When merging the hide_headers and pass_headers configuration, nginx builds a deduplicated list before hashing. The dedup step uses a nested linear scan:

for (i = 0; i < conf->hide_headers->nelts; i++) {  // outer: H user headers
    hk = hide_headers.elts;
    for (j = 0; j < hide_headers.nelts; j++) {      // inner: O(H) scan
        if (ngx_strcasecmp(h[i].data, hk[j].key.data) == 0) {
            goto exist;
        }
    }
    // push new entry
}

Complexity: O(H²) where H = number of hide_headers + default headers.

In practice H is small (< 30) so this is a negligible defect. Noted for completeness; the subsequent ngx_hash_init already builds an O(1) lookup structure for the hot path.

CWE

CWE-407: Inefficient Algorithmic Complexity (config-init, low impact)

Fix (sketch)

Use the hide_headers ngx_hash being built as the dedup structure:

// After building the default headers into the hash, check membership
// via ngx_hash_find before pushing each user header, instead of the
// O(H) linear scan.
key = ngx_hash_key_lc(h[i].data, h[i].len);
if (ngx_hash_find(&temp_hash, key, h[i].data, h[i].len)) {
    goto exist;
}

Speedup

H=30: negligible absolute, 30x algorithmic improvement.

Status

PATCHED (patch in this file)

1.6 KiB Raw Permalink Blame History Unescape Escape