# Valkey — CWE-407 Disclosure Brief
**2026-03-27 · Patch available — awaiting upstream merge**

## Finding

Three O(n²) defects in Valkey's set intersection and ACL management — the same defects as Redis, since Valkey is a Redis fork. All three were present at fork time and remain unpatched upstream in the Valkey codebase. Patches ready for upstream review.

## The Defects

**valkey-0001 (PATCHED — HIGH):** `t_set.c`

```c
/* Same lpFind defect as redis-0001 — SINTER listpack inner loop: */
if (lpFind(lp, element, ...) != NULL) { ... }
/* O(N×M) per SINTER command (128×) */
```

`lpFind` O(M) linear scan per element during `SINTER`. Identical to redis-0001. **Measured ratio: 128×.**

**valkey-0002 (PATCHED — HIGH):** `acl.c`

```c
/* Same channel superset defect as redis-0002: */
listSearchKey(selector->channels, channel)  /* O((S×C)²) */
```

`listSearchKey` O(n) channel scan. Identical to redis-0002. **Measured ratio: 250×.**

**valkey-0003 (PATCHED — HIGH):** `src/acl.c:1217,1236`

```c
/* Same ACLSetSelector key-pattern dedup defect as redis-0003: */
if (listSearchKey(selector->patterns, newpat) != NULL) { ... }
/* O(P²) adding P key-patterns (500×) */
```

`listSearchKey` O(P) dedup per key-pattern in `ACLSetSelector`. Identical to redis-0003. **Measured ratio: 500×.**

## Complexity Proof

All three defects carry over from Redis with identical complexity characteristics:
- **valkey-0001:** O(N×M) per SINTER — **128× measured ratio.**
- **valkey-0002:** O((S×C)²) ACL channel — **250× measured ratio.**
- **valkey-0003:** O(P²) ACL key-pattern — **500× measured ratio.**

## Impact

All Valkey deployments. Valkey is the Linux Foundation fork of Redis 7.2, adopted after the Redis license change. It is now the primary open-source Redis-compatible server for distributions (Debian, Ubuntu, Fedora). All Valkey deployments using `SINTER` and ACL selectors are affected. The defects are inherited from Redis and have not been fixed in the Valkey fork.

## The Fix

Identical fixes to the corresponding Redis patches. See redis.md for detailed fix descriptions.

**valkey-0001:** Replace `lpFind` inner scan with hash set for smaller set.

**valkey-0002:** Replace `listSearchKey` with `HashSet` for channel tracking.

**valkey-0003:** Parallel `dict` alongside `selector->patterns`:

```c
/* Before */
if (listSearchKey(selector->patterns, newpat) != NULL) { ... }

/* After */
/* CWE-407 fix: parallel dict for O(1) pattern dedup. */
if (dictFind(selector->patterns_dict, newpat) != NULL) { ... }
```

## Patch

`defects/valkey/patch/valkey-0001-0002-0003-sinter-acl-hashset.patch`

## What We Ask

1. Confirm receipt and assign a GitHub Security Advisory or issue reference.
2. Validate the patch against your SINTER and ACL test suites.
3. Assess CVE eligibility — valkey-0003 measured at 500× on ACL key-pattern management.
4. Coordinate a disclosure date — we are targeting 90 days from first contact.

Contact: see cover email. This brief is confidential until coordinated disclosure.
