1308036 - Overflows in nsSupportsArray could cause buffer overruns

Status: RESOLVED FIXED

(Core :: XPCOM, defect)

Description

[q1]

nsSupportsArray (xpcom\ds\nsSupportsArray.cpp/.h) neither checks for overflow when adding elements, nor limits the number of elements per instance of the class. It is, thus, possible for InsertElementsAt() or GrowArrayBy() to experience an integer overflow, causing failure to allocate a large-enough buffer, and subsequently a buffer overrun.

I do not have a POC at present, but since nsSupportsArray is used by add-ons, presumably a condition that causes an add-on to allocate very large arrays could manifest the bug(s). Also there are some uses of nsSupportsArray in FF itself.

The bugs are still present in trunk.


Details
-------

The bugs are in InsertElementsAt() line 396 (can overflow) and GrowArrayBy() lines 117 (should use uint32_t), 127 (can overflow), 128 (can overflow), and 135 (can overflow).

There are 4 bug cases.

1. If the addition on line 396 overflows, InsertElementsAt() doesn't attempt to allocate more space, but instead incorrectly assumes that the space already has been allocated, and proceeds to write beyond |mArray|'s end:

384: NS_IMETHODIMP_(bool)
385: nsSupportsArray::InsertElementsAt(nsISupportsArray* aElements, uint32_t aIndex)
386: {
387:   if (!aElements) {
388:     return false;
389:   }
390:   uint32_t countElements;
391:   if (NS_FAILED(aElements->Count(&countElements))) {
392:     return false;
393:   }
394: 
395:   if (aIndex <= mCount) {
396:     if (mArraySize < (mCount + countElements)) {
397:       // need to grow the array
398:       GrowArrayBy(countElements);
399:     }
400:
... insert the elements [aElements...aElements+aIndex).


2. If the addition on line 396 does not overflow, but |countElements| on line 398 is large enough to be interpreted as a negative |int32_t| by GrowArrayBy(), GrowArrayBy() allocates only kGrowArrayBy additional elements of space (lines 123-24 execute), which is insufficient and again causes InsertElementsAt() to overrun |mArray|:

116: void
117: nsSupportsArray::GrowArrayBy(int32_t aGrowBy)
118: {
119:   // We have to grow the array. Grow by kGrowArrayBy slots if we're smaller
120:   // than kLinearThreshold bytes, or a power of two if we're larger.
121:   // This is much more efficient with most memory allocators, especially
122:   // if it's very large, or of the allocator is binned.
123:   if (aGrowBy < kGrowArrayBy) {
124:     aGrowBy = kGrowArrayBy;
125:   }
126: 
127:   uint32_t newCount = mArraySize + aGrowBy;  // Minimum increase
128:   uint32_t newSize = sizeof(mArray[0]) * newCount;
129: 
130:   if (newSize >= (uint32_t)kLinearThreshold) {
131:     // newCount includes enough space for at least kGrowArrayBy new slots.
132:     // Select the next power-of-two size in bytes above that if newSize is
133:     // not a power of two.
134:     if (newSize & (newSize - 1)) {
135:       newSize = 1u << mozilla::CeilingLog2(newSize);
136:     }
137: 
138:     newCount = newSize / sizeof(mArray[0]);
139:   }
140:   // XXX This would be far more efficient in many allocators if we used
141:   // XXX PR_Realloc(), etc
142:   nsISupports** oldArray = mArray;
143: 
144:   mArray = new nsISupports*[newCount];
145:   mArraySize = newCount;
...

3. If the addition on line 396 does not overflow, and |countElements| is not large enough to be interpreted as a negative |int32_t| by GrowArrayBy(), but it is large enough for GrowArrayBy() line 128 to calculate a |newSize| >= 0x80000001, line 135 executes, causing |newSize| to become a small positive value, which again is insufficient and leads to a buffer overrun as above.

4. The multiplication on line 128 also will overflow if |newCount| >= 0x20000000 (64-bit builds) or 0x40000000 (32-bit builds).

Comment 1

[Daniel Veditz [:dveditz]]

We'll need to check, but we don't think we use this in contexts where the array would get that large. And on 32-bit systems we'd probably crash before we got there.

Comment 2

[Nathan Froyd [:froydnj]]

(In reply to Daniel Veditz [:dveditz] from comment #1)
> We'll need to check, but we don't think we use this in contexts where the
> array would get that large. And on 32-bit systems we'd probably crash before
> we got there.

I'm not quite sure what question I'm answering here, so a couple thoughts:

nsISupportsArray has a big interface, but a lot of it is inaccessible to script.  InsertElementsAt, in particular, doesn't seem to be reachable by script; its only caller is AppendElements, which appears to be dead code according to DXR.  The GrowBy vulnerability is more worrisome, but requires a long array length.  Judging by:

https://dxr.mozilla.org/mozilla-central/search?q=nsISupportsArray&redirect=false

nsISupportsArray is used mostly for holding things for clipboard operations, so I wouldn't expect the array lengths to be very long.  Worth fixing in any event.

Comment 3

[Eric Rahm [:erahm]]

I'll take a look at this.

Comment 4

[q1]

> InsertElementsAt, in particular, doesn't seem to be reachable by script...

You're correct. I tried it from browser-scope scratchpad, and no dice.

However, the following script crashes FF when run from browser-scope scratchpad (click "continue" in the "unresponsive script" alert boxes):

   var sa=Components.classes['@mozilla.org/supports-array;1'].createInstance(Components.interfaces.nsISupportsArray);
   var s=Components.classes['@mozilla.org/supports-string;1'].createInstance(Components.interfaces.nsISupportsString);

   s.data='';

   for (var i = 0; i <= 0x80001000; ++i) {
      sa.AppendElement(s);
   }

Presumably it triggers the overflow in GrowArrayBy() line 128, and the subsequent overrun.

Since AppendElement() is scriptable, this bug could be invoked by an add-on that uses very large arrays.

I'm currently running the script on a debug build, but it takes a long time to execute.

BTW, what governs whether a method is accessible from script?

Comment 5

[q1]

> Since AppendElement() is scriptable, this bug could be invoked by an add-on that uses very large arrays.

And if there is a bug in the add-on that allows an attacker to make it use very large arrays, an attacker could force the overrun.

Comment 6

[Eric Rahm [:erahm]]

(In reply to q1 from comment #4)
> BTW, what governs whether a method is accessible from script?

There are scriptable, noscript, notxpcom markers. nsISupportsArray is marked as a scriptable interface [1], but many of the functions are set as notxpcom so they are not exposed.

[1] http://searchfox.org/mozilla-central/rev/76609a05d6ef7ba4223ed79e479c73fb2543a107/xpcom/ds/nsISupportsArray.idl#33

Comment 7

[q1]

(In reply to q1 from comment #4)
> However, the following script crashes FF when run from browser-scope
> scratchpad...

I used FF x64 in this test.

Comment 8

[q1]

(In reply to Eric Rahm [:erahm] from comment #6)
> (In reply to q1 from comment #4)
> > BTW, what governs whether a method is accessible from script?
> 
> There are scriptable, noscript, notxpcom markers. nsISupportsArray is marked
> as a scriptable interface [1], but many of the functions are set as notxpcom
> so they are not exposed.
> 
> [1]
> http://searchfox.org/mozilla-central/rev/
> 76609a05d6ef7ba4223ed79e479c73fb2543a107/xpcom/ds/nsISupportsArray.idl#33

Hmm, that's interesting, but AppendElement() isn't even in the IDL, yet it is accessible from scripts.

Comment 9

[Eric Rahm [:erahm]]

Although this interface was deprecated in 2002 it still sees a fair amount of use including in other interfaces. It's also used a fair amount in addons (847 textual instances); I audited a few calls and they're clearly already broken by the likes of bug 407956 so I guess there's prior art to being okay with breaking addons.

I'll look at putting together an upliftable patch fixing the overflow issue and then as follow up look at what pieces we can remove altogether (the notxpcom bits being the easiest).

Comment 10

[q1]

Must be in nsiCollection?

Comment 11

[q1]

(In reply to q1 from comment #10)
> Must be in nsiCollection?

It is. Thanks, Eric, for the pointer.

Comment 12

[Eric Rahm [:erahm]]

Attachment: Part 1: Check sizes when growing nsISupportsArray

This adds size checks when growing the nsISupportsArray. It also removes
|InsertElementsAt| and |AppendElements| which are unused notxpcom interfaces
that would need similar modifications.

MozReview-Commit-ID: ET32q0OCrLU

Comment 13

[Eric Rahm [:erahm]]

(In reply to Eric Rahm [:erahm] from comment #12)
> Created attachment 8798597 [details] [diff] [review]
> Part 1: Check sizes when growing nsISupportsArray
> 
> This adds size checks when growing the nsISupportsArray. It also removes
> |InsertElementsAt| and |AppendElements| which are unused notxpcom interfaces
> that would need similar modifications.
> 
> MozReview-Commit-ID: ET32q0OCrLU

I've filed a non-sec-embargoed follow up for the cleanup, so really there's just going to be one part here.

Comment 14

[q1]

(In reply to Eric Rahm [:erahm] from comment #12)
> Created attachment 8798597 [details] [diff] [review]
> Part 1: Check sizes when growing nsISupportsArray

Also please fix bug case 3 (overflow on line 135/new line 142).

Comment 15

[Eric Rahm [:erahm]]

Attachment: Part 1: Check sizes when growing nsISupportsArray

Updated to handle the power of 2 left shift.

MozReview-Commit-ID: ET32q0OCrLU

Comment 16

[Nathan Froyd [:froydnj]]

Comment on attachment 8798656 [details] [diff] [review]
Part 1: Check sizes when growing nsISupportsArray

Review of attachment 8798656 [details] [diff] [review]:
-----------------------------------------------------------------

Hooray for smaller interfaces.

::: xpcom/ds/nsSupportsArray.cpp
@@ +139,5 @@
>      // newCount includes enough space for at least kGrowArrayBy new slots.
>      // Select the next power-of-two size in bytes above that if newSize is
>      // not a power of two.
> +    if (newSize.value() & (newSize.value() - 1)) {
> +      newSize = UINT64_C(1) << mozilla::CeilingLog2(newSize.value());

It's unfortunate that we can't use mozilla::RoundUpPow2 here.  Kinda wonder how many other places are using RoundUpPow2 with issues if the argument is >= INT32_MAX (INT64_MAX on 64-bit platforms).

Comment 17

[Nathan Froyd [:froydnj]]

Thinking about this a little more after looking through the cleanup patches...we have a number of methods that return an int32_t, but all the checks in the patch and the lengths are uint32_t.  Surely that sort of mismatch cannot end well.

Comment 18

[Eric Rahm [:erahm]]

(In reply to Nathan Froyd [:froydnj] from comment #17)
> Thinking about this a little more after looking through the cleanup
> patches...we have a number of methods that return an int32_t, but all the
> checks in the patch and the lengths are uint32_t.  Surely that sort of
> mismatch cannot end well.

Those are for indexing methods, I guess worst case scenario we'd return a negative value for a really large index, hopefully the caller would interpret that as not found.

Comment 19

[Eric Rahm [:erahm]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/49bf7e023d0d1c36aa12b15ba164bc6f9b8bfe7b
Bug 1308036 - Check sizes when growing nsISupportsArray. r=froydnj

Comment 20

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/49bf7e023d0d