Last Comment Bug 649939 - Crash with too much recursion in js_IteratorMore
: Crash with too much recursion in js_IteratorMore
Status: RESOLVED FIXED
[fixed-in-tracemonkey][sg:dos] recurs...
: crash, regression, testcase
Product: Core
Classification: Components
Component: JavaScript Engine (show other bugs)
: unspecified
: x86 All
: -- critical (vote)
: ---
Assigned To: Paul Biggar
:
: Jason Orendorff [:jorendorff]
Mentors:
Depends on:
Blocks: fastiterators 630996
  Show dependency treegraph
 
Reported: 2011-04-14 01:58 PDT by Jan de Mooij [:jandem]
Modified: 2013-01-14 07:53 PST (History)
11 users (show)
choller: in‑testsuite+
See Also:
Crash Signature:
(edit)
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---


Attachments
Check for recursion (4.40 KB, patch)
2011-06-16 16:12 PDT, Paul Biggar
no flags Details | Diff | Splinter Review
Check for recursion (4.16 KB, patch)
2011-06-16 17:02 PDT, Paul Biggar
jwalden+bmo: review+
Details | Diff | Splinter Review

Description Jan de Mooij [:jandem] 2011-04-14 01:58:55 PDT
Bug 637010 fixed a crash when calling Iterator.prototype.next(). However, there's still a segfault when you call it twice:
--
Iterator.prototype.next();
Iterator.prototype.next();
--
This segfaults as a result of infinite recursion:
--
#1602 0x000f4650 in js_IteratorMore (cx=0x70b490, iterobj=0x1402168, rval=0x104d7c0) at ../jsiter.cpp:966
#1603 0x000f540c in iterator_next (cx=0x70b490, argc=0, vp=0x104d7c0) at ../jsiter.cpp:723
#1604 0x000f1286 in js::CallJSNative (cx=0x70b490, native=0xf537b <iterator_next(JSContext*, unsigned int, js::Value*)>, argc=0, vp=0x104d7c0) at jscntxtinlines.h:698
#1605 0x000edfb4 in js::Invoke (cx=0x70b490, argsRef=@0xbf8209c0, flags=0) at jsinterp.cpp:679
#1606 0x000eea8a in js::ExternalInvoke (cx=0x70b490, thisv=@0xbf820a28, fval=@0x104d7b0, argc=0, argv=0x0, rval=0x104d7b0) at jsinterp.cpp:839
#1607 0x000f4650 in js_IteratorMore (cx=0x70b490, iterobj=0x1402168, rval=0x104d7b0) at ../jsiter.cpp:966
#1608 0x000f540c in iterator_next (cx=0x70b490, argc=0, vp=0x104d7b0) at ../jsiter.cpp:723
#1609 0x000f1286 in js::CallJSNative (cx=0x70b490, native=0xf537b <iterator_next(JSContext*, unsigned int, js::Value*)>, argc=0, vp=0x104d7b0) at jscntxtinlines.h:698
#1610 0x000edfb4 in js::Invoke (cx=0x70b490, argsRef=@0xbf820b60, flags=0) at jsinterp.cpp:679
#1611 0x000eea8a in js::ExternalInvoke (cx=0x70b490, thisv=@0xbf820bc8, fval=@0x104d7a0, argc=0, argv=0x0, rval=0x104d7a0) at jsinterp.cpp:839
--
I'm not sure if this is exploitable, but at least it seems sg:dos.
Comment 1 David Mandelin [:dmandelin] 2011-04-26 16:30:23 PDT
Can you post the full test case?
Comment 2 Jan de Mooij [:jandem] 2011-04-27 10:34:40 PDT
It's in comment 0:

Iterator.prototype.next();
Iterator.prototype.next();
Comment 3 Jesse Ruderman 2011-05-06 22:45:26 PDT
Alternative testcase, found by my DOM fuzzer:

(new Iterator({})).__proto__.next()
Comment 4 Jesse Ruderman 2011-05-06 22:48:58 PDT
Like bug 637010, this is a regression from "fastiterators" bug 558754.  Sorta.  The patch in bug 637010 turned it from a null deref crash into a too-much-recursion crash.
Comment 5 Paul Biggar 2011-05-18 17:13:10 PDT
Thinking aloud...

I think there are two problems here, the first sort-of masking the second.

