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

OpenSCAD — CWE-407 Disclosure Brief (openscad-0001)

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

Finding

O(N²) vertex deduplication in AMF export where std::find scans a vector<vertex_str> for every vertex added during mesh export.

The Defect

openscad-0001 (PATCHED — MEDIUM): src/io/export_amf.cc

// add_vertex — fires per vertex during AMF export:
auto vi = std::find(vertices.begin(), vertices.end(), vs);
if (vi == vertices.end()) {
    vertices.push_back(vs);
    return vertices.size() - 1;
} else {
    return std::distance(vertices.begin(), vi);
}

Each vertex addition scans the entire vertex list for duplicates. With V vertices, total cost is O(V²).

Complexity Proof

At V=10,000 vertices:

• Defective: ~50,000,000 string comparisons (3 strings per vertex)
• Fixed: 10,000 hash lookups
• ~5,000× op reduction.

Impact

OpenSCAD exports complex 3D models to AMF format. Dense meshes from high-resolution CSG operations routinely produce tens of thousands of vertices. Export time grows quadratically with mesh complexity.

The Fix

Add an unordered_map<vertex_str, size_t> index alongside the vertex vector for O(1) dedup:

static size_t add_vertex(std::vector<vertex_str>& vertices,
                          std::unordered_map<vertex_str, size_t, vertex_str_hash>& vertex_index,
                          const Point& p) {
    vertex_str vs{STR(x), STR(y), STR(z)};
    auto it = vertex_index.find(vs);
    if (it == vertex_index.end()) {
        size_t idx = vertices.size();
        vertices.push_back(vs);
        vertex_index[vs] = idx;
        return idx;
    } else {
        return it->second;
    }
}

Patch

Fix available: defects/openscad-0001/patch/openscad-0001-amf-vertex-dedup.patch

Single-file patch in export_amf.cc.

What We Ask

A patch is ready for review.

1. Confirm receipt and assign a GitHub issue reference (openscad/openscad).
2. Assess severity — fires on every AMF export, scales with mesh complexity.
3. Coordinate a disclosure date — we target 90 days from first contact.
4. We will credit the OpenSCAD team in the public disclosure. Preferred acknowledgment format welcome.

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