612837 - Crash in array_unshift due to integer overflow

Status: RESOLVED WORKSFORME

(Core :: JavaScript Engine, defect)

Description

[Christian Holler (:decoder)]

User-Agent:       Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.9.2.12) Gecko/20101027 Ubuntu/10.10 (maverick) Firefox/3.6.12
Build Identifier: Mozilla/5.0 (X11; Linux i686; rv:2.0b6) Gecko/20100101 Firefox/4.0b6

Hello. We haven't put this into a security advisory yet because we are unsure about the impact, we believe the issue to be not exploitable:

In Firefox 4 (verified with b7), the function array_unshift suffers from an integer overflow when calculating the new length (length + argc). When allocating an array of size 2^32 - 1 and then unshifting one element, the function ensureDenseArrayElements is called in line 2160 of jsarray.cpp with length + argc:

if (!obj->ensureDenseArrayElements(cx, length + argc))

As far as I understood this is supposed to allocate the array. In this case, the function gets 0 as input and does not allocate anything. Three lines later, the unshift function performs a memmove:

memmove(elems + argc, elems, length * sizeof(jsval));

In this case, length * 8 will overflow as well but will be large, causing the memmove to crash (segmentation fault) in a non-debug build. In a debug build, an assertion is triggered:

$ ./js
js> var a = new Array(4294967295);
js> a.unshift("foo");
Assertion failure: newlen + argc == length + argc, at jsarray.cpp:2159
Aborted

We believe the issue not to be exploitable because we cannot make argc arbitrary large. If we could cause argc to grow, lets say up to 2^31, then we could call ensureDenseArrayElements with a size of 0 and cause the memmove to move only a small amount of memory without crashing. However, we haven't found a way to call unshift with more than 2^19 elements because the call stack limits the maximum number of arguments that unshift can take. It might however be possible to achieve the same effect in a different way or to exploit the issue differently.

Reproducible: Always

Steps to Reproduce:
1. Create array with capacity 2^32 - 1
2. Unshift a single argument into the array
3. Inspect crash ;)
Actual Results:  
Crash.

Expected Results:  
Unclear, I do not know exactly what ECMA says about maximum array sizes. Probably an error message should indicate the overflow.

Comment 1

[Boris Zbarsky [:bzbarsky]]

> Unclear, I do not know exactly what ECMA says about maximum array sizes.

It's sorta schizoid about the whole thing... On the one hand, only indices 
0 <= i < 2^31-1 are treated as array indices.  On the other hand, unshift is generic (as in, is supposed to work on not just arrays), and as a result is defined entirely in terms of arbitrary property gets/sets, not in terms of array indices.

Comment 2

[Bob Clary [:bc] (inactive)]

dupe of bug 519119 ?

Comment 3

[Christian Holler (:decoder)]

Indeed, the problem might be related. I just tried the original test case and it didn't terminate so far. That might be the reason why it has gone undetected so far although the error can be provoked within seconds. But as far as I can remember, we tried this bug on 1.9.x and saw no failure.

Comment 4

[David Anderson [:dvander] - inactive, e-mail if emergency]

Attachment: fix

Comment 5

[Jeff Walden [:Waldo]]

Comment on attachment 493812 [details] [diff] [review]
fix

This code seems to have substantially changed since the patch was posted -- does the bug still exist?  In any case the patch isn't going to work here.

Comment 6

[David Anderson [:dvander] - inactive, e-mail if emergency]

bug 603318 changed the surrounding code, making this no longer a problem.