polynomial-redos: Missing ^ Made a Trim Regex O(n^2)

The short version

A regex that trims a string but is anchored only at the end with $, with no ^ at the start, lets the search for a match’s start position and the quantifier’s backtracking compound into O(n^2) time on certain inputs. CodeQL’s js/polynomial-redos flags this as severity: high.

What it looks like

CodeQL flagged js/polynomial-redos (high) on a single line written to strip trailing slashes:

const trimmed = base.replace(/\/+$/, "");

And it wasn’t a single finding. The same line had been copy-pasted into three different functions in the same file, and CodeQL raised the identical finding at all three spots. Nothing was failing at runtime — this was static analysis pointing out that the pattern could become dangerous, while the code kept working fine in practice.

Findings like this get dismissed as “probably a false positive” more often than not. This one wasn’t: the regex itself genuinely had room to blow up to O(n^2).

Why

\/+$ reads as “one or more slashes followed by the end of the string.” Anchoring it with $ makes it look safe at a glance. But nothing pins down the start position the match is attempted from — there’s no ^.

String.prototype.replace retries a failing regex by advancing the start position one character at a time. Without ^, \/+$ is free to ask, from any position in the string, “does a run of slashes reach the end starting here?”

Feed it an input shaped like “many slashes followed by a single non-slash character” (say, $n$ slashes followed by one arbitrary character), and every start position ultimately fails to match because of that trailing character. But before each failure is confirmed, the engine backtracks: at each start position it retries the $ match while shedding slashes consumed by + one at a time. The number of candidate start positions scales with the string length, and so does the number of backtracking attempts at each one — multiply the two and you get O(n^2) overall. That’s exactly what CodeQL’s js/polynomial-redos was flagging.

The code itself lived in a seed script that reads a base URL from an environment variable, and only operators could set that variable. But js/polynomial-redos is a rule that tracks whether externally controllable values flow into a regex, and it treats environment variables and CLI arguments as tracked entry points. It has no way to account for the operational fact that only operators can reach that entry point, so it’s flagged severity: high regardless.

Fixing it

We dropped the regex and replaced it with a linear loop that walks back from the end of the string, trimming characters until it hits one that isn’t a slash:

function stripTrailingSlashes(s: string): string {
  let end = s.length;
  while (end > 0 && s.charCodeAt(end - 1) === 47 /* '/' */) {
    end -= 1;
  }
  return s.slice(0, end);
}

Walking backward with charCodeAt means there’s no start-position search and no backtracking — it always finishes in a number of steps proportional to the string length, O(n). All three call sites were switched to this function, and the behavior itself — “strip every trailing slash” — didn’t change.

Preventing a repeat

All three spots shared the same shape — no leading anchor, a quantifier bounded only by a trailing anchor — because the same line had been copied across three functions, so the same bug spread to all three at once. A trailing $ doesn’t make a regex safe by itself.

There are broadly three ways to avoid this flavor of O(n^2) in a regex with a quantifier: (1) pin the start too with ^, which eliminates the start-position search entirely — though that changes the match semantics and doesn’t work for a case like this one, where you want to strip a trailing run of slashes wherever it happens to end the string; (2) bound the quantifier, e.g. {1,64} instead of +, capping the backtracking attempts per start position at a constant — effectively the only option left when you can’t fix the start position, such as scanning with a global /g regex; (3) skip the regex and write a scan instead. We picked (3) here since it let us keep the behavior identical.

The same approach used for this fix — checking for the same shape (no leading anchor, a quantifier, only a trailing anchor) — can be used to find other copies of this pattern elsewhere. Keep in mind that js/polynomial-redos tracks where the input comes from, so an identical-looking regex won’t get flagged if no externally controllable value reaches it. When a static analysis tool raises the same finding in multiple places at once, it’s worth checking whether they all trace back to the same copied source before fixing just one and moving on.