585815 - (CVE-2010-2760) Possible unfixed nsTreeSelection dangling pointer issues from bug 571106 (ZDI-CAN-903)

Status: RESOLVED FIXED

(Core :: XUL, defect)

Description

[Reed Loden [:reed]]

ZDI just notified us that the researcher who reported ZDI-10-131 (Mozilla Firefox nsTreeSelection Dangling Pointer Remote Code Execution Vulnerability), also known as bug 571106, has reported that the vulnerability is still an issue even though a patch was released.

Need to make sure that the entirety of the researcher's original report has been fixed and not just what the PoC may be showing. I will follow-up with ZDI to see if there is a better testcase for the issue.

Since I accidentally submitted bug 571106, comment #0 with extra blank lines, I will repaste the original report in the next comment.

Comment 1

[Reed Loden [:reed]]

ZDI-CAN-755: Mozilla Firefox nsTreeSelection Dangling Pointer Remote Code Execution Vulnerability

-- ABSTRACT ------------------------------------------------------------

TippingPoint has identified a vulnerability affecting the following 
products:

    Mozilla Firefox 3.6.x

-- VULNERABILITY DETAILS -----------------------------------------------

This vulnerability allows remote attackers to execute arbitrary code on
vulnerable installations of Mozilla Firefox. User interaction is
required to exploit this vulnerability in that the target must visit a
malicious page or open a malicious file.

The specific flaw exists within the implementation of XUL <tree>
element's "selection" attribute. There is an integer overflow when
calculating the bounds of a new selection range. When calling
adjustSelection on this manged range both ranges are deleted leaving a
dangling reference. A remote attacker can exploit this vulnerability to
execute arbitrary code under the context of the browser.


View of XUL <tree> element exposes "selection" attribute. This in turn
allows user to precisely choose set of tree's rows to be shown as
selected. The way class nsTreeSelection
(layout/xul/base/src/tree/src/nsTreeSelection.cpp) is implemented is
quite interesting: with a linked list of nsTreeRange instances where
nsTreeRange represents single continuous range of selected rows (and
possibly a pointer to the next range). nsTreeSelection holds directly
only one pointer, to the first range, mFirstRange.

What is also important to note: whenever any nsTreeRange instance is
deleted, delete (inside destructor) is called recursively on the next
linked instances as well.

Imagine we have the following piece of Javascript code:

  [1]  sel = tree.treeBoxObject.view.selection;
  [2]  sel.rangedSelect(0, 0x7fffffff, true);
  [3]  sel.adjustSelection(1, 1);

At [1] we grab the reference to selection object. At this moment
mFirstRange is null, no row is selected, so there is no need for any
range to keep track of.

Then [2] we call method rangedSelect(). From
nsTreeSelection::RangedSelect():

  ...
  PRInt32 start = aStartIndex < aEndIndex ? aStartIndex : aEndIndex;
  PRInt32 end = aStartIndex < aEndIndex ? aEndIndex : aStartIndex;
  ...
  nsTreeRange* range = new nsTreeRange(this, start, end);
  if (!range)
    return NS_ERROR_OUT_OF_MEMORY;

  range->Invalidate();

  if (aAugment && mFirstRange)
    mFirstRange->Insert(range);
  else
    mFirstRange = range;
  ...

That makes mFirstRange being set to range <0, 2G>, or more precisely
(yet in ad hoc pseudo code):

  mFirstRange = {
    min:  0,
    max:  2G,
    prev: null,
    next: null
  }

And at [3] we hit integer overflow that causes a lot of trouble. From
nsTreeSelection::AdjustSelection(PRInt32 aIndex, PRInt32 aCount):

  ...
  nsTreeRange* newRange = nsnull;

  PRBool selChanged = PR_FALSE;
  nsTreeRange* curr = mFirstRange;
  while (curr) {
    if (aCount > 0) {
      // inserting
      if (aIndex > curr->mMax) {
        ...
      }
      else if (aIndex <= curr->mMin) {
        ...
      }
      else {
        // adjustment happen inside the range.
        // break apart the range and create two ranges
        ADD_NEW_RANGE(newRange, this, curr->mMin, aIndex - 1);
        ADD_NEW_RANGE(newRange, this, aIndex + aCount, curr->mMax +
aCount);
        selChanged = PR_TRUE;
      }
    }
    else {
      ...
    }
    curr = curr->mNext;
  }

  delete mFirstRange;
  mFirstRange = newRange;
  ...

