java-topology/whitepaper/outreach/cataclysm-0002.md

Cataclysm: DDA — CWE-407 Disclosure Brief (cataclysm-0002)

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

Finding

Two O(n²) defects in Cataclysm: DDA's mod dependency tree. The dependency_node::inherit_errors() function uses std::find on a vector to deduplicate error messages. The get_dependencies_as_nodes() and get_dependents_as_nodes() functions use std::find on a vector to deduplicate dependency nodes. Both fire during mod loading.

The Defect

cataclysm-0002 (PATCHED — MEDIUM): src/dependency_tree.cpp:103,157,216

// In inherit_errors() — error dedup:
std::vector<std::string> cur_errors = all_errors[error_type];
for (auto &node_error : node_errors) {
    if (std::find(cur_errors.begin(), cur_errors.end(), node_error)
        == cur_errors.end()) {  // O(E) per error
        all_errors[cerror.first].push_back(node_error);
    }
}

// In get_dependencies_as_nodes() — node dedup:
if (std::find(ret.begin(), ret.end(), *it) == ret.end()) {  // O(N) per node
    ret.push_back(*it);
}

Error dedup scans a stale copy of the error vector for each incoming error. Node dedup scans the result vector for each dependency. Both grow quadratically with mod count.

Complexity Proof

At N=200 mods with E=50 inherited errors:

• Error dedup defective: 50 × average 25 scans = ~1,250 string comparisons per node
• Error dedup fixed: 50 × O(1) = 50 set lookups per node
• ~25× op reduction in error inheritance. Similarly for node dedup.

Impact

Cataclysm: DDA has a large modding community. Players commonly run 50-200+ mods simultaneously. Mod dependency resolution and error propagation fire during game startup. Games with many mods and complex dependency chains experience slower load times.

The Fix

Replace vector dedup with std::unordered_set shadow indexes:

// Before
if (std::find(cur_errors.begin(), cur_errors.end(), node_error) == cur_errors.end())

// After
// CWE-407 fix: unordered_set for O(1) dedup instead of O(E) vector scan.
std::unordered_set<std::string> cur_errors_set(
    all_errors[error_type].begin(), all_errors[error_type].end());
if (cur_errors_set.find(node_error) == cur_errors_set.end()) {
    all_errors[cerror.first].push_back(node_error);
    cur_errors_set.insert(node_error);
}

Patch

Fix available: defects/cataclysm-0002/patch/cataclysm-0002.patch

Single-file patch on src/dependency_tree.cpp. Adds std::unordered_set shadows for error dedup in inherit_errors(), node dedup in get_dependencies_as_nodes(), and node dedup in get_dependents_as_nodes().

What We Ask

A patch is ready for review.

1. Confirm receipt and assign a GitHub issue reference (CleverRaven/Cataclysm-DDA).
2. Assess severity — fires during mod loading, scales with mod count.
3. Coordinate a disclosure date — we target 90 days from first contact.
4. We will credit the Cataclysm: DDA team in the public disclosure. Preferred acknowledgment format welcome.

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