#286 - Route DFS has no global expansion budget — dense graph / unreachable goal = CPU blowup - code/cl8y-dex-terraclassic

Brouie commented

2026-06-03 07:19:51 +00:00

(Migrated from gitlab.com)

Severity: Medium
Reachability: Unauthenticated, via the solver (/route/solve*), which enumerates paths through this DFS.
Affected: find_paths_top_k (indexer/src/api/route_paths.rs).
Root cause: the DFS bounds depth (max_hops) and result count (max_paths), but has no global expansion/visit budget, so an unreachable goal on a dense graph enumerates the whole reachable simple-path set up to max_hops.

Summary

find_paths_top_k stops once it has collected max_paths results and won't go deeper than max_hops, and on_path blocks node revisits. But when the goal is unreachable (or only reachable via many routes), found never fills, so the DFS explores every simple path up to max_hops before returning — O(branching^max_hops). It runs synchronously inside the async handler, so it blocks the executor while it churns.

The token graph is attacker-influenceable: anyone can create pairs, which add edges. A dense subgraph plus a goal token with no route forces worst-case enumeration on every request. max_hops keeps it from being unbounded, but there's no cap on total node expansions, which is what you want against an adversarial graph.

Current codebase

route_paths.rs find_paths_top_k / inner dfs: caps are found.len() >= max_paths and path.len() >= max_hops; no counter on total dfs invocations / expansions.

Recommended direction

Add a global expansion budget: count dfs calls (or edges relaxed), abort and return what's found when it's hit, and flag the result as truncated.
Bound candidate enumeration feeding the solver, and prefer iterative deepening so cheap routes return fast without exploring the whole graph.

Acceptance criteria

A dense graph with an unreachable goal returns within a bounded expansion count, not full enumeration.
The response flags when the search was truncated by the budget.

Test plan (abuse)

case	expect
dense synthetic graph, unreachable goal	bounded work, truncated flag
normal graph, reachable goal	unchanged results

**Severity:** Medium **Reachability:** Unauthenticated, via the solver (`/route/solve*`), which enumerates paths through this DFS. **Affected:** `find_paths_top_k` (`indexer/src/api/route_paths.rs`). **Root cause:** the DFS bounds depth (`max_hops`) and result count (`max_paths`), but has no global expansion/visit budget, so an unreachable goal on a dense graph enumerates the whole reachable simple-path set up to `max_hops`. ## Summary `find_paths_top_k` stops once it has collected `max_paths` results and won't go deeper than `max_hops`, and `on_path` blocks node revisits. But when the goal is unreachable (or only reachable via many routes), `found` never fills, so the DFS explores every simple path up to `max_hops` before returning — O(branching^max_hops). It runs synchronously inside the async handler, so it blocks the executor while it churns. The token graph is attacker-influenceable: anyone can create pairs, which add edges. A dense subgraph plus a goal token with no route forces worst-case enumeration on every request. `max_hops` keeps it from being unbounded, but there's no cap on total node expansions, which is what you want against an adversarial graph. ## Current codebase - `route_paths.rs` `find_paths_top_k` / inner `dfs`: caps are `found.len() >= max_paths` and `path.len() >= max_hops`; no counter on total `dfs` invocations / expansions. ## Recommended direction 1. Add a global expansion budget: count `dfs` calls (or edges relaxed), abort and return what's found when it's hit, and flag the result as truncated. 2. Bound candidate enumeration feeding the solver, and prefer iterative deepening so cheap routes return fast without exploring the whole graph. ## Acceptance criteria - [ ] A dense graph with an unreachable goal returns within a bounded expansion count, not full enumeration. - [ ] The response flags when the search was truncated by the budget. ## Test plan (abuse) | case | expect | |---|---| | dense synthetic graph, unreachable goal | bounded work, truncated flag | | normal graph, reachable goal | unchanged results |

PlasticDigits commented

2026-06-03 10:55:42 +00:00

(Migrated from gitlab.com)

