Skip to content

Commit 206ca67

Browse files
elliott-with-the-longest-name-on-githubelliott-with-the-longest-name-on-github
authored
Merge commit from fork
1 parent 14933f7 commit 206ca67

5 files changed

Lines changed: 128 additions & 10 deletions

File tree

‎.changeset/eleven-files-sort.md‎

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,5 @@
1+
---
2+
'devalue': patch
3+
---
4+
5+
fix: force sparse arrays to allocate sparsely

‎src/constants.js‎

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -5,3 +5,8 @@ export const POSITIVE_INFINITY = -4;
55
export const NEGATIVE_INFINITY = -5;
66
export const NEGATIVE_ZERO = -6;
77
export const SPARSE = -7;
8+
9+
// The largest valid value for a JavaScript array's `length` property,
10+
// and the largest valid array index (one less than the max length).
11+
export const MAX_ARRAY_LEN = 2 ** 32 - 1;
12+
export const MAX_ARRAY_INDEX = MAX_ARRAY_LEN - 1;

‎src/parse.js‎

Lines changed: 18 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -1,13 +1,15 @@
11
import { decode64 } from './base64.js';
22
import {
33
HOLE,
4+
MAX_ARRAY_INDEX,
45
NAN,
56
NEGATIVE_INFINITY,
67
NEGATIVE_ZERO,
78
POSITIVE_INFINITY,
89
SPARSE,
910
UNDEFINED
1011
} from './constants.js';
12+
import { is_valid_array_index, is_valid_array_len } from './utils.js';
1113

1214
/**
1315
* Revive a value serialized with `devalue.stringify`
@@ -219,22 +221,35 @@ export function unflatten(parsed, revivers) {
219221
// Sparse array encoding: [SPARSE, length, idx, val, idx, val, ...]
220222
const len = value[1];
221223

222-
if (!Number.isInteger(len) || len < 0) {
224+
if (!is_valid_array_len(len)) {
223225
throw new Error('Invalid input');
224226
}
225227

226-
const array = new Array(len);
228+
/** @type {any[]} */
229+
const array = [];
227230
hydrated[index] = array;
228231

