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

// 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

// 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

// 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

// 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:

// 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

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

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

4.6 KiB Raw Permalink Blame History Unescape Escape