2003278 - Make nsTArray::Sort() safe-by-default again

Status: RESOLVED FIXED

(Core :: XPCOM, defect)

Description

[Andrew McCreight [:mccr8]]

Bug 1839051 changed nsTArray::Sort to use std::sort, which has the unfortunate property is that if the comparator isn't stable, you get out-of-bounds array accesses. Then, bug 1887697 changed nsTArray::Sort from using bounds checked iterators to raw pointers. This turns the out-of-bounds array accesses from safe crashes to sec-high bugs. Bug 1956780 at least added a debug check that the comparator is okay, but given the huge numbers of issues that has found, it doesn't feel right that we're unsafe by default.

According to this bugzilla query, we've had 16 different bugs filed about this assertion. 4 of those are still open, and another 4 are incomplete and inactive. That also doesn't include the issues filed directly as sec bugs, like bug 2001855 and bug 1944313. That is a huge source of security bugs that we could fix by basically reverting a single patch.

The only measured performance improvements from bug 1887697 was a MacOS installer size improvement, so I think we could make this change without causing problems. I think bug 1887697 was an interesting experiment to try, but I think we've failed the test here.

If somehow we do find that the change now causes a regression, we could add an unsafe variant and use that for callers that carefully check the validity, but I'm inclined to not worry about it unless we find a regression.

Comment 1

[BugBot [:suhaib / :marco]]

Set release status flags based on info from the regressing bug 1887697

:jstutte, since you are the author of the regressor, bug 1887697, could you take a look? Also, could you set the severity field?

For more information, please visit BugBot documentation.

Comment 2

[Emilio Cobos Álvarez [:emilio]]

I think keeping the weak-ordering assert is worth it tho, please don't remove it.

Comment 3

[Jens Stutte [:jstutte]]

FWIW, I totally forgot about bug 1887697. I assume we should use bounds checked iterators also for StableSort then, if possible.

Comment 4

[Andrew McCreight [:mccr8]]

