115 lines
3.6 KiB
Python
115 lines
3.6 KiB
Python
"""
|
|
wine-0003 — CWE-407: crypt32 CRYPT_CheckSimpleChainForCycles O(N^2)
|
|
|
|
Simulates defect (nested loop cert comparison) vs. fix (hash-set thumbprint lookup).
|
|
Benchmarks at N=100 and N=1000, asserts speedup > 3x.
|
|
"""
|
|
import hashlib
|
|
import time
|
|
import os
|
|
|
|
os.environ["PYTHONUNBUFFERED"] = "1"
|
|
|
|
|
|
def make_cert(serial: int) -> dict:
|
|
"""Simulate a certificate context with a unique serial number."""
|
|
return {"serial": serial, "issuer": "CA", "subject": f"cert-{serial}"}
|
|
|
|
|
|
def cert_compare(a: dict, b: dict) -> bool:
|
|
"""Simulate CertCompareCertificate — compare full struct."""
|
|
return a["serial"] == b["serial"] and a["issuer"] == b["issuer"]
|
|
|
|
|
|
def thumbprint(cert: dict) -> bytes:
|
|
"""Simulate SHA-1 thumbprint of a certificate (stable identifier)."""
|
|
key = f"{cert['issuer']}:{cert['serial']}".encode()
|
|
return hashlib.sha1(key).digest()
|
|
|
|
|
|
# --- Defective O(N^2) implementation ---
|
|
|
|
def check_chain_cycles_defective(chain: list) -> int:
|
|
"""
|
|
Mirror of CRYPT_CheckSimpleChainForCycles in dlls/crypt32/chain.c.
|
|
Returns index of first duplicate (cycle) or 0 if none.
|
|
"""
|
|
n = len(chain)
|
|
cyclic_index = 0
|
|
for i in range(n):
|
|
if cyclic_index:
|
|
break
|
|
for j in range(i + 1, n):
|
|
if cert_compare(chain[i], chain[j]):
|
|
cyclic_index = j
|
|
break
|
|
return cyclic_index
|
|
|
|
|
|
# --- Fixed O(N) implementation ---
|
|
|
|
def check_chain_cycles_fixed(chain: list) -> int:
|
|
"""
|
|
O(N) replacement using hash set of thumbprints.
|
|
"""
|
|
seen: dict[bytes, int] = {}
|
|
for i, cert in enumerate(chain):
|
|
tp = thumbprint(cert)
|
|
if tp in seen:
|
|
return i
|
|
seen[tp] = i
|
|
return 0
|
|
|
|
|
|
def build_chain(n: int, *, inject_cycle_at: int = None) -> list:
|
|
"""Build a chain of n unique certs, optionally duplicating one."""
|
|
chain = [make_cert(i) for i in range(n)]
|
|
if inject_cycle_at is not None and inject_cycle_at < n:
|
|
# duplicate cert 0 at inject_cycle_at
|
|
chain[inject_cycle_at] = make_cert(0)
|
|
return chain
|
|
|
|
|
|
def benchmark(fn, chain: list, reps: int = 5) -> float:
|
|
"""Return best wall-clock time in seconds over reps runs."""
|
|
best = float("inf")
|
|
for _ in range(reps):
|
|
t0 = time.perf_counter()
|
|
fn(chain)
|
|
t1 = time.perf_counter()
|
|
best = min(best, t1 - t0)
|
|
return best
|
|
|
|
|
|
def run_tests() -> None:
|
|
# --- Correctness tests ---
|
|
# No cycle
|
|
chain_clean = build_chain(20)
|
|
assert check_chain_cycles_defective(chain_clean) == 0, "FAIL: false positive (defective)"
|
|
assert check_chain_cycles_fixed(chain_clean) == 0, "FAIL: false positive (fixed)"
|
|
print(" [correctness] no-cycle chain: PASS")
|
|
|
|
# With cycle at index 10
|
|
chain_cyclic = build_chain(20, inject_cycle_at=10)
|
|
idx_d = check_chain_cycles_defective(chain_cyclic)
|
|
idx_f = check_chain_cycles_fixed(chain_cyclic)
|
|
assert idx_d == 10, f"FAIL: defective detected cycle at {idx_d}, expected 10"
|
|
assert idx_f == 10, f"FAIL: fixed detected cycle at {idx_f}, expected 10"
|
|
print(" [correctness] cyclic chain (dup at 10): PASS")
|
|
|
|
# --- Performance benchmarks ---
|
|
for n, reps in [(100, 20), (1000, 5)]:
|
|
chain = build_chain(n)
|
|
t_def = benchmark(check_chain_cycles_defective, chain, reps)
|
|
t_fix = benchmark(check_chain_cycles_fixed, chain, reps)
|
|
ratio = t_def / t_fix if t_fix > 0 else float("inf")
|
|
print(f" [bench N={n:4d}] defective={t_def*1e6:.1f}us fixed={t_fix*1e6:.1f}us ratio={ratio:.1f}x")
|
|
assert ratio > 3.0, (
|
|
f"FAIL: expected speedup > 3x at N={n}, got {ratio:.2f}x"
|
|
)
|
|
|
|
print("\nPASS wine-0003")
|
|
|
|
|
|
if __name__ == "__main__":
|
|
run_tests()
|