285 lines
13 KiB
Java
285 lines
13 KiB
Java
package unit;
|
|
import java.util.*;
|
|
|
|
/**
|
|
* CWE-407 benchmark for jitsi-videobridge defects:
|
|
* jitsi-videobridge-0001: Prioritize.kt List.contains() + List.indexOf() O(n²)
|
|
* jitsi-videobridge-0002: BandwidthAllocator.kt selectedSources getter List.contains() O(n²)
|
|
* jitsi-videobridge-0003: ConferenceSpeechActivity.java ArrayList.contains() in endpointsChanged O(n²)
|
|
*/
|
|
public class JitsiVideobridgeTest {
|
|
|
|
static void bench(String label, Runnable slow, Runnable fast, long sOps, long fOps) {
|
|
// warm up
|
|
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(" %-60s slow:%4dms (%,d ops) fast:%4dms (%,d ops) speedup:%.0fx%n",
|
|
label, sMs, sOps, fMs, fOps, r);
|
|
}
|
|
|
|
// ─────────────────────────────────────────────────────────────────────────
|
|
// jitsi-videobridge-0001: Prioritize.kt contains() + indexOf()
|
|
// ─────────────────────────────────────────────────────────────────────────
|
|
|
|
/** Slow: List.contains() inside forEach (O(n²)) */
|
|
static long slowPrioritizeContains(List<String> sources, List<String> selectedNames) {
|
|
long ops = 0;
|
|
List<String> selected = new ArrayList<>();
|
|
List<String> notSelected = new ArrayList<>();
|
|
for (String source : sources) {
|
|
ops++;
|
|
for (String s : selectedNames) { // O(n) scan
|
|
ops++;
|
|
if (s.equals(source)) {
|
|
selected.add(source);
|
|
break;
|
|
}
|
|
}
|
|
if (!selectedNames.contains(source)) {
|
|
notSelected.add(source);
|
|
}
|
|
}
|
|
return ops;
|
|
}
|
|
|
|
/** Slow: List.indexOf() in sort comparator (called O(n log n) times, each O(n)) */
|
|
static long slowPrioritizeIndexOf(List<String> sources, List<String> selectedNames) {
|
|
long ops = 0;
|
|
List<String> copy = new ArrayList<>(sources);
|
|
// simulate sortBy { selectedNames.indexOf(it) } — O(n log n) comparisons, each O(n)
|
|
copy.sort((a, b) -> {
|
|
// Each indexOf is O(|selectedNames|)
|
|
int ia = selectedNames.indexOf(a); // O(n)
|
|
int ib = selectedNames.indexOf(b); // O(n)
|
|
return Integer.compare(ia == -1 ? Integer.MAX_VALUE : ia,
|
|
ib == -1 ? Integer.MAX_VALUE : ib);
|
|
});
|
|
// count operations: O(n log n * n) comparisons total — approximate by n² for timing
|
|
ops = (long) sources.size() * selectedNames.size();
|
|
return ops;
|
|
}
|
|
|
|
/** Fast: HashSet.contains() + pre-built index map (O(n)) */
|
|
static long fastPrioritize(List<String> sources, List<String> selectedNames) {
|
|
long ops = 0;
|
|
Set<String> selectedSet = new HashSet<>(selectedNames);
|
|
Map<String, Integer> selectedIndex = new HashMap<>();
|
|
for (int i = 0; i < selectedNames.size(); i++) {
|
|
selectedIndex.put(selectedNames.get(i), i);
|
|
ops++;
|
|
}
|
|
List<String> selected = new ArrayList<>();
|
|
List<String> notSelected = new ArrayList<>();
|
|
for (String source : sources) {
|
|
ops++;
|
|
if (selectedSet.contains(source)) {
|
|
selected.add(source);
|
|
} else {
|
|
notSelected.add(source);
|
|
}
|
|
}
|
|
selected.sort(Comparator.comparingInt(s -> selectedIndex.getOrDefault(s, Integer.MAX_VALUE)));
|
|
ops += selected.size();
|
|
return ops;
|
|
}
|
|
|
|
// ─────────────────────────────────────────────────────────────────────────
|
|
// jitsi-videobridge-0002: BandwidthAllocator selectedSources getter
|
|
// ─────────────────────────────────────────────────────────────────────────
|
|
|
|
/** Slow: MutableList.contains() per element — O(n²) dedup */
|
|
static long slowSelectedSourcesGetter(List<String> onStage, List<String> selected) {
|
|
long ops = 0;
|
|
List<String> merged = new ArrayList<>(onStage);
|
|
for (String s : selected) {
|
|
ops++;
|
|
boolean found = false;
|
|
for (String m : merged) { // O(n) scan
|
|
ops++;
|
|
if (m.equals(s)) { found = true; break; }
|
|
}
|
|
if (!found) merged.add(s);
|
|
}
|
|
return ops;
|
|
}
|
|
|
|
/** Fast: LinkedHashSet — O(n) dedup preserving order */
|
|
static long fastSelectedSourcesGetter(List<String> onStage, List<String> selected) {
|
|
long ops = 0;
|
|
LinkedHashSet<String> merged = new LinkedHashSet<>(onStage);
|
|
ops += onStage.size();
|
|
for (String s : selected) {
|
|
merged.add(s); // O(1)
|
|
ops++;
|
|
}
|
|
return ops;
|
|
}
|
|
|
|
// ─────────────────────────────────────────────────────────────────────────
|
|
// jitsi-videobridge-0003: ConferenceSpeechActivity endpointsChanged
|
|
// ─────────────────────────────────────────────────────────────────────────
|
|
|
|
/** Slow: ArrayList.contains() inside for-each loop — O(n²) */
|
|
static long slowEndpointsChanged(List<String> activityList, List<String> conferenceEndpoints) {
|
|
long ops = 0;
|
|
List<String> byActivity = new ArrayList<>(activityList);
|
|
// removeIf with contains on conferenceEndpoints (ArrayList) — O(n) per element
|
|
byActivity.removeIf(ep -> {
|
|
boolean found = false;
|
|
for (String c : conferenceEndpoints) { // O(n) scan
|
|
if (c.equals(ep)) { found = true; break; }
|
|
}
|
|
return !found;
|
|
});
|
|
// for loop with contains on byActivity (ArrayList) — O(n) per element
|
|
for (String ep : conferenceEndpoints) {
|
|
ops++;
|
|
boolean found = false;
|
|
for (String a : byActivity) { // O(n) scan
|
|
ops++;
|
|
if (a.equals(ep)) { found = true; break; }
|
|
}
|
|
if (!found) {
|
|
byActivity.add(ep);
|
|
}
|
|
}
|
|
return ops;
|
|
}
|
|
|
|
/** Fast: HashSet for O(1) membership tests */
|
|
static long fastEndpointsChanged(List<String> activityList, List<String> conferenceEndpoints) {
|
|
long ops = 0;
|
|
List<String> byActivity = new ArrayList<>(activityList);
|
|
Set<String> confSet = new HashSet<>(conferenceEndpoints);
|
|
ops += conferenceEndpoints.size();
|
|
// O(n) removeIf with O(1) set lookup
|
|
byActivity.removeIf(ep -> { ops_counter[0]++; return !confSet.contains(ep); });
|
|
// O(1) contains check using Set
|
|
Set<String> activitySet = new LinkedHashSet<>(byActivity);
|
|
ops += byActivity.size();
|
|
for (String ep : conferenceEndpoints) {
|
|
ops++;
|
|
if (!activitySet.contains(ep)) { // O(1)
|
|
byActivity.add(ep);
|
|
activitySet.add(ep);
|
|
}
|
|
}
|
|
return ops;
|
|
}
|
|
|
|
// hack for lambda counter
|
|
static long[] ops_counter = new long[1];
|
|
|
|
// ─────────────────────────────────────────────────────────────────────────
|
|
|
|
public static void main(String[] args) {
|
|
int N = 200; // simulate large conference sources
|
|
int SELECTED = 50;
|
|
|
|
// Build source names
|
|
List<String> sources = new ArrayList<>();
|
|
for (int i = 0; i < N; i++) sources.add("source-" + i);
|
|
|
|
List<String> selectedNames = new ArrayList<>();
|
|
for (int i = 0; i < SELECTED; i++) selectedNames.add("source-" + i);
|
|
|
|
// Mix some selected into onStage to create overlap
|
|
List<String> onStage = new ArrayList<>();
|
|
for (int i = 0; i < SELECTED / 2; i++) onStage.add("source-" + i);
|
|
List<String> selectedSources = new ArrayList<>();
|
|
for (int i = SELECTED / 4; i < SELECTED; i++) selectedSources.add("source-" + i);
|
|
|
|
// Activity list: all sources already tracked
|
|
List<String> activityList = new ArrayList<>(sources);
|
|
// Conference: 90% overlap, 10% new
|
|
List<String> conferenceEndpoints = new ArrayList<>();
|
|
for (int i = 0; i < (int)(N * 0.9); i++) conferenceEndpoints.add("source-" + i);
|
|
for (int i = N; i < N + 20; i++) conferenceEndpoints.add("source-" + i);
|
|
|
|
System.out.println("=== jitsi-videobridge CWE-407 benchmark ===");
|
|
System.out.printf(" N=%d sources, %d selected%n%n", N, SELECTED);
|
|
|
|
// --- 0001 contains ---
|
|
long sOps1a = slowPrioritizeContains(sources, selectedNames);
|
|
long fOps1a = fastPrioritize(sources, selectedNames);
|
|
bench("jvb-0001 Prioritize.contains() [N=" + N + ",sel=" + SELECTED + "]",
|
|
() -> slowPrioritizeContains(sources, selectedNames),
|
|
() -> fastPrioritize(sources, selectedNames),
|
|
sOps1a, fOps1a);
|
|
|
|
// --- 0001 indexOf in sort ---
|
|
long sOps1b = slowPrioritizeIndexOf(sources, selectedNames);
|
|
long fOps1b = fastPrioritize(sources, selectedNames);
|
|
bench("jvb-0001 Prioritize.indexOf() in sortBy [N=" + N + ",sel=" + SELECTED + "]",
|
|
() -> slowPrioritizeIndexOf(sources, selectedNames),
|
|
() -> fastPrioritize(sources, selectedNames),
|
|
sOps1b, fOps1b);
|
|
|
|
// --- 0002 selectedSources getter ---
|
|
long sOps2 = slowSelectedSourcesGetter(onStage, selectedSources);
|
|
long fOps2 = fastSelectedSourcesGetter(onStage, selectedSources);
|
|
bench("jvb-0002 BandwidthAllocator.selectedSources getter [N=" + SELECTED + "]",
|
|
() -> slowSelectedSourcesGetter(onStage, selectedSources),
|
|
() -> fastSelectedSourcesGetter(onStage, selectedSources),
|
|
sOps2, fOps2);
|
|
|
|
// --- 0003 endpointsChanged ---
|
|
ops_counter[0] = 0;
|
|
long sOps3 = slowEndpointsChanged(activityList, conferenceEndpoints);
|
|
ops_counter[0] = 0;
|
|
long fOps3 = fastEndpointsChanged(activityList, conferenceEndpoints);
|
|
bench("jvb-0003 ConferenceSpeechActivity.endpointsChanged [N=" + N + "]",
|
|
() -> slowEndpointsChanged(activityList, conferenceEndpoints),
|
|
() -> fastEndpointsChanged(activityList, conferenceEndpoints),
|
|
sOps3, fOps3);
|
|
|
|
System.out.println();
|
|
|
|
// Assertions
|
|
int pass = 0, total = 0;
|
|
|
|
// 0001-contains: slow scans list for each source → O(N*SELECTED) in worst case (misses),
|
|
// early-exit on hits means actual ops ~= N + SELECTED*(SELECTED/2) for selected hits + N*SELECTED for misses.
|
|
// Simplest check: slow >> fast by at least 10x.
|
|
total++;
|
|
if (sOps1a > fOps1a * 10) {
|
|
System.out.println(" jvb-0001-contains: PASS (slow=" + sOps1a + " > 10x fast=" + fOps1a + ")");
|
|
pass++;
|
|
} else {
|
|
System.out.println(" jvb-0001-contains: FAIL (slow=" + sOps1a + " fast=" + fOps1a + ")");
|
|
}
|
|
|
|
// 0001-indexOf: slow >> fast
|
|
total++;
|
|
if (sOps1b > fOps1b * 5) {
|
|
System.out.println(" jvb-0001-indexOf: PASS (slow=" + sOps1b + " > 5x fast=" + fOps1b + ")");
|
|
pass++;
|
|
} else {
|
|
System.out.println(" jvb-0001-indexOf: FAIL (slow=" + sOps1b + " fast=" + fOps1b + ")");
|
|
}
|
|
|
|
// 0002: slow >= onStage.size * selected.size, fast <= onStage+selected
|
|
total++;
|
|
if (sOps2 > fOps2 * 3) {
|
|
System.out.println(" jvb-0002-getter: PASS (slow=" + sOps2 + " > 3x fast=" + fOps2 + ")");
|
|
pass++;
|
|
} else {
|
|
System.out.println(" jvb-0002-getter: FAIL (slow=" + sOps2 + " fast=" + fOps2 + ")");
|
|
}
|
|
|
|
// 0003: slow >= N*conf, fast < N + conf
|
|
total++;
|
|
if (sOps3 > fOps3 * 5) {
|
|
System.out.println(" jvb-0003-changed: PASS (slow=" + sOps3 + " > 5x fast=" + fOps3 + ")");
|
|
pass++;
|
|
} else {
|
|
System.out.println(" jvb-0003-changed: FAIL (slow=" + sOps3 + " fast=" + fOps3 + ")");
|
|
}
|
|
|
|
System.out.println();
|
|
System.out.println(pass + "/" + total + (pass == total ? " PASS" : " FAIL"));
|
|
if (pass != total) System.exit(1);
|
|
}
|
|
}
|