# UNDF: UNDF-2026-000000413
# haproxy-0002 — flt_spoe.c SPOE message/group duplicate detection O(N²)

## Ecosystem
haproxy (C)

## Severity
LOW — config parsing only, not hot path

## Location
`src/flt_spoe.c`
- Line 1580: `while (*args[cur_arg])` + `list_for_each_entry(ph, &curmphs, list)` + `strcmp`
- Line 1604: `while (*args[cur_arg])` + `list_for_each_entry(ph, &curgphs, list)` + `strcmp`
- Line 1991: `while (*args[cur_arg])` + `list_for_each_entry(ph, &curgrp->phs, list)` + `strcmp`

## Description
When parsing `messages` and `groups` directives in a SPOE agent section,
haproxy checks for duplicate names by walking the linked list of already-
registered placeholders for every new argument:

```c
while (*args[cur_arg]) {              // outer: N args
    list_for_each_entry(ph, &curmphs, list) { // inner: O(M) list scan
        if (strcmp(ph->id, args[cur_arg]) == 0) { // string comparison
            /* duplicate found */
        }
    }
    ...
    cur_arg++;
}
```

Complexity: O(N²) for N message/group names in a SPOE `messages` directive.

Fix: accumulate seen names in a hash table (e.g., haproxy's `eb_root`
ebtree or a simple open-addressing hashtable) and check O(1) per insertion.

## CWE
CWE-407: Inefficient Algorithmic Complexity

## Fix (sketch)
Replace linked-list scan with `ebtst_lookup` on a per-parse-context
`eb_root`:

```c
struct eb_root seen_msgs = EB_ROOT;
while (*args[cur_arg]) {
    // O(log N) ebtree lookup instead of O(N) list walk
    if (ebtst_lookup(&seen_msgs, args[cur_arg])) {
        ha_alert("duplicate '%s'\n", args[cur_arg]);
        goto out;
    }
    // insert into ebtree
    struct ebmb_node *node = calloc(1, sizeof(*node) + strlen(args[cur_arg]) + 1);
    memcpy(node->key, args[cur_arg], strlen(args[cur_arg]) + 1);
    ebst_insert(&seen_msgs, node);
    ...
    cur_arg++;
}
```

## Speedup
N=100 names: 100x reduction (O(N²) → O(N log N)).

## Status
PATCHED (patch in this file)