The first is that this didn't go to infinite recursion on the first call. When a cx is initialized, cx->iterValue is cleared (calloc) to the integer 0. When iterator_next is called, it checks tht cx->iterValue is the magic value JS_NO_ITER_VALUE, which it isn't, and so it thinks it has a pending value of 0, and returns it. I think the solution there is to initialize cx->iterValue in js_NewContext. (The cx->iterValue state machine doesn't expect iteration to start from a iterator_next).

The second problem is during the fetching and caching of the next value in the iteration. Iterator.prototype.next() is iterator_next, which calls js_IteratorMore, which has no NativeIterator, so needs to get it's value from calling the next() method, which calls iterator_next.

Wait, what? iterator_next can only be called when you're iterating without using a custom object (which would have a different next() method). So it expects to be iterating over a native object, using a native iterator. So it's really surprised to find iterator_next when it calls next(). When else would this happen? Basically never except when calling next() on the prototype.

If it were calling next() for a native object, it would never have ended up here. And the other callers of js_IteratorMore are the opcodes in the interpreter (or JIT equivalents). So we don't want to call next() again if the iterobj is Iterator.

But then what? What's the intended result of Iterator.prototype.next()? I guess it should do the same as if it were in a for..in loop. I'll look at that tomorrow.
Comment 6 Paul Biggar 2011-05-19 10:58:05 PDT
brendan, I talked to dherman about this, and we collectively cannot decide what this code should do:

  Iterator.prototype.next()

The docs (https://developer.mozilla.org/en/JavaScript/Guide/Iterators_and_Generators) don't say and the proposal (http://wiki.ecmascript.org/doku.php?id=proposals:iterators_and_generators) is written in ES4 speak, but also doesn't seem to say.

My first thought was that it should iterate over Iterator.prototype. This is a bit weird, because that would be an internal iterator when the rest of JS only really uses external iterators. And we'd have to define how it should behave after it's done iterating and throws its first StopIteration (options are reset or keep throwing StopIteration, I'm guessing the latter).
Comment 7 David Mandelin [:dmandelin] 2011-05-24 14:02:36 PDT
Jeff, do you have any advice for Paul on comment 6?
Comment 8 Jeff Walden [:Waldo] (remove +bmo to email) 2011-06-06 15:24:48 PDT
Seems to me that Iterator.prototype should be an iterator which is initially unstarted and which, on .next(), throws StopIteration.  As in Python (I think?), nexting more should continue to throw StopIteration.  This doesn't seem particularly more or less sensible than any other semantics, so if you feel strongly for something else, I could easily be persuaded.
Comment 9 Paul Biggar 2011-06-16 16:12:33 PDT
Created attachment 539924 [details] [diff] [review]
Check for recursion

This checks if the fetched method is iterator_next (which will lead to recursion). Rather nasty.

Looking for a better way to do this, but I can't really think of one. We can't use the proto (proto.next might change), nor NativeIterator (that only says if we're iterating across a vector), nor check if we're calling on Iterator (different globals).
Comment 10 Paul Biggar 2011-06-16 17:02:40 PDT
Created attachment 539942 [details] [diff] [review]
Check for recursion

Check for recursion more directly.
Comment 11 Jeff Walden [:Waldo] (remove +bmo to email) 2011-06-17 16:41:11 PDT
Comment on attachment 539942 [details] [diff] [review]
Check for recursion

>+function assertRaises(exc, callback) {

exc is no longer needed, please remove it to reduce confusion for test readers.


>diff --git a/js/src/jsiter.cpp b/js/src/jsiter.cpp
>--- a/js/src/jsiter.cpp
>+++ b/js/src/jsiter.cpp
>@@ -960,16 +960,23 @@ js_IteratorMore(JSContext *cx, JSObject 
>         return true;
>     }
> 
>     /* Fetch and cache the next value from the iterator. */
>     if (!ni) {
>         jsid id = ATOM_TO_JSID(cx->runtime->atomState.nextAtom);
>         if (!js_GetMethod(cx, iterobj, id, JSGET_METHOD_BARRIER, rval))
>             return false;
>+
>+        /*
>+         * Check for Iterator.prototype.next, which is undefined by the spec,
>+         * but can lead to infinite recursion.
>+         */
>+        JS_CHECK_RECURSION(cx, return false);

First, put this check above the start of this block.  It looks like both this block (via function call) and the next block (via property get) could reenter, so it seems both need the recursion check.  (Or at least they won't both be hurt by it.)  Second, it doesn't seem to me that the comment should call out one specific method as the source of the recursion -- just say something like "We're reentering and performing indeterminate actions which might recur, so guard against stack exhaustion."

Other than those bits, looks fine.
Comment 13 Chris Leary [:cdleary] (not checking bugmail) 2011-06-20 17:12:19 PDT
cdleary-bot mozilla-central merge info:
http://hg.mozilla.org/mozilla-central/rev/1f11cd362858
Comment 14 Christian Holler (:decoder) 2013-01-14 07:53:25 PST
A testcase for this bug was automatically identified at js/src/jit-test/tests/basic/bug649939.js.

Note You need to log in before you can comment on or make changes to this bug.