113 lines
4.6 KiB
Java
113 lines
4.6 KiB
Java
package unit;
|
||
|
||
import java.util.ArrayList;
|
||
import java.util.Arrays;
|
||
import java.util.LinkedHashSet;
|
||
import java.util.List;
|
||
import java.util.Set;
|
||
|
||
/**
|
||
* CWE-407 unit test: elasticsearch-003
|
||
* XContentHelper.merge() uses ArrayList.contains() inside a for loop for list dedup.
|
||
*
|
||
* Defect: O(n²) — ArrayList.contains() called once per element of baseList
|
||
* Fix: O(n) — HashSet/LinkedHashSet membership check is O(1)
|
||
*
|
||
* No JUnit. Run with: javac XContentHelperMergeContains.java && java -cp . unit.XContentHelperMergeContains
|
||
*/
|
||
public class XContentHelperMergeContains {
|
||
|
||
// ---- SLOW: mirrors the defective XContentHelper logic exactly ----
|
||
static List<Object> mergeListSlow(List<Object> listToMerge, List<Object> baseList) {
|
||
List<Object> mergedList = new ArrayList<>(listToMerge);
|
||
for (Object o : baseList) {
|
||
if (mergedList.contains(o) == false) { // O(mergedList.size()) per iteration
|
||
mergedList.add(o);
|
||
}
|
||
}
|
||
return mergedList;
|
||
}
|
||
|
||
// ---- FAST: LinkedHashSet preserves insertion order, O(1) contains ----
|
||
static List<Object> mergeListFast(List<Object> listToMerge, List<Object> baseList) {
|
||
LinkedHashSet<Object> merged = new LinkedHashSet<>(listToMerge);
|
||
merged.addAll(baseList); // addAll deduplicates via HashSet — O(1) per element
|
||
return new ArrayList<>(merged);
|
||
}
|
||
|
||
// ---- count how many .contains() probes the slow path does ----
|
||
static long countSlowProbes(int listToMergeSize, int baseListSize) {
|
||
// After listToMerge is loaded into mergedList, for each element of baseList we scan
|
||
// mergedList linearly. In the worst case (no duplicates) mergedList grows by 1 each time.
|
||
long probes = 0;
|
||
int size = listToMergeSize;
|
||
for (int i = 0; i < baseListSize; i++) {
|
||
probes += size; // contains() scans 'size' elements
|
||
size++; // element added (no duplicate)
|
||
}
|
||
return probes;
|
||
}
|
||
|
||
// ---- expected fast probes: O(1) each, total = baseListSize ----
|
||
static long countFastProbes(int baseListSize) {
|
||
return baseListSize; // each HashSet.contains is O(1)
|
||
}
|
||
|
||
public static void main(String[] args) {
|
||
System.out.println("=== elasticsearch-003: XContentHelper.merge List dedup CWE-407 ===\n");
|
||
|
||
// --- Correctness check ---
|
||
List<Object> base = new ArrayList<>(Arrays.asList("a", "b", "c", "d"));
|
||
List<Object> extra = new ArrayList<>(Arrays.asList("c", "d", "e", "f"));
|
||
|
||
List<Object> slow = mergeListSlow(extra, base);
|
||
List<Object> fast = mergeListFast(extra, base);
|
||
|
||
// Both should have the same elements (order: extra first, then new from base)
|
||
if (!slow.equals(fast)) {
|
||
System.out.println("FAIL correctness: slow=" + slow + " fast=" + fast);
|
||
System.exit(1);
|
||
}
|
||
System.out.println("correctness OK merged=" + slow);
|
||
|
||
// --- No duplicate check ---
|
||
Set<Object> seen = new LinkedHashSet<>(slow);
|
||
if (seen.size() != slow.size()) {
|
||
System.out.println("FAIL: merged list contains duplicates: " + slow);
|
||
System.exit(1);
|
||
}
|
||
System.out.println("no-duplicates OK");
|
||
|
||
// --- Op-count comparison at scale ---
|
||
System.out.println("\n=== Op-count: worst case (no duplicates) ===");
|
||
System.out.printf("%-8s %-14s %-12s %-10s%n", "n", "slow_probes", "fast_probes", "ratio");
|
||
System.out.println("-".repeat(52));
|
||
|
||
int[] sizes = {10, 50, 100, 500, 1000};
|
||
for (int n : sizes) {
|
||
long slowOps = countSlowProbes(n, n); // merge two equal-length lists
|
||
long fastOps = countFastProbes(n);
|
||
double ratio = (double) slowOps / fastOps;
|
||
System.out.printf("%-8d %-14d %-12d %-10.1f%n", n, slowOps, fastOps, ratio);
|
||
|
||
// verify slow is worse than fast
|
||
if (slowOps <= fastOps && n > 1) {
|
||
System.out.println("FAIL: slow was not worse than fast at n=" + n);
|
||
System.exit(1);
|
||
}
|
||
}
|
||
|
||
// --- Verify at n=100: slow should be ≥ 50× worse ----
|
||
int n = 100;
|
||
long slowOps = countSlowProbes(n, n);
|
||
long fastOps = countFastProbes(n);
|
||
double ratio = (double) slowOps / fastOps;
|
||
if (ratio < 50.0) {
|
||
System.out.printf("FAIL: expected ratio >= 50x at n=100, got %.1fx%n", ratio);
|
||
System.exit(1);
|
||
}
|
||
System.out.printf("%nspeedup at n=100: %.1fx PASS%n", ratio);
|
||
|
||
System.out.println("\nALL PASS");
|
||
}
|
||
}
|