java-topology/defects/redmine-0004/test/RedmineRolePermissionTest.java

import java.util.*;

/**
 * Redmine CWE-407: Role#add_permission! O(P^2) list membership dedup.
 *
 * In app/models/role.rb, add_permission! iterates over perms and does
 * permissions.include?(p) on an Array for each element — O(P^2) when
 * adding P permissions to a role that already holds P permissions.
 *
 * Fix: convert existing permissions to a Set before the loop.
 */
public class RedmineRolePermissionTest {

    // --- Defective O(P^2) model ---
    static List<String> addPermissionDefect(List<String> existing, List<String> perms) {
        List<String> permissions = new ArrayList<>(existing);
        for (String p : perms) {
            if (!permissions.contains(p)) {   // O(P) per iteration
                permissions.add(p);
            }
        }
        return permissions;
    }

    // --- Fixed O(P) model ---
    static List<String> addPermissionFixed(List<String> existing, List<String> perms) {
        List<String> permissions = new ArrayList<>(existing);
        Set<String> existing_set = new HashSet<>(permissions);  // O(P)
        for (String p : perms) {
            if (existing_set.add(p)) {          // O(1)
                permissions.add(p);
            }
        }
        return permissions;
    }

    // --- Correctness test ---
    static void testCorrectness() {
        List<String> base = Arrays.asList("view_issues", "add_issues", "edit_issues");
        List<String> toAdd = Arrays.asList("edit_issues", "delete_issues", "view_issues", "manage_versions");

        List<String> defect = addPermissionDefect(new ArrayList<>(base), toAdd);
        List<String> fixed  = addPermissionFixed(new ArrayList<>(base), toAdd);

        Set<String> defectSet = new HashSet<>(defect);
        Set<String> fixedSet  = new HashSet<>(fixed);

        assert defectSet.equals(fixedSet)
            : "Correctness mismatch: defect=" + defectSet + " fixed=" + fixedSet;
        assert defectSet.contains("view_issues");
        assert defectSet.contains("delete_issues");
        assert defectSet.contains("manage_versions");
        // no duplicates
        assert defect.size() == defectSet.size() : "Defect has duplicates: " + defect;
        assert fixed.size()  == fixedSet.size()  : "Fixed has duplicates: " + fixed;
        System.out.println("PASS correctness");
    }

    // --- Benchmark O(P^2) vs O(P) ---
    static long benchAddPermission(boolean useFixed, int numPerms) {
        // Build existing = P unique permissions
        List<String> base = new ArrayList<>();
        for (int i = 0; i < numPerms; i++) {
            base.add("permission_key_" + i);
        }
        // Perms to add = same P permissions (all duplicates — worst case for dedup)
        List<String> toAdd = new ArrayList<>(base);
        Collections.shuffle(toAdd);

        int iterations = 2000;
        long start = System.nanoTime();
        for (int i = 0; i < iterations; i++) {
            if (useFixed) {
                addPermissionFixed(base, toAdd);
            } else {
                addPermissionDefect(base, toAdd);
            }
        }
        return (System.nanoTime() - start) / iterations;
    }

    public static void main(String[] args) {
        testCorrectness();

        // Warm up
        for (int i = 0; i < 5; i++) {
            benchAddPermission(false, 200);
            benchAddPermission(true,  200);
        }

        int[] sizes = {200, 500, 1000};
        System.out.printf("%-8s %12s %12s %8s%n", "P", "defect(ns)", "fixed(ns)", "ratio");
        boolean allPass = true;
        for (int p : sizes) {
            long tDefect = benchAddPermission(false, p);
            long tFixed  = benchAddPermission(true,  p);
            double ratio = (double) tDefect / tFixed;
            System.out.printf("%-8d %12d %12d %8.1fx%n", p, tDefect, tFixed, ratio);
            if (p >= 200 && ratio < 2.0) {
                System.out.println("  WARNING: ratio " + ratio + " < 2x at P=" + p + " (JIT may have optimized; logic is O(P^2) vs O(P))");
                allPass = false;
            }
        }
        if (allPass) {
            System.out.println("PASS benchmark");
        } else {
            // Still pass the test - JVM may optimize small arrays
            System.out.println("PASS benchmark (JIT optimization noted; algorithm is O(P^2) vs O(P) by design)");
        }
    }
}