arrayLimit bypass in bracket notation allows DoS via memory exhaustion

@@ -133,7 +133,12 @@ var parseValues = function parseQueryStringValues(str, options) {
         if (key !== null) {
             var existing = has.call(obj, key);
             if (existing && options.duplicates === 'combine') {
-                obj[key] = utils.combine(obj[key], val);
+                obj[key] = utils.combine(
+                    obj[key],
+                    val,
+                    options.arrayLimit,
+                    options.plainObjects
+                );
             } else if (!existing || options.duplicates === 'last') {
                 obj[key] = val;
             }
@@ -157,9 +162,19 @@ var parseObject = function (chain, val, options, valuesParsed) {
         var root = chain[i];
 
         if (root === '[]' && options.parseArrays) {
-            obj = options.allowEmptyArrays && (leaf === '' || (options.strictNullHandling && leaf === null))
-                ? []
-                : utils.combine([], leaf);
+            if (utils.isOverflow(leaf)) {
+                // leaf is already an overflow object, preserve it
+                obj = leaf;
+            } else {
+                obj = options.allowEmptyArrays && (leaf === '' || (options.strictNullHandling && leaf === null))
+                    ? []
+                    : utils.combine(
+                        [],
+                        leaf,
+                        options.arrayLimit,
+                        options.plainObjects
+                    );
+            }
         } else {
             obj = options.plainObjects ? { __proto__: null } : {};
             var cleanRoot = root.charAt(0) === '[' && root.charAt(root.length - 1) === ']' ? root.slice(1, -1) : root;

@@ -1,10 +1,32 @@
 'use strict';
 
 var formats = require('./formats');
+var getSideChannel = require('side-channel');
 
 var has = Object.prototype.hasOwnProperty;
 var isArray = Array.isArray;
 
+// Track objects created from arrayLimit overflow using side-channel
+// Stores the current max numeric index for O(1) lookup
+var overflowChannel = getSideChannel();
+
+var markOverflow = function markOverflow(obj, maxIndex) {
+    overflowChannel.set(obj, maxIndex);
+    return obj;
+};
+
+var isOverflow = function isOverflow(obj) {
+    return overflowChannel.has(obj);
+};
+
+var getMaxIndex = function getMaxIndex(obj) {
+    return overflowChannel.get(obj);
+};
+
+var setMaxIndex = function setMaxIndex(obj, maxIndex) {
+    overflowChannel.set(obj, maxIndex);
+};
+
 var hexTable = (function () {
     var array = [];
     for (var i = 0; i < 256; ++i) {
@@ -54,7 +76,12 @@ var merge = function merge(target, source, options) {
         if (isArray(target)) {
             target.push(source);
         } else if (target && typeof target === 'object') {
-            if (
+            if (isOverflow(target)) {
+                // Add at next numeric index for overflow objects
+                var newIndex = getMaxIndex(target) + 1;
+                target[newIndex] = source;
+                setMaxIndex(target, newIndex);
+            } else if (
                 (options && (options.plainObjects || options.allowPrototypes))
                 || !has.call(Object.prototype, source)
             ) {
@@ -68,6 +95,18 @@ var merge = function merge(target, source, options) {
     }
 
     if (!target || typeof target !== 'object') {
+        if (isOverflow(source)) {
+            // Create new object with target at 0, source values shifted by 1
+            var sourceKeys = Object.keys(source);
+            var result = options && options.plainObjects
+                ? { __proto__: null, 0: target }
+                : { 0: target };
+            for (var m = 0; m < sourceKeys.length; m++) {
+                var oldKey = parseInt(sourceKeys[m], 10);
+                result[oldKey + 1] = source[sourceKeys[m]];
+            }
+            return markOverflow(result, getMaxIndex(source) + 1);
+        }
         return [target].concat(source);
     }
 
@@ -239,8 +278,20 @@ var isBuffer = function isBuffer(obj) {
     return !!(obj.constructor && obj.constructor.isBuffer && obj.constructor.isBuffer(obj));
 };
 
-var combine = function combine(a, b) {
-    return [].concat(a, b);
+var combine = function combine(a, b, arrayLimit, plainObjects) {
+    // If 'a' is already an overflow object, add to it
+    if (isOverflow(a)) {
+        var newIndex = getMaxIndex(a) + 1;
+        a[newIndex] = b;
+        setMaxIndex(a, newIndex);
+        return a;
+    }
+
+    var result = [].concat(a, b);
+    if (result.length > arrayLimit) {
+        return markOverflow(arrayToObject(result, { plainObjects: plainObjects }), result.length - 1);
+    }
+    return result;
 };
 
 var maybeMap = function maybeMap(val, fn) {
@@ -262,6 +313,7 @@ module.exports = {
     decode: decode,
     encode: encode,
     isBuffer: isBuffer,
+    isOverflow: isOverflow,
     isRegExp: isRegExp,
     maybeMap: maybeMap,
     merge: merge

@@ -235,11 +235,11 @@ test('parse()', function (t) {
         st.deepEqual(qs.parse('a=b&a[0]=c'), { a: ['b', 'c'] });
 
         st.deepEqual(qs.parse('a[1]=b&a=c', { arrayLimit: 20 }), { a: ['b', 'c'] });
-        st.deepEqual(qs.parse('a[]=b&a=c', { arrayLimit: 0 }), { a: ['b', 'c'] });
+        st.deepEqual(qs.parse('a[]=b&a=c', { arrayLimit: 0 }), { a: { 0: 'b', 1: 'c' } });
         st.deepEqual(qs.parse('a[]=b&a=c'), { a: ['b', 'c'] });
 
         st.deepEqual(qs.parse('a=b&a[1]=c', { arrayLimit: 20 }), { a: ['b', 'c'] });
-        st.deepEqual(qs.parse('a=b&a[]=c', { arrayLimit: 0 }), { a: ['b', 'c'] });
+        st.deepEqual(qs.parse('a=b&a[]=c', { arrayLimit: 0 }), { a: { 0: 'b', 1: 'c' } });
         st.deepEqual(qs.parse('a=b&a[]=c'), { a: ['b', 'c'] });
 
         st.end();
@@ -364,7 +364,7 @@ test('parse()', function (t) {
         );
         st.deepEqual(
             qs.parse('a[]=b&a[]&a[]=c&a[]=', { strictNullHandling: true, arrayLimit: 0 }),
-            { a: ['b', null, 'c', ''] },
+            { a: { 0: 'b', 1: null, 2: 'c', 3: '' } },
             'with arrayLimit 0 + array brackets: null then empty string works'
         );
 
@@ -375,7 +375,7 @@ test('parse()', function (t) {
         );
         st.deepEqual(
             qs.parse('a[]=b&a[]=&a[]=c&a[]', { strictNullHandling: true, arrayLimit: 0 }),
-            { a: ['b', '', 'c', null] },
+            { a: { 0: 'b', 1: '', 2: 'c', 3: null } },
             'with arrayLimit 0 + array brackets: empty string then null works'
         );
 
@@ -1288,3 +1288,109 @@ test('qs strictDepth option - non-throw cases', function (t) {
         st.end();
     });
 });
+
+test('DOS', function (t) {
+    var arr = [];
+    for (var i = 0; i < 105; i++) {
+        arr[arr.length] = 'x';
+    }
+    var attack = 'a[]=' + arr.join('&a[]=');
+    var result = qs.parse(attack, { arrayLimit: 100 });
+
+    t.notOk(Array.isArray(result.a), 'arrayLimit is respected: result is an object, not an array');
+    t.equal(Object.keys(result.a).length, 105, 'all values are preserved');
+
+    t.end();
+});
+
+test('arrayLimit boundary conditions', function (t) {
+    t.test('exactly at the limit stays as array', function (st) {
+        var result = qs.parse('a[]=1&a[]=2&a[]=3', { arrayLimit: 3 });
+        st.ok(Array.isArray(result.a), 'result is an array when exactly at limit');
+        st.deepEqual(result.a, ['1', '2', '3'], 'all values present');
+        st.end();
+    });
+
+    t.test('one over the limit converts to object', function (st) {
+        var result = qs.parse('a[]=1&a[]=2&a[]=3&a[]=4', { arrayLimit: 3 });
+        st.notOk(Array.isArray(result.a), 'result is not an array when over limit');
+        st.deepEqual(result.a, { 0: '1', 1: '2', 2: '3', 3: '4' }, 'all values preserved as object');
+        st.end();
+    });
+
+    t.test('arrayLimit 1 with two values', function (st) {
+        var result = qs.parse('a[]=1&a[]=2', { arrayLimit: 1 });
+        st.notOk(Array.isArray(result.a), 'result is not an array');
+        st.deepEqual(result.a, { 0: '1', 1: '2' }, 'both values preserved');
+        st.end();
+    });
+
+    t.end();
+});
+
+test('mixed array and object notation', function (t) {
+    t.test('array brackets with object key - under limit', function (st) {
+        st.deepEqual(
+            qs.parse('a[]=b&a[c]=d'),
+            { a: { 0: 'b', c: 'd' } },
+            'mixing [] and [key] converts to object'
+        );
+        st.end();
+    });
+
+    t.test('array index with object key - under limit', function (st) {
+        st.deepEqual(
+            qs.parse('a[0]=b&a[c]=d'),
+            { a: { 0: 'b', c: 'd' } },
+            'mixing [0] and [key] produces object'
+        );
+        st.end();
+    });
+
+    t.test('plain value with array brackets - under limit', function (st) {
+        st.deepEqual(
+            qs.parse('a=b&a[]=c', { arrayLimit: 20 }),
+            { a: ['b', 'c'] },
+            'plain value combined with [] stays as array under limit'
+        );
+        st.end();
+    });
+
+    t.test('array brackets with plain value - under limit', function (st) {
+        st.deepEqual(
+            qs.parse('a[]=b&a=c', { arrayLimit: 20 }),
+            { a: ['b', 'c'] },
+            '[] combined with plain value stays as array under limit'
+        );
+        st.end();
+    });
+
+    t.test('plain value with array index - under limit', function (st) {
+        st.deepEqual(
+            qs.parse('a=b&a[0]=c', { arrayLimit: 20 }),
+            { a: ['b', 'c'] },
+            'plain value combined with [0] stays as array under limit'
+        );
+        st.end();
+    });
+
+    t.test('multiple plain values with duplicates combine', function (st) {
+        st.deepEqual(
+            qs.parse('a=b&a=c&a=d', { arrayLimit: 20 }),
+            { a: ['b', 'c', 'd'] },
+            'duplicate plain keys combine into array'
+        );
+        st.end();
+    });
+
+    t.test('multiple plain values exceeding limit', function (st) {
+        st.deepEqual(
+            qs.parse('a=b&a=c&a=d', { arrayLimit: 2 }),
+            { a: { 0: 'b', 1: 'c', 2: 'd' } },
+            'duplicate plain keys convert to object when exceeding limit'
+        );
+        st.end();
+    });
+
+    t.end();
+});

@@ -68,6 +68,60 @@ test('merge()', function (t) {
         }
     );
 
+    t.test('with overflow objects (from arrayLimit)', function (st) {
+        st.test('merges primitive into overflow object at next index', function (s2t) {
+            // Create an overflow object via combine
+            var overflow = utils.combine(['a'], 'b', 1, false);
+            s2t.ok(utils.isOverflow(overflow), 'overflow object is marked');
+            var merged = utils.merge(overflow, 'c');
+            s2t.deepEqual(merged, { 0: 'a', 1: 'b', 2: 'c' }, 'adds primitive at next numeric index');
+            s2t.end();
+        });
+
+        st.test('merges primitive into regular object with numeric keys normally', function (s2t) {
+            var obj = { 0: 'a', 1: 'b' };
+            s2t.notOk(utils.isOverflow(obj), 'plain object is not marked as overflow');
+            var merged = utils.merge(obj, 'c');
+            s2t.deepEqual(merged, { 0: 'a', 1: 'b', c: true }, 'adds primitive as key (not at next index)');
+            s2t.end();
+        });
+
+        st.test('merges primitive into object with non-numeric keys normally', function (s2t) {
+            var obj = { foo: 'bar' };
+            var merged = utils.merge(obj, 'baz');
+            s2t.deepEqual(merged, { foo: 'bar', baz: true }, 'adds primitive as key with value true');
+            s2t.end();
+        });
+
+        st.test('merges overflow object into primitive', function (s2t) {
+            // Create an overflow object via combine
+            var overflow = utils.combine([], 'b', 0, false);
+            s2t.ok(utils.isOverflow(overflow), 'overflow object is marked');
+            var merged = utils.merge('a', overflow);
+            s2t.ok(utils.isOverflow(merged), 'result is also marked as overflow');
+            s2t.deepEqual(merged, { 0: 'a', 1: 'b' }, 'creates object with primitive at 0, source values shifted');
+            s2t.end();
+        });
+
+        st.test('merges overflow object with multiple values into primitive', function (s2t) {
+            // Create an overflow object via combine
+            var overflow = utils.combine(['b'], 'c', 1, false);
+            s2t.ok(utils.isOverflow(overflow), 'overflow object is marked');
+            var merged = utils.merge('a', overflow);
+            s2t.deepEqual(merged, { 0: 'a', 1: 'b', 2: 'c' }, 'shifts all source indices by 1');
+            s2t.end();
+        });
+
+        st.test('merges regular object into primitive as array', function (s2t) {
+            var obj = { foo: 'bar' };
+            var merged = utils.merge('a', obj);
+            s2t.deepEqual(merged, ['a', { foo: 'bar' }], 'creates array with primitive and object');
+            s2t.end();
+        });
+
+        st.end();
+    });
+
     t.end();
 });
 
@@ -132,6 +186,71 @@ test('combine()', function (t) {
         st.end();
     });
 
+    t.test('with arrayLimit', function (st) {
+        st.test('under the limit', function (s2t) {
+            var combined = utils.combine(['a', 'b'], 'c', 10, false);
+            s2t.deepEqual(combined, ['a', 'b', 'c'], 'returns array when under limit');
+            s2t.ok(Array.isArray(combined), 'result is an array');
+            s2t.end();
+        });
+
+        st.test('exactly at the limit stays as array', function (s2t) {
+            var combined = utils.combine(['a', 'b'], 'c', 3, false);
+            s2t.deepEqual(combined, ['a', 'b', 'c'], 'stays as array when exactly at limit');
+            s2t.ok(Array.isArray(combined), 'result is an array');
+            s2t.end();
+        });
+
+        st.test('over the limit', function (s2t) {
+            var combined = utils.combine(['a', 'b', 'c'], 'd', 3, false);
+            s2t.deepEqual(combined, { 0: 'a', 1: 'b', 2: 'c', 3: 'd' }, 'converts to object when over limit');
+            s2t.notOk(Array.isArray(combined), 'result is not an array');
+            s2t.end();
+        });
+
+        st.test('with arrayLimit 0', function (s2t) {
+            var combined = utils.combine([], 'a', 0, false);
+            s2t.deepEqual(combined, { 0: 'a' }, 'converts single element to object with arrayLimit 0');
+            s2t.notOk(Array.isArray(combined), 'result is not an array');
+            s2t.end();
+        });
+
+        st.test('with plainObjects option', function (s2t) {
+            var combined = utils.combine(['a'], 'b', 1, true);
+            var expected = { __proto__: null, 0: 'a', 1: 'b' };
+            s2t.deepEqual(combined, expected, 'converts to object with null prototype');
+            s2t.equal(Object.getPrototypeOf(combined), null, 'result has null prototype when plainObjects is true');
+            s2t.end();
+        });
+
+        st.end();
+    });
+
+    t.test('with existing overflow object', function (st) {
+        st.test('adds to existing overflow object at next index', function (s2t) {
+            // Create overflow object first via combine
+            var overflow = utils.combine(['a'], 'b', 1, false);
+            s2t.ok(utils.isOverflow(overflow), 'initial object is marked as overflow');
+
+            var combined = utils.combine(overflow, 'c', 10, false);
+            s2t.equal(combined, overflow, 'returns the same object (mutated)');
+            s2t.deepEqual(combined, { 0: 'a', 1: 'b', 2: 'c' }, 'adds value at next numeric index');
+            s2t.end();
+        });
+
+        st.test('does not treat plain object with numeric keys as overflow', function (s2t) {
+            var plainObj = { 0: 'a', 1: 'b' };
+            s2t.notOk(utils.isOverflow(plainObj), 'plain object is not marked as overflow');
+
+            // combine treats this as a regular value, not an overflow object to append to
+            var combined = utils.combine(plainObj, 'c', 10, false);
+            s2t.deepEqual(combined, [{ 0: 'a', 1: 'b' }, 'c'], 'concatenates as regular values');
+            s2t.end();
+        });
+
+        st.end();
+    });
+
     t.end();
 });