1483699 - Latent (?) read and write beyond bounds in nsTArray_Impl::AppendElements()

Status: RESOLVED FIXED

(Core :: XPCOM, defect)

Description

[mozillabugs]

Attachment: bug_1222_str_1.htm

nsTArray_Impl::AppendElements(size_type aCount) (xpcom\ds\nsTArray.h) can experience an integer overflow. If it does, it underallocates a buffer, constructs elements beyond bounds, and returns a pointer that callers can use to read and write beyond bounds. The bug is that line 1687 doesn't check for overflow on the addition: [1]

	1684:   template<typename ActualAlloc = Alloc>
	1685:   elem_type* AppendElements(size_type aCount) {
	1686:     if (!ActualAlloc::Successful(this->template EnsureCapacity<ActualAlloc>(
	1687:           Length() + aCount, sizeof(elem_type)))) {
	1688:       return nullptr;
	1689:     }
	1690:     elem_type* elems = Elements() + Length();
	1691:     size_type i;
	1692:     for (i = 0; i < aCount; ++i) {
	1693:       elem_traits::Construct(elems + i);
	1694:     }
	1695:     this->IncrementLength(aCount);
	1696:     return elems;

Since this overload of AppendElements() takes only a count (and not also an array), it can be called with an anomalously large count without the caller having allocated space for the data to be appended.

Having searched the callers, I find that the bug appears to be latent as of FF 60.0.2. Probably the closest thing to an exploitable attack is in nsDataObj::CStream::OnDataAvailable() (widget\windows\nsDataObj.cpp), which contains this code:

	114: NS_IMETHODIMP
	115: nsDataObj::CStream::OnDataAvailable(nsIRequest *aRequest,
	116:                                     nsISupports *aContext,
	117:                                     nsIInputStream *aInputStream,
	118:                                     uint64_t aOffset, // offset within the stream
	119:                                     uint32_t aCount) // bytes available on this call
	120: {
	121:     // Extend the write buffer for the incoming data.
	122:     uint8_t* buffer = mChannelData.AppendElements(aCount, fallible);
	123:     if (!buffer) {
	124:       return NS_ERROR_OUT_OF_MEMORY;
	125:     }
	126:     NS_ASSERTION((mChannelData.Length() == (aOffset + aCount)),
	127:       "stream length mismatch w/write buffer");
	128: 
	129:     // Read() may not return aCount on a single call, so loop until we've
	130:     // accumulated all the data OnDataAvailable has promised.
	131:     nsresult rv;
	132:     uint32_t odaBytesReadTotal = 0;
	133:     do {
	134:       uint32_t bytesReadByCall = 0;
	135:       rv = aInputStream->Read((char*)(buffer + odaBytesReadTotal),
	136:                               aCount, &bytesReadByCall
	137:       odaBytesReadTotal += bytesReadByCall;
	138:     } while (aCount < odaBytesReadTotal && NS_SUCCEEDED(rv));
	139:     return rv;
	140: }

|aCount| in that function appears sometimes to come from other code that has not yet allocated space for the data. This appears to occur when reading a file via the file:// protocol (though not via http://). If, for example, you drag an image (even a broken one that FF refuses to display) from FF into Explorer, OnDataAvailable() is called repeatedly to read the data that's become available. If you set |network.buffer.cache.count| large enough, the chunks read can be very large, over 0x80000000 bytes. If the correct order of chunks occurs, line 122 will cause the overflow.

I have attached an STR that illustrates this issue, though I have not yet gotten a sequence of chunks that causes the overflow.

It would be easy unintentionally to write exploitable code by, say, reading 2 or more lengths out of a media file, creating an nsTArray to hold the corresponding data, and repeatedly calling AppendElements() to allocate storage for them, e.g.:

	nsTArray <char> media;
	uint32_t len1 = mediafile.Read32 (); // assume |len1| is 0x1000 
	char *pPart1 = media.AppendElements (len1);
	uint32_t len2 = mediafile.Read32 (); // assume |len2| is 0xFFFFF000 

	// Oops, overflows to 0 and returns underallocated pointer in 32-bit builds!

	char *pPart2 = media.AppendElements (len2);


To use the STR, first set |network.buffer.cache.count| to 262144. Now put the STR .htm file into a local folder, expand the .7z file into the same folder, and load the .htm file in FF using the local folder path.

Set a BP on nsDataObj::CStream::OnDataAvailable() and drag the broken image icon into Explorer. The BP should trigger multiple times, usually with different (sometimes very large) |aCount| values. If you are lucky, and are using the Win32 FF build, it might cause the overflow and crash FF. You might have to try this test several times to see large values, depending upon how the STR data file is allocated on your disk and how busy your system is.

[1] A similar bug also exists on all call-paths into 
nsTArray_base::InsertSlotsAt() (xpcom\ds\nsTArray-inl.h), which has the same issue:

	342:  size_type newLen = Length() + aCount;
	343:
	344:  EnsureCapacity<ActualAlloc>(newLen, aElemSize);

InsertElementsAt (index_type, size_type), for example, calls InsertSlotsAt().

Comment 1

[mozillabugs]

Attachment: bug_1222_str_1.7z

Comment 2

[Ryan VanderMeulen [:RyanVM]]

Nathan, can you please take a look at this?

Comment 3

[Nathan Froyd [:froydnj]]

Attachment: part 1 - add overflow checks for extending arrays

This patch is not perfect; there's still possible issues in ReplaceElementsAt.
InsertSlotsAt will be taken care of in the next patch.  I'm leaving
ReplaceElementsAt for the time being.

Comment 4

[Nathan Froyd [:froydnj]]

Attachment: part 2 - make InsertSlotsAt error checking more thorough

I don't know what the existing code was trying to do, but it certainly
wasn't clear, and possibly not correct.

Comment 5

[Nathan Froyd [:froydnj]]

Patches posted.

Comment 6

[Andrew McCreight [:mccr8]]

Comment on attachment 9002922 [details] [diff] [review]
part 1 - add overflow checks for extending arrays

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

I was going to mention ReplaceElementsAt, but I see you already did.

I think for ReplaceElementsAt you could add something like
  if (MOZ_UNLIKELY(aCount > Length())) {
    InvalidArrayIndex_CRASH(aCount, Length());
  }
then do
  EnsureCapacity<...>(Length() - aCount, aArrayLen)

The check is somewhat nonsensical (you really care that aStart + aCount is bounded by the length) but it seems like a simple thing you can check to avoid overflow there. (In general, the (a + b - c) pattern is a little sketchy, though I guess this is unsigned so overflowing then underflowing back is okay...) 

I wonder if having a EnsureCapacityPlusOne method (maybe with a better name!) would be nicer from an audititability standpoint? I guess I'm not sure of what the invariant is that allows this to be safe, so maybe not.

Looking for arithmetic at the call sites of methods called "EnsureCapacity" may be some rich ground for finding other overflow issues...

::: xpcom/ds/nsTArray.h
@@ +397,5 @@
>                                                         size_type aElemSize);
>  
> +  // Extend the storage to accommodate aCount extra elements.
> +  // @param aLength The current size of the array.
> +  // @param aLength The number of elements to add.

aLength -> aCount

@@ +2374,5 @@
>  
>    index_type len = Length();
>    index_type otherLen = aArray.Length();
> +  if (!Alloc::Successful(this->template ExtendCapacity<Alloc>(
> +        len, otherLen, sizeof(elem_type)))) {

preexisting nit: indentation here looks off.

Comment 7

[Nathan Froyd [:froydnj]]

I will have to look at the ReplaceElementsAt bit later.

(In reply to Andrew McCreight [:mccr8] from comment #6)
> I wonder if having a EnsureCapacityPlusOne method (maybe with a better
> name!) would be nicer from an audititability standpoint? I guess I'm not
> sure of what the invariant is that allows this to be safe, so maybe not.
> 
> Looking for arithmetic at the call sites of methods called "EnsureCapacity"
> may be some rich ground for finding other overflow issues...

The EnsureCapacity(Length() + 1) call is safe because Length() returns an integer guaranteed to fit in 31 bits, so it can't overflow a 32-bit integer, and EnsureCapacity checks for new lengths that don't fit in 31 bits.

Comment 8

[Andrew McCreight [:mccr8]]

Comment on attachment 9002923 [details] [diff] [review]
part 2 - make InsertSlotsAt error checking more thorough

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

::: xpcom/ds/nsTArray-inl.h
@@ +355,5 @@
>    if (MOZ_UNLIKELY(aIndex > Length())) {
>      InvalidArrayIndex_CRASH(aIndex, Length());
>    }
>  
> +  if (!ActualAlloc::Successful(this->ExtendCapacity<ActualAlloc>(Length(), aCount, aElemSize))) {

Is there no failure monad for ResultTypeProxy? ;)

@@ -355,5 @@
>    if (MOZ_UNLIKELY(aIndex > Length())) {
>      InvalidArrayIndex_CRASH(aIndex, Length());
>    }
>  
> -  size_type newLen = Length() + aCount;

Can we somehow ban all non-checked arithmetic from this file...

Comment 9

[mozillabugs]

(In reply to Andrew McCreight [:mccr8] from comment #8)

> Can we somehow ban all non-checked arithmetic from this file...

A good idea. I like CheckedInt because it packages arithmetic and over-/underflow checking together, which means less duplicative code to mess up, e.g., https://bugzilla.mozilla.org/show_bug.cgi?id=1379411 .

Comment 10

[Sebastian Hengst [:aryx] (needinfo me if it's about an intermittent or backout)]

https://hg.mozilla.org/integration/mozilla-inbound/rev/fada6a49425e2a3c782ffa9b56c9ed92c0669fa4
https://hg.mozilla.org/integration/mozilla-inbound/rev/83758eaff784a61eb522559eb9e6203667c3a6b0

https://hg.mozilla.org/mozilla-central/rev/fada6a49425e
https://hg.mozilla.org/mozilla-central/rev/83758eaff784

Comment 11

[Ryan VanderMeulen [:RyanVM]]

Please nominate this for Beta and ESR60 uplift when you get a chance. It grafts cleanly as-landed.

Comment 12

[Nathan Froyd [:froydnj]]

Comment on attachment 9002922 [details] [diff] [review]
part 1 - add overflow checks for extending arrays

[Beta/Release Uplift Approval Request]

Feature/Bug causing the regression: N/A

User impact if declined: Possible exploits.

Is this code covered by automated tests?: Yes

Has the fix been verified in Nightly?: No

Needs manual test from QE?: No

If yes, steps to reproduce: 

List of other uplifts needed: None

Risk to taking this patch: Low

Why is the change risky/not risky? (and alternatives if risky): Small change, well understood.

String changes made/needed: None.

[ESR Uplift Approval Request]

If this is not a sec:{high,crit} bug, please state case for ESR consideration: Fewer security bugs is more better.

User impact if declined: Possible exploits

Fix Landed on Version: 

Risk to taking this patch: Low

Why is the change risky/not risky? (and alternatives if risky): Small change, well understood.

String or UUID changes made by this patch: None.

Comment 13

[Pascal Chevrel:pascalc (PTO until April 26)]

Comment on attachment 9002922 [details] [diff] [review]
part 1 - add overflow checks for extending arrays

Uplift approved for 63 beta 14, thanks.

Comment 14

[Sebastian Hengst [:aryx] (needinfo me if it's about an intermittent or backout)]

https://hg.mozilla.org/releases/mozilla-beta/rev/b4e29532f528
https://hg.mozilla.org/releases/mozilla-beta/rev/de127662180d

Comment 15

[Ryan VanderMeulen [:RyanVM]]

Comment on attachment 9002922 [details] [diff] [review]
part 1 - add overflow checks for extending arrays

Fewer sec bugs are indeed more better. Approved for ESR 60.3.

Comment 16

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/releases/mozilla-esr60/rev/b3359becd7b1
https://hg.mozilla.org/releases/mozilla-esr60/rev/791c8ecf252d