java-topology/defects/istio/unit/Istio0004Test.java

package unit;

import java.util.*;

/**
 * Standalone unit test for istio-0004: CWE-407.
 *
 * istio-0004: BackendPolicy parents accumulation — O(P²) linear dedup using
 *   slices.Contains during Gateway API config reconciliation.
 *
 *   slow() simulates the current code: for each BackendPolicy in the sorted
 *         list, call slices.Contains(parents, parentName) before append:
 *         O(P²) comparisons total.
 *   fast() simulates the fix: use a seen-map + ordered slice for O(P) total.
 *   Assert: slowOps > fastOps * 10x for P=200 policies.
 *
 * Called from krt.NewCollection reconciler on every BackendPolicy event.
 */
public class Istio0004Test {

    /**
     * Simulates current backend_policies.go parents dedup:
     *   for _, pol := range pols {
     *       parentName := ...
     *       if !slices.Contains(parents, parentName) {   // O(P) per iteration
     *           parents = append(parents, parentName)
     *       }
     *   }
     */
    static long slowParentsDedup(int numPolicies, int numUniqueParents) {
        long ops = 0;
        List<String> parents = new ArrayList<>(numUniqueParents);
        for (int i = 0; i < numPolicies; i++) {
            // Each policy maps to one of numUniqueParents distinct parents
            String parentName = "Kind/ns.svc" + (i % numUniqueParents);
            // slices.Contains: linear scan
            boolean found = false;
            for (String existing : parents) {
                ops++;
                if (existing.equals(parentName)) { found = true; break; }
            }
            if (!found) {
                parents.add(parentName);
            }
        }
        return ops;
    }

    /**
     * Simulates the fix: seenParents map for O(1) dedup.
     *   seenParents := make(map[string]struct{}, len(pols))
     *   for _, pol := range pols {
     *       if _, exists := seenParents[parentName]; !exists {
     *           seenParents[parentName] = struct{}{}
     *           parents = append(parents, parentName)
     *       }
     *   }
     */
    static long fastParentsDedup(int numPolicies, int numUniqueParents) {
        long ops = 0;
        List<String> parents = new ArrayList<>(numUniqueParents);
        Set<String> seenParents = new HashSet<>(numUniqueParents);
        for (int i = 0; i < numPolicies; i++) {
            String parentName = "Kind/ns.svc" + (i % numUniqueParents);
            ops++; // O(1) hash set check
            if (seenParents.add(parentName)) {
                parents.add(parentName);
            }
        }
        return ops;
    }

    public static void main(String[] args) {
        // Test 1: P=500 policies, 50 unique parents (many policies, few parent kinds)
        // With 500 pols and 50 unique: first 50 inserts cost 0+1+...+49=1225 ops;
        // remaining 450 duplicate lookups cost ~25 ops each on avg = 11250 ops → ~12475 total
        // fast: 500 × 1 = 500 ops. Ratio ≈ 25x
        int P = 500;
        int U = 50;
        long slow1 = slowParentsDedup(P, U);
        long fast1 = fastParentsDedup(P, U);
        System.out.printf("Parents dedup P=%d unique=%d: slow=%d ops, fast=%d ops, ratio=%.1fx%n",
                P, U, slow1, fast1, (double) slow1 / fast1);
        assert slow1 > fast1 * 10 :
                "Expected slow>fast*10x, got slow=" + slow1 + " fast=" + fast1;

        // Test 2: P=500 all-unique parents — worst case for slices.Contains (always scans full list)
        int P2 = 500;
        long slow2 = slowParentsDedup(P2, P2);
        long fast2 = fastParentsDedup(P2, P2);
        double ratio2 = (double) slow2 / fast2;
        System.out.printf("Parents dedup P=%d all-unique: slow=%d ops, fast=%d ops, ratio=%.1fx%n",
                P2, slow2, fast2, ratio2);
        assert ratio2 > 50 : "Expected ratio>50x at P=500, got " + ratio2;

        // Test 3: Complexity scaling — O(P^2) vs O(P)
        long slow10 = slowParentsDedup(10, 10);
        long slow100 = slowParentsDedup(100, 100);
        double complexityRatio = (double) slow100 / slow10;
        System.out.printf("Complexity ratio (100 vs 10): %.1fx (expect ~100x for O(P^2))%n",
                complexityRatio);
        assert complexityRatio > 50 : "Expected O(P^2) scaling, got " + complexityRatio;

        // Test 4: Verify correctness — both produce same number of unique parents
        int P3 = 100;
        int U3 = 10;
        // Run both and verify they produce same final list size (numUniqueParents)
        List<String> slowList = new ArrayList<>();
        Set<String> slowSeen = new HashSet<>();
        for (int i = 0; i < P3; i++) {
            String pn = "Kind/ns.svc" + (i % U3);
            if (!slowList.contains(pn)) slowList.add(pn);
        }
        List<String> fastList = new ArrayList<>();
        Set<String> fastSeen = new HashSet<>();
        for (int i = 0; i < P3; i++) {
            String pn = "Kind/ns.svc" + (i % U3);
            if (fastSeen.add(pn)) fastList.add(pn);
        }
        assert slowList.size() == fastList.size() :
                "Mismatch: slow=" + slowList.size() + " fast=" + fastList.size();
        assert slowList.size() == U3 : "Expected " + U3 + " unique parents, got " + slowList.size();
        System.out.printf("Correctness: both produce %d unique parents PASS%n", U3);

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