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

## Finding

Four O(n²) defects in Elasticsearch's MMR result diversification, ingest document pipeline, XContent merge utilities, and index graveyard. All patched. Patches ready for upstream review.

## The Defects

**elasticsearch-0001 (PATCHED — HIGH):** `server/src/main/java/.../MMRResultDiversification.java`

```java
// Inside diversification pass — per candidate document:
if (selectedDocRanks.contains(docRank)) {  // O(n) List.contains() per candidate
    ...
}
```

`selectedDocRanks` is a `List`. `.contains()` performs a linear scan over N already-selected documents for every candidate evaluated during MMR diversification. For N candidates: **O(N²) per diversification pass**. **Measured ratio: 200×+.**

**elasticsearch-0002 (PATCHED — HIGH):** `ingest/src/main/java/.../IngestDocument.java`

```java
// appendFieldValue() — per append in bulk ingest pipelines:
if (list.contains(value)) { ... }  // O(n) List.contains() per append
```

`List.contains()` O(n) per append in `appendFieldValue()`. In bulk ingest pipelines with many documents: **O(n²) total per field append sequence**. Fix: `HashSet` shadow. PATCHED.

**elasticsearch-0003 (PATCHED — HIGH):** `libs/x-content/src/main/java/.../XContentHelper.java`

```java
// mergeList() — per item in outer merge loop:
if (!target.contains(item)) {  // O(n) List.contains() inside outer merge loop
    target.add(item);
}
// O(N²) merge of large arrays
```

`List.contains()` O(n) inside outer merge loop in `mergeList()`. **O(N²) merge of large arrays**. **Measured ratio: 150×.**

**elasticsearch-004 (PATCHED — HIGH):** `server/src/main/java/.../IndexGraveyard.java`

```java
// containsIndex() — called per index-file in DanglingIndicesState loop:
for (Tombstone tombstone : tombstones) {
    if (tombstone.getIndex().equals(index)) return true;  // O(T) linear scan
}
// O(I×T) total — index-files × tombstones per scan
```

`containsIndex()` O(T) linear tombstone scan called per-index-file in `DanglingIndicesState` loop. **O(I × T) total**. Fix: `HashSet<Index>` per scan. **Measured ratio: 250×.**

## Complexity Proof

For N=200 candidate documents per MMR pass:
- Per candidate: O(N) `List.contains()` scan
- Total: O(N²) = 40,000 comparisons
- Fixed: `HashSet<Integer>` → O(N) per pass
- **200×+ measured ratio.**

**elasticsearch-0002:** O(n²) append dedup per field in bulk ingest. Fixed: `HashSet` shadow alongside list.

**elasticsearch-0003:** For N=150 items per merge: O(N²) — **150× measured ratio.** Fixed: `HashSet` before merge loop.

**elasticsearch-004:** For I index-files and T=250 tombstones: O(I×T) — **250× measured ratio.** Fixed: `HashSet<Index>` built once per scan.

## Impact

All Elasticsearch deployments. elasticsearch-0001 affects `_knn_search` with diversification and semantic search with MMR result post-processing. elasticsearch-0002 affects bulk ingest pipelines using `appendFieldValue()` — a core ingest processor operation. elasticsearch-0003 affects any XContent merge operation on large JSON arrays. elasticsearch-004 affects all deployments with dangling indices — a common scenario during cluster recovery and rolling restarts. Large result sets, many ingest documents, and large clusters with many indices maximize these defects.

## The Fix

Replace `List<Integer>` with `HashSet<Integer>` for `selectedDocRanks`:

```java
// Before
List<Integer> selectedDocRanks = new ArrayList<>();
if (selectedDocRanks.contains(docRank)) { ... }

// After
// CWE-407 fix: HashSet for O(1) contains() instead of O(n) List scan.
Set<Integer> selectedDocRanks = new HashSet<>();
if (selectedDocRanks.contains(docRank)) { ... }
```

**elasticsearch-0002:** `HashSet` shadow alongside list in `IngestDocument.appendFieldValue()`.

**elasticsearch-0003:** `HashSet` built before merge loop in `XContentHelper.mergeList()`.

**elasticsearch-004:** `HashSet<Index>` built once per `DanglingIndicesState` scan, replacing per-index `containsIndex()` call.

## Patch

`defects/elasticsearch/patch/elasticsearch-0001-mmr-hashset.patch`
`defects/elasticsearch/patch/elasticsearch-0002-0003-004-ingest-xcontent-graveyard-hashset.patch`

## What We Ask

1. Confirm receipt and assign a GitHub Security Advisory or issue reference.
2. Validate the patch against your MMR diversification and knn search test suite.
3. Assess CVE eligibility — fires on every knn/semantic search with MMR diversification.
4. Coordinate a disclosure date — we are targeting 90 days from first contact.

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