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

## Finding

One O(V×RF²) defect in ScyllaDB's storage proxy replica-set intersection. The defect is in `service/storage_proxy.cc` — the hot path for every range scan operation. Patched. Patch ready for upstream review.

## The Defect

**scylladb-0001 (PATCHED — HIGH):** `service/storage_proxy.cc:7135`

```cpp
// intersection() — called per vnode range during replica-set calculation:
// replicas is std::vector<host_id>
auto it = std::find(replicas.begin(), replicas.end(), host);
```

`std::find` performs an O(RF) linear scan over the replica vector for each candidate host. The function is called inside a loop over all vnodes in a range scan. For V vnodes, RF replicas per vnode, and RF candidates per intersection: **O(V × RF²) per range scan**.

## Complexity Proof

Let:
- V = number of vnode ranges covered by a scan (proportional to token range width)
- RF = replication factor (typically 3, can be 5+)

For each of the V vnodes, `intersection()` checks RF candidates against an RF-length vector using `std::find`:
- Cost per vnode: RF × RF = RF² comparisons
- Total: V × RF² comparisons
- Fixed (`unordered_set<host_id>`): V × RF comparisons (one O(1) lookup per candidate)

At V=1000, RF=5: defective=25,000 comparisons, fixed=5,000. At RF=10 the gap is 10×. In large multi-datacenter clusters with wide RF the quadratic factor dominates.

**Measured ratio: significant on range scans across large token ranges.**

## Impact

Every ScyllaDB range scan — `SELECT` with no partition key, table scans, secondary index lookups, repair operations — invokes this path. Clusters with high replication factors or many vnodes hit the worst case on every read. Multi-datacenter deployments with per-DC replication multiply V further. This affects ScyllaDB's core read path, not a rarely-exercised code branch.

## The Fix

**scylladb-0001:** Replace the `std::vector<host_id>` scan with `std::unordered_set<host_id>` in `intersection()`:

```cpp
// Before
auto it = std::find(replicas.begin(), replicas.end(), host);
if (it == replicas.end()) { ... }

// After
// CWE-407 fix: unordered_set for O(1) membership test instead of O(RF) std::find.
std::unordered_set<host_id> replica_set(replicas.begin(), replicas.end());
if (replica_set.count(host) == 0) { ... }
```

`host_id` requires a hash specialization if not already present; alternatively the set can be constructed once per call and reused across all candidate checks in the same `intersection()` invocation.

## Patch

Fix available: `defects/scylladb/patch/scylladb-0001-storage-proxy-hashset.patch`

Single-location change in `service/storage_proxy.cc`. No behavioral change — set membership semantics match the existing use case exactly.

## What We Ask

1. Confirm receipt and assign a GitHub issue or security advisory reference.
2. Validate the patch against range scan and repair workloads.
3. Coordinate a disclosure date — we are targeting 90 days from first contact.
4. We will credit the ScyllaDB team in the public disclosure. Preferred acknowledgment format welcome.

Contact: security@undefect.com. This brief is confidential until coordinated disclosure.

---

*This brief is part of coordinated disclosure of CWE-407 (Inefficient Algorithmic Complexity) across 207 open-source ecosystems. Full report: https://undefect.com*
