"RegExp DoS issue"是什么？

Question

我刚刚在服务器上安装了nodejs，一个基本的npm install显示了很多这样的消息:

$ npm install
npm WARN deprecated minimatch@2.0.10: Please update to minimatch 3.0.2 or higher to avoid a RegExp DoS issue
npm WARN deprecated minimatch@0.2.14: Please update to minimatch 3.0.2 or higher to avoid a RegExp DoS issue
npm WARN deprecated graceful-fs@1.2.3: graceful-fs v3.0.0 and before will fail on node releases >= v7.0. Please update to graceful-fs@^4.0.0 as soon as possible. Use 'npm ls graceful-fs' to find it in the tree.
npm WARN deprecated graceful-fs@2.0.3: graceful-fs v3.0.0 and before will fail on node releases >= v7.0. Please update to graceful-fs@^4.0.0 as soon as possible. Use 'npm ls graceful-fs' to find it in the tree.
npm WARN prefer global node-gyp@3.4.0 should be installed with -g

注意右边出现的信息:

npm WARN ... or higher to avoid a RegExp DoS issue
                       ^^^^^^^^^^^^^^^^^^^^^^^^^^^

在我的本地服务器上，我已经使用了minimatch 3.0.3。然而，由于服务器没有使用最新版本的node，这对我来说是新的，并开始调查:

这个问题在npm的github中被报告，并在其他问题中提到。一般来说，可以通过将minimatch版本升级到至少3.0.2来解决这个问题。

然而，我想知道这个RegExp DoS问题是什么?是否有任何特定的正则表达式，是允许DoS攻击通过minimatch?我无法想象这是怎么发生的，也不想重现它，但我没能找到更多的文档和minimatch的Github问题列表没有任何痕迹。

从发布页面中，我看到了3.0.2版本的唯一提交，其中基本上封装了regex语法(我对JavaScript不够熟悉，无法跟踪所有的细节)。

Answer 1

从提交链接到(https://github.com/isaacs/minimatch/commit/6944abf9e0694bd22fd9dad293faa40c2bc8a955):

在提交中添加的测试是创建一个像这样的正则表达式:

var exploit = '!(' + genstr(1024 * 15, '\') + 'A)'

那就是创建一个从'!('开始的字符串，然后是1024*15个副本，然后是'A)'。这必须是DoS条件。

这条线

tail = tail.replace(/((?:\{2}){0,64})(\?)|/g, function (_, $1, $2) {

可能是窒息的那个