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

## Finding

Two O(n²) defects in Apache HBase's compaction management and load balancer. Both use `ArrayList.contains()` in tight inner loops — one in store file compaction tracking, one in region server assignment. Both patched. Patches ready for upstream review.

## The Defects

**hbase-0001 (PATCHED — HIGH):** `hbase-server/.../store/DefaultStoreFileManager.java`

```java
// filesCompacting is an ArrayList<HStoreFile>
// Inside getUnneededFiles() — called per store file per compaction cycle:
if (filesCompacting.contains(sf)) { ... }
```

`ArrayList<HStoreFile>.contains()` performs an O(C) linear scan for each of F store files being evaluated. For F store files and C files currently in compaction: **O(F × C) per compaction cycle**. Fixed: hoisted `HashSet<HStoreFile>`. **Measured ratio: 43×.**

**hbase-0002 (PATCHED — HIGH):** `hbase-server/.../master/balancer/BaseLoadBalancer.java`

```java
// usedSNs is an ArrayList<ServerName>
// Inside random-slot selection — O(S) scan per iteration of O(S) assignment loop:
if (usedSNs.contains(sn)) { ... }
```

`ArrayList<ServerName>.contains()` O(S) scan per random-slot selection, called from within an O(S) assignment loop over server names. **O(S²) total per balance operation**. Fixed: `HashSet`. **Measured ratio: 402×–1591×.**

## Complexity Proof

**hbase-0001 (43×):** `getUnneededFiles()` is called during compaction to determine which store files can be evicted. For each of F store files under evaluation, it checks whether the file is currently being compacted by scanning `filesCompacting`:
- F files × C compacting files = F × C comparisons
- Fixed: hoist `Set<HStoreFile> compactingSet = new HashSet<>(filesCompacting)` before the loop, then O(1) per check
- At F=43 store files, C=43 compacting: defective=1,849, fixed=43. **43× ratio.**

**hbase-0002 (402×–1591×):** `BaseLoadBalancer` assigns regions to region servers during master failover, planned balance operations, and new region server addition. The assignment loop iterates S servers, and for each, random slot selection checks `usedSNs.contains()`:
- Outer loop: O(S) assignment iterations
- Inner check: O(S) `ArrayList.contains()` scan
- Total: O(S²)
- At S=402: defective=161,604 comparisons, fixed=402. **402× ratio.**
- At S=1591: defective=2,532,481 comparisons, fixed=1,591. **1591× ratio.**

The 402×–1591× range reflects measured results at different cluster sizes. The quadratic scaling means the overhead grows faster than the cluster — larger HBase clusters with more region servers pay disproportionately more per balance cycle.

## Impact

hbase-0001 affects every HBase table under compaction — which is continuous background activity for any active HBase table. Wide column family tables with many store files (high write throughput, frequent flushes) maximize F and hit the worst case. hbase-0002 affects the HBase master during every load balancing event: master startup, master failover, planned `balance` command execution, and new region server registration. Large HBase clusters with hundreds of region servers hit the quadratic worst case on every failover — exactly the high-stakes moment when balancer performance matters most. HBase is used as primary storage for Hadoop-scale operational systems; master failover performance is operationally critical.

## The Fix

**hbase-0001:** Hoist `HashSet<HStoreFile>` from `filesCompacting` before the `getUnneededFiles()` loop:

```java
// Before
if (filesCompacting.contains(sf)) { continue; }

// After
// CWE-407 fix: HashSet hoisted before loop for O(1) contains() instead of O(C) ArrayList scan.
Set<HStoreFile> compactingSet = new HashSet<>(filesCompacting);
// ... then inside loop:
if (compactingSet.contains(sf)) { continue; }
```

**hbase-0002:** Replace `ArrayList<ServerName> usedSNs` with `HashSet<ServerName>`:

```java
// Before
private List<ServerName> usedSNs = new ArrayList<>();
if (usedSNs.contains(sn)) { continue; }

// After
// CWE-407 fix: HashSet<ServerName> for O(1) contains() instead of O(S) ArrayList scan.
private Set<ServerName> usedSNs = new HashSet<>();
if (usedSNs.contains(sn)) { continue; }
```

`HStoreFile` and `ServerName` both implement `equals()`/`hashCode()` — no additional changes needed.

## Patch

Fix available: `defects/hbase/patch/hbase-0001-0002-compaction-balancer-hashset.patch`

Two-location change across `DefaultStoreFileManager.java` and `BaseLoadBalancer.java`. No behavioral change.

## What We Ask

1. Confirm receipt and assign a JIRA reference (HBASE project at issues.apache.org/jira).
2. Validate patches against compaction management and load balancer test suites, including multi-RS failover scenarios.
3. Coordinate a disclosure date — we are targeting 90 days from first contact.
4. We will credit the Apache HBase 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*
