如何使用Regexploit识别ReDoS正则表达式拒绝服务攻击

关于Regexploit

Regexploit可以帮助广大研究人员找出易受正则表达式拒绝服务攻击(ReDoS)的正则表达式。

许多默认正则表达式解析器都很复杂，而且存在很多安全问题。当显示匹配的输入字符串时，使用正则表达式匹配的方式可能速度会很快，但是某些不匹配的输入字符串可能会使正则表达式匹配器进入疯狂的回溯循环，并且需要花费很长时间来处理。此时，将有可能导致应用程序出现拒绝服务的情况，因为CPU在尝试匹配正则表达式时会卡住。

该工具的主要目的如下：

寻找易受正则表达式拒绝服务攻击(ReDoS)的正则表达式;
给出一个会导致死循环回溯的恶意字符串示例;

最坏情况复杂性

最坏情况复杂性反映了正则表达式匹配器的回溯过程相对于输入字符串长度的复杂性。这个最坏情况复杂性是以立方计算的，如果字符串的易受攻击部分的长度增加了一倍，则执行时间应延长约8倍(2^3)。

工具安装

该工具需要在本地安装并配置好Python 3.8+环境。由于Regexploit会从JavaScript/TypeScript代码中提取正则表达式，因此还需要安装好NodeJS 12+。

首先，我们可以创建一个虚拟环境：

python3 -m venv .env 
 
source .env/bin/activate

然后使用pip来安装Regexploit：

pip install regexploit

工具使用

1. 正则表达式处理

我们可以通过stdin(每个正则表达式占一行)向Regexploit输入正则表达式：

regexploit

或者直接处理正则表达式列表文件：

cat myregexes.txt | regexploit

2. 自动提取正则表达式

Regexploit内置支持解析Python、JavaScript、TypeScript、C#、YAML和JSON代码中的正则表达式。

(1) Python代码

通过AST解析Python代码(无需执行)并提取正则表达式，并分析是否易受ReDoS：

regexploit-py my-project/ 
 
regexploit-py "my-project/**/*.py" --glob

(2) Javascript / Typescript

该功能将使用regexploit/bin/javascript中捆绑的NodeJS包实现，并解析JavaScript中的正则表达式：

regexploit-js my-module/my-file.js another/file.js some/folder/ 
 
regexploit-js "my-project/node_modules/**/*.js" --glob

(3) JSON/YAML

YAML支持需要安装pyyaml，我们可以使用命令“pip install regexploit[yaml]”进行安装：

regexploit-json *.json 
 
regexploit-yaml *.yaml

(4) C#(.NET)

regexploit-csharp something.cs

工具使用样例

运行Regexploit，并在命令行中输入正则表达式“v\w*_\w*_\w*$”：

$ regexploit 
 
v\w*_\w*_\w*$ 
 
Pattern: v\w*_\w*_\w*$ 
 
--- 
 
Worst-case complexity: 3 ⭐⭐⭐ (cubic) 
 
Repeated character: [5f:_] 
 
Final character to cause backtracking: [^WORD] 
 
Example: 'v' + '_' * 3456 + '!'