Safe regex patterns from ReDos attack

Question

I've recently faced with some redos attack issues.

Explain in simple steps:

Regex denial of services: it means the attacker can put some malicious/crafted inputs to bring your server down by making it impossible to stop to finding the correct pattern, so it takes your whole CPU, and finally causing internal server error.

e.g. if you have a pattern like ^((ab)*)+$, and the attacker put a malicious input like abababababababababababababababababa it will cause a catastrophic error:

The issue comes to the surface when using Nested quantifiers, quantifying over a sub-expression which can, itself, match in many ways in the same position. as you can see in the below picture(https://jex.im/regulex):

There are many solutions for many pattern matching problems, e.g if you want a pattern for URL there are tons of answers(also in the StackOverflow), which are good answers but almost vulnerable to this kind of attack.

I've found some useful tools like safe-regex: https://www.npmjs.com/package/safe-regex , which works good but have false-positives and false negatives. As you already know, Safe Regex Patterns from Redos Attack are hard to find.

Need

I'm asking, is there any list of safe regex patterns out there to use for common uses like passwords, URLs,etc.?

Useful resource

Useful for only js platform, https://github.com/validatorjs/validator.js

Update

I've struggled with this issue and found there are some libraries like re2, and validator.js, which are good tools, and found out that java solves this problem from v9 and erlang too, but in javascript regex engine still has the problem in chrome, but in firefox, it will throw an error which is good to handle in try cache, and finally, I've put my tries to make a list for this purpose at this Github link:

https://github.com/phoenixdevio/safe-regex-patterns

still couldn't found a good solution. although I know there may be a solution using the atomic group. it will be great if anyone could help with this to make the list more and better.

Answer 1

这并不能直接回答您的问题，但避免此类攻击的最简单方法（根据我的经验）是使用基于https://github.com/google/re2的正则表达式库，因为它不会容易受到 ReDOS 攻击。对于节点，参考库是https://github.com/uhop/node-re2/

RE2 有意识地避免任何需要最坏情况指数时间来评估的正则表达式功能。这些功能本质上是描述上下文无关语言（CFL）而不是正则表达式的功能，并且是对传统正则表达式语言的扩展，因为有些人不知道什么时候足够了。

最值得注意的缺失功能是反向引用和前瞻断言。如果您的应用程序使用这些功能，您应该继续使用 RegExp。但由于这些功能从根本上来说很容易受到 ReDoS 的攻击，因此您应该强烈考虑替换它们。

如果你的正则表达式与它不兼容，那么它几乎肯定容易受到 ReDOS 的影响，并且（作为奖励）许多通常容易​​受到ReDOS影响的（如你的示例）仍然有效，但在 re2 中不易受到影响。