110 lines
4.1 KiB
Java
110 lines
4.1 KiB
Java
/**
|
|
* CWE-407 unit test for OpenFOAM moleculeCloud.C molsToDelete dedup defect.
|
|
*
|
|
* Defect: moleculeCloud::removeHighEnergyOverlaps() uses
|
|
* DynamicList<molecule*> molsToDelete with findIndex() O(N) membership
|
|
* check inside a nested molecule-pair loop, yielding O(pairs * D)
|
|
* complexity where D = number of deletions.
|
|
*
|
|
* Fix: Replace DynamicList + findIndex with HashSet for O(1) membership.
|
|
*
|
|
* This test models the defect pattern in Java:
|
|
* - Defective: ArrayList + contains() for dedup in nested loop
|
|
* - Fixed: HashSet for O(1) dedup
|
|
*/
|
|
import java.util.*;
|
|
|
|
public class OpenFOAMMolsToDeleteDedupTest {
|
|
|
|
/** Simulate molecule with an id and origId */
|
|
static class Molecule {
|
|
final int id;
|
|
final int origId;
|
|
Molecule(int id, int origId) { this.id = id; this.origId = origId; }
|
|
@Override public int hashCode() { return origId; }
|
|
@Override public boolean equals(Object o) {
|
|
return o instanceof Molecule && ((Molecule) o).origId == this.origId;
|
|
}
|
|
}
|
|
|
|
/** Defective: ArrayList + contains() O(N) per check => O(pairs * D) */
|
|
static int defective(List<Molecule> cellI, List<Molecule> cellJ,
|
|
List<Integer> removalOrder) {
|
|
List<Molecule> molsToDelete = new ArrayList<>();
|
|
long ops = 0;
|
|
for (Molecule molI : cellI) {
|
|
for (Molecule molJ : cellJ) {
|
|
ops++;
|
|
int idxI = removalOrder.indexOf(molI.id);
|
|
int idxJ = removalOrder.indexOf(molJ.id);
|
|
if (molI.id == molJ.id || idxJ < idxI) {
|
|
// findIndex(molsToDelete, molJ) == -1
|
|
ops += molsToDelete.size();
|
|
if (!molsToDelete.contains(molJ)) {
|
|
molsToDelete.add(molJ);
|
|
}
|
|
} else {
|
|
ops += molsToDelete.size();
|
|
if (!molsToDelete.contains(molI)) {
|
|
molsToDelete.add(molI);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
return (int) ops;
|
|
}
|
|
|
|
/** Fixed: HashSet for O(1) membership => O(pairs) */
|
|
static int fixed(List<Molecule> cellI, List<Molecule> cellJ,
|
|
List<Integer> removalOrder) {
|
|
Set<Molecule> molsToDeleteSet = new HashSet<>();
|
|
long ops = 0;
|
|
for (Molecule molI : cellI) {
|
|
for (Molecule molJ : cellJ) {
|
|
ops++;
|
|
int idxI = removalOrder.indexOf(molI.id);
|
|
int idxJ = removalOrder.indexOf(molJ.id);
|
|
if (molI.id == molJ.id || idxJ < idxI) {
|
|
ops++; // O(1) HashSet lookup
|
|
molsToDeleteSet.add(molJ);
|
|
} else {
|
|
ops++;
|
|
molsToDeleteSet.add(molI);
|
|
}
|
|
}
|
|
}
|
|
return (int) ops;
|
|
}
|
|
|
|
public static void main(String[] args) {
|
|
// Simulate: 500 molecules in each cell, 3 molecule types
|
|
int N = 500;
|
|
List<Integer> removalOrder = Arrays.asList(0, 1, 2);
|
|
Random rng = new Random(42);
|
|
|
|
List<Molecule> cellI = new ArrayList<>();
|
|
List<Molecule> cellJ = new ArrayList<>();
|
|
for (int i = 0; i < N; i++) {
|
|
cellI.add(new Molecule(rng.nextInt(3), i));
|
|
cellJ.add(new Molecule(rng.nextInt(3), N + i));
|
|
}
|
|
|
|
int defOps = defective(cellI, cellJ, removalOrder);
|
|
int fixOps = fixed(cellI, cellJ, removalOrder);
|
|
|
|
double ratio = (double) defOps / fixOps;
|
|
|
|
System.out.println("=== OpenFOAM moleculeCloud molsToDelete Dedup Test ===");
|
|
System.out.println("Molecules per cell: " + N);
|
|
System.out.println("Defective ops: " + defOps);
|
|
System.out.println("Fixed ops: " + fixOps);
|
|
System.out.printf("Ratio (defective/fixed): %.1fx%n", ratio);
|
|
|
|
// Verify: defective should be significantly more expensive
|
|
boolean pass = ratio >= 5.0;
|
|
System.out.println("RESULT: " + (pass ? "PASS" : "FAIL")
|
|
+ " (ratio >= 5.0 required)");
|
|
|
|
if (!pass) System.exit(1);
|
|
}
|
|
}
|