271 lines
11 KiB
Java
271 lines
11 KiB
Java
package unit;
|
||
|
||
import java.util.*;
|
||
|
||
/**
|
||
* Linkerd2Algorithm — CWE-407 unit test for linkerd2-0002
|
||
*
|
||
* linkerd2-0002: pkg/inject/inject.go:855-865
|
||
* func FilterPodOpaquePorts(defaultPorts []string) []string {
|
||
* for _, c := range containers { // O(C) containers
|
||
* for _, p := range c.Ports { // O(P) ports
|
||
* port := strconv.Itoa(p.ContainerPort)
|
||
* if util.ContainsString(port, defaultPorts) { // O(D) linear scan
|
||
* ...
|
||
* }
|
||
* }
|
||
* }
|
||
* }
|
||
*
|
||
* util.ContainsString is a linear scan over []string.
|
||
* Called per pod in the linkerd-proxy-injector admission webhook.
|
||
*
|
||
* SLOW: ContainsString(port, defaultPorts) — O(D) per port per container
|
||
* FAST: map[string]struct{} pre-built once — O(1) per port
|
||
*
|
||
* No JUnit. Run: javac -d . Linkerd2Algorithm.java && java -ea unit.Linkerd2Algorithm
|
||
*/
|
||
public class Linkerd2Algorithm {
|
||
|
||
// -------------------------------------------------------------------------
|
||
// Data model — mirrors ContainerPort and Container
|
||
// -------------------------------------------------------------------------
|
||
|
||
static class ContainerPort {
|
||
final int port;
|
||
ContainerPort(int port) { this.port = port; }
|
||
}
|
||
|
||
static class Container {
|
||
final List<ContainerPort> ports;
|
||
Container(List<ContainerPort> ports) { this.ports = ports; }
|
||
}
|
||
|
||
static long slowOps = 0;
|
||
static long fastOps = 0;
|
||
|
||
// -------------------------------------------------------------------------
|
||
// SLOW: O(C × P × D) — models util.ContainsString per port
|
||
// -------------------------------------------------------------------------
|
||
|
||
static boolean containsStringSlow(String str, List<String> collection) {
|
||
for (String s : collection) { // O(D) linear scan
|
||
slowOps++;
|
||
if (s.equals(str)) return true;
|
||
}
|
||
return false;
|
||
}
|
||
|
||
/**
|
||
* Models FilterPodOpaquePorts — find ports that are in the defaultPorts list.
|
||
*/
|
||
static List<String> filterOpaquePortsSlow(List<Container> containers, List<String> defaultPorts) {
|
||
List<String> filteredPorts = new ArrayList<>();
|
||
for (Container c : containers) { // O(C)
|
||
for (ContainerPort p : c.ports) { // O(P)
|
||
String port = String.valueOf(p.port);
|
||
if (containsStringSlow(port, defaultPorts)) { // O(D) — defect
|
||
filteredPorts.add(port);
|
||
}
|
||
}
|
||
}
|
||
return filteredPorts;
|
||
}
|
||
|
||
/**
|
||
* Models the service port annotation check at inject.go:826-841.
|
||
*/
|
||
static List<String> filterServiceOpaquePortsSlow(List<ContainerPort> svcPorts, List<String> defaultPorts) {
|
||
List<String> filtered = new ArrayList<>();
|
||
for (ContainerPort p : svcPorts) { // O(SP)
|
||
String port = String.valueOf(p.port);
|
||
if (containsStringSlow(port, defaultPorts)) { // O(D)
|
||
filtered.add(port);
|
||
}
|
||
}
|
||
return filtered;
|
||
}
|
||
|
||
// -------------------------------------------------------------------------
|
||
// FAST: O(C × P) — pre-build map[string]struct{} once from defaultPorts
|
||
// -------------------------------------------------------------------------
|
||
|
||
static List<String> filterOpaquePortsFast(List<Container> containers, List<String> defaultPorts) {
|
||
// Build set once — O(D)
|
||
Set<String> defaultSet = new HashSet<>(defaultPorts.size() * 2);
|
||
for (String p : defaultPorts) { fastOps++; defaultSet.add(p); }
|
||
|
||
List<String> filteredPorts = new ArrayList<>();
|
||
for (Container c : containers) { // O(C)
|
||
for (ContainerPort p : c.ports) { // O(P)
|
||
String port = String.valueOf(p.port);
|
||
fastOps++;
|
||
if (defaultSet.contains(port)) { // O(1)
|
||
filteredPorts.add(port);
|
||
}
|
||
}
|
||
}
|
||
return filteredPorts;
|
||
}
|
||
|
||
static List<String> filterServiceOpaquePortsFast(List<ContainerPort> svcPorts, List<String> defaultPorts) {
|
||
Set<String> defaultSet = new HashSet<>(defaultPorts);
|
||
List<String> filtered = new ArrayList<>();
|
||
for (ContainerPort p : svcPorts) {
|
||
fastOps++;
|
||
String port = String.valueOf(p.port);
|
||
if (defaultSet.contains(port)) filtered.add(port);
|
||
}
|
||
return filtered;
|
||
}
|
||
|
||
// -------------------------------------------------------------------------
|
||
// Helpers
|
||
// -------------------------------------------------------------------------
|
||
|
||
/** Default opaque ports list (mirrors linkerd2 defaults, extensible) */
|
||
static List<String> buildDefaultPorts(int D) {
|
||
List<String> ports = new ArrayList<>(D);
|
||
// Start from common well-known opaque ports
|
||
int[] wellKnown = {25, 443, 587, 3306, 5432, 6379, 6380, 7000, 7001, 7199,
|
||
8080, 8443, 9042, 9160, 9200, 9300, 10000, 11211, 27017,
|
||
27018, 28015, 50000};
|
||
for (int i = 0; i < D; i++) {
|
||
if (i < wellKnown.length) {
|
||
ports.add(String.valueOf(wellKnown[i]));
|
||
} else {
|
||
ports.add(String.valueOf(30000 + i));
|
||
}
|
||
}
|
||
return ports;
|
||
}
|
||
|
||
/** Build containers, each with P ports. Half ports are from defaultPorts. */
|
||
static List<Container> buildContainers(int C, int P, List<String> defaultPorts) {
|
||
List<Container> containers = new ArrayList<>(C);
|
||
for (int i = 0; i < C; i++) {
|
||
List<ContainerPort> ports = new ArrayList<>(P);
|
||
for (int j = 0; j < P; j++) {
|
||
// Alternate: every other port is from defaultPorts
|
||
if (j % 2 == 0 && !defaultPorts.isEmpty()) {
|
||
ports.add(new ContainerPort(Integer.parseInt(defaultPorts.get(j % defaultPorts.size()))));
|
||
} else {
|
||
ports.add(new ContainerPort(8000 + i * P + j));
|
||
}
|
||
}
|
||
containers.add(new Container(ports));
|
||
}
|
||
return containers;
|
||
}
|
||
|
||
// -------------------------------------------------------------------------
|
||
// Tests
|
||
// -------------------------------------------------------------------------
|
||
|
||
static void testCorrectness() {
|
||
List<String> defaultPorts = Arrays.asList("3306", "5432", "6379", "443");
|
||
List<Container> containers = new ArrayList<>();
|
||
// Container with mysql port (should match) and a random port
|
||
containers.add(new Container(Arrays.asList(
|
||
new ContainerPort(3306), // MySQL — opaque
|
||
new ContainerPort(8080) // App — not opaque
|
||
)));
|
||
containers.add(new Container(Arrays.asList(
|
||
new ContainerPort(5432), // PostgreSQL — opaque
|
||
new ContainerPort(9000) // Monitoring — not opaque
|
||
)));
|
||
|
||
List<String> slowResult = filterOpaquePortsSlow(containers, defaultPorts);
|
||
List<String> fastResult = filterOpaquePortsFast(containers, defaultPorts);
|
||
|
||
assert slowResult.size() == 2 : "slow: expected 2 opaque ports, got " + slowResult.size();
|
||
assert fastResult.size() == 2 : "fast: expected 2 opaque ports, got " + fastResult.size();
|
||
assert slowResult.equals(fastResult) : "results differ: " + slowResult + " vs " + fastResult;
|
||
System.out.println("PASS correctness: opaque port filtering verified");
|
||
}
|
||
|
||
static void testOpsCount_C5_P10_D25() {
|
||
int C = 5, P = 10, D = 25;
|
||
List<String> defaultPorts = buildDefaultPorts(D);
|
||
List<Container> containers = buildContainers(C, P, defaultPorts);
|
||
|
||
slowOps = 0; fastOps = 0;
|
||
List<String> slowResult = filterOpaquePortsSlow(containers, defaultPorts);
|
||
long afterSlow = slowOps;
|
||
List<String> fastResult = filterOpaquePortsFast(containers, defaultPorts);
|
||
long fastOnly = fastOps;
|
||
|
||
assert slowResult.size() == fastResult.size()
|
||
: "sizes differ: " + slowResult.size() + " vs " + fastResult.size();
|
||
|
||
System.out.printf("PASS ops_count C=%d P=%d D=%d: slowOps=%d fastOps=%d ratio=%.1fx%n",
|
||
C, P, D, afterSlow, fastOnly, (double) afterSlow / Math.max(fastOnly, 1));
|
||
assert afterSlow >= fastOnly * 3 :
|
||
"expected slowOps >> fastOps, got slow=" + afterSlow + " fast=" + fastOnly;
|
||
}
|
||
|
||
static void testPerf_C10_P20_D50_HighChurn() {
|
||
int C = 10, P = 20, D = 50;
|
||
List<String> defaultPorts = buildDefaultPorts(D);
|
||
List<Container> containers = buildContainers(C, P, defaultPorts);
|
||
|
||
long t0 = System.nanoTime();
|
||
int slowResult = 0;
|
||
for (int i = 0; i < 10000; i++) {
|
||
slowResult += filterOpaquePortsSlow(containers, defaultPorts).size();
|
||
}
|
||
long slowMs = (System.nanoTime() - t0) / 1_000_000;
|
||
|
||
long t1 = System.nanoTime();
|
||
int fastResult = 0;
|
||
for (int i = 0; i < 10000; i++) {
|
||
fastResult += filterOpaquePortsFast(containers, defaultPorts).size();
|
||
}
|
||
long fastMs = (System.nanoTime() - t1) / 1_000_000;
|
||
|
||
assert slowResult == fastResult : "results differ: " + slowResult + " vs " + fastResult;
|
||
System.out.printf("PASS perf C=%d P=%d D=%d 10000 injections: slow=%dms fast=%dms ratio=%.1fx%n",
|
||
C, P, D, slowMs, fastMs, (double) slowMs / Math.max(fastMs, 1));
|
||
assert slowMs >= fastMs :
|
||
"expected slow >= fast, got slow=" + slowMs + "ms fast=" + fastMs + "ms";
|
||
}
|
||
|
||
static void testPerf_C20_P30_D100_stress() {
|
||
int C = 20, P = 30, D = 100;
|
||
List<String> defaultPorts = buildDefaultPorts(D);
|
||
List<Container> containers = buildContainers(C, P, defaultPorts);
|
||
|
||
long t0 = System.nanoTime();
|
||
int slowResult = 0;
|
||
for (int i = 0; i < 3000; i++) {
|
||
slowResult += filterOpaquePortsSlow(containers, defaultPorts).size();
|
||
}
|
||
long slowMs = (System.nanoTime() - t0) / 1_000_000;
|
||
|
||
long t1 = System.nanoTime();
|
||
int fastResult = 0;
|
||
for (int i = 0; i < 3000; i++) {
|
||
fastResult += filterOpaquePortsFast(containers, defaultPorts).size();
|
||
}
|
||
long fastMs = (System.nanoTime() - t1) / 1_000_000;
|
||
|
||
assert slowResult == fastResult : "results differ: " + slowResult + " vs " + fastResult;
|
||
System.out.printf("PASS stress C=%d P=%d D=%d 3000 injections: slow=%dms fast=%dms ratio=%.1fx%n",
|
||
C, P, D, 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("=== Linkerd2Algorithm: inject opaque port filter (linkerd2-0002) ===");
|
||
testCorrectness();
|
||
testOpsCount_C5_P10_D25();
|
||
testPerf_C10_P20_D50_HighChurn();
|
||
testPerf_C20_P30_D100_stress();
|
||
System.out.println("4/4 PASS");
|
||
}
|
||
}
|