regexploit - Find regular expressions which are vulnerable to R

项目说明

Regexploit

!regexploit_logo

Find regexes which are to Regular Expression Denial of Service (ReDoS).

More info on the Doyensec blog

Many default regular expression parsers ha worst-case complexity. Regex matching may be quick when presented with a matching input string. However, certain non-matching input strings can make the regular expression matcher go into crazy backtracking loops and take ages to process. This can cause denial of service, as the CPU will be stuck trying to match the regex.

This tool is designed to:
* find regular expressions which are to ReDoS
* give an example malicious string which will cause catastrophic backtracking

Worst-case complexity

This reflects the complexity of the regular expression matcher's backtracking procedure with respect to the length of the entered string.

Cubic complexity here means that if the part of the string is doubled in length, the execution time should be about 8 times longer (2^3).
For exponential ReDoS with starred stars e.g. (a*)*$ a fudge factor is used and the complexity will be greater than 10.

For explotability, cubic complexity or higher is typically required unless truly giant strings are allowed as input.

Example

Run regexploit and enter the regular expression v\w*_\w*_\w*$ at the command line.

The part \w*_\w*_\w* contains three o repeating groups (\w matches letters, digits *and underscores*). As showed in the line Repeated character: [5f:_], a long string of _ (0x5f) will match this section in many different ways. The worst-case complexity is 3 as there are 3 infinitely repeating groups. An example to cause ReDoS is given: it consists of the required prefix v, a long string of _ and then a ! (non-word character) to cause backtracking. Not all ReDoSes require a particular character at the end, but in this case, a long string of _ will match the regex successfully and won't backtrack. The line Final character to cause backtracking: [^WORD] shows that a non-matching character (not a word character) is required at the end to prevent matching and cause ReDoS.

As another example, install a module to ReDoS such as pip install ua-parser==0.9.0.
To scan the installed python modules run regexploit-python-env.

For each regular expression it prints one or more malicious string to trigger ReDoS. Setting your user agent to ;0 Build/HuaweiA000000000000000... and browsing a website using an old of ua-parser may cause the server to take a long time to process your request, probably ending in status 502.

Installation

Python 3.8+ is required. To extract regexes from Ja / TypeScript code, NodeJS 12+ is also required.

Optionally make a en

Now actually install with pip

Usage

Regexploit with a list of regexes

Enter regular expressions (one per line) into regexploit.

or via a file

Extract regexes automatically

There is built-in support for parsing regexes out of Python, Ja, TypeScript, C#, YAML and JSON.

Python code

Parses Python code (without executing it) via the AST to find regexes. The regexes are then analysed for ReDoS.

Ja / Typescript

This will use the bundled NodeJS package in regexploit/bin/ja which parses your Ja as an AST with eslint and prints out all regexes.

Those regexes are fed into the python ReDoS finder.

N.B. there are differences between ja and python regex parsing so there may be some errors. I'm not sure I want to write a JS regex AST!

Python imports

Search for regexes in all the python modules currently installed in your path / env. This means you can pip install whate you are interested in and they will be analysed. Cpython code is included.

N.B. this doesn't parse the python code to an AST and will only find regexes compiled automatically on module import. Modules are actually imported, so code in the modules will be executed. This is helpful for finding regexes which are built up from smaller strings on load e.g. C in Pillow

JSON / YAML

Yaml support requires pyyaml, which can be installed with pip install regexploit[yaml].

C# (.NET)

:trophy: Bugs reported :trophy:

* C: uap-core affecting uap-python, uap-ruby, etc. (User-Agent header parsing)
* C: cpython's urllib.request (WWW-Authenticate header parsing)
* C: CairoSVG (S)
* C: httplib2 (WWW-Authenticate header parsing)
* C: python-pillow (PDF parsing)
* C: python-markdown2 (Markdown parsing)
* C: npm/ssri (SRI parsing)
* C: pygments lexers for ADL, CADL, Ceylon, Evoque, Factor, Logos, Matlab, Octave, ODIN, Scilab & VCL (Syntax highlighting)
* C: ua-parser-js (User-Agent header parsing)
* C: RestSharp (JSON deserialisation in a .NET C# package)
* bpo-38804: cpython's http.cookiejar (Set-Cookie header parsing)
* SimpleCrawler (archived) (HTML parsing)
* C: is-svg (S)
* nuget.org, NuGetGallery and NuGet.Client (Parsing NuGet package IDs)
* markdown (python) (Markdown parsing)
* ansi-html (nodejs) (ANSI parsing)
* Plus unpublished bugs in a handful of pypi, npm, ruby and nuget packages

Credits

This tool has been created by Ben Caller of Doyensec LLC during research time.

!alt text

项目信息

开发语言：Python

Star 数：850

技术要点

该项目属于漏洞知识库方向的开源资源，代码结构清晰，适合安全研究人员学习参考。项目围绕Find regular expressions which are vulnerable to ReDoS (Regular Expression Denial of Service)展开，提供了可运行的实现，对理解相关安全机制、工具原理与攻防技术具有较高的研究价值。

从技术实现角度看，此类项目的核心在于对底层原理的深入理解与工程化落地。开发者在研究过程中可以结合官方文档与社区讨论，梳理项目的初始化流程、核心模块职责与数据流转，逐步掌握其中的技术细节与设计思路。

使用与学习建议

1. 下载源码压缩包，解压到本地环境。

2. 根据项目类型准备对应的运行环境与依赖。

3. 按照 README 中的步骤完成配置与部署。

4. 在隔离的测试环境中运行验证，避免影响生产系统。

免责声明

本资源来源于开源社区，仅供安全研究、技术学习与合法授权范围内的攻防演练使用，请勿用于任何非法或侵害他人权益的用途。使用本项目产生的一切后果由使用者自行承担。