320 lines
12 KiB
Java
320 lines
12 KiB
Java
package unit;
|
||
|
||
import java.util.*;
|
||
|
||
/**
|
||
* Unit test for nestjs-0001/0002: CWE-407 in NestJS DI scanner.
|
||
*
|
||
* nestjs-0001 (HIGH):
|
||
* File: packages/core/scanner.ts:155
|
||
* Symbol: DependenciesScanner.scanForModules — ctxRegistry.includes(innerModule)
|
||
* Defect: The module-scan visited-set is a plain Array passed by reference
|
||
* through all recursive scanForModules() calls. At each module in the import
|
||
* list, Array.includes() performs an O(n) scan of the ever-growing registry.
|
||
* For N modules total: sum 0+1+...+(N-1) = N*(N-1)/2 comparisons = O(N²).
|
||
* Fix: Replace ctxRegistry: Array with ctxRegistry: Set; use Set.add()
|
||
* and Set.has() — both O(1). Cold-start speedup is ~N/2 at large N.
|
||
*
|
||
* nestjs-0002 (MEDIUM):
|
||
* File: packages/common/module-utils/utils/get-injection-providers.util.ts:41-42
|
||
* Symbol: getInjectionProviders — result.includes(p), search.includes(p)
|
||
* Defect: Provider dependency resolution loop uses Array.includes() against
|
||
* both a growing result accumulator and a search list on every filter call.
|
||
* With P providers, R result items, S search items, W iterations:
|
||
* O(P × W × (R + 2S)) comparisons per getInjectionProviders() call.
|
||
* Fix: Maintain resultSet: Set<Provider> and searchSet: Set<InjectionToken>
|
||
* as companions; replace .includes() with .has() — O(1) per check.
|
||
*
|
||
* Modeled here in Java:
|
||
* JS Array + .includes() ≡ List<T> + contains() (defective)
|
||
* JS Set + .has() ≡ java.util.Set + contains() (fixed)
|
||
* comparisons tracked at each membership-test site.
|
||
*
|
||
* Expected at N=300 (nestjs-0001): ratio > 50x
|
||
* Expected at nestjs-0002 scale: ratio > 10x
|
||
*/
|
||
public class NestJSTest {
|
||
|
||
static void bench(String label, Runnable slow, Runnable fast, long sOps, long fOps) {
|
||
slow.run(); fast.run();
|
||
long t0 = System.nanoTime(); slow.run(); long sMs = (System.nanoTime()-t0)/1_000_000;
|
||
long t1 = System.nanoTime(); fast.run(); long fMs = (System.nanoTime()-t1)/1_000_000;
|
||
double r = fOps > 0 ? (double)sOps/fOps : 0;
|
||
System.out.printf(" %-52s slow:%4dms (%,d ops) fast:%4dms (%,d ops) speedup:%.0fx%n",
|
||
label, sMs, sOps, fMs, fOps, r);
|
||
}
|
||
|
||
// =========================================================================
|
||
// nestjs-0001 model: ctxRegistry as Array vs Set in recursive module scan
|
||
// =========================================================================
|
||
|
||
/**
|
||
* Defective scanForModules: ctxRegistry is a plain List.
|
||
* Simulates visiting N modules in a linear chain: each module imports the
|
||
* next. The registry grows by 1 per visit; at visit k the .contains() scan
|
||
* examines k elements. Total comparisons = 0+1+...+(N-1) = N*(N-1)/2.
|
||
*/
|
||
static class DefectiveScanner {
|
||
long comparisons = 0;
|
||
|
||
void scan(int moduleId, List<Object> ctxRegistry, int totalModules) {
|
||
Object module = moduleId;
|
||
ctxRegistry.add(module);
|
||
|
||
// Simulate one import per module (linear chain)
|
||
if (moduleId + 1 < totalModules) {
|
||
Object nextModule = moduleId + 1;
|
||
// ctxRegistry.includes(nextModule) — O(n) scan
|
||
boolean found = false;
|
||
for (Object m : ctxRegistry) {
|
||
comparisons++;
|
||
if (m.equals(nextModule)) { found = true; break; }
|
||
}
|
||
if (!found) {
|
||
scan(moduleId + 1, ctxRegistry, totalModules);
|
||
}
|
||
}
|
||
}
|
||
|
||
void run(int N) {
|
||
List<Object> ctxRegistry = new ArrayList<>();
|
||
scan(0, ctxRegistry, N);
|
||
}
|
||
}
|
||
|
||
/**
|
||
* Fixed scanForModules: ctxRegistry is a Set.
|
||
* Set.contains() is O(1) average. Total comparisons = N-1 (one per module
|
||
* after the root, since the root is never checked against itself).
|
||
*/
|
||
static class FixedScanner {
|
||
long comparisons = 0;
|
||
|
||
void scan(int moduleId, Set<Object> ctxRegistry, int totalModules) {
|
||
Object module = moduleId;
|
||
ctxRegistry.add(module);
|
||
|
||
if (moduleId + 1 < totalModules) {
|
||
Object nextModule = moduleId + 1;
|
||
// ctxRegistry.has(nextModule) — O(1)
|
||
comparisons++;
|
||
if (!ctxRegistry.contains(nextModule)) {
|
||
scan(moduleId + 1, ctxRegistry, totalModules);
|
||
}
|
||
}
|
||
}
|
||
|
||
void run(int N) {
|
||
Set<Object> ctxRegistry = new HashSet<>();
|
||
scan(0, ctxRegistry, N);
|
||
}
|
||
}
|
||
|
||
// =========================================================================
|
||
// nestjs-0002 model: getInjectionProviders Array.includes vs Set.has
|
||
// =========================================================================
|
||
|
||
/**
|
||
* Defective getInjectionProviders: result and search are plain Lists.
|
||
*
|
||
* The key defect: for each of P providers per iteration, the code does
|
||
* result.includes(p) — an O(result.size) scan — and search.includes(p) —
|
||
* an O(search.size) scan. As result accumulates providers over W iterations
|
||
* the result.includes cost dominates.
|
||
*
|
||
* Worst-case model: search is size S each round, all providers match on the
|
||
* first iteration and go into result; subsequent iterations re-scan result
|
||
* for all P providers (finding them all already there, full scans each time).
|
||
*/
|
||
static long getInjectionProvidersDefective(int P, int W) {
|
||
long comparisons = 0;
|
||
List<Integer> result = new ArrayList<>();
|
||
// seed result with half of P to simulate partially-filled accumulator
|
||
int preload = P / 2;
|
||
for (int i = 0; i < preload; i++) result.add(i);
|
||
|
||
// Each of W iterations: filter all P providers against result (O(result.size))
|
||
int S = 5; // fixed search size
|
||
List<Integer> search = new ArrayList<>();
|
||
for (int i = preload; i < preload + S && i < P; i++) search.add(i);
|
||
|
||
for (int iter = 0; iter < W && !search.isEmpty(); iter++) {
|
||
List<Integer> match = new ArrayList<>();
|
||
for (int p = 0; p < P; p++) {
|
||
// result.includes(p) — O(result.size)
|
||
boolean inResult = false;
|
||
for (int r : result) {
|
||
comparisons++;
|
||
if (r == p) { inResult = true; break; }
|
||
}
|
||
if (inResult) continue;
|
||
|
||
// search.includes(p) — O(search.size)
|
||
boolean inSearch = false;
|
||
for (int s : search) {
|
||
comparisons++;
|
||
if (s == p) { inSearch = true; break; }
|
||
}
|
||
if (inSearch) match.add(p);
|
||
}
|
||
result.addAll(match);
|
||
|
||
// Advance search window (new deps)
|
||
int base = preload + S + iter * S;
|
||
search = new ArrayList<>();
|
||
for (int i = base; i < base + S && i < P; i++) search.add(i);
|
||
}
|
||
return comparisons;
|
||
}
|
||
|
||
/**
|
||
* Fixed getInjectionProviders: result and search backed by Sets.
|
||
* All membership checks are O(1).
|
||
*/
|
||
static long getInjectionProvidersFixed(int P, int W) {
|
||
long comparisons = 0;
|
||
List<Integer> result = new ArrayList<>();
|
||
Set<Integer> resultSet = new HashSet<>();
|
||
int preload = P / 2;
|
||
for (int i = 0; i < preload; i++) { result.add(i); resultSet.add(i); }
|
||
|
||
int S = 5;
|
||
Set<Integer> searchSet = new HashSet<>();
|
||
for (int i = preload; i < preload + S && i < P; i++) searchSet.add(i);
|
||
|
||
for (int iter = 0; iter < W && !searchSet.isEmpty(); iter++) {
|
||
List<Integer> match = new ArrayList<>();
|
||
for (int p = 0; p < P; p++) {
|
||
comparisons++; // resultSet.has(p) — O(1)
|
||
if (resultSet.contains(p)) continue;
|
||
comparisons++; // searchSet.has(p) — O(1)
|
||
if (searchSet.contains(p)) match.add(p);
|
||
}
|
||
for (int m : match) { result.add(m); resultSet.add(m); }
|
||
|
||
int base = preload + S + iter * S;
|
||
searchSet = new HashSet<>();
|
||
for (int i = base; i < base + S && i < P; i++) searchSet.add(i);
|
||
}
|
||
return comparisons;
|
||
}
|
||
|
||
// =========================================================================
|
||
// Tests
|
||
// =========================================================================
|
||
|
||
/**
|
||
* Test 1 — Correctness: defective and fixed scanners visit the same modules.
|
||
*/
|
||
static void testScannerCorrectnessMatch() {
|
||
int N = 50;
|
||
DefectiveScanner def = new DefectiveScanner();
|
||
FixedScanner fix = new FixedScanner();
|
||
|
||
// Both should visit all N modules (linear chain means all are reachable)
|
||
def.run(N);
|
||
fix.run(N);
|
||
|
||
// After visiting N modules comparisons follow:
|
||
// Defective: when visiting module k (0-indexed), registry has size k,
|
||
// so .contains() on the next module scans k elements.
|
||
// Total = 1+2+...+(N-1) = N*(N-1)/2
|
||
// Fixed: each visit does exactly 1 Set.contains() for the child check.
|
||
// Total = N-1 (root has one child check; leaf module has no child)
|
||
long expectedDef = (long) N * (N - 1) / 2;
|
||
assert def.comparisons == expectedDef
|
||
: "defective scanner comparisons should be N*(N-1)/2=" + expectedDef
|
||
+ "; got " + def.comparisons;
|
||
assert fix.comparisons == N - 1
|
||
: "fixed scanner comparisons should be N-1=" + (N - 1)
|
||
+ "; got " + fix.comparisons;
|
||
|
||
System.out.println("PASS testScannerCorrectnessMatch");
|
||
}
|
||
|
||
/**
|
||
* Test 2 — nestjs-0001: ratio of defective vs fixed scanner comparisons > 50x at N=300.
|
||
*
|
||
* Defective: (N-1)*(N-2)/2 comparisons ~ O(N²)
|
||
* Fixed: N-1 comparisons ~ O(N)
|
||
* Ratio at N=300: ~149x
|
||
*/
|
||
static void testScannerRatioAtScale() {
|
||
int N = 300;
|
||
DefectiveScanner def = new DefectiveScanner();
|
||
FixedScanner fix = new FixedScanner();
|
||
def.run(N);
|
||
fix.run(N);
|
||
|
||
long defComp = def.comparisons;
|
||
long fixComp = fix.comparisons;
|
||
double ratio = (double) defComp / fixComp;
|
||
|
||
long expectedDef = (long) N * (N - 1) / 2;
|
||
assert defComp == expectedDef
|
||
: "defective scanner: expected N*(N-1)/2=" + expectedDef
|
||
+ "; got " + defComp;
|
||
assert fixComp == N - 1
|
||
: "fixed scanner: expected N-1=" + (N - 1) + "; got " + fixComp;
|
||
assert ratio > 50.0
|
||
: "ratio should be >50x at N=300; got " + ratio;
|
||
|
||
System.out.printf(
|
||
"PASS testScannerRatioAtScale (defective=%d, fixed=%d, ratio=%.0fx)%n",
|
||
defComp, fixComp, ratio);
|
||
}
|
||
|
||
/**
|
||
* Test 3 — nestjs-0002: getInjectionProviders defective is O(P*W*(R+S)), fixed is O(P*W).
|
||
*
|
||
* P=50 providers, W=10 iterations: ratio > 10x expected.
|
||
*/
|
||
static void testGetInjectionProvidersRatio() {
|
||
int P = 50;
|
||
int W = 10;
|
||
|
||
long defComp = getInjectionProvidersDefective(P, W);
|
||
long fixComp = getInjectionProvidersFixed(P, W);
|
||
double ratio = (double) defComp / fixComp;
|
||
|
||
assert defComp > fixComp
|
||
: "defective should have more comparisons than fixed; def="
|
||
+ defComp + " fix=" + fixComp;
|
||
assert ratio > 3.0
|
||
: "ratio should be >3x at P=50, W=10; got " + ratio;
|
||
|
||
System.out.printf(
|
||
"PASS testGetInjectionProvidersRatio (defective=%d, fixed=%d, ratio=%.1fx)%n",
|
||
defComp, fixComp, ratio);
|
||
}
|
||
|
||
/**
|
||
* Test 4 — nestjs-0002 at larger scale: P=200 providers, W=15 iterations.
|
||
* Ratio should be > 10x.
|
||
*/
|
||
static void testGetInjectionProvidersRatioLargeScale() {
|
||
int P = 200;
|
||
int W = 15;
|
||
|
||
long defComp = getInjectionProvidersDefective(P, W);
|
||
long fixComp = getInjectionProvidersFixed(P, W);
|
||
double ratio = (double) defComp / fixComp;
|
||
|
||
assert ratio > 10.0
|
||
: "ratio should be >10x at P=200, W=15; got " + ratio;
|
||
|
||
System.out.printf(
|
||
"PASS testGetInjectionProvidersRatioLargeScale (defective=%d, fixed=%d, ratio=%.1fx)%n",
|
||
defComp, fixComp, ratio);
|
||
}
|
||
|
||
// =========================================================================
|
||
|
||
public static void main(String[] args) {
|
||
testScannerCorrectnessMatch();
|
||
testScannerRatioAtScale();
|
||
testGetInjectionProvidersRatio();
|
||
testGetInjectionProvidersRatioLargeScale();
|
||
System.out.println("All NestJS tests passed.");
|
||
}
|
||
}
|