232+
// Setting `array.length = len` (or equivalently calling `new Array(len)`)
233+
// on an untrusted `len` is a DoS vector: V8 eagerly allocates a
234+
// contiguous backing store for array lengths below ~10^8, so a
235+
// small payload with a huge declared length can force arbitrary
236+
// memory allocation. Touching the largest-possible index first
237+
// forces V8 into dictionary-elements mode, where `length` is
238+
// just a number and no contiguous allocation occurs.
239+
array[MAX_ARRAY_INDEX] = undefined;
240+
delete array[MAX_ARRAY_INDEX];
241+
229242
for (let i = 2; i < value.length; i += 2) {
230243
const idx = value[i];
231244

232-
if (!Number.isInteger(idx) || idx < 0 || idx >= len) {
245+
if (!is_valid_array_index(idx) || idx >= len) {
233246
throw new Error('Invalid input');
234247
}
235248

236249
array[idx] = hydrate(value[i + 1]);
237250
}
251+
252+
array.length = len;
238253
} else {
239254
const array = new Array(value.length);
240255
hydrated[index] = array;

‎src/utils.js‎

Lines changed: 23 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,5 @@
1+
import { MAX_ARRAY_INDEX, MAX_ARRAY_LEN } from './constants.js';
2+
13
/** @type {Record<string, string>} */
24
export const escaped = {
35
'<': '\\u003C',
@@ -113,19 +115,33 @@ export function stringify_key(key) {
113115
return is_identifier.test(key) ? '.' + key : '[' + JSON.stringify(key) + ']';
114116
}
115117

118+
/** @param {number} n */
119+
export function is_valid_array_index(n) {
120+
if (!Number.isInteger(n)) return false;
121+
if (n < 0) return false;
122+
if (n > MAX_ARRAY_INDEX) return false;
123+
return true;
124+
}
125+
126+
/** @param {number} n */
127+
export function is_valid_array_len(n) {
128+
if (!Number.isInteger(n)) return false;
129+
if (n < 0) return false;
130+
if (n > MAX_ARRAY_LEN) return false;
131+
return true;
132+
}
133+
116134
/** @param {string} s */
117-
function is_valid_array_index(s) {
135+
function is_valid_array_index_string(s) {
118136
if (s.length === 0) return false;
119137
if (s.length > 1 && s.charCodeAt(0) === 48) return false; // leading zero
120138
for (let i = 0; i < s.length; i++) {
121139
const c = s.charCodeAt(i);
122140
if (c < 48 || c > 57) return false;
123141
}
124-
// by this point we know it's a string of digits, but it has to be within the range of valid array indices
125-
const n = +s;
126-
if (n >= 2 ** 32 - 1) return false;
127-
if (n < 0) return false;
128-
return true;
142+
// by this point we know it's a string of digits, but it has to be within
143+
// the range of valid array indices
144+
return is_valid_array_index(+s);
129145
}
130146

131147
/**
@@ -135,7 +151,7 @@ function is_valid_array_index(s) {
135151
export function valid_array_indices(array) {
136152
const keys = Object.keys(array);
137153
for (var i = keys.length - 1; i >= 0; i--) {
138-
if (is_valid_array_index(keys[i])) {
154+
if (is_valid_array_index_string(keys[i])) {
139155
break;
140156
}
141157
}

‎test/index.test.js‎

Lines changed: 77 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1421,6 +1421,83 @@ uvu.test('valid sparse array parses correctly', () => {
14211421
assert.is(Object.getPrototypeOf(result), Array.prototype);
14221422
});
14231423

1424+
// Regression test for a DoS vulnerability in sparse array parsing.
1425+
// The SPARSE encoding is `[-7, length, idx, val, ...]`. Previously, `parse`
1426+
// handled this by calling `new Array(length)`, which V8 eagerly allocates
1427+
// a backing store for. A malicious payload containing many such arrays
1428+
// — each claiming a huge length but carrying no actual data — could force
1429+
// the parser to allocate arbitrarily large amounts of memory and crash
1430+
// the host process.
1431+
//
1432+
// Each case below crafts a payload whose combined implied allocation is
1433+
// ~20GB. With a correct fix (lazy allocation / deferred length), every
1434+
// case finishes near-instantly. Without it, the test process dies.
1435+
1436+
/**
1437+
* Builds a payload shaped like:
1438+
* [ {k0:1, k1:2, ..., k(count-1):count}, // root object, references each sparse array
1439+
* [-7, perArrayLen, 0, count+1], // sparse array #0: length = perArrayLen, index 0 -> values[count+1]
1440+
* [-7, perArrayLen, 0, count+1], // sparse array #1
1441+
* ...
1442+
* 42 ] // values[count+1], placed at index 0 of each sparse array
1443+
*
1444+
* Hydrating the root object forces every sparse array to be hydrated,
1445+
* which (without the fix) triggers `new Array(perArrayLen)` `count` times.
1446+
*
1447+
* @param {number} count
1448+
* @param {number} perArrayLen
1449+
*/
1450+
function buildSparseDoSPayload(count, perArrayLen) {
1451+
let payload = '[{';
1452+
1453+
for (let i = 0; i < count; i += 1) {
1454+
if (i > 0) payload += ',';
1455+
payload += `"k${i}":${i + 1}`;
1456+
}
1457+
1458+
payload += '}';
1459+
1460+
for (let i = 0; i < count; i += 1) {
1461+
payload += `,[${consts.SPARSE},${perArrayLen},0,${count + 1}]`;
1462+
}
1463+
1464+
payload += ',42]';
1465+
return payload;
1466+
}
1467+
1468+
// Matrix of (perArrayLen, count) pairs — each row allocates ~2.5e9 slots
1469+
// (~20GB assuming 8-byte pointers) if the parser eagerly materializes
1470+
// sparse arrays.
1471+
const sparseDoSCases = [
1472+
{ perArrayLen: 10_000, count: 250_000 },
1473+
{ perArrayLen: 100_000, count: 25_000 },
1474+
{ perArrayLen: 1_000_000, count: 2_500 },
1475+
{ perArrayLen: 10_000_000, count: 250 },
1476+
{ perArrayLen: 100_000_000, count: 25 }
1477+
];
1478+
1479+
for (const { perArrayLen, count } of sparseDoSCases) {
1480+
uvu.test(`does not eagerly allocate sparse arrays (len=${perArrayLen}, count=${count})`, () => {
1481+
const payload = buildSparseDoSPayload(count, perArrayLen);
1482+
const result = parse(payload);
1483+
1484+
// The root is the object whose keys reference every sparse array;
1485+
// accessing them forces hydration of all `count` arrays.
1486+
assert.is(typeof result, 'object');
1487+
assert.ok(result !== null);
1488+
1489+
// Spot-check the first and last sparse arrays.
1490+
const first = result.k0;
1491+
const last = result[`k${count - 1}`];
1492+
assert.ok(Array.isArray(first));
1493+
assert.ok(Array.isArray(last));
1494+
assert.is(first.length, perArrayLen);
1495+
assert.is(last.length, perArrayLen);
1496+
assert.is(first[0], 42);
1497+
assert.is(last[0], 42);
1498+
});
1499+
}
1500+
14241501
uvu.test.run();
14251502

14261503
// --- stringifyAsync tests ---

0 commit comments

Comments
 (0)