Closed Bug 960145 Opened 6 years ago Closed 6 years ago

range analysis for phi nodes ignores OSR values

Categories

(Core :: JavaScript Engine: JIT, defect)

defect
Not set

Tracking

()

RESOLVED FIXED
mozilla30
Tracking Status
firefox27 --- wontfix
firefox28 + fixed
firefox29 + fixed
firefox30 + fixed
firefox-esr24 28+ fixed
b2g18 --- unaffected
b2g-v1.1hd --- unaffected
b2g-v1.2 ? fixed
b2g-v1.3 ? fixed
b2g-v1.3T --- fixed
b2g-v1.4 --- fixed

People

(Reporter: sunfish, Assigned: sunfish)

References

Details

(Keywords: sec-critical, Whiteboard: [qa-][adv-main28+][adv-esr24.4+])

Attachments

(3 files, 1 obsolete file)

Range analysis for phi nodes ignores OSR value operands (see MPhi::computeRange). In the testcase in bug 960071, the loop phi has a zero constant and an OSR value. Range analysis ignores the OSR value and returns [0,0]. At runtime, the OSR edge is executed, the OSR value is 1, the phi node has value 1, and the range check fails.

Ignoring OSR values seems wrong in view of this testcase. It's been this way since af9e58e86102 (bug 765119).

This issue was hidden in part by a bug in --ion-check-range-analysis which caused it to neglect to check ranges on phi nodes. I've filed bug 960143 for this.
How bad of a problem is this, in terms of security?
At this time, there's no known exploitable testcase. However, there is a theoretical possibility that one could be constructed.
Keywords: sec-audit
Attached patch osrlike-values.patch (obsolete) — Splinter Review
Here is a patch which fixes the bug conservatively, by deleting the isOSRLikeValue code. It fixes all known instances of the bug, including the testsuite failures noted in bug 960143 and the testcase in bug 960071.

The question with this patch is what impact it will have on performance.
Comment on attachment 8360563 [details] [diff] [review]
osrlike-values.patch

Looking at a variety of tests, this optimization doesn't appear to come up very often, so disabling it seems best.
Attachment #8360563 - Flags: review?(mrosenberg)
Comment on attachment 8360563 [details] [diff] [review]
osrlike-values.patch

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

The patch looks legit, I'd just like a bit of confirmation about what is going on before you land it.  The original ignore-osr-values was correct under the assumption that the OSR value can't take on a value that wouldn't be computed in the loop.  I can only assume that it doesn't actually look like a loop in MIR because of the return, but the try/catch block magically resurrects a value?

Also, I am curious if it is possible to ever observe this value.  For example, in the testcase for bug 960071, if you insert a use of x inside the loop, does range analysis say that it is always 0, or does it say it may be larger than zero?

