russell@unturf.com
9a0253e724
selenium-0001: SessionCapabilitiesMutator list.contains O(NxM) -> LinkedHashSet O(N+M). Grid Node session mutation hot path. Bench: 192x at N=M=1000. selenium-0002: ChromiumOptions merge helpers consolidate four list.contains loops behind addArgumentsUnique/addEncodedExtensionsUnique. Bench: 254x at N=M=1000. playwright-0001: roleUtils validRoles / allowsNameFromContent Array.includes on 20-70 element constant arrays per element. Converted to Set<string> at module load. Bench: 11x at N=10000 elements. webdriverio-0001: xpath-conditions extractOrConditions orMatches.find + values.includes per regex match -> Map<attr, Set<values>>. Bench: 6x at K=V=60 in the 'mobileSelectorPerformanceOptimizer'. Each defect ships: ticket, patch with complexity-gate header, Python benchmark + correctness test, Makefile, outreach brief. All 16 tests pass. UNDF IDs: 1276 (playwright), 1277 (selenium-0001), 1288 (selenium-0002), 1289 (webdriverio).
123 lines
4.5 KiB
Python
123 lines
4.5 KiB
Python
#!/usr/bin/env python3
|
|
# UNDF: UNDF-2026-000001277 (selenium-0001),
|
|
# UNDF-2026-000001288 (selenium-0002)
|
|
#
|
|
# CWE-407: Algorithmic Complexity
|
|
#
|
|
# Defects:
|
|
# selenium-0001: SessionCapabilitiesMutator.mergeChromiumOptions /
|
|
# mergeFirefoxOptions dedup args+extensions via
|
|
# List.contains inside forEach -> O(N*M) per session.
|
|
# selenium-0002: ChromiumOptions.mergeInPlace and mergeInOptionsFromCaps
|
|
# apply the same list.contains dedup pattern across four
|
|
# merge loops, giving O(N*M) per merge.
|
|
#
|
|
# Fixes:
|
|
# selenium-0001: Pre-build a LinkedHashSet from stereotype args/extensions
|
|
# once, then iterate incoming with set.add() semantics.
|
|
# Order preserved, cost drops to O(N+M).
|
|
# selenium-0002: Helpers addArgumentsUnique / addEncodedExtensionsUnique
|
|
# consolidate the four merge loops behind a HashSet-backed
|
|
# dedup. Cost drops to O(N+M) per call.
|
|
#
|
|
# Complexity gates (from bench/results.txt on this machine):
|
|
# selenium-0001: N=M=1000 defective=24.7ms, fixed=0.13ms. Fixed must
|
|
# complete in <5ms. k-scaling: time(5x) / time(1x) < 17.5x.
|
|
# selenium-0002: N=M=1000 defective=121.9ms, fixed=0.48ms. Fixed must
|
|
# complete in <5ms. k-scaling: time(5x) / time(1x) < 17.5x.
|
|
|
|
import os
|
|
import sys
|
|
import unittest
|
|
|
|
HERE = os.path.dirname(os.path.abspath(__file__))
|
|
BENCH = os.path.join(os.path.dirname(HERE), "bench")
|
|
sys.path.insert(0, BENCH)
|
|
|
|
import importlib.util
|
|
|
|
|
|
def _load(fname):
|
|
path = os.path.join(BENCH, fname)
|
|
spec = importlib.util.spec_from_file_location(fname, path)
|
|
mod = importlib.util.module_from_spec(spec)
|
|
spec.loader.exec_module(mod)
|
|
return mod
|
|
|
|
|
|
_mod_0001 = _load("bench-selenium-0001.py")
|
|
_mod_0002 = _load("bench-selenium-0002.py")
|
|
|
|
|
|
# ---------------------------------------------------------------------------
|
|
# Correctness: fix must produce the same merged list as the defective version.
|
|
# ---------------------------------------------------------------------------
|
|
|
|
def _merge_defective(stereotype, incoming):
|
|
result = list(stereotype)
|
|
for arg in incoming:
|
|
if arg not in result:
|
|
result.append(arg)
|
|
return result
|
|
|
|
|
|
def _merge_fixed(stereotype, incoming):
|
|
result = list(stereotype)
|
|
seen = set(result)
|
|
for arg in incoming:
|
|
if arg not in seen:
|
|
seen.add(arg)
|
|
result.append(arg)
|
|
return result
|
|
|
|
|
|
class TestSelenium0001Correctness(unittest.TestCase):
|
|
def test_merge_empty_stereotype(self):
|
|
self.assertEqual(
|
|
_merge_fixed([], ["--a", "--b", "--a"]),
|
|
_merge_defective([], ["--a", "--b", "--a"]),
|
|
)
|
|
|
|
def test_merge_overlapping(self):
|
|
stereo = ["--x", "--y"]
|
|
inc = ["--y", "--z", "--x", "--w"]
|
|
self.assertEqual(_merge_fixed(stereo, inc), _merge_defective(stereo, inc))
|
|
|
|
def test_merge_order_preserved(self):
|
|
stereo = ["--a", "--b", "--c"]
|
|
inc = ["--d", "--e"]
|
|
fixed = _merge_fixed(stereo, inc)
|
|
self.assertEqual(fixed, ["--a", "--b", "--c", "--d", "--e"])
|
|
|
|
|
|
class TestSelenium0001ComplexityGate(unittest.TestCase):
|
|
def test_fixed_wallclock_N1000(self):
|
|
t_s = _mod_0001.bench_fixed(1000, 1000)
|
|
self.assertLess(t_s * 1000, 5.0,
|
|
f"fixed took {t_s*1000:.3f}ms at N=M=1000, expected <5ms")
|
|
|
|
def test_fixed_scaling_linear(self):
|
|
t_100 = min(_mod_0001.bench_fixed(100, 100) for _ in range(3))
|
|
t_500 = min(_mod_0001.bench_fixed(500, 500) for _ in range(3))
|
|
# Ensure fixed scales ~linearly: 5x input should cost <17.5x (not 25x)
|
|
ratio = t_500 / t_100 if t_100 > 0 else float("inf")
|
|
self.assertLess(ratio, 17.5,
|
|
f"fixed N=500/N=100 ratio {ratio:.2f}x, expected <17.5x (O(N))")
|
|
|
|
|
|
class TestSelenium0002ComplexityGate(unittest.TestCase):
|
|
def test_fixed_wallclock_N1000(self):
|
|
t_s = _mod_0002.bench_fixed(1000, 1000)
|
|
self.assertLess(t_s * 1000, 5.0,
|
|
f"fixed took {t_s*1000:.3f}ms at N=M=1000, expected <5ms")
|
|
|
|
def test_fixed_scaling_linear(self):
|
|
t_100 = min(_mod_0002.bench_fixed(100, 100) for _ in range(3))
|
|
t_500 = min(_mod_0002.bench_fixed(500, 500) for _ in range(3))
|
|
ratio = t_500 / t_100 if t_100 > 0 else float("inf")
|
|
self.assertLess(ratio, 17.5,
|
|
f"fixed N=500/N=100 ratio {ratio:.2f}x, expected <17.5x (O(N))")
|
|
|
|
|
|
if __name__ == "__main__":
|
|
unittest.main(verbosity=2)
|