Svelte devalue: DoS via sparse array deserialization

@@ -0,0 +1,5 @@
+---
+'devalue': patch
+---
+
+fix: force sparse arrays to allocate sparsely

@@ -5,3 +5,8 @@ export const POSITIVE_INFINITY = -4;
 export const NEGATIVE_INFINITY = -5;
 export const NEGATIVE_ZERO = -6;
 export const SPARSE = -7;
+
+// The largest valid value for a JavaScript array's `length` property,
+// and the largest valid array index (one less than the max length).
+export const MAX_ARRAY_LEN = 2 ** 32 - 1;
+export const MAX_ARRAY_INDEX = MAX_ARRAY_LEN - 1;

@@ -1,13 +1,15 @@
 import { decode64 } from './base64.js';
 import {
 	HOLE,
+	MAX_ARRAY_INDEX,
 	NAN,
 	NEGATIVE_INFINITY,
 	NEGATIVE_ZERO,
 	POSITIVE_INFINITY,
 	SPARSE,
 	UNDEFINED
 } from './constants.js';
+import { is_valid_array_index, is_valid_array_len } from './utils.js';
 
 /**
  * Revive a value serialized with `devalue.stringify`
@@ -219,22 +221,35 @@ export function unflatten(parsed, revivers) {
 				// Sparse array encoding: [SPARSE, length, idx, val, idx, val, ...]
 				const len = value[1];
 
-				if (!Number.isInteger(len) || len < 0) {
+				if (!is_valid_array_len(len)) {
 					throw new Error('Invalid input');
 				}
 
-				const array = new Array(len);
+				/** @type {any[]} */
+				const array = [];
 				hydrated[index] = array;
 
