2

是否有一种算法可以确定给定的 JavaScript 正则表达式是否容易受到ReDoS的攻击？该算法不必是完美的——一些误报和误报是可以接受的。（我对ECMA-262正则表达式特别感兴趣。）

4

2 回答 2

2

如果不实际运行它，很难验证正则表达式是否邪恶。您可以尝试检测 Wiki 中详述的一些模式并概括它们：

例如对于

  • (a+)+
  • ([a-zA-Z]+)*
  • (a|aa)+
  • (a|a?)+
  • (.*a){x} 对于 x > 10

您可以检查)+or )*or){序列并针对它们进行验证。但是，我保证攻击者会找到绕过它们的方法。

从本质上讲，这是一个允许用户设置正则表达式的雷区。但是，如果您可以使正则表达式搜索超时，终止线程，然后将该正则表达式标记为“坏”，您可以在一定程度上减轻威胁。如果稍后使用正则表达式，也许您可​​以通过在入口点针对预期输入运行它来验证它？

稍后，如果在后期评估的文本与您的正则表达式有不同的效果并将其标记为错误，则您仍然需要能够终止它，以便在没有用户干预的情况下不会再次使用它。

于 2015-12-02T16:03:17.563 回答
0

TL;DR有点，但不完全

In [9]: re.compile("(a+)+", re.DEBUG)
max_repeat 1 4294967295
  subpattern 1
    max_repeat 1 4294967295
      literal 97

请注意那些嵌套的重复 1..N，对于大 N，这很糟糕。

这会处理所有 Wikipedia 示例，除了(a|aa)+和a*b?a*x。

同样，如果您的引擎支持反向引用，则很难解释这些反向引用。

IMO 邪恶正则表达式是两个因素的组合：组合爆炸和引擎实施中的监督。因此，最坏的情况还取决于正则表达式引擎，有时还取决于标志。回溯并不总是很容易识别。

但是，可以识别简单的情况。

于 2016-08-05T10:08:21.410 回答