Closed Bug 1528829 (CVE-2019-9793) Opened 1 year ago Closed 1 year ago

Arbitrary range mis-inference due to loop phi range analysis disregarding overflows/truncation

Categories

(Core :: JavaScript Engine: JIT, defect, P1)

defect

Tracking

()

RESOLVED FIXED
mozilla67
Tracking Status
firefox-esr60 66+ fixed
firefox65 --- wontfix
firefox66 + fixed
firefox67 + fixed

People

(Reporter: niklas.baumstark, Assigned: nbp)

References

Details

(4 keywords, Whiteboard: [reporter-external] [client-bounty-form] [verif?][jsbugmon:update,testComment=2,origRev=dd4aa59c6a12][post-critsmash-triage][adv-main66+][adv-esr60.6+])

Attachments

(4 files)

Attached file writeup.md

The bug exists in the current release and mozilla-central branches of the Spidermonkey engine included in Firefox. It exists on all platforms.

The issue lets an attacker produce an arbitrary value in compiled JavaScript code, for which the range analysis will infer a fully controlled, incorrect range. For a detailed analysis of the issue and its exploitability, along with reproducing code samples, please refer to the attached writeup.md file.

Flags: sec-bounty?

In case you will fix this bug as a security issue, please credit "Bruno Keith & Niklas Baumstark from the phoenhex team"

Group: firefox-core-security → javascript-core-security
Component: Security → JavaScript Engine: JIT
Product: Firefox → Core
Flags: needinfo?(nicolas.b.pierron)
Keywords: sec-critical

Slightly more reduced:

function f(o) {
    o += 1;
    o += -2147483647;
    for (let i = 0; i < 1; ++i) {
        o -= 1;
    }
}
f(0);
f(0);
f(2147483647);

asserts on m-c rev dd4aa59c6a12 on a build compiled with --enable-debug --enable-more-deterministic and run with --fuzzing-safe --no-threads --ion-warmup-threshold=0 --baseline-eager --ion-check-range-analysis at:

Assertion failure: Integer input should be lower or equal than Upperbound., at js/src/jit/MacroAssembler.cpp:2029

Status: UNCONFIRMED → NEW
Ever confirmed: true
Whiteboard: [reporter-external] [client-bounty-form] [verif?] → [reporter-external] [client-bounty-form] [verif?][jsbugmon:update,testComment=2,origRev=dd4aa59c6a12]

