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

Naev — CWE-407 Disclosure Brief (naev-0002)

2026-04-13 · Defect documented — fix in progress

Finding

One O(I × N) defect in Naev's tech group item deduplication. Documented with annotations. tech_addGroupItemPrice() linearly scans the output array for every item added, producing quadratic dedup behavior.

The Defect

naev-0002 (DOCUMENTED — MEDIUM): src/tech.c:656

// In tech_addGroupItemPrice() — fires per item across all tech groups:
/* Skip if already in list. */
f = 0;
for (int j = array_size(items) - 1; j >= 0; j--) {
    if (items[j] == item->u.ptr) {
        f = 1;
        break;
    }
}

The output items array grows as items are collected from tech groups. For each new item, the entire array is scanned backwards for duplicates. With I items across all tech groups and N growing output size, total cost: O(I × N).

Complexity Proof

At I=500 items, N growing to 500:

• Defective: 500 × 250 avg = 125,000 pointer comparisons
• Fixed (proposed): sorted array + bsearch = 500 × log(500) ≈ 4,500 operations
• ~28× op reduction at 500 items.

Impact

Naev is an open-source 2D space trading and combat game. Tech groups define available ships, outfits, and commodities. The dedup fires during tech tree population at game load and when the player visits outfitters/shipyards. Large mod packs with many tech groups amplify the quadratic cost.

Proposed Fix

Track seen pointers in a sorted array and use bsearch() for O(log N) dedup:

// Current: O(N) linear scan per item
for (int j = array_size(items) - 1; j >= 0; j--) { ... }

// Proposed: sorted seen-array + bsearch for O(log N) dedup

Patch

Annotation patch available: defects/naev-0002/patch/naev-0002.patch

Documents the defect pattern with inline comments. Full fix pending implementation.

What We Ask

1. Confirm receipt and assign a GitHub issue reference (naev/naev).
2. Assess severity — fires during tech tree population.
3. Coordinate a disclosure date — we are targeting 90 days from first contact.
4. We will credit the Naev team in the public disclosure. Preferred acknowledgment format welcome.

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