1763012 - Differential testing: miscompute related to div bails

Status: RESOLVED FIXED

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

Description

[lukas.bernhard]

During differential fuzzing, I encountered a miscomputation. The attached sample computes different values, depending on whether ion is enabled or not. Reproduces on git commit: 73a6abf1aaedbf7613fa90a7f459a8c0dfe5f0ce

Precautionary flagging as s-s because the code optimization fails to insert a necessary guard.

sample.js:

function main() {

  let v35;
  let counter = 0;
  let counter2 = 0;

  function f() {
      let v28 = 0;
      do {
          let v29 = v28++;
          v29 /= v29; 
          const v30 = --v29;
          let v31 = 0; 
          while (v31 < 6) {
              const v33 = ++v31;
              switch (v30) {
              case v30: // generates an MCompare (LICM'ed)
                  const v34 = v33 >= 8;
                  v35 = v34 ? 10 : 100;
                  counter += 1;
                  break;
              default:
                  // DCE'd in ion
                  counter2 += 1;
                  break;
              }
          }
      } while (v28 < 8);
  }
  
  f();
  f();
  
  print(counter);  // 90 with ion, 84 without
  print(counter2); // 6  with ion, 12 without
}

main();

obj-x86_64-pc-linux-gnu/dist/bin/js  --fast-warmup --no-threads --cpu-count=1 --ion-offthread-compile=off --fuzzing-safe --ion-range-analysis=on --ion-gvn=on sample.js

prints 90, 6

obj-x86_64-pc-linux-gnu/dist/bin/js  --fast-warmup --no-threads --cpu-count=1 --ion-offthread-compile=off --fuzzing-safe --differential-testing --no-ion sample.js

prints 84,12

Bisecting the issue identifies commit 26b5e252bc45b53394637f438eddd1300229912c related to bug 1637946.
On this old version of spidermonkey the required commandline for reproducing is:

obj-x86_64-pc-linux-gnu/dist/bin/js  --no-threads --cpu-count=1 --ion-offthread-compile=off --fuzzing-safe --ion-range-analysis=on --ion-gvn=on --warp --blinterp-warmup-threshold=4 --baseline-warmup-threshold=10 --ion-warmup-threshold=30 sample.js

My understanding of whats happening:
When OSRing, v29 is an MIRType::Int32. The switch generates an MCompare, comparing v30 with itself. This compare gets hoisted out of the inner loop and evaluates to true (because comparing an int32 with itself is always true). Hence the default block gets DCE'd and instead we always execute the "case v30".
v30 now has no more live users and doesn't need to be computed at all. Therefore v29 has no more live users. The division (v29/=29) should still bail because the correctness of the switch code depends on this. However, neither Guard nor GuardRangeBailout are set and somehow (???) the div vanishes during codegen.

Comment 1

[Nicolas B. Pierron [:nbp]]

Jan, can you look at this issue, as this seems to be related to bug 1637946.

Comment 2

[Steven DeTar [:sdetar]]

Jan told me Iain was going to look into this bug so I am changing the NI to Iain.

Comment 3

[Iain Ireland [:iain]]

This is kind of a mess.

Bug 1637946 isn't at fault here; it just let us optimize enough to expose an existing issue.

Simplifying, we have:

1 phi ... (Int32)
2 div phi1:Int32 phi1:Int32 (Int32)
3 toDouble div2:Int32 (Double)
4 compare toDouble3:Double toDouble3:Double (Bool)
5 test compare4:Bool block1 block2

Range analysis concludes that the range of the div, if it does not bail out, is [INT_MIN, INT_MAX] (aka it does not include NaN). Therefore, the range of the toDouble also does not include NaN, which lets us set operandsAreNeverNan_ on the MCompare. In turn, that lets us fold away the MCompare.

But once we've folded that away, the div has no uses, so we decide that it's dead code.

We don't really have a great way to express that we need the bailouts for an instruction, but not its actual result. Marking it as isGuard or isGuardRangeBailouts is probably the best existing option. I'm not sure where the best place to set the flag would be; unfortunately the isDouble serves as a level of indirection between the producer (div) and consumer (compare).

nbp, any thoughts?

(At first look I think this probably isn't exploitable: we get the wrong result, but the entire compilation agrees on what that result is, so I don't see a way to turn this into eg an out-of-bounds read. Not 100% confident, though.)

Comment 4

[Nicolas B. Pierron [:nbp]]

Hypothetical reasoning, If the division instruction was not a single instruction, but split into bailing instructions which are checking whether we are in a corner case scenario and the executing code for the division once we eliminated all the others. Then it would be safe to elide the division computation, but not the bailing branch.

