Closed Bug 685321 Opened 13 years ago Closed 12 years ago

Assertion failure: [infer failure] Missing type pushed 0: int, at jsinfer.cpp:341 with destructuring assignment

Categories

(Core :: JavaScript Engine, defect)

defect
Not set
critical

Tracking

()

VERIFIED FIXED
mozilla11
Tracking Status
firefox7 - wontfix
firefox8 - wontfix
firefox9 + verified
firefox10 + verified
firefox11 + verified
status1.9.2 --- unaffected

People

(Reporter: decoder, Assigned: dmandelin)

References

Details

(Keywords: assertion, testcase, Whiteboard: [sg:critical][qa!])

Attachments

(1 file, 1 obsolete file)

The following test asserts on mozilla-central revision b7d269a291b6 (options -m -n -a):


function f() {
    function g() {
        for (var i = 0; i < 3; i++)
        x = i;
    };
    var [x] = 0;
    g();
    assertEq(x, 2);
}
f();
In function 'f', 'x' is not marked as a closure variable by the emitter, and analysis and JM will not account for modifications that 'g' makes to the variable.  This is bad news for JM, both with and without TI.
Whiteboard: [sg:critical?]
Is this a regression? I guess technically it must be somewhere since JM isn't on the 1.9.2 branch, but does the problem go that far back? In other words, are our current Firefox 6 or 7 users vulnerable, or is this just a (near) future problem?
The closure variable stuff was added for Firefox 4, so the problem could potentially go back that far.  dvander, do you mind looking at this?  I don't know at all the code which determines closure variables, and IonMonkey will also need this information to be correct.
FWIW, I couldn't repro on a JS 1.8.5 shell, which is trivially different from Firefox 4's.

