Skip to content

Commit 1e30c93

Browse files
juliangruberG-Rath
juliangruber
and
G-Rath
authored
Merge commit from fork
* test: backport * fix: bound expansion length across comma alternatives and sequences * fix: don't count dropped empties against `max` Capping the intermediate `values` array at `max` entries counted alternatives that `combine` goes on to drop as empty, so `max` stopped bounding the number of *kept* results: `expand('{a,,b}', { max: 2 })` returned `['a']` where it used to return `['a', 'b']`. Skip those values rather than counting them. The cap itself stays - it is what bounds the array when the values are empty and so contribute no characters for `maxLength` to see. --------- Co-authored-by: Gareth Jones <3151613+G-Rath@users.noreply.github.com>
1 parent 878df39 commit 1e30c93

2 files changed

Lines changed: 126 additions & 4 deletions

File tree

‎index.js‎

Lines changed: 30 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -145,7 +145,8 @@ function combine(
145145
function expandSequence(
146146
body,
147147
isAlphaSequence,
148-
max
148+
max,
149+
maxLength
149150
) {
150151
var n = body.split(/\.\./)
151152
var N = []
@@ -171,6 +172,7 @@ function expandSequence(
171172
}
172173
var pad = n.some(isPadded)
173174

175+
var length = 0
174176
for (var i = x; test(i, y) && N.length < max; i += incr) {
175177
var c
176178
if (isAlphaSequence) {
@@ -192,7 +194,9 @@ function expandSequence(
192194
}
193195
}
194196
}
197+
if (length + c.length > maxLength) break
195198
N.push(c)
199+
length += c.length
196200
}
197201
return N
198202
}
@@ -273,7 +277,7 @@ function expand(
273277

274278
var values;
275279
if (isSequence) {
276-
values = expandSequence(m.body, isAlphaSequence, max);
280+
values = expandSequence(m.body, isAlphaSequence, max, maxLength);
277281
} else {
278282
var n = parseCommaParts(m.body);
279283
if (n.length === 1 && n[0] !== undefined) {
@@ -297,9 +301,31 @@ function expand(
297301
/* c8 ignore stop */
298302
}
299303

304+
// Values that `combine` is going to drop as empty produce no result, so
305+
// they must not count against `max` - otherwise `{a,,b}` with `max: 2`
306+
// would stop at `['a', '']` and yield one result instead of two. Skipping
307+
// them outright keeps `values` bounded while leaving `max` a bound on
308+
// *kept* results.
309+
var dropsEmpties = dropEmpties && !m.post.length && !pre
310+
for (var d = 0; dropsEmpties && d < acc.length; d++) {
311+
if (acc[d]) {
312+
dropsEmpties = false
313+
}
314+
}
315+
300316
values = []
301-
for (var j = 0; j < n.length; j++) {
302-
values.push.apply(values, expand(n[j], max, maxLength, false))
317+
var valuesLength = 0
318+
outer: for (var j = 0; j < n.length; j++) {
319+
var expanded = expand(n[j], max, maxLength, false)
320+
for (var k = 0; k < expanded.length; k++) {
321+
var v = expanded[k]
322+
if (dropsEmpties && !v) continue
323+
if (values.length >= max || valuesLength + v.length > maxLength) {
324+
break outer
325+
}
326+
values.push(v)
327+
valuesLength += v.length
328+
}
303329
}
304330
}
305331

‎test/ghsa-rgw5-rvv9-x895.js‎

Lines changed: 96 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,96 @@
1+
var test = require('tape');
2+
var expand = require('..');
3+
4+
// Bypass of CVE-2026-14257's mitigation: each comma-separated alternative
5+
// (`{alt,alt,...}`) is expanded independently, and `maxLength` only bounded
6+
// each alternative's own output, not the running total accumulated across
7+
// all of them. Many alternatives - each individually far under `maxLength` -
8+
// could still sum to an unbounded intermediate array before the final
9+
// `combine` call ever got a chance to truncate.
10+
test('total length across comma alternatives is bounded', async t => {
11+
var alt = '{1..5}'
12+
var str = '{' + Array(1000).fill(alt).join(',') + '}'
13+
var startTime = performance.now()
14+
var expanded = expand(str, { maxLength: 50 })
15+
var endTime = performance.now()
16+
17+
var totalLength = expanded.reduce((sum, s) => sum + s.length, 0)
18+
t.ok(
19+
totalLength <= 50,
20+
`Expected total length (${totalLength}) to respect maxLength`,
21+
)
22+
t.ok(expanded.length > 0, 'still returns a (truncated) result')
23+
t.ok(
24+
endTime - startTime < 500,
25+
`Expected time (${endTime - startTime}ms) to be less than 500ms`,
26+
)
27+
28+
// Regression case from the report: 400 alternatives, each individually
29+
// bounded by maxLength but unbounded in aggregate before the fix.
30+
var part = '{' + '0'.repeat(50) + '1..100000}'
31+
var bigStr = '{' + Array(400).fill(part).join(',') + '}'
32+
t.doesNotThrow(() => {
33+
var bigExpanded = expand(bigStr)
34+
var bigTotal = bigExpanded.reduce((sum, s) => sum + s.length, 0)
35+
t.ok(
36+
bigTotal <= 4_000_000,
37+
`Expected total length (${bigTotal}) to stay bounded`,
38+
)
39+
})
40+
41+
t.end();
42+
})
43+
44+
// A padded sequence's element width follows the input, so generating all `max`
45+
// elements before `combine` could discard them cost time proportional to
46+
// `max * width` - a ~400KB input blocked the event loop for over two minutes.
47+
test('padded sequences respect maxLength while generating', async t => {
48+
var str = '{' + '0'.repeat(400_000) + '1..100000}'
49+
var startTime = performance.now()
50+
var expanded = expand(str)
51+
var elapsed = performance.now() - startTime
52+
53+
var totalLength = expanded.reduce((sum, s) => sum + s.length, 0)
54+
t.ok(
55+
totalLength <= 4_000_000,
56+
`Expected total length (${totalLength}) to stay bounded`,
57+
)
58+
t.ok(expanded.length > 0, 'still returns a (truncated) result')
59+
t.ok(
60+
elapsed < 2000,
61+
`Expected time (${elapsed}ms) to be less than 2000ms`,
62+
)
63+
64+
// Truncating early must not change results that fit within the bound.
65+
t.same(
66+
expand('{01..10}'),
67+
['01', '02', '03', '04', '05', '06', '07', '08', '09', '10'],
68+
'padded sequences under the bound are unaffected',
69+
)
70+
71+
t.end();
72+
})
73+
74+
// Bounding the intermediate `values` array must not change what `max` counts:
75+
// alternatives that expand to nothing are dropped by `combine`, so they cost a
76+
// slot in `values` but never a result.
77+
test('max bounds the number of kept results', async t => {
78+
t.same(
79+
expand('{a,,b}', { max: 2 }),
80+
['a', 'b'],
81+
'dropped empty alternatives do not count against max',
82+
)
83+
t.same(
84+
expand('{a,,,b,c}', { max: 3 }),
85+
['a', 'b', 'c'],
86+
'consecutive empty alternatives do not count against max',
87+
)
88+
// Here the empties survive as `xy`, so they are results and do count.
89+
t.same(
90+
expand('x{a,,b}y', { max: 2 }),
91+
['xay', 'xy'],
92+
'kept empty alternatives still count against max',
93+
)
94+
95+
t.end();
96+
})

0 commit comments

Comments
 (0)