1822754 - (CVE-2023-29548) Wrong lowering of UDiv MIR in ARM64 Ion compiler

Status: VERIFIED FIXED

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

Description

[JunYoung Park]

Overview

Target: SpiderMonkey ARM64 latest of 2023/3/15 - commit 5860c73273ab6a71408c8b595db695c149155dff

Wrong lowering of UDiv MIR in ARM64 Ion compiler results in wrong optimization result.

Proof of Concept Code

(module
  (type (;0;) (func (param i32) (result i32)))
  (import "mem" "mem" (memory (;0;) 1024))
  (func (;0;) (type 0) (param i32) (result i32)
    local.get 0
    i32.const -1 ;; any value of -2^n will work
    i32.div_u)
  (export "main" (func 0)))

// [('i32.div_u', 'i32', ('i32.const',))]
// const code = new Uint8Array([...]);
const code = new Uint8Array([0,97,115,109,1,0,0,0,1,6,1,96,1,127,1,127,2,13,1,3,109,101,109,3,109,101,109,2,0,128,8,3,2,1,0,7,8,1,4,109,97,105,110,0,0,10,9,1,7,0,32,0,65,127,110,11,11,1,0]);

let memory = new WebAssembly.Memory({
    initial: 1024
})
const module = new WebAssembly.Module(code);
const instance = new WebAssembly.Instance(module, {
    mem: {
        mem: memory
    }
});

// print(instance.exports.main(0, 1, 2))
print(instance.exports.main(-2)); // any value would work

$ builds/arm64_debug/dist/bin/js --wasm-compiler=baseline poc.js
0
$ builds/arm64_debug/dist/bin/js --wasm-compiler=ion poc.js
-2

Root Cause Analysis

When lowering UDiv, shift value is calculated with the absolute value of the divisor. When the divisor is the negation of an integer which is power of two, LDivPowTwoI LIR will be generated with shift=0, resulting in an identity (x -> x) or right shift operation, which is wrong.

// src/jit/arm64/Lowering-arm64.cpp:574
void LIRGeneratorARM64::lowerUDiv(MDiv* div) {
  LAllocation lhs = useRegister(div->lhs());
  if (div->rhs()->isConstant()) {
    int32_t rhs = div->rhs()->toConstant()->toInt32();
    int32_t shift = mozilla::FloorLog2(mozilla::Abs(rhs)); // [*] Bug

    if (rhs != 0 && uint32_t(1) << shift == mozilla::Abs(rhs)) { // [1] rhs=0xffffffff, shift=0, abs=1
      LDivPowTwoI* lir = new (alloc()) LDivPowTwoI(lhs, shift, false); // [2] shift=0, negativeDivisor=false 
      if (div->fallible()) {
        assignSnapshot(lir, div->bailoutKind());
      }
      define(lir, div);
      return;
    }

    (...)

  }

  (...)
}

We are handling the case where rhs is constant. Therefore, rhs is considered as a signed integer, and shift value is calculated with absolute value of rhs. ([*] Bug part) To explain more in detail, the compiler enters the condition [1] when rhs is -2^n, and in [2], LDivPowTwoI LIR will be generated. The LIR will be later handled with an identity or a right shift operation in the code generation. (See src/jit/arm64/CodeGenerator-arm64.cpp:515 for more detail)

If we think of an example where rhs=-1, abs(rhs)=1, so shift=0. shift=0 will be later handled as an identity operation in the code generation.

The expected behavior is to consider rhs as an unsigned value. Then, the code will work as intended.

You can refer to the following result codes below:

• arm64 baseline

