102 lines
3.6 KiB
Java
102 lines
3.6 KiB
Java
import java.util.*;
|
|
|
|
/**
|
|
* Unit test for Suricata CWE-407: SigFindSignatureBySidGid O(S) linear scan
|
|
* called per threshold.conf line, giving O(T*S) total at startup.
|
|
*
|
|
* Defect: util-threshold-config.c calls SigFindSignatureBySidGid() for each
|
|
* threshold config line. That function walks the entire sig_list linked list
|
|
* O(S) per call. With T threshold lines: O(T * S).
|
|
*
|
|
* In production Suricata: S = 30,000-80,000 (ET rules), T = 100-5,000
|
|
* threshold/suppress entries. At T=1000, S=30000: 30 million comparisons.
|
|
*
|
|
* Fix: Build a HashMap<(sid,gid), Signature> once before threshold parsing.
|
|
* Lookup becomes O(1) per line. Total: O(S + T) instead of O(T * S).
|
|
*/
|
|
public class SuricataThresholdLookupTest {
|
|
|
|
static class Signature {
|
|
int sid;
|
|
int gid;
|
|
Signature(int sid, int gid) { this.sid = sid; this.gid = gid; }
|
|
}
|
|
|
|
// --- Defective: linear scan per lookup ---
|
|
static int defectiveOps = 0;
|
|
|
|
static Signature findSigLinear(List<Signature> sigList, int sid, int gid) {
|
|
for (Signature s : sigList) {
|
|
defectiveOps++;
|
|
if (s.sid == sid && s.gid == gid)
|
|
return s;
|
|
}
|
|
return null;
|
|
}
|
|
|
|
// --- Fixed: hash map lookup ---
|
|
static int fixedOps = 0;
|
|
|
|
static Map<Long, Signature> buildSigMap(List<Signature> sigList) {
|
|
Map<Long, Signature> map = new HashMap<>();
|
|
for (Signature s : sigList) {
|
|
fixedOps++;
|
|
long key = ((long) s.sid << 32) | (s.gid & 0xFFFFFFFFL);
|
|
map.put(key, s);
|
|
}
|
|
return map;
|
|
}
|
|
|
|
static Signature findSigFixed(Map<Long, Signature> sigMap, int sid, int gid) {
|
|
fixedOps++;
|
|
long key = ((long) sid << 32) | (gid & 0xFFFFFFFFL);
|
|
return sigMap.get(key);
|
|
}
|
|
|
|
public static void main(String[] args) {
|
|
int S = 30000; // number of signatures (typical ET ruleset)
|
|
int T = 1000; // number of threshold config lines
|
|
|
|
// Build signature list
|
|
List<Signature> sigList = new ArrayList<>();
|
|
for (int i = 0; i < S; i++)
|
|
sigList.add(new Signature(i + 1, 1));
|
|
|
|
// Threshold entries: lookup random sids
|
|
int[] thresholdSids = new int[T];
|
|
Random rng = new Random(42);
|
|
for (int i = 0; i < T; i++)
|
|
thresholdSids[i] = rng.nextInt(S) + 1;
|
|
|
|
// Run defective version: linear scan per threshold line
|
|
defectiveOps = 0;
|
|
for (int sid : thresholdSids) {
|
|
Signature found = findSigLinear(sigList, sid, 1);
|
|
assert found != null : "Should find sid " + sid;
|
|
}
|
|
int defOps = defectiveOps;
|
|
|
|
// Run fixed version: build hash map once, then O(1) lookups
|
|
fixedOps = 0;
|
|
Map<Long, Signature> sigMap = buildSigMap(sigList);
|
|
for (int sid : thresholdSids) {
|
|
Signature found = findSigFixed(sigMap, sid, 1);
|
|
assert found != null : "Should find sid " + sid;
|
|
}
|
|
int fixOps = fixedOps;
|
|
|
|
double ratio = (double) defOps / fixOps;
|
|
|
|
System.out.println("=== Suricata suricata-0001: SigFindSignatureBySidGid O(T*S) ===");
|
|
System.out.println("S (signatures): " + S);
|
|
System.out.println("T (threshold lines): " + T);
|
|
System.out.println("Defective ops: " + defOps);
|
|
System.out.println("Fixed ops: " + fixOps);
|
|
System.out.printf("Ratio: %.1fx%n", ratio);
|
|
|
|
// Verify ratio shows quadratic vs linear improvement
|
|
assert ratio > 100.0 : "Expected >100x ratio, got " + ratio;
|
|
|
|
System.out.println("PASS");
|
|
}
|
|
}
|