russell@unturf.com
176d9f88de
deluge-0001: FilterManager filter_torrent_ids() and filter_state_active() use list.remove(id) inside a loop — O(T^2). Fix: set-based removal / list comprehension. 94x overhead at T=2000. deluge-0002: TorrentManager get_torrent_list() uses list.index()+pop() inside a loop — O(T^2). Fix: list comprehension. 98x overhead at T=2000. Transmission: re-confirmed CLEAN (binary search blocklist, map peer pool, bitfield piece tracking). 2 defects, 4/4 PASS.
99 lines
3.4 KiB
Java
99 lines
3.4 KiB
Java
/**
|
|
* CWE-407 simulation: Deluge TorrentManager list.index()+pop() inside loop.
|
|
*
|
|
* Simulates get_torrent_list() with the defective O(T^2) list.index()+pop()
|
|
* pattern vs the fixed O(T) list comprehension approach.
|
|
*
|
|
* deluge-0002: torrentmanager list.index()+pop() in loop
|
|
*/
|
|
import java.util.*;
|
|
|
|
public class DelugeTorrentManagerTest {
|
|
|
|
/** DEFECTIVE: list.index()+pop() inside loop — O(T^2) */
|
|
static List<String> getTorrentListDefective(List<String> allIds, Set<String> ownedIds) {
|
|
List<String> ids = new ArrayList<>(allIds);
|
|
for (String tid : new ArrayList<>(ids)) {
|
|
if (!ownedIds.contains(tid)) {
|
|
int idx = ids.indexOf(tid); // O(N) scan
|
|
if (idx >= 0) {
|
|
ids.remove(idx); // O(N) shift
|
|
}
|
|
}
|
|
}
|
|
return ids;
|
|
}
|
|
|
|
/** FIXED: list comprehension — O(T) */
|
|
static List<String> getTorrentListFixed(List<String> allIds, Set<String> ownedIds) {
|
|
List<String> result = new ArrayList<>();
|
|
for (String tid : allIds) {
|
|
if (ownedIds.contains(tid)) {
|
|
result.add(tid);
|
|
}
|
|
}
|
|
return result;
|
|
}
|
|
|
|
public static void main(String[] args) {
|
|
int[] sizes = {100, 500, 1000, 2000};
|
|
System.out.println("=== Deluge TorrentManager CWE-407 Test (deluge-0002) ===");
|
|
System.out.printf("%-8s %12s %12s %8s %s%n",
|
|
"T", "Defective(ms)", "Fixed(ms)", "Ratio", "Status");
|
|
|
|
boolean allPass = true;
|
|
for (int T : sizes) {
|
|
// Setup: T torrents, 30% owned by current user
|
|
List<String> allIds = new ArrayList<>();
|
|
Set<String> ownedIds = new HashSet<>();
|
|
for (int i = 0; i < T; i++) {
|
|
String id = "torrent-" + i;
|
|
allIds.add(id);
|
|
if (i % 3 == 0) {
|
|
ownedIds.add(id);
|
|
}
|
|
}
|
|
|
|
// Warmup
|
|
for (int w = 0; w < 3; w++) {
|
|
getTorrentListDefective(allIds, ownedIds);
|
|
getTorrentListFixed(allIds, ownedIds);
|
|
}
|
|
|
|
// Benchmark defective
|
|
int iters = Math.max(10, 50000 / T);
|
|
long t0 = System.nanoTime();
|
|
for (int i = 0; i < iters; i++) {
|
|
getTorrentListDefective(allIds, ownedIds);
|
|
}
|
|
long defectiveNs = System.nanoTime() - t0;
|
|
|
|
// Benchmark fixed
|
|
t0 = System.nanoTime();
|
|
for (int i = 0; i < iters; i++) {
|
|
getTorrentListFixed(allIds, ownedIds);
|
|
}
|
|
long fixedNs = System.nanoTime() - t0;
|
|
|
|
double ratio = (double) defectiveNs / fixedNs;
|
|
boolean pass = ratio > 2.0;
|
|
allPass &= pass;
|
|
|
|
// Correctness check
|
|
List<String> dResult = getTorrentListDefective(allIds, ownedIds);
|
|
List<String> fResult = getTorrentListFixed(allIds, ownedIds);
|
|
boolean correct = dResult.equals(fResult);
|
|
allPass &= correct;
|
|
|
|
System.out.printf("%-8d %12.2f %12.2f %8.1fx %s%s%n",
|
|
T,
|
|
defectiveNs / 1e6 / iters,
|
|
fixedNs / 1e6 / iters,
|
|
ratio,
|
|
pass ? "PASS" : "FAIL",
|
|
correct ? "" : " MISMATCH");
|
|
}
|
|
System.out.println("\nOverall: " + (allPass ? "PASS" : "FAIL"));
|
|
System.exit(allPass ? 0 : 1);
|
|
}
|
|
}
|