Polynomial backtracking in some regexes

[RunDevelopment]

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.

[DavidAnson]

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]

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",