Note, that shell doesn't have the -n option, I ran with -m -a.
(In reply to Wesley W. Garland from comment #4)
> FWIW, I couldn't repro on a JS 1.8.5 shell, which is trivially different
> from Firefox 4's.
> 
> Note, that shell doesn't have the -n option, I ran with -m -a.

The assert triggered here only exists in the type inference code (-n). However, the underlying issue described by bhackett might go back much further, you won't get this assert though. It should however be possible though to come up with a correctness test that shows the problem. If I understand the problem correctly, the modification made by 'g' in this code will not be visible outside the function, so checking that should work. I'll try this tomorrow with a small test.
I looked at this a while on Friday. I found that the parser does mark an 'x' variable (i.e., a 'name' parse node with atom "x") as closed over at these lines in jsparse.cpp:

            /* Mark the outer dn as escaping. */
            outer_dn->pn_dflags |= PND_CLOSED;

But later, in the emitter in MaybeEmitVarDecl, it doesn't note the closed name here:

    if (cg->inFunction() &&
        JOF_OPTYPE(pn->getOp()) == JOF_LOCAL &&
        pn->pn_cookie.slot() < cg->bindings.countVars() &&
        cg->shouldNoteClosedName(pn))
    {
        if (!cg->closedVars.append(pn->pn_cookie.slot()))

It seems that the parse node here doesn't have the same identity as the one marked by the parser. 

If I change the test case not to use the destructuring assignment, then the nodes do have the same identity, the closed-over flag gets propagated by the the code above, and the test passes.
Crashing testcase on aurora tip:

var o = {};
function f() {
    function g() {
        x = 80;
        return x;
    };
    Object.defineProperty(o, "f", {get:g});
    var [x] = 0;
    x = {};
    2 + o.f;
    print(x);
}
f();
Tentatively taking.
Assignee: general → jwalden+bmo
The root of the problem, which I think I finally understand now, is this.

In the non-destructuring case, the parse node for the variable name |x| in |var x| is created by NewBindingNode.  That does the work to reuse the existing placeholder definition which is found in lexdeps, added there by LeaveFunction when leaving |g|.

But in the destructuring case, |x|'s parse node is created by NameNode::create, way way deep in Parser::primaryExpr.  (This seems to be a consequence of making destructuring-parsing a sub-mode of primary-expression parsing.)  That NameNode parse node isn't the placeholder created in lexdeps when doing LeaveFunction for the function |g|.  So we continue on our way with the wrong parse node, and we insert a definition for that parse node into decls.  Meanwhile, the real placeholder in lexdeps gets PND_CLOSED all the way out, because we never find a definition for it.  So we get divergence, and eventually someone tries to work with a closed-over variable only to find things are whack.

Whee, analysis done.  I think.  Fix coming tomorrow, I hope.
I am somewhat inclined to rewrite the parsing of |var DECL|, where |DECL| uses destructuring syntax, to fix this, because it's not at all clear to me where exactly it could be fixed in the current code.

Changing the place where the NameNode is created seems incredibly dodgy to me, because that code is central to all name parsing everywhere, and I have nowhere near enough understanding of the code to be confident that any change I'd make would only affect this narrow destructuring-specific situation.

Changing BindDestructuringVar seems initially more plausible.  But at that point you already have the mis-constructed parse node, and it's already been inserted into the parse tree, so you'd have to do an after-the-fact hot-swap or something.  That seems nearly as dangerous itself.

Changing BindVarOrConst or Define (the former calls the latter) might also be plausible.  But you still have the mis-constructed parse node to deal with.  And you have the same problem with the NameNode location, that this is quite central code, and that changing it will affect a lot of other code in subtle ways such that it's difficult to have much certainty in a fully correct fix.

Of course the down side of a rewrite is that such a fix is a very unlikely candidate for backporting.  Maybe that matters, maybe it doesn't.  Any of the potential plausible spot fixes look equally un-candidate-worthy to me.  So maybe rewriting really is the way to go.  Thoughts from others appreciated.
Waldo, do we know how far back this problem goes? And based on your last comment, this doesn't sounds like something we'd like to take on beta, but if you disagree please say so. And also, do we believe this is actually exploitable? Trying to figure out what releases we need to worry about this for...
I don't believe the destructuring parsing has changed much since it was first introduced.  The name resolution stuff that seems to be the cause of it probably goes back to bug upvar2 or so.  The JSCodeGenerator list that is mistaken, that's now being used by TI and others, is somewhat newer (I think), but I don't know that it's that much newer.  If this doesn't go back to Firefox 4 at least, I'd be surprised.

Without a spot-fix, yeah, I don't see this being taken for beta.  Not to say one's not possible, but I'm not smart enough, and don't know enough about how all the pieces intertwine here, to write it.  Perhaps after the rewrite I'll understand enough, but it's hard to say.

As for exploitability, I don't know who depends on this information for correctness.  But if (as seems the case) it's any of the JITs, it probably is with enough pain, or at least it isn't clearly non-exploitable.
I think this is exploitable.  That 'x = 80' line is specifying the address which the program will dereference, and while this is just a read, it should be possible to get the program to write to a location based on the value it reads here.
As per comment 13 this is confirmed sg:critical (invalid read influencing control flow).
Whiteboard: [sg:critical?] → [sg:critical]
Jeff, this critical bug is almost 2 months old by now, can you find some time to work on this, or should we find someone else to take this over? Thanks.
I've kind of been holding off on this because I know it conflicts pretty badly with stuff Luke is doing for parsing of let-statements and such.  Probably it makes more sense for him to do it at this point, since he's already touching that code so much.
Assignee: jwalden+bmo → luke
Jeff and I talked and it would seem that his destructuring overhaul (or spot fix if one should magically appear) would be orthogonal (even complementary) to the let changes.
Assignee: luke → jwalden+bmo
I started work on this several hours ago today, and thus far things proceed nicely -- lots of simplifications to the parsing code to be made.  The hard part -- actually binding names correctly and all that -- yet remains.
Status: NEW → ASSIGNED
OS: Linux → All
Hardware: x86_64 → All
Attached patch one-line spot fix (obsolete) — Splinter Review
Waldo, will you please take this and add a test and land it? Full speed ahead on the cleanups for EmitVariables etc. in other bugs. This is the minimal fix for this bug.

/be
Blocks: 566022
Blocks: 701248
Jason, can you expedite review on this? This sg:crit has been outstanding for a while. I verified that the patch fixes the problem and passes shell tests, and it seems safe to be conservative about marking variables as closed-over, but it's harder to see whether this fixes all the security vulnerabilities associated with the underlying bug.
Attachment #574986 - Attachment is obsolete: true
Attachment #575365 - Flags: review?(jorendorff)
The analysis in comment 10 did almost hit the target, but paragraph 4 backed away for fear of changing a common subroutine without analyzing how it is used. (That's not an argument for doing away with common subroutines by manually expanding them into their call sites, because then we would have to make this bug's fix in many places.)

The logic in the one-line fix is required in that place in the common Define subroutine, though, as the comment for TCF_DECL_DESTRUCTURING suggests.

/*
 * Set when parsing a declaration-like destructuring pattern.  This
 * flag causes PrimaryExpr to create PN_NAME parse nodes for variable
 * references which are not hooked into any definition's use chain,
 * added to any tree context's AtomList, etc. etc.  CheckDestructuring
 * will do that work later.
 *
 * The comments atop CheckDestructuring explain the distinction
 * between assignment-like and declaration-like destructuring
 * patterns, and why they need to be treated differently.
 */
#define TCF_DECL_DESTRUCTURING  0x10000

This comment fails to detail how CheckDestructuring calls BindDestructuringVar calls binder -> BindVarOrConst calls Define, but comment 10 tracked that well enough.

Destructuring in JS requires parsing object and array lvalue patterns as object and array literal rvalues at first, and then fixing up the parse tree (with error checks) to be a "pattern" instead of a "literal".

This is already formalized in the ES6 drafts -- see http://wiki.ecmascript.org/doku.php?id=globalization:specification_drafts. There is no getting around it without a different parsing algorithm (GLR could do it), but not a practical one I know of.

Given the nature of the parsing problem, the challenges of validating and revising the AST and any def/use chains computed eagerly in one pass while parsing can't be avoided.

The one-line fix needs a comment, but it is a complete fix. It covers all the Define cases that convert a use misattributed to an earlier def into a fresh def and therefore strip some or all uses from the old def's chain, linking them from the new def's chain (the old def is dn, the new one pn).

The one-line fix is a consistent fix. The bug 566022 patch that introduced this bug added PND_CLOSED but failed to propagate it to the new def from the old.

Jason is a good reviewer choice, or Jim Blandy -- they know how the one-pass def/use chaining code works.

/be
I did look at the patch for bug 566022, sorry I missed this regression in it, but I don't see a review stamp there. Dvander, did it get real review, maybe when the moo branch landed?

/be
Comment on attachment 575365 [details] [diff] [review]
spot fix with test case

The test case doesn't fail for me in tip, even with -m -n -a.
Is it supposed to? 

Please also add the test case in comment 7.

Why propagate only PND_CLOSED and not all the PND_USE2DEF_FLAGS? I can't fit the entire algorithm in my head at once, so I'm not good at reasoning about this stuff. I can imagine a possible argument that the situation I'm worrying about, where one of the other PND_USE2DEF_FLAGS is marked on the wrong def before it's shadowed, just can't happen.

r=me with those addressed.
Attachment #575365 - Flags: review?(jorendorff) → review+
(In reply to Jason Orendorff [:jorendorff] from comment #23)
> The test case doesn't fail for me in tip, even with -m -n -a.
> Is it supposed to?

Oh ffs. Ignore this. I was using the shell wrong. (You have to put the flags before the filename, dummy...)

The test asserts just like it's supposed to.
this has merged, -> RESO FIXED ...but David, what about these review comments?

> Please also add the test case in comment 7.
> 
> Why propagate only PND_CLOSED and not all the PND_USE2DEF_FLAGS? I can't fit
> the entire algorithm in my head at once, so I'm not good at reasoning about
> this stuff. I can imagine a possible argument that the situation I'm
> worrying about, where one of the other PND_USE2DEF_FLAGS is marked on the
> wrong def before it's shadowed, just can't happen.
> 
> r=me with those addressed.
Status: ASSIGNED → RESOLVED
Closed: 13 years ago
Resolution: --- → FIXED
Reopening this bug, seems there's two outstanding issues here, one testcase is missing, and there's a review comment that's not dealt with.

With both those issues dealt with we'd still be interested in taking this for 9, but time's running short.
Status: RESOLVED → REOPENED
Resolution: FIXED → ---
Oops, not sure how I missed those review comments. I just landed the additional test case:

http://hg.mozilla.org/integration/mozilla-inbound/rev/1fc0e97638e0

I will briefly look at the USE2DEF issue, but I don't think it's worth spending a lot of time on because Jeff will be done with the definitive fix for this bug soon anyway--this patch is just temporary until that one is done.
From reading the code, it looks to me that propagating more USE2DEF flags is probably at least OK--it seems to feed into conservative analyses. I tested a version of the patch that does that and it checks out OK on shell tests. One risk is that it could deoptimize more things.

I don't think it's worth worrying too much about this stopgap fix anyway, and we'll likely have the better fix before the 11 Aurora merge, but at this point I think options are:

1. Take the current patch onto 9 and/or 10. It is working so far on trunk. The main issue is that it may not fix hypothetical problems around not propagating the other flags. It also carries some level of risk from being a new patch.

2. Take the patch that propagates more USE2DEF flags onto 9 and/or 10 (after landing it to trunk). This covers the hypothetical problems, but is another patch, so more risk of regression.

3. Don't take any of these patches to 9 and 10.

My default action will be #3 (do nothing) unless someone else says they want #1 or #2.
For what it's worth, I have a comprehensive fix finished down to about five jstests.py failures and an unknown number of jit-test failures (but I would place reasonable odds on any failures there being from new patterns, not from jit-specific stuff).  Once those are fixed it could use the normal polishing before posting, but beyond those things it's in good shape.  (And yes, it does fix the problem here, and the hackaround already posted is removable with it in place.)  I'm holding off on polishing off the rest of it until various other emitter and parser bugs-in-progress get fixed first.  Lots of churn in this code of late...and that's a good thing!
David, can you attach a complete patch for branches here and request approval? Doesn't sound like we need to worry about the USE2DEF flag details here given waldo's upcoming fixes, so let's land what we landed on trunk for branches here!
Where's the comprehensive patch going? I suggest a new bug.

I used CLOSED only ,not USE2DEF_FLAGS, because I was concerned about deoptimizations and I saw no correctness requirements.

/be
New bug because it can be open, not s-s, mainly; also because it will be cleaning up code, not fixing a bug that no longer bites, namely this bug.

/be
I'll file a new bug.
Comment on attachment 575365 [details] [diff] [review]
spot fix with test case

Benefits: it fixes a security vulnerability. Risk is low: it is a 1-line deoptimization patch (that had no effect on benchmarks).
Attachment #575365 - Flags: approval-mozilla-beta?
Attachment #575365 - Flags: approval-mozilla-aurora?
Filed bug 708892 for the finish.
Assignee: jwalden+bmo → dmandelin
And now that we have the new bug this one is fixed.
Status: REOPENED → RESOLVED
Closed: 13 years ago12 years ago
Resolution: --- → FIXED
Comment on attachment 575365 [details] [diff] [review]
spot fix with test case

[Triage Comment]
Low risk fix to an sg:crit bug. Let's land on aurora and beta today.
Attachment #575365 - Flags: approval-mozilla-beta?
Attachment #575365 - Flags: approval-mozilla-beta+
Attachment #575365 - Flags: approval-mozilla-aurora?
Attachment #575365 - Flags: approval-mozilla-aurora+
Whiteboard: [sg:critical] → [sg:critical][qa+]
Verified fixed with jsshell from beta, aurora, nightly tinderbox debug builds on OS X.
Status: RESOLVED → VERIFIED
Flags: in-testsuite+
Flags: in-litmus-
Whiteboard: [sg:critical][qa+] → [sg:critical][qa!]
Whiteboard: [sg:critical][qa!] → [sg:critical][qa-]
Whiteboard: [sg:critical][qa-] → [sg:critical][qa!]
Depends on: 719750
Group: core-security
You need to log in before you can comment on or make changes to this bug.