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

## Finding

One O(F²) defect in LevelDB's version set compaction input selection. The defect is in `db/version_set.cc` — the `GetOverlappingInputs()` function used to select Level-0 files for compaction. An O(F) two-pass fix achieves 25× improvement. Patched. Patch ready for upstream review.

## The Defect

**leveldb-001 (PATCHED — HIGH):** `db/version_set.cc`

```cpp
// GetOverlappingInputs() — Level-0 file selection for compaction:
// When a file's range expands the search range, restart from i=0:
for (size_t i = 0; i < level_files.size(); ) {
    FileMetaData* f = level_files[i++];
    if (/* f overlaps [begin, end] */) {
        if (/* f expands the range */) {
            begin = ...; end = ...;
            inputs->clear();
            i = 0;  // ← restart scan from beginning
        }
    }
}
```

When a newly-added Level-0 file expands the search key range, the scan resets `i=0` and re-examines all previously-visited files. For F Level-0 files arranged so that each addition triggers a restart, the total number of file examinations is F + (F-1) + (F-2) + ... + 1 = **O(F²)**. Level-0 allows overlapping files by design, making this restart pattern a normal occurrence rather than a pathological case.

## Complexity Proof

Let:
- F = number of files at Level-0

Each range expansion resets the scan to `i=0`. In the worst case (files ordered such that each new overlap discovered is from an earlier file), the algorithm performs:
- Pass 1: scans F files, finds overlap at file F-1, expands range, resets
- Pass 2: scans F files again from the start, finds another overlap, resets
- ...up to F resets total

Total comparisons: up to F² in the worst case.

The O(F) two-pass fix:
1. First pass: collect all files overlapping the initial range → O(F)
2. Expand range based on collected files
3. Second pass: collect any additional files overlapping the expanded range → O(F)
- Total: O(F) regardless of overlap structure

At F=500 Level-0 files (reachable under heavy write load or delayed compaction): defective=250,000 comparisons, fixed=1,000. **Measured ratio: 25×.**

## Impact

Every LevelDB deployment that allows Level-0 file accumulation — which occurs under high write throughput, compaction backpressure, or write bursts — hits this path. LevelDB is the storage engine underlying Bitcoin Core's UTXO set, Chromium's IndexedDB, and numerous embedded key-value store use cases. `GetOverlappingInputs()` is called at compaction trigger time; under write pressure, when Level-0 has many files and compaction is most needed, this function is slowest. The defect creates a compaction latency spike precisely when write throughput is highest.

## The Fix

**leveldb-001:** Replace the restart-on-expansion loop with a two-pass O(F) algorithm:

```cpp
// Before — O(F²): reset i=0 on range expansion
for (size_t i = 0; i < level_files.size(); ) {
    FileMetaData* f = level_files[i++];
    if (AfterFile(ucmp, &user_begin, f) || BeforeFile(ucmp, &user_end, f)) {
        // no overlap
    } else {
        inputs->push_back(f);
        if (level == 0) {
            if (/* f expands range */) {
                begin = ...; end = ...;
                inputs->clear();
                i = 0;  // restart
            }
        }
    }
}

// After — O(F): two-pass, no restart
// CWE-407 fix: two-pass scan eliminates O(F²) restart-on-expansion for Level-0.
// Pass 1: expand range
for (size_t i = 0; i < level_files.size(); i++) { /* expand [begin,end] */ }
// Pass 2: collect all files in expanded range
for (size_t i = 0; i < level_files.size(); i++) { /* add overlapping files */ }
```

## Patch

Fix available: `defects/leveldb/patch/leveldb-001-getoverlapping-twopass.patch`

Single-function rewrite in `db/version_set.cc`. The two-pass approach is semantically equivalent: the final set of overlapping files is identical, just computed without quadratic restarts.

## What We Ask

1. Confirm receipt and assign a GitHub issue or security advisory reference.
2. Validate the patch against compaction selection tests, especially Level-0 overlap scenarios.
3. Coordinate a disclosure date — we are targeting 90 days from first contact.
4. We will credit the LevelDB 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*
