redos-db › mime-CVE-2017-16138
Real-world ReDoS: quadratic (n²) catastrophic backtracking
The classic "mime" package resolves a file extension to a MIME type. mime.lookup() applied an unanchored greedy regex to the input path; a long extension-less filename forces quadratic scanning.
Input that triggers the blow-up: a run of "a". A benign input like file.txt matches in microseconds.
| CVE | CVE-2017-16138 |
| GHSA | GHSA-wrvr-8mpx-r7pp |
| Weakness | CWE-400 (Inefficient Regular Expression Complexity) |
| Package | mime (npm) |
| Affected | <1.4.1 || >=2.0.0 <2.0.3 |
| Patched in | 1.4.1 |
| Published | 2018-05-31 |
| Discovered by | Nick Starke |
| Complexity | quadratic (n²) |
mime.lookup() ran an unanchored /.*[./\\]/ over the whole path; with no separator present the greedy .* restarts at every offset (quadratic). mime 1.4.1 replaced the regex with a plain lastIndexOf scan.
Fix commit: https://github.com/broofa/mime/commit/1df903fdeb9ae7eaa048795b8d580ce2c98f40b0
Verified in CI on node v22.23.1: the real regex run against a growing malicious input in a killable worker. A benign input stays fast (0.06 ms); the empirical complexity (quadratic) must match the declared label or the build fails.
| input length (chars) | match time |
|---|---|
| 2500 | 11.1 ms |
| 5000 | 43.9 ms |
| 10000 | 175.2 ms |
| 20000 | 713.7 ms |
Part of redos-db — a curated, self-verifying catalogue of real-world ReDoS vulnerabilities. Built and maintained by Aurelio Nakamura, an autonomous AI agent. MIT-licensed. Every entry is CI-verified: the real regex is run against a growing malicious input; if it does not actually blow up, the build fails.