russell@unturf.com
0de158cd7a
nagioscore-0001: add_notification find_notification linked-list O(C²) HIGH 999x nagioscore-0002: add_object_to_objectlist linked-list dedup O(N²) MEDIUM 1499x zabbix-0001: process_problem_tags tag dedup O(T²) HIGH 1499x zabbix-0002: discoverer_queue_lock job ID dedup O(N²) MEDIUM 1499x zenoss: CLEAN — uses OrderedDict/set/catalog throughout 4/4 PASS, 4 defects across 2 targets
76 lines
2.8 KiB
Java
76 lines
2.8 KiB
Java
import java.util.*;
|
||
|
||
/**
|
||
* CWE-407 unit test for Zabbix zabbix-0002:
|
||
* discoverer_queue_lock() in discoverer_queue.c — O(N²) job ID dedup via
|
||
* zbx_vector_uint64_search linear scan.
|
||
*
|
||
* Defect: While iterating discovery jobs in the queue, the code builds a
|
||
* visited-IDs vector using zbx_vector_uint64_search (linear scan) to detect
|
||
* when we've looped back to a previously-seen job. N jobs × O(N) search = O(N²).
|
||
*
|
||
* Fix: Use a HashSet (zbx_hashset_t in C) for O(1) ID membership check.
|
||
*/
|
||
public class ZabbixDiscovererQueueDedupTest {
|
||
|
||
public static void main(String[] args) {
|
||
int N = 3000; // number of discovery jobs in queue
|
||
|
||
// Simulate unique job IDs
|
||
long[] jobIds = new long[N];
|
||
for (int i = 0; i < N; i++) {
|
||
jobIds[i] = i + 1;
|
||
}
|
||
|
||
// --- Defective: linear scan of ids vector ---
|
||
List<Long> idsDefective = new ArrayList<>();
|
||
long opsDefective = 0;
|
||
long startDef = System.nanoTime();
|
||
for (long id : jobIds) {
|
||
boolean found = false;
|
||
for (Long existing : idsDefective) {
|
||
opsDefective++;
|
||
if (existing == id) {
|
||
found = true;
|
||
break;
|
||
}
|
||
}
|
||
if (!found) {
|
||
idsDefective.add(id);
|
||
}
|
||
}
|
||
long defectiveNs = System.nanoTime() - startDef;
|
||
|
||
// --- Fixed: HashSet for O(1) lookup ---
|
||
HashSet<Long> idsFixed = new HashSet<>();
|
||
long opsFixed = 0;
|
||
long startFix = System.nanoTime();
|
||
for (long id : jobIds) {
|
||
opsFixed++;
|
||
if (!idsFixed.contains(id)) {
|
||
idsFixed.add(id);
|
||
}
|
||
}
|
||
long fixedNs = System.nanoTime() - startFix;
|
||
|
||
double ratio = (double) opsDefective / Math.max(opsFixed, 1);
|
||
double speedup = (double) defectiveNs / Math.max(fixedNs, 1);
|
||
|
||
System.out.println("=== Zabbix zabbix-0002: discoverer queue ID dedup CWE-407 ===");
|
||
System.out.println("Jobs: " + N);
|
||
System.out.println("Defective ops: " + opsDefective);
|
||
System.out.println("Fixed ops: " + opsFixed);
|
||
System.out.println("Op ratio: " + String.format("%.1fx", ratio));
|
||
System.out.println("Defective time: " + (defectiveNs / 1_000_000) + " ms");
|
||
System.out.println("Fixed time: " + (fixedNs / 1_000_000) + " ms");
|
||
System.out.println("Speedup: " + String.format("%.1fx", speedup));
|
||
|
||
assert idsFixed.size() == N : "Fixed should have all IDs";
|
||
assert idsDefective.size() == N : "Defective should have all IDs";
|
||
|
||
boolean pass = ratio > 5.0;
|
||
System.out.println("RESULT: " + (pass ? "PASS" : "FAIL") +
|
||
" (ratio " + String.format("%.1f", ratio) + "x, threshold 5x)");
|
||
if (!pass) System.exit(1);
|
||
}
|
||
}
|