engineering/java-topology
1
0
Fork 0
Code Issues Pull requests Projects Releases Packages Wiki Activity Actions
java-topology/docs/tickets/redot-cwe407-12-defects.md
russell@unturf.com fdbb9a1aa9 redot: 12 CWE-407 defects, patches, outreach brief, UNDF-2026-000001231..1242 
All 12 O(N²) algorithmic complexity defects confirmed in Redot Engine 26.2-alpha
(commit 360a8d3). Inherited verbatim from Godot Engine upstream. All patched.

Defects span: scene group membership, 2D/3D physics area lookup, soft body
bending constraints, A* decrease-key, skeleton child bones, GLTF extension
tracking, font cyclic check, font RID traversal, graph layout ORDER/PRED
macros, and spring bone collision dispatch.

Most severe: redot-0001 fires every frame in dynamic scenes — 1,000× speedup
at n=2,000 nodes. redot-0002/0003 fire 60Hz in physics-heavy games — 50×.

Strategy: patch Redot first, Godot follows our lead.
2026-04-03 21:00:29 -04:00

2.1 KiB
Raw Permalink Blame History

Redot Engine — CWE-407 — 12 Defects

Status: patch-ready — awaiting PR submission UNDF IDs: UNDF-2026-000001231 through UNDF-2026-000001242 Project: https://github.com/Redot-Engine/redot-engine Version: 26.2-alpha (commit 360a8d3) Date: 2026-04-04

Summary

12 O(N²) algorithmic complexity defects inherited from Godot Engine. All present verbatim in Redot 26.2. All patched.

Defects

ID File Defect Fix Speedup
redot-0001 scene/main/scene_tree.cpp:176 nodes.has(p_node) O(n) per add_to_group HashSet shadow 1,000×
redot-0002 modules/godot_physics_2d/godot_body_2d.h:167 areas.find() O(n) per tick HashMap<RID,int> 50×
redot-0003 modules/godot_physics_3d/godot_body_3d.h:161 areas.find() O(n) per tick HashMap<RID,int> 50×
redot-0004 modules/godot_physics_3d/godot_soft_body_3d.cpp:665 node_links.has() O(n) HashSet shadow 4×
redot-0005 core/math/a_star.cpp:382 open_list.find() O(N) per relaxation open_index field O(N²)→O(N log N)
redot-0006 scene/3d/skeleton_3d.cpp:237 child_bones.has() O(B) HashSet child_bones B×
redot-0007 editor/import/3d/post_import_plugin_skeleton_rest_fixer.cpp:203 Vector.has() O(K) per track HashSet T×
redot-0008 modules/gltf/gltf_state.h + gltf_document.cpp:445 extensions_used.has() O(E) HashSet E×
redot-0009 scene/resources/font.cpp:136 _is_cyclic() O(F^D) no visited HashSet visited F^D→F
redot-0010 scene/resources/font.cpp:105 _update_rids_fb() O(N²) diamond HashSet visited N²→N
redot-0011 scene/gui/graph_edit_arranger.cpp:433 ORDER/PRED O(N) Vector::find HashMap maps C×N→N+C
redot-0012 scene/3d/spring_bone_simulator_3d.cpp:1455 collisions.has/find O(N) HashSet+HashMap S×C×N→N+S×C

Patches

All patches in: ~/git/java-topology/defects/redot/patch/

PR Plan

  1. Fork: https://github.com/Redot-Engine/redot-engine → fox's fork
  2. Branch: cwe407-hashset-shadow-index-12-defects
  3. Apply all 12 patches
  4. Open PR against main

Contact

security@undefect.com — coordinated disclosure