java-topology/whitepaper/outreach/scummvm-0001.md

ScummVM — CWE-407 Disclosure Brief (scummvm-0001)

2026-04-13 · Patch available — awaiting upstream merge

Finding

An O(N²) visited-node check in PathfindingGrid::getNearestOpenNode() at engines/crab/PathfindingGrid.cpp. The BFS pathfinding uses Common::Array<PathfindingGraphNode*> as a visited set with Common::find() (O(N) linear scan) per neighbor check. At N grid nodes, total BFS cost becomes O(N²) instead of O(N).

The Defect

scummvm-0001 (PATCHED — MEDIUM): engines/crab/PathfindingGrid.cpp

Common::Array<PathfindingGraphNode *> allUsedNodes;
// ...
if (Common::find(allUsedNodes.begin(), allUsedNodes.end(),
    checkNodes.front()->_neighborNodes[i]) == allUsedNodes.end()) {
    // O(N) per neighbor check
    allUsedNodes.push_back(checkNodes.front()->_neighborNodes[i]);

Complexity Proof

At N=2,000 grid nodes, average 4 neighbors each:

• Defective: 2,000 × 4 × 2,000/2 = 8,000,000 comparisons
• Fixed: 2,000 × 4 × O(1) = 8,000 lookups
• 1,000× op reduction

Impact

ScummVM runs classic adventure games across platforms. The Crab engine pathfinding fires on every NPC and player movement in grid-based games. Large maps with many pathfinding queries per frame accumulate this cost. Mobile and embedded platforms (where ScummVM runs frequently) suffer the most from the quadratic scaling.

The Fix

Replace Common::Array visited set with std::unordered_set<PathfindingGraphNode*> for O(1) membership checks:

std::unordered_set<PathfindingGraphNode *> visitedNodes;
visitedNodes.insert(startNode);
// ...
if (visitedNodes.find(neighbor) == visitedNodes.end()) {
    visitedNodes.insert(neighbor);

Patch

Fix available: defects/scummvm-0001/patch/scummvm-0001.patch

1,000× op reduction at N=2,000 grid nodes.

What We Ask

1. Confirm receipt and assign a GitHub issue reference (scummvm/scummvm).
2. Assess severity — fires on every pathfinding query in Crab engine games.
3. Coordinate a disclosure date — targeting 90 days from first contact.
4. We will credit the ScummVM team in the public disclosure.

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