Bug 1199400 (CVE-2015-7221)

Overflow in nsDeque::GrowCapacity can cause memory-safety bug

RESOLVED FIXED in Firefox 43

Status

()

defect
RESOLVED FIXED
4 years ago
2 years ago

People

(Reporter: q1, Assigned: erahm)

Tracking

({sec-moderate})

40 Branch
mozilla43
Points:
---
Bug Flags:
sec-bounty +

Firefox Tracking Flags

(firefox43 fixed, firefox-esr38 affected)

Details

(Whiteboard: [post-critsmash-triage][adv-main43+])

Attachments

(3 attachments, 6 obsolete attachments)

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.
Flags: sec-bounty?
Eric, do you have any interest in digging into this code to figure this out? I doubt anybody has looked at it in years.
Flags: needinfo?(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.
This takes a very straightforward approach of asserting the byte size has not overflowed.
Attachment #8656297 - Flags: review?(nfroyd)
Assignee: nobody → erahm
Status: NEW → ASSIGNED
Flags: needinfo?(erahm)
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.)
Attachment #8656297 - Flags: review?(nfroyd) → feedback+
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|.
Attachment #8656794 - Flags: review?(nfroyd)
Here we use CheckedInt to make sure the calculated byte size does not overflow.
Attachment #8656795 - Flags: review?(nfroyd)
Attachment #8656297 - Attachment is obsolete: true
(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--) ...
(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...
> 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.
(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).
(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....
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
Attachment #8656794 - Attachment is obsolete: true
Attachment #8656794 - Flags: review?(nfroyd)
Attachment #8656795 - Attachment is obsolete: true
Attachment #8656795 - Flags: review?(nfroyd)
Attachment #8656889 - Flags: review?(nfroyd)
Attachment #8656890 - Flags: review?(nfroyd)
Attachment #8656891 - Flags: review?(nfroyd)
I'm going to mark this sec-moderate because getting a contiguous 1GB allocation on a 32-bit system is not very plausible.
Keywords: sec-moderate
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)?
Attachment #8656889 - Flags: review?(nfroyd) → review+
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.
Attachment #8656892 - Flags: review?(nfroyd) → review+
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.
Attachment #8656891 - Flags: review?(nfroyd) → review+
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.
Attachment #8656890 - Flags: review?(nfroyd)
Okay, we'll hold off on switching to size_t. I'll update the patches accordingly.
This uses CheckedInt<int32_t> and adds an extra sanity check as requested.
Attachment #8657265 - Flags: review?(nfroyd)
Attachment #8656891 - Attachment is obsolete: true
This just updates teh description.
Attachment #8656892 - Attachment is obsolete: true
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.
Attachment #8656890 - Attachment is obsolete: true
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).
Attachment #8657267 - Flags: review+
Comment on attachment 8657265 [details] [diff] [review]
Part 1: Use CheckedInt when growing nsDeque capacity

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

Thank you!
Attachment #8657265 - Flags: review?(nfroyd) → review+
(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?).
If we want to uplift this, part 1 is the main piece. It should be reasonably straightforward to backport.
Group: core-security → core-security-release
Flags: sec-bounty? → sec-bounty+
Whiteboard: [post-critsmash-triage]
Whiteboard: [post-critsmash-triage] → [post-critsmash-triage][adv-main43+]
Alias: CVE-2015-7221
Group: core-security-release
You need to log in before you can comment on or make changes to this bug.