As we are calling AdjustSelection(1, 1), two ADD_NEW_RANGE() are
executed.
This means that something like <0, 0>.Insert(<2, -2G>) will be called.
Notice that because of integer overflow lower bound (2) is above higher
bound (-2G).

  void Insert(nsTreeRange* aRange) {
    if (mMin >= aRange->mMax)
      aRange->Connect(mPrev, this);
    else if (mNext)
      mNext->Insert(aRange);
    else 
      aRange->Connect(this, nsnull);
  }

So, now <2, -2G>.Connect(mPrev = null, <0, 0>):

  void Connect(nsTreeRange* aPrev = nsnull, nsTreeRange* aNext = nsnull)
{
    if (aPrev)
      aPrev->mNext = this;
    else
      mSelection->mFirstRange = this;

    if (aNext)
      aNext->mPrev = this;

    mPrev = aPrev;
    mNext = aNext;
  }

Which results in:

  mFirstRange = {
    min:  2,
    max:  -2G,
    prev: null,
    next: {
      min:  0,
      max:  0,
      prev: mFirstRange,
      next: null
    }
  }

But we can not forget about the epilogue of AdjustSelection():

  delete mFirstRange;
  mFirstRange = newRange;

Final result: both ranges (<2, -2G>, <0, 0>) are deleted and mFirstRange
points at deleted range <0, 0>.

-- CREDIT --------------------------------------------------------------

This vulnerability was discovered by:
    * regenrecht

Comment 2

[Olli Pettay [:smaug][[e-mail]]]

uh, right deleting mFirstRange.
I'm not sure what kind of behavior we want.

Comment 3

[Olli Pettay [:smaug][[e-mail]]]

Attachment: wip

This is just an idea, totally untested.

Comment 4

[Olli Pettay [:smaug][[e-mail]]]

But still trying to find some testcase where the crash might happen.

Comment 5

[Olli Pettay [:smaug][[e-mail]]]

Ok, I have a testcase.

Comment 6

[Olli Pettay [:smaug][[e-mail]]]

Attachment: a testcase

Comment 7

[Al Billings [:abillings - ex-MoCo]]

