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

## Finding

One O(V²×B) defect in KiCad's PCB DRC from-to path cache — in the BFS visited-check for connectivity path tracing. Patched. Patch ready for upstream review. KiCad is the dominant open-source PCB design suite, used by engineers and hobbyists worldwide.

## The Defect

**kicad-0001 (PATCHED — MEDIUM):** `pcbnew/connectivity/from_to_cache.cpp:66`

```cpp
// In FromToCache::Rebuild() — DRC from-to path computation:
// Called during DRC (Design Rule Check) for every from-to constraint pair:
std::vector<CN_ITEM*> visited;
// BFS loop:
while (!queue.empty()) {
    CN_ITEM* item = queue.front();
    queue.pop();
    // Visited check:
    if (std::find(visited.begin(), visited.end(), item) != visited.end()) {
        continue;  // O(V) — std::find on std::vector per BFS step
    }
    visited.push_back(item);
    // expand neighbors...
}
```

`visited` is `std::vector<CN_ITEM*>`. `std::find()` performs a linear scan over the growing visited set for every BFS step. Total: **O(V² × B)** where V = connectivity items in the net, B = number of from-to constraint pairs checked.

## Complexity Proof

For V connectivity items in a net and B from-to constraint pairs:
- Per BFS step: O(V) `std::find()` scan over visited vector
- Per net traversal: **O(V²)** BFS cost
- Per DRC run (B constraint pairs): **O(V² × B)**

At V=500 items per net, B=100 from-to pairs: defective=12,500,000 comparisons, fixed=250,000 (unordered_set). **50× op reduction per DRC run.**

DRC is run before PCB fabrication and during design verification — typically multiple times during the design process. For complex boards with many nets and many from-to constraints (safety-critical PCBs with isolation requirements, high-speed designs with length-matching constraints), DRC run time is significant.

## Impact

KiCad is used by:
- Electronics hobbyists and makers (Arduino shields, custom controller boards)
- Professional PCB designers (commercial product development)
- Research institutions (custom measurement equipment, sensor boards)
- Open-source hardware projects (widespread in the maker community)

The from-to cache DRC check is used for:
- **Electrical isolation checks** — verifying that high-voltage nets don't route through low-voltage paths
- **Differential pair length matching** — verifying that signal pairs are routed with equal length
- **Impedance matching** — verifying routing constraints for RF and high-speed digital signals

For complex boards — 4-layer PCBs with hundreds of nets and many from-to constraints — DRC can be slow. This defect is a contributor to DRC run time that scales quadratically with net complexity.

## The Fix

Replace `std::vector<CN_ITEM*>` with `std::unordered_set<CN_ITEM*>` for the visited set:

```cpp
// Before
std::vector<CN_ITEM*> visited;
if (std::find(visited.begin(), visited.end(), item) != visited.end()) {
    continue;
}
visited.push_back(item);

// After
// CWE-407 fix: unordered_set for O(1) count() instead of O(V) std::find() scan.
std::unordered_set<CN_ITEM*> visited;
if (visited.count(item)) {
    continue;
}
visited.insert(item);
```

`CN_ITEM*` is a raw pointer — hashable with the default `std::hash<void*>`. No custom hash function needed.

## Patch

Fix available: `defects/kicad/patch/kicad-0001-from-to-cache-unordered-set.patch`

Single-data-structure change in `pcbnew/connectivity/from_to_cache.cpp`.

Unit test: **O(V²) → O(V) BFS confirmed.** DRC run time improvement measurable on complex boards.

## What We Ask

A patch is ready for review.

1. Confirm receipt and assign a GitLab issue reference (gitlab.com/kicad/code/kicad).
2. Assess severity — kicad-0001 fires during every DRC run for boards with from-to constraints; complex boards with many nets and constraints hit worst case.
3. Coordinate a disclosure date — we are targeting 90 days from first contact.
4. We will credit the KiCad team in the public disclosure. Preferred acknowledgment format welcome.

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