Christian Holler (:decoder) Reporter
	Description • 6 years ago

The following testcase crashes on mozilla-central revision 7007206a3cd4 (build with --enable-posix-nspr-emulation --enable-valgrind --enable-gczeal --disable-tests --disable-profiling --enable-debug --enable-optimize, run with --fuzzing-safe --ion-offthread-compile=off --ion-check-range-analysis --ion-offthread-compile=off):

function AsmModule() {
    "use asm";      
    function f3(x,y){
        x = x|0;
        y = +y;
        var n = 10;
        a: while( (x|0) < 30 ) x = (x+(2147483647))|0
        do {
             x = (x+1)|0;
             n = (n + 1)|0;
        } while((n|0) < 100)
    }
    function bar(k,d) {
        k = k|0;
        d = +d;
    }
    return {bar:bar,f3:f3}
}
var obj = AsmModule();
print(obj.f3(1,1.5))


Backtrace:

Program terminated with signal SIGTRAP, Trace/breakpoint trap.
#0  0x00001b18d65360a4 in ?? ()
#1  0x0000000000000000 in ?? ()
rax	0xc	12
rbx	0x7fb44092c880	140412154202240
rcx	0x64	100
rdx	0x120	288
rsi	0x7fb43f21dbe0	140412130024416
rdi	0x80000000	2147483648
rbp	0x7fff21e93e18	140733762321944
rsp	0x7fff21e93e18	140733762321944
r8	0x0	0
r9	0x0	0
r10	0x7fff21e93f58	140733762322264
r11	0x1	1
r12	0x7fff21e93e48	140733762321992
r13	0x7fb440918000	140412154118144
r14	0x7fb43f21dbe0	140412130024416
r15	0x0	0
rip	0x1b18d65360a4	29793488953508
=> 0x1b18d65360a4:	cmpl   $0x0,0x30(%r14)
   0x1b18d65360a9:	je     0x1b18d65360b1



S-s because this is likely an asm.js range analysis problem.

	Andrew McCreight [:mccr8]
	Comment 1 • 6 years ago

Benjamin, can you take a look?

	Benjamin Bouvier [:bbouvier] (inactive) Assignee
	Comment 2 • 6 years ago

This summarizes the issue: before the second loop, x = INT32_MAX - 2.

The second loop does this:

        do {
             x = (x+1)|0;
             n = (n+1)|0;
        } while((n|0) < 100)


Now the interesting line is x = (x+1)|0, which is add23 in the PDF output of iongraph. The range for this MIR node is the full int32 range, which is correct. But then it doesn't get a beta node in the block that gets back to the head (block6), and phi18 gets an incorrect range. Either it should get its own beta node, or its information isn't correctly back-propagated to the loop head. It should get the full int32 range too.

	Benjamin Bouvier [:bbouvier] (inactive) Assignee
	Comment 3 • 6 years ago

It seems the phi ends up getting a range because of RangeAnalysis::analyzeLoopPhi(). What's strange is that we end up in the code section that's below the comment that says "The phi may change by N each iteration, and is either nondecreasing or nonincreasing", which is false here, because the phi depends on a truncated add which will overflow.

The phi is first assigned a range here: https://searchfox.org/mozilla-central/source/js/src/jit/RangeAnalysis.cpp#2301 which is the full int32 range, which is correct. Then it's refined with the input nodes, including the beta node before the loop, which has a lower bound of 30.

I think the linear sum optimization shouldn't be done at all since the add in the phi is truncated, and thus isn't either non-increasing or non-decreasing (it can overflow).

	Benjamin Bouvier [:bbouvier] (inactive) Assignee
	Comment 4 • 6 years ago

That's a very naive patch, but I don't pretend to exactly know what this is doing. If this is wrong, feel free to cancel review and please take over.

If there's a truncated add or sub in a phi's argument, we shouldn't even consider linearizing the sum (the add/sub could be overflowing, thus it's unbounded).

	Dan Gohman [:sunfish]
	Comment 5 • 6 years ago

Would it work to just make that call to ExtractLinearSum pass it MathSpace::Infinite as the second argument, rather than using the default? That way it would reject sums that are in MathSpace::Modulo, which seems like what's needed.

	Benjamin Bouvier [:bbouvier] (inactive) Assignee
	Comment 6 • 6 years ago

Yes, it's a much better patch, thanks.

	Dan Gohman [:sunfish]
	Comment 7 • 6 years ago

Comment on attachment 9022849 [details] [diff] [review]
fix.patch

