java-topology/whitepaper/outreach/three.js.md

three.js — CWE-407 Disclosure Brief

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

Finding

Two O(n²) defects in three.js's WebGPU/WebGL node material system. Array.includes() and Array.indexOf() perform linear membership tests during shader graph traversal, making addNode() and StackNode filtering quadratic. Patched.

The Defects

three-0001a (PATCHED — MEDIUM): src/nodes/core/NodeBuilder.js:762

// In NodeBuilder.addNode() — fires per node during shader build:
if ( this.nodes.includes( node ) === false ) {  // O(N) linear scan
    this.nodes.push( node );
}
// ...
if ( this.sequentialNodes.includes( node ) === false ) {  // O(N) linear scan
    this.sequentialNodes.push( node );
}

this.nodes.includes(node) is O(N) and fires once per node during the shader build traversal, making addNode() O(N²) for graphs with N nodes.

three-0001b (PATCHED — MEDIUM): src/nodes/core/StackNode.js:382

// In StackNode — fires during node graph evaluation:
const newNodes = this.nodes.filter( ( node ) => nodes.indexOf( node ) === - 1 );
// nodes.indexOf(node) is O(N) inside filter — O(N²) overall

Complexity Proof

three-0001a: At N=1,000 nodes in a shader graph:

• Defective: 1,000 + 999 + ... ≈ 500,000 comparisons during build
• Fixed: 1,000 Set lookups (O(1) each)
• ~500× op reduction. Fires on every shader compilation.

three-0001b: At N=500 nodes:

• Defective: ~125,000 indexOf comparisons
• Fixed: ~500 Set lookups
• ~250× op reduction.

Impact

three.js is the most widely-used 3D graphics library for the web, powering countless WebGL and WebGPU applications. The node material system (TSL/NodeMaterial) is the primary shader authoring API for WebGPU. Complex materials with hundreds of nodes (PBR chains, post-processing stacks, procedural generation) trigger quadratic build times on every shader compilation, including hot reloads during development.

The Fix

three-0001a: Add Set shadow indexes alongside the node arrays:

// Before — O(N) per membership check
if ( this.nodes.includes( node ) === false ) { ... }

// After — O(1) per membership check
this._nodesSet = new Set();
if ( this._nodesSet.has( node ) === false ) {
    this.nodes.push( node );
    this._nodesSet.add( node );
}

three-0001b: Convert to Set for the filter operation:

// Before — O(N²)
const newNodes = this.nodes.filter( ( node ) => nodes.indexOf( node ) === - 1 );

// After — O(N)
const nodesSnapshot = new Set( nodes );
const newNodes = this.nodes.filter( ( node ) => nodesSnapshot.has( node ) === false );

Patch

Fix available: defects/three.js/patch/three-0001-node-builder-array-includes-set.patch

Two-file patch across src/nodes/core/NodeBuilder.js and src/nodes/core/StackNode.js.

What We Ask

A patch is ready for review.

1. Confirm receipt and assign a GitHub issue reference (mrdoob/three.js).
2. Assess severity — fires on every shader compilation in WebGPU/NodeMaterial pipelines.
3. Coordinate a disclosure date — we are targeting 90 days from first contact.
4. We will credit the three.js team in the public disclosure. Preferred acknowledgment format welcome.

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