Bug 1199400 (CVE-2015-7221)

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

RESOLVED FIXED in Firefox 43

Status

()

RESOLVED FIXED
3 years ago
2 years ago

People

(Reporter: q1, Assigned: erahm)

Tracking

({sec-moderate})

40 Branch
mozilla43
sec-moderate
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)

(Reporter)

Description

3 years ago
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)
(Assignee)

Comment 2

3 years ago
(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.
(Assignee)

Comment 4

3 years ago
Created attachment 8656297 [details] [diff] [review]
Sanity check byte size when growing deque

This takes a very straightforward approach of asserting the byte size has not overflowed.
Attachment #8656297 - Flags: review?(nfroyd)
(Assignee)

Updated

3 years ago
Assignee: nobody → erahm
Status: NEW → ASSIGNED
(Assignee)

Updated

3 years ago
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+
(Assignee)

Comment 6

3 years ago
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|.
Attachment #8656794 - Flags: review?(nfroyd)
(Assignee)

Comment 7

3 years ago
Created attachment 8656795 [details] [diff] [review]
Part 2: Use CheckedInt when growing nsDeque capacity

Here we use CheckedInt to make sure the calculated byte size does not overflow.
Attachment #8656795 - Flags: review?(nfroyd)
(Assignee)

Updated

3 years ago
Attachment #8656297 - Attachment is obsolete: true
(Reporter)

Comment 9

3 years ago
(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...
(Reporter)

Comment 11

3 years ago
> 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.
(Assignee)

Comment 12

3 years ago
(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).
(Reporter)

Comment 13

3 years ago
(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....
(Assignee)

Comment 14

3 years ago
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
(Assignee)

Updated

3 years ago
Attachment #8656794 - Attachment is obsolete: true
Attachment #8656794 - Flags: review?(nfroyd)
(Assignee)

Updated

3 years ago
Attachment #8656795 - Attachment is obsolete: true
Attachment #8656795 - Flags: review?(nfroyd)
(Assignee)

Comment 16

3 years ago
Created attachment 8656889 [details] [diff] [review]
Part 0: Remove unused nsDequeIterator
Attachment #8656889 - Flags: review?(nfroyd)
(Assignee)

Comment 17

3 years ago
Created attachment 8656890 [details] [diff] [review]
Part 1: Use unsigned types for sizes in nsDeque
Attachment #8656890 - Flags: review?(nfroyd)
(Assignee)

Comment 18

3 years ago
Created attachment 8656891 [details] [diff] [review]
Part 2: Use CheckedInt when growing nsDeque capacity
Attachment #8656891 - Flags: review?(nfroyd)
(Assignee)

Comment 19

3 years ago
Created attachment 8656892 [details] [diff] [review]
Part 3: Add tests for possible corner cases due to using unsigned types
Attachment #8656892 - 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)
(Assignee)

Comment 25

3 years ago
Okay, we'll hold off on switching to size_t. I'll update the patches accordingly.
(Assignee)

Comment 26

3 years ago
Created attachment 8657265 [details] [diff] [review]
Part 1: Use CheckedInt when growing nsDeque capacity

This uses CheckedInt<int32_t> and adds an extra sanity check as requested.
Attachment #8657265 - Flags: review?(nfroyd)
(Assignee)

Updated

3 years ago
Attachment #8656891 - Attachment is obsolete: true
(Assignee)

Comment 27

3 years ago
Created attachment 8657267 [details] [diff] [review]
Part 2: Add tests for possible nsDeque corner cases

This just updates teh description.
(Assignee)

Updated

3 years ago
Attachment #8656892 - Attachment is obsolete: true
(Assignee)

Comment 28

3 years ago
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
(Assignee)

Comment 29

3 years ago
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+
(Reporter)

Comment 33

3 years ago
(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?).
(Assignee)

Comment 35

3 years ago
If we want to uplift this, part 1 is the main piece. It should be reasonably straightforward to backport.
https://hg.mozilla.org/mozilla-central/rev/4cd826f4b033
https://hg.mozilla.org/mozilla-central/rev/7fd961937687
https://hg.mozilla.org/mozilla-central/rev/2b1e7c1466c5
Status: ASSIGNED → RESOLVED
Last Resolved: 3 years ago
status-firefox43: --- → fixed
Resolution: --- → FIXED
Target Milestone: --- → mozilla43
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
status-firefox-esr38: --- → affected
Group: core-security-release
You need to log in before you can comment on or make changes to this bug.