russell@unturf.com
ff6292d067
postgres-0001: pg_inherits.c typeInheritsFrom() BFS visited List → HTAB O(1) asterisk-0001: app_queue.c interface_exists() ao2_iterator walk → ao2_find O(1) haproxy-0001: http_ana.c cookie-server scan linked-list → eb-tree index O(log S) nginx-0001: ngx_http_link_multi_headers() O(H²) double-scan → O(H) hash pass postfix: CLEAN (htable throughout; two marginal LOW admin-bounded candidates) bevy: CLEAN (FixedBitSet/HashSet throughout; only hardware-bounded marginals)
73 lines
2.8 KiB
Java
73 lines
2.8 KiB
Java
import java.util.*;
|
||
|
||
/**
|
||
* CWE-407 unit test for HAProxy http_ana.c defect.
|
||
*
|
||
* haproxy-0001: src/http_ana.c http_manage_client_side_cookies()
|
||
* while (srv) { if memcmp(val_beg, srv->cookie, ...) } — O(S) linked-list
|
||
* walk per HTTP request to match a cookie value to a backend server.
|
||
* Fix: build struct eb_root cookies_tree at config-time (same as cfgdiag.c
|
||
* already does for diagnostic purposes); use ebis_lookup() for O(log S) lookup.
|
||
*/
|
||
public class HaproxyTest {
|
||
|
||
// Simulate defect: O(S) linked-list walk per request
|
||
static String cookieLookup_list(List<String[]> servers, String cookieVal) {
|
||
// servers: list of {name, cookie}
|
||
for (String[] srv : servers) { // O(S) — defect
|
||
if (srv[1] != null && srv[1].equals(cookieVal)) {
|
||
return srv[0];
|
||
}
|
||
}
|
||
return null;
|
||
}
|
||
|
||
// Simulate fix: O(1) hash map (models eb-tree O(log S))
|
||
static String cookieLookup_tree(Map<String, String> cookieIndex, String cookieVal) {
|
||
return cookieIndex.get(cookieVal); // O(1) / O(log S) with eb-tree
|
||
}
|
||
|
||
static void testHaproxy0001() throws Exception {
|
||
int S = 1000; // backend servers
|
||
List<String[]> servers = new ArrayList<>();
|
||
Map<String, String> cookieIndex = new HashMap<>();
|
||
|
||
for (int i = 0; i < S; i++) {
|
||
String name = "backend" + i;
|
||
String cookie = "srv" + String.format("%04d", i);
|
||
servers.add(new String[]{name, cookie});
|
||
cookieIndex.put(cookie, name);
|
||
}
|
||
|
||
// Request targets last server (worst case for linear scan)
|
||
String target = "srv" + String.format("%04d", S - 1);
|
||
|
||
// correctness
|
||
String r1 = cookieLookup_list(servers, target);
|
||
String r2 = cookieLookup_tree(cookieIndex, target);
|
||
assert r1 != null && r1.equals(r2) : "list and tree must agree: " + r1 + " vs " + r2;
|
||
assert cookieLookup_list(servers, "srvXXXX") == null;
|
||
assert cookieLookup_tree(cookieIndex, "srvXXXX") == null;
|
||
|
||
// performance: simulate R HTTP requests
|
||
int R = 50_000;
|
||
long t0 = System.nanoTime();
|
||
for (int r = 0; r < R; r++) cookieLookup_list(servers, target);
|
||
long tList = System.nanoTime() - t0;
|
||
|
||
t0 = System.nanoTime();
|
||
for (int r = 0; r < R; r++) cookieLookup_tree(cookieIndex, target);
|
||
long tTree = System.nanoTime() - t0;
|
||
|
||
double ratio = (double) tList / tTree;
|
||
System.out.printf("haproxy-0001: list=%.3fs tree=%.3fs ratio=%.1f×%n",
|
||
tList / 1e9, tTree / 1e9, ratio);
|
||
assert ratio > 20 : "Expected >20× speedup, got " + ratio;
|
||
System.out.println("PASS haproxy-0001");
|
||
}
|
||
|
||
public static void main(String[] args) throws Exception {
|
||
testHaproxy0001();
|
||
System.out.println("ALL PASS");
|
||
}
|
||
}
|