Repository: ota-meshi/eslint-plugin-regexp
Pull request #246 (2021-06-13 13:11:43)

Add `no-super-linear-move` rule
This is the other rule I wanted to add, as mention in #242.

This one detects super-linear runtime caused by moves, not backtracking. 

The detected cases are actually really hard to fix, so this rule isn't auto-fixable. But I added an explanation of 3 fixing strategies in the docs to compensate.


Patch:
diff --git a/README.md b/README.md
index ccb6566..0f55646 100644
--- a/README.md
+++ b/README.md
@@ -110,6 +110,7 @@ The rules with the following star :star: are included in the `plugin:regexp/reco
 | [regexp/no-optional-assertion](https://ota-meshi.github.io/eslint-plugin-regexp/rules/no-optional-assertion.html) | disallow optional assertions |  |
 | [regexp/no-potentially-useless-backreference](https://ota-meshi.github.io/eslint-plugin-regexp/rules/no-potentially-useless-backreference.html) | disallow backreferences that reference a group that might not be matched |  |
 | [regexp/no-super-linear-backtracking](https://ota-meshi.github.io/eslint-plugin-regexp/rules/no-super-linear-backtracking.html) | disallow exponential and polynomial backtracking | :wrench: |
+| [regexp/no-super-linear-move](https://ota-meshi.github.io/eslint-plugin-regexp/rules/no-super-linear-move.html) | disallow quantifiers that cause quadratic moves |  |
 | [regexp/no-useless-assertions](https://ota-meshi.github.io/eslint-plugin-regexp/rules/no-useless-assertions.html) | disallow assertions that are known to always accept (or reject) |  |
 | [regexp/no-useless-backreference](https://ota-meshi.github.io/eslint-plugin-regexp/rules/no-useless-backreference.html) | disallow useless backreferences in regular expressions | :star: |
 | [regexp/no-useless-dollar-replacements](https://ota-meshi.github.io/eslint-plugin-regexp/rules/no-useless-dollar-replacements.html) | disallow useless `$` replacements in replacement string |  |
diff --git a/docs/rules/README.md b/docs/rules/README.md
index 6bd65ca..ee472b3 100644
--- a/docs/rules/README.md
+++ b/docs/rules/README.md
@@ -24,6 +24,7 @@ The rules with the following star :star: are included in the `plugin:regexp/reco
 | [regexp/no-optional-assertion](./no-optional-assertion.md) | disallow optional assertions |  |
 | [regexp/no-potentially-useless-backreference](./no-potentially-useless-backreference.md) | disallow backreferences that reference a group that might not be matched |  |
 | [regexp/no-super-linear-backtracking](./no-super-linear-backtracking.md) | disallow exponential and polynomial backtracking | :wrench: |
+| [regexp/no-super-linear-move](./no-super-linear-move.md) | disallow quantifiers that cause quadratic moves |  |
 | [regexp/no-useless-assertions](./no-useless-assertions.md) | disallow assertions that are known to always accept (or reject) |  |
 | [regexp/no-useless-backreference](./no-useless-backreference.md) | disallow useless backreferences in regular expressions | :star: |
 | [regexp/no-useless-dollar-replacements](./no-useless-dollar-replacements.md) | disallow useless `$` replacements in replacement string |  |
