96 lines
3.4 KiB
Java
96 lines
3.4 KiB
Java
/**
|
||
* CWE-407 simulation: VLC randomizer_Remove O(N×C) linear scan.
|
||
*
|
||
* Simulates the defect in src/playlist/randomizer.c where
|
||
* randomizer_Remove() calls randomizer_RemoveOne() for each item,
|
||
* which calls randomizer_IndexOf() → vlc_vector_index_of() — a
|
||
* linear scan of the vector. Total: O(N×C), where N = playlist size
|
||
* and C = items to remove. When C ≈ N this is O(N²).
|
||
*
|
||
* Fix: use a HashSet for O(1) lookup → O(N+C) total.
|
||
*/
|
||
import java.util.*;
|
||
|
||
public class VlcTest {
|
||
|
||
/* --- Defective path: linear scan per removal --- */
|
||
static long removeDefective(ArrayList<Object> playlist, Object[] toRemove) {
|
||
long ops = 0;
|
||
for (Object item : toRemove) {
|
||
// randomizer_IndexOf → vlc_vector_index_of: linear scan
|
||
int idx = -1;
|
||
for (int i = 0; i < playlist.size(); i++) {
|
||
ops++;
|
||
if (playlist.get(i) == item) {
|
||
idx = i;
|
||
break;
|
||
}
|
||
}
|
||
if (idx >= 0) {
|
||
playlist.remove(idx);
|
||
}
|
||
}
|
||
return ops;
|
||
}
|
||
|
||
/* --- Fixed path: hash set for O(1) membership, single pass --- */
|
||
static long removeFixed(ArrayList<Object> playlist, Object[] toRemove) {
|
||
long ops = 0;
|
||
Set<Object> removeSet = new HashSet<>();
|
||
for (Object item : toRemove) {
|
||
removeSet.add(item);
|
||
ops++; // building the set
|
||
}
|
||
Iterator<Object> it = playlist.iterator();
|
||
while (it.hasNext()) {
|
||
ops++;
|
||
if (removeSet.contains(it.next())) {
|
||
it.remove();
|
||
}
|
||
}
|
||
return ops;
|
||
}
|
||
|
||
public static void main(String[] args) {
|
||
int[] sizes = {100, 500, 1000};
|
||
boolean allPass = true;
|
||
|
||
System.out.println("=== VLC randomizer_Remove CWE-407 Test ===");
|
||
System.out.printf("%-8s %-12s %-12s %-8s %-6s%n",
|
||
"N", "Defective", "Fixed", "Ratio", "Pass");
|
||
|
||
for (int N : sizes) {
|
||
// Build playlist of N items, remove N/2 items scattered randomly
|
||
Object[] items = new Object[N];
|
||
for (int i = 0; i < N; i++) items[i] = new Object();
|
||
|
||
// Remove the last N/2 items (worst case: they are at end of list)
|
||
int removeCount = N / 2;
|
||
Object[] toRemove = new Object[removeCount];
|
||
// Remove items from the second half — they sit at the end,
|
||
// so each indexOf scan traverses ~N items
|
||
System.arraycopy(items, N - removeCount, toRemove, 0, removeCount);
|
||
|
||
ArrayList<Object> playlist1 = new ArrayList<>(Arrays.asList(items));
|
||
ArrayList<Object> playlist2 = new ArrayList<>(Arrays.asList(items));
|
||
|
||
long opsDefective = removeDefective(playlist1, toRemove);
|
||
long opsFixed = removeFixed(playlist2, toRemove);
|
||
|
||
double ratio = (double) opsDefective / opsFixed;
|
||
boolean pass = ratio > 2.0;
|
||
if (!pass) allPass = false;
|
||
|
||
System.out.printf("%-8d %-12d %-12d %-8.1fx %-6s%n",
|
||
N, opsDefective, opsFixed, ratio, pass ? "PASS" : "FAIL");
|
||
}
|
||
|
||
System.out.println();
|
||
if (allPass) {
|
||
System.out.println("ALL PASS — defective path is quadratic, fixed path is linear");
|
||
} else {
|
||
System.out.println("FAIL — ratio not demonstrated");
|
||
System.exit(1);
|
||
}
|
||
}
|
||
}
|