russell@unturf.com
49edd9e440
pgbouncer-0001 (CWE-312 SCRAM verifier logged at slog_debug) was already documented. pgbouncer-0002: find_database() uses statlist_for_each + strcmp O(D) on every new client connection login path. find_global_user() uses aatree_search O(log U) but DB lookup was never upgraded. Fix: AA-tree or hash index mirroring user_tree pattern. 100x op-count at D=100, 1000x at D=1000. Test PASS. MOADs 0002/0003/0005 CLEAN.
142 lines
4.3 KiB
Python
142 lines
4.3 KiB
Python
"""
|
|
pgbouncer-0002: CWE-407 — find_database() O(D) linear scan on per-connection login path
|
|
|
|
Source: src/objects.c, function find_database()
|
|
Defect: statlist_for_each + strcmp iterates all D databases on every new client
|
|
connection login. User lookup uses aatree_search() O(log U) but DB lookup
|
|
was never upgraded from linked-list O(D).
|
|
|
|
Fix: Add an AA-tree (or hash table) index for database lookup, matching the pattern
|
|
used by user_tree for global user lookup.
|
|
|
|
Benchmark: measures op-count ratio between linear scan (defective) and dict (fixed)
|
|
at N=100 and N=1000 databases. Assert speedup > 3x.
|
|
"""
|
|
|
|
import time
|
|
import sys
|
|
|
|
export_PYTHONUNBUFFERED = True # handled by caller via env
|
|
|
|
# ---- simulate the defective linked-list find_database ----
|
|
|
|
def find_database_linear(db_list, name):
|
|
"""O(D) linear scan — mirrors statlist_for_each + strcmp in objects.c"""
|
|
for db_name in db_list:
|
|
if db_name == name:
|
|
return db_name
|
|
return None
|
|
|
|
|
|
# ---- simulate the fixed hash/tree find_database ----
|
|
|
|
def find_database_hash(db_index, name):
|
|
"""O(1) hash lookup — mirrors what an AA-tree or hash index provides"""
|
|
return db_index.get(name)
|
|
|
|
|
|
def build_db_list(n):
|
|
return [f"tenant_{i:06d}" for i in range(n)]
|
|
|
|
|
|
def build_db_index(db_list):
|
|
return {name: name for name in db_list}
|
|
|
|
|
|
def measure_op_count_linear(db_list, queries):
|
|
"""Count total strcmp-equivalent ops for all queries against linear list."""
|
|
total_ops = 0
|
|
for name in queries:
|
|
for db_name in db_list:
|
|
total_ops += 1
|
|
if db_name == name:
|
|
break
|
|
return total_ops
|
|
|
|
|
|
def measure_op_count_hash(db_index, queries):
|
|
"""Count total ops for hash lookup — always 1 per query."""
|
|
return len(queries)
|
|
|
|
|
|
def run_benchmark(n, label):
|
|
db_list = build_db_list(n)
|
|
db_index = build_db_index(db_list)
|
|
|
|
# Queries: worst-case (last element in list) to stress the linear scan
|
|
queries = [db_list[-1]] * 1000 # 1000 connections all hitting last DB
|
|
|
|
op_count_linear = measure_op_count_linear(db_list, queries)
|
|
op_count_hash = measure_op_count_hash(db_index, queries)
|
|
|
|
# Also measure wall time
|
|
t0 = time.perf_counter()
|
|
for q in queries:
|
|
find_database_linear(db_list, q)
|
|
t_linear = time.perf_counter() - t0
|
|
|
|
t0 = time.perf_counter()
|
|
for q in queries:
|
|
find_database_hash(db_index, q)
|
|
t_hash = time.perf_counter() - t0
|
|
|
|
ratio_ops = op_count_linear / max(op_count_hash, 1)
|
|
ratio_time = t_linear / max(t_hash, 1e-9)
|
|
|
|
print(f" D={n}: linear={op_count_linear} ops, hash={op_count_hash} ops, "
|
|
f"op-ratio={ratio_ops:.1f}x, time-ratio={ratio_time:.1f}x")
|
|
|
|
return ratio_ops, ratio_time
|
|
|
|
|
|
def test_correctness():
|
|
"""Both implementations must return the same result."""
|
|
db_list = build_db_list(50)
|
|
db_index = build_db_index(db_list)
|
|
|
|
# Known hit
|
|
result_linear = find_database_linear(db_list, "tenant_000025")
|
|
result_hash = find_database_hash(db_index, "tenant_000025")
|
|
assert result_linear == result_hash == "tenant_000025", (
|
|
f"correctness fail: linear={result_linear}, hash={result_hash}"
|
|
)
|
|
|
|
# Known miss
|
|
result_linear = find_database_linear(db_list, "does_not_exist")
|
|
result_hash = find_database_hash(db_index, "does_not_exist")
|
|
assert result_linear is None and result_hash is None, (
|
|
f"miss correctness fail: linear={result_linear}, hash={result_hash}"
|
|
)
|
|
print("PASS correctness: linear and hash agree on hit and miss")
|
|
|
|
|
|
def test_speedup_n100():
|
|
ratio_ops, _ = run_benchmark(100, "N=100")
|
|
assert ratio_ops >= 3.0, f"FAIL N=100: op-ratio {ratio_ops:.1f}x < 3x threshold"
|
|
print(f"PASS N=100: op-ratio {ratio_ops:.1f}x >= 3x")
|
|
|
|
|
|
def test_speedup_n1000():
|
|
ratio_ops, _ = run_benchmark(1000, "N=1000")
|
|
assert ratio_ops >= 3.0, f"FAIL N=1000: op-ratio {ratio_ops:.1f}x < 3x threshold"
|
|
print(f"PASS N=1000: op-ratio {ratio_ops:.1f}x >= 3x")
|
|
|
|
|
|
def main():
|
|
print("=== pgbouncer-0002: CWE-407 find_database() O(D) linear scan ===")
|
|
print()
|
|
|
|
print("Correctness check:")
|
|
test_correctness()
|
|
print()
|
|
|
|
print("Benchmark — op-count ratio (linear / hash), worst-case queries:")
|
|
test_speedup_n100()
|
|
test_speedup_n1000()
|
|
print()
|
|
print("ALL PASS")
|
|
return 0
|
|
|
|
|
|
if __name__ == "__main__":
|
|
sys.exit(main())
|