0xbe069c8b000  d10043ff  sub     sp, sp, #0x10 (16)
0xbe069c8b004  f90007fe  str     x30, [sp, #8]
0xbe069c8b008  f90003fd  str     x29, [sp]
0xbe069c8b00c  910003fd  mov     x29, sp
0xbe069c8b010  71008d5f  cmp     w10, #0x23 (35)
0xbe069c8b014  540000e0  b.eq    #+0x1c (addr 0xbe069c8b030)
0xbe069c8b018  d4a00000  unimplemented (Exception)
0xbe069c8b01c  d503201f  nop
0xbe069c8b020  d10043ff  sub     sp, sp, #0x10 (16)
0xbe069c8b024  f90007fe  str     x30, [sp, #8]
0xbe069c8b028  f90003fd  str     x29, [sp]
0xbe069c8b02c  910003fd  mov     x29, sp
0xbe069c8b030  910003fc  mov     x28, sp
0xbe069c8b034  d2800a10  mov     x16, #0x50
0xbe069c8b038  f2a00010  movk    x16, #0x0, lsl #16
0xbe069c8b03c  cb3063e8  sub     x8, sp, x16
0xbe069c8b040  f9401ef0  ldr     x16, [x23, #56]
0xbe069c8b044  eb08021f  cmp     x16, x8
0xbe069c8b048  54000043  b.lo    #+0x8 (addr 0xbe069c8b050)
0xbe069c8b04c  d4a00000  unimplemented (Exception)
0xbe069c8b050  d10143ff  sub     sp, sp, #0x50 (80)
0xbe069c8b054  b9004fe0  str     w0, [sp, #76]
0xbe069c8b058  f90023f7  str     x23, [sp, #64]
0xbe069c8b05c  12800000  mov     w0, #0xffffffff
0xbe069c8b060  b9404fe1  ldr     w1, [sp, #76]
0xbe069c8b064  1ac00821  udiv    w1, w1, w0
0xbe069c8b068  2a0103e0  mov     w0, w1
0xbe069c8b06c  14000002  b       #+0x8 (addr 0xbe069c8b074)
0xbe069c8b070  d4200000  brk     #0x0
0xbe069c8b074  910143ff  add     sp, sp, #0x50 (80)
0xbe069c8b078  f94003fd  ldr     x29, [sp]
0xbe069c8b07c  f94007fe  ldr     x30, [sp, #8]
0xbe069c8b080  910043ff  add     sp, sp, #0x10 (16)
0xbe069c8b084  910003fc  mov     x28, sp
0xbe069c8b088  d65f03c0  ret

• arm64 ion

0x2ed13ecb6000  d10043ff  sub     sp, sp, #0x10 (16)
0x2ed13ecb6004  f90007fe  str     x30, [sp, #8]
0x2ed13ecb6008  f90003fd  str     x29, [sp]
0x2ed13ecb600c  910003fd  mov     x29, sp
0x2ed13ecb6010  71008d5f  cmp     w10, #0x23 (35)
0x2ed13ecb6014  540000e0  b.eq    #+0x1c (addr 0x2ed13ecb6030)
0x2ed13ecb6018  d4a00000  unimplemented (Exception)
0x2ed13ecb601c  d503201f  nop
0x2ed13ecb6020  d10043ff  sub     sp, sp, #0x10 (16)
0x2ed13ecb6024  f90007fe  str     x30, [sp, #8]
0x2ed13ecb6028  f90003fd  str     x29, [sp]
0x2ed13ecb602c  910003fd  mov     x29, sp
0x2ed13ecb6030  910003fc  mov     x28, sp
0x2ed13ecb6034  2a0003e2  mov     w2, w0
0x2ed13ecb6038  2a0203e1  mov     w1, w2
0x2ed13ecb603c  2a0103e0  mov     w0, w1 ;; [!] Bug here: function returns as arg1
0x2ed13ecb6040  f94003fd  ldr     x29, [sp]
0x2ed13ecb6044  f94007fe  ldr     x30, [sp, #8]
0x2ed13ecb6048  910043ff  add     sp, sp, #0x10 (16)
0x2ed13ecb604c  910003fc  mov     x28, sp
0x2ed13ecb6050  d65f03c0  ret

Suggested Patch

rhs must be considered as an unsigned value when lowering UDiv MIR to LIR. The following two lines of code would be fixed.

// src/jit/arm64/Lowering-arm64.cpp:574
void LIRGeneratorARM64::lowerUDiv(MDiv* div) {
  LAllocation lhs = useRegister(div->lhs());
  if (div->rhs()->isConstant()) {
-    int32_t rhs = div->rhs()->toConstant()->toInt32();
-    int32_t shift = mozilla::FloorLog2(mozilla::Abs(rhs));
+    uint32_t rhs = div->rhs()->toConstant()->toUint32();
+    int32_t shift = mozilla::FloorLog2(rhs);

    if (rhs != 0 && uint32_t(1) << shift == mozilla::Abs(rhs)) {
      LDivPowTwoI* lir = new (alloc()) LDivPowTwoI(lhs, shift, false);
      if (div->fallible()) {
        assignSnapshot(lir, div->bailoutKind());
      }
      define(lir, div);
      return;
    }

    (...)

  }

  (...)
}

Comment 1

[Jan de Mooij [:jandem]]

Nicolas, maybe you can take a look at this one?

Comment 2

[Nicolas B. Pierron [:nbp]]

Ryan, is this legal to have -1 constant flow as argument of i32.div_u?

Comment 3

[Nicolas B. Pierron [:nbp]]

Attachment: Bug 1822754 - Use a different strategy to convert integers to unsigned.

Comment 4

[Nicolas B. Pierron [:nbp]]

Attachment: Bug 1822754 - Add test case for udiv with -1.

Comment 5

[Nicolas B. Pierron [:nbp]]

the lowerUDiv function is called if the unsigned_ flag is set. This flag can be set by Range Analysis, in which case the operands are guaranteed to be unsigned values. The other case where this flag is set is when WebAssembly set unsigned_ flag, but in such case the Range Analysis step is supposed to be disabled.

Thus, despite the wrong computation, there does not seems to be any direct security risk involved in this change. There might have some in the application written in WebAssembly.

Comment 6

[BugBot [:suhaib / :marco/ :calixte]]

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

Comment 7

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/4100f6375c7c

Comment 8

[Ryan Hunt [:rhunt] (on leave until early May)]

Yes, this wasm code is legal. Wasm integer types don't have signedness and are raw bits. i32.const -1 would use the twos complement representation.

Comment 9

[BugBot [:suhaib / :marco/ :calixte]]

The patch landed in nightly and beta is affected.
:nbp, is this bug important enough to require an uplift?

• If yes, please nominate the patch for beta approval.
• If no, please set status-firefox112 to wontfix.

For more information, please visit auto_nag documentation.

Comment 10

[Nicolas B. Pierron [:nbp]]

Attachment: web-test-case.html

This is a test case to be used to test release versions of android while waiting for the test case to be landed.

Comment 11

[Nicolas B. Pierron [:nbp]]

Comment on attachment 9324683 [details]
Bug 1822754 - Use a different strategy to convert integers to unsigned.

Beta/Release Uplift Approval Request

• User impact if declined: Wrong result for unsigned division, potentially causing issue in Web Assembly applications.
• Is this code covered by automated tests?: No
• Has the fix been verified in Nightly?: No
• Needs manual test from QE?: Yes
• If yes, steps to reproduce: I have not tested on android yet, however the test case pass on simulator builds of SpiderMonkey.

The tests are in a separated patch coming after to avoid pointing at the issue, in the mean time I attached a test case which can be used verify if the fix is correctly applied.

Otherwise landing the test case and running the JS test suite on Android on x64 should clarify if there is anything wrong.

• List of other uplifts needed: None
• Risk to taking this patch: Low
• Why is the change risky/not risky? (and alternatives if risky): The code is minimal and now matches what we already have for the x86/x64 backend.
• String changes made/needed: N/A
• Is Android affected?: Yes

ESR Uplift Approval Request

• If this is not a sec:{high,crit} bug, please state case for ESR consideration: Wrong results often lead to exploitable issue. While this does not seems to be the case here, I prefer to be on the safe side.
• User impact if declined: Wrong result for unsigned division, potentially causing issue in Web Assembly applications.
• Fix Landed on Version: 113
• Risk to taking this patch: Low
• Why is the change risky/not risky? (and alternatives if risky): The code is minimal and now matches what we already have for the x86/x64 backend.

Comment 12

[Dianna Smith [:diannaS]]

Comment on attachment 9324683 [details]
Bug 1822754 - Use a different strategy to convert integers to unsigned.

Approved for 112.0b9

Comment 13

[Dianna Smith [:diannaS]]

https://hg.mozilla.org/releases/mozilla-beta/rev/225745d42a65

Comment 14

[Ryan VanderMeulen [:RyanVM]]

Comment on attachment 9324683 [details]
Bug 1822754 - Use a different strategy to convert integers to unsigned.

Approved for 102.10esr.

Comment 15

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/releases/mozilla-esr102/rev/5d3420871c84

Comment 16

[Delia Pop]

Attachment: Verification.png

Verified as fixed on the latest Nightly 113.0a1 from 04/03 and Beta 112.0b9. Using the test case provided above, the following results were obtained:
got 0 expect 0
got 1 expect 1

In the "won't fix" version, on RC 111.1.1 the results were:
got 5 expect 0
got 2147483647 expect 1

Devices used:

• Google Pixel 6 (Android 13)
• Xiaomi 12 Pro (Android 13)
• OPPO A15s (Android 10)

Comment 17

[Tom Ritter [:tjr] (OOTO until 4/30 at least)]

Attachment: advisory.txt

Comment 18

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

Add test case for udiv with -1. r=iain
https://hg.mozilla.org/integration/autoland/rev/6cf8025f98f0dd19749b024b7a7adcc404648b6b
https://hg.mozilla.org/mozilla-central/rev/6cf8025f98f0