russell@unturf.com 652608142a feat: close outreach doc gap — 276 docs (batches 11-16)

All projects with patches now have outreach docs. 276 new docs covering
CWE-407, CWE-312, CWE-362 across C, C++, Java, Python, Go, Rust, C#,
PHP, Ruby, JavaScript, Dart, Erlang, R, and more.

Outreach gap: 276 -> 0.

2026-04-15 13:57:42 -04:00

2 KiB

Raw Permalink Blame History

Simutrans — CWE-407 Disclosure Brief (simutrans-0003)

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

Finding

An O(S²) dedup scan in haltestelle_t::rebuild_connections() at src/simutrans/simhalt.cc:1222. Multiple calls to append_unique() on consecutive_halts and consecutive_halts_schedule arrays (one per goods category) perform O(S) linear scans per insertion where S = schedule entries. This fires per category per schedule entry.

The Defect

simutrans-0003 (PATCHED — MEDIUM): src/simutrans/simhalt.cc:1222

// For each schedule entry and category:
consecutive_halts[catg_index].append_unique(previous_halt[catg_index]);
consecutive_halts_schedule[catg_index].append_unique(previous_halt[catg_index]);
// Each append_unique is O(S) linear scan

Complexity Proof

At 256 categories, S=100 schedule entries per category:

Defective: 256 × 2 × 100 × 100/2 = 2,560,000 comparisons
Fixed: 256 × 2 × 100 × O(1) = 51,200 hash lookups
50× op reduction

Impact

Simutrans rebuilds connections on every schedule change and network update. Complex transit networks with many categories and long schedules trigger the worst case. This function fires frequently during gameplay, contributing to frame stutter on large maps.

The Fix

Add parallel inthashtable_tpl<uint16, bool> hash sets alongside each consecutive_halts and consecutive_halts_schedule array. Check the hash set before appending:

if(!consecutive_halts_seen[catg_index].get(halt_id)) {
    consecutive_halts_seen[catg_index].put(halt_id, true);
    consecutive_halts[catg_index].append(halt);
}

Patch

Fix available: defects/simutrans-0003/patch/simutrans-0003.patch

50× op reduction at 256 categories, S=100.

What We Ask

Confirm receipt and assign a GitHub issue reference (simutrans/simutrans).
Coordinate a disclosure date — targeting 90 days from first contact.
We will credit the Simutrans team in the public disclosure.

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

2 KiB Raw Permalink Blame History Unescape Escape