Skip to content

Commit cb4b9e4

Browse files
G-Rathjuliangruber
andauthored
fix: backport GHSA-mh99-v99m-4gvg (#129)
* fix: default to a `max` of `100000` * fix: backport GHSA-mh99-v99m-4gvg * test: adopt the bounded default max on v1 The backport changes the default `max` from `Infinity` to `EXPANSION_MAX` (100,000), matching v5. `test/sequence.js` still asserted the old unbounded behaviour, so the suite was red. Update both assertions to the capped default and add a single-sequence case exercising the cap. Otherwise keep 1.x's observable behaviour untouched, so this ships the vulnerability fixes and nothing else. Two places had drifted: `${` no longer suppressed expansion of the rest of the string. Expanding the tail matches bash and the 2.x and 5.x lines, but it is a breaking change for 1.x, so return the remainder as a single literal as before - routed through `combine`, so `max` and `maxLength` still bound it. `test/dollar.js` only covered inputs where every group is `${`-prefixed and so could not detect this; widen it. Empty results were dropped against the whole string rather than against the current run. The old implementation recursed on `m.post`, so the drop tested only the expansion of the call's own substring, and the `{a},b}` rewrite starts a fresh such run part-way through a string by turning `isTop` back on. Collapsing that recursion into one accumulator lost the distinction, so `{a,b}{},}` gained two results. Track how much of each accumulator entry predates the current run and drop against that. Also fix the `maxLength` README example, which used a budget of 100 against ~1500-character expansions and so documented a result that is actually `[]`, and note that `expand` takes options in the API heading. --------- Co-authored-by: Julian Gruber <[email protected]>
1 parent 447763a commit cb4b9e4

5 files changed

Lines changed: 344 additions & 83 deletions

File tree

‎README.md‎

Lines changed: 23 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -51,11 +51,33 @@ expand('ppp{,config,oe{,conf}}')
5151
var expand = require('brace-expansion');
5252
```
5353

54-
### var expanded = expand(str)
54+
### var expanded = expand(str, [options])
5555

5656
Return an array of all possible and valid expansions of `str`. If none are
5757
found, `[str]` is returned.
5858

59+
The `options` object can provide a `max` value to cap the number
60+
of expansions allowed. This is limited to `100_000` by default,
61+
to prevent DoS attacks.
62+
63+
```js
64+
const expansions = expand('{1..100}'.repeat(5), {
65+
max: 100,
66+
})
67+
// expansions.length will be 100, not 100^5
68+
```
69+
70+
The `options` object can also provide a `maxLength` value to cap the
71+
total number of characters across all expansions. This is limited to
72+
`4_000_000` by default, to prevent memory exhaustion from inputs whose
73+
result count stays under `max` while each result grows very long.
74+
75+
```js
76+
const expansions = expand('{a,b}'.repeat(1500), {
77+
maxLength: 10_000,
78+
})
79+
```
80+
5981
Valid expansions are:
6082

6183
```js

‎index.js‎

Lines changed: 226 additions & 80 deletions
Original file line numberDiff line numberDiff line change
@@ -9,6 +9,20 @@ var escClose = '\0CLOSE'+Math.random()+'\0';
99
var escComma = '\0COMMA'+Math.random()+'\0';
1010
var escPeriod = '\0PERIOD'+Math.random()+'\0';
1111

12+
var EXPANSION_MAX = 100000
13+
14+
// `EXPANSION_MAX` caps the *number* of expansions, but not their length. An
15+
// input like `'{a,b}'.repeat(1500)` stays under that count - its output is
16+
// truncated to 100k results - while making every result ~1500 characters
17+
// long. The result set, and the intermediate arrays built while combining
18+
// brace sets, then grow large enough to exhaust memory and crash the process
19+
// (CVE-2026-14257). `EXPANSION_MAX_LENGTH` bounds the total number of
20+
// characters the accumulator may hold at any point, so memory stays flat no
21+
// matter how many brace groups are chained. The limit sits well above any
22+
// realistic expansion (100k results hitting `EXPANSION_MAX` measure ~1M
23+
// characters) so legitimate input is unaffected.
24+
var EXPANSION_MAX_LENGTH = 4000000
25+
1226
function numeric(str) {
1327
return parseInt(str, 10) == str
1428
? parseInt(str, 10)
@@ -67,7 +81,8 @@ function expandTop(str, options) {
6781
return [];
6882

6983
options = options || {};
70-
var max = options.max == null ? Infinity : options.max;
84+
var max = options.max == null ? EXPANSION_MAX : options.max;
85+
var maxLength = options.maxLength == null ? EXPANSION_MAX_LENGTH : options.maxLength;
7186

7287
// I don't know why Bash 4.3 does this, but it does.
7388
// Anything starting with {} will have the first two bytes preserved
@@ -79,7 +94,7 @@ function expandTop(str, options) {
7994
str = '\\{\\}' + str.substr(2);
8095
}
8196

82-
return expand(escapeBraces(str), max, true).map(unescapeBraces);
97+
return expand(escapeBraces(str), max, maxLength, true).map(unescapeBraces);
8398
}
8499

85100
function identity(e) {
@@ -100,15 +115,151 @@ function gte(i, y) {
100115
return i >= y;
101116
}
102117

103-
function expand(str, max, isTop) {
104-
var expansions = [];
118+
// Build `{ acc[a] + pre + values[v] }` for every combination, capping the
119+
// number of results at `max` and the total number of characters at `maxLength`.
120+
// This is the one place output grows, so bounding it here keeps the single
121+
// accumulator - and therefore memory - flat regardless of how many brace groups
122+
// are combined (CVE-2026-14257).
123+
//
124+
// `base[a]` is the length of the part of `acc[a]` that predates the current
125+
// empty-drop baseline (see `expand`). The matching baselines for the results
126+
// are appended to `outBase`, which the caller carries forward alongside them.
127+
function combine(
128+
acc,
129+
base,
130+
pre,
131+
values,
132+
max,
133+
maxLength,
134+
dropEmpties,
135+
outBase
136+
) {
137+
var out = []
138+
var length = 0
139+
for (var a = 0; a < acc.length; a++) {
140+
for (var v = 0; v < values.length; v++) {
141+
if (out.length >= max) return out
142+
var expansion = acc[a] + pre + values[v]
143+
// Bash drops empty results at the top level. Skip them before they count
144+
// against `max`, so `max` bounds the number of *kept* results. "Empty"
145+
// means "adds nothing past the baseline", not "empty overall".
146+
if (dropEmpties && expansion.length === base[a]) continue
147+
if (length + expansion.length > maxLength) return out
148+
out.push(expansion)
149+
outBase.push(base[a])
150+
length += expansion.length
151+
}
152+
}
153+
return out
154+
}
155+
156+
// The expansion values of a single numeric (`1..5`) or alphabetic (`a..e..2`)
157+
// sequence body.
158+
function expandSequence(
159+
body,
160+
isAlphaSequence,
161+
max
162+
) {
163+
var n = body.split(/\.\./)
164+
var N = []
165+
// A sequence body always splits into two or three parts, but the compiler
166+
// can't know that.
167+
/* c8 ignore start */
168+
if (n[0] === undefined || n[1] === undefined) {
169+
return N
170+
}
171+
/* c8 ignore stop */
172+
var x = numeric(n[0])
173+
var y = numeric(n[1])
174+
var width = Math.max(n[0].length, n[1].length)
175+
var incr =
176+
n.length === 3 && n[2] !== undefined ?
177+
Math.max(Math.abs(numeric(n[2])), 1)
178+
: 1
179+
var test = lte
180+
var reverse = y < x
181+
if (reverse) {
182+
incr *= -1
183+
test = gte
184+
}
185+
var pad = n.some(isPadded)
186+
187+
for (var i = x; test(i, y) && N.length < max; i += incr) {
188+
var c
189+
if (isAlphaSequence) {
190+
c = String.fromCharCode(i)
191+
if (c === '\\') {
192+
c = ''
193+
}
194+
} else {
195+
c = String(i)
196+
if (pad) {
197+
var need = width - c.length
198+
if (need > 0) {
199+
var z = new Array(need + 1).join('0')
200+
if (i < 0) {
201+
c = '-' + z + c.slice(1)
202+
} else {
203+
c = z + c
204+
}
205+
}
206+
}
207+
}
208+
N.push(c)
209+
}
210+
return N
211+
}
212+
213+
function expand(
214+
str,
215+
max,
216+
maxLength,
217+
isTop
218+
) {
219+
// Consume the string's top-level brace groups left to right, threading a
220+
// running set of combined prefixes (`acc`). Expanding the tail iteratively -
221+
// rather than recursing on `m.post` once per group - keeps the native stack
222+
// depth constant, so deeply chained input (`'{a,b}'.repeat(3000)`) can no
223+
// longer overflow the stack, and leaves a single accumulator whose size
224+
// `maxLength` bounds directly (CVE-2026-14257).
225+
var acc = ['']
226+
227+
// Bash drops empty results, but only when the *first* group of the run is a
228+
// comma set - a sequence like `{a..\}` may legitimately yield ''. The drop
229+
// is on the final strings, so it is applied to whichever `combine` produces
230+
// them (the one with no brace set left in the tail).
231+
//
232+
// The old implementation recursed on `m.post`, so the drop tested only the
233+
// expansion of the current call's substring. The `{a},b}` rewrite below turns
234+
// `isTop` back on part-way through a string, starting a fresh such run, so
235+
// the drop must ignore whatever `acc` already holds from earlier groups.
236+
// `accBase[a]` records how much of `acc[a]` predates the current run;
237+
// `combine` treats an expansion as empty when it adds nothing past that.
238+
var accBase = [0]
239+
var dropEmpties = false
240+
var firstGroup = true
241+
var nextBase
105242

106-
// The `{a},b}` rewrite below restarts expansion on a rewritten string with
107-
// the same `max` and `isTop = true`. Loop instead of recursing so a long run
108-
// of non-expanding `{}` groups can't exhaust the call stack.
109243
for (;;) {
110244
var m = balanced('{', '}', str);
111-
if (!m || /\$$/.test(m.pre)) return [str];
245+
246+
// No brace set left: the rest of the string is literal.
247+
if (!m) {
248+
return combine(acc, accBase, str, [''], max, maxLength, dropEmpties, [])
249+
}
250+
251+
// no need to expand pre, since it is guaranteed to be free of brace-sets
252+
var pre = m.pre;
253+
254+
// For compatibility reasons, `${` is not eligible for brace expansion, and
255+
// on the 1.x line it suppresses expansion of the rest of the string too:
256+
// the whole remainder is literal. The 2.x and 5.x lines instead keep
257+
// expanding the tail, which is what bash does, but changing that here would
258+
// be a breaking change for 1.x consumers. Routed through `combine` so the
259+
// result is still bounded by `max` and `maxLength`.
260+
if (/\$$/.test(pre)) {
261+
return combine(acc, accBase, str, [''], max, maxLength, dropEmpties, [])
262+
}
112263

113264
var isNumericSequence = /^-?\d+\.\.-?\d+(?:\.\.-?\d+)?$/.test(m.body);
114265
var isAlphaSequence = /^[a-zA-Z]\.\.[a-zA-Z](?:\.\.-?\d+)?$/.test(m.body);
@@ -118,92 +269,87 @@ function expand(str, max, isTop) {
118269
// {a},b}
119270
if (m.post.match(/,(?!,).*\}/)) {
120271
str = m.pre + '{' + m.body + escClose + m.post;
272+
// The rewritten string is expanded as if it were a fresh top-level one,
273+
// so start a new empty-drop run: anchor the baseline at what `acc`
274+
// holds now, and let the next expanding group decide whether to drop.
121275
isTop = true
276+
firstGroup = true
277+
dropEmpties = false
278+
accBase = []
279+
for (var b = 0; b < acc.length; b++) {
280+
accBase.push(acc[b].length)
281+
}
122282
continue
123283
}
124-
return [str];
284+
// Nothing here expands, so the whole remaining string is literal.
285+
return combine(
286+
acc,
287+
accBase,
288+
pre + '{' + m.body + '}' + m.post,
289+
[''],
290+
max,
291+
maxLength,
292+
dropEmpties,
293+
[]
294+
)
295+
}
296+
297+
if (firstGroup) {
298+
dropEmpties = isTop && !isSequence
299+
firstGroup = false
125300
}
126301

127-
var n;
302+
var values;
128303
if (isSequence) {
129-
n = m.body.split(/\.\./);
304+
values = expandSequence(m.body, isAlphaSequence, max);
130305
} else {
131-
n = parseCommaParts(m.body);
132-
if (n.length === 1) {
306+
var n = parseCommaParts(m.body);
307+
if (n.length === 1 && n[0] !== undefined) {
133308
// x{{a,b}}y ==> x{a}y x{b}y
134-
n = expand(n[0], max, false).map(embrace);
309+
n = expand(n[0], max, maxLength, false).map(embrace);
310+
//XXX is this necessary? Can't seem to hit it in tests.
311+
/* c8 ignore start */
135312
if (n.length === 1) {
136-
var post = m.post.length
137-
? expand(m.post, max, false)
138-
: [''];
139-
return post.map(function(p) {
140-
return m.pre + n[0] + p;
141-
});
142-
}
143-
}
144-
}
145-
146-
// at this point, n is the parts, and we know it's not a comma set
147-
// with a single entry.
148-
149-
// no need to expand pre, since it is guaranteed to be free of brace-sets
150-
var pre = m.pre;
151-
var post = m.post.length
152-
? expand(m.post, max, false)
153-
: [''];
154-
155-
var N;
156-
157-
if (isSequence) {
158-
var x = numeric(n[0]);
159-
var y = numeric(n[1]);
160-
var width = Math.max(n[0].length, n[1].length)
161-
var incr = n.length == 3
162-
? Math.max(Math.abs(numeric(n[2])), 1)
163-
: 1;
164-
var test = lte;
165-
var reverse = y < x;
166-
if (reverse) {
167-
incr *= -1;
168-
test = gte;
169-
}
170-
var pad = n.some(isPadded);
171-
172-
N = [];
173-
174-
for (var i = x; test(i, y) && N.length < max; i += incr) {
175-
var c;
176-
if (isAlphaSequence) {
177-
c = String.fromCharCode(i);
178-
if (c === '\\')
179-
c = '';
180-
} else {
181-
c = String(i);
182-
if (pad) {
183-
var need = width - c.length;
184-
if (need > 0) {
185-
var z = new Array(need + 1).join('0');
186-
if (i < 0)
187-
c = '-' + z + c.slice(1);
188-
else
189-
c = z + c;
190-
}
191-
}
313+
nextBase = []
314+
acc = combine(
315+
acc,
316+
accBase,
317+
pre + n[0],
318+
[''],
319+
max,
320+
maxLength,
321+
dropEmpties && !m.post.length,
322+
nextBase
323+
)
324+
accBase = nextBase
325+
if (!m.post.length) break
326+
str = m.post
327+
continue
192328
}
193-
N.push(c);
329+
/* c8 ignore stop */
194330
}
195-
} else {
196-
N = concatMap(n, function(el) { return expand(el, max, false) });
197-
}
198331

199-
for (var j = 0; j < N.length; j++) {
200-
for (var k = 0; k < post.length && expansions.length < max; k++) {
201-
var expansion = pre + N[j] + post[k];
202-
if (!isTop || isSequence || expansion)
203-
expansions.push(expansion);
332+
values = []
333+
for (var j = 0; j < n.length; j++) {
334+
values.push.apply(values, expand(n[j], max, maxLength, false))
204335
}
205336
}
206337

207-
return expansions;
338+
nextBase = []
339+
acc = combine(
340+
acc,
341+
accBase,
342+
pre,
343+
values,
344+
max,
345+
maxLength,
346+
dropEmpties && !m.post.length,
347+
nextBase
348+
)
349+
accBase = nextBase
350+
if (!m.post.length) break
351+
str = m.post
208352
}
353+
354+
return acc
209355
}

0 commit comments

Comments
 (0)