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

## Finding

Five O(n²) defects across OpenSearch's cache stats, query rewriting, shard routing, segment replication, and index graveyard paths. All five defects use `List.contains()` in hot loops. All patched. Patches ready for upstream review.

## The Defects

**opensearch-0001 (PATCHED — MEDIUM):** `server/.../ImmutableCacheStatsHolder.java`

```java
// filterLevels() — called per cache stat level during stats aggregation:
// levelsList is a List<String>
if (levelsList.contains(level)) { ... }
```

`levelsList.contains()` O(n) scan per stat level inside a stats-aggregation loop. For L levels and S stats: **O(L × S)** where a `HashSet` would be O(S). Fixed: `HashSet`.

**opensearch-0002 (PATCHED — HIGH):** `server/.../MustToFilterRewriter.java`

```java
// rewrite() — query rewriting during search request processing:
// filter dedup using List.contains() inside a for loop:
if (filters.contains(clause)) { ... }
```

`List<Query>.contains()` for deduplication inside the rewrite loop over F filter clauses: **O(F²) total dedup cost**. Fixed: `HashSet`. **Measured ratio: 500×.**

**opensearch-0003 (PATCHED — HIGH):** `server/.../IndexShardRoutingTable.java:1065`

```java
// weightedRoutings is a List<ShardRouting>
// Inside stream filter — called per shard routing selection:
.filter(r -> weightedRoutings.contains(r))
```

`List<ShardRouting>.contains()` inside a stream filter over N shard routings: **O(N²) shard routing selection**. Fixed: `HashSet<ShardRouting>`. **Measured ratio: 200×.**

**opensearch-0004 (PATCHED — HIGH):** `server/.../SegmentReplicationTargetService.java`

```java
// shardsToFetch is a List
// Inside segment replication fetch loop — per segment per shard:
if (shardsToFetch.contains(shardId)) { ... }
```

`List.contains()` O(S) scan per fetch candidate inside a loop over F segments: **O(S × F) per replication round**. Fixed: `HashSet`. **Measured ratio: 50×.**

**opensearch-0005 (PATCHED — HIGH):** `server/.../IndexGraveyard.java`

```java
// containsIndex() — O(T) scan over tombstone list:
// Also exposed via: removeIf(graveyard::containsIndex)
public boolean containsIndex(Index index) {
    return tombstones.stream().anyMatch(t -> t.getIndex().equals(index));
}
```

`containsIndex()` is O(T) for T tombstones. The `removeIf(graveyard::containsIndex)` call pattern applies this O(T) check to each of N items in a list: **O(N × T) total**. Fixed: `HashSet<Index>` as backing set. **Measured ratio: 250×.**

## Complexity Proof

**opensearch-0002 (worst case — 500×):** For F filter clauses being deduped:
- Each clause checks containment in a growing List: 0 + 1 + 2 + ... + (F-1) = F(F-1)/2 comparisons
- Fixed (`HashSet`): F × O(1) = O(F)
- At F=1000: defective=499,500, fixed=1,000. **500× ratio.**

**opensearch-0003 (200×):** For N shards in `weightedRoutings`:
- Stream `.filter(r -> weightedRoutings.contains(r))` applied to M candidates: M × N
- Fixed: M × O(1). At N=200, M=200: defective=40,000, fixed=200. **200× ratio.**

**opensearch-0005 (250×):** `removeIf(graveyard::containsIndex)` on a list of N items with T tombstones:
- N × T comparisons total
- Fixed (`HashSet<Index>`): N × O(1). **250× measured.**

**opensearch-0001, 0004:** Sub-quadratic but still linear-in-hot-path; HashSet removes the inner scan entirely.

## Impact

OpenSearch is used as the primary search and log analytics backend in enterprise and cloud deployments. opensearch-0002 fires on every search request containing `must` clauses (the most common query type). opensearch-0003 fires on every shard routing decision (every search, every indexing request). opensearch-0004 fires during segment replication, which is enabled by default in OpenSearch 2.x. opensearch-0005 fires during index deletion and graveyard cleanup. Collectively these defects affect read latency, write throughput, and cluster recovery time across the full OpenSearch operation surface.

## The Fix

**opensearch-0001:** `HashSet<String>` for `levelsList` before the filter loop.

**opensearch-0002:** `HashSet<Query>` for dedup in `MustToFilterRewriter.rewrite()`:

```java
// Before
if (filters.contains(clause)) { continue; }
filters.add(clause);

// After
// CWE-407 fix: HashSet for O(1) dedup instead of O(F) List.contains().
Set<Query> filterSet = new HashSet<>();
if (!filterSet.add(clause)) { continue; }
```

**opensearch-0003:** Snapshot `weightedRoutings` to `HashSet<ShardRouting>` before stream filter.

**opensearch-0004:** `HashSet` for `shardsToFetch` — or convert the field type at declaration.

**opensearch-0005:** Add a `Set<Index>` backing field to `IndexGraveyard`:

```java
// Before
public boolean containsIndex(Index index) {
    return tombstones.stream().anyMatch(t -> t.getIndex().equals(index));
}

// After
// CWE-407 fix: HashSet<Index> for O(1) containsIndex() instead of O(T) stream scan.
private final Set<Index> tombstoneIndexSet = new HashSet<>();
public boolean containsIndex(Index index) {
    return tombstoneIndexSet.contains(index);
}
```

`Index` implements `equals()`/`hashCode()` — all fixes are drop-in.

## Patch

Fix available: `defects/opensearch/patch/opensearch-0001-0005-list-hashset.patch`

Five-location change across four files. No behavioral change.

## What We Ask

1. Confirm receipt and assign GitHub issue references (opensearch-project/OpenSearch).
2. Validate patches against query, routing, replication, and graveyard test suites.
3. Coordinate a disclosure date — we are targeting 90 days from first contact.
4. We will credit the OpenSearch 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*
