1171603 - (CVE-2015-4487) Overflow nsTSubstring::ReplacePrep causes memory-safety bugs in string library

Status: RESOLVED FIXED

(Core :: XPCOM, defect)

Description

[q1]

User Agent: Mozilla/5.0 (Windows NT 5.1; rv:36.0) Gecko/20100101 Firefox/36.0
Build ID: 20150305021524

Steps to reproduce:

nsTSubstring::ReplacePrep (C:\docs\dev\firefox\source\38.0.1\xpcom\string\nsTSubstring.h) can cause memory to be written that the destination string object does not own. This bug could permit an attacker to write portions of Firefox's address space, potentially allowing her to execute code of her choice.

The bug is in line 1003:

 998:  NS_WARN_UNUSED_RESULT bool ReplacePrep(index_type aCutStart,
 999:                                         size_type aCutLength,
1000:                                         size_type aNewLength)
1001:  {
1002:    aCutLength = XPCOM_MIN(aCutLength, mLength - aCutStart);
1003:    uint32_t newTotalLen = mLength - aCutLength + aNewLength;
1004:    if (aCutStart == mLength && Capacity() > newTotalLen) {
1005:      mFlags &= ~F_VOIDED;
1006:      mData[newTotalLen] = char_type(0);
1007:      mLength = newTotalLen;
1008:      return true;
1009:    }
1010:    return ReplacePrepInternal(aCutStart, aCutLength, aNewLength, newTotalLen);
1011:  }

If aCutStart > mLength, aCutLength becomes a very large uint32_t. The same thing happens if aCutLength is very large, or if aNewLength is very large. In all of these cases, newTotalLen can overflow, resulting in a call to ReplacePrepInternal with a too-small newTotalLen.


The simplest case is where aNewLength is very large.

Using aNewLength == 0xfffffffe and mLength == 10 for the existing string, imagine a call to Append (&s, 0xfffffffe). (The same kind of thing works on AppendASCII, etc.). Append lives at nsTSubstring.h line 531:

531:  void Append(const char_type* aData, size_type aLength = size_type(-1))
532:  {
533:    Replace(mLength, 0, aData, aLength);
534:  }
 
The call to Replace resolves to the function at nsTSubstring.cpp line 502 with arguments (10, 0, &s, 0xfffffffe):

502: void
503: nsTSubstring_CharT::Replace(index_type aCutStart, size_type aCutLength,
504:                             const char_type* aData, size_type aLength)
505: {
506:   if (!Replace(aCutStart, aCutLength, aData, aLength,
507:                mozilla::fallible)) {
508:     AllocFailed(Length() - aCutLength + 1);
509:   }
510: }

which then chains to the function at nsTSubstring.cpp line 512 with arguments (10, 0, &s, 0xfffffffe, mozilla::fallible)):

512: bool
513: nsTSubstring_CharT::Replace(index_type aCutStart, size_type aCutLength,
514:                             const char_type* aData, size_type aLength,
515:                             const fallible_t& aFallible)
516: {
517:   // unfortunately, some callers pass null :-(
518:   if (!aData) {
519:     aLength = 0;
520:   } else {
521:     if (aLength == size_type(-1)) {
522:       aLength = char_traits::length(aData);
523:     }
524: 
525:     if (IsDependentOn(aData, aData + aLength)) {
526:       nsTAutoString_CharT temp(aData, aLength);
527:       return Replace(aCutStart, aCutLength, temp, aFallible);
528:     }
529:   }
530: 
531:   aCutStart = XPCOM_MIN(aCutStart, Length());
532: 
533:   bool ok = ReplacePrep(aCutStart, aCutLength, aLength);
534:   if (!ok) {
535:     return false;
536:   }
537: 
538:   if (aLength > 0) {
539:     char_traits::copy(mData + aCutStart, aData, aLength);
540:   }
541: 
542:   return true;
543: }

Control passes to line 525, which returns false because aData does not overlap mData. Line 531 then computes 10 for aCutStart, so line 533 calls ReplacePrep (10, 0, 0xfffffffe). That function:

 998:  NS_WARN_UNUSED_RESULT bool ReplacePrep(index_type aCutStart,
 999:                                         size_type aCutLength,
1000:                                         size_type aNewLength)
1001:  {
1002:    aCutLength = XPCOM_MIN(aCutLength, mLength - aCutStart);
1003:    uint32_t newTotalLen = mLength - aCutLength + aNewLength;
1004:    if (aCutStart == mLength && Capacity() > newTotalLen) {
1005:      mFlags &= ~F_VOIDED;
1006:      mData[newTotalLen] = char_type(0);
1007:      mLength = newTotalLen;
1008:      return true;
1009:    }
1010:    return ReplacePrepInternal(aCutStart, aCutLength, aNewLength, newTotalLen);
1011:  }

