1199400 - (CVE-2015-7221) Overflow in nsDeque::GrowCapacity can cause memory-safety bug

Status: RESOLVED FIXED

(Core :: XPCOM, defect)

Description

[q1]

nsDeque::GrowCapacity (xpcom\glue\nsDeque.cpp) does not properly check for overflow. This can cause it to allocate a buffer that is too small to contain the deque's elements, some of which then are written to memory that the deque does not own.

Details:
--------

If the deque's existing capacity |mCapacity| has the range [0x10000000, 0x1fffffff] (1-2 GB), then line 166 (below) computes a valid |theNewSize| with the range [0x40000000, 0x7ffffffc] and the tests on lines 167-70 pass:

163: bool
164: nsDeque::GrowCapacity()
165: {
166:   int32_t theNewSize = mCapacity << 2;
167:   NS_ASSERTION(theNewSize > mCapacity, "Overflow");
168:   if (theNewSize <= mCapacity) {
169:     return false;
170:   }

Control passes to line 171, which multiples |theNewSize| by |sizeof(void*)|, which is 4 on x86 architectures. The resulting values [0x100000000, 0x1fffffff0] overflow |size_t| on x86 architectures, and are truncated to [0, 0xfffffff0] [1]:

171:   void** temp = (void**)malloc(theNewSize * sizeof(void*));
172:   if (!temp) {
173:     return false;
174:   }

Line 171 can allocate sizes near the lower end of this range, so then control passes to lines 181-82, which write beyond the end of the buffer:

175: 
176:   //Here's the interesting part: You can't just move the elements
177:   //directly (in situ) from the old buffer to the new one.
178:   //Since capacity has changed, the old origin doesn't make
179:   //sense anymore. It's better to resequence the elements now.
180: 
181:   memcpy(temp, mData + mOrigin, sizeof(void*) * (mCapacity - mOrigin));
182:   memcpy(temp + (mCapacity - mOrigin), mData, sizeof(void*) * mOrigin);
...

Any elements added later are also written beyond the end of the buffer.

[1] There is no overflow on x64 architectures, where |sizeof(size_t)| == 8.

Comment 1

[Andrew McCreight [:mccr8]]

Eric, do you have any interest in digging into this code to figure this out? I doubt anybody has looked at it in years.

Comment 2

[Eric Rahm [:erahm]]

(In reply to Andrew McCreight [:mccr8] from comment #1)
> Eric, do you have any interest in digging into this code to figure this out?
> I doubt anybody has looked at it in years.

Sure I'll take a look.

Comment 3

[Eric Rahm [:erahm]]

https://treeherder.mozilla.org/#/jobs?repo=try&revision=ea8dda4f0743

Comment 4

[Eric Rahm [:erahm]]

Attachment: Sanity check byte size when growing deque

This takes a very straightforward approach of asserting the byte size has not overflowed.

Comment 5

[Nathan Froyd [:froydnj]]

Comment on attachment 8656297 [details] [diff] [review]
Sanity check byte size when growing deque

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

::: xpcom/glue/nsDeque.cpp
@@ +164,5 @@
>  nsDeque::GrowCapacity()
>  {
>    int32_t theNewSize = mCapacity << 2;
>    NS_ASSERTION(theNewSize > mCapacity, "Overflow");
>    if (theNewSize <= mCapacity) {

I would feel way more comfortable about this function (and these checks in particular) if mCapacity and company were of unsigned type.

Or perhaps some of these calculations could use mozilla/CheckedInt.h.

@@ +170,5 @@
>    }
> +
> +  // Sanity check the new byte size.
> +  size_t oldByteSize = mCapacity * sizeof(void*);
> +  size_t newByteSize = theNewSize * sizeof(void*);

I think CheckedInt would make this clearer, because really what you're trying to do here is ensure that the amount for malloc doesn't overflow, and checking against the previous amount that you malloc'd is kind of a roundabout way of doing that.  (I think this way works, but it's not particularly obvious that overflow, etc. work out in your favor.)

Comment 6

[Eric Rahm [:erahm]]

Attachment: Part 1: Use unsigned types for sizes in nsDeque

This updates nsDeque to use size_t for its members that track sizes and
offsets. Method params and return values are updated as well, this required
a few changes outside of xpcom that use |GetSize|.

Comment 7

[Eric Rahm [:erahm]]

Attachment: Part 2: Use CheckedInt when growing nsDeque capacity

Here we use CheckedInt to make sure the calculated byte size does not overflow.

Comment 8

[Eric Rahm [:erahm]]

https://treeherder.mozilla.org/#/jobs?repo=try&revision=07ee8222a031

Comment 9

[q1]

(In reply to Eric Rahm [:erahm] (out 9/7 - 9/24) from comment #6)
> Created attachment 8656794 [details] [diff] [review]
> Part 1: Use unsigned types for sizes in nsDeque
> 
> This updates nsDeque to use size_t for its members that track sizes and
> offsets. Method params and return values are updated as well, this required
> a few changes outside of xpcom that use |GetSize|.

Because of the change to the post-decrement operator, you'll get an nullptr exception by writing:

   for (nsDequeIterator it = somensDequeObject.End(); it >= somensDequeObject.Begin(); foo = *it--) ...

Comment 10

[Nathan Froyd [:froydnj]]

(In reply to q1 from comment #9)
> (In reply to Eric Rahm [:erahm] (out 9/7 - 9/24) from comment #6)
> > Created attachment 8656794 [details] [diff] [review]
> > Part 1: Use unsigned types for sizes in nsDeque
> > 
> > This updates nsDeque to use size_t for its members that track sizes and
> > offsets. Method params and return values are updated as well, this required
> > a few changes outside of xpcom that use |GetSize|.
> 
> Because of the change to the post-decrement operator, you'll get an nullptr
> exception by writing:
> 
>    for (nsDequeIterator it = somensDequeObject.End(); it >=
> somensDequeObject.Begin(); foo = *it--) ...

The good news is that nsDequeIterator seems to be completely unused, so...

Comment 11

[q1]

> The good news is that nsDequeIterator seems to be completely unused, so...

That is good news, because it's a bit ugly. Still, it should either work correctly or get removed from the codebase.

Comment 12

[Eric Rahm [:erahm]]

(In reply to q1 from comment #11)
> > The good news is that nsDequeIterator seems to be completely unused, so...
> 
> That is good news, because it's a bit ugly. Still, it should either work
> correctly or get removed from the codebase.

We should really just delete the iterator class, it's not used and it doesn't conform to standard concepts of iteration (nsDeque::End() is actually a valid element).

Comment 13

[q1]

(In reply to Eric Rahm [:erahm] (out 9/7 - 9/24) from comment #12)
> (In reply to q1 from comment #11)
> > > The good news is that nsDequeIterator seems to be completely unused, so...
> > 
> > That is good news, because it's a bit ugly. Still, it should either work
> > correctly or get removed from the codebase.
> 
> We should really just delete the iterator class, it's not used and it
> doesn't conform to standard concepts of iteration (nsDeque::End() is
> actually a valid element).

Ya. That's the bit of ugly I was thinking of....

Comment 14

[Eric Rahm [:erahm]]

Going to update with:
- New patch: Removing the iterator class, it's untested, unused, and odd
- Updated switch to size_t patch removing modassign, updating PushFront, updating bizarro modulus to standard modulus
- CheckedInt should be basically the same
- Add some tests for stuff that would have been broken

Comment 15

[Eric Rahm [:erahm]]

https://treeherder.mozilla.org/#/jobs?repo=try&revision=a2f0f45fd8ed

Comment 16

[Eric Rahm [:erahm]]

Attachment: Part 0: Remove unused nsDequeIterator

Comment 17

[Eric Rahm [:erahm]]

Attachment: Part 1: Use unsigned types for sizes in nsDeque

Comment 18

[Eric Rahm [:erahm]]

Attachment: Part 2: Use CheckedInt when growing nsDeque capacity

Comment 19

[Eric Rahm [:erahm]]

Attachment: Part 3: Add tests for possible corner cases due to using unsigned types

Comment 20

[Andrew McCreight [:mccr8]]

I'm going to mark this sec-moderate because getting a contiguous 1GB allocation on a 32-bit system is not very plausible.

Comment 21

[Nathan Froyd [:froydnj]]

Comment on attachment 8656889 [details] [diff] [review]
Part 0: Remove unused nsDequeIterator

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

Good riddance.

::: xpcom/glue/nsDeque.cpp
@@ +377,4 @@
>  void*
>  nsDeque::Last() const
>  {
> +  return ObjectAt(mSize - 1);

Hey, look, dodgy code in an unused method!

Would you please file a followup for removing this method (and others that happen to be unused)?

Comment 22

[Nathan Froyd [:froydnj]]

Comment on attachment 8656892 [details] [diff] [review]
Part 3: Add tests for possible corner cases due to using unsigned types

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

r=me assuming this works before and after your changes.

Comment 23

[Nathan Froyd [:froydnj]]

Comment on attachment 8656891 [details] [diff] [review]
Part 2: Use CheckedInt when growing nsDeque capacity

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

r=me with the change below, assuming you agree with me.

::: xpcom/glue/nsDeque.cpp
@@ +135,5 @@
>  bool
>  nsDeque::GrowCapacity()
>  {
> +  mozilla::CheckedInt<size_t> newCapacity = mCapacity;
> +  newCapacity *= 4;

So now that I've seen part 2, which I'm not sure I have the mental capacity to think through the repercussions of doing, WDYT about the simpler fix of just applying CheckedInt here?  Something like:

CheckedInt<int32_t> newCapacity = mCapacity;
newCapacity *= 4;

// I think the current patch is correct in its checks, but it'd be
// nice to have this check in here for completeness.
if (!newCapacity.isValid()) {
  return false;
}

CheckedInt<int32_t> newByteSize = newCapacity;
newByteSize *= sizeof(void*);

// Verify that newByteSize.isValid();

// Allocate and store mCapacity as this current patch has.

Comment 24

[Nathan Froyd [:froydnj]]

Comment on attachment 8656890 [details] [diff] [review]
Part 1: Use unsigned types for sizes in nsDeque

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

As suggested for part 2, I'm not sure I have the mental capacity right now to think through all the effects this change would require.  Let's try just applying CheckedInt<int32_t> in part 2 and see where that gets us.

Comment 25

[Eric Rahm [:erahm]]

Okay, we'll hold off on switching to size_t. I'll update the patches accordingly.

Comment 26

[Eric Rahm [:erahm]]

Attachment: Part 1: Use CheckedInt when growing nsDeque capacity

This uses CheckedInt<int32_t> and adds an extra sanity check as requested.

Comment 27

[Eric Rahm [:erahm]]

Attachment: Part 2: Add tests for possible nsDeque corner cases

This just updates teh description.

Comment 28

[Eric Rahm [:erahm]]

Comment on attachment 8656890 [details] [diff] [review]
Part 1: Use unsigned types for sizes in nsDeque

We'll hold off on this for a general "cleanup nsDeque" follow up.

Comment 29

[Eric Rahm [:erahm]]

Comment on attachment 8657267 [details] [diff] [review]
Part 2: Add tests for possible nsDeque corner cases

Carrying forward r+ (these tests pass before and after the changes).

Comment 30

[Eric Rahm [:erahm]]

https://treeherder.mozilla.org/#/jobs?repo=try&revision=befd8ae782a7

Comment 31

[Nathan Froyd [:froydnj]]

Comment on attachment 8657265 [details] [diff] [review]
Part 1: Use CheckedInt when growing nsDeque capacity

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

Thank you!

Comment 32

[Eric Rahm [:erahm]]

https://treeherder.mozilla.org/#/jobs?repo=try&revision=a4645d8cd66c

Comment 33

[q1]

(In reply to Andrew McCreight [:mccr8] from comment #20)
> I'm going to mark this sec-moderate because getting a contiguous 1GB
> allocation on a 32-bit system is not very plausible.

I was curious about how easy it is to get a 1GB allocation on x86 FF. So I started FF 40.0 debug on Win7 SP1 x64. Then I set breakpoints on some random instantiations of |new char []| and the like, attached the debugger to FF, and loaded mozilla.org. It breakpointed at nsPNGEncoder::AddImageFrame line 292:

   uint8_t* row = new uint8_t[aWidth * 4];

I doctored aWidth to 0x10000000, stepped it, and (a bit to my surprise), it returned row = 0x80000000. I was then able to use the debugger to change the values of the bytes at 0x80000000 and 0xbfffffff, so it definitely worked.

That said, I suppose this would be more difficult if I had used FF for awhile before setting the breakpoint, and it'd certainly be more difficult on an x86 OS (but how many people run those nowadays?).

Comment 34

[Eric Rahm [:erahm]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/4cd826f4b033f0cf1c93bfa5066ea1f14d77c6ef
Bug 1199400 - Part 0: Remove unused nsDequeIterator. r=froydnj

https://hg.mozilla.org/integration/mozilla-inbound/rev/7fd9619376872691295a9ed787c281e77be3481a
Bug 1199400 - Part 1: Use CheckedInt when growing nsDeque capacity. r=froydnj

https://hg.mozilla.org/integration/mozilla-inbound/rev/2b1e7c1466c562c917d02f2b8df9c6fa79dbe15a
Bug 1199400 - Part 2: Add tests for possible nsDeque corner cases. r=froydnj

Comment 35

[Eric Rahm [:erahm]]

If we want to uplift this, part 1 is the main piece. It should be reasonably straightforward to backport.

Comment 36

[Phil Ringnalda (:philor)]

https://hg.mozilla.org/mozilla-central/rev/4cd826f4b033
https://hg.mozilla.org/mozilla-central/rev/7fd961937687
https://hg.mozilla.org/mozilla-central/rev/2b1e7c1466c5