848747 - IonMonkey: Assertion failure: t >= 0 || -(t + 1) != T((1ULL << (8 * sizeof(T) - 1)) - 1) (You cant negate the smallest possible negative integer!), at ./dist/include/mozilla/MathAlgorithms.h:94

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Christian Holler (:decoder)]

Attachment: Testcase for shell

The attached testcase asserts on mozilla-central revision ee4879719f78 (no options required).

Comment 1

[Christian Holler (:decoder)]

Meant to make this s-s because it could cause some integer operation going bad and the trace shows "computeInterval" on the stack, suggesting that this could possibly lead to some form of out-of-bounds:

Program received signal SIGSEGV, Segmentation fault.
0x0000000000b57130 in mozilla::Abs<int> (t=-2147483648) at ./dist/include/mozilla/MathAlgorithms.h:92
92        MOZ_ASSERT(t >= 0 ||
(gdb) bt
#0  0x0000000000b57130 in mozilla::Abs<int> (t=-2147483648) at ./dist/include/mozilla/MathAlgorithms.h:92
#1  0x0000000000b90dae in js::mjit::LoopState::computeInterval (this=0x14b8510, cv=..., pmin=0x7fffffff0298, pmax=0x7fffffff029c) at /srv/repos/mozilla-central/js/src/methodjit/LoopState.cpp:2062
#2  0x0000000000b889db in js::mjit::LoopState::cannotIntegerOverflow (this=0x14b8510, pushed=...) at /srv/repos/mozilla-central/js/src/methodjit/LoopState.cpp:916
#3  0x0000000000b4da2f in js::mjit::Compiler::jsop_binary (this=0x7fffffff1660, op=JSOP_MUL, stub=0xe41acb <js::mjit::stubs::Mul(js::VMFrame&)>, type=JSVAL_TYPE_INT32, typeSet=0x14aa718)
    at /srv/repos/mozilla-central/js/src/methodjit/FastArithmetic.cpp:208
#4  0x0000000000ae30c7 in js::mjit::Compiler::generateMethod (this=0x7fffffff1660) at /srv/repos/mozilla-central/js/src/methodjit/Compiler.cpp:2590
#5  0x0000000000aced1a in js::mjit::Compiler::performCompilation (this=0x7fffffff1660) at /srv/repos/mozilla-central/js/src/methodjit/Compiler.cpp:569
#6  0x0000000000accab6 in js::mjit::Compiler::compile (this=0x7fffffff1660) at /srv/repos/mozilla-central/js/src/methodjit/Compiler.cpp:145
#7  0x0000000000ad8e1a in js::mjit::CanMethodJIT (cx=0x14024b0, script=0x7ffff6032380, pc=0x140984c "mV", construct=false, request=js::mjit::CompileRequest_Interpreter, frame=0x7ffff62f44f8)
    at /srv/repos/mozilla-central/js/src/methodjit/Compiler.cpp:1098
#8  0x000000000063e802 in js::Interpret (cx=0x14024b0, entryFrame=0x7ffff62f4038, interpMode=js::JSINTERP_NORMAL) at /srv/repos/mozilla-central/js/src/jsinterp.cpp:1384
#9  0x0000000000632aef in js::RunScript (cx=0x14024b0, fp=0x7ffff62f4038) at /srv/repos/mozilla-central/js/src/jsinterp.cpp:340
#10 0x00000000006352b8 in js::ExecuteKernel (cx=0x14024b0, script=0x7ffff6032128, scopeChainArg=(JSObject &) @0x7ffff602e060 [object global] delegate, thisv=..., type=js::EXECUTE_GLOBAL, evalInFrame=..., result=0x0)
    at /srv/repos/mozilla-central/js/src/jsinterp.cpp:530
#11 0x00000000006355dd in js::Execute (cx=0x14024b0, script=0x7ffff6032128, scopeChainArg=(JSObject &) @0x7ffff602e060 [object global] delegate, rval=0x0) at /srv/repos/mozilla-central/js/src/jsinterp.cpp:570
#12 0x000000000048d963 in JS_ExecuteScript (cx=0x14024b0, objArg=(JSObject *) 0x7ffff602e060 [object global] delegate, scriptArg=0x7ffff6032128, rval=0x0) at /srv/repos/mozilla-central/js/src/jsapi.cpp:5516
#13 0x000000000040c80f in Process (cx=0x14024b0, obj_=(JSObject *) 0x7ffff602e060 [object global] delegate, filename=0x7fffffffe1a0 "min.js", forceTTY=false) at /srv/repos/mozilla-central/js/src/shell/js.cpp:467
#14 0x0000000000427b72 in ProcessArgs (cx=0x14024b0, obj_=(JSObject *) 0x7ffff602e060 [object global] delegate, op=0x7fffffffdcd0) at /srv/repos/mozilla-central/js/src/shell/js.cpp:5025
#15 0x0000000000427d66 in Shell (cx=0x14024b0, op=0x7fffffffdcd0, envp=0x7fffffffdee0) at /srv/repos/mozilla-central/js/src/shell/js.cpp:5062
#16 0x00000000004287a9 in main (argc=2, argv=0x7fffffffdec8, envp=0x7fffffffdee0) at /srv/repos/mozilla-central/js/src/shell/js.cpp:5284

Comment 2

[Jeff Walden [:Waldo]]

I've got this, already have a patch even, was going to fix in bug 847480.  I can do a backportable fix here.

The consequence is that an integral value is assumed to be within a smaller range of values than it should be.  The failure mode I was able to demonstrate was of an integer overflow not being tested for, with a value then computed as a very-negative int32_t rather than properly (for JS) overflowing into double-space.  This is just wrong math.  But judging by comments in the code, such a number may flow into a dense array element access, which (at least by nature of the error I could see) could access memory up to INT32_MAX bytes past the end of the array's data, pretty close to arbitrary.  Without more knowledge of how dense array accesses are allowed in JM-optimized constrained loops I can't be completely sure this is the case.  But it at least presents a theoretical concern beyond just wrong integers being computed.

Comment 3

[Jeff Walden [:Waldo]]

Attachment: Bail if the input intervals include INT32_MIN

abs(INT32_MIN) has undefined behavior, because on twos-complement architectures you can't fit 2**31 in an int32_t.

Inductively we only need to check the lhs/rhs min values, because if only a max were INT32_MIN we'd already have a bug.  I am open to being requested to test both min/max for belt-and-suspenders purposes.  :-)

Comment 4

[Jeff Walden [:Waldo]]

Attachment: Test demonstrating this bug can be used to make code semantically wrong

Comment 5

[Jeff Walden [:Waldo]]

More generally than this particular case, it's always an error to pass the minimum integer value to mozilla::Abs -- as it was before with std::abs or ::abs, but those methods didn't complain or assert if you tried it.  (Bug 835542 would be pinpointed as the regressor here -- please don't mark that to give anyone ideas -- but it's a lie, because the previous code behaves exactly the way mozilla::Abs does now, when assertions are compiled out.)

The remaining cases in SpiderMonkey where this method's used are all either totally harmless -- the incoming value is constrained to never be that -- or getting back INT32_MIN (a negative value) from Abs just happens to not cause errors.  The dodgiest-looking one is with use of JSOP_MOD in a JM-compiled loop.  But if you look carefully at it, you'll see that when signed-integer overflow works the way you'd naively expect, the correct semantics happen.  So I think this is the only issue in SpiderMonkey of this sort that needs fixing.  (Ion has its own range analysis code, but that code does the analysis by using Abs<int64_t> on int32_t, which can never hit an undefined case.)

Bug 847480 will replace mozilla::Abs with a version that can handle INT32_MIN and friends, which should eliminate misuse-of-abs bugs as a case entirely (assuming the resulting unsigned value is used correctly, that is).

Comment 6

[Jeff Walden [:Waldo]]

This affects everything, nobody's touched this code back at least as far as esr17.

Comment 7

[Nicolas B. Pierron [:nbp]]

Comment on attachment 722403 [details] [diff] [review]
Bail if the input intervals include INT32_MIN

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

This patch add a condition which checks if any of the operands might not safely flow into the Abs function.
The return false will just cause the integer overflow analysis to fail in JM in this rare specific case.

Comment 8

[Nicolas B. Pierron [:nbp]]

Comment on attachment 722405 [details] [diff] [review]
Test demonstrating this bug can be used to make code semantically wrong

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

*** Do not land until all maintained branches are fixed

::: js/src/jit-test/tests/jaeger/loops/integer-4.js
@@ +1,1 @@
> +function foo(x) {

x argument seems to be unused in this test case, does it matter?

@@ +13,5 @@
> +  // on multiplications if the enclosing loop is a "constrainedLoop" (the name
> +  // of the relevant field).  Loops become unconstrained when unhandled ops are
> +  // found in the loop.  Increment operators generate a DUP op, which is not
> +  // presently a handled op, causing the loop to become unconstrained.
> +  for (var i = 0x7ffffff0; i < 0x7fffffff; i = i + 1) {

Does the test case still assert if the 2 constants are replaced by 0 and 0xf instead of 0x7ffffffx ?

@@ +14,5 @@
> +  // of the relevant field).  Loops become unconstrained when unhandled ops are
> +  // found in the loop.  Increment operators generate a DUP op, which is not
> +  // presently a handled op, causing the loop to become unconstrained.
> +  for (var i = 0x7ffffff0; i < 0x7fffffff; i = i + 1) {
> +    var y = (0x7fffffff + ((i & 1) * -2147483648)) + 5;

(i & 1) possible values are 0 and 1, which when multiplied by INT32_MIN are still int32 values.  Which the previous patch considered as being invalid because the input of Abs.
Would it be possible to make the same failure happen with a left-hand side possibly being -1 instead of 1, in which case this wrong value error would be more critical and easier to noticed?

@@ +18,5 @@
> +    var y = (0x7fffffff + ((i & 1) * -2147483648)) + 5;
> +  }
> +  return y;
> +}
> +assertEq(foo(0x7fffffff), 0x7fffffff + 5);

Is the +5 needed for the test case ?

Comment 9

[Jeff Walden [:Waldo]]

Attachment: Better test

(In reply to Nicolas B. Pierron [:nbp] from comment #8)
> x argument seems to be unused in this test case, does it matter?

Detritus, removed.

> Does the test case still assert if the 2 constants are replaced by 0 and 0xf
> instead of 0x7ffffffx ?

More detritus.  (This is why tests should get reviewed at least somewhat, so this confusion doesn't persist.  :-) )

> (i & 1) possible values are 0 and 1, which when multiplied by INT32_MIN are
> still int32 values.  Which the previous patch considered as being invalid
> because the input of Abs.
> Would it be possible to make the same failure happen with a left-hand side
> possibly being -1 instead of 1, in which case this wrong value error would
> be more critical and easier to noticed?

Using -1 results in an out-of-range value immediately, rather than requiring biasing by -INT32_MIN to get out of int32_t range.  The consequences of failure, and the ease of noticing it, are about the same between -1 and 1, tho.

But good call on adding such a test -- done here.  Also a bunch more comments to make it more understandable.

> > +assertEq(foo(0x7fffffff), 0x7fffffff + 5);
> 
> Is the +5 needed for the test case ?

It's only necessary it be a positive value, as test comments now clarify.

Comment 10

[Jeff Walden [:Waldo]]

(In reply to Nicolas B. Pierron [:nbp] from comment #7)
> This patch add a condition which checks if any of the operands might not
> safely flow into the Abs function.
> The return false will just cause the integer overflow analysis to fail in JM
> in this rare specific case.

Yep, exactly.  The consequence is that such multiplications will be overflow-checked where they weren't before, and any overflows that might happen will trigger double math and everything will be hunky-dory.

Comment 11

[Jeff Walden [:Waldo]]

Comment on attachment 722403 [details] [diff] [review]
Bail if the input intervals include INT32_MIN

[Security approval request comment]
How easily could an exploit be constructed based on the patch?
The underlying issue is fairly obvious (see infra).  Finagling JM into generating wrong code isn't easy if you don't know JM loop analysis code, but it probably wouldn't take more than a few hours for a compiler-knowledgeable person.  That said, the only wrong code I can demonstrate produces incorrect values but doesn't do anything dangerous.


Do comments in the patch, the check-in comment, or tests included in the patch paint a bulls-eye on the security problem?
No.  However, seeing tests of INT32_MIN just before obvious absolute-value computations suggests the underlying issue pretty clearly.


Which older supported branches are affected by this flaw?  If not all supported branches, which bug introduced the flaw?
Everything.  Blame suggests this dates to the initial landing in bug 652520.


Do you have backports for the affected branches? If not, how different, hard to create, and risky will they be?
The relevant code hasn't changed meaningfully since before esr17, so backports are trivial to generate.


How likely is this patch to cause regressions; how much testing does it need?
Unlikely to regress stuff, doesn't need much testing.  The edge case is clear and obviously addressed.  We'll deoptimize to already-used code paths, so there's no new risk.

Comment 12

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

Comment on attachment 722403 [details] [diff] [review]
Bail if the input intervals include INT32_MIN

sec-approval+ for branch but the release management team is unlikely to take it for branches without a security rating (especially since your comments make this seem like a non-serious issue).

Comment 13

[Brian Hackett [Laid off!]]

computeInterval is only used for determining whether to remove integer overflow checks on a given computation.  I think that any breakage within it will only result in the script behaving incorrectly, not any s-s issue.

Comment 14

[Jeff Walden [:Waldo]]

Okay -- sounds like this isn't sensitive, then.  Will land soon, maybe today if the tree reopens.

Comment 15

[Jeff Walden [:Waldo]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/1b6a570e1345 (patch and test both)

Comment 16

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

jsfunfuzz found this too.

Comment 17

[Ed Morley [:emorley]]

https://hg.mozilla.org/mozilla-central/rev/1b6a570e1345