+				// Setting `array.length = len` (or equivalently calling `new Array(len)`)
+				// on an untrusted `len` is a DoS vector: V8 eagerly allocates a
+				// contiguous backing store for array lengths below ~10^8, so a
+				// small payload with a huge declared length can force arbitrary
+				// memory allocation. Touching the largest-possible index first
+				// forces V8 into dictionary-elements mode, where `length` is
+				// just a number and no contiguous allocation occurs.
+				array[MAX_ARRAY_INDEX] = undefined;
+				delete array[MAX_ARRAY_INDEX];
+
 				for (let i = 2; i < value.length; i += 2) {
 					const idx = value[i];
 
-					if (!Number.isInteger(idx) || idx < 0 || idx >= len) {
+					if (!is_valid_array_index(idx) || idx >= len) {
 						throw new Error('Invalid input');
 					}
 
 					array[idx] = hydrate(value[i + 1]);
 				}
+
+				array.length = len;
 			} else {
 				const array = new Array(value.length);
 				hydrated[index] = array;

@@ -1,3 +1,5 @@
+import { MAX_ARRAY_INDEX, MAX_ARRAY_LEN } from './constants.js';
+
 /** @type {Record<string, string>} */
 export const escaped = {
 	'<': '\\u003C',
@@ -113,19 +115,33 @@ export function stringify_key(key) {
 	return is_identifier.test(key) ? '.' + key : '[' + JSON.stringify(key) + ']';
 }
 
+/** @param {number} n */
+export function is_valid_array_index(n) {
+	if (!Number.isInteger(n)) return false;
+	if (n < 0) return false;
+	if (n > MAX_ARRAY_INDEX) return false;
+	return true;
+}
+
+/** @param {number} n */
+export function is_valid_array_len(n) {
+	if (!Number.isInteger(n)) return false;
+	if (n < 0) return false;
+	if (n > MAX_ARRAY_LEN) return false;
+	return true;
+}
+
 /** @param {string} s */
-function is_valid_array_index(s) {
+function is_valid_array_index_string(s) {
 	if (s.length === 0) return false;
 	if (s.length > 1 && s.charCodeAt(0) === 48) return false; // leading zero
 	for (let i = 0; i < s.length; i++) {
 		const c = s.charCodeAt(i);
 		if (c < 48 || c > 57) return false;
 	}
-	// by this point we know it's a string of digits, but it has to be within the range of valid array indices
-	const n = +s;
-	if (n >= 2 ** 32 - 1) return false;
-	if (n < 0) return false;
-	return true;
+	// by this point we know it's a string of digits, but it has to be within
+	// the range of valid array indices
+	return is_valid_array_index(+s);
 }
 
 /**
@@ -135,7 +151,7 @@ function is_valid_array_index(s) {
 export function valid_array_indices(array) {
 	const keys = Object.keys(array);
 	for (var i = keys.length - 1; i >= 0; i--) {
-		if (is_valid_array_index(keys[i])) {
+		if (is_valid_array_index_string(keys[i])) {
 			break;
 		}
 	}

@@ -1421,6 +1421,83 @@ uvu.test('valid sparse array parses correctly', () => {
 	assert.is(Object.getPrototypeOf(result), Array.prototype);
 });
 
+// Regression test for a DoS vulnerability in sparse array parsing.
+// The SPARSE encoding is `[-7, length, idx, val, ...]`. Previously, `parse`
+// handled this by calling `new Array(length)`, which V8 eagerly allocates
+// a backing store for. A malicious payload containing many such arrays
+// — each claiming a huge length but carrying no actual data — could force
+// the parser to allocate arbitrarily large amounts of memory and crash
+// the host process.
+//
+// Each case below crafts a payload whose combined implied allocation is
+// ~20GB. With a correct fix (lazy allocation / deferred length), every
+// case finishes near-instantly. Without it, the test process dies.
+
+/**
+ * Builds a payload shaped like:
+ *   [ {k0:1, k1:2, ..., k(count-1):count},   // root object, references each sparse array
+ *     [-7, perArrayLen, 0, count+1],         // sparse array #0: length = perArrayLen, index 0 -> values[count+1]
+ *     [-7, perArrayLen, 0, count+1],         // sparse array #1
+ *     ...
+ *     42 ]                                   // values[count+1], placed at index 0 of each sparse array
+ *
+ * Hydrating the root object forces every sparse array to be hydrated,
+ * which (without the fix) triggers `new Array(perArrayLen)` `count` times.
+ *
+ * @param {number} count
+ * @param {number} perArrayLen
+ */
+function buildSparseDoSPayload(count, perArrayLen) {
+	let payload = '[{';
+
+	for (let i = 0; i < count; i += 1) {
+		if (i > 0) payload += ',';
+		payload += `"k${i}":${i + 1}`;
+	}
+
+	payload += '}';
+
+	for (let i = 0; i < count; i += 1) {
+		payload += `,[${consts.SPARSE},${perArrayLen},0,${count + 1}]`;
+	}
+
+	payload += ',42]';
+	return payload;
+}
+
+// Matrix of (perArrayLen, count) pairs — each row allocates ~2.5e9 slots
+// (~20GB assuming 8-byte pointers) if the parser eagerly materializes
+// sparse arrays.
+const sparseDoSCases = [
+	{ perArrayLen: 10_000, count: 250_000 },
+	{ perArrayLen: 100_000, count: 25_000 },
+	{ perArrayLen: 1_000_000, count: 2_500 },
+	{ perArrayLen: 10_000_000, count: 250 },
+	{ perArrayLen: 100_000_000, count: 25 }
+];
+
+for (const { perArrayLen, count } of sparseDoSCases) {
+	uvu.test(`does not eagerly allocate sparse arrays (len=${perArrayLen}, count=${count})`, () => {
+		const payload = buildSparseDoSPayload(count, perArrayLen);
+		const result = parse(payload);
+
+		// The root is the object whose keys reference every sparse array;
+		// accessing them forces hydration of all `count` arrays.
+		assert.is(typeof result, 'object');
+		assert.ok(result !== null);
+
+		// Spot-check the first and last sparse arrays.
+		const first = result.k0;
+		const last = result[`k${count - 1}`];
+		assert.ok(Array.isArray(first));
+		assert.ok(Array.isArray(last));
+		assert.is(first.length, perArrayLen);
+		assert.is(last.length, perArrayLen);
+		assert.is(first[0], 42);
+		assert.is(last[0], 42);
+	});
+}
+
 uvu.test.run();
 
 // --- stringifyAsync tests ---