Closed Bug 1127012 Opened 10 years ago Closed 9 years ago

Assertion failure: pn_type < PNK_LIMIT, at ParseNode.h:494


(Core :: JavaScript Engine, defect)

Not set



Tracking Status
firefox35 --- wontfix
firefox36 --- wontfix
firefox37 + fixed
firefox38 + fixed
firefox39 + fixed
firefox-esr31 --- unaffected
b2g-v1.4 --- unaffected
b2g-v2.0 --- unaffected
b2g-v2.0M --- unaffected
b2g-v2.1 --- fixed
b2g-v2.1S --- fixed
b2g-v2.2 --- fixed
b2g-master --- fixed


(Reporter: arai, Assigned: Waldo)



(Keywords: regression, sec-critical, Whiteboard: [adv-main37+])


(4 files)

Assertion failure: pn_type < PNK_LIMIT, at ParseNode.h:494

js> for (var {[ function(){} ]: {}}=1 in x) {}

Process 6585 stopped
* thread #1: tid = 0x7d8fe, 0x000000010092bbf8 js`js::frontend::ParseNode::getKind(this=0x0000000000000000) const + 24 at ParseNode.h:494, queue = '', stop reason = EXC_BAD_ACCESS (code=1, address=0x0)
    frame #0: 0x000000010092bbf8 js`js::frontend::ParseNode::getKind(this=0x0000000000000000) const + 24 at ParseNode.h:494
   491 	    bool isOp(JSOp op) const               { return getOp() == op; }
   493 	    ParseNodeKind getKind() const {
-> 494 	        MOZ_ASSERT(pn_type < PNK_LIMIT);
   495 	        return ParseNodeKind(pn_type);
   496 	    }
   497 	    void setKind(ParseNodeKind kind) {
(lldb) bt
* thread #1: tid = 0x7d8fe, 0x000000010092bbf8 js`js::frontend::ParseNode::getKind(this=0x0000000000000000) const + 24 at ParseNode.h:494, queue = '', stop reason = EXC_BAD_ACCESS (code=1, address=0x0)
  * frame #0: 0x000000010092bbf8 js`js::frontend::ParseNode::getKind(this=0x0000000000000000) const + 24 at ParseNode.h:494
    frame #1: 0x0000000100263073 js`js::frontend::Parser<js::frontend::FullParseHandler>::cloneParseTree(this=0x00007fff5fbfe320, opn=0x0000000000000000) + 115 at ParseNode.cpp:322
    frame #2: 0x000000010026323a js`js::frontend::Parser<js::frontend::FullParseHandler>::cloneParseTree(this=0x00007fff5fbfe320, opn=0x0000000103592090) + 570 at ParseNode.cpp:337
    frame #3: 0x00000001002635f0 js`js::frontend::Parser<js::frontend::FullParseHandler>::cloneParseTree(this=0x00007fff5fbfe320, opn=0x0000000103592138) + 1520 at ParseNode.cpp:382
    frame #4: 0x0000000100263c69 js`js::frontend::Parser<js::frontend::FullParseHandler>::cloneLeftHandSide(this=0x00007fff5fbfe320, opn=0x0000000103592058) + 921 at ParseNode.cpp:483
    frame #5: 0x000000010009c8b9 js`js::frontend::Parser<js::frontend::FullParseHandler>::forStatement(this=0x00007fff5fbfe320) + 3561 at Parser.cpp:4824
    frame #6: 0x00000001000ae86b js`js::frontend::Parser<js::frontend::FullParseHandler>::statement(this=0x00007fff5fbfe320, canHaveDirectives=true) + 683 at Parser.cpp:5837
    frame #7: 0x0000000100246b44 js`js::frontend::CompileScript(cx=0x0000000103581180, alloc=0x0000000103532230, scopeChain=JS::HandleObject at 0x00007fff5fbfdc68, evalCaller=JS::HandleScript at 0x00007fff5fbfdc60, evalStaticScope=Handle<js::StaticEvalObject *> at 0x00007fff5fbfdc58, options=0x00007fff5fbff268, srcBuf=0x00007fff5fbfefd8, source_=0x0000000000000000, staticLevel=0, extraSct=0x0000000000000000) + 4692 at BytecodeCompiler.cpp:346
    frame #8: 0x0000000100712282 js`JS::Compile(cx=0x0000000103581180, obj=JS::HandleObject at 0x00007fff5fbfef88, options=0x00007fff5fbff268, srcBuf=0x00007fff5fbfefd8, script=JS::MutableHandleScript at 0x00007fff5fbfef80) + 450 at jsapi.cpp:3898
    frame #9: 0x0000000100712356 js`JS::Compile(cx=0x0000000103581180, obj=JS::HandleObject at 0x00007fff5fbff018, options=0x00007fff5fbff268, chars=0x00000001035082e0, length=41, script=JS::MutableHandleScript at 0x00007fff5fbff010) + 102 at jsapi.cpp:3908
    frame #10: 0x00000001007124ff js`JS::Compile(cx=0x0000000103581180, obj=JS::HandleObject at 0x00007fff5fbff120, options=0x00007fff5fbff268, bytes=0x00000001054fdbc0, length=41, script=JS::MutableHandleScript at 0x00007fff5fbff118) + 383 at jsapi.cpp:3923
    frame #11: 0x000000010000a5da js`EvalAndPrint(cx=0x0000000103581180, global=Handle<JSObject *> at 0x00007fff5fbff350, bytes=0x00000001054fdbc0, length=41, lineno=1, compileOnly=false, out=0x00007fff763cb408) + 330 at js.cpp:474
    frame #12: 0x0000000100009f69 js`ReadEvalPrintLoop(cx=0x0000000103581180, global=Handle<JSObject *> at 0x00007fff5fbff440, in=0x00007fff763cb370, out=0x00007fff763cb408, compileOnly=false) + 793 at js.cpp:542
    frame #13: 0x000000010000982d js`Process(cx=0x0000000103581180, obj_=0x000000010535a060, filename=0x0000000000000000, forceTTY=true) + 493 at js.cpp:589
    frame #14: 0x0000000100008e98 js`ProcessArgs(cx=0x0000000103581180, obj_=0x000000010535a060, op=0x00007fff5fbff958) + 376 at js.cpp:5488
    frame #15: 0x000000010000475f js`Shell(cx=0x0000000103581180, op=0x00007fff5fbff958, envp=0x00007fff5fbffaa0) + 447 at js.cpp:5755
    frame #16: 0x00000001000020c9 js`main(argc=1, argv=0x00007fff5fbffa90, envp=0x00007fff5fbffaa0) + 4201 at js.cpp:6096
    frame #17: 0x0000000100000da4 js`start + 52

Similar bug happens with default value in destructuring (bug 1125658, bug 1126518, bug 1126555).

I guess many cases (PN_CODE, PN_NULLARY for RegExp, PN_TERNARY for if/for in comprehension) in cloneParseTree were not used until computed property was implemented (bug 924688), and now they're also used by default value in destructuring (bug 932080).
We should have test cases for it.

  for (var {[ [for (x of y) x] ]: {}}=1 in x) {}
  for (var {[ /x/ ]: {}}=1 in x) {}

Not sure the impact of this bug, so marking this as security.
I can confirm that bug 924688 introduced this. Prior to that the example code at the top of comment 0 resulted in a syntax error.
Blocks: 924688
some more test cases:
  for (var {[ let (x = 10) x ]: y}=1 in x) {}
  for (var {[ [x for (x in y)] ]: y}=1 in x) {}
  for (var {[ [x for each (x in y)] ]: y}=1 in x) {}

`for` and `let` are the issue related to scope object.
Jason: what happens downstream of the failed assertion? Is this exploitable or handled more or less gracefully?
Flags: needinfo?(jorendorff)
Keywords: regression
Swiping the needinfo.  He's busy enough, I need to work on this code soon, and the investigation will be helpful in preparing for that.  Report back soon, ideally today.
Flags: needinfo?(jorendorff) → needinfo?(jwalden+bmo)
The exact problem from comment 0 is a guaranteed non-array null dereference, which we presume is safe.

But as comment 2 demonstrates, there are *all* *sorts* of nodes (all the ones that can be expressions) that flow through computed property names.  And the problem extends to every way that cloneParseTree mishandles things, which means identifying every single way that a particular ParseNodeKind's structure doesn't quite correspond to that of its arity, as interpreted by that method.

The only way to diligently, confidently, and correctly handle this is to make cloning work by looking at ParseNodeKind.  (And forking out more ParseNodeKinds if needed, and making the existing kinds imply particular arities, and so on.)  Unfortunately, there's not a good way to examine the current situation and identify all the ways that it differs from a situation with proper handling, short of removing all dependence upon an "arity" concept and very carefully auditing the code to handle each ParseNodeKind and finding the ones whose proper handling doesn't depend on arity.

So the answer is, this has approximately unknowable security implications.  But given the variety of nodes flying around, probably best to assume the worst.

I think it's time to bite the bullet and get rid of arity as a concept in the JS engine.  Gonna be some messy work, and very detail-oriented because of converting from arity-handling (of which there are only a few) to kind-handling (of which there are ~119 now).  But it's really the only way to be sure here, and we've meant to do this for years.  jorendorff agrees that it's time to take this step.  Starting work now.
Assignee: nobody → jwalden+bmo
Flags: needinfo?(jwalden+bmo)
Keywords: sec-critical
For what it's worth, the bug to get rid of arity is bug 1130811.  DON'T PANIC at the massive number of patches happening in there.  It should be possible, if finicky, to extract out the salient changes when all's said and done in the end, but that won't totally be possible until the end, when I can compare pre- and post-states with all things done kindwise.
More intelligent cloning by kind does work -- partial patchwork to rewrite cloneParseTree to clone by kind shows that creating a new ObjectBox for the PNK_REGEXP case, and associating it correctly, is just what the doctor ordered to fix this test from comment 0:

  for (var {[ /x/ ]: {}}=1 in x) {}

Initial work on that cloneParseTree fixing suggests it's likely to be the trickiest to get right, and the bit that's least amenable to code-sharing.  As a sanity check I went and looked back at this bug to see if my first steps rewriting cloneParseTree fixed anything they were expected to fix.  They didn't at all, because I was trying to play fast and loose relying on prior patchwork in that bug that had illuminated PN_NULLARY nodes' structures, without stopping to think that it might ignore precisely what made this bug tricky (in the PNK_REGEXP case, I was copying the pn_objbox over directly, not cloning it).  Going through the other PN_NULLARY nodes revealed many other places with screwups.  I suspect for that part, it's going to be a slog of looking at the parser to see how each kind is created, then verifying exactly when nodes of each kind have their characteristics modified, and what needs to be transferred and how for purposes of cloning.

The cloneParseTree patchwork will, by dint of the deviations from the current state being perhaps clearest, be most likely to reveal what's wrong with the current code.  I'm uncertain as yet how I'll be managing the landing of those patches, and the creation of small, backportable patches here.  Possibly creating big cumulative patches to send off for targeted fuzzing, and/or doing the cloneParseTree work in this bug but holding off on landing until backporting and targeted fuzzing are complete.  Not sure yet, too busy trying to fix the code to worry much about that yet (except to say that I plan to keep tryservering of cloneParseTree progress to a minimum).
The cloneParseTree code implicated in all the crashes here is only invoked for these patterns:

  for (var ... = ... in ...) ...
  for (let ... = ... in ...) ...
  [... for (... in ...)]
  [... for (... of ...)]
  (... for (... in ...))
  (... for (... of ...))

It happens that ESmumble completely removes the first two syntaxes, which were only in ES<mumble because of grammar reuse considerations, unintentionally.  They're used in test suites and possibly almost never anywhere else.  Not 100% clear.

As for the latter four, those are legacy generator syntax.  No one supports them but us.  At some point we want to remove them.

So conceivably we could get rid of the cloneParseTree mistakes (I haven't yet established there are no mistakes in other arity-handling code) by removing support for all these non-standard syntaxes.

If only the first two syntaxes were problematic, that might be practical, even to backport.  (Although I'd be on the fence somewhat about doing it, versus letting a removal ride the trains, given the byzantine nature of for-loop parsing.)  But the last four are more or less implicated by any legacy generator use.  And there are many right now.

So while it looks almost possible to just remove this code -- and that would by far be the safest fix, from the security point of view -- I think we probably do sadly need the full fix.  I have code rewriting cloneParseTree kind-wise for all but 14 kinds, of which all but one or two are trivial (but unwritten yet because I can't test them).  Hoping to finish this Real Soon, maybe later today.  But those two hard cases are *very* complicated, so don't be surprised if it takes longer.  :-\
Generally cloning is just copying the right fields, cloning the right children, cloning list contents, and so on.  But not always.  Specifically, there appear to be serious problems with extending this approach to name-arity nodes.  Cloning must do...something...about the use-def chain.  Right now it clones a name node as another use of the underlying Definition.  But how do you clone a Definition?  We do this:

      * If the old name is a definition, the new one has pn_defn set.
      * Make the old name a use of the new node.
     if (opn->isDefn()) {
         handler.linkUseToDef(opn, (Definition *) pn);

So the Definition gets cloned as a use of the original definition.  That's fine *as long as we're not nested within a function* -- we do want to create a use of a definition when we clone.  But if we're inside a function, we want to make an honest-to-goodness clone of the Definition, as a Definition.  Certainly it's complete madness to clone function() { var x = ...; return x; } and have the |x| references in the clone refer to the |x| in the original.  But I'm not sure there's any practical way to do this, short of propagating a nestingLevel integer downward, or something similarly crazy.

Where does that leave us?  Admittedly, I might be misunderstanding how PNK_NAME nodes work.  But I doubt I am, and I see no way for cloning to believably handle this.

What to do?  The problematic syntax is fully non-standard, and it seems very difficult to adapt the current strategy to support it.  I think we should just close Pandora's box and prohibit computed property names in all contexts that clone a parse tree -- report a syntax error whenever a PNK_COMPUTED_PROPERTY_NAME is to be cloned.  Simple, straightforward, returns us to the state we were in before computed property names were introduced, ergo obviously addresses the problem.

We could also partially support cloning as many different node kinds as we think are safe.  As I mentioned, I got it down to a very, very few remaining kinds.  But then cases that wouldn't work would be basically inscrutable for any developer who hit them.  Can't very well say "you used a PNK_LEXICALSCOPE node, you lose", can we?  Maybe if our AST referred to ECMAScript grammar terms and we could say "don't use a try-catch inside a computed property name", but it doesn't.

So here's the simple patch.  Unfortunate that it has to break actual syntax, but it's new syntax we've supported only a few releases, it's non-standard, and it's weird enough that it might well be that no one at all uses it.
Attachment #8570340 - Flags: review?(jorendorff)
Comment on attachment 8570340 [details] [diff] [review]
Turn computed property names in cloned destructuring patterns into syntax errors

Review of attachment 8570340 [details] [diff] [review]:

r=me, assuming there's no other expedient fix. See below.

::: js/src/frontend/ParseNode.cpp
@@ +643,5 @@
> +    if (opn->isKind(PNK_COMPUTED_NAME)) {
> +        report(ParseError, false, opn, JSMSG_COMPUTED_NAME_IN_PATTERN);
> +        return null();
> +    }

Doesn't ES6 specify that this should work?

    let {length, [Symbol.isConcatSpreadable]: spreadable} = obj;

I'm ok with this as a stopgap, if there's no other immediate fix. But it's backing out a feature...
Attachment #8570340 - Flags: review?(jorendorff) → review+
(In reply to Jason Orendorff [:jorendorff] from comment #11)
> Doesn't ES6 specify that this should work?
>     let {length, [Symbol.isConcatSpreadable]: spreadable} = obj;

It does specify that it should work.  And it still does work.

The *only* place where cloneParseTree is called, is for a declaration that's within a for-in or for-of loop, or for the implied declaration in a legacy generator.  For a plain old declaration at statement level, cloning does not occur.  And for a plain old declaration as the first of three components of a for(;;) PNK_FORHEAD, cloning does not occur.  This is only changing/rejecting behavior in one syntax that is *not* part of the ES6 syntax for for-loops, and in another syntax that's legacy and that will never be standardized.
Comment 8 clarifies this. Good news! A+
Comment on attachment 8570340 [details] [diff] [review]
Turn computed property names in cloned destructuring patterns into syntax errors

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

Mistakes here go off the rails in extraordinarily complicated code that none of us correctly understand, *even setting aside this bug*.  Making confident predictions as to the consequences of mistakes here would be ludicrous.  The chance of this being exploitable probably depends on the automatically-assessed (and then manually-massaged) exploitability of what a fuzzer manages to produce for this.  It's not something we can eyeball, even given we're more familiar than anyone with the code.

> Do comments in the patch, the check-in comment, or tests included
> in the patch paint a bulls-eye on the security problem?

The landing of an error message to the effect that a particular syntax is "not supported", rather than our just fixing it to work, is a flag.  Doubly so because we're breaking syntax in (assuming we take this on branches, which we have to) stable releases, not letting it ride trains!  But there otherwise aren't comments waving the bloody shirt.

That said, omeone recognizing computed property names allow almost the entire gamut of parse nodes to appear here, would quickly see that the current state of affairs opened up Pandora's box.  Even cursory use of computed-name syntax here breaks trivially.

No tests here.  I have some locally, but they're what I wrote when I was trying to keep the existing syntax working, and they're extraordinarily overwrought if computed names here are just going to be a syntax error.

> Which older supported branches are affected by this flaw?
> If not all supported branches, which bug introduced the flaw?

Computed property names were introduced in bug 924688.  If the TM on that is right, this is an issue back to 34.

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

Backports should be trivial to create and should present no risk of anything but disabling the syntax meant to be disabled.

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

We're breaking previously-functional syntax in stable releases.  But this is new syntax (computed property names), and invalid syntax (see comment 8), and extraordinarily obscure syntax (the for-loop bits, at least -- our legacy generators are less obscure, but we can still fall back on the newness argument).  So there's a very good chance it won't break anything (except what it's meant to break).  But there's no possible way to know for sure.  Extra testing isn't going to make a bit of difference about that, or give us any meaningful reassurance.
Attachment #8570340 - Flags: sec-approval?
Comment on attachment 8570340 [details] [diff] [review]
Turn computed property names in cloned destructuring patterns into syntax errors

sec-approval+ for trunk. Let's check in and see if things break!

We'll want this on Aurora and Beta after an appropriate interval.
Attachment #8570340 - Flags: sec-approval? → sec-approval+

Sadly I landed this just before noticing bug 1140196.  Ideally they would have been both landed/fixt at once, as if you squint hard you can see that this patch discloses that something's screwball about cloneParseTree.  An attacker conceivably could see what this bug did, then find that other path into the same code.  But as long as that bug's reviewed quickly, it's not the end of the world.
Closed: 9 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla39
Please nominate this for Aurora/Beta uplift as soon as you get a chance.
Flags: needinfo?(jwalden+bmo)
Comment on attachment 8570340 [details] [diff] [review]
Turn computed property names in cloned destructuring patterns into syntax errors

The Xdr.h part of this bug fails to merge, by the nature of the XDR bytecode version.  I'll have to do special work to update that one weird part of the patch, so no autolanding of this patch on any branches.

Approval Request Comment
[Feature/regressing bug #]: bug 924688

[User impact if declined]: going off the rails in totally-un-understood code, triggering crashes in a variety of places, with very difficult-to-ascertain consequences quite possibly up to full-blown exploits

[Describe test coverage new/current, TreeHerder]: I have a test locally that verifies computed property names here turn into syntax errors, but I haven't landed it because it's a little overdone, and it slightly elucidates the exact situations where problems arise -- and once that's exposed it's trivial to fuzz the syntax and do very targeted exploit pentesting.  No need to give the attacks any help on that front.

[Risks and why]: Very little , just adds a new syntax error, and that for either non-standard syntaxes, or for very-obscure valid syntax that we've only supported a handful of releases.  Could break an extension, but it'd have to be a very cutting-edge extension with fresh code first added in the last several months.

[String/UUID change made/needed]: N/A
Flags: needinfo?(jwalden+bmo)
Attachment #8570340 - Flags: approval-mozilla-beta?
Attachment #8570340 - Flags: approval-mozilla-aurora?
Comment on attachment 8570340 [details] [diff] [review]
Turn computed property names in cloned destructuring patterns into syntax errors

Let's get this sec-crit fix that has already landed on m-c into Beta 4. Beta+ Aurora+
Attachment #8570340 - Flags: approval-mozilla-beta?
Attachment #8570340 - Flags: approval-mozilla-beta+
Attachment #8570340 - Flags: approval-mozilla-aurora?
Attachment #8570340 - Flags: approval-mozilla-aurora+
Attached patch Aurora backportSplinter Review
This relies on a bytecode version reserved by <>.
Attached patch Beta backportSplinter Review
Beta still has the old bytecode-reservation system, so this is a little screwy, more so than for the other backport.  But this still uses (two) bytecode version(s) reserved by <>.
Attached patch b2g34 backportSplinter Review
This uses a bytecode version reserved by <>.
Whiteboard: [adv-main37+]
Group: core-security → core-security-release
Group: core-security-release
You need to log in before you can comment on or make changes to this bug.