The pairs need to be stored in postrgres via factory with token indexes, so that all pairs associated with a token can be looked up qwuickly with 0 LCD/RPC calls. Once thats done, recheck if the recommended fixes are still needed or if correctly storing/indexing the data is sufficient.

Brouie commented

2026-06-04 05:27:01 +00:00

(Migrated from gitlab.com)

mentioned in issue #285

Brouie commented

2026-06-04 05:27:05 +00:00

(Migrated from gitlab.com)

mentioned in merge request !744

Brouie commented

2026-06-04 05:39:16 +00:00

(Migrated from gitlab.com)

Fixed — added the global DFS expansion budget + truncated flag.

One correction to the triage premise: the path-enumeration graph is ALREADY built in-memory from Postgres (db_pairs::get_all_pairs in best_execution.rs), so find_paths_top_k does zero LCD/RPC. The factory/token-index Postgres storage you mentioned would shrink the candidate edge set but would NOT cap the worst-case enumeration — so the actual fix is a pure in-memory bound, independent of that storage work.

Fix: MAX_DFS_EXPANSIONS = 50_000 global node-expansion budget in route_paths::find_paths_top_k. When the budget is hit the DFS aborts and the function returns (paths, truncated=true); that surfaces as a new route_search_truncated: Some(true) field on RouteSolveResponse (omitted otherwise). The sibling BFS find_path (route_solver.rs) is already O(V+E) via a visited set, so it's untouched.

Tests (route_paths.rs):

dense_unreachable_graph_truncates_within_budget — a complete graph on 50 nodes with an unreachable goal. Without the budget this enumerates ~N^3 simple paths; with it the search returns bounded + truncated=true in ~0.01s. This is the abuse case.
normal_graph_finds_route_not_truncated — a real 3-hop route still resolves, truncated=false (no regression).
small_unreachable_graph_completes_not_truncated — no false-positive truncation on a small absent-goal graph.

3/3 pass. Branch qa/286-route-dfs-expansion-budget, MR fork→main (no closing keyword). @PlasticDigits

Fixed — added the global DFS expansion budget + truncated flag. One correction to the triage premise: the path-enumeration graph is ALREADY built in-memory from Postgres (`db_pairs::get_all_pairs` in best_execution.rs), so `find_paths_top_k` does zero LCD/RPC. The factory/token-index Postgres storage you mentioned would shrink the candidate edge set but would NOT cap the worst-case enumeration — so the actual fix is a pure in-memory bound, independent of that storage work. **Fix**: `MAX_DFS_EXPANSIONS = 50_000` global node-expansion budget in `route_paths::find_paths_top_k`. When the budget is hit the DFS aborts and the function returns `(paths, truncated=true)`; that surfaces as a new `route_search_truncated: Some(true)` field on `RouteSolveResponse` (omitted otherwise). The sibling BFS `find_path` (route_solver.rs) is already O(V+E) via a visited set, so it's untouched. **Tests** (route_paths.rs): - `dense_unreachable_graph_truncates_within_budget` — a complete graph on 50 nodes with an unreachable goal. Without the budget this enumerates ~N^3 simple paths; with it the search returns bounded + `truncated=true` in ~0.01s. This is the abuse case. - `normal_graph_finds_route_not_truncated` — a real 3-hop route still resolves, `truncated=false` (no regression). - `small_unreachable_graph_completes_not_truncated` — no false-positive truncation on a small absent-goal graph. 3/3 pass. Branch `qa/286-route-dfs-expansion-budget`, MR fork→main (no closing keyword). @PlasticDigits

Brouie commented

2026-06-04 05:39:18 +00:00

(Migrated from gitlab.com)

mentioned in merge request !745

Brouie commented

2026-06-04 06:29:25 +00:00

(Migrated from gitlab.com)

mentioned in issue #279

PlasticDigits commented

2026-06-04 08:09:05 +00:00

(Migrated from gitlab.com)

Strategy is denied as it may cause priority routes to be trauncated in the solver

PlasticDigits commented

2026-06-04 08:14:19 +00:00

(Migrated from gitlab.com)

