java-topology/whitepaper/outreach/dosbox-x.md

DOSBox-X — CWE-407 Disclosure Brief

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

Finding

Two O(n²) defects in DOSBox-X's overlay filesystem driver: one in the DOS name cache and one in the deleted-files tracker. Both patched. Patches ready for upstream review. The source code itself contains comments acknowledging both defects: "Also set is probably better" and "Set is probably better, or some other solution."

The Defects

dosbox-x-0001 (PATCHED — MEDIUM): src/dos/drive_overlay.cpp:730

// In add_DOSname_to_cache() — fires during overlay directory enumeration:
void Overlay_Drive::add_DOSname_to_cache(const char* name) {
    for (auto itc = DOSnames_cache.begin(); itc != DOSnames_cache.end(); ++itc){
        if (!strcasecmp((*itc).c_str(), name)) return;  // O(N) linear scan
    }
    DOSnames_cache.push_back(name);
}

DOSnames_cache is std::vector<std::string> with a case-insensitive linear scan for deduplication. O(N) per insertion, O(N²) total for N cached names. The code comments: "Also set is probably better."

dosbox-x-0002 (PATCHED — HIGH): src/dos/drive_overlay.cpp:1689

// In is_deleted_file() — fires on every file I/O operation:
for (auto it = deleted_files_in_base.begin(); it != deleted_files_in_base.end(); it++) {
    if (!strcasecmp((*it).c_str(), name) || !strcasecmp((*it).c_str(), tname)
        || (strlen(fname) && !strcasecmp((*it).c_str(), fname)))
        return true;
}

deleted_files_in_base is std::vector<std::string> scanned linearly for every file operation — open, stat, attr, FindFirst, and more. O(N) per query where N = deleted file count. The code comments: "Set is probably better, or some other solution."

Complexity Proof

dosbox-x-0001: At N=1,000 cached DOS names:

• Defective: 999 + 998 + ... ≈ 500,000 comparisons during enumeration
• Fixed: 1,000 × O(1) = 1,000 insertions (unordered_set)
• ~500× op reduction during directory enumeration.

dosbox-x-0002: At N=500 deleted files, Q=2,000 file operations:

• Defective: 2,000 × 500 × 3 (three strcasecmp per entry) = 3,000,000 comparisons
• Fixed: 2,000 × 3 × O(1) = 6,000 lookups (unordered_set)
• ~500× op reduction across file I/O.

Impact

DOSBox-X is a cross-platform DOS/Windows emulator used for retro gaming, legacy software preservation, and vintage computing research. The overlay filesystem allows layering modifications on top of a base filesystem image — commonly used for game mods, save states, and configuration overlays.

dosbox-x-0001 fires during every overlay directory enumeration. Games that enumerate large directories (file managers, level loaders, mod managers) trigger quadratic deduplication.

dosbox-x-0002 fires on every file operation — FileOpen, FileExists, GetFileAttr, FindFirst — against the deleted-files tracker. With many deleted files in the overlay, every file I/O call degrades to O(N). This sits on the hottest path in the overlay filesystem.

The Fix

dosbox-x-0001: Replace std::vector<std::string> with std::unordered_set using case-insensitive hash/equal:

// Before
std::vector<std::string> DOSnames_cache; //Also set is probably better.

// After
// CWE-407 fix: unordered_set with case-insensitive hash for O(1) dedup.
std::unordered_set<std::string, CaseInsensitiveHash, CaseInsensitiveEqual> DOSnames_set;

dosbox-x-0002: Replace std::vector<std::string> with std::unordered_set using case-insensitive hash/equal:

// Before
std::vector<std::string> deleted_files_in_base; //Set is probably better...

// After
// CWE-407 fix: unordered_set for O(1) lookup on every file I/O operation.
std::unordered_set<std::string, CaseInsensitiveHash, CaseInsensitiveEqual> deleted_files_set;

Patch

Fix available: defects/dosbox-x/patch/dosbox-x-0001-overlay-DOSnames-cache-vector-dedup.patch and defects/dosbox-x/patch/dosbox-x-0002-overlay-deleted-files-vector-scan.patch

Two-file patch across drives.h and drive_overlay.cpp.

dosbox-x-0001: ~500× speedup at N=1,000. dosbox-x-0002: ~500× speedup at N=500, Q=2,000.

What We Ask

A patch is ready for review.

1. Confirm receipt and assign an issue reference (joncampbell123/dosbox-x).
2. Assess severity — dosbox-x-0002 sits on every file I/O hot path in the overlay driver. The source code itself acknowledges both defects with "set is probably better" comments.
3. Coordinate a disclosure date — we are targeting 90 days from first contact.
4. We will credit the DOSBox-X team in the public disclosure. Preferred acknowledgment format welcome.

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