Beagle SCM

JS-070 MED: untrusted regex compiled/run per-line with no ReDoS guard

views/spot/match.js's regexMatcher compiles new RegExp(jsBody) from the user URI fragment, then runs re.exec per line over every candidate file behind the regex: VIEW. The only ceiling is a whole-file 16 MiB gate — no per-line length cap and no time/step budget — so (a+)+$ against a long line hangs the single-threaded runtime. Native used a Thompson NFA (linear), so this is also a parity divergence; matchFlat (the spot backtracker) likewise has no guard. Method: Issues.

Input

Context

• views/regex/regex.js:1-6 — the regex: verb is one line; it just

  module.exports = require("../spot/search.js"), riding the shared scaffold.

• views/spot/match.js:47 re = new RegExp(jsBody) where :45

  jsBody = body.replace(…) and body is the user URI fragment — untrusted, backtracking JS-RegExp (catastrophic for (a+)+$).

• :50-66 run(): splitLinesBytes then re.exec(lineText) per line, per

  file — no per-line length cap, no step/time budget.

• Only ceiling: views/spot/search.js:273-274 whole-file SPOTBIG gate

  if (bytes.length >= (1<<24)) return (16 MiB) — does NOT bound a single long line's backtracking.

• Parity: the comment :8 :37-40 notes native walked a Thompson NFA

  (NFAu8Search, linear); the JS RegExp diverges on adversarial input.

• views/spot/match.js:158 matchFlat — recursive backtracker

  (:222 :243 :269 :311 :329 :376 recurse with no depth/step guard), so the structural spot mode is exposed to the same blowup.

Goals

• A regex: (and spot:) search over a hostile file cannot wedge the runtime:

  a per-line length cap and/or a step/time budget bounds the work.

• A repro test: regex:(a+)+$ (or spot analogue) over a long single-line

  file completes within a wall-clock budget instead of hanging.

Constraints

• Pure JS, rides views/spot/search.js; keep the {,m}→{0,m} dialect

  rewrite (:45) and the per-line first-match byte-span behavior.

• Stay a faithful subset of native (grep_match_span); don't regress the

  parity corpus. Scope: regexMatcher/matchFlat guards (+ a size cap).

WIP

Design decisions

• Add a per-line byte cap (skip / truncate over-long lines) plus a step or

  wall-clock budget around re.exec; on overflow treat the line as no-match.

• Minimum bar: reject nested unbounded quantifiers ((a+)+, (a*)*) at

  compile time so the worst exponentials never run.

• Add a step-counter guard to matchFlat (bail → no-match on overflow);

  longer-term, port the bounded Thompson NFA for true linear parity.

TODOs

• Repro-first test/js/regex/* (+ spot): regex:(a+)+$ over a long

  single-line file hangs today; assert it returns within a budget.

• Add the per-line cap + step/time budget (and nested-quantifier reject)

  to regexMatcher; add the step guard to matchFlat.

Blockers and bummers

• No preemption in the JS runtime → a step COUNTER (not a wall clock) is the

  portable budget; pick a bound that keeps the parity corpus green.

• 2026-07-07 audit: STILL OPEN — views/spot/match.js:47 re = new RegExp(jsBody) from the

  untrusted URI fragment, no per-line cap / step budget; matchFlat:158 is still the uncapped recursive backtracker. Only ceiling remains the whole-file SPOTBIG gate in search.js.

Outcome

• (pending)