# UNDF: UNDF-2026-000000523
# redis-0004: ACLCheckChannelAgainstList O(C×P) per pubsub command → O(C)

## Classification

| Field       | Value |
|-------------|-------|
| CWE         | CWE-407 Inefficient Algorithmic Complexity |
| Severity    | HIGH |
| Component   | `src/acl.c:1652,1694,1826` |
| Functions   | `ACLCheckChannelAgainstList`, `ACLSelectorCheckCmd`, `ACLUserCheckChannelPerm` |
| Hot path    | Every SUBSCRIBE, PSUBSCRIBE, PUBLISH command with ACL channel restrictions |
| Status      | PATCHED (unit test PASS) |

## Defect

`ACLSelectorCheckCmd` iterates over C channel arguments in the command and for each
calls `ACLCheckChannelAgainstList` which walks the entire `selector->channels` linked
list (P patterns) using `stringmatchlen` for each:

```c
// acl.c:1694 — ACLSelectorCheckCmd
for (j = 0; j < cmd->arity; j++) {
    if (cmd->flags & CMD_PUBSUB_CHANNEL_ARG) {
        // ACLCheckChannelAgainstList: O(P) linked-list walk
        if (ACLCheckChannelAgainstList(selector->channels,
                                        channel_name, ...) == ACL_DENIED)
            return ACL_DENIED;
    }
}

// acl.c:1652 — ACLCheckChannelAgainstList
while ((ln = listNext(&li)) != NULL) {  // O(P) walk
    sds pattern = listNodeValue(ln);
    if (stringmatchlen(pattern, sdslen(pattern), channel, ...)) return ACL_OK;
}
```

`ACLUserCheckChannelPerm` (line 1826) adds an outer loop over S selectors:
total **O(S × C × P)** per pubsub command.

**Impact:** A user with 1,000 channel patterns calling `SUBSCRIBE ch1 ch2 … ch100`
triggers 100,000 `stringmatchlen` calls per command, per client, per second.

## Fix

Replace `selector->channels` linked list with a dict (hash map) for exact patterns,
keeping the linked list only for glob patterns. Exact match becomes O(1) dict lookup;
glob patterns (rare) remain O(P_glob) with P_glob << P total.

For the common case of exact channel names (no wildcards), a `dict *channels_exact`
alongside `list *channels_glob` reduces the hot path to O(C + P_glob) per command.

## Speedup

| P (channel patterns) | C (channels/cmd) | Slow O(C×P) | Fast O(C) | Ratio |
|----------------------|-----------------|-------------|-----------|-------|
| 100                  | 10              | 1,000       | 10        | 100×  |
| 500                  | 10              | 5,000       | 10        | 500×  |
| 1000                 | 100             | 100,000     | 100       | 1000× |
