[GH-ISSUE #657] Polynomial backtracking in some regexes #491

New issue

Closed

opened 2026-03-03 01:27:23 +03:00 by kerem · 2 comments

kerem commented

2026-03-03 01:27:23 +03:00

Owner

Originally created by @RunDevelopment on GitHub (Nov 28, 2022).
Original GitHub issue: https://github.com/DavidAnson/markdownlint/issues/657

Hi!

We recently added markdownlint to our project, and so I took a look at the README which contained this regex:

/((^---\s*$[^]*?^---\s*$)|(^\+\+\+\s*$[^]*?^(\+\+\+|\.\.\.)\s*$)|(^\{\s*$[^]*?^\}\s*$))(\r\n|\r|\n|$)/m

I noticed \s*$[^]*?. This part of the pattern can be exploited to create attack strings that take O(n^2) time to process. So luckily it's not exponential time ReDoS, but it should still be fixed.

How to fix it:

The problem is that \s and [^]*? can exchange characters, \r, \n, and 2 others to be exact. In your case, the problem is that the \s* can consume characters after the first line break and beyond. E.g. In ---\n\n\n\nfoo\n---, the \s will consume the 3 first \n after the starting ---. The fix is to ensure that the \s* can't consume line ends, so replacing \s* with [ \t]* will fix the issue.

While [ \t]* will fix the issue, it's not an exact fix. \s* matches many kinds of spaces, not just ASCII space and tab. Whether you want to include those spaces as well is up to you. The easiest way to say "all spaces but no line ends" is (?:(?=.)\s)* btw.

This fix also has to be applied to the 2 other occurrences of \s*$[^]*? in the regex.

Detecting ReDoS (and other regex problems)

Remember the project we added markdown lint to? That one actually detected this problem :)
^{(I might be able to see that \s*$[^]*? is a problem from looking at it, but I can't tell you exactly which characters are the problem.)}

It's an ESLint plugin to detect problems in regexes, enforce best practices and some other stuff. You can use its regexp/no-super-linear-backtracking rule to find all cases of polynomial and exponential backtracking in your regexes (at least, all that it can detect).

I recommend you add it to your code base, because this regex wasn't the only one with polynomial backtracking it found, and it likely won't be the last if you intend to use regexes in your code base.

If you need help fixing case of ReDoS, feel free to ask me on GitHub or per email.

Despite ReDoS being a security vulnerability, I opened this public issue. I did this for 3 reasons:

I couldn't find your email.
Polynomial ReDoS isn't a high or critical vulnerability, so you usually can't do too much damage with it.
The regex was prominently displayed in the regex. If anyone knew how to exploit it and wanted to do so, they would have done it by now...

I would still recommend setting up a security policy that at least contains contact information.

Originally created by @RunDevelopment on GitHub (Nov 28, 2022). Original GitHub issue: https://github.com/DavidAnson/markdownlint/issues/657 Hi! We [recently added markdownlint](https://github.com/ota-meshi/eslint-plugin-regexp/pull/494) to [our project](https://github.com/ota-meshi/eslint-plugin-regexp), and so I took a look at the README which contained this regex: > `/((^---\s*$[^]*?^---\s*$)|(^\+\+\+\s*$[^]*?^(\+\+\+|\.\.\.)\s*$)|(^\{\s*$[^]*?^\}\s*$))(\r\n|\r|\n|$)/m` I noticed `\s*$[^]*?`. This part of the pattern can be exploited to create attack strings that take O(n^2) time to process. So luckily it's not exponential time [ReDoS](https://en.wikipedia.org/wiki/ReDoS), but it should still be fixed. ### How to fix it: The problem is that `\s` and `[^]*?` can exchange characters, `\r`, `\n`, and 2 others to be exact. In your case, the problem is that the `\s*` can consume characters after the first line break and beyond. E.g. In `---\n\n\n\nfoo\n---`, the `\s` will consume the 3 first `\n` after the starting `---`. The fix is to ensure that the `\s*` can't consume line ends, so replacing `\s*` with `[ \t]*` will fix the issue. While `[ \t]*` will fix the issue, it's not an exact fix. `\s*` matches many kinds of spaces, not just ASCII space and tab. Whether you want to include those spaces as well is up to you. The easiest way to say "all spaces but no line ends" is `(?:(?=.)\s)*` btw. This fix also has to be applied to the 2 other occurrences of `\s*$[^]*?` in the regex. ### Detecting ReDoS (and other regex problems) Remember the project we added markdown lint to? That one actually detected this problem :) <sup>(I might be able to see that `\s*$[^]*?` is a problem from looking at it, but I can't tell you exactly which characters are the problem.)</sup> It's an ESLint plugin to detect problems in regexes, enforce best practices and some other stuff. You can use its [`regexp/no-super-linear-backtracking`](https://ota-meshi.github.io/eslint-plugin-regexp/rules/no-super-linear-backtracking.html) rule to find all cases of polynomial and exponential backtracking in your regexes (at least, all that it can detect). I recommend you add it to your code base, because this regex wasn't the only one with polynomial backtracking it found, and it likely won't be the last if you intend to use regexes in your code base. If you need help fixing case of ReDoS, feel free to ask me on GitHub or per email. --- Despite ReDoS being a security vulnerability, I opened this public issue. I did this for 3 reasons: - I couldn't find your email. - Polynomial ReDoS isn't a high or critical vulnerability, so you usually can't do too much damage with it. - The regex was prominently displayed in the regex. If anyone knew how to exploit it and wanted to do so, they would have done it by now... I would still recommend setting up a security policy that at least contains contact information.

kerem

2026-03-03 01:27:23 +03:00

closed this issue
added the
enhancement

fixed in next
labels

kerem commented

2026-03-03 01:27:24 +03:00

Author

Owner

@DavidAnson commented on GitHub (Nov 28, 2022):

Thanks for bringing this to my attention! As you probably know, CodeQL raises issues for this problem, and I spent time one or two releases ago addressing all of the issues it found.

It looks like it flagged this scenario, but only associated with the test case and so I dismissed it. https://github.com/DavidAnson/markdownlint/security/code-scanning/16

I will try your plug-in and address the issues it raises. As you say, this particular scenario does not seem overly concerning – especially because this is something the user can override via configuration.

@DavidAnson commented on GitHub (Nov 28, 2022): Thanks for bringing this to my attention! As you probably know, CodeQL raises issues for this problem, and I spent time one or two releases ago addressing all of the issues it found. It looks like it flagged this scenario, but only associated with the test case and so I dismissed it. https://github.com/DavidAnson/markdownlint/security/code-scanning/16 I will try your plug-in and address the issues it raises. As you say, this particular scenario does not seem overly concerning – especially because this is something the user can override via configuration.

kerem commented

2026-03-03 01:27:24 +03:00

Author

Owner

@DavidAnson commented on GitHub (Dec 8, 2022):

diff --git a/.eslintrc.json b/.eslintrc.json
index 46e07bb..8627726 100644
--- a/.eslintrc.json
+++ b/.eslintrc.json
@@ -7,6 +7,7 @@
     "eslint:all",
     "plugin:jsdoc/recommended",
     "plugin:n/recommended",
+    "plugin:regexp/recommended",
     "plugin:unicorn/all"
   ],
   "ignorePatterns": [
diff --git a/package.json b/package.json
index 05195c4..12a4198 100644
--- a/package.json
+++ b/package.json
@@ -68,6 +68,7 @@
     "eslint-plugin-es": "4.1.0",
     "eslint-plugin-jsdoc": "39.6.4",
     "eslint-plugin-n": "15.6.0",
+    "eslint-plugin-regexp": "1.11.0",
     "eslint-plugin-unicorn": "45.0.1",
     "globby": "13.1.2",
     "js-yaml": "4.1.0",

@DavidAnson commented on GitHub (Dec 8, 2022): ```diff diff --git a/.eslintrc.json b/.eslintrc.json index 46e07bb..8627726 100644 --- a/.eslintrc.json +++ b/.eslintrc.json @@ -7,6 +7,7 @@ "eslint:all", "plugin:jsdoc/recommended", "plugin:n/recommended", + "plugin:regexp/recommended", "plugin:unicorn/all" ], "ignorePatterns": [ diff --git a/package.json b/package.json index 05195c4..12a4198 100644 --- a/package.json +++ b/package.json @@ -68,6 +68,7 @@ "eslint-plugin-es": "4.1.0", "eslint-plugin-jsdoc": "39.6.4", "eslint-plugin-n": "15.6.0", + "eslint-plugin-regexp": "1.11.0", "eslint-plugin-unicorn": "45.0.1", "globby": "13.1.2", "js-yaml": "4.1.0", ```

kerem referenced this issue

2026-03-03 01:30:36 +03:00

[PR #491] [MERGED] Add eslint-plugin-markdownlint to Related/Tooling section #879

kerem referenced this issue

2026-03-07 20:10:18 +03:00

[PR #491] [MERGED] Add eslint-plugin-markdownlint to Related/Tooling section #2727