computes aCutLength == 0 on line 1002, and newTotalLen == 10 - 0 + 0xfffffffe == 8 on line 1003. The test on line 1004 passes, line 1006 spuriously writes a 0 to mData [8], and control returns to the caller (nsTSubstring_CharT::Replace) at line 534. Control then eventually passes to line 539:

539:     char_traits::copy(mData + aCutStart, aData, aLength);

which copies 0xfffffffe bytes from aData into the unallocated region beginning at mData + 10.

Comment 1

[Mats Palmgren (inactive)]

IIRC, we analyzed these methods for integer overflow a year or two ago.

Comment 2

[Mats Palmgren (inactive)]

> If aCutStart > mLength

I'm pretty sure that can't occur.  I buried this in some large Grid patches:
+    MOZ_ASSERT(aCutStart <= mLength);
and it looks green on Try:
https://treeherder.mozilla.org/#/jobs?repo=try&revision=bbe6413ac829

There is also an implicit invariant that string lengths (mLength) are < 2G:
http://mxr.mozilla.org/mozilla-central/source/xpcom/string/nsTSubstring.cpp#44

I suspect that we have very few calls to Append[ASCII] that pass a length
that isn't a string length.

Have you found any instances where aNewLength in ReplacePrep isn't a string length?

Comment 3

[q1]

