1288561 - Overflow in nsAttrAndChildArray::GrowBy() causes buffer overrun

Status: RESOLVED FIXED

(Core :: DOM: Core & HTML, defect)

Description

[q1]

Attachment: bug399_poc_1.htm

nsAttrAndChildArray::GrowBy() (dom\base\nsAttrAndChildArray.cpp) can experience an integer overflow, which causes the function to allocate a buffer that is too small for the data that other members of nsAttrAndChildArray write into it. Probably the bug can be manifested only on x64 builds. The bug is in line 792:

765: bool
766: nsAttrAndChildArray::GrowBy(uint32_t aGrowSize)
767: {
768:   CheckedUint32 size = 0;
769:   if (mImpl) {
770:     size += mImpl->mBufferSize;
771:     size += NS_IMPL_EXTRA_SIZE;
772:     if (!size.isValid()) {
773:       return false;
774:     }
775:   }
776: 
777:   CheckedUint32 minSize = size.value();
778:   minSize += aGrowSize;
779:   if (!minSize.isValid()) {
780:     return false;
781:   }
782: 
783:   if (minSize.value() <= ATTRCHILD_ARRAY_LINEAR_THRESHOLD) {
784:     do {
785:       size += ATTRCHILD_ARRAY_GROWSIZE;
786:       if (!size.isValid()) {
787:         return false;
788:       }
789:     } while (size.value() < minSize.value());
790:   }
791:   else {
792:     size = 1u << mozilla::CeilingLog2(minSize.value());

...whose RHS undetectably overflows if minSize.value() >= 0x80000001. The rest of the expression then assigns the overflowed value to |size|, which views it as valid, so the later check on lines 798-800:

793:   }
794: 
795:   bool needToInitialize = !mImpl;
796:   CheckedUint32 neededSize = size;
797:   neededSize *= sizeof(void*);
798:   if (!neededSize.isValid()) {
799:     return false;
800:   }

doesn't detect the problem, causing line 802:

801: 
802:   Impl* newImpl = static_cast<Impl*>(realloc(mImpl, neededSize.value()));

to allocate a buffer that is far too small to contain the data.

I am currently running the attached POC to see whether it will crash FF, but it's slow, so I've posted the bug anyway.

You can demonstrate the bug by using the debugger to set aGrowSize such that line 778 computes minSize >= 0x80000001. Then step through line 792 and notice that |size| becomes tiny.

Cf. https://bugzilla.mozilla.org/show_bug.cgi?id=1172055 , which fixed other problems in this function, but left this one tiny window open.

The bug is still present in tip-of-the-tree trunk http://hg.mozilla.org/mozilla-central/file/tip/dom/base/nsAttrAndChildArray.cpp .

Comment 1

[Andrew Overholt [:overholt]]

baku, can you please take a look here? FWIW bug 651120 may remove this code entirely.
Nick, is it worth investigating making CeilingLog2 not overflow? Or something ...

Comment 2

[q1]

FWIW, the POC doesn't work. After running a very long time, it causes something else to hit a limit before it can cause line 792 to overflow. I guess that there probably is still a way to cause this overflow, but I don't know of one right now.

Comment 3

[Nicholas Nethercote [inactive]]

> Nick, is it worth investigating making CeilingLog2 not overflow? Or
> something ...

AIUI: The line in question:

> size = 1u << mozilla::CeilingLog2(minSize.value());

TheCeilingLog2() call is fine. It returns 32. Then we do |1u << 32|, which is undefined, because 32 is the number of bits in |1u|. There's a good chance the right-hand side will evaluate to zero, so |size| will be set to zero, so we'll erroneously allocate a zero-sized buffer.

Something like this should fix it:

> CheckedUint32 shift = mozilla::CeilingLog2(minSize.value());
> if (shift == 32) {
>   return false;
> }
> size = 1u << shift;

Comment 4

[q1]

(In reply to Nicholas Nethercote [:njn] from comment #3)
> > Nick, is it worth investigating making CeilingLog2 not overflow? Or
> > something ...
> 
> AIUI: The line in question:
> 
> > size = 1u << mozilla::CeilingLog2(minSize.value());
> 
> TheCeilingLog2() call is fine. It returns 32. Then we do |1u << 32|, which
> is undefined, because 32 is the number of bits in |1u|. There's a good
> chance the right-hand side will evaluate to zero, so |size| will be set to
> zero, so we'll erroneously allocate a zero-sized buffer.

That's basically what happens when you use the debugger to set |minSize| == 0x80000001, though the result is 1 instead of 0.

> 
> Something like this should fix it:
> 
> > CheckedUint32 shift = mozilla::CeilingLog2(minSize.value());
> > if (shift == 32) {
> >   return false;
> > }
> > size = 1u << shift;

For caution, I suggest ">=" instead of "==".

Comment 5

[Andrea Marchesini [:baku]]

Attachment: bug1288561.patch

Comment 6

[Andrew McCreight [:mccr8]]

This sounds difficulty or impossible to trigger, based on the test case, so I'm going to mark it sec-moderate.

Comment 7

[Wes Kocher (:KWierso) (Not reading bugmail; email directly if needed)]

https://hg.mozilla.org/mozilla-central/rev/bfee15680331