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

## Finding

Three O(n²) defects in Apache Hadoop HDFS's block management and balancer. All patched. Patches ready for upstream review.

## The Defects

**hadoop-0002 (PATCHED — HIGH):** `hdfs/server/blockmanagement/PendingReconstructionBlocks.java`

```java
// O(B×R) pending block scan per reconstruction event:
for (Block block : pendingBlocks) {
    if (pendingSet.contains(block)) {  // List.contains() O(R) per block
        ...
    }
}
// O(B×R) total
```

`List.contains()` O(R) scan per block in pending reconstruction tracking. **Measured ratio: 301×.**

**hadoop-0003 (PATCHED — HIGH):** `hdfs/server/blockmanagement/StoragePolicySatisfier.java`

```java
// O(T×N×E) storage policy evaluation scan:
for (StorageType type : requiredTypes) {
    for (DatanodeStorageInfo info : storages) {
        if (excludedStorages.contains(info)) { ... }  // O(E) scan per storage
    }
}
// O(T×N×E) total
```

`excludedStorages.contains()` O(E) scan inside nested T×N loop. **Measured ratio: 49×.**

**hadoop-0004 (PATCHED — HIGH):** `hdfs/server/balancer/Dispatcher.java`

```java
// srcBlocks ArrayList.contains() in block selection + MovedBlocks.locations ArrayList.contains() in move recording:
if (srcBlocks.contains(block)) { ... }           // O(B) per selection pass
if (locations.contains(storageInfo)) { ... }     // O(B) per move record
// O(B²) at both sites in block balancing
```

Two `ArrayList.contains()` O(B) scans in block selection and move-recording loops. **O(B²) at both sites**. Fix: `HashSet` at both sites. **Measured ratio: 1000×.**

## Complexity Proof

**hadoop-0002:** For B=301 blocks, R reconstruction records:
- O(B×R) — **301× measured ratio.**
- Fixed: `HashSet<Block>` → O(B).

**hadoop-0003:** For T types, N storages, E=49 excluded:
- O(T×N×E) — **49× measured ratio.**
- Fixed: `HashSet<DatanodeStorageInfo>` → O(T×N).

**hadoop-0004:** For B=1000 blocks in the balancer:
- Two `ArrayList.contains()` O(B) scans per block selection and move recording
- Total: **O(B²) at both sites**
- **1000× measured ratio.** Fixed: `HashSet` at both sites.

## Impact

All Apache Hadoop HDFS deployments. hadoop-0002 affects block reconstruction — which runs continuously in large clusters to maintain replication factor after node failures. hadoop-0003 affects storage policy satisfaction — which runs during block placement for tiered storage (SSD/HDD/Archive policies). hadoop-0004 affects the HDFS balancer — which runs to equalize disk usage across DataNodes and is triggered manually or on schedule in large clusters. Apache Hadoop is deployed in large-scale data warehousing and big data processing. Large clusters with many blocks and storage tiers hit all three defects under normal operation.

## The Fix

**hadoop-0002:** Replace `pendingBlocks` `List` with `LinkedHashSet`:

```java
// Before
if (pendingSet.contains(block)) { ... }  // O(R) List scan

// After
// CWE-407 fix: HashSet for O(1) contains() instead of O(R) List scan.
Set<Block> pendingHashSet = new HashSet<>(pendingBlocks);
if (pendingHashSet.contains(block)) { ... }
```

**hadoop-0003:** Pre-build `HashSet<DatanodeStorageInfo>` from `excludedStorages`.

**hadoop-0004:** Replace `srcBlocks` and `locations` `ArrayList` with `HashSet` at both sites in `Dispatcher.java`.

## Patch

`defects/hadoop/patch/hadoop-0002-0003-blockmanagement-hashset.patch`
`defects/hadoop/patch/hadoop-0004-dispatcher-hashset.patch`

## What We Ask

1. Confirm receipt and assign a GitHub Security Advisory or JIRA reference.
2. Validate the patch against your HDFS block management test suite.
3. Assess CVE eligibility — hadoop-0002 fires continuously in large cluster block reconstruction.
4. Coordinate a disclosure date — we are targeting 90 days from first contact.

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