java-topology/defects/snort3-0002/test/Snort3ChpMatchTallyTest.java

import java.util.*;

/**
 * snort3-0002: CWE-407 — chp_add_candidate_to_tally O(M*T) linear scan
 *
 * Source: src/network_inspectors/appid/detector_plugins/http_url_patterns.cc
 * Function: chp_add_candidate_to_tally()
 *
 * Defect: CHPMatchTally is a std::vector<CHPMatchCandidate>. For each Aho-Corasick
 * pattern match callback (chp_key_pattern_match), chp_add_candidate_to_tally performs
 * std::find_if over the entire match_tally vector to locate the CHPApp entry and
 * decrement its key_pattern_countdown. With M pattern matches and T unique CHPApp
 * candidates in the tally, the total work is O(M * T) per HTTP packet.
 *
 * Fix: Add std::unordered_map<CHPApp*, size_t> match_tally_index alongside the vector.
 * Lookup becomes O(1) amortized, reducing total work to O(M + T) per packet.
 *
 * Complexity: O(M*T) -> O(M+T) per HTTP packet
 * Severity: MEDIUM (per HTTP flow, M~50-200 pattern matches, T~10-50 candidates)
 * Speedup: up to T-fold (e.g., 50x at T=50 candidates)
 */
public class Snort3ChpMatchTallyTest {

    // Simulate CHPApp as an opaque identity (pointer in C++)
    static class CHPApp {
        final int id;
        final int keyPatternCount;
        final int keyPatternLengthSum;
        CHPApp(int id, int kpc, int kpls) {
            this.id = id;
            this.keyPatternCount = kpc;
            this.keyPatternLengthSum = kpls;
        }
    }

    static class CHPMatchCandidate {
        CHPApp chpapp;
        int keyPatternLengthSum;
        int keyPatternCountdown;
        CHPMatchCandidate(CHPApp app) {
            this.chpapp = app;
            this.keyPatternLengthSum = app.keyPatternLengthSum;
            this.keyPatternCountdown = app.keyPatternCount - 1;
        }
    }

    // --- DEFECTIVE implementation: O(M*T) ---
    static void chp_add_candidate_to_tally_defective(List<CHPMatchCandidate> match_tally, CHPApp chpapp) {
        // Linear scan over tally - O(T) per call
        for (CHPMatchCandidate item : match_tally) {
            if (item.chpapp == chpapp) {
                item.keyPatternCountdown--;
                return;
            }
        }
        match_tally.add(new CHPMatchCandidate(chpapp));
    }

    // --- FIXED implementation: O(1) amortized ---
    static void chp_add_candidate_to_tally_fixed(
            List<CHPMatchCandidate> match_tally,
            Map<CHPApp, Integer> match_tally_index,
            CHPApp chpapp) {
        Integer idx = match_tally_index.get(chpapp);
        if (idx != null) {
            match_tally.get(idx).keyPatternCountdown--;
            return;
        }
        int newIdx = match_tally.size();
        match_tally.add(new CHPMatchCandidate(chpapp));
        match_tally_index.put(chpapp, newIdx);
    }

    // Simulate M pattern match callbacks for a given set of CHPApp candidates
    static long benchDefective(List<CHPApp> apps, int matchesPerApp) {
        List<CHPMatchCandidate> tally = new ArrayList<>();
        long ops = 0;
        for (CHPApp app : apps) {
            for (int m = 0; m < matchesPerApp; m++) {
                // Count ops: linear scan
                int scanned = 0;
                boolean found = false;
                for (CHPMatchCandidate item : tally) {
                    scanned++;
                    if (item.chpapp == app) {
                        item.keyPatternCountdown--;
                        found = true;
                        break;
                    }
                }
                ops += scanned;
                if (!found) {
                    tally.add(new CHPMatchCandidate(app));
                    ops++;
                }
            }
        }
        return ops;
    }