diff --git a/docs/rules/no-super-linear-move.md b/docs/rules/no-super-linear-move.md
new file mode 100644
index 0000000..fd2908b
--- /dev/null
+++ b/docs/rules/no-super-linear-move.md
@@ -0,0 +1,214 @@
+---
+pageClass: "rule-details"
+sidebarDepth: 0
+title: "regexp/no-super-linear-move"
+description: "disallow quantifiers that cause quadratic moves"
+---
+# regexp/no-super-linear-move
+
+> disallow quantifiers that cause quadratic moves
+
+- :exclamation: <badge text="This rule has not been released yet." vertical="middle" type="error"> ***This rule has not been released yet.*** </badge>
+
+## :book: Rule Details
+
+This rule reports super-linear worst-case runtime caused by a regex being moved across the input string. The reported cases are a problem because the super-linear worst-case runtime can be exploited by attackers in what is called [Regular expression Denial of Service - ReDoS][1].
+
+<eslint-code-block>
+
+```js
+/* eslint regexp/no-super-linear-move: "error" */
+
+/* ✓ GOOD */
+var foo = /abc|def/;
+var foo = /\ba+b/;
+var foo = /^\s*foo:/;
+var foo = /ab+/;
+var foo = /#.*/;
+
+/* ✗ BAD */
+var foo = /a+b/;
+var foo = /^\s*foo:/m;
+var foo = /<.*?>/;
+```
+
+</eslint-code-block>
+
+### Background
+
+Regexes are often used to find text of within a string (e.g. `/abc/.exec("123 abc def")`). The position of the matching text is unknown and has to be determined by the regex engine. In practice, the regex engine will move the regex across the input string character by character. While there are many optimizations to skip parts of the input string, there will still be _O(n)_ possible positions. If there is no text matching the regex in the input string, then all _O(n)_ positions will be checked.
+
+This is not problem in it self, _O(n)_ is expected for linear string searching algorithms.
+
+Problems arise when the regex itself takes more than _O(1)_ steps (on average) to reject any position within the input.
+
+Example: The regex `/^a+b/` takes _O(n)_ steps to find no match in an input of _n_-many `a`s. However, the regex `/a+b/` (no assertion) takes _O(n)_ steps to find no match in the same input at position 0. It will take another _O(n-1)_ steps at position 1, another _O(n-2)_ steps at position 2, and so on. In total, `/a+b/` will take _O(n^2)_ steps to find no match in an input of _n_-many `a`s.
+
+If a regex is moved across the string and takes _O(n)_ steps (on average) to reject each of the _O(n)_ possible positions, then it will reject the input string in _O(n^2)_ steps.
+
+### Possible fixes
+
+There are multiple ways to fix this kind of super-linear runtime.
+
+However, there is no one-site-fits-all solution. Adequate testing and code review are necessary to ensure that the fixed regex is still correct.
+
+#### Change the quantifier
+
+If the quantifier is preceded by an assertion, the quantifier might be too broad (= accept too many characters). Narrowing down the quantifier might fix the issue.
+
+Example: `/^\s*(\w+)\s*[:=]/m`
+
+This is a simple regex to find keys in a config file. Keys must be at the start of a line and may be surrounded by whitespace characters.
+
+This rule says that the first `\s*` causes quadratic runtime for "any attack string `/[\n\r\u2028\u2029]+/`."
+
+The problem with `\s*` is that `\s` also allows line break characters (the characters in the attack string). `^` already ensures the "start of a line" requirement, so there is no reason to allow line breaks after the `^`.
+
+The fix is to remove all line break characters from `\s`. This is difficult, so let's cheat a little and say that only spaces and tabs (`[\t ]`) are allows to surround the key.
+
+<eslint-code-block>
+
+```js
+/* eslint regexp/no-super-linear-move: "error" */
+
+/* ✗ BAD */
+var example = /^\s*(\w+)\s*[:=]/m
+
+/* ✓ FIXED */
+var fix = /^[\t ]*(\w+)[\t ]*[:=]/m
+```
+
+</eslint-code-block>
+
+#### Limit the quantifier
+
+All quantifiers reported by this rule are unbound (= maximum is infinite). This is because attackers need strings with a lengths >1000 character to exploit the quadratic runtime.
+
+If the quantifier simply stops searching after some maximum number of steps, the quantifier isn't exploitable.
+
+Note: The maximum of the quantifier should be reasonably small (typically <100). Choosing a large maximum (>1000) will cause the quantifier to be exploitable despite the limit.
+
+Example: `/((?:\\{2})*)(\\?)\|/g`
+
+This regex **was** used by [`minimatch`](https://github.com/isaacs/minimatch) to find escaped and unescaped `|` characters.
+
+This rule says that the `(?:\\{2})*` causes quadratic runtime for "any attack string `/(?:\\{2})+/`."
+
+The fix is to limit the `(?:\\{2})*` quantifier. `minimatch` limited it to at most 64 repetitions. You read more about this vulnerability [here](https://medium.com/node-security/minimatch-redos-vulnerability-590da24e6d3c).
+
+<eslint-code-block>
+
+```js
+/* eslint regexp/no-super-linear-move: "error" */
+
+/* ✗ BAD */
+var example = /((?:\\{2})*)(\\?)\|/g
+
+/* ✓ FIXED */
+var fix = /((?:\\{2}){0,64})(\\?)\|/g
+```
+
+</eslint-code-block>
+
+#### Add an assertion
+
+Adding a lookbehind, `\b`, or `^` assertion at the start of the pattern can solve a lot of issues.
+
+This fix is typically only applicable if the exploitable quantifier can consume exactly one character per iteration. Quantifiers that can consume more than character per iteration (e.g. `(?:abc)+`, `(?:ab?)+`) are very difficult to fix with this approach.
+
+Example: `/[a-z_][a-z_0-9]*(?=\s*\()/i`
+
+This is a simple regex to find the names of functions and function-like macros in a C program.
+
+This rule says that the first `[a-z_0-9]*` causes quadratic runtime for "any attack string `/[A-Z_]+/i`."
+
+The problem is that `[a-z_][a-z_0-9]*` isn't guaranteed to start at the start of the function name, the `[a-z_]` can also match anywhere inside the function name.
+
+The fix is to add an assertion to make sure that `[a-z_]` matches the first character of a name. We can use the lookbehind `(?<![a-z_0-9])` == `(?<!\w)`. In this case, it's also possible to use the built-in `\b` assertion.
+
+Note that using `(?<![a-z_])` is not enough. `(?<![a-z_])[a-z_]` can still match in the middle of the name for names with numbers (e.g. `str2int`). The lookbehind has to disallow the characters of the quantifier `[a-z_0-9]*`.
+
+<eslint-code-block>
+
+```js
+/* eslint regexp/no-super-linear-move: "error" */
+
+/* ✗ BAD */
+var example = /[a-z_][a-z_0-9]*(?=\s*\()/i
+
+/* ✓ FIXED */
+var fix1 = /(?<![a-z_0-9])[a-z_][a-z_0-9]*(?=\s*\()/i
+var fix2 = /(?<!\w)[a-z_][a-z_0-9]*(?=\s*\()/i
+var fix3 = /\b[a-z_][a-z_0-9]*(?=\s*\()/i
+```
+
+</eslint-code-block>
+
+### Limitations of this rule
+
+This rule implements a simple detection method. It is unable to find certain cases.
+
+This means that this rule might not be able to verify fixed regexes. This rule might be unable to detect that supposedly fixed regexes are actually still vulnerable.
+
+
+## :wrench: Options
+
+```json
+{
+  "regexp/no-super-linear-move": ["error", {
+    "report": "certain",
+    "ignoreSticky": false
+  }]
+}
+```
+
+### `report: "certain" | "potential"`
+
+This option has the same function as the [`report` option of `regexp/no-super-linear-backtracking`](./no-super-linear-backtracking.html#report). The default value is `"certain"`.
+
+### `ignoreSticky: boolean`
+
+By default, this rule ignores regexes with the sticky (`y`) flag. These regexes do not move across the input string on their own and they are mostly immune to this type of super-linear worst-case because of that. However, some algorithms (and even built-in JavaScript functions) manually move regexes across the string and others change the flags of regexes.
+
+This option determines whether this rule will ignore regexes with sticky (`y`) flag.
+
+- `ignoreSticky: true`  (_default_)
+
+  Regexes with the sticky (`y`) flag will be ignored.
+
+- `ignoreSticky: false`
+
+  All regexes will be analysed.
+
+### `ignorePartial: boolean`:
+
+Some regexes are used as fragments to build more complex regexes. Example:
+
+```js
+const fn = /\w+(?=\s*\()/.source;
+const pattern = RegExp(`#\\s*define\\s+${fn}`, "g");
+```
+
+Even if a fragment had exploitable quantifiers, it might not cause super-linear runtime depending on how the fragment is used.
+
+- `ignorePartial: true`  (_default_)
+
+  The rule does not check regexes used as a fragment. It assumes that fragments are used in a way such that super-linear runtime caused by moves is prevented.
+
+- `ignorePartial: false`
+
+  The rule checks all regexes regardless of how they are used.
+
+
+## :books: Further reading
+
+- [Regular expression Denial of Service - ReDoS][1]
+- [scslre]
+
+[1]: https://owasp.org/www-community/attacks/Regular_expression_Denial_of_Service_-_ReDoS
+[scslre]: https://github.com/RunDevelopment/scslre
+
+## :mag: Implementation
+
+- [Rule source](https://github.com/ota-meshi/eslint-plugin-regexp/blob/master/lib/rules/no-super-linear-move.ts)
+- [Test source](https://github.com/ota-meshi/eslint-plugin-regexp/blob/master/tests/lib/rules/no-super-linear-move.ts)
diff --git a/lib/rules/no-super-linear-move.ts b/lib/rules/no-super-linear-move.ts
new file mode 100644
index 0000000..d271764
--- /dev/null
+++ b/lib/rules/no-super-linear-move.ts
@@ -0,0 +1,355 @@
+import type { RegExpVisitor } from "regexpp/visitor"
+import type { Alternative, Pattern, Quantifier } from "regexpp/ast"
+import type { RegExpContext } from "../utils"
+import { createRule, defineRegexpVisitor } from "../utils"
+import { UsageOfPattern } from "../utils/get-usage-of-pattern"
+import type { ParsedLiteral } from "scslre"
+import { analyse } from "scslre"
+import type { Descendant } from "regexp-ast-analysis"
+import {
+    isPotentiallyEmpty,
+    getMatchingDirection,
+    getFirstConsumedCharAfter,
+} from "regexp-ast-analysis"
+import type { NoParentNode, Expression } from "refa"
+import {
+    visitAst,
+    JS,
+    transform,
+    combineTransformers,
+    Transformers,
+} from "refa"
+
+interface Report {
+    quant: Quantifier
+    attack: string
+}
+
+/**
+ * Create a parsed literal object as required by the scslre library.
+ */
+function getParsedLiteral(
+    context: RegExpContext,
+    ignoreSticky: boolean,
+): ParsedLiteral {
+    const { flags, flagsString, patternAst } = context
+
+    return {
+        pattern: patternAst,
+        flags: {
+            type: "Flags",
+            raw: flagsString ?? "",
+            parent: null,
+            start: NaN,
+            end: NaN,
+            dotAll: flags.dotAll ?? false,
+            global: flags.global ?? false,
+            ignoreCase: flags.ignoreCase ?? false,
+            multiline: flags.multiline ?? false,
+            sticky: !ignoreSticky && (flags.sticky ?? false),
+            unicode: flags.unicode ?? false,
+        },
+    }
+}
+
+/**
+ * Removes duplicates from the given reports.
+ */
+function dedupeReports(reports: Iterable<Report>): Report[] {
+    const seen = new Set<Quantifier>()
+    const result: Report[] = []
+
+    for (const r of reports) {
+        if (!seen.has(r.quant)) {
+            result.push(r)
+            seen.add(r.quant)
+        }
+    }
+
+    return result
+}
+
+/**
+ * Returns all quantifiers that are reachable from the start of the
+ * given node without consuming or asserting any characters.
+ */
+function* findReachableQuantifiers(
+    node: Descendant<Pattern> | Alternative,
+): Iterable<Quantifier> {
+    switch (node.type) {
+        case "CapturingGroup":
+        case "Group":
+        case "Pattern": {
+            for (const a of node.alternatives) {
+                yield* findReachableQuantifiers(a)
+            }
+            break
+        }
+
+        case "Assertion": {
+            if (node.kind === "lookahead" || node.kind === "lookbehind") {
+                for (const a of node.alternatives) {
+                    yield* findReachableQuantifiers(a)
+                }
+            }
+            break
+        }
+
+        case "Quantifier": {
+            yield node
+            break
+        }
+
+        case "Alternative": {
+            const dir = getMatchingDirection(node)
+            for (let i = 0; i < node.elements.length; i++) {
+                const elementIndex =
+                    dir === "ltr" ? i : node.elements.length - 1 - i
+                const element = node.elements[elementIndex]
+
+                yield* findReachableQuantifiers(element)
+
+                if (!isPotentiallyEmpty(element)) {
+                    break
+                }
+            }
+            break
+        }
+
+        default:
+            break
+    }
+}
+
+const TRANFORMER_OPTIONS: Transformers.CreationOptions = {
+    ignoreAmbiguity: true,
+    ignoreOrder: true,
+}
+const PASS_1 = combineTransformers([
+    Transformers.inline(TRANFORMER_OPTIONS),
+    Transformers.removeDeadBranches(TRANFORMER_OPTIONS),
+    Transformers.unionCharacters(TRANFORMER_OPTIONS),
+    Transformers.moveUpEmpty(TRANFORMER_OPTIONS),
+    Transformers.nestedQuantifiers(TRANFORMER_OPTIONS),
+    Transformers.removeUnnecessaryAssertions(TRANFORMER_OPTIONS),
+    Transformers.applyAssertions(TRANFORMER_OPTIONS),
+])
+const PASS_2 = combineTransformers([
+    Transformers.inline(TRANFORMER_OPTIONS),
+    Transformers.removeDeadBranches(TRANFORMER_OPTIONS),
+    Transformers.replaceAssertions({
+        ...TRANFORMER_OPTIONS,
+        replacement: "empty-set",
+    }),
+])
+
+export default createRule("no-super-linear-move", {
+    meta: {
+        docs: {
+            description: "disallow quantifiers that cause quadratic moves",
+            category: "Possible Errors",
+            recommended: false,
+        },
+        schema: [
+            {
+                type: "object",
+                properties: {
+                    report: {
+                        enum: ["certain", "potential"],
+                    },
+                    ignoreSticky: {
+                        type: "boolean",
+                    },
+                    ignorePartial: {
+                        type: "boolean",
+                    },
+                },
+                additionalProperties: false,
+            },
+        ],
+        messages: {
+            unexpected:
+                "Any attack string {{attack}} plus some rejecting suffix will cause quadratic runtime because of this quantifier.",
+        },
+        type: "problem",
+    },
+    create(context) {
+        const reportUncertain =
+            (context.options[0]?.report ?? "certain") === "potential"
+        const ignoreSticky = context.options[0]?.ignoreSticky ?? false
+        const ignorePartial = context.options[0]?.ignorePartial ?? true
+
+        /** Returns reports reported by scslre. */
+        function getScslreReports(
+            regexpContext: RegExpContext,
+            assumeRejectingSuffix: boolean,
+        ): Iterable<Report> {
+            const { flags } = regexpContext
+
+            const result = analyse(getParsedLiteral(regexpContext, true), {
+                reportTypes: { Move: true, Self: false, Trade: false },
+                assumeRejectingSuffix,
+            })
+
+            return result.reports.map<Report>((r) => {
+                if (r.type !== "Move") {
+                    throw new Error("Unexpected report type")
+                }
+
+                return {
+                    quant: r.quant,
+                    attack: `/${r.character.literal.source}+/${
+                        flags.ignoreCase ? "i" : ""
+                    }`,
+                }
+            })
+        }
+
+        /**
+         * Returns reports found using a simple quantifier approach.
+         *
+         * The main idea of the approach implemented here is the follows: If
+         * there is a star quantifier q that can consume a non-empty word w
+         * without asserting characters outside of w and that can be reached
+         * without consuming or asserting characters, then we can construct an
+         * attack string w^n.
+         *
+         * Example: /(?:ab){2,}:/
+         * Here, q is `(?:ab){2,}` and w is `ab`. By repeating "ab", we can
+         * create attack strings for which the regex will take O(n^2) time to
+         * move across.
+         */
+        function* getSimpleReports(
+            regexpContext: RegExpContext,
+            assumeRejectingSuffix: boolean,
+        ): Iterable<Report> {
+            const { patternAst, flags } = regexpContext
+
+            const parser = JS.Parser.fromAst(
+                getParsedLiteral(regexpContext, true),
+            )
+
+            for (const q of findReachableQuantifiers(patternAst)) {
+                if (q.max !== Infinity) {
+                    // we are only interested in star quantifiers
+                    continue
+                }
+                if (
+                    q.element.type === "Assertion" ||
+                    q.element.type === "Backreference"
+                ) {
+                    // these elements cannot consume characters
+                    continue
+                }
+
+                let e: NoParentNode<Expression> = parser.parseElement(
+                    q.element,
+                    {
+                        assertions: "parse",
+                        backreferences: "disable",
+                    },
+                ).expression
+                // apply and remove all assertions
+                e = transform(PASS_1, e)
+                e = transform(PASS_2, e)
+
+                if (e.alternatives.length === 0) {
+                    // there are no possible attack strings
+                    continue
+                }
+
+                let hasCharacters = false
+                visitAst(e, {
+                    onCharacterClassEnter() {
+                        hasCharacters = true
+                    },
+                })
+
+                if (!hasCharacters) {
+                    // the element is empty
+                    // repeating this doesn't make sense for attack strings
+                    continue
+                }
+
+                if (!assumeRejectingSuffix) {
+                    // Let's try to filter out some false positives.
+                    //
+                    // The basic idea here is that if there is a path after
+                    // the quantifier that can reach the end of the pattern
+                    // without consuming or assertion characters, then it is
+                    // not possible to find a rejecting suffix.
+                    //
+                    // This is actually not enough and will cause some false
+                    // positives (e.g. `/(?:abc)*a/`) but it's the best I can
+                    // think of right now.
+                    const after = getFirstConsumedCharAfter(
+                        q,
+                        getMatchingDirection(q),
+                        flags,
+                    )
+                    if (after.empty && after.look.char.isAll) {
+                        // it is not possible to find a rejecting suffix
+                        continue
+                    }
+                }
+
+                const attack = `/${
+                    JS.toLiteral({
+                        type: "Quantifier",
+                        alternatives: e.alternatives,
+                        min: 1,
+                        max: Infinity,
+                        lazy: false,
+                    }).source
+                }/${flags.ignoreCase ? "i" : ""}`
+
+                yield { quant: q, attack }
+            }
+        }
+
+        /**
+         * Create visitor
+         */
+        function createVisitor(
+            regexpContext: RegExpContext,
+        ): RegExpVisitor.Handlers {
+            const {
+                node,
+                flags,
+                getRegexpLocation,
+                getUsageOfPattern,
+            } = regexpContext
+
+            if (ignoreSticky && flags.sticky) {
+                return {}
+            }
+
+            const usage = getUsageOfPattern()
+
+            if (ignorePartial && usage === UsageOfPattern.partial) {
+                return {}
+            }
+
+            const assumeRejectingSuffix =
+                reportUncertain && usage !== UsageOfPattern.whole
+
+            for (const report of dedupeReports([
+                ...getSimpleReports(regexpContext, assumeRejectingSuffix),
+                ...getScslreReports(regexpContext, assumeRejectingSuffix),
+            ])) {
+                context.report({
+                    node,
+                    loc: getRegexpLocation(report.quant),
+                    messageId: "unexpected",
+                    data: { attack: report.attack },
+                })
+            }
+
+            return {}
+        }
+
+        return defineRegexpVisitor(context, {
+            createVisitor,
+        })
+    },
+})
diff --git a/lib/rules/strict.ts b/lib/rules/strict.ts
index 0e7cc4c..5656ecd 100644
--- a/lib/rules/strict.ts
+++ b/lib/rules/strict.ts
@@ -67,6 +67,10 @@ export default createRule("strict", {
 
             // validator
             regexMessage: "{{message}}.",
+
+            // suggestions
+            hexEscapeSuggestion:
+                "Replace the octal escape with a hexadecimal escape.",
         },
         type: "suggestion",
     },
@@ -97,19 +101,36 @@ export default createRule("strict", {
             function report(
                 messageId: string,
                 element: Element,
-                fix?: string | null,
+                fix?: string | null | { fix: string; messageId: string },
             ): void {
                 reported = true
 
-                context.report({
-                    node,
-                    loc: getRegexpLocation(element),
-                    messageId,
-                    data: {
-                        expr: element.raw,
-                    },
-                    fix: fix ? fixReplaceNode(element, fix) : null,
-                })
+                if (fix && typeof fix === "object") {
+                    context.report({
+                        node,
+                        loc: getRegexpLocation(element),
+                        messageId,
+                        data: {
+                            expr: element.raw,
+                        },
+                        suggest: [
+                            {
+                                messageId: fix.messageId,
+                                fix: fixReplaceNode(element, fix.fix),
+                            },
+                        ],
+                    })
+                } else {
+                    context.report({
+                        node,
+                        loc: getRegexpLocation(element),
+                        messageId,
+                        data: {
+                            expr: element.raw,
+                        },
+                        fix: fix ? fixReplaceNode(element, fix) : null,
+                    })
+                }
             }
 
             return {
@@ -131,12 +152,16 @@ export default createRule("strict", {
                         return
                     }
                     if (cNode.value !== 0 && isOctalEscape(cNode.raw)) {
-                        // e.g. \023
-                        report(
-                            "octalEscape",
-                            cNode,
-                            `\\x${cNode.value.toString(16).padStart(2, "0")}`,
-                        )
+                        // e.g. \023, \34
+
+                        // this could be confused with a backreference
+                        // use a suggestion instead of a fix
+                        report("octalEscape", cNode, {
+                            fix: `\\x${cNode.value
+                                .toString(16)
+                                .padStart(2, "0")}`,
+                            messageId: "hexEscapeSuggestion",
+                        })
                         return
                     }
 
diff --git a/lib/utils/rules.ts b/lib/utils/rules.ts
index 08e1a72..3e5ed9b 100644
--- a/lib/utils/rules.ts
+++ b/lib/utils/rules.ts
@@ -23,6 +23,7 @@ import noOptionalAssertion from "../rules/no-optional-assertion"
 import noPotentiallyUselessBackreference from "../rules/no-potentially-useless-backreference"
 import noStandaloneBackslash from "../rules/no-standalone-backslash"
 import noSuperLinearBacktracking from "../rules/no-super-linear-backtracking"
+import noSuperLinearMove from "../rules/no-super-linear-move"
 import noTriviallyNestedAssertion from "../rules/no-trivially-nested-assertion"
 import noTriviallyNestedQuantifier from "../rules/no-trivially-nested-quantifier"
 import noUnusedCapturingGroup from "../rules/no-unused-capturing-group"
@@ -89,6 +90,7 @@ export const rules = [
     noPotentiallyUselessBackreference,
     noStandaloneBackslash,
     noSuperLinearBacktracking,
+    noSuperLinearMove,
     noTriviallyNestedAssertion,
     noTriviallyNestedQuantifier,
     noUnusedCapturingGroup,


Test patch:
diff --git a/tests/lib/rules/no-super-linear-move.ts b/tests/lib/rules/no-super-linear-move.ts
new file mode 100644
index 0000000..0a6cd75
--- /dev/null
+++ b/tests/lib/rules/no-super-linear-move.ts
@@ -0,0 +1,84 @@
+import { RuleTester } from "eslint"
+import rule from "../../../lib/rules/no-super-linear-move"
+
+const tester = new RuleTester({
+    parserOptions: {
+        ecmaVersion: 2020,
+        sourceType: "module",
+    },
+})
+
+tester.run("no-super-linear-move", rule as any, {
+    valid: [
+        String.raw`/regexp/`,
+        String.raw`/\ba*:/`,
+
+        // no rejecting suffix
+        String.raw`/a*/`,
+
+        {
+            code: String.raw`/a*/.test(input)`,
+            options: [{ report: "potential" }],
+        },
+        {
+            code: String.raw`export default /a*/`,
+            options: [{ report: "certain" }],
+        },
+        { code: String.raw`/a*b/.source`, options: [{ ignorePartial: true }] },
+        { code: String.raw`/a*b/y`, options: [{ ignoreSticky: true }] },
+    ],
+    invalid: [
+        {
+            code: String.raw`/a*:/`,
+            errors: [
+                "Any attack string /a+/ plus some rejecting suffix will cause quadratic runtime because of this quantifier.",
+            ],
+        },
+        {
+            code: String.raw`/^\s*(\w+)\s*[:=]/m`,
+            errors: [
+                "Any attack string /[\\n\\r\\u2028\\u2029]+/ plus some rejecting suffix will cause quadratic runtime because of this quantifier.",
+            ],
+        },
+        {
+            code: String.raw`/((?:\\{2})*)(\\?)\|/g`,
+            errors: [
+                "Any attack string /(?:\\\\{2})+/ plus some rejecting suffix will cause quadratic runtime because of this quantifier.",
+            ],
+        },
+        {
+            code: String.raw`/[a-z_][A-Z_0-9]*(?=\s*\()/i`,
+            errors: [
+                "Any attack string /[A-Z_]+/i plus some rejecting suffix will cause quadratic runtime because of this quantifier.",
+            ],
+        },
+        {
+            code: String.raw`/(?!\d)\w+(?=\s*\()/i`,
+            errors: [
+                "Any attack string /[A-Z_]+/i plus some rejecting suffix will cause quadratic runtime because of this quantifier.",
+            ],
+        },
+
+        {
+            code: String.raw`export default /a*/`,
+            options: [{ report: "potential" }],
+            errors: [
+                "Any attack string /a+/ plus some rejecting suffix will cause quadratic runtime because of this quantifier.",
+            ],
+        },
+        {
+            code: String.raw`/a*b/.source`,
+            options: [{ ignorePartial: false }],
+            errors: [
+                "Any attack string /a+/ plus some rejecting suffix will cause quadratic runtime because of this quantifier.",
+            ],
+        },
+        {
+            code: String.raw`/a*b/y`,
+            options: [{ ignoreSticky: false }],
+            errors: [
+                "Any attack string /a+/ plus some rejecting suffix will cause quadratic runtime because of this quantifier.",
+            ],
+        },
+    ],
+})
diff --git a/tests/lib/rules/strict.ts b/tests/lib/rules/strict.ts
index aea2f7a..861dcbe 100644
--- a/tests/lib/rules/strict.ts
+++ b/tests/lib/rules/strict.ts
@@ -133,12 +133,37 @@ tester.run("strict", rule as any, {
         },
         {
             code: "/\\012/",
-            output: "/\\x0a/",
+            output: null,
             errors: [
                 {
                     message:
                         "Invalid legacy octal escape sequence '\\012'. Use a hexadecimal escape instead.",
                     column: 2,
+                    suggestions: [
+                        {
+                            output: "/\\x0a/",
+                            desc:
+                                "Replace the octal escape with a hexadecimal escape.",
+                        },
+                    ],
+                },
+            ],
+        },
+        {
+            code: "/\\12/",
+            output: null,
+            errors: [
+                {
+                    message:
+                        "Invalid legacy octal escape sequence '\\12'. Use a hexadecimal escape instead.",
+                    column: 2,
+                    suggestions: [
+                        {
+                            output: "/\\x0a/",
+                            desc:
+                                "Replace the octal escape with a hexadecimal escape.",
+                        },
+                    ],
                 },
             ],
         },