java-topology/docs/tickets/selenium-0001-grid-session-mutator-list-contains.md

selenium-0001: SessionCapabilitiesMutator — O(N×M) args/extensions dedup per session

Target: SeleniumHQ/selenium Severity: MEDIUM-HIGH CWE: CWE-407 (Inefficient Algorithmic Complexity) MOAD: MOAD-0001 (A Sedimentary Defect) File: java/src/org/openqa/selenium/grid/node/config/SessionCapabilitiesMutator.java:136-141, 154-159, 194-199 Language: Java Status: open

Description

Selenium Grid Node runs SessionCapabilitiesMutator on every incoming session creation request. It merges the node's slot stereotype capabilities with the client-requested capabilities. For the Chromium and Firefox merge paths, the args and extensions arrays are deduplicated via List.contains inside a forEach loop, giving O(N×M) where N is the client args/extensions count and M is the stereotype's existing arg/extension count.

A Grid hub handling N parallel sessions per second pays this cost N times per second. On CI farms running large Chrome arg lists (20–50 flags plus an extension profile), the per-session cost compounds.

Root Cause

// SessionCapabilitiesMutator.java:120-142  mergeChromiumOptions
for (Map.Entry<String, Object> entry : capsOptions.entrySet()) {
  String name = entry.getKey();
  Object value = entry.getValue();
  if (name.equals("args")) {
    List<String> arguments = new ArrayList<>((List<String>) value);
    List<String> stereotypeArguments =
        new ArrayList<>(
            (List<String>) (stereotypeOptions.getOrDefault(("args"), new ArrayList<>())));

    arguments.forEach(
        arg -> {
          if (!stereotypeArguments.contains(arg)) {   // O(M) scan per arg
            stereotypeArguments.add(arg);
          }
        });
    toReturn.put("args", stereotypeArguments);
  }

  if (name.equals("extensions")) {
    // same pattern for extensions (lines 154-159)
    ...
    extensionList.forEach(
        extension -> {
          if (!stereotypeExtensions.contains(extension)) {   // O(M) scan per extension
            stereotypeExtensions.add(extension);
          }
        });
    ...
  }
}

// mergeFirefoxOptions (lines 194-199): identical pattern for args

ArrayList.contains() is O(M). Called inside forEach(List) of size N, total cost is O(N×M) per session per merged list (args and extensions both).

Fix

Build a LinkedHashSet once from the stereotype list (preserves order, O(1) lookup), then iterate the client list and add only new items. Writes the final list back from the set via new ArrayList<>(set).

Set<String> stereotypeArgSet = new LinkedHashSet<>(stereotypeArguments);
for (String arg : arguments) {
  if (stereotypeArgSet.add(arg)) {
    stereotypeArguments.add(arg);
  }
}

Cost becomes O(N+M): one Set build + N Set lookups with amortized O(1) add. Semantics preserved: LinkedHashSet preserves insertion order matching the original ArrayList.contains-based dedup, and Set.add returns true only on first insertion, matching the original if-not-contains-then-add guard.

Severity Note

Affects every session-creation request routed through a Grid Node. Impact grows linearly with session throughput and with the size of Chrome flag lists. Typical production CI farms handle 10–100 sessions/sec with 20–50 args per session, giving a measurable but non-critical wall-clock cost. Greatest benefit accrues to large enterprises running Selenium Grid at scale.

Complexity Gate

• N=M=20: fixed must complete in <1ms per session
• k-scaling 5×: time ratio must be <17.5× (O(k) ≈5×, not O(k²) ≈25×)