Build1 publisher3 min readPublished
A 1000ms timeout in an isolated worker decides which ReDoS warnings survive
A dev.to post describes a ReDoS scanner that builds the string which hangs each flagged regex, times it at growing input sizes in a worker, and reports only the patterns that measurably blow up.
The Engineer · Build desk
What happened
- A dependency-free parser turns each JavaScript regex into an AST and flags three families: nested quantifiers, quantified alternation with overlapping branches, and adjacent or overlapping quantifiers.
- For each candidate the tool builds an attack string in three parts: a prefix that reaches the loop, a pumped core of repeats the loop accepts, and one trailing character that forces the match to fail.
- It then times the pattern at growing input sizes in an isolated worker, and the published run shows a 27-character proof input hanging past 1000ms with the curve starting at 11 characters.
- Patterns the static pass flagged that never blow up on a reachable input are dropped from the report rather than reported with a lower confidence.
Compiled by The EngineerSomething wrong?How this is made
Why it matters
- capability The finding arrives with a string a reviewer can paste into the test suite, so the bug closes with a failing test instead of a suppression comment.
- constraint Machine speed and runner load now decide which warnings print, because the verdict is a wall-clock measurement.
- decision Anyone adopting this has to decide what an empty report means: safe, or merely unmeasured on the hardware that ran the scan.
- cost Confirmation costs wall-clock time on purpose, roughly a second of hung probe per vulnerable pattern plus the faster sizes below it, and that budget lands in whatever job runs the scan.
A backtracking engine stops the instant it finds a match [12], so an input the pattern accepts tells you nothing about the worst case. In `/^(a+)+$/` fed 26 `a`s and a `!`, the `!` can never match `$`, so the engine has to try every way of splitting those 26 `a`s between the inner `a+` and the outer group before it gives up [5]. The post counts that as 2^n partitions [5]. At n=26 the count is 67,108,864 [23]. Four more `a`s multiply it by sixteen, so a pattern the author measured at over a second at 26 characters would run roughly sixteen seconds at 30 on the same laptop, under the post's own model [6][24].
Get the prefix wrong and a genuinely vulnerable pattern looks safe [13]. The loop inside `<([a-z]+)([^>]*)*>` is only reachable when the input starts with `<` [15], so the generator has to replay the required tokens ahead of the loop before it pumps anything [11]. The author wrote that two of the trickiest false negatives fixed in the engine were probing only the first inner loop instead of all of them, and failing to reach a loop that sat mid-pattern [14]. Sensitivity comes from the witness generator.
Static ambiguity analysis flags patterns whose damage is bounded by a required token elsewhere in the expression, and those are the false positives [7]. "A warning you can't trust gets ignored," the author wrote [8]. The dynamic step exists to remove them: "That's how you kill the false positives: make the engine prove it to itself," he wrote [19]. The candidate arrives with the sub-node responsible attached. That is what lets the generator aim the pump at a specific loop [10].
Three conditions have to hold for the measured verdict to mean anything on your build. The engine has to be the same, since the parser targets JavaScript patterns [9]. The machine has to be no faster at backtracking than the author's laptop [6]. And the runner has to be idle enough that a one-second cutoff means what it says [16]. Miss the last one and the failure mode inverts: on a faster or quieter box, a pattern that hung at 1100ms returns in 900ms and leaves the report entirely, because unconfirmed candidates are dropped [18].
The introduction also promises a rewrite the tool has verified still matches the same strings [2]. The text supplied breaks off at "Finding the bug is half the job. The tool also" [22], so the equivalence check behind that promise is asserted and not shown. What is shown runs with no dependencies and entirely offline [2][9]. A build box with no network egress can run it.
What to watch
- Whether the repository publishes the equivalence check used to verify that a suggested rewrite matches the same language as the original.
- Whether the hard timeout and the probe sizes are configurable, since the cutoff is what decides the report.
- Whether the candidate set grows beyond the three families the parser currently walks.