Skip to content
Logo

Safe by default

A backtracking regex engine, which is what JavaScript and most languages' built-in regex engines are, can take exponential time on a pattern that matches the same input in many ways. (?:\w+| )* is one: on a long run of letters followed by a character it can't match, the engine tries every way of splitting the letters into words before it gives up. Wherever the input is untrusted, that's a denial-of-service risk, called ReDoS.

toPattern and toRegExp analyze every pattern before returning it. With the default configuration, they throw VulnerablePatternError rather than return one that can take superlinear time:

import {
  ,
  ,
  ,
  ,
  ,
  ,
  ,
  ,
} from "@ghostry/aster";
 
const { ,  } = ();
 
const  = ()
  .("word", () => (("a", "z")))
  .("text", ({  }) => ((, (" "))))
  .();
 
try {
  (, "text");
} catch () {
  if ( instanceof .) {
    ..; // "exponential"
  }
}

The error's message says which rule is ambiguous, gives an input that shows it, and lists the ways out.

Analyze without throwing

analyze(grammar, rule, options) reports how slow a pattern can be, and never throws for a slow one:

analyze(words, "text");
// {
//   complexity: "exponential",
//   rule: "text",
//   attack: { prefix: "a", pump: "aa", suffix: "!" },
//   exact: true,
// }
  • complexity is "linear", "polynomial" (with a degree), or "exponential".
  • rule is the innermost named rule that holds the ambiguity, which is where to rewrite.
  • attack is an input that drives the worst case: prefix, then pump repeated, then suffix. Each repetition of an exponential pattern's pump doubles the engine's work.
  • exact says whether the finding is exact. See Large patterns.

A linear result is just { complexity: "linear" }.

Fixing a slow rule

A pattern is slow when some input can be split more than one way. Rewrite the rule so every input has one reading. Here, words separated by single spaces:

const sentence = grammar()
  .define("word", () => oneOrMore(range("a", "z")))
  .define("text", ({ word }) =>
    sequence([word, zeroOrMore(sequence([literal(" "), word]))]),
  )
  .compose();
 
toPattern(sentence, "text"); // "^[a-z]+(?: [a-z]+)*$"
analyze(sentence, "text"); // { complexity: "linear" }

If you only need to read the input, not validate it with a regex, use the parser. It runs in linear time for every grammar, including ones whose regex toPattern refuses.

Searches

The analysis accounts for the engine stopping at the first match it finds. A search (anchored: false) stops at its first match, so the same rule can be slow anchored and fast as a search. The ambiguous words grammar above is one:

analyze(words, "text", { anchored: false }); // { complexity: "linear" }

Here every input has a match at its first offset, even if it's empty, so the engine never has to try every split.

It works the other way too. A search retries at every offset, so unanchored a*b is quadratic, though anchored it's linear.

Allowing slower patterns

Configure the instance to accept more:

initialize({ allowedComplexity: "polynomial" }); // rejects only exponential patterns
initialize({ allowedComplexity: "exponential" }); // accepts every pattern

allowedComplexity is the slowest pattern toPattern and toRegExp return. A value it doesn't know throws InvalidConfigError, so a typo can't turn the check off.

Large patterns

The analysis runs in two passes. The first assumes every path through the pattern fails, so it never misses a slow pattern, and most patterns are proven linear there. When it finds something, a second, exact pass works out where the engine would stop at a match.

The exact pass can need exponentially many steps for a few patterns. analysisBudget bounds it, at 1,000,000 steps by default, about half a second. Past the budget, the first pass's finding stands, with exact: false. That finding never misses a slow pattern, but it can flag one that a real engine always finishes quickly.

initialize({ analysisBudget: 0 }); // never run the exact pass
initialize({ analysisBudget: Infinity }); // never fall back

Each instance caches its analyses per composed grammar, so asking for the same rule's pattern twice analyzes it once.