# UNDF: UNDF-2026-000000563
# uwsgi-0001: HTTP Header Duplicate Detection O(H²) — CWE-407

**Severity:** HIGH
**CWE:** CWE-407 (Inefficient Algorithmic Complexity)
**Component:** uWSGI HTTP request parser — header deduplication
**Affected files:**
- `proto/http.c:417`
- `plugins/http/http.c:778`
- `plugins/http/spdy3.c:207`

---

## Defect

When parsing incoming HTTP/SPDY request headers, uWSGI builds a linked list
(`uwsgi_string_list`) of seen header names to detect duplicates (RFC 7230:
combine same-name headers with `, `). For each header H_i parsed, it calls
`uwsgi_string_list_has_item()` which does a linear walk of all previously
seen headers:

```c
// proto/http.c:417  (same pattern in http.c:778 and spdy3.c:207)
usl = uwsgi_string_list_has_item(headers, base, key_len);
```

`uwsgi_string_list_has_item` (core/strings.c):
```c
struct uwsgi_string_list *uwsgi_string_list_has_item(
        struct uwsgi_string_list *list, char *key, size_t keylen) {
    struct uwsgi_string_list *usl = list;
    while (usl) {                          // O(H) walk
        if (keylen == usl->len) {
            if (!memcmp(key, usl->value, keylen)) {
                return usl;
            }
        }
        usl = usl->next;
    }
    return NULL;
}
```

Outer loop: H headers, each triggers an O(H) scan → **O(H²) total**.

An attacker or a proxy that sends many HTTP headers (e.g. many `Cookie:`,
`Accept-Encoding:`, `X-Custom-*:` lines) causes quadratic CPU work in the
uWSGI worker parsing the request.

---

## Complexity

| N (headers) | Operations (defect) | Operations (fix) |
|-------------|---------------------|------------------|
| 10          | 55                  | 10               |
| 50          | 1,275               | 50               |
| 100         | 5,050               | 100              |
| 200         | 20,100              | 200              |
| 500         | 125,250             | 500              |

Speedup at H=500: **250x**.

---

## Fix

Replace the linked-list dedup scan with a small open-address hash table
keyed on (normalised) header name. Since HTTP header count is bounded by
`limit-request-fields` (default 100, max ~100), a fixed-size hash table
with 256 slots suffices.

```c
// Fixed: use a stack-allocated hash map for O(1) lookup
#define HDR_HASH_SIZE 256
#define HDR_HASH_MASK (HDR_HASH_SIZE - 1)

struct hdr_entry { char *key; size_t len; struct uwsgi_string_list *usl; };
struct hdr_entry hdr_map[HDR_HASH_SIZE];
memset(hdr_map, 0, sizeof(hdr_map));

// For each parsed header:
uint32_t slot = fnv1a(base, key_len) & HDR_HASH_MASK;
// linear probe on collision (collision rate low for realistic header counts)
while (hdr_map[slot].key) {
    if (hdr_map[slot].len == key_len &&
        !memcmp(hdr_map[slot].key, base, key_len)) {
        usl = hdr_map[slot].usl;   // found duplicate
        break;
    }
    slot = (slot + 1) & HDR_HASH_MASK;
}
if (!usl) {
    // new header — add to list and record in hash map
    usl = uwsgi_string_new_list(&headers, NULL);
    hdr_map[slot].key = base;
    hdr_map[slot].len = key_len;
    hdr_map[slot].usl = usl;
}
```

All three affected files (`proto/http.c`, `plugins/http/http.c`,
`plugins/http/spdy3.c`) require the same fix within their respective
header-parsing loops.

---

## References

- RFC 7230 §3.2.2 — Field Order: multiple same-name headers MUST be merged
- `core/strings.c:45` — `uwsgi_string_list_has_item` implementation