(1) Need some basic checks like if the input/output token has no pairs then find_paths_top_k can exit immdiately
(2) Need a demonstration of the type of situation that could cause this memory issue
(3) Should add concurrency to find_paths_top_k to reduce this issue

It is a serious problem if a path exists and is not discovered, as this will cause the user to incorrectly believe the dex is broken or may cause new projects to not list with rare/unusual intermediate tokens. If some type of limiting is needed, truncation is NOT acceptable as we do not know which paths would be truncated and which would not be.

(1) Need some basic checks like if the input/output token has no pairs then find_paths_top_k can exit immdiately (2) Need a demonstration of the type of situation that could cause this memory issue (3) Should add concurrency to `find_paths_top_k` to reduce this issue It is a serious problem if a path exists and is not discovered, as this will cause the user to incorrectly believe the dex is broken or may cause new projects to not list with rare/unusual intermediate tokens. If some type of limiting is needed, truncation is NOT acceptable as we do not know which paths would be truncated and which would not be.

Brouie commented

2026-06-04 11:38:45 +00:00

(Migrated from gitlab.com)

Superseding my earlier "added the expansion budget + truncated flag" note above — you denied that and you were right, so the budget/truncation is gone entirely. Reworked the fix in !745 with no truncation; a route that exists is always discovered.

Short version (full detail + the four-point reply is on !745):

Reachability gate: one BFS from the goal precomputes hop-distance; if the input token can't reach the output within max_hops we return "no route" in O(V+E) without enumerating. That's the dense+unreachable abuse case from this issue, now linear, and it also covers your (1) — a token with no pairs is just unreachable so it bails instantly.
Admissible distance pruning on the DFS — only steps into a neighbor that can still reach the goal in the remaining hops, which provably never drops a valid route.
Iterative deepening keeps the K shortest routes (fewest hops = priority), so a short/direct route can't get crowded out by longer ones. Found + fixed a real latent bug doing this (the old max_paths cap could fill all 5 slots with 2-hop routes and miss a 1-hop direct pair).
Enumeration runs under spawn_blocking now (your (3), off the async executor).
Demonstration (your (2)): a test builds a complete graph on 50 nodes with an unreachable goal — the unpruned walk does >100k node expansions, the gated version does 0. Plus a bounded+complete reachable case and the crowd-out regression.

route_paths 8/8, full indexer lib suite green. @PlasticDigits

Superseding my earlier "added the expansion budget + truncated flag" note above — you denied that and you were right, so the budget/truncation is gone entirely. Reworked the fix in !745 with no truncation; a route that exists is always discovered. Short version (full detail + the four-point reply is on !745): - Reachability gate: one BFS from the goal precomputes hop-distance; if the input token can't reach the output within max_hops we return "no route" in O(V+E) without enumerating. That's the dense+unreachable abuse case from this issue, now linear, and it also covers your (1) — a token with no pairs is just unreachable so it bails instantly. - Admissible distance pruning on the DFS — only steps into a neighbor that can still reach the goal in the remaining hops, which provably never drops a valid route. - Iterative deepening keeps the K shortest routes (fewest hops = priority), so a short/direct route can't get crowded out by longer ones. Found + fixed a real latent bug doing this (the old max_paths cap could fill all 5 slots with 2-hop routes and miss a 1-hop direct pair). - Enumeration runs under spawn_blocking now (your (3), off the async executor). - Demonstration (your (2)): a test builds a complete graph on 50 nodes with an unreachable goal — the unpruned walk does >100k node expansions, the gated version does 0. Plus a bounded+complete reachable case and the crowd-out regression. route_paths 8/8, full indexer lib suite green. @PlasticDigits

PlasticDigits commented

2026-06-04 12:54:29 +00:00

(Migrated from gitlab.com)

mentioned in commit 679cc56fac

mentioned in commit 679cc56fac77db4ff2b51b35d0e7844bb85a976d

PlasticDigits (Migrated from gitlab.com) closed this issue

2026-06-04 13:04:47 +00:00

PlasticDigits commented

2026-06-05 03:23:59 +00:00

(Migrated from gitlab.com)

mentioned in merge request !758