Immutable.js List 32-bit trie overflow → unrecoverable DoS
Summary
List#set, List#setSize, List#setIn, List#updateIn (and the functional set / setIn / updateIn) mishandle an index or size in the range [2 30, 2 31):
- On an empty
List the operation enters an uncatchable infinite loop (a tight CPU spin; a surrounding try/catch never regains control). Only killing the worker recovers it. - On a populated
List (≥ 32 elements — i.e. any array of ≥ 32 items turned into a List by fromJS) the loop allocates without bound → heap exhaustion → the process aborts (SIGABRT, exit 134, or kernel OOM-kill 137). A real crash, not a recoverable error.
The index may be a numeric string, so it can come straight from a request body, URL, or key-path. A single small unauthenticated request is enough.
There is also a companion silent data-corruption issue in setSize:
```js
List([1, 2, 3]).setSize(2 ** 31); // before fix => size 0 (silently cleared)
List([1, 2, 3]).setSize(2 ** 32 + 5); // before fix => size 5 (huge value wraps to 5)
```
Impact
Availability only. A reachable configuration is any endpoint that routes untrusted input into a List index or a setIn/updateIn key-path — which the extremely common state = fromJS(body); state.setIn(userPath, value) pattern does (config stores, document/collection editors, redux-immutable reducers, JSON-Patch endpoints, etc.).
No confidentiality or integrity impact, no RCE. The companion setSize bug can silently corrupt application state (wrong size) without crashing.
Reproduction (immutable 5.1.7)
```ts
import { fromJS, List } from 'immutable';
// 1) Populated List: OOM -> process abort (SIGABRT, exit 134) within ~2s
fromJS({ items: new Array(64).fill(0) }).setIn(['items', '1073741824'], 'x');
// 2) Empty List: hangs forever, uncatchable
List().set(2 ** 30, 'x');
// 3) Silent truncation
List([1, 2, 3]).setSize(2 ** 31); // => size 0
List([1, 2, 3]).setSize(2 ** 32 + 5); // => size 5
```
A remote 43-byte HTTP request ({"path":["items","1073741824"],"value":"x"}) is sufficient to abort a worker that applies it via state = state.setIn(path, value).
Any index in [2 30, 2 31) works (1073741824, 2000000000, …). An index in [2 31, 2 32) does not crash — it silently wraps (clearing the List) via the same root cause.
Root cause
List stores its values in a 32-wide trie (SHIFT = 5, so each level addresses 5 more bits) and uses signed 32-bit bitwise arithmetic throughout setListBounds() (src/List.js):
1. Infinite loop (the hang / OOM). The level-raising loop
```js
while (newTailOffset >= 1 << (newLevel + SHIFT)) {
newRoot = new VNode(
newRoot && newRoot.array.length ? [newRoot] : [],
owner
);
newLevel += SHIFT;
}
```
relies on 1 << (newLevel + SHIFT). A JavaScript shift count is taken mod 32, so once newLevel + SHIFT reaches 31 the term goes negative (1 << 31 === -2147483648) and at 32 wraps to 1 (1 << 35 === 8). The comparison then stays true forever and the loop never terminates. On a populated List, each iteration retains a new VNode ([newRoot]), so the heap fills and V8 aborts; on an empty List it spins on CPU without allocating.
2. Silent wraparound (the setSize corruption). The begin |= 0 / end |= 0 coercion (ToInt32) silently wraps large finite values ((2 31) | 0 === -2147483648, (2 32 + 5) | 0 === 5), producing a wrong resulting size instead of an error.
The threshold is 2 ** 30: that is the largest size for which 1 << (newLevel + SHIFT) stays a valid positive 32-bit integer throughout the loops (newLevel + SHIFT stays ≤ 30).
Remediation
The fix is contained to setListBounds() in src/List.js:
1. Validate up front, before the lossy | 0 coercion. Compute the intended origin and capacity in full precision and throw a clear, catchable RangeError when they exceed the addressable range (MAX_LIST_SIZE = 2 ** 30). Infinity/NaN are left to the existing | 0 → 0 behaviour (so setSize(Infinity) stays 0 and slice(0, Infinity) still means "to the end").
2. Stop the shift from wrapping. Replace 1 << exp in the level-raising loops with a helper that uses the cheap bitwise shift while it is exact (exp ≤ 30, the common path including every push/setSize/slice) and falls back to the non-wrapping 2 ** exp only for the rare deep trees reached when a negative origin (unshift / negative index) is normalized to a large positive capacity (exp can reach 35 there, where 1 << 35 would wrap to 8).
This turns every hang, the misleading "Maximum call stack size exceeded", the OOM/SIGABRT, and the silent setSize truncation into one descriptive RangeError, preserves all behaviour for sizes < 2 30, and keeps the hot push path on the fast bitwise shift (the 2 exp branch is never reached by non-negative operations).
Is the new