(apparently we weren't testing --ion-warmup-threshold=0 . fuzz-flags.txt only tests the value of 100, and this testcase does not reproduce with 100, only with 10 and 0 (values that I tested).)

https://hg.mozilla.org/mozilla-central/annotate/dd4aa59c6a12/js/src/shell/fuzz-flags.txt

Assignee: nobody → nicolas.b.pierron
Status: NEW → ASSIGNED
Flags: needinfo?(nicolas.b.pierron)

Ok, if I understand correctly, the issue is in Fold Linear Arithmetic, as it mistakenly join an overflow with an underflow check.
While both checks are the same, it seems safe to join an overflow check with an overflow check as well as joining an underflow check with an underflow check.

Range Analysis assumed that both the overflow checks and the underflow checks would result in a bailout and that the range can safely be computed within the non-bailing bounds. However, folding an overflow with an underflow is shrinking the range from both sides.

This issue can be solved by either inserting a bound-check instruction or by forbidding folding overflow with underflow checks.

Thanks to Bruno Keith & Niklas Baumstark from the phoenhex team for finding this
issue and reporting it with a proper analysis.

Comment on attachment 9044938 [details]
Bug 1528829 - Restrict ExtractLinearSum to monotonous operation in infinite math space.

As this is a Range Analysis related topic, we have the 2 reviewer implicit policy. Feel free to create a phabricator account or to report it here.

Attachment #9044938 - Flags: review?(sunfish)

I have an account on phabricator now, but I don't currently have permissions to view the patch.

Flags: needinfo?(nicolas.b.pierron)
Flags: needinfo?(nicolas.b.pierron)
Attachment #9044938 - Flags: review?(sunfish)

(In reply to Dan Gohman [:sunfish] from comment #8)

I have an account on phabricator now, but I don't currently have permissions to view the patch.

Now you should be able to view the patch and review it.

autobisectjs shows this is probably related to the following changeset:

The first bad revision is:
changeset: https://hg.mozilla.org/mozilla-central/rev/07358be0ec02
user: Sander Mathijs van Veen
date: Tue Oct 11 07:04:00 2016 +0200
summary: Bug 1295130 - Fold AddI opcode with constant into other AddI with constant r=nbp

Bug 1295130 may have been the regressor here.

Blocks: 1295130

(In reply to Gary Kwong [:gkw] [:nth10sd] from comment #10)

Bug 1295130 may have been the regressor here.

This sounds more than likely to be the case. As it introduces the optimization which is folding the overflow check with the underflow check.

I will proof-read similar code before asking for approval & uplift.

Comment on attachment 9044938 [details]
Bug 1528829 - Restrict ExtractLinearSum to monotonous operation in infinite math space.

Security Approval Request

How easily could an exploit be constructed based on the patch?

The patch hint that this is a bound-check error and that this is related to numbers of alternating signs.

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

Yes

Which older supported branches are affected by this flaw?

all

If not all supported branches, which bug introduced the flaw?

Bug 1295130

Do you have backports for the affected branches?

No

If not, how different, hard to create, and risky will they be?

We had 2 different coding style changes affecting the backport of this patch, but it should be easy to redo this patch on old branches, as the latest big change was Bug 1319242.

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

This patch might cause performance regressions as it prevent code to optimize cases and now split the code. The worse case would appear on code which does something like:

i+=1;
i-=1;
i+=1;
i-=1;
i+=1;
i-=1;
i+=1;
i-=1;
i+=1;
i-=1;
// …

If these appear to be a performance issue which matter, then we should make a follow-up bug to implement the second proposal presented in comment 5, which is to create a bound-check instruction when a SimpleLinearSum is used to create a MIR instruction.

Attachment #9044938 - Flags: sec-approval?
Attachment #9044718 - Attachment mime type: text/markdown → text/plain

Comment on attachment 9044938 [details]
Bug 1528829 - Restrict ExtractLinearSum to monotonous operation in infinite math space.

sec-approval+ for m-c. We'll want patches nominated for branches as well.

Attachment #9044938 - Flags: sec-approval? → sec-approval+

Thanks to Bruno Keith & Niklas Baumstark from the phoenhex team for finding this
issue and reporting it with a proper analysis.

(In reply to Nicolas B. Pierron [:nbp] from comment #12)

If not, how different, hard to create, and risky will they be?

We had 2 different coding style changes affecting the backport of this patch, but it should be easy to redo this patch on old branches, as the latest big change was Bug 1319242.

Apparently the clang-format got applied to all branches, so I saw no issue to backport attachment 9044938 [details] to beta and release.
However, I made attachment 9045629 [details] to backport this change to esr-60.

Priority: -- → P1

https://hg.mozilla.org/mozilla-central/rev/50b4e10ccc47

Go ahead with the Beta & ESR60 approval requests whenever you're comfortable doing so.

Group: javascript-core-security → core-security-release
Status: ASSIGNED → RESOLVED
Closed: 1 year ago
Flags: needinfo?(nicolas.b.pierron)
Flags: in-testsuite?
Resolution: --- → FIXED
Target Milestone: --- → mozilla67

(In reply to Ryan VanderMeulen [:RyanVM] from comment #17)

Go ahead with the Beta & ESR60 approval requests whenever you're comfortable doing so.

So far I cannot spot any regressions on arewefastyet.com, I will ask for approvals.

Flags: needinfo?(nicolas.b.pierron)

Comment on attachment 9044938 [details]
Bug 1528829 - Restrict ExtractLinearSum to monotonous operation in infinite math space.

Beta/Release Uplift Approval Request

Feature/Bug causing the regression

Bug 1295130

User impact if declined

Potential out-of-bound failures.

Is this code covered by automated tests?

Yes

Has the fix been verified in Nightly?

Yes

Needs manual test from QE?

No

If yes, steps to reproduce

List of other uplifts needed

None

Risk to taking this patch

Low

Why is the change risky/not risky? (and alternatives if risky)

The change is not risky, because it is small and applies to all uses of ExtractLinearSum.

It limits the ability of ExtractLinearSum to merge terms which are not monotonously increasing/decreasing constants, which avoid merging an underflow check with an overflow check, when working in the infinite math-space represented on the int32 range.

String changes made/needed

N/A

Attachment #9044938 - Flags: approval-mozilla-beta?

Comment on attachment 9045629 [details]
Bug 1528829 - Restrict ExtractLinearSum to monotonous operation in infinite math space.

ESR Uplift Approval Request

If this is not a sec:{high,crit} bug, please state case for ESR consideration

sec-high.

User impact if declined

Potential out-of-bound failures.

Fix Landed on Version

67

Risk to taking this patch

Low

Why is the change risky/not risky? (and alternatives if risky)

The change is not risky, because it is small and applies to all uses of ExtractLinearSum.

It limits the ability of ExtractLinearSum to merge terms which are not monotonously increasing/decreasing constants, which avoid merging an underflow check with an overflow check, when working in the infinite math-space represented on the int32 range.

String or UUID changes made by this patch

N/A

Attachment #9045629 - Flags: approval-mozilla-esr60?

Comment on attachment 9044938 [details]
Bug 1528829 - Restrict ExtractLinearSum to monotonous operation in infinite math space.

"The change is not risky, because it is small and applies to all uses of ExtractLinearSum." I'm going to just take your word for that :) Sounds like it didn't cause problems on Nightly.

OK for uplift for beta 11.

Attachment #9044938 - Flags: approval-mozilla-beta? → approval-mozilla-beta+
Flags: qe-verify-
Whiteboard: [reporter-external] [client-bounty-form] [verif?][jsbugmon:update,testComment=2,origRev=dd4aa59c6a12] → [reporter-external] [client-bounty-form] [verif?][jsbugmon:update,testComment=2,origRev=dd4aa59c6a12][post-critsmash-triage]
Flags: sec-bounty? → sec-bounty+
Comment 3 is private: false

Comment on attachment 9045629 [details]
Bug 1528829 - Restrict ExtractLinearSum to monotonous operation in infinite math space.

No known fallout on Nightly or Beta. Approving for 60.6esr also.

Attachment #9045629 - Flags: approval-mozilla-esr60? → approval-mozilla-esr60+

(In reply to Nicolas B. Pierron [:nbp] from comment #25)

Created attachment 9048177 [details]
Bug 1528829 - Add test case to check range analysis correctness.

Based on RyanVM feedback, we should wait until next version mid-cycle before landing this test case.

Flags: needinfo?(nicolas.b.pierron)
Whiteboard: [reporter-external] [client-bounty-form] [verif?][jsbugmon:update,testComment=2,origRev=dd4aa59c6a12][post-critsmash-triage] → [reporter-external] [client-bounty-form] [verif?][jsbugmon:update,testComment=2,origRev=dd4aa59c6a12][post-critsmash-triage][adv-main66+][advesr60.6+]
Whiteboard: [reporter-external] [client-bounty-form] [verif?][jsbugmon:update,testComment=2,origRev=dd4aa59c6a12][post-critsmash-triage][adv-main66+][advesr60.6+] → [reporter-external] [client-bounty-form] [verif?][jsbugmon:update,testComment=2,origRev=dd4aa59c6a12][post-critsmash-triage][adv-main66+][adv-esr60.6+]
Alias: CVE-2019-9793
Flags: needinfo?(nicolas.b.pierron)
Flags: in-testsuite?
Flags: in-testsuite+
Group: core-security-release
You need to log in before you can comment on or make changes to this bug.