# Valhalla — CWE-407 Disclosure Brief

**Project:** Valhalla (routing engine)
**Disclosure date:** 2026-03-27
**Severity:** HIGH
**Speedup:** 200×
**Status:** PATCHED

---

## Finding

Valhalla's tile-build link classification code in `mjolnir/linkclassification.cc` calls `std::find` on a `forward_nodes` vector inside a loop over reverse nodes during road network classification. This produces O(F×R) per-tile behavior during map tile construction, where F and R are the counts of forward and reverse node entries respectively.

## The Defect(s)

| ID | Location | Pattern | Complexity |
|----|----------|---------|------------|
| valhalla-0001 | `mjolnir/linkclassification.cc:659` | `std::find(forward_nodes)` in reverse-node loop during tile build | O(F×R) |

## Complexity Proof

Let F = number of entries in the `forward_nodes` vector, R = number of reverse nodes being iterated in the outer loop.

During link (ramp/connector road) classification, the algorithm iterates over R reverse-direction node entries and for each one calls `std::find(forward_nodes.begin(), forward_nodes.end(), node_id)` to check whether the node is also present in the forward direction:

```
for each reverse_node in reverse_nodes:   # R iterations
    std::find(forward_nodes, node_id)     # O(F) scan
Total: O(R × F)
```

In dense urban tile regions, both F and R can number in the thousands (all link nodes in a tile). The product F×R reaches into the millions of comparisons for a single tile.

Replacing `forward_nodes` with `std::unordered_set<uint64_t>` reduces each lookup to O(1):

```
O(F) to build set + O(R) lookups = O(F + R)
```

For F=R=1000: defective = 10⁶ ops; fixed = 2000 ops. Measured speedup: 200×.

## Impact

Operators building or updating Valhalla tile sets from OSM data experience quadratic tile-build times for dense map regions. High-density urban tiles (city centers with many ramp/link roads) are disproportionately affected. Tile build pipelines for global map coverage involve millions of tiles; the O(F×R) defect multiplies across all link-heavy tiles, significantly extending total build time and infrastructure cost.

## The Fix

Before the reverse-node loop, construct `std::unordered_set<GraphId> forward_set(forward_nodes.begin(), forward_nodes.end())`. Replace the `std::find` call with `forward_set.count(node_id)`.

## Patch

```diff
  // mjolnir/linkclassification.cc:659
+ std::unordered_set<GraphId> forward_set(
+     forward_nodes.begin(), forward_nodes.end());
+
  for (const auto& reverse_node : reverse_nodes) {
-     if (std::find(forward_nodes.begin(), forward_nodes.end(),
-                   reverse_node.nodeid) != forward_nodes.end()) {
+     if (forward_set.count(reverse_node.nodeid)) {
          // classify as bidirectional link
      }
  }
```

## What We Ask

Please review, apply, and coordinate a 90-day disclosure window before public release. Reply to security@undefect.com.

---

*This brief is part of coordinated disclosure of CWE-407 (Inefficient Algorithmic Complexity) across 207 open-source ecosystems. Full report: https://undefect.com*