My understanding would be that as soon as MDiv range is computed, we should use the MDiv::fallible() function to set the GuardRangeBailout flag. This way, we can remove unused infallible MDiv instructions, while keeping these instructions around. Unfortunately, this is an approximation, as most of the time, NaN might not matter in the computation, but we would still be forced to keep it around.

The ultimate solution would be along the lines of keeping 2 Ranges, one with bailouts as we do today, and one without bailouts. If a removal decision taken from the one with bailout would be different than the one taken without bailout, then we know that one of the input is fallible and that it should be marked as a GuardRangeBailout.

In terms of being exploitable, what might happen is that a branch, which is not supposed to be taken, is taken with a right-hand-side value of the removed MDiv instruction being 0. Range Analysis only does forward propagation of range information, and does not create any guards filtering out values of inputs. Thus the Range of MDiv inputs remain untouched, and propagated as before in all branches, even the one which is not supposed to be taken. Thus, while incorrect, this should not yield any out-of-bound which are not already guarded against.

Comment 5

[Daniel Veditz [:dveditz]]

Nicolas: are you confident enough to unhide this as "not a security bug", or should we keep it hidden and call it sec-audit? If something worse comes to mind we could then switch that to an appropriate vulnerability rating.

Comment 6

[Nicolas B. Pierron [:nbp]]

(In reply to Daniel Veditz [:dveditz] from comment #5)

Nicolas: are you confident enough to unhide this as "not a security bug", or should we keep it hidden and call it sec-audit? If something worse comes to mind we could then switch that to an appropriate vulnerability rating.

I am confident that this issue is not a problem, but I suggest we wait before opening this bug, as the solution described in comment 4 applies to more instructions than MDiv.

While the conclusion is most likely identical, it is probably wiser to keep this issue as sec-audit.

Comment 7

[lukas.bernhard]

Differential fuzzing found another instance of the issue, this time using MMod instead of MDiv

function main() {
    for (v7 of "aaaaaa") {
        for (let v13 = 0; v13 < 100; v13++) { } 
    }   

    const v17 = [0,0,0];
    let v18 = 0;
    function v20() {
        for (let v48 = 0; v48 < 100; v48++) {
            const v49 = 0 % v48;
            [..."aaaaaaaaa",...v17];
            const v62 = v49 === v49;
            if (v62) {
                v18 += 1;
            }   
        }   
    }
    v20();
    v20();
    print(v18); // 198 w/o ion, 199 with ion
}
main();

Comment 8

[Iain Ireland [:iain]]

Attachment: Bug 1763012: Mark fallible div/mod as guards r=jandem,nbp

This is a fairly conservative fix, but I didn't see any slowdown on Octane or Speedometer.

Comment 9

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

Landed: https://hg.mozilla.org/integration/autoland/rev/8dcec19a555a83fbe12e3b37a22f870914654d8c

Backed out for causing assertions and test failures in Recover.cpp / dce-with-rinstructions.js:
https://hg.mozilla.org/integration/autoland/rev/adcf94c5d955a2a2d3489478ce088bbef3e6eb16

Push with failures: https://treeherder.mozilla.org/jobs?repo=autoland&group_state=expanded&resultStatus=testfailed%2Cbusted%2Cexception%2Cretry&revision=8dcec19a555a83fbe12e3b37a22f870914654d8c&selectedTaskRun=Ikf9cnRTTSCgh9JXC3fk9A.0
Failure log: https://treeherder.mozilla.org/logviewer?job_id=376854567&repo=autoland

Comment 10

[Nicolas B. Pierron [:nbp]]

(In reply to Sebastian Hengst [:aryx] (needinfo me if it's about an intermittent or backout) from comment #9)

Backed out for causing assertions and test failures in Recover.cpp / dce-with-rinstructions.js:

I guess the options, are to either refined the Range info by using beta nodes on i argument, to explicitly filter out unexpected ranges. Such as:

i = i | 0;
if (i < 1) return i;
var x = 1 / i;

Comment 11

[Iain Ireland [:iain]]

Good call, that fixes the testcase.

Comment 12

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

Mark fallible div/mod as guards r=jandem,nbp
https://hg.mozilla.org/integration/autoland/rev/f0e5faac065b2adc2d28e09dec181993d2aaee00
https://hg.mozilla.org/mozilla-central/rev/f0e5faac065b

Comment 13

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

Since the status are different for nightly and release, what's the status for beta?
For more information, please visit auto_nag documentation.

Comment 14

[Iain Ireland [:iain]]

This can ride the trains.