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

// 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>:

// 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

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

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

2.4 KiB Raw Permalink Blame History Unescape Escape