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

## Finding

One O(S×R×S') defect in FoundationDB's data distribution relocation queue. The defect is in `DDRelocationQueue.actor.cpp` — the path that decides whether a data move can launch based on server overlap. Patched. Patch ready for upstream review.

## The Defect

**foundationdb-0001 (PATCHED — HIGH):** `DDRelocationQueue.actor.cpp:465`

```cpp
// canLaunchSrc() — called per relocation request, double loop over servers:
// servers is std::vector<UID>
int count = std::count(servers.begin(), servers.end(), srcId);
```

`std::count` performs an O(S') linear scan over the `servers` vector for each entry in the outer loop over R relocations, which itself iterates S source servers. The double loop combined with the inner `std::count` produces **O(S × R × S') per launch eligibility check**. For S ≈ S' (servers appear in both the candidate and active relocation lists), this degrades to O(S² × R).

## Complexity Proof

Let:
- S = number of source servers in the relocation being evaluated
- R = number of active relocations being checked for conflict
- S' = size of the `servers` vector on each active relocation (number of servers involved)

`canLaunchSrc()` iterates R active relocations. For each, it iterates S source server IDs from the candidate relocation. For each (relocation, server) pair, `std::count` scans the full S'-length `servers` vector:
- Cost: S × R × S' comparisons
- When S ≈ S' (common — relocations involve the same server pool): S² × R
- Fixed (`unordered_set<UID>` per relocation): S × R lookups at O(1) each = O(S × R)

At S=50, R=100, S'=50: defective=250,000 comparisons, fixed=5,000. **50× improvement at these parameters; scales worse as cluster grows.**

The data distribution subsystem in FoundationDB is invoked continuously during shard movement, failure recovery, and storage server rebalancing. This path runs in the critical loop gating data movement decisions.

## Impact

Every FoundationDB cluster running data distribution — which is always active during normal operation, failure recovery, and explicit rebalancing — executes this path. Clusters under recovery from storage server failure or during initial data distribution after adding storage servers maximize R (many concurrent relocations) and S (large teams). Wide replication configurations multiply S further. This defect slows the data distribution actor loop, delaying recovery and rebalancing decisions across the cluster.

## The Fix

**foundationdb-0001:** Build an `unordered_set<UID>` from each active relocation's server list before the inner scan:

```cpp
// Before
int count = std::count(servers.begin(), servers.end(), srcId);

// After
// CWE-407 fix: unordered_set for O(1) membership instead of O(S') std::count scan.
std::unordered_set<UID> server_set(servers.begin(), servers.end());
int count = server_set.count(srcId);  // O(1) per lookup
```

`UID` requires a hash specialization; FoundationDB already provides `std::hash<UID>` in the codebase. The set can be constructed once per active relocation entry and reused across all S source server checks in the same `canLaunchSrc()` call.

## Patch

Fix available: `defects/foundationdb/patch/foundationdb-0001-ddrelocation-hashset.patch`

Single-location change in `DDRelocationQueue.actor.cpp`. No behavioral change — `unordered_set::count()` returns 0 or 1 matching the semantics of `std::count` for unique server IDs.

## What We Ask

1. Confirm receipt and assign a GitHub issue or security advisory reference.
2. Validate the patch against data distribution and failure recovery simulation tests.
3. Coordinate a disclosure date — we are targeting 90 days from first contact.
4. We will credit the FoundationDB 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*