(In reply to Emilio Cobos Álvarez [:emilio] from comment #2)

I think keeping the weak-ordering assert is worth it tho, please don't remove it.

Yeah, definitely. Using safe iterators will just turn weak-ordering failures from unsafe crashes to safe crashes, so we still want those checks.

Comment 5

[Jens Stutte [:jstutte]]

I assume we should use bounds checked iterators also for StableSort then, if possible.

Hmm, we had some bugs where we explicitly switched to a use without bound checks for performance reasons, see bug 1848765 and bug 1668200. Unfortunately there is no reported impact. I wonder if we want to have the choice.

Comment 6

[Jens Stutte [:jstutte]]

Attachment: (secure)

Comment 7

[Jens Stutte [:jstutte]]

Comment on attachment 9530100 [details]
(secure)

Security Approval Request

• How easily could an exploit be constructed based on the patch?: The patch does only reveal that std:sort/stable_sort in general may go out of bounds for bad comparators, which is probably well known. There is no hint on the motivating case from bug 2001855 or other related bugs.
  The exception added in the patch is for a case that motivated the change to not have bounds check in general and thus believed to be performance critical and well tested enough to be kept.
  So I'd say there is no other info here than trying to hammer on any sort may reveal issues we did not yet find ourselves.
• Do comments in the patch, the check-in comment, or tests included in the patch paint a bulls-eye on the security problem?: No
• Which branches (beta, release, and/or ESR) are affected by this flaw, and do the release status flags reflect this affected/unaffected state correctly?: All branches but 115 ESR. Flags seem up to date.
• If not all supported branches, which bug introduced the flaw?: Bug 1887697
• Do you have backports for the affected branches?: No
• If not, how different, hard to create, and risky will they be?: I assume the patch should graft cleanly on all affected branches.
• How likely is this patch to cause regressions; how much testing does it need?: The patch may cause performance regression we will want to monitor. We can add more exceptions if needed (and if we trust those comparators enough).
• Is the patch ready to land after security approval is given?: Yes
• Is Android affected?: Yes

Comment 8

[Andrew McCreight [:mccr8]]

So I'd say there is no other info here than trying to hammer on any sort may reveal issues we did not yet find ourselves.

We have a number of public fuzz bugs for the comparator assertion that probably give ways to trigger this issue. (See the link in the second paragraph of comment 0.) I'm not sure if we want to hide those or leave it alone.

Comment 9

[Jens Stutte [:jstutte]]

(In reply to Andrew McCreight [:mccr8] from comment #8)

So I'd say there is no other info here than trying to hammer on any sort may reveal issues we did not yet find ourselves.

We have a number of public fuzz bugs for the comparator assertion that probably give ways to trigger this issue. (See the link in the second paragraph of comment 0.) I'm not sure if we want to hide those or leave it alone.

Maybe? My claim was only about the patch's content, though one could suspect us having a problem in that area and start looking for issues found by the AssertStrictWeakOrder in bugzilla and/or crash-stats, of course. The patch is just not adding more information about exploitation but landing it might send a signal to search for them, indeed.

But what bothers me more is that bug 1957177 actually talks exactly about one of the exceptions I wanted to cargo-cult. Maybe we shouldn't keep any for now?

Comment 10

[Andrew McCreight [:mccr8]]

(In reply to Jens Stutte [:jstutte] from comment #9)

But what bothers me more is that bug 1957177 actually talks exactly about one of the exceptions I wanted to cargo-cult. Maybe we shouldn't keep any for now?

Ah good catch. I was meaning to go through and audit the open bugs to see if they matched the exceptions but I hadn't gotten to it.

Comment 11

[Emilio Cobos Álvarez [:emilio]]

If the performance cost of the bounds checking doesn't show up in benchmarks that seems fine.

Comment 12

[Jens Stutte [:jstutte]]

(In reply to Emilio Cobos Álvarez [:emilio] from comment #11)

If the performance cost of the bounds checking doesn't show up in benchmarks that seems fine.

I would actually put it the other way around: A comparator has to be trusted to consider disabling the bounds check. This one is known to be flaky, so...

Comment 13

[Jens Stutte [:jstutte]]

I checked the existing filed bugs and it seems we can keep the DisplayList exception. It is probably also good to have at least one use of this template magic in the codebase.

Comment 14

[Daniel Veditz [:dveditz]]

Comment on attachment 9530100 [details]
(secure)

granting early sec-approval so we can get a few extra days of nightly testing to help smoke out any problems. sec-approval+ , a=dveditz

Comment 15

[Pulsebot]

Pushed by [e-mail]:
https://github.com/mozilla-firefox/firefox/commit/cb8cb1c5374b
https://hg.mozilla.org/integration/autoland/rev/155b1621d551
Have a SortBoundsCheck option for nsTArray Sort and StableSort. r=xpcom-reviewers,layout-reviewers,emilio

Comment 16

[Sebastian Hengst [:aryx] (needinfo me if it's about an intermittent or backout)]

https://hg.mozilla.org/mozilla-central/rev/155b1621d551

Comment 17

[Jens Stutte [:jstutte]]

Note that we may see some negative impact on code size, see bug 1887697 comment 7. That is probably expected and unavoidable.

Comment 18

[Jens Stutte [:jstutte]]

Attachment: (secure)

Original Revision: https://phabricator.services.mozilla.com/D274620

Comment 19

[Phabricator Automation]

firefox-esr140 Uplift Approval Request

• User impact if declined: This mitigates the security impact of std::sort going out of bounds with faulty comparators, seen on bug 1957177, bug 1978693, bug 1980313, bug 2001855 and bug1956867 (which will continue to crash but safely).
• Code covered by automated testing: yes
• Fix verified in Nightly: yes
• Needs manual QE test: no
• Steps to reproduce for manual QE testing:
• Risk associated with taking this patch: low
• Explanation of risk level: Patch is in Nightly and Beta 147.
• String changes made/needed: none
• Is Android affected?: yes

Comment 20

[Pulsebot]

https://hg.mozilla.org/releases/mozilla-esr140/rev/4ac0e6666d7b

Comment 21

[Jens Stutte [:jstutte]]

The regression is expected, we simply have to inline more code at each call site. I do not want to chat too much in that not-hidden bug about the reasons.