251 lines
10 KiB
Java
251 lines
10 KiB
Java
package unit;
|
||
|
||
import java.util.*;
|
||
|
||
/**
|
||
* Cilium0002Test — CWE-407 unit test for cilium-0002
|
||
*
|
||
* cilium-0002: rule.go:310-316 — L7 rule deduplication in mergeL4Filter()
|
||
* for _, newRule := range newPolicy.HTTP {
|
||
* if !newRule.Exists(existingPolicy.L7Rules) { // O(M) linear scan
|
||
*
|
||
* Exists() calls slices.ContainsFunc(rules.HTTP, h.Equal) — O(M) per call.
|
||
* Total: O(N × M) where N = new rules, M = existing rules.
|
||
* Called per selector per port during policy reconciliation.
|
||
*
|
||
* SLOW: linear scan over existing rules list per new rule → O(N × M)
|
||
* FAST: pre-built map[ruleKey]struct{} → O(N + M) total
|
||
*
|
||
* No JUnit. Run: javac -d . Cilium0002Test.java && java -ea unit.Cilium0002Test
|
||
*/
|
||
public class Cilium0002Test {
|
||
|
||
// -------------------------------------------------------------------------
|
||
// Data model — mirrors PortRuleHTTP
|
||
// -------------------------------------------------------------------------
|
||
|
||
static class HTTPRule {
|
||
final String path;
|
||
final String method;
|
||
final String host;
|
||
|
||
HTTPRule(String path, String method, String host) {
|
||
this.path = path;
|
||
this.method = method;
|
||
this.host = host;
|
||
}
|
||
|
||
// models PortRuleHTTP.Equal() — field-by-field comparison
|
||
boolean equal(HTTPRule o) {
|
||
return Objects.equals(path, o.path) &&
|
||
Objects.equals(method, o.method) &&
|
||
Objects.equals(host, o.host);
|
||
}
|
||
}
|
||
|
||
// Key for hash-based dedup (canonical form of the three primary fields)
|
||
static String ruleKey(HTTPRule r) {
|
||
return r.path + "\0" + r.method + "\0" + r.host;
|
||
}
|
||
|
||
// -------------------------------------------------------------------------
|
||
// SLOW: O(N × M) — models the defective mergeL4Filter() pattern
|
||
// -------------------------------------------------------------------------
|
||
|
||
/**
|
||
* Merges newRules into existingRules, skipping duplicates.
|
||
* Models: for _, newRule := range newPolicy.HTTP { if !newRule.Exists(existing) ... }
|
||
* Complexity: O(N × M)
|
||
*/
|
||
static List<HTTPRule> mergeRules_slow(List<HTTPRule> existingRules,
|
||
List<HTTPRule> newRules) {
|
||
List<HTTPRule> merged = new ArrayList<>(existingRules);
|
||
for (HTTPRule newRule : newRules) { // O(N)
|
||
boolean found = false;
|
||
for (HTTPRule existing : merged) { // O(M) — Exists() defect
|
||
if (existing.equal(newRule)) {
|
||
found = true;
|
||
break;
|
||
}
|
||
}
|
||
if (!found) {
|
||
merged.add(newRule);
|
||
}
|
||
}
|
||
return merged;
|
||
}
|
||
|
||
// -------------------------------------------------------------------------
|
||
// FAST: O(N + M) — pre-index existing rules into a hash set
|
||
// -------------------------------------------------------------------------
|
||
|
||
/**
|
||
* Merges newRules into existingRules, skipping duplicates.
|
||
* Builds a hash map of existing rules in O(M), then O(1) per new rule.
|
||
* Total: O(N + M)
|
||
*/
|
||
static List<HTTPRule> mergeRules_fast(List<HTTPRule> existingRules,
|
||
List<HTTPRule> newRules) {
|
||
Set<String> existingSet = new HashSet<>(existingRules.size());
|
||
for (HTTPRule r : existingRules) { // O(M) — one-time construction
|
||
existingSet.add(ruleKey(r));
|
||
}
|
||
List<HTTPRule> merged = new ArrayList<>(existingRules);
|
||
for (HTTPRule newRule : newRules) { // O(N)
|
||
if (!existingSet.contains(ruleKey(newRule))) { // O(1)
|
||
merged.add(newRule);
|
||
existingSet.add(ruleKey(newRule));
|
||
}
|
||
}
|
||
return merged;
|
||
}
|
||
|
||
// -------------------------------------------------------------------------
|
||
// Helpers
|
||
// -------------------------------------------------------------------------
|
||
|
||
static List<HTTPRule> buildRules(int count, String prefix) {
|
||
List<HTTPRule> rules = new ArrayList<>(count);
|
||
for (int i = 0; i < count; i++) {
|
||
rules.add(new HTTPRule(
|
||
"/" + prefix + "/path-" + i,
|
||
(i % 2 == 0) ? "GET" : "POST",
|
||
prefix + "-service.default.svc.cluster.local"
|
||
));
|
||
}
|
||
return rules;
|
||
}
|
||
|
||
/** Build new rules where half overlap with existing, half are new */
|
||
static List<HTTPRule> buildNewRules(int count, List<HTTPRule> existing, int overlapFraction) {
|
||
List<HTTPRule> rules = new ArrayList<>(count);
|
||
int existingSize = existing.size();
|
||
for (int i = 0; i < count; i++) {
|
||
if (i % overlapFraction == 0 && existingSize > 0) {
|
||
// duplicate an existing rule
|
||
HTTPRule orig = existing.get(i % existingSize);
|
||
rules.add(new HTTPRule(orig.path, orig.method, orig.host));
|
||
} else {
|
||
// new unique rule
|
||
rules.add(new HTTPRule("/new/path-" + i, "GET", "new-service.ns.svc"));
|
||
}
|
||
}
|
||
return rules;
|
||
}
|
||
|
||
// -------------------------------------------------------------------------
|
||
// Tests
|
||
// -------------------------------------------------------------------------
|
||
|
||
static void testCorrectness() {
|
||
List<HTTPRule> existing = Arrays.asList(
|
||
new HTTPRule("/api/v1", "GET", "svc.ns"),
|
||
new HTTPRule("/api/v2", "POST", "svc.ns"),
|
||
new HTTPRule("/health", "GET", "svc.ns")
|
||
);
|
||
List<HTTPRule> newRules = Arrays.asList(
|
||
new HTTPRule("/api/v1", "GET", "svc.ns"), // duplicate
|
||
new HTTPRule("/api/v3", "PUT", "svc.ns"), // new
|
||
new HTTPRule("/health", "GET", "svc.ns") // duplicate
|
||
);
|
||
|
||
List<HTTPRule> slow = mergeRules_slow(existing, newRules);
|
||
List<HTTPRule> fast = mergeRules_fast(existing, newRules);
|
||
|
||
// should add only /api/v3 PUT — final size = 4
|
||
assert slow.size() == 4 : "slow: expected 4 rules, got " + slow.size();
|
||
assert fast.size() == 4 : "fast: expected 4 rules, got " + fast.size();
|
||
assert slow.size() == fast.size() : "sizes differ: " + slow.size() + " vs " + fast.size();
|
||
System.out.println("PASS correctness: merged to " + slow.size() + " rules");
|
||
}
|
||
|
||
static void testOpsCount_M100_N100() {
|
||
int M = 100, N = 100;
|
||
List<HTTPRule> existing = buildRules(M, "existing");
|
||
List<HTTPRule> newRules = buildNewRules(N, existing, 3);
|
||
|
||
// Simulate op counting for slow: worst case scan
|
||
long slowBoundOps = (long) N * M; // O(N*M)
|
||
long fastBoundOps = (long) (N + M); // O(N+M)
|
||
|
||
assert slowBoundOps > fastBoundOps * 40 :
|
||
"Expected slowOps >> fastOps, got " + slowBoundOps + " vs " + fastBoundOps;
|
||
|
||
List<HTTPRule> slow = mergeRules_slow(existing, newRules);
|
||
List<HTTPRule> fast = mergeRules_fast(existing, newRules);
|
||
assert slow.size() == fast.size() : "sizes differ: " + slow.size() + " vs " + fast.size();
|
||
|
||
System.out.printf("PASS ops M=%d N=%d: slow_bound=%d fast_bound=%d ratio=%.0fx result=%d%n",
|
||
M, N, slowBoundOps, fastBoundOps,
|
||
(double) slowBoundOps / fastBoundOps, slow.size());
|
||
}
|
||
|
||
static void testPerf_M500_N500() {
|
||
int M = 500, N = 500;
|
||
List<HTTPRule> existing = buildRules(M, "svc");
|
||
List<HTTPRule> newRules = buildNewRules(N, existing, 4);
|
||
|
||
long t0 = System.nanoTime();
|
||
// Simulate 1000 policy reconciliations
|
||
long slowSize = 0;
|
||
for (int i = 0; i < 1000; i++) {
|
||
slowSize += mergeRules_slow(new ArrayList<>(existing), newRules).size();
|
||
}
|
||
long slowMs = (System.nanoTime() - t0) / 1_000_000;
|
||
|
||
long t1 = System.nanoTime();
|
||
long fastSize = 0;
|
||
for (int i = 0; i < 1000; i++) {
|
||
fastSize += mergeRules_fast(new ArrayList<>(existing), newRules).size();
|
||
}
|
||
long fastMs = (System.nanoTime() - t1) / 1_000_000;
|
||
|
||
assert slowSize == fastSize : "sizes differ: " + slowSize + " vs " + fastSize;
|
||
System.out.printf(
|
||
"PASS perf M=%d N=%d 1000 reconciliations: slow=%dms fast=%dms ratio=%.1fx%n",
|
||
M, N, slowMs, fastMs, (double) slowMs / Math.max(fastMs, 1));
|
||
assert slowMs > fastMs :
|
||
"expected slow > fast, got slow=" + slowMs + "ms fast=" + fastMs + "ms";
|
||
}
|
||
|
||
static void testPerf_M1000_N200_stress() {
|
||
// Worst case: large existing policy, many new rules merging in
|
||
int M = 1000, N = 200;
|
||
List<HTTPRule> existing = buildRules(M, "complex-svc");
|
||
List<HTTPRule> newRules = buildNewRules(N, existing, 5);
|
||
|
||
long t0 = System.nanoTime();
|
||
long slowResult = 0;
|
||
for (int i = 0; i < 500; i++) {
|
||
slowResult += mergeRules_slow(new ArrayList<>(existing), newRules).size();
|
||
}
|
||
long slowMs = (System.nanoTime() - t0) / 1_000_000;
|
||
|
||
long t1 = System.nanoTime();
|
||
long fastResult = 0;
|
||
for (int i = 0; i < 500; i++) {
|
||
fastResult += mergeRules_fast(new ArrayList<>(existing), newRules).size();
|
||
}
|
||
long fastMs = (System.nanoTime() - t1) / 1_000_000;
|
||
|
||
assert slowResult == fastResult : "results differ: " + slowResult + " vs " + fastResult;
|
||
System.out.printf(
|
||
"PASS stress M=%d N=%d 500 reconciliations: slow=%dms fast=%dms ratio=%.1fx%n",
|
||
M, N, slowMs, fastMs, (double) slowMs / Math.max(fastMs, 1));
|
||
assert slowMs >= fastMs :
|
||
"expected slow >= fast, got slow=" + slowMs + "ms fast=" + fastMs + "ms";
|
||
}
|
||
|
||
// -------------------------------------------------------------------------
|
||
// Main
|
||
// -------------------------------------------------------------------------
|
||
|
||
public static void main(String[] args) {
|
||
System.out.println("=== Cilium0002Test: L7 rule dedup quadratic (cilium-0002) ===");
|
||
testCorrectness();
|
||
testOpsCount_M100_N100();
|
||
testPerf_M500_N500();
|
||
testPerf_M1000_N200_stress();
|
||
System.out.println("4/4 PASS");
|
||
}
|
||
}
|