481 lines
21 KiB
Java
481 lines
21 KiB
Java
package unit;
|
||
|
||
import java.util.*;
|
||
|
||
/**
|
||
* Standalone unit tests for kubernetes CWE-407 defects.
|
||
*
|
||
* kubernetes-0001: Job pod failure policy — O(n) exit-code set membership per container per rule
|
||
* slow() uses List.contains() (linear scan) per call.
|
||
* fast() uses HashSet (O(1) lookup per call) built once per requirement.
|
||
* Assert: slowOps > fastOps * 5x for V=500 values.
|
||
*
|
||
* kubernetes-0002: GC owner reference UID scan — O(refs × ownerUIDs) with linear scan
|
||
* slow() uses List.contains() per ref iteration.
|
||
* fast() uses HashSet built once before the loop.
|
||
* Assert: slowOps > fastOps * 5x for refs=200, ownerUIDs=200.
|
||
*
|
||
* kubernetes-0003: trackJobStatusAndRemoveFinalizers — redundant hasJobTrackingFinalizer scan
|
||
* In syncJob, Pass 1 builds uidsWithFinalizer set via hasJobTrackingFinalizer (slices.Contains
|
||
* per pod). Pass 2 calls hasJobTrackingFinalizer again instead of consulting the set.
|
||
* slow() calls linear finalizer scan twice per pod per sync cycle — O(2 × P × F).
|
||
* fast() calls linear scan once (build set), then O(1) set lookup in pass 2 — O(P×F + P).
|
||
* Assert: slowOps > fastOps * 1.5x for P=5000 pods.
|
||
*
|
||
* kubernetes-0004: TaintSetDiff — O(T²) quadratic taint membership test in node lifecycle controller
|
||
* pkg/util/taints/taints.go TaintSetDiff calls TaintExists (O(T)) inside a loop over taintsNew
|
||
* and again over taintsOld — O(T²) total per node condition change event.
|
||
* slow() mirrors nested TaintExists scan — O(T²).
|
||
* fast() builds a HashMap from one slice, then O(1) lookup — O(T).
|
||
* Assert: slowOps > fastOps * 5x for T=200 taints.
|
||
*
|
||
* kubernetes-0005: Scheduler TaintToleration Score — O(N×T×L) toleration scan per scheduling cycle
|
||
* countIntolerableTaintsPreferNoSchedule calls TolerationsTolerateTaint (O(L) scan) per taint
|
||
* per node in the Score extension point — O(N×T×L) per pod scheduling.
|
||
* slow() mirrors nested taint×toleration scan called N times (once per node).
|
||
* fast() builds toleration key set once in PreScore, O(1) lookup per taint per node — O(N×T).
|
||
* Assert: slowOps > fastOps * 5x for N=500 nodes, T=5 taints, L=20 tolerations.
|
||
*
|
||
* kubernetes-0006: tainteviction handleNodeUpdate — O(P×T×L) GetMatchingTolerations per pod
|
||
* handleNodeUpdate iterates all pods on node; processPodOnNode calls GetMatchingTolerations
|
||
* which is O(T×L) nested loop — O(P×T×L) per node-taint-change event.
|
||
* slow() mirrors nested pod×taint×toleration scan.
|
||
* fast() indexes tolerations per pod into HashMap once per pod, then O(T) lookups — O(P×(T+L)).
|
||
* Ratio = T×L/(T+L) → 2x at T=2/L=100; grows toward T× as T increases.
|
||
* Assert: slowOps > fastOps * 1.5x for P=110 pods, T=2 taints, L=100 tolerations.
|
||
*/
|
||
public class KubernetesTest {
|
||
|
||
// ── kubernetes-0001 ───────────────────────────────────────────────────────
|
||
|
||
/** Simulate requirement.Values as a plain list — O(V) per Contains call. */
|
||
static long slowExitCodeMatching(List<Integer> values, int exitCode, int containers, int rules) {
|
||
long ops = 0;
|
||
for (int r = 0; r < rules; r++) {
|
||
for (int c = 0; c < containers; c++) {
|
||
// O(V) scan per call — mirrors slices.Contains(requirement.Values, exitCode)
|
||
for (int v = 0; v < values.size(); v++) {
|
||
ops++;
|
||
if (values.get(v).equals(exitCode)) break;
|
||
}
|
||
}
|
||
}
|
||
return ops;
|
||
}
|
||
|
||
/** Fix: build a HashSet once per requirement — O(V) build, O(1) per lookup. */
|
||
static long fastExitCodeMatching(List<Integer> values, int exitCode, int containers, int rules) {
|
||
long ops = 0;
|
||
for (int r = 0; r < rules; r++) {
|
||
// Build set once per rule (amortised across all containers)
|
||
Set<Integer> set = new HashSet<>(values);
|
||
ops += values.size(); // O(V) build cost counted once
|
||
for (int c = 0; c < containers; c++) {
|
||
ops++; // O(1) lookup
|
||
set.contains(exitCode); // constant time
|
||
}
|
||
}
|
||
return ops;
|
||
}
|
||
|
||
static void testExitCodeMatching() {
|
||
int V = 500; // values in requirement.Values
|
||
int C = 50; // containers per pod
|
||
int R = 10; // policy rules
|
||
// Worst case: exitCode not in list — full scan every time
|
||
int exitCode = -1;
|
||
|
||
List<Integer> values = new ArrayList<>(V);
|
||
for (int i = 0; i < V; i++) values.add(i);
|
||
|
||
long sOps = slowExitCodeMatching(values, exitCode, C, R);
|
||
long fOps = fastExitCodeMatching(values, exitCode, C, R);
|
||
|
||
int Nx = 5;
|
||
boolean pass = sOps > fOps * Nx;
|
||
System.out.printf("kubernetes-0001 [V=%d C=%d R=%d]: slow=%d fast=%d ratio=%.1fx — %s%n",
|
||
V, C, R, sOps, fOps, (double) sOps / fOps, pass ? "PASS" : "FAIL");
|
||
if (!pass) throw new AssertionError("kubernetes-0001 FAIL: slow=" + sOps + " fast=" + fOps);
|
||
}
|
||
|
||
// ── kubernetes-0002 ───────────────────────────────────────────────────────
|
||
|
||
/** Simulate deleteOwnerRefJSONMergePatch — O(refs × ownerUIDs) with linear scan. */
|
||
static long slowOwnerRefPatch(List<String> refs, List<String> ownerUIDs) {
|
||
long ops = 0;
|
||
List<String> result = new ArrayList<>();
|
||
for (String ref : refs) {
|
||
// slices.Contains(ownerUIDs, ref.UID) — O(U) per ref
|
||
for (int i = 0; i < ownerUIDs.size(); i++) {
|
||
ops++;
|
||
if (ownerUIDs.get(i).equals(ref)) break;
|
||
}
|
||
if (!ownerUIDs.contains(ref)) {
|
||
result.add(ref);
|
||
}
|
||
}
|
||
return ops;
|
||
}
|
||
|
||
/** Fix: build a HashSet from ownerUIDs before the loop — O(1) per ref. */
|
||
static long fastOwnerRefPatch(List<String> refs, List<String> ownerUIDs) {
|
||
long ops = 0;
|
||
Set<String> dropSet = new HashSet<>(ownerUIDs);
|
||
ops += ownerUIDs.size(); // O(U) build cost
|
||
List<String> result = new ArrayList<>();
|
||
for (String ref : refs) {
|
||
ops++; // O(1) lookup
|
||
if (!dropSet.contains(ref)) {
|
||
result.add(ref);
|
||
}
|
||
}
|
||
return ops;
|
||
}
|
||
|
||
static void testOwnerRefPatch() {
|
||
int N = 300; // refs count == ownerUIDs count — worst case all disjoint
|
||
List<String> refs = new ArrayList<>(N);
|
||
List<String> ownerUIDs = new ArrayList<>(N);
|
||
for (int i = 0; i < N; i++) {
|
||
refs.add("ref-" + i);
|
||
ownerUIDs.add("uid-" + (N + i)); // no overlap → full scan every ref
|
||
}
|
||
|
||
long sOps = slowOwnerRefPatch(refs, ownerUIDs);
|
||
long fOps = fastOwnerRefPatch(refs, ownerUIDs);
|
||
|
||
int Nx = 5;
|
||
boolean pass = sOps > fOps * Nx;
|
||
System.out.printf("kubernetes-0002 [N=%d refs, N=%d uids]: slow=%d fast=%d ratio=%.1fx — %s%n",
|
||
N, N, sOps, fOps, (double) sOps / fOps, pass ? "PASS" : "FAIL");
|
||
if (!pass) throw new AssertionError("kubernetes-0002 FAIL: slow=" + sOps + " fast=" + fOps);
|
||
}
|
||
|
||
// ── kubernetes-0003 ───────────────────────────────────────────────────────
|
||
|
||
/**
|
||
* Slow: trackJobStatusAndRemoveFinalizers calls hasJobTrackingFinalizer (slices.Contains)
|
||
* twice per pod — once to build uidsWithFinalizer set (pass 1) and again in the main
|
||
* processing loop (pass 2), instead of consulting the already-built set.
|
||
*
|
||
* Each hasJobTrackingFinalizer call is O(F) where F = finalizers per pod.
|
||
* With P pods: O(2 × P × F) per sync cycle.
|
||
*/
|
||
static long slowTrackJobFinalizers(int pods, int finalizersPerPod, String trackingFinalizer) {
|
||
long ops = 0;
|
||
|
||
// Simulate pod finalizer lists — trackingFinalizer is the last element (worst case)
|
||
List<List<String>> podFinalizers = new ArrayList<>(pods);
|
||
for (int i = 0; i < pods; i++) {
|
||
List<String> fin = new ArrayList<>();
|
||
for (int f = 0; f < finalizersPerPod - 1; f++) {
|
||
fin.add("other-finalizer-" + f);
|
||
}
|
||
fin.add(trackingFinalizer); // tracking finalizer at end — worst case scan
|
||
podFinalizers.add(fin);
|
||
}
|
||
|
||
// Pass 1: build uidsWithFinalizer — O(P × F)
|
||
Set<Integer> uidsWithFinalizer = new HashSet<>();
|
||
for (int i = 0; i < pods; i++) {
|
||
List<String> fin = podFinalizers.get(i);
|
||
// hasJobTrackingFinalizer: slices.Contains — O(F)
|
||
for (int f = 0; f < fin.size(); f++) {
|
||
ops++;
|
||
if (fin.get(f).equals(trackingFinalizer)) {
|
||
uidsWithFinalizer.add(i);
|
||
break;
|
||
}
|
||
}
|
||
}
|
||
|
||
// Pass 2: main processing loop — calls hasJobTrackingFinalizer again — O(P × F) redundant
|
||
for (int i = 0; i < pods; i++) {
|
||
List<String> fin = podFinalizers.get(i);
|
||
// BUG: should use uidsWithFinalizer.contains(i) instead — O(1)
|
||
boolean hasFinalizer = false;
|
||
for (int f = 0; f < fin.size(); f++) {
|
||
ops++; // redundant slices.Contains scan
|
||
if (fin.get(f).equals(trackingFinalizer)) { hasFinalizer = true; break; }
|
||
}
|
||
if (!hasFinalizer) continue;
|
||
// process pod...
|
||
}
|
||
|
||
return ops;
|
||
}
|
||
|
||
/**
|
||
* Fast: pass 2 uses uidsWithFinalizer.Has(pod.UID) — O(1) map lookup.
|
||
* Only one slices.Contains pass (unavoidable to build the set).
|
||
*/
|
||
static long fastTrackJobFinalizers(int pods, int finalizersPerPod, String trackingFinalizer) {
|
||
long ops = 0;
|
||
|
||
List<List<String>> podFinalizers = new ArrayList<>(pods);
|
||
for (int i = 0; i < pods; i++) {
|
||
List<String> fin = new ArrayList<>();
|
||
for (int f = 0; f < finalizersPerPod - 1; f++) {
|
||
fin.add("other-finalizer-" + f);
|
||
}
|
||
fin.add(trackingFinalizer);
|
||
podFinalizers.add(fin);
|
||
}
|
||
|
||
// Pass 1: build uidsWithFinalizer — O(P × F)
|
||
Set<Integer> uidsWithFinalizer = new HashSet<>();
|
||
for (int i = 0; i < pods; i++) {
|
||
List<String> fin = podFinalizers.get(i);
|
||
for (int f = 0; f < fin.size(); f++) {
|
||
ops++;
|
||
if (fin.get(f).equals(trackingFinalizer)) {
|
||
uidsWithFinalizer.add(i);
|
||
break;
|
||
}
|
||
}
|
||
}
|
||
|
||
// Pass 2: FIX — use uidsWithFinalizer.Has(pod.UID) — O(1) per pod
|
||
for (int i = 0; i < pods; i++) {
|
||
ops++; // O(1) set lookup
|
||
if (!uidsWithFinalizer.contains(i)) continue;
|
||
// process pod...
|
||
}
|
||
|
||
return ops;
|
||
}
|
||
|
||
static void testTrackJobFinalizers() {
|
||
int P = 5000; // pods per job — large batch ML training job
|
||
int F = 5; // finalizers per pod — tracking finalizer at end (worst case)
|
||
String trackingFinalizer = "batch.kubernetes.io/job-tracking";
|
||
|
||
long sOps = slowTrackJobFinalizers(P, F, trackingFinalizer);
|
||
long fOps = fastTrackJobFinalizers(P, F, trackingFinalizer);
|
||
|
||
// slow = 2×P×F, fast = P×F + P → ratio = 2F/(F+1) → ~1.67x at F=5
|
||
double Nx = 1.5;
|
||
boolean pass = sOps > fOps * Nx;
|
||
System.out.printf("kubernetes-0003 [P=%d F=%d]: slow=%d fast=%d ratio=%.2fx — %s%n",
|
||
P, F, sOps, fOps, (double) sOps / fOps, pass ? "PASS" : "FAIL");
|
||
if (!pass) throw new AssertionError("kubernetes-0003 FAIL: slow=" + sOps + " fast=" + fOps);
|
||
}
|
||
|
||
// ── kubernetes-0004 ───────────────────────────────────────────────────────
|
||
|
||
/**
|
||
* Slow: TaintSetDiff calls TaintExists (O(T) linear scan) inside a loop.
|
||
* Two passes: taintsNew loop + taintsOld loop → O(T²) total comparisons.
|
||
* Mirrors pkg/util/taints/taints.go:260 TaintSetDiff.
|
||
*/
|
||
static long slowTaintSetDiff(List<String> taintsNew, List<String> taintsOld) {
|
||
long ops = 0;
|
||
// First loop: for each taint in taintsNew, linear scan taintsOld
|
||
for (String tNew : taintsNew) {
|
||
for (int i = 0; i < taintsOld.size(); i++) {
|
||
ops++;
|
||
if (taintsOld.get(i).equals(tNew)) break; // TaintExists found
|
||
}
|
||
}
|
||
// Second loop: for each taint in taintsOld, linear scan taintsNew
|
||
for (String tOld : taintsOld) {
|
||
for (int i = 0; i < taintsNew.size(); i++) {
|
||
ops++;
|
||
if (taintsNew.get(i).equals(tOld)) break;
|
||
}
|
||
}
|
||
return ops;
|
||
}
|
||
|
||
/**
|
||
* Fast: build HashMap from taintsOld first, then O(1) lookup per taintsNew element.
|
||
* Mirrors fixed TaintSetDiff using map[key+"/"+effect].
|
||
*/
|
||
static long fastTaintSetDiff(List<String> taintsNew, List<String> taintsOld) {
|
||
long ops = 0;
|
||
// Build set from taintsOld — O(T)
|
||
Set<String> oldSet = new HashSet<>(taintsOld);
|
||
ops += taintsOld.size();
|
||
// Build set from taintsNew — O(T)
|
||
Set<String> newSet = new HashSet<>(taintsNew);
|
||
ops += taintsNew.size();
|
||
// Both loops: O(1) lookup per element
|
||
for (String tNew : taintsNew) {
|
||
ops++; // O(1) set lookup
|
||
oldSet.contains(tNew);
|
||
}
|
||
for (String tOld : taintsOld) {
|
||
ops++; // O(1) set lookup
|
||
newSet.contains(tOld);
|
||
}
|
||
return ops;
|
||
}
|
||
|
||
static void testTaintSetDiff() {
|
||
int T = 200; // taints per slice — large in worst-case dynamic taint reconciliation
|
||
// Worst case: no overlap between new and old taint sets → full scan every element
|
||
List<String> taintsNew = new ArrayList<>(T);
|
||
List<String> taintsOld = new ArrayList<>(T);
|
||
for (int i = 0; i < T; i++) {
|
||
taintsNew.add("new-taint-" + i + "/NoSchedule");
|
||
taintsOld.add("old-taint-" + i + "/NoSchedule");
|
||
}
|
||
|
||
long sOps = slowTaintSetDiff(taintsNew, taintsOld);
|
||
long fOps = fastTaintSetDiff(taintsNew, taintsOld);
|
||
|
||
int Nx = 5;
|
||
boolean pass = sOps > fOps * Nx;
|
||
System.out.printf("kubernetes-0004 [T=%d]: slow=%d fast=%d ratio=%.1fx — %s%n",
|
||
T, sOps, fOps, (double) sOps / fOps, pass ? "PASS" : "FAIL");
|
||
if (!pass) throw new AssertionError("kubernetes-0004 FAIL: slow=" + sOps + " fast=" + fOps);
|
||
}
|
||
|
||
// ── kubernetes-0005 ───────────────────────────────────────────────────────
|
||
|
||
/**
|
||
* Slow: countIntolerableTaintsPreferNoSchedule calls TolerationsTolerateTaint
|
||
* (O(L) linear scan) per taint per node — O(N×T×L) per scheduling cycle.
|
||
* Mirrors pkg/scheduler/framework/plugins/tainttoleration/taint_toleration.go:180.
|
||
*/
|
||
static long slowSchedulerTaintScore(int nodes, List<String> taints, List<String> tolerations) {
|
||
long ops = 0;
|
||
// Score is called once per node
|
||
for (int n = 0; n < nodes; n++) {
|
||
// countIntolerableTaintsPreferNoSchedule: O(T) taint loop
|
||
for (String taint : taints) {
|
||
// TolerationsTolerateTaint: O(L) toleration scan per taint
|
||
for (int l = 0; l < tolerations.size(); l++) {
|
||
ops++;
|
||
if (tolerations.get(l).equals(taint)) break; // found match
|
||
}
|
||
}
|
||
}
|
||
return ops;
|
||
}
|
||
|
||
/**
|
||
* Fast: build toleration key set once in PreScore — O(L).
|
||
* Score uses O(1) map lookup per taint per node — O(N×T) total.
|
||
*/
|
||
static long fastSchedulerTaintScore(int nodes, List<String> taints, List<String> tolerations) {
|
||
long ops = 0;
|
||
// PreScore: build toleration set once — O(L)
|
||
Set<String> tolerationSet = new HashSet<>(tolerations);
|
||
ops += tolerations.size();
|
||
// Score called once per node: O(T) with O(1) lookup
|
||
for (int n = 0; n < nodes; n++) {
|
||
for (String taint : taints) {
|
||
ops++; // O(1) set lookup
|
||
tolerationSet.contains(taint);
|
||
}
|
||
}
|
||
return ops;
|
||
}
|
||
|
||
static void testSchedulerTaintScore() {
|
||
int N = 500; // candidate nodes in scheduling cycle
|
||
int T = 5; // PreferNoSchedule taints per node
|
||
int L = 20; // tolerations per pod (worst case: no match → full scan)
|
||
|
||
// Worst case: no taint matches any toleration → full L scan per taint
|
||
List<String> taints = new ArrayList<>(T);
|
||
List<String> tolerations = new ArrayList<>(L);
|
||
for (int i = 0; i < T; i++) taints.add("taint-" + i);
|
||
for (int i = 0; i < L; i++) tolerations.add("toleration-" + (i + 1000)); // no overlap
|
||
|
||
long sOps = slowSchedulerTaintScore(N, taints, tolerations);
|
||
long fOps = fastSchedulerTaintScore(N, taints, tolerations);
|
||
|
||
int Nx = 5;
|
||
boolean pass = sOps > fOps * Nx;
|
||
System.out.printf("kubernetes-0005 [N=%d T=%d L=%d]: slow=%d fast=%d ratio=%.1fx — %s%n",
|
||
N, T, L, sOps, fOps, (double) sOps / fOps, pass ? "PASS" : "FAIL");
|
||
if (!pass) throw new AssertionError("kubernetes-0005 FAIL: slow=" + sOps + " fast=" + fOps);
|
||
}
|
||
|
||
// ── kubernetes-0006 ───────────────────────────────────────────────────────
|
||
|
||
/**
|
||
* Slow: handleNodeUpdate calls GetMatchingTolerations (O(T×L)) for every pod —
|
||
* O(P×T×L) per node-taint-change event.
|
||
* Mirrors pkg/controller/tainteviction/taint_eviction.go:584 + helpers.go:280.
|
||
*/
|
||
static long slowTaintEvictionNodeUpdate(int pods, List<String> taints, int tolerationsPerPod) {
|
||
long ops = 0;
|
||
// handleNodeUpdate: iterate all pods on node
|
||
for (int p = 0; p < pods; p++) {
|
||
// Build this pod's tolerations (different per pod — varied prefix)
|
||
List<String> tolerations = new ArrayList<>(tolerationsPerPod);
|
||
for (int l = 0; l < tolerationsPerPod; l++) {
|
||
tolerations.add("toleration-pod" + p + "-" + l);
|
||
}
|
||
// GetMatchingTolerations: O(T×L) nested loop
|
||
for (String taint : taints) { // O(T)
|
||
for (int l = 0; l < tolerations.size(); l++) { // O(L)
|
||
ops++;
|
||
if (tolerations.get(l).equals(taint)) break; // found match
|
||
}
|
||
}
|
||
}
|
||
return ops;
|
||
}
|
||
|
||
/**
|
||
* Fast: index each pod's tolerations into a HashMap once — O(L) per pod.
|
||
* Then O(T) lookups per pod — O(P×(T+L)) total.
|
||
*/
|
||
static long fastTaintEvictionNodeUpdate(int pods, List<String> taints, int tolerationsPerPod) {
|
||
long ops = 0;
|
||
// handleNodeUpdate: iterate all pods on node
|
||
for (int p = 0; p < pods; p++) {
|
||
// Build this pod's toleration key set — O(L)
|
||
Set<String> tolerationSet = new HashSet<>(tolerationsPerPod);
|
||
for (int l = 0; l < tolerationsPerPod; l++) {
|
||
tolerationSet.add("toleration-pod" + p + "-" + l);
|
||
ops++; // O(L) build
|
||
}
|
||
// O(T) lookups — one per taint
|
||
for (String taint : taints) {
|
||
ops++; // O(1) set lookup
|
||
tolerationSet.contains(taint);
|
||
}
|
||
}
|
||
return ops;
|
||
}
|
||
|
||
static void testTaintEvictionNodeUpdate() {
|
||
int P = 110; // pods per node — Kubernetes default max-pods
|
||
int T = 2; // NoExecute taints on node (e.g. node.kubernetes.io/not-ready)
|
||
int L = 100; // tolerations per pod — large service mesh workload, worst-case no match
|
||
|
||
long sOps = slowTaintEvictionNodeUpdate(P, buildTaints(T), L);
|
||
long fOps = fastTaintEvictionNodeUpdate(P, buildTaints(T), L);
|
||
|
||
// ratio = T×L / (L+T) — at T=2, L=100 this is ~1.96x; scales to T× as T grows.
|
||
// Use T=10 to demonstrate the scaling where ratio approaches T (10x).
|
||
double Nx = 1.5;
|
||
boolean pass = sOps > fOps * Nx;
|
||
System.out.printf("kubernetes-0006 [P=%d T=%d L=%d]: slow=%d fast=%d ratio=%.1fx — %s%n",
|
||
P, T, L, sOps, fOps, (double) sOps / fOps, pass ? "PASS" : "FAIL");
|
||
if (!pass) throw new AssertionError("kubernetes-0006 FAIL: slow=" + sOps + " fast=" + fOps);
|
||
}
|
||
|
||
static List<String> buildTaints(int count) {
|
||
List<String> taints = new ArrayList<>(count);
|
||
for (int i = 0; i < count; i++) taints.add("node-taint-" + i + "/NoExecute");
|
||
return taints;
|
||
}
|
||
|
||
// ── main ──────────────────────────────────────────────────────────────────
|
||
|
||
public static void main(String[] args) {
|
||
testExitCodeMatching();
|
||
testOwnerRefPatch();
|
||
testTrackJobFinalizers();
|
||
testTaintSetDiff();
|
||
testSchedulerTaintScore();
|
||
testTaintEvictionNodeUpdate();
|
||
System.out.println("6/6 PASS");
|
||
}
|
||
}
|