java-topology/defects/openmsx-0001/test/test_openmsx0001.cpp

// Unit test for openmsx-0001: CWE-407 checkBreakPoints O(B) scan
// Demonstrates the defect (O(B) per instruction) and verifies the fix
// (O(k) index lookup, k = breakpoints at current PC).
//
// Compile: g++ -std=c++17 -O2 -o test_openmsx0001 test_openmsx0001.cpp
// Run:     ./test_openmsx0001

#include <algorithm>
#include <cassert>
#include <cstdint>
#include <cstdio>
#include <optional>
#include <unordered_map>
#include <vector>

// Minimal stand-in for BreakPoint.
struct BreakPoint {
    unsigned id;
    std::optional<uint16_t> address; // nullopt = dynamic
    bool enabled = true;

    unsigned getId()                      const { return id; }
    std::optional<uint16_t> getAddress()  const { return address; }
    bool isEnabled()                      const { return enabled; }
};

// --- DEFECT model: O(B) scan per PC ---
struct DefectChecker {
    std::vector<BreakPoint> breakPoints;

    void insert(BreakPoint bp) { breakPoints.push_back(std::move(bp)); }

    // Returns number of scan iterations performed (observable proxy for work).
    int checkBreakPoints(uint16_t pc, int& matchCount) {
        matchCount = 0;
        int scanned = 0;
        for (const auto& bp : breakPoints) {
            ++scanned;
            if (bp.isEnabled() && bp.getAddress() && *bp.getAddress() == pc)
                ++matchCount;
        }
        return scanned; // O(B)
    }
};

// --- FIX model: O(k) index lookup ---
struct FixedChecker {
    std::vector<BreakPoint> breakPoints;
    std::unordered_map<uint16_t, std::vector<unsigned>> breakIndex;

    void insert(BreakPoint bp) {
        if (auto addr = bp.getAddress())
            breakIndex[*addr].push_back(bp.getId());
        breakPoints.push_back(std::move(bp));
    }

    void remove(unsigned id) {
        auto it = std::find_if(breakPoints.begin(), breakPoints.end(),
                               [&](const BreakPoint& b){ return b.getId() == id; });
        if (it == breakPoints.end()) return;
        if (auto addr = it->getAddress()) {
            auto& ids = breakIndex[*addr];
            ids.erase(std::find(ids.begin(), ids.end(), id));
            if (ids.empty()) breakIndex.erase(*addr);
        }
        breakPoints.erase(it);
    }

    // Returns number of index-entry accesses (observable proxy for work).
    int checkBreakPoints(uint16_t pc, int& matchCount) {
        matchCount = 0;
        int scanned = 0;
        auto it = breakIndex.find(pc);
        if (it != breakIndex.end()) {
            for (unsigned bpId : it->second) {
                ++scanned;
                auto bpIt = std::find_if(breakPoints.begin(), breakPoints.end(),
                    [&](const BreakPoint& b){ return b.getId() == bpId; });
                if (bpIt != breakPoints.end() && bpIt->isEnabled())
                    ++matchCount;
            }
        }
        // dynamic BPs (no address) always need a scan — uncommon in practice
        for (const auto& bp : breakPoints) {
            if (bp.isEnabled() && !bp.getAddress()) {
                ++scanned;
                ++matchCount;
            }
        }
        return scanned; // O(k), k << B
    }
};

static void test_defect_scales_with_all_breakpoints() {
    // Defect: scanning cost grows with total breakpoints, not with matches.
    // Place B breakpoints all at address 0x1000. Query PC 0x0000 (no match).
    const int B = 200;
    DefectChecker d;
    for (int i = 0; i < B; ++i)
        d.insert({unsigned(i), uint16_t(0x1000)});

    int matches = -1;
    int scanned = d.checkBreakPoints(0x0000, matches);

    // All B breakpoints were scanned even though none matched.
    assert(scanned == B && "defect: O(B) scan regardless of PC");
    assert(matches == 0);
    printf("PASS defect: checkBreakPoints scanned %d BPs for a no-match PC\n", scanned);
}

static void test_fix_skips_non_matching_breakpoints() {
    // Fix: index lookup returns only the breakpoints for the queried PC.
    const int B = 200;
    FixedChecker f;
    for (int i = 0; i < B; ++i)
        f.insert({unsigned(i), uint16_t(0x1000)});

    int matches = -1;
    int scanned = f.checkBreakPoints(0x0000, matches);

    // Zero entries in index for 0x0000 -> zero work for fixed BPs.
    assert(scanned == 0 && "fix: O(k=0) lookup for unset PC");
    assert(matches == 0);
    printf("PASS fix:    checkBreakPoints scanned %d BPs for a no-match PC\n", scanned);
}

static void test_fix_finds_matching_breakpoints() {
    const int B = 200;
    FixedChecker f;
    for (int i = 0; i < B; ++i)
        f.insert({unsigned(i), uint16_t(i < 3 ? 0x0200 : 0x1000)});

    int matches = -1;
    int scanned = f.checkBreakPoints(0x0200, matches);

    // Only 3 BPs at 0x0200 are consulted, not all B.
    assert(scanned == 3 && "fix: only BPs at queried PC are scanned");
    assert(matches == 3);
    printf("PASS fix:    checkBreakPoints scanned %d / %d BPs, found %d matches\n",
           scanned, B, matches);
}

static void test_fix_remove_updates_index() {
    FixedChecker f;
    f.insert({1u, uint16_t(0x0400)});
    f.insert({2u, uint16_t(0x0400)});
    f.insert({3u, uint16_t(0x0800)});

    f.remove(1u);

    int matches = -1;
    int scanned = f.checkBreakPoints(0x0400, matches);
    assert(matches == 1 && "fix: remove updates index correctly");
    assert(scanned == 1);
    printf("PASS fix:    after remove, only 1 BP left at 0x0400\n");

    f.remove(2u);
    scanned = f.checkBreakPoints(0x0400, matches);
    assert(matches == 0);
    assert(scanned == 0 && "fix: index entry erased when last BP removed");
    printf("PASS fix:    index entry cleaned up after all BPs at address removed\n");
}

static void test_speedup_ratio() {
    // Confirm fix gives measurable reduction in scan work for large B, no match.
    const int B = 500;
    DefectChecker d;
    FixedChecker  f;
    for (int i = 0; i < B; ++i) {
        d.insert({unsigned(i), uint16_t(0xF000)});
        f.insert({unsigned(i), uint16_t(0xF000)});
    }

    int m1, m2;
    int defect_scanned = d.checkBreakPoints(0x0000, m1);
    int fixed_scanned  = f.checkBreakPoints(0x0000, m2);

    assert(m1 == 0 && m2 == 0);
    // Defect: scanned all B. Fix: scanned 0.
    int ratio = (fixed_scanned == 0) ? B : defect_scanned / fixed_scanned;
    printf("PASS speedup: defect scanned %d, fix scanned %d, ratio >= %dx\n",
           defect_scanned, fixed_scanned, ratio);
    assert(defect_scanned == B);
    assert(fixed_scanned  == 0);
}

int main() {
    printf("--- openmsx-0001 CWE-407 checkBreakPoints O(B) scan ---\n");
    test_defect_scales_with_all_breakpoints();
    test_fix_skips_non_matching_breakpoints();
    test_fix_finds_matching_breakpoints();
    test_fix_remove_updates_index();
    test_speedup_ratio();
    printf("ALL PASS\n");
    return 0;
}