235 lines
11 KiB
Java
235 lines
11 KiB
Java
package unit;
|
||
import java.util.*;
|
||
|
||
/**
|
||
* CWE-407 benchmark for linphone-sdk defects:
|
||
* linphone-0001: offeranswer.cpp matchPayloads O(n²) codec negotiation
|
||
* - outer for(remote) + inner genericMatch scan of local: O(|remote| × |local|)
|
||
* - CAN_RECV fallback nested loops: O(|local| × |remote|)
|
||
* - matchCryptoAlgo nested vectors: O(|remote| × |local|)
|
||
*/
|
||
public class LinphoneTest {
|
||
|
||
static void bench(String label, Runnable slow, Runnable fast, long sOps, long fOps) {
|
||
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);
|
||
}
|
||
|
||
// Simulated payload type: (mimeType, clockRate, channels) → payloadNumber
|
||
static class PayloadType {
|
||
final String mimeType;
|
||
final int clockRate;
|
||
final int channels;
|
||
int number;
|
||
PayloadType(String m, int c, int ch, int n) { mimeType = m; clockRate = c; channels = ch; number = n; }
|
||
String key() { return (mimeType + "/" + clockRate + "/" + channels).toLowerCase(); }
|
||
}
|
||
|
||
// ─────────────────────────────────────────────────────────────────────────
|
||
// linphone-0001a: matchPayloads outer(remote) × inner(local) generic scan
|
||
// ─────────────────────────────────────────────────────────────────────────
|
||
|
||
/** Slow: O(|remote| × |local|) — genericMatch linear scan per remote entry */
|
||
static long slowMatchPayloads(List<PayloadType> local, List<PayloadType> remote) {
|
||
long ops = 0;
|
||
List<PayloadType> result = new ArrayList<>();
|
||
for (PayloadType remote_pt : remote) {
|
||
ops++;
|
||
// genericMatch: linear scan of local
|
||
PayloadType matched = null;
|
||
for (PayloadType local_pt : local) {
|
||
ops++;
|
||
if (local_pt.mimeType.equalsIgnoreCase(remote_pt.mimeType)
|
||
&& local_pt.clockRate == remote_pt.clockRate
|
||
&& local_pt.channels == remote_pt.channels) {
|
||
matched = local_pt;
|
||
break;
|
||
}
|
||
}
|
||
if (matched != null) result.add(matched);
|
||
}
|
||
return ops;
|
||
}
|
||
|
||
/** Fast: O(|remote| + |local|) — HashMap pre-built from local */
|
||
static long fastMatchPayloads(List<PayloadType> local, List<PayloadType> remote) {
|
||
long ops = 0;
|
||
// Pre-build map from local — O(|local|)
|
||
Map<String, PayloadType> localMap = new HashMap<>();
|
||
for (PayloadType pt : local) {
|
||
ops++;
|
||
localMap.putIfAbsent(pt.key(), pt);
|
||
}
|
||
List<PayloadType> result = new ArrayList<>();
|
||
for (PayloadType remote_pt : remote) {
|
||
ops++;
|
||
PayloadType matched = localMap.get(remote_pt.key());
|
||
if (matched != null) result.add(matched);
|
||
}
|
||
return ops;
|
||
}
|
||
|
||
// ─────────────────────────────────────────────────────────────────────────
|
||
// linphone-0001b: CAN_RECV fallback nested loop (lines 308-315)
|
||
// ─────────────────────────────────────────────────────────────────────────
|
||
|
||
/** Slow: O(|local| × |remote|) — nested loop checking payload numbers */
|
||
static long slowCanRecvFallback(List<PayloadType> local, List<PayloadType> remote) {
|
||
long ops = 0;
|
||
boolean found = false;
|
||
for (PayloadType p1 : local) {
|
||
ops++;
|
||
for (PayloadType p2 : remote) {
|
||
ops++;
|
||
if (p2.number == p1.number) { found = true; break; }
|
||
}
|
||
if (found) break;
|
||
}
|
||
return ops;
|
||
}
|
||
|
||
/** Fast: O(|local| + |remote|) — HashSet of remote payload numbers */
|
||
static long fastCanRecvFallback(List<PayloadType> local, List<PayloadType> remote) {
|
||
long ops = 0;
|
||
Set<Integer> remoteNums = new HashSet<>();
|
||
for (PayloadType p2 : remote) { ops++; remoteNums.add(p2.number); }
|
||
for (PayloadType p1 : local) {
|
||
ops++;
|
||
if (remoteNums.contains(p1.number)) break;
|
||
}
|
||
return ops;
|
||
}
|
||
|
||
// ─────────────────────────────────────────────────────────────────────────
|
||
// linphone-0001c: matchCryptoAlgo nested vector scan (lines 345-360)
|
||
// ─────────────────────────────────────────────────────────────────────────
|
||
|
||
/** Slow: O(|remote| × |local|) — nested loops for crypto algo matching */
|
||
static long slowMatchCrypto(List<Integer> localAlgos, List<Integer> remoteAlgos) {
|
||
long ops = 0;
|
||
int result = 0;
|
||
for (int rc : remoteAlgos) {
|
||
ops++;
|
||
if (rc == 0) break;
|
||
for (int lc : localAlgos) {
|
||
ops++;
|
||
if (rc == lc) { result = rc; break; }
|
||
}
|
||
}
|
||
return ops;
|
||
}
|
||
|
||
/** Fast: O(|remote| + |local|) — HashSet of local algo IDs */
|
||
static long fastMatchCrypto(List<Integer> localAlgos, List<Integer> remoteAlgos) {
|
||
long ops = 0;
|
||
Set<Integer> localSet = new HashSet<>(localAlgos);
|
||
ops += localAlgos.size();
|
||
int result = 0;
|
||
for (int rc : remoteAlgos) {
|
||
ops++;
|
||
if (rc == 0) break;
|
||
if (localSet.contains(rc)) { result = rc; break; }
|
||
}
|
||
return ops;
|
||
}
|
||
|
||
// ─────────────────────────────────────────────────────────────────────────
|
||
|
||
public static void main(String[] args) {
|
||
// Realistic SDP: 40 remote codecs, 35 local codecs
|
||
// (video with H.264/VP8/VP9/AV1 + RTX/FEC/RED variants)
|
||
int LOCAL = 35, REMOTE = 40;
|
||
|
||
String[] mimes = {"H264", "VP8", "VP9", "AV1", "opus", "PCMU", "PCMA", "G722",
|
||
"telephone-event", "flexfec-03", "red", "ulpfec", "rtx"};
|
||
int[] rates = {90000, 90000, 90000, 90000, 48000, 8000, 8000, 8000, 8000, 90000, 90000, 90000, 90000};
|
||
|
||
List<PayloadType> local = new ArrayList<>();
|
||
List<PayloadType> remote = new ArrayList<>();
|
||
for (int i = 0; i < LOCAL; i++) {
|
||
int mi = i % mimes.length;
|
||
local.add(new PayloadType(mimes[mi], rates[mi], 1, 96 + i));
|
||
}
|
||
for (int i = 0; i < REMOTE; i++) {
|
||
int mi = (i + 2) % mimes.length; // offset to create some misses
|
||
remote.add(new PayloadType(mimes[mi], rates[mi], 1, 96 + i));
|
||
}
|
||
|
||
// Crypto algos: 8 remote, 6 local
|
||
List<Integer> localCrypto = Arrays.asList(1, 2, 3, 4, 5, 6);
|
||
List<Integer> remoteCrypto = Arrays.asList(3, 5, 7, 8, 9, 2, 1, 0);
|
||
|
||
System.out.println("=== linphone CWE-407 benchmark ===");
|
||
System.out.printf(" local=%d codecs, remote=%d codecs%n%n", LOCAL, REMOTE);
|
||
|
||
long sOpsA = slowMatchPayloads(local, remote);
|
||
long fOpsA = fastMatchPayloads(local, remote);
|
||
bench("linphone-0001a matchPayloads genericMatch scan [L=" + LOCAL + ",R=" + REMOTE + "]",
|
||
() -> slowMatchPayloads(local, remote),
|
||
() -> fastMatchPayloads(local, remote),
|
||
sOpsA, fOpsA);
|
||
|
||
long sOpsB = slowCanRecvFallback(local, remote);
|
||
long fOpsB = fastCanRecvFallback(local, remote);
|
||
bench("linphone-0001b CAN_RECV fallback nested loop [L=" + LOCAL + ",R=" + REMOTE + "]",
|
||
() -> slowCanRecvFallback(local, remote),
|
||
() -> fastCanRecvFallback(local, remote),
|
||
sOpsB, fOpsB);
|
||
|
||
long sOpsC = slowMatchCrypto(localCrypto, remoteCrypto);
|
||
long fOpsC = fastMatchCrypto(localCrypto, remoteCrypto);
|
||
bench("linphone-0001c matchCryptoAlgo nested scan [L=6,R=8]",
|
||
() -> slowMatchCrypto(localCrypto, remoteCrypto),
|
||
() -> fastMatchCrypto(localCrypto, remoteCrypto),
|
||
sOpsC, fOpsC);
|
||
|
||
System.out.println();
|
||
|
||
// Assertions
|
||
int pass = 0, total = 0;
|
||
|
||
// 0001a: slow is O(remote * local/avg) due to early-break on match; fast is O(local+remote).
|
||
// Key invariant: fast ops < slow ops when local is large.
|
||
total++;
|
||
if (fOpsA < sOpsA) {
|
||
System.out.printf(" linphone-0001a: PASS (slow=%d fast=%d, speedup=%.1fx)%n", sOpsA, fOpsA, (double)sOpsA/fOpsA);
|
||
pass++;
|
||
} else {
|
||
System.out.println(" linphone-0001a: FAIL (slow=" + sOpsA + " fast=" + fOpsA + ")");
|
||
}
|
||
|
||
// 0001b: the fast path builds a full set (O(remote)) before scanning local.
|
||
// Worst case for slow is O(local * remote) when nothing matches early.
|
||
// Use all-misses input to force the worst case.
|
||
List<PayloadType> localNoMatch = new ArrayList<>();
|
||
List<PayloadType> remoteNoMatch = new ArrayList<>();
|
||
for (int i = 0; i < LOCAL; i++) localNoMatch.add(new PayloadType("codec", 8000, 1, 200 + i));
|
||
for (int i = 0; i < REMOTE; i++) remoteNoMatch.add(new PayloadType("other", 8000, 1, 300 + i));
|
||
|
||
long sOpsB2 = slowCanRecvFallback(localNoMatch, remoteNoMatch);
|
||
long fOpsB2 = fastCanRecvFallback(localNoMatch, remoteNoMatch);
|
||
total++;
|
||
if (sOpsB2 > fOpsB2 * 2) {
|
||
System.out.printf(" linphone-0001b: PASS all-miss (slow=%d > 2x fast=%d)%n", sOpsB2, fOpsB2);
|
||
pass++;
|
||
} else {
|
||
System.out.println(" linphone-0001b: FAIL all-miss (slow=" + sOpsB2 + " fast=" + fOpsB2 + ")");
|
||
}
|
||
|
||
total++;
|
||
if (sOpsC >= localCrypto.size() * remoteCrypto.size() / 4 && fOpsC < sOpsC) {
|
||
System.out.println(" linphone-0001c: PASS (slow=" + sOpsC + " fast=" + fOpsC + ")");
|
||
pass++;
|
||
} else {
|
||
System.out.println(" linphone-0001c: FAIL (slow=" + sOpsC + " fast=" + fOpsC + ")");
|
||
}
|
||
|
||
System.out.println();
|
||
System.out.println(pass + "/" + total + (pass == total ? " PASS" : " FAIL"));
|
||
if (pass != total) System.exit(1);
|
||
}
|
||
}
|