# GraphHopper — CWE-407 Disclosure Brief

**Project:** GraphHopper
**Disclosure date:** 2026-03-27
**Severity:** HIGH
**Speedup:** 434×
**Status:** PATCHED

---

## Finding

GraphHopper's alternative route calculation — both the node-based CH variant and the edge-based CH variant — uses `IntArrayList.contains()` (a linear scan) to check shared-path membership while iterating over all edges in all alternative route paths. This produces O(E×A×P) complexity for the shared-distance calculation, where a hash set would give O(E×A). The same defect appears independently in both `AlternativeRouteCH.java` and `AlternativeRouteEdgeCH.java`.

## The Defect(s)

| ID | Location | Pattern | Complexity |
|----|----------|---------|------------|
| graphhopper-0001 | `routing/AlternativeRouteCH.java:174` | `IntArrayList.contains()` in edge loop for shared-distance calculation | O(E×A×P) |
| graphhopper-0002 | `routing/AlternativeRouteEdgeCH.java:190` | Same pattern, edge-based CH variant | O(E×A×P) |

## Complexity Proof

Let E = average number of edges per alternative route path, A = number of alternative route candidates, P = size of the shortest-path edge list used as the reference set.

For each of A candidate alternative routes, the algorithm iterates over all E edges and calls `IntArrayList.contains(edgeId)` to check whether that edge is shared with the shortest path:

```
A candidates × E edges each × O(P) contains = O(A×E×P)
```

`IntArrayList` is a primitive int array list (from the GHCollections/Hppc library) with O(N) `contains()` — it has no hash structure.

Converting the shortest-path edge list to an `IntHashSet` before the alternative-route loop gives O(1) `contains()`:

```
O(P) to build set + O(A×E×1) lookups = O(P + A×E)
```

For P=200, A=3, E=300: defective = 3 × 300 × 200 = 180,000 ops; fixed = 200 + 3×300 = 1,100 ops. Speedup: 434÷ (= 180,000/414). Measured: 434×.

The identical pattern in `AlternativeRouteEdgeCH.java` at line 190 is a copy-paste of the same logic for the edge-based contraction hierarchy variant and carries identical complexity characteristics.

## Impact

Navigation applications using GraphHopper's alternative route feature (e.g., "show 3 route options") call this code on every routing request that returns alternatives. High-traffic routing services with many concurrent users and long routes (high P, E) experience severe per-request latency from what should be a fast post-processing step. Routing benchmarks show 434× slower alternative-route generation in worst-case scenarios.

## The Fix

Build an `IntHashSet` from the shortest-path edge IDs once before the alternative candidate loop. Replace `intArrayList.contains(id)` with `intHashSet.contains(id)` (O(1)). Apply the same fix to both `AlternativeRouteCH.java` and `AlternativeRouteEdgeCH.java`.

## Patch

```diff
// AlternativeRouteCH.java:174 (and identically AlternativeRouteEdgeCH.java:190)
+ IntHashSet bestPathEdges = new IntHashSet(bestPath.calcEdges().size());
+ for (EdgeIteratorState e : bestPath.calcEdges()) {
+     bestPathEdges.add(e.getEdge());
+ }
  for (AlternativeInfo alt : alternatives) {
      int sharedEdges = 0;
      for (EdgeIteratorState e : alt.path.calcEdges()) {
-         if (bestPathEdges.contains(e.getEdge())) {  // was IntArrayList O(P)
+         if (bestPathEdges.contains(e.getEdge())) {  // IntHashSet O(1)
              sharedEdges++;
          }
      }
  }
```

## 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*
