Vulnerability Instance

Underscore has unlimited recursion in _.flatten and _.isEqual, potential for DoS attack
### Impact

In simple words, some programs that use `_.flatten` or `_.isEqual` could be made to crash. Someone who wants to do harm may be able to do this on purpose. This can only be done if the program has special properties. It only works in Underscore versions up to 1.13.7. A more detailed explanation follows.

In affected versions of Underscore, the `_.flatten` and `_.isEqual` functions use recursion without a depth limit. Under very specific conditions, detailed below, an attacker could exploit this in a Denial of Service (DoS) attack by triggering a stack overflow.

A proof of concept (PoC) for this type of attack with `_.isEqual`:

```js
const _ = require('underscore');

// build JSON string for nested object ~4500 levels deep
// (for this to be an attack, the JSON would have to come from
// a request or other untrusted input)
let json = '';
for (let i = 0; i < 4500; i++) json += '{"n":';
json += '"x"';
for (let i = 0; i < 4500; i++) json += '}';

// construct two distinct objects with equal shape from the above JSON
const a = JSON.parse(json);
const b = JSON.parse(json);

_.isEqual(a, b); // RangeError: Maximum call stack size exceeded
```

A proof of concept (PoC) for this type of attack with `_.flatten`:

```js
const _ = require('underscore');

// build nested array ~4500 levels deep
// (like with _.isEqual, this nested array would have to be sourced
// from an untrusted external source for it to be an attack)
let nested = [];
for (let i = 0; i < 4500; i++) nested = [nested];

_.flatten(nested); // RangeError: Maximum call stack size exceeded
```

An application that crashes because of this can be restarted, so the bug is most relevant to applications for which continued operation is important, such as server applications. Furthermore, an application is only vulnerable to this type of attack if ALL of the following conditions are met:

- Untrusted input must be used to create a recursive datastructure, for example using `JSON.parse`, with no enforced depth limit.
- The datastructure thus created must be passed to `_.flatten` or `_.isEqual`.
- In the case of `_.flatten`, the vulnerability can only be exploited if it is possible for a remote client to prepare a datastructure that consists of arrays at all levels AND if no finite depth limit is passed as the second argument to `_.flatten`.
- In the case of `_.isEqual`, the vulnerability can only be exploited if there exists a code path in which two distinct datastructures that were submitted by the same remote client are compared using `_.isEqual`. For example, if a client submits data that are stored in a database, and the same client can later submit another datastructure that is then compared to the data that were saved in the database previously, OR if a client submits a single request, but its data are parsed twice, creating two non-identical but equivalent datastructures that are then compared.
- Exceptions originating from the call to `_.flatten` or `_.isEqual`, as a result of a stack overflow, are not being caught.

All versions of Underscore up to and including 1.13.7 are affected by this weakness.

### Patches

The problem has been patched in version 1.13.8. Upgrading to 1.13.8 or later completely prevents exploitation.

**Note:** historically, there have been breaking changes in minor releases of Underscore, especially between versions 1.6 and 1.9. However, upgrading from version 1.9 or later to any later 1.x version should be feasible with little or no effort for all users.

### Workarounds

A workaround that works for both functions is to enforce a depth limit on the datastructure that is created from untrusted input. A limit of 1000 levels should prevent attacks from being successful on most systems. In systems with highly constrained hardware, we recommend lower limits, for example 100 levels.

Another possible workaround that only works for `_.flatten`, is to pass a second argument that limits the flattening depth to 1000 or less.

### References

- https://github.com/jashkenas/underscore/issues/3011
- https://underscorejs.org/#1.13.8
- https://underscorejs.org/#flatten
- https://underscorejs.org/#isEqual