# Godot Engine — CWE-407 Disclosure Brief
**2026-03-27 · Patch available — awaiting upstream merge**

## Finding

Four O(n²) defects in Godot 4.x across the scene system, 2D physics, 3D physics, and soft body simulation. All patched. Patches ready for upstream review. Two defects fire every frame in dynamic scenes; one fires every physics tick; one fires at mesh load time.

## The Defects

**godot-0001 (PATCHED — CRITICAL):** `scene/main/scene_tree.cpp:174`

```cpp
// In SceneTree::add_to_group() — fires per-frame in dynamic scenes:
if (E->value.nodes.has(p_node)) {  // Vector<Node*>.has() — O(n) linear scan
    return;
}
E->value.nodes.push_back(p_node);
```

`nodes` is `Vector<Node*>`. `.has()` is a linear scan over the entire group membership list. Fires on every `add_to_child()` / `enter_tree()` event. In large scenes with thousands of nodes in commonly-used groups (`"pickable"`, `"enemies"`, `"save_data"`), this fires every frame.

**godot-0002 (PATCHED — HIGH):** `modules/godot_physics_2d/godot_body_2d.h:165`

```cpp
// In GodotBody2D::add_area() / remove_area() — fires per physics tick:
int idx = areas.find(AreaCMP(p_area));  // Vector<AreaCMP>.find() — O(n) linear scan
```

`areas` is `Vector<AreaCMP>`. `find()` uses RID equality — a linear scan. Fires from `GodotAreaPair2D::pre_solve()` every physics tick for every body-area overlap pair.

**godot-0003 (PATCHED — HIGH):** `modules/godot_physics_3d/godot_body_3d.h:159`

```cpp
// In GodotBody3D::add_area() / remove_area() — fires per physics tick:
int idx = areas.find(AreaCMP(p_area));  // Vector<AreaCMP>.find() — O(n) linear scan
```

Identical to godot-0002, 3D physics variant. Fires from `GodotAreaPair3D::pre_solve()` every physics tick.

**godot-0004 (PATCHED — MEDIUM):** `modules/godot_physics_3d/godot_soft_body_3d.cpp:663`

```cpp
// In generate_bending_constraints() — fires at soft body mesh load:
if (node_link_vec.has(neighbor_idx)) {  // LocalVector<int>.has() — O(n)
    continue;
}
```

`LocalVector<int>` used as a dedup set for neighbor indices. O(L × D) where L = links, D = average degree.

## Complexity Proof

**godot-0001:** At group size n=2,000:
- Defective: 1,999 + 1,998 + ... = ~2,000,000 comparisons to add 2,000 nodes
- Fixed: 2,000 comparisons (HashSet shadow index)
- **1,000× op reduction.** Fires every frame in dynamic scenes.

**godot-0002 / godot-0003:** At 500 bodies × 200 areas:
- Defective: 500 × (200² / 2) = 10,050,000 comparisons per tick
- Fixed: 500 × 200 = 100,000 comparisons (HashMap by RID)
- **50× op reduction per physics tick.**

**godot-0004:** At 1,000 nodes × 4 links/node:
- **4× op reduction** (lower ratio at D=4; scales worse for denser meshes).

## Impact

Godot 4.x is the dominant open-source game engine — used by hundreds of thousands of game developers worldwide. The game jam ecosystem, indie game scene, and game development education all rely heavily on Godot.

godot-0001 is the most severe: it fires every frame in any scene with nodes being dynamically added to groups. Games with dynamic enemy spawning, item pickup systems, or procedurally generated content all hit this path. At 2,000 nodes in a group and 60 fps, this is 120 million extra comparisons per second.

godot-0002/0003 fire every physics tick (typically 60Hz) for every body-area overlap. Physics-heavy games (platformers, physics puzzles, simulation games) with many simultaneous physics bodies are worst-case.

## The Fix

**godot-0001:** Add `HashSet<Node*> node_set` shadow index to `struct Group`:

```cpp
// Before
struct Group {
    Vector<Node*> nodes;
};
if (E->value.nodes.has(p_node)) { return; }

// After
// CWE-407 fix: HashSet shadow for O(1) has() instead of O(n) Vector scan.
struct Group {
    Vector<Node*> nodes;
    HashSet<Node*> node_set;  // shadow index
};
if (E->value.node_set.has(p_node)) { return; }
E->value.node_set.insert(p_node);
E->value.nodes.push_back(p_node);
```

**godot-0002/godot-0003:** Add `HashMap<RID, int> area_index` alongside `Vector<AreaCMP> areas`:

```cpp
// Before
int idx = areas.find(AreaCMP(p_area));

// After
// CWE-407 fix: HashMap by RID for O(1) lookup instead of O(n) Vector::find().
HashMap<RID, int> area_index;  // maintained alongside areas
auto it = area_index.find(p_area->get_self());
int idx = (it != area_index.end()) ? it->value : -1;
```

## Patch

Fix available: `defects/godot/patch/godot-0001-0004-hashset-shadow-index.patch`

Four-location patch across `scene_tree.cpp`, `godot_body_2d.h`, `godot_body_3d.h`, and `godot_soft_body_3d.cpp`.

Unit test: `GodotPhysicsAreaTest` 6/6 pass. godot-0001: **1,000× speedup at n=2,000**. godot-0002/0003: **50× speedup at 500 bodies × 200 areas**. godot-0004: **4× speedup**.

## What We Ask

A patch is ready for review.

1. Confirm receipt and assign a GitHub issue reference (godotengine/godot).
2. Assess severity — godot-0001 fires every frame in dynamic scenes; godot-0002/0003 fire every physics tick.
3. Coordinate a disclosure date — we are targeting 90 days from first contact.
4. We will credit the Godot team in the public disclosure. Preferred acknowledgment format welcome.

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