(In reply to Mats Palmgren (:mats) from comment #2)
> > If aCutStart > mLength
> 
> I'm pretty sure that can't occur.  I buried this in some large Grid patches:
> +    MOZ_ASSERT(aCutStart <= mLength);
> and it looks green on Try:
> https://treeherder.mozilla.org/#/jobs?repo=try&revision=bbe6413ac829

I am not familiar with this test. Can you explain it?

> There is also an implicit invariant that string lengths (mLength) are < 2G:
> http://mxr.mozilla.org/mozilla-central/source/xpcom/string/nsTSubstring.
> cpp#44

I'll look at that. Thanks.
 
> I suspect that we have very few calls to Append[ASCII] that pass a length
> that isn't a string length.
>
> Have you found any instances where aNewLength in ReplacePrep isn't a string
> length?

If you mean instances where the length passed into Append[AScII] is not implicitly specified by a literal, and where the body and length of a ns*String are not passed in, yes, there are quite a few. Here's a nonexhaustive list:

StringBuilder::ToString in (38.0.1\dom\base\FragmentOrElement.cpp line 2224)
nsFeedSniffer::AppendSegmentToString (38.0.1\browser\components\feeds\nsFeedSniffer.cpp line 343)
AppendSegmentToString (38.0.1\docshell\base\nsDocShell.cpp line 10823)
nsContentUtils::GetPseudoAttributeValue (38.0.1\dom\base\nsContentUtils.cpp line 1131; this one _appears_ safe)
nsPlainTextSerializer::AddToLine (38.0.1\dom\base\nsPlainTextSerializer.cpp line 1249)
nsXMLHttpRequest::StreamReaderFunc (38.0.1\dom\base\nsXMLHttpRequest.cpp line 1843)
DictionaryBase::AppendJSONToString (38.0.1\dom\bindings\BindingUtils.cpp line 1734)
TextDecoder::Decode (38.0.1\dom\encoding\TextDecoder.cpp line 77)
nsJSONWriter::Write (38.0.1\dom\json\nsJSON.cpp line 305 & 311)
nsJSONWriter::FlushBuffer() (38.0.1\dom\json\nsJSON.cpp line 328)
AppendSegmentToString (38.0.1\dom\security\nsCSPContext.cpp line 1210)
nsBase64Encoder::Write (38.0.1\netwerk\base\nsBase64Encoder.cpp line 27)
CopyRawHeader (\38.0.1\netwerk\mime\nsMIMEHeaderParamImpl.cpp line 1082)


Even if all these usages currently are safe (which I don't know), the string library should protect itself from bad arguments, so that someone doesn't inadvertently add a security bug.

Comment 4

[Mats Palmgren (inactive)]

(In reply to q1 from comment #3)
> (In reply to Mats Palmgren (:mats) from comment #2)
> > > If aCutStart > mLength
> > 
> > I'm pretty sure that can't occur.  I buried this in some large Grid patches:
> > +    MOZ_ASSERT(aCutStart <= mLength);
> > and it looks green on Try:
> > https://treeherder.mozilla.org/#/jobs?repo=try&revision=bbe6413ac829
> 
> I am not familiar with this test. Can you explain it?

I added the above assertion to the code and then ran all our
regression test suites with that change and the tests passed.

ReplacePrep is an internal method so I think that assertion
is good enough to cover any mistake with 'aCutStart'.

> Even if all these usages currently are safe (which I don't know), the string
> library should protect itself from bad arguments, so that someone doesn't
> inadvertently add a security bug.

Sure.  Using CheckedInt for calculating 'newTotalLen' and returning
false if it overflows seems reasonable.  I wonder why we didn't
do that when we looked at this earlier though.

Comment 5

[Andrea Marchesini [:baku]]

Attachment: crash7.patch

Comment 6

[Mats Palmgren (inactive)]

Comment on attachment 8625450 [details] [diff] [review]
crash7.patch

Looks good to me.  You should get r+ from a module peer though (I'm not).

Comment 7

[Andrea Marchesini [:baku]]

Comment on attachment 8625450 [details] [diff] [review]
crash7.patch

ehsan, move this patch if your review queue is too crazy.

Comment 8

[Ryan VanderMeulen [:RyanVM]]

Needs a sec rating and/or sec-approval before landing.

Comment 9

[Andrea Marchesini [:baku]]

Attachment: crash7.patch

[Security approval request comment]
How easily could an exploit be constructed based on the patch?

Not easy at all.

Do comments in the patch, the check-in comment, or tests included in the patch paint a bulls-eye on the security problem?

The problem is well described in the bug.

Which older supported branches are affected by this flaw?

all.

Do you have backports for the affected branches? If not, how different, hard to create, and risky will they be?

It should be easy to port this patch everywhere in case it doesn't apply.

How likely is this patch to cause regressions; how much testing does it need?

I don't see how it can cause regressions.

Comment 10

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

Do you have a suggestion as to the security rating? Can we actually trigger this bug?

Comment 11

[Andrea Marchesini [:baku]]

I don't think it's possible to trigger this bug. Or at least we need to play with a string with length close to 2^32.
I would say sec-moderate or less.

Comment 12

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

Comment on attachment 8628244 [details] [diff] [review]
crash7.patch

Clearing sec-approval?. As a bug that isn't a sec-high or sec-critical, it doesn't need sec-approval+ to be checked in.

Comment 13

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/97c7e83acb6b

Comment 14

[Ryan VanderMeulen [:RyanVM]]

Backed out for Windows Werror bustage.
https://treeherder.mozilla.org/logviewer.html#?job_id=11315031&repo=mozilla-inbound

Comment 15

[Andrea Marchesini [:baku]]

Attachment: crash7.patch

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

Comment 16

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/9d8209f754df

Comment 17

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

https://hg.mozilla.org/mozilla-central/rev/9d8209f754df

Comment 18

[Ryan VanderMeulen [:RyanVM]]

Please nominate this for aurora/beta/esr38/b2g37/b2g34 approval when you get a chance.

Comment 19

[Andrea Marchesini [:baku]]

Comment on attachment 8629539 [details] [diff] [review]
crash7.patch

[Approval Request Comment]
Bug caused by (feature/regressing bug #): this is old code.
User impact if declined: possibly a crash
Testing completed: none
Risk to taking this patch (and alternatives if risky): none 
String or UUID changes made by this patch: none

Comment 20

[Sylvestre Ledru [:Sylvestre]]

Comment on attachment 8629539 [details] [diff] [review]
crash7.patch

Fix a crash, taking it for aurora & beta.
However, not for esr 38 as it is just a sec moderate and it does not seem to be a critical issue from the user perspective.

Comment 21

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/releases/mozilla-aurora/rev/5d348e83333b

Comment 22

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/releases/mozilla-beta/rev/25e950d0b041

Comment 23

[Josh Cheng [:josh]]

Comment on attachment 8629539 [details] [diff] [review]
crash7.patch

Seems very edge and not critical. Also NI new FxOS RM Mahi if he has different opinion.

Comment 24

[Mahendra Potharaju [:mahe]]

Agree with Josh. Thanks for adding me to the loop.

Comment 25

[Carsten Book [:Tomcat]]

removing the b2g 2.5 flag since this commit has been reverted due to an incorrect merge, sorry for the confusion