# UNDF: UNDF-2026-000000583
# curl-0003: Curl_hsts O(N) linked-list scan → O(1) hash map

## Classification

| Field       | Value |
|-------------|-------|
| CWE         | CWE-407 Inefficient Algorithmic Complexity |
| Severity    | MEDIUM |
| Component   | `lib/hsts.c:225` (`Curl_hsts`), `lib/hsts.c:389` (`hsts_add`) |
| Hot path    | HSTS file load O(N²) + per-request HTTPS upgrade check O(N) |
| Status      | PATCHED (unit test PASS) |

## Defect

`Curl_hsts` performs an O(N) linear scan of the entire HSTS entry list on every call:

```c
// hsts.c:225
struct stsentry *Curl_hsts(struct hsts *h, const char *hostname, ...) {
  for(e = Curl_llist_head(&h->list); e; e = n) {  // O(N) every call
    struct stsentry *sts = Curl_node_elem(e);
    if((hlen == ntail) && curl_strnequal(hostname, sts->host, hlen))
      return sts;
  }
  return NULL;
}
```

**Two O(N²) impact paths:**

1. **File load** (`hsts_load` → `hsts_add` → `Curl_hsts` for dedup): N calls, each
   O(N) → **O(N²)** total. A 1,000-entry HSTS file performs 500,000 comparisons.

2. **Per-request HTTPS upgrade** (`Curl_hsts_parse` lines 192, 207): called twice
   per incoming HSTS header, each O(N). With N=1,000 entries and 100 req/s: 200,000
   comparisons/sec just for HSTS lookups.

## Fix

Replace `Curl_llist` in `struct hsts` with a hash table keyed on hostname (case-insensitive):

```c
// hsts_add: O(1) insert
// Curl_hsts: O(1) lookup
struct stsentry *Curl_hsts(struct hsts *h, const char *hostname, ...) {
    return Curl_hashmap_get_icase(h->entries, hostname, hlen);
}
```

Speedup: ~500× at N=1,000 (O(N²)=500K → O(N)=1K at file load).