(In reply to comment #6)
> Created attachment 464482 [details]
> a testcase

That crashes 1.9.2.8 reliably.

Comment 8

[Robert O'Callahan (:roc) (email my personal email if necessary)]

Olli, any idea how long this will take to fix?

Comment 9

[Olli Pettay [:smaug][[e-mail]]]

Doing this right now. Trying to find some not-very-ugly solution, and if that
doesn't work, will do the ugly way.

Comment 10

[Olli Pettay [:smaug][[e-mail]]]

Attachment: patch

This is the simple, not so ugly approach.
Other would be to validate all the indexes everywhere. That would easily leave some errors.

I haven't pushed this to comm-central Tryserver. I believe Thunderbird has some tests for AdjustSelection.

(Btw, I found at least one possible nsTreeRange leak while going through the 
 code. It is a 'safe' leak. I'll file a bug.)

Comment 11

[[e-mail]]

Comment on attachment 464598 [details] [diff] [review]
patch

>     if (aCount > 0) {
So, one thought I had was that we should call mFirstRange->RemoveRange(PR_INT32_MAX + ~aCount, -aCount) first, which would mean that we don't have to worry about range-checking the added ranges (this would presumably also make the patch on bug 571106 unnecessary).

>+  // Creating new ranges may have set mFirstRange.
>+  if (!mFirstRange) {
>+    mFirstRange = newRange;
Alternatively, I would just get rid of newRange and use mFirstRange throughout. It makes it more obvious that the code is doing the right thing.

Comment 12

[Olli Pettay [:smaug][[e-mail]]]

Attachment: patch

Comment 13

[Olli Pettay [:smaug][[e-mail]]]

http://hg.mozilla.org/mozilla-central/rev/d10ea35df086

Comment 14

[LegNeato]

Comment on attachment 464774 [details] [diff] [review]
patch

a=LegNeato for 1.9.2.9 and 1.9.1.12.

Please note that for these releases code-freeze is TONIGHT @ 11:59 pm PST. This needs to be landed as soon as possible.

Comment 15

[Daniel Veditz [:dveditz]]

Attachment: new PoC from ZDI

This is the new PoC ZDI sent us for the part they think is unfixed. Let's test the patch against this and make sure we're not dealing with two different security bugs and missing the one they know about again.

Comment 16

[Daniel Veditz [:dveditz]]

Comment 1 repeats the advisory from bug 571106, here's the advisory sent with the PoC I just attached.

ZDI-CAN-903: Mozilla Firefox nsTreeSelection Dangling Pointer Remote Code Execution Vulnerability

-- CVSS ----------------------------------------------------------------
10, (AV:N/AC:L/Au:N/C:C/I:C/A:C)

-- ABSTRACT ------------------------------------------------------------

TippingPoint has identified a vulnerability affecting the following 
products:

    Mozilla Firefox 3.6.x

-- VULNERABILITY DETAILS -----------------------------------------------

This vulnerability allows remote attackers to execute arbitrary code on
vulnerable installations of Mozilla Firefox. User interaction is
required to exploit this vulnerability in that the target must visit a
malicious page or open a malicious file.

The specific flaw exists within the fix implemented for CVE-2010-2753 in
the nsTreeSelection interface. In a certain condition, the application
still can be made to free a reference and then made to use said freed
reference. This can lead to code execution under the context of the
application.

This is a rudimentary advisory. The issue is suspected to be located in
the following code. The specific pointer that has been freed is newRange
and is assigned to mFirstRange. To reproduce please see the provided
proof-of-concept.

source/layout/xul/base/src/tree/src/nsTreeSelection.cpp:
716 NS_IMETHODIMP
717 nsTreeSelection::AdjustSelection(PRInt32 aIndex, PRInt32 aCount)
718 {
719   NS_ASSERTION(aCount != 0, "adjusting by zero");
720   if (!aCount) return NS_OK;
721 
722   // adjust mShiftSelectPivot, if necessary
723   if ((mShiftSelectPivot != 1) && (aIndex <= mShiftSelectPivot)) {
724     // if we are deleting and the delete includes the shift select
pivot, reset it
725     if (aCount < 0 && (mShiftSelectPivot <= (aIndex -aCount -1))) {
726         mShiftSelectPivot = -1;
727     }
728     else {
729         mShiftSelectPivot += aCount;
730     }
731   }
732 
733   // adjust mCurrentIndex, if necessary
734   if ((mCurrentIndex != -1) && (aIndex <= mCurrentIndex)) {
735     // if we are deleting and the delete includes the current index,
reset it
736     if (aCount < 0 && (mCurrentIndex <= (aIndex -aCount -1))) {
737         mCurrentIndex = -1;
738     }
739     else {
740         mCurrentIndex += aCount;
741     }
742   }
743 
744   // no selection, so nothing to do.
745   if (!mFirstRange) return NS_OK;
746 
747   nsTreeRange* newRange = nsnull;
748 
749   PRBool selChanged = PR_FALSE;
750   nsTreeRange* curr = mFirstRange;
751   while (curr) {
752     if (aCount > 0) {
753       // inserting
754       if (aIndex > curr->mMax) {
755         // adjustment happens after the range, so no change
756         ADD_NEW_RANGE(newRange, this, curr->mMin, curr->mMax);
757       }
758       else if (aIndex <= curr->mMin) {  
759         // adjustment happens before the start of the range, so
shift down
760         ADD_NEW_RANGE(newRange, this, curr->mMin + aCount,
curr->mMax + aCount);
761         selChanged = PR_TRUE;
762       }
763       else {
764         // adjustment happen inside the range.
765         // break apart the range and create two ranges
766         ADD_NEW_RANGE(newRange, this, curr->mMin, aIndex - 1);
767         ADD_NEW_RANGE(newRange, this, aIndex + aCount, curr->mMax +
aCount);
768         selChanged = PR_TRUE;
769       }
770     }
771     else {
772       // deleting
773       if (aIndex > curr->mMax) {
774         // adjustment happens after the range, so no change
775         ADD_NEW_RANGE(newRange, this, curr->mMin, curr->mMax);
776       }
777       else {
778         // remember, aCount is negative
779         selChanged = PR_TRUE;
780         PRInt32 lastIndexOfAdjustment = aIndex - aCount - 1;
781         if (aIndex <= curr->mMin) {
782           if (lastIndexOfAdjustment < curr->mMin) {
783             // adjustment happens before the start of the range, so
shift up
784             ADD_NEW_RANGE(newRange, this, curr->mMin + aCount,
curr->mMax + aCount);
785           }
786           else if (lastIndexOfAdjustment >= curr->mMax) {
787             // adjustment contains the range.  remove the range by
not adding it to the newRange
788           }
789           else {
790             // adjustment starts before the range, and ends in the
middle of it, so trim the range
791             ADD_NEW_RANGE(newRange, this, aIndex, curr->mMax +
aCount)
792           }
793         }
794         else if (lastIndexOfAdjustment >= curr->mMax) {
795          // adjustment starts in the middle of the current range,
and contains the end of the range, so trim the range
796          ADD_NEW_RANGE(newRange, this, curr->mMin, aIndex - 1)
797         }
798         else {
799           // range contains the adjustment, so shorten the range
800           ADD_NEW_RANGE(newRange, this, curr->mMin, curr->mMax +
aCount)
801         }
802       }
803     }
804     curr = curr->mNext;
805   }
806 
807   delete mFirstRange;   // XXX
808   mFirstRange = newRange;
809 
810   // Fire the select event
811   if (selChanged)
812     FireOnSelectHandler();
813 
814   return NS_OK;
815 }

source/layout/xul/base/src/tree/src/nsTreeSelection.cpp:
438 NS_IMETHODIMP nsTreeSelection::RangedSelect(PRInt32 aStartIndex,
PRInt32 aEndIndex, PRBool aAugment)
439 {
440   PRBool single;
441   nsresult rv = GetSingle(&single);
442   if (NS_FAILED(rv))
443     return rv;
444 
445   if ((mFirstRange || (aStartIndex != aEndIndex)) && single)
446     return NS_OK;
447 
448   if (!aAugment) {
449     // Clear our selection.
450     if (mFirstRange) {
451         mFirstRange->Invalidate();
452         delete mFirstRange;
453     }
454   }
455 
456   if (aStartIndex == -1) {
457     if (mShiftSelectPivot != -1)
458       aStartIndex = mShiftSelectPivot;
459     else if (mCurrentIndex != -1)
460       aStartIndex = mCurrentIndex;
461     else
462       aStartIndex = aEndIndex;
463   }
464 
465   mShiftSelectPivot = aStartIndex;
466   rv = SetCurrentIndex(aEndIndex);
467   if (NS_FAILED(rv))
468     return rv;
469   
470   PRInt32 start = aStartIndex < aEndIndex ? aStartIndex :
aEndIndex;
471   PRInt32 end = aStartIndex < aEndIndex ? aEndIndex : aStartIndex;
472 
473   if (aAugment && mFirstRange) {
474     // We need to remove all the items within our selected range
from the selection,
475     // and then we insert our new range into the list.
476     nsresult rv = mFirstRange->RemoveRange(start, end);
477     if (NS_FAILED(rv))
478       return rv;
479   }
480 
481   nsTreeRange* range = new nsTreeRange(this, start, end);   // XXX
482   if (!range)
483     return NS_ERROR_OUT_OF_MEMORY;
484 
485   range->Invalidate();
486 
487   if (aAugment && mFirstRange)
488     mFirstRange->Insert(range);
489   else
490     mFirstRange = range;        // XXX
491 
492   FireOnSelectHandler();
493 
494   return NS_OK;
495 }

Version(s)  tested: Mozilla Firefox 3.6.6
Platform(s) tested: Windows XP SP3

-- CREDIT --------------------------------------------------------------

This vulnerability was discovered by:
    * regenrecht

Comment 17

[Olli Pettay [:smaug][[e-mail]]]

http://hg.mozilla.org/releases/mozilla-1.9.2/rev/dde129cb7505
http://hg.mozilla.org/releases/mozilla-1.9.1/rev/579e8ff3f1f2

Without the patch I can reproduce the crash using the poc, the patch
does seem to fix it.

(Pushed a bit late, sorry about that.)

Comment 18

[Daniel Veditz [:dveditz]]

Thanks! I also tested Olli's testcase and the zdi PoC, and today's minefield fixes both versions.

It would be nice to work both variants (testing both ends of the range) into an in-tree regression test after we ship the branch fixes.

Comment 19

[Al Billings [:abillings - ex-MoCo]]

Verified fixed for 1.9.2.9 with Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.9.2.9pre) Gecko/20100817 Namoroka/3.6.9pre ( .NET CLR 3.5.30729) and for 1.9.1.12 with Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.9.1.12pre) Gecko/20100817 Shiretoko/3.5.12pre ( .NET CLR 3.5.30729) using attached testcase and new PoC. Both of these tests crash in 1.9.2.8 and 1.9.1.11 but not in post-fix nightlies.

Comment 20

[Mats Palmgren (inactive)]

Crash test:
https://hg.mozilla.org/integration/mozilla-inbound/rev/124faac1aae7

Comment 21

[Phil Ringnalda (:philor)]

https://hg.mozilla.org/mozilla-central/rev/124faac1aae7