1528829 - (CVE-2019-9793) Arbitrary range mis-inference due to loop phi range analysis disregarding overflows/truncation

Status: RESOLVED FIXED

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

Description

[Niklas Baumstark]

Attachment: 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.

Comment 1

[Niklas Baumstark]

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

Comment 2

[Gary Kwong [:gkw] [:nth10sd] (NOT official MoCo now)]

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

Comment 3

[Gary Kwong [:gkw] [:nth10sd] (NOT official MoCo now)]

(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

Comment 5

[Nicolas B. Pierron [:nbp]]

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.

Comment 6

[Nicolas B. Pierron [:nbp]]

Attachment: Bug 1528829 - Restrict ExtractLinearSum to monotonous operation in infinite math space.

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

Comment 7

[Nicolas B. Pierron [:nbp]]

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.

Comment 8

[Dan Gohman [:sunfish]]

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

Comment 9

[Nicolas B. Pierron [:nbp]]

(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.

Comment 10

[Gary Kwong [:gkw] [:nth10sd] (NOT official MoCo now)]

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.

Comment 11

[Nicolas B. Pierron [:nbp]]

(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 12

[Nicolas B. Pierron [:nbp]]

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.

Comment 13

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

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.

Comment 14

[Nicolas B. Pierron [:nbp]]

Attachment: Bug 1528829 - Restrict ExtractLinearSum to monotonous operation in infinite math space.

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

Comment 15

[Nicolas B. Pierron [:nbp]]

(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.

Comment 16

[Nicolas B. Pierron [:nbp]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/50b4e10ccc478b5cca15b828b24203de6396d3f2

Comment 17

[Ryan VanderMeulen [:RyanVM]]

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

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

Comment 18

[Nicolas B. Pierron [:nbp]]

(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.

Comment 19

[Nicolas B. Pierron [:nbp]]

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

Comment 20

[Nicolas B. Pierron [:nbp]]

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

Comment 21

[Liz Henry (:lizzard) (relman/hg->git project)]

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.

Comment 22

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/releases/mozilla-beta/rev/197546cf8331

Comment 23

[Ryan VanderMeulen [:RyanVM]]

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.

Comment 24

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

https://hg.mozilla.org/releases/mozilla-esr60/rev/8944cc42a3eb

Comment 25

[Nicolas B. Pierron [:nbp]]

Attachment: Bug 1528829 - Add test case to check range analysis correctness.

Comment 26

[Nicolas B. Pierron [:nbp]]

(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.

Comment 27

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

https://hg.mozilla.org/integration/autoland/rev/b2bc140a4d766e6b86d85b77e2bc12733402dc27
https://hg.mozilla.org/mozilla-central/rev/b2bc140a4d76