java-topology/defects/snort3-0001/test/Snort3ServiceCandidateDedupTest.java

import java.util.*;

/**
 * Unit test for Snort3 CWE-407 defect: ServiceDiscovery.match_by_pattern()
 * and get_port_based_services() use std::find on service_candidates vector
 * for dedup, creating O(M*C) complexity per AppID pattern match.
 *
 * File: src/network_inspectors/appid/service_plugins/service_discovery.cc
 * Lines: 273-281 (match_by_pattern), 351-356 (get_port_based_services)
 *
 * Fix: replace std::find with std::unordered_set for O(1) lookup.
 */
public class Snort3ServiceCandidateDedupTest {

    // Simulate ServiceDetector pointers as Integer IDs
    // --- DEFECTIVE: std::find O(M*C) ---
    static List<Integer> matchByPatternDefective(List<Integer> existingCandidates, int[] matchedServices) {
        List<Integer> candidates = new ArrayList<>(existingCandidates);
        for (int service : matchedServices) {
            if (!candidates.contains(service)) {
                candidates.add(service);
            }
        }
        return candidates;
    }

    // --- FIXED: unordered_set O(M+C) ---
    static List<Integer> matchByPatternFixed(List<Integer> existingCandidates, int[] matchedServices) {
        List<Integer> candidates = new ArrayList<>(existingCandidates);
        Set<Integer> seen = new HashSet<>(candidates);
        for (int service : matchedServices) {
            if (seen.add(service)) {
                candidates.add(service);
            }
        }
        return candidates;
    }

    public static void main(String[] args) {
        // Simulate: many pattern matches with overlapping service detectors
        // In real Snort: custom AppID ODP with many detectors can produce large match lists
        // In real Snort, custom ODP rule sets can have hundreds of service detectors;
        // with deep packet inspection + multiple pattern matches per flow, M can be large.
        int[] sizes = {500, 2000, 5000, 10000};
        System.out.println("snort3-0001: ServiceDiscovery service_candidates std::find dedup");
        System.out.println("M\tDefect(ms)\tFixed(ms)\tRatio");

        for (int M : sizes) {
            // Existing candidates (from port-based detection)
            List<Integer> existing = new ArrayList<>();
            for (int i = 0; i < M / 4; i++) {
                existing.add(i);
            }

            // Pattern matches: half overlap, half new
            Random rng = new Random(42);
            int[] matches = new int[M];
            for (int i = 0; i < M; i++) {
                matches[i] = rng.nextInt(M);
            }

            // Warmup
            for (int w = 0; w < 3; w++) {
                matchByPatternDefective(existing, matches);
                matchByPatternFixed(existing, matches);
            }

            int iters = Math.max(1, 200000 / M);

            long t0 = System.nanoTime();
            for (int i = 0; i < iters; i++) {
                matchByPatternDefective(existing, matches);
            }
            long defectNs = System.nanoTime() - t0;

            t0 = System.nanoTime();
            for (int i = 0; i < iters; i++) {
                matchByPatternFixed(existing, matches);
            }
            long fixedNs = System.nanoTime() - t0;

            double defectMs = defectNs / 1e6;
            double fixedMs = fixedNs / 1e6;
            double ratio = defectMs / fixedMs;

            System.out.printf("%d\t%.1f\t\t%.1f\t\t%.1fx%n", M, defectMs, fixedMs, ratio);

            // Correctness
            List<Integer> dResult = matchByPatternDefective(existing, matches);
            List<Integer> fResult = matchByPatternFixed(existing, matches);
            assert new HashSet<>(dResult).equals(new HashSet<>(fResult)) : "Results differ at M=" + M;
            assert dResult.size() == fResult.size() : "Sizes differ at M=" + M;
            assert ratio > 1.5 || M < 100 : "Expected speedup at M=" + M + " but got ratio=" + ratio;
        }

        System.out.println("ALL PASS");
    }
}