The reason I did this is because when we OSR, we have *no* range information, so any value that can be derived from an OSR block will almost certainly not have any bounds, upper or lower.
(In reply to Marty Rosenberg [:mjrosenb] from comment #5)
> Comment on attachment 8360563 [details] [diff] [review]
> osrlike-values.patch
> 
> Review of attachment 8360563 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> The patch looks legit, I'd just like a bit of confirmation about what is
> going on before you land it.  The original ignore-osr-values was correct
> under the assumption that the OSR value can't take on a value that wouldn't
> be computed in the loop.  I can only assume that it doesn't actually look
> like a loop in MIR because of the return, but the try/catch block magically
> resurrects a value?

Yes, that does appear to be what's happening. And since the OSR entry is representing a control edge which no longer exists, I don't see a way for MPhi::computeRange to detect when this is happening.

> Also, I am curious if it is possible to ever observe this value.  For
> example, in the testcase for bug 960071, if you insert a use of x inside the
> loop, does range analysis say that it is always 0, or does it say it may be
> larger than zero?

Ok, I tried putting "print(x * 5);" inside the loop, before the return. Range analysis says that x is always 0 at that point.

I also tried breaking out the parts of the for loop, to observe x before the loop exit test:

(function() {
    for (let x = 0; ; ) {
        print(x * 5);
        if (!(x < 1))
            break;
        try {
            return w
        } catch (e) {}
        ++x;
    }
})()

Even in this case, range analysis still says that the phi has range [0,0], even though it's 1 in the second iteration. (The proposed patch fixes this testcase too.)

> The reason I did this is because when we OSR, we have *no* range
> information, so any value that can be derived from an OSR block will almost
> certainly not have any bounds, upper or lower.

That makes sense. From my survey, it doesn't seem to come up in practice though.
(In reply to Dan Gohman [:sunfish] from comment #6)
> (function() {
>     for (let x = 0; ; ) {
>         print(x * 5);
>         if (!(x < 1))
>             break;
>         try {
>             return w
>         } catch (e) {}
>         ++x;
>     }
> })()

This test case highlight a bigger issue which is that we are removing a branch, and computing some truth which is only valid on the stripped MIRGraph, right?  I think that as soon as we remove a branch, we should guard for our assumptions in any of the OSR blocks which might be taken after in the same execution.

OSR are not supposed to be frequent cases, so adding guards which are preventing any OSR after sounds like a safe approach.
(In reply to Nicolas B. Pierron [:nbp] from comment #7)
> (In reply to Dan Gohman [:sunfish] from comment #6)
> > (function() {
> >     for (let x = 0; ; ) {
> >         print(x * 5);
> >         if (!(x < 1))
> >             break;
> >         try {
> >             return w
> >         } catch (e) {}
> >         ++x;
> >     }
> > })()
> 
> This test case highlight a bigger issue which is that we are removing a
> branch, and computing some truth which is only valid on the stripped
> MIRGraph, right?  I think that as soon as we remove a branch, we should
> guard for our assumptions in any of the OSR blocks which might be taken
> after in the same execution.
> 
> OSR are not supposed to be frequent cases, so adding guards which are
> preventing any OSR after sounds like a safe approach.

From what I've seen so far, the MIRGraph and the other data structures remain consistent after the branch is removed. The only problematic assumption I've seen is range analysis effectively assuming that OSR edges correspond to edges which are still present.

I ran the entire Octane benchmark suite, along with a variety of other testcases, and didn't find any place where this assumption actually makes range information more precise. Consequently, it seems best to just remove the assumption.
Assignee: nobody → sunfish
mrosenberg, ping?
Flags: needinfo?(mrosenberg)
Attachment #8360563 - Flags: review?(mrosenberg) → review+
Duplicate of this bug: 960071
Same patch; added reviewer and updated email address.
Attachment #8360563 - Attachment is obsolete: true
Flags: needinfo?(mrosenberg)
Setting to sec-critical, on the principle of "Assume the worst" [0].

[0] https://wiki.mozilla.org/Security/Bug_Approval_Process
Keywords: sec-auditsec-critical
Comment on attachment 8373854 [details] [diff] [review]
osrlike-values.patch

[Security approval request comment]
How easily could an exploit be constructed based on the patch?

Not easily. 

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?

At worst, everything back to mozilla18.

If not all supported branches, which bug introduced the flaw?

Bug 765119.

Do you have backports for the affected branches? If not, how different, hard to create, and risky will they be?

Backports would be easy to create. The patch is just removing code.

How likely is this patch to cause regressions; how much testing does it need?

Unlikely. It's just removing code.
Attachment #8373854 - Flags: sec-approval?
Comment on attachment 8373854 [details] [diff] [review]
osrlike-values.patch

sec-approval+ for trunk. Please create Aurora, Beta, and ESR24 patches. I'm not sure about B2G so we'll see there.
Attachment #8373854 - Flags: sec-approval? → sec-approval+
mozilla-aurora can use the main osrlike-values.patch patch.
The bug is in ion, so b2g18 is unaffected, since it has ion disabled.
Keywords: checkin-needed
https://hg.mozilla.org/mozilla-central/rev/56673c075bed

Please nominate the patches for aurora/beta/esr24 uplift :)
Status: NEW → RESOLVED
Closed: 6 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla30
Comment on attachment 8373854 [details] [diff] [review]
osrlike-values.patch

[Approval Request Comment]
Bug caused by (feature/regressing bug #): bug 765119
User impact if declined: Security bug
Testing completed (on m-c, etc.): On m-c
Risk to taking this patch (and alternatives if risky): very low; it's literally just removing an optimization
String or IDL/UUID changes made by this patch: none
Attachment #8373854 - Flags: approval-mozilla-aurora?
Comment on attachment 8374432 [details] [diff] [review]
the patch ported to mozilla-beta

Bug caused by (feature/regressing bug #): bug 765119
User impact if declined: Security bug
Testing completed (on m-c, etc.): On m-c
Risk to taking this patch (and alternatives if risky): very low; it's literally just removing an optimization
String or IDL/UUID changes made by this patch: none
Attachment #8374432 - Flags: approval-mozilla-beta?
Comment on attachment 8374434 [details] [diff] [review]
the patch ported to mozila-esr24

[Approval Request Comment]
If this is not a sec:{high,crit} bug, please state case for ESR consideration: It is sec-critical.
User impact if declined: Security bug.
Fix Landed on Version: mozilla-central
Risk to taking this patch (and alternatives if risky): very low; it's literally just removing an optimization
String or UUID changes made by this patch: none

See https://wiki.mozilla.org/Release_Management/ESR_Landing_Process for more info.
Attachment #8374434 - Flags: approval-mozilla-esr24?
Attachment #8374434 - Flags: approval-mozilla-esr24? → approval-mozilla-esr24+
Attachment #8374432 - Flags: approval-mozilla-beta? → approval-mozilla-beta+
Attachment #8373854 - Flags: approval-mozilla-aurora? → approval-mozilla-aurora+
Whiteboard: [qa-]
Whiteboard: [qa-] → [qa-][adv-main28+][adv-esr24.4+]
Group: core-security
You need to log in before you can comment on or make changes to this bug.