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

## Finding

One O(n²) defect in Ninja's dependency log. `deps_log.cc` uses `std::find` during depfile merge operations, causing O(D²) overhead per target when merging dependency records with many deps. Patch ready for upstream review.

## The Defects

**ninja-0001 (PATCHED — HIGH):** `src/deps_log.cc`

```cpp
// Depfile merge — per dep per target:
for (const auto& dep : new_deps) {
    auto it = std::find(existing_deps.begin(), existing_deps.end(), dep);
    // O(D) std::find per dep — O(D²) total merge
    if (it == existing_deps.end()) {
        existing_deps.push_back(dep);
    }
}
```

`std::find` O(D) scan per dep during depfile merge. For D deps per target: **O(D²) total**. **Measured ratio: 500×.**

## Complexity Proof

For D=500 deps per target:
- Merge: D × O(D) = O(D²) = 250,000 comparisons
- Fixed: `unordered_set<string_id>` → O(D)
- **500× measured ratio.**

## Impact

All Ninja users — Ninja is the dominant low-level build system used by Chrome, LLVM, Android, and projects built with CMake, Meson, GN, and similar meta-build systems. Depfile merging runs during incremental builds. Targets with large dependency sets (generated files with many includes, auto-generated source files) hit O(D²) per merge. Large C++/C projects with deep include trees are most affected.

## The Fix

Replace `std::find` + `push_back` with `unordered_set<string_id>` dedup:

```cpp
// Before
auto it = std::find(existing_deps.begin(), existing_deps.end(), dep);
if (it == existing_deps.end()) existing_deps.push_back(dep);

// After
// CWE-407 fix: unordered_set for O(1) dedup instead of O(D) std::find scan.
if (existing_deps_set.insert(dep).second) {
    existing_deps.push_back(dep);
}
```

## Patch

`defects/ninja/patch/ninja-0001-deps-log-unordered-set.patch`

## What We Ask

1. Confirm receipt and assign a GitHub Security Advisory or issue reference.
2. Validate the patch against your deps log and depfile merge test suite.
3. Assess CVE eligibility — 500× overhead on depfile merge for large dependency sets.
4. Coordinate a disclosure date — we are targeting 90 days from first contact.

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