296 lines
11 KiB
Java
296 lines
11 KiB
Java
package unit;
|
||
|
||
import java.util.ArrayList;
|
||
import java.util.HashMap;
|
||
import java.util.HashSet;
|
||
import java.util.List;
|
||
import java.util.Map;
|
||
import java.util.Set;
|
||
|
||
/**
|
||
* nomad CWE-407 unit tests:
|
||
*
|
||
* nomad-0001: Bitmap.IndexesInRangeFiltered — slices.Contains(filter) inside O(range) loop
|
||
* nomad-0002: stream/subscription.filter() — slices.Contains(namespaces) per event
|
||
* nomad-0003: GetVaultConfigurations dedup — slices.Contains(secrets) inside nested loops
|
||
* nomad-0004: checkstore.Difference — slices.Contains(ids) per stored check
|
||
*
|
||
* No JUnit, no external deps.
|
||
* Compile: javac -d . NomadAlgorithmTest.java
|
||
* Run: java -ea unit.NomadAlgorithmTest
|
||
*/
|
||
public class NomadAlgorithmTest {
|
||
|
||
static int passed = 0;
|
||
static int total = 0;
|
||
|
||
// -----------------------------------------------------------------------
|
||
// nomad-0001: Bitmap.IndexesInRangeFiltered
|
||
// -----------------------------------------------------------------------
|
||
|
||
/**
|
||
* Slow: mirrors Go IndexesInRangeFiltered with slices.Contains.
|
||
* For each index in [from, to], linearly scans filter[] → O(range × |filter|).
|
||
*/
|
||
static long slowIndexesInRangeFiltered(boolean[] bitmap, int from, int to, int[] filter) {
|
||
long ops = 0;
|
||
List<Integer> result = new ArrayList<>();
|
||
for (int i = from; i <= to; i++) {
|
||
ops++;
|
||
if (!bitmap[i]) {
|
||
if (filter.length == 0) {
|
||
result.add(i);
|
||
} else {
|
||
// linear scan — the defect
|
||
boolean skip = false;
|
||
for (int f : filter) {
|
||
ops++;
|
||
if (f == i) { skip = true; break; }
|
||
}
|
||
if (!skip) result.add(i);
|
||
}
|
||
}
|
||
}
|
||
return ops;
|
||
}
|
||
|
||
/**
|
||
* Fast: build map[int] from filter once, then O(1) lookup per index → O(range + |filter|).
|
||
*/
|
||
static long fastIndexesInRangeFiltered(boolean[] bitmap, int from, int to, int[] filter) {
|
||
long ops = 0;
|
||
Set<Integer> filterSet = new HashSet<>();
|
||
for (int f : filter) { filterSet.add(f); ops++; }
|
||
List<Integer> result = new ArrayList<>();
|
||
for (int i = from; i <= to; i++) {
|
||
ops++;
|
||
if (!bitmap[i]) {
|
||
if (filterSet.isEmpty() || !filterSet.contains(i)) {
|
||
result.add(i);
|
||
}
|
||
}
|
||
}
|
||
return ops;
|
||
}
|
||
|
||
static void testBitmapFilter() {
|
||
System.out.println("--- nomad-0001: Bitmap.IndexesInRangeFiltered ---");
|
||
// Simulate port range 20000-60000 (40000 ports), P already-offered ports
|
||
int minPort = 20000;
|
||
int maxPort = 60000;
|
||
int bitmapSize = maxPort + 1;
|
||
boolean[] bitmap = new boolean[bitmapSize]; // all false = available
|
||
|
||
int[] offerSizes = {10, 50, 100};
|
||
for (int p : offerSizes) {
|
||
int[] filter = new int[p];
|
||
for (int i = 0; i < p; i++) filter[i] = minPort + i;
|
||
|
||
long slowOps = slowIndexesInRangeFiltered(bitmap, minPort, maxPort, filter);
|
||
long fastOps = fastIndexesInRangeFiltered(bitmap, minPort, maxPort, filter);
|
||
|
||
double ratio = (double) slowOps / fastOps;
|
||
boolean pass = ratio > (double) p / 2.0; // conservative: expect at least p/2 speedup
|
||
total++;
|
||
if (pass) passed++;
|
||
System.out.printf(" range=%d filter=%-3d slow=%,10d fast=%,10d ratio=%6.1fx %s%n",
|
||
maxPort - minPort, p, slowOps, fastOps, ratio, pass ? "PASS" : "FAIL");
|
||
assert pass : "nomad-0001 FAIL: ratio=" + ratio + " expected >" + (p / 2.0);
|
||
}
|
||
}
|
||
|
||
// -----------------------------------------------------------------------
|
||
// nomad-0002: stream/subscription filter — namespace check per event
|
||
// -----------------------------------------------------------------------
|
||
|
||
/**
|
||
* Slow: slices.Contains(namespaces, event.Namespace) per event → O(E × N).
|
||
*/
|
||
static long slowFilterEvents(String[] events, String[] namespaces) {
|
||
long ops = 0;
|
||
List<String> result = new ArrayList<>();
|
||
for (String event : events) {
|
||
ops++;
|
||
// linear scan over namespaces
|
||
boolean found = false;
|
||
for (String ns : namespaces) {
|
||
ops++;
|
||
if (ns.equals(event)) { found = true; break; }
|
||
}
|
||
if (found) result.add(event);
|
||
}
|
||
return ops;
|
||
}
|
||
|
||
/**
|
||
* Fast: pre-build HashSet from namespaces → O(E + N).
|
||
*/
|
||
static long fastFilterEvents(String[] events, String[] namespaces) {
|
||
long ops = 0;
|
||
Set<String> nsSet = new HashSet<>();
|
||
for (String ns : namespaces) { nsSet.add(ns); ops++; }
|
||
List<String> result = new ArrayList<>();
|
||
for (String event : events) {
|
||
ops++;
|
||
if (nsSet.contains(event)) result.add(event);
|
||
}
|
||
return ops;
|
||
}
|
||
|
||
static void testStreamNamespaceFilter() {
|
||
System.out.println("--- nomad-0002: stream filter namespace scan ---");
|
||
int[] eventCounts = {1000, 5000, 10000};
|
||
int namespaceCount = 50;
|
||
String[] namespaces = new String[namespaceCount];
|
||
for (int i = 0; i < namespaceCount; i++) namespaces[i] = "ns-" + i;
|
||
|
||
for (int e : eventCounts) {
|
||
String[] events = new String[e];
|
||
for (int i = 0; i < e; i++) events[i] = "ns-" + (i % namespaceCount);
|
||
|
||
long slowOps = slowFilterEvents(events, namespaces);
|
||
long fastOps = fastFilterEvents(events, namespaces);
|
||
|
||
double ratio = (double) slowOps / fastOps;
|
||
boolean pass = ratio > (double) namespaceCount / 3.0;
|
||
total++;
|
||
if (pass) passed++;
|
||
System.out.printf(" events=%-5d namespaces=%d slow=%,10d fast=%,8d ratio=%6.1fx %s%n",
|
||
e, namespaceCount, slowOps, fastOps, ratio, pass ? "PASS" : "FAIL");
|
||
assert pass : "nomad-0002 FAIL: ratio=" + ratio;
|
||
}
|
||
}
|
||
|
||
// -----------------------------------------------------------------------
|
||
// nomad-0003: GetVaultConfigurations secret provider dedup
|
||
// -----------------------------------------------------------------------
|
||
|
||
/**
|
||
* Slow: accumulate providers in a list, slices.Contains check per entry → O(S²).
|
||
*/
|
||
static long slowProviderDedup(String[] providers) {
|
||
long ops = 0;
|
||
List<String> secrets = new ArrayList<>();
|
||
for (String p : providers) {
|
||
ops++;
|
||
boolean found = false;
|
||
for (String existing : secrets) {
|
||
ops++;
|
||
if (existing.equals(p)) { found = true; break; }
|
||
}
|
||
if (!found) secrets.add(p);
|
||
}
|
||
return ops;
|
||
}
|
||
|
||
/**
|
||
* Fast: use HashSet for O(1) contains → O(S).
|
||
*/
|
||
static long fastProviderDedup(String[] providers) {
|
||
long ops = 0;
|
||
Set<String> seen = new HashSet<>();
|
||
for (String p : providers) {
|
||
ops++;
|
||
seen.add(p);
|
||
}
|
||
return ops;
|
||
}
|
||
|
||
static void testVaultSecretsDedup() {
|
||
System.out.println("--- nomad-0003: vault secrets provider dedup ---");
|
||
// Many tasks, few unique providers → worst case for the dedup scan
|
||
int[] sizes = {200, 500, 1000};
|
||
int uniqueProviders = 10;
|
||
|
||
for (int n : sizes) {
|
||
String[] providers = new String[n];
|
||
for (int i = 0; i < n; i++) providers[i] = "provider-" + (i % uniqueProviders);
|
||
|
||
long slowOps = slowProviderDedup(providers);
|
||
long fastOps = fastProviderDedup(providers);
|
||
|
||
double ratio = (double) slowOps / fastOps;
|
||
boolean pass = ratio > 5.0;
|
||
total++;
|
||
if (pass) passed++;
|
||
System.out.printf(" tasks=%-4d unique=%d slow=%,8d fast=%,6d ratio=%6.1fx %s%n",
|
||
n, uniqueProviders, slowOps, fastOps, ratio, pass ? "PASS" : "FAIL");
|
||
assert pass : "nomad-0003 FAIL: ratio=" + ratio;
|
||
}
|
||
}
|
||
|
||
// -----------------------------------------------------------------------
|
||
// nomad-0004: checkstore.Difference — O(current × ids)
|
||
// -----------------------------------------------------------------------
|
||
|
||
/**
|
||
* Slow: for each stored ID, scan the ids[] slice → O(C × I).
|
||
*/
|
||
static long slowDifference(String[] stored, String[] ids) {
|
||
long ops = 0;
|
||
List<String> remove = new ArrayList<>();
|
||
for (String id : stored) {
|
||
ops++;
|
||
boolean found = false;
|
||
for (String x : ids) {
|
||
ops++;
|
||
if (x.equals(id)) { found = true; break; }
|
||
}
|
||
if (!found) remove.add(id);
|
||
}
|
||
return ops;
|
||
}
|
||
|
||
/**
|
||
* Fast: build set from ids, O(1) lookup per stored ID → O(C + I).
|
||
*/
|
||
static long fastDifference(String[] stored, String[] ids) {
|
||
long ops = 0;
|
||
Set<String> idSet = new HashSet<>();
|
||
for (String x : ids) { idSet.add(x); ops++; }
|
||
List<String> remove = new ArrayList<>();
|
||
for (String id : stored) {
|
||
ops++;
|
||
if (!idSet.contains(id)) remove.add(id);
|
||
}
|
||
return ops;
|
||
}
|
||
|
||
static void testChecksStoreDifference() {
|
||
System.out.println("--- nomad-0004: checkstore.Difference ---");
|
||
int[] storedCounts = {100, 500, 1000};
|
||
int idCount = 80;
|
||
|
||
for (int c : storedCounts) {
|
||
String[] stored = new String[c];
|
||
for (int i = 0; i < c; i++) stored[i] = "check-" + i;
|
||
String[] ids = new String[idCount];
|
||
for (int i = 0; i < idCount; i++) ids[i] = "check-" + (i * 3); // sparse overlap
|
||
|
||
long slowOps = slowDifference(stored, ids);
|
||
long fastOps = fastDifference(stored, ids);
|
||
|
||
double ratio = (double) slowOps / fastOps;
|
||
boolean pass = ratio > (double) idCount / 3.0;
|
||
total++;
|
||
if (pass) passed++;
|
||
System.out.printf(" stored=%-4d ids=%d slow=%,8d fast=%,6d ratio=%6.1fx %s%n",
|
||
c, idCount, slowOps, fastOps, ratio, pass ? "PASS" : "FAIL");
|
||
assert pass : "nomad-0004 FAIL: ratio=" + ratio;
|
||
}
|
||
}
|
||
|
||
// -----------------------------------------------------------------------
|
||
|
||
public static void main(String[] args) {
|
||
System.out.println("=== Nomad CWE-407 unit tests ===");
|
||
testBitmapFilter();
|
||
testStreamNamespaceFilter();
|
||
testVaultSecretsDedup();
|
||
testChecksStoreDifference();
|
||
System.out.printf("%n%d/%d PASS%n", passed, total);
|
||
if (passed != total) {
|
||
System.exit(1);
|
||
}
|
||
}
|
||
}
|