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

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

3.7 KiB Raw Permalink Blame History Unescape Escape