    static long benchFixed(List<CHPApp> apps, int matchesPerApp) {
        List<CHPMatchCandidate> tally = new ArrayList<>();
        Map<CHPApp, Integer> tallyIndex = new HashMap<>();
        long ops = 0;
        for (CHPApp app : apps) {
            for (int m = 0; m < matchesPerApp; m++) {
                ops++; // O(1) hash lookup
                Integer idx = tallyIndex.get(app);
                if (idx != null) {
                    tally.get(idx).keyPatternCountdown--;
                } else {
                    int newIdx = tally.size();
                    tally.add(new CHPMatchCandidate(app));
                    tallyIndex.put(app, newIdx);
                    ops++; // map insert
                }
            }
        }
        return ops;
    }

    static void testCorrectness() {
        int T = 5;  // distinct CHPApp candidates
        int M = 3;  // matches per app
        List<CHPApp> apps = new ArrayList<>();
        for (int i = 0; i < T; i++) apps.add(new CHPApp(i, 3, i + 10));

        // Build tally with defective impl
        List<CHPMatchCandidate> tallyD = new ArrayList<>();
        for (int m = 0; m < M; m++) {
            for (CHPApp app : apps) {
                chp_add_candidate_to_tally_defective(tallyD, app);
            }
        }

        // Build tally with fixed impl
        List<CHPMatchCandidate> tallyF = new ArrayList<>();
        Map<CHPApp, Integer> indexF = new HashMap<>();
        for (int m = 0; m < M; m++) {
            for (CHPApp app : apps) {
                chp_add_candidate_to_tally_fixed(tallyF, indexF, app);
            }
        }

        // Both should have same number of candidates
        assert tallyD.size() == T : "Defective: wrong tally size " + tallyD.size();
        assert tallyF.size() == T : "Fixed: wrong tally size " + tallyF.size();

        // Both should have same countdown values (first match creates with count-1=2, then M-1=2 decrements -> 0)
        for (int i = 0; i < T; i++) {
            assert tallyD.get(i).keyPatternCountdown == tallyF.get(i).keyPatternCountdown
                : "Countdown mismatch at index " + i
                + ": defective=" + tallyD.get(i).keyPatternCountdown
                + " fixed=" + tallyF.get(i).keyPatternCountdown;
        }
        System.out.println("PASS correctness: both produce identical tally (T=" + T + ", M=" + M + ")");
    }

    static void testOpCount() {
        // T candidates, each with M=10 pattern matches
        int T = 50;
        int M = 10;
        List<CHPApp> apps = new ArrayList<>();
        for (int i = 0; i < T; i++) apps.add(new CHPApp(i, M, i + 10));

        long opsD = benchDefective(apps, M);
        long opsF = benchFixed(apps, M);

        double ratio = (double) opsD / opsF;
        System.out.printf("PASS op-count: T=%d M=%d | defective=%d ops | fixed=%d ops | ratio=%.1fx%n",
            T, M, opsD, opsF, ratio);
        assert ratio > 5.0 : "Expected >5x ratio, got " + ratio;
    }

    static void testLargeScale() {
        // Simulate a heavy HTTP scan: T=100 candidates, M=20 matches each
        int T = 100;
        int M = 20;
        List<CHPApp> apps = new ArrayList<>();
        for (int i = 0; i < T; i++) apps.add(new CHPApp(i, M, i + 10));

        long t0D = System.nanoTime();
        long opsD = benchDefective(apps, M);
        long t1D = System.nanoTime();

        long t0F = System.nanoTime();
        long opsF = benchFixed(apps, M);
        long t1F = System.nanoTime();

        double ratio = (double) opsD / opsF;
        System.out.printf("PASS large-scale: T=%d M=%d | defective=%d ops (%.2fms) | fixed=%d ops (%.2fms) | ratio=%.1fx%n",
            T, M, opsD, (t1D - t0D) / 1e6, opsF, (t1F - t0F) / 1e6, ratio);
        assert ratio > 10.0 : "Expected >10x ratio, got " + ratio;
    }

    public static void main(String[] args) {
        System.out.println("=== snort3-0002: CHP match_tally O(M*T) -> O(M+T) ===");
        testCorrectness();
        testOpCount();
        testLargeScale();
        System.out.println("ALL PASS");
    }
}