Napoleon's Pixelated Mugshot

    redos-detector
    TypeScript icon, indicating that this package has built-in type declarations

    3.2.1 • Public • Published

    redos-detector

    A CLI and library which tests with certainty if a regex pattern is safe from ReDoS attacks. Supported in the browser, Node and Deno.

    By default it considers a pattern unsafe if there are potentially more than 200 backtracks possible.

    There are some cases where it may report a pattern as unsafe when in reality it's safe, but it should never report a pattern as safe when it is not.

    Note that this tool checks patterns that are expected to run using an engine that implements the ECMA-262 (JS) standard. If your pattern will be run in a different engine please be aware the result given here could be incorrect due to differences in engine behaviour.

    Demo

    https://redosdetector.com/ [Source]

    Examples

    Good

    isSafe(/^([a-c]*)d([a-c]*)$/).safe === true;

    Demo

    because for any given input string this can only match in one way, or not match.

    Bad

    isSafe(/^([a-b]*)([a-c]*)$/).safe === false;

    Demo

    because the input a could match in both places. The input ax could result in both being tried.

    The CLI would output the following for this:

    Regex is not safe. There could be infinite backtracks.
    
    The following trails show how the same input can be matched multiple ways.
    2: `[a-b]` | 10: `[a-c]`
    ========================
     2: `[a-b]` | 10: `[a-c]`
    10: `[a-c]` | 10: `[a-c]`
    =========================
     2: `[a-b]` | 10: `[a-c]`
    10: `[a-c]` | 10: `[a-c]`
    10: `[a-c]` | 10: `[a-c]`
    =========================
    2: `[a-b]` | 10: `[a-c]`
    2: `[a-b]` | 10: `[a-c]`
    ========================
    
    Hit maximum number of backtracks so there may be more results than shown here.
    Note there may be more results than shown here as some infinite loops are detected and removed.
    

    The first result means you could have a match where given the same input string, [a-c] takes a character (at position 10), or [a-b] takes a character (at position 2).

    Note this could be made good again by making the first group atomic. Atomic groups are not supported directly right now, but can be inferred using a pattern like ^(?=([a-b]*))\1([a-c]*)$ (Demo).

    isSafe(/^(a|a)+$/).safe === false;

    Demo

    is bad because in the group a could match on both sides. The input aaaaaax could result in many combinations being tried.

    How does it work?

    This tool will generate all the combinations of input strings that would match the pattern, and will output any input string that could match the pattern in multiple ways.

    Usage

    This can be used via the CLI, or as a library. It's on npm.

    There's also an ESLint plugin "eslint-plugin-redos-detector".

    Result Structure

    The following is the structure of the result you will get from both isSafe, isSafePattern and the CLI with the --json flag.

    Root

    type Root = {
      safe: boolean;
      error:
        | null
        | 'hitMaxBacktracks'
        | 'hitMaxSteps'
        | 'stackOverflow'
        | 'timedOut';
      trails: Trail[];
      patternDowngraded: boolean;
      pattern: string;
      worstCaseBacktrackCount:
        | {
            infinite: true;
          }
        | {
            infinite: false;
            value: number;
          };
    };

    Trail

    type Trail = {
      trail: {
        a: Side;
        b: Side;
      }[];
    };

    Side

    type Side = {
      backreferenceStack: {
        index: number;
        node: Node;
      }[];
      node: Node;
      quantifierIterations: {
        iteration: number;
        node: Node;
      }[];
    };

    Node

    type Node = {
      start: Location;
      end: Location;
      source: string;
    };

    Location

    type Location = {
      offset: number;
    };

    Options

    The following options exist for both the library and CLI:

    • unicode: Enable unicode mode. (Default: false)
    • maxBacktracks: If worst case count of possible backtracks is above this number, the regex will be considered unsafe. (Default: 200)
    • maxSteps: The maximum number of steps to make. Every time a new node is read from the pattern this counts as one step. If this limit is hit error will be hitMaxSteps. (Default: 20000)
    • timeout: The maximum amount of time (ms) to spend processing. Once this time is passed the trails found so far will be returned, and the error will be timeout. (Default: Infinity)
    • downgradePattern: Automatically downgrade the pattern if it's not supported as is. If this happens patternDowngraded will be true and pattern will contain the downgraded version. An exception may be thrown if the pattern needed to be downgraded and it wasn't. (Default: true)

    Note it's possible for there to be a infinite number of results, so you should probably make sure at least one of the maxSteps and timeout options is set to a finite number.

    CLI

    $ npx redos-detector check "<regex pattern>" (--unicode) (--maxBacktracks <number>) (--maxSteps <number>) (--timeout <number>) (--alwaysIncludeTrails) (--disableDowngrade) (--resultsLimit <number>) (--json)

    to run on the fly or

    $ npm i -g redos-detector

    to make the command available globally as redos-detector.

    By default this will output the result in a text format, and the exit status will be 0 if the pattern is safe, otherwise non-0. You should not try and parse this text output as it may change between any version.

    Only the first 15 results will be shown in the text output, but this can be changed with the --resultsLimit option. This option is ignored with --json.

    The --json option will result in JSON being outputted containing more information. The structure of this will follow semantic versioning. When this option is used the exit status will always be 0 (unless an exception occurred), so you should always check the safe property to determine if the pattern is safe.

    Library

    $ npm install redos-detector

    The following functions are provided:

    • isSafe(regexp: RegExp, options?: { maxBacktracks?: number, maxSteps?: number, timeout?: number, downgradePattern?: boolean }): This takes a RegExp. Currently the only supported flag is u.
    • isSafePattern(pattern: string, options?: { maxBacktracks?: number, maxSteps?: number, timeout?: number, downgradePattern?: boolean, unicode?: boolean }): This takes just the pattern as a string. E.g. a*.
    • downgradePattern(input: { pattern: string, unicode: boolean }: This downgrades the provided pattern to one which is supported. You won't need to use this unless you set the downgradePattern option to false.

    Useful Resources

    Here are some great resources, which I found super helpful when building this.

    Install

    npm i redos-detector

    DownloadsWeekly Downloads

    236

    Version

    3.2.1

    License

    MIT

    Unpacked Size

    699 kB

    Total Files

    45

    Last publish

    Collaborators

    • tjenkinson