I haven't worked on the bounds-check elimination parts of range analysis before, but this change looks right to me. The code below it is doing analysis that isn't valid in the face of wrapping overflow, and requiring ExtractLinearSum to find non-wrapping results filters out the problematic cases.

	Nicolas B. Pierron [:nbp]
	Comment 8 • 6 years ago

(In reply to Benjamin Bouvier [:bbouvier] from comment #2)
>         do {
>              x = (x+1)|0;
>              n = (n+1)|0;
>         } while((n|0) < 100)
> 
> 
> Now the interesting line is x = (x+1)|0, which is add23 in the PDF output of
> iongraph. The range for this MIR node is the full int32 range, which is
> correct. But then it doesn't get a beta node in the block that gets back to
> the head (block6), and phi18 gets an incorrect range. Either it should get
> its own beta node, or its information isn't correctly back-propagated to the
> loop head. It should get the full int32 range too.

It does not get a beta node because "x" is not one of the term of the condition.

	Nicolas B. Pierron [:nbp]
	Comment 9 • 6 years ago

Comment on attachment 9022849 [details] [diff] [review]
fix.patch

Review of attachment 9022849 [details] [diff] [review]:
-----------------------------------------------------------------

I am convinced that this patch is a correct fix, as it prevent us from doing any symbolic bounds checks which are not considering the truncated aspect of the math used in the computation of "x".

However, I am sad, as this would remove some optimization oportunity on asm.js-like JavaScript.

A follow-up improvement might be to allowed the modulo Math space if and only if we can figure a lower and upper bound for the computed value.

	Benjamin Bouvier [:bbouvier] (inactive) Assignee
	Comment 10 • 6 years ago

Comment on attachment 9022849 [details] [diff] [review]
fix.patch

[Security Approval Request]

How easily could an exploit be constructed based on the patch?: Not very hard, if you trigger the right assumptions; can lead to a bounds check removal.

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 older supported branches are affected by this flaw?: all

If not all supported branches, which bug introduced the flaw?: asm.js in general

Do you have backports for the affected branches?: No

If not, how different, hard to create, and risky will they be?: I suppose the same patch could apply on all branches.

How likely is this patch to cause regressions; how much testing does it need?: Local testing on x86 64 bits showed no issues. Since it's being more conservative than what was allowed before, it might introduce runtime speed regressions at the price of correctness. (nbp has an idea of optimization we could do, if it became an issue)

	Al Billings [:abillings - ex-MoCo]
	Comment 11 • 6 years ago

sec-approval+ for trunk. We should get patched nominated for Beta and ESR60 as well.

	Benjamin Bouvier [:bbouvier] (inactive) Assignee
	Comment 12 • 6 years ago

remote:   https://hg.mozilla.org/integration/mozilla-inbound/rev/d23dffc8c0757eea950109058f371a0e3801d31d

	Benjamin Bouvier [:bbouvier] (inactive) Assignee
	Comment 13 • 6 years ago

Comment on attachment 9022849 [details] [diff] [review]
fix.patch

[Beta/Release Uplift Approval Request]

Feature/Bug causing the regression: None

User impact if declined: see sec-approval comment

Is this code covered by automated tests?: No

Has the fix been verified in Nightly?: Yes

Needs manual test from QE?: Yes

If yes, steps to reproduce: Run test in comment 0 in a Spidermonkey shell built on latest mozilla-inbound.

List of other uplifts needed: None

Risk to taking this patch: Low

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

String changes made/needed:

	Sebastian Hengst [:aryx] (needinfo me if it's about an intermittent or backout)
	Comment 14 • 6 years ago

https://hg.mozilla.org/mozilla-central/rev/d23dffc8c075

	Julien Cristau [:jcristau]
	Comment 15 • 6 years ago

Comment on attachment 9022849 [details] [diff] [review]
fix.patch

asmjs sec fix, approved for 64.0b9

	Ryan VanderMeulen [:RyanVM]
	Comment 16 • 6 years ago
uplift

https://hg.mozilla.org/releases/mozilla-beta/rev/d84c76f0dddd

	Ryan VanderMeulen [:RyanVM]
	Comment 17 • 6 years ago

Comment on attachment 9022849 [details] [diff] [review]
fix.patch

Approved for 60.4.0esr also.

	Ryan VanderMeulen [:RyanVM]
	Comment 18 • 6 years ago
uplift

https://hg.mozilla.org/releases/mozilla-esr60/rev/6398541ec302

	Fuzzing Team
	Comment 19 • 6 years ago

JSBugMon: This bug has been automatically verified fixed.

	Fuzzing Team
	Comment 20 • 5 years ago

JSBugMon: This bug has been automatically verified fixed on Fx64