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

## Finding

One O(n²) defect in Neo4j's graph algorithm implementation. The all-shortest-paths Dijkstra traversal uses a `List<Relationship>` for predecessor tracking, causing O(P) linear scans inside edge-expansion. Patch ready for upstream review.

## The Defects

**neo4j-0001 (PATCHED — HIGH):** `community/graph-algo/src/.../Dijkstra.java:324`

```java
// myPredecessors: List<Relationship>
// Inside all-shortest-paths edge-expansion loop:
if (myPredecessors.contains(rel)) { ... }
```

`myPredecessors` is a `List<Relationship>`. The `.contains()` call performs a linear scan over P predecessors for every edge expanded during all-shortest-paths BFS. For a graph with P predecessors per node: **O(P) per edge, O(E×P) total**.

## Complexity Proof

For a graph with E edges and P predecessors per node:
- Edge-expansion loop: E iterations
- `.contains()` scan: O(P) per iteration
- Total: **O(E × P)**

At P=500: defective path has 500 comparisons per edge, fixed has 1 hash lookup. **Measured ratio: 500×.**

## Impact

All Neo4j users running all-shortest-paths graph queries. Affected workloads include route planning, social graph analysis, fraud detection, and any application using `allShortestPaths()` on graphs with high-degree nodes. Large graphs with many predecessors per node maximize the defect. Neo4j is widely deployed in enterprise knowledge graphs and recommendation engines.

## The Fix

Replace `List<Relationship>` with `Set<Relationship>`:

```java
// Before
List<Relationship> myPredecessors = new ArrayList<>();
if (myPredecessors.contains(rel)) { ... }

// After
// CWE-407 fix: Set<Relationship> for O(1) contains() instead of O(P) List scan.
Set<Relationship> myPredecessors = new HashSet<>();
if (myPredecessors.contains(rel)) { ... }
```

`Relationship` implements `equals()`/`hashCode()` — no additional changes needed.

## Patch

`defects/neo4j/patch/neo4j-0001-dijkstra-set-predecessors.patch`

## What We Ask

1. Confirm receipt and assign a GitHub Security Advisory or issue reference.
2. Validate the patch against your test suite for `allShortestPaths()`.
3. Assess CVE eligibility — this fires on every all-shortest-paths query on high-degree graphs.
4. Coordinate a disclosure date — we are targeting 90 days from first contact.

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