GC hazards in jsarray.c: unrooted atoms for large index

VERIFIED FIXED in mozilla1.8.1beta2

Status

()

Core
JavaScript Engine
--
critical
VERIFIED FIXED
11 years ago
10 years ago

People

(Reporter: Igor Bukanov, Assigned: Igor Bukanov)

Tracking

({verified1.8.0.5, verified1.8.1})

Trunk
mozilla1.8.1beta2
verified1.8.0.5, verified1.8.1
Points:
---
Bug Flags:
blocking1.7.14 ?
blocking-aviary1.0.9 ?
blocking1.8.1 +
blocking1.8.0.5 +
in-testsuite +

Firefox Tracking Flags

(Not tracked)

Details

(Whiteboard: [sg:critical])

Attachments

(6 attachments, 7 obsolete attachments)

(Assignee)

Description

11 years ago
In many places SpiderMonkey code assumes that potential GC calls would not collect atoms. Unfortunately this is not true since the branch callback is allowed to call JS_MaybeGC/JS_ForceGC which would collect unrooted atoms.

The following example demonstrates the problem for the browser/shell:

var N = 0xFFFFFFFF;

var a = [];
a[N - 1] = 1;
a.__defineGetter__(N - 1, function() { 
	var tmp = [];
	tmp[N - 2] = 0;
        if (typeof gc == 'function')
                gc();
        for (var i = 0; i != 50000; ++i) {
                var tmp = 1 / 3;
                tmp /= 10;
        }
        for (var i = 0; i != 1000; ++i) {
                // Make string with 11 characters that would take
                // (11 + 1) * 2 bytes or sizeof(JSAtom) so eventually
                // malloc will ovewrite just freed atoms. 
                var tmp2 = Array(12).join(' ');
	}
	return 10; 
});


// The following always-throw getter is to stop unshift from doing
// 2^32 iterations.
var toStop = "stringToStop";
a[N - 3] = 0;
a.__defineGetter__(N - 3, function() { throw toStop; });

var good = false;

try {
	a.unshift(1);
} catch (e) {
	if (e === toStop)
		good = true;
}

When embedded in a <script> tag, it crashes the browser.
(Assignee)

Comment 1

11 years ago
Created attachment 227465 [details] [diff] [review]
Fix

In most places the patch just reorders IndexToId and OBJ_GET_PROPERTY calls so a getter would not have a chance to kill the atom behind a large index. 

The exception to this rule is in array_reverse and array_pop methods where the ids when necessary are protected with JS_KEEP_ATOMS call and array_extra where for the MAP case the id is re-build again to simplify the implementation.

The patch is not minimal since I could not to resist and optimized IndexToId to avoid constructing temporary JSString.
Attachment #227465 - Flags: review?(mrbkap)
(Assignee)

Comment 2

11 years ago
Initially I thought that a generic way to fix the problem would be to make sure that GC call from the branch callback would always keep atoms. But it is way to easy to prevent collection of atoms at all. So with the patch from comment  1 I took a conservative approach of rooting the atoms in jsarray.c. This is the reason for changing the bug title as the focus here is on just jsarray.c.
Summary: GC hazards via collection of live atoms from branch callback → GC hazards in jsarray.c: unrooted atoms for large index
(Assignee)

Comment 3

11 years ago
Here is a test case to show the problem in browser/jsshell with Array.protype.pop method. Without the patch it segfaults:

var N = 0xFFFFFFFF;
var a = [];  
a[N - 1] = 0;

var expected = "GETTER RESULT";

a.__defineGetter__(N - 1, function() {
        delete a[N - 1];
        var tmp = [];
        tmp[N - 2] = 1;

        if (typeof gc == 'function')
                gc();
        for (var i = 0; i != 50000; ++i) {
                var tmp = 1 / 3;
                tmp /= 10;
        }
        for (var i = 0; i != 1000; ++i) {
                // Make string with 11 characters that would take
                // (11 + 1) * 2 bytes or sizeof(JSAtom) so eventually
                // malloc will ovewrite just freed atoms.
                var tmp2 = Array(12).join(' ');
        }
        return expected;
});

var actual = a.pop();

print(actual === expected);
(Assignee)

Comment 4

11 years ago
Created attachment 227518 [details] [diff] [review]
Fix for 1.8.1, 1.8.0 branches

This a fix version for 1.8.1 branch.
Attachment #227518 - Flags: approval1.8.1?
(Assignee)

Comment 5

11 years ago
I guess it is way to late for 1.8.0.5 approval but I ask in any case. And if this is too late indeed, then I think I have to make comments in the patch less explicit about making an exploit.
Flags: blocking1.8.1?
Flags: blocking1.8.0.5?
(Assignee)

Comment 6

11 years ago
(In reply to comment #5)
> I guess it is way to late for 1.8.0.5 approval but I ask in any case. And if
> this is too late indeed, then I think I have to make comments in the patch less
> explicit about making an exploit.

Or wait with a trunk commit until 1.8.0.6 

(Assignee)

Comment 7

11 years ago
Comment on attachment 227518 [details] [diff] [review]
Fix for 1.8.1, 1.8.0 branches

The patch applies to 1.8.0 branch as is.
Attachment #227518 - Attachment description: Fix for 1.8.1 branch → Fix for 1.8.1, 1.8.0 branches
Attachment #227518 - Flags: approval1.8.0.5?
(Assignee)

Comment 8

11 years ago
As far as I can see jsarray.c is the only source of this type of hazards in the engine. Other users of js_Atomize* either root the atoms via JS_KEEP_ATOMS or they never call getter/setter or other scriptable code (js_XDRAtom case).
Comment on attachment 227465 [details] [diff] [review]
Fix

Drive-by, thanks for fixing:

+     * a branch callback call and the latter invokes js_GC without
+     * GC_KEEP_ATOMS flag, GC would collect the atom that we would access later

"the" after "without"

+    if (len > JSVAL_INT_MAX + 1)

To my eyes len >= JSVAL_INT_MAX + 1 is slightly clearer.

+        ok = ok && IndexToId(cx, len - i - 1, &id2) &&
+             PropertyExists(cx, obj, id2, &id2exists) &&
+             (!id2exists || OBJ_GET_PROPERTY(cx, obj, id2, tmproot2));

You clearly want JS2's &&= operator ;-).

Breaking as soon as ok is false would use the same number of instructions but be faster in a failure case.  That doesn't matter, but it is the way most code in SpiderMonkey is written. And retesting ok in "ok = ok && ..." after previous successes is unnecessary in the case we want to optimize (no failures). So I'm still in favor of breaking on first failure.

This repeated comment:
+                 * Construct id2 after we got property's value not to worry
+                 * about getter there triggering GC and collectiong id2.

could be reworded to say "to not worry" -- splitting an infinitive is ok in such cases.  The longer way around is "so as not to worry".

/be
Attachment #227465 - Flags: review+
(Assignee)

Comment 10

11 years ago
(In reply to comment #9)
> And retesting ok in "ok = ok && ..." after previous
> successes is unnecessary in the case we want to optimize (no failures).

I claim a sane compiler would do exactly the same number of tests in
  ok = A && B
and
  ok = A
  ok = ok && B

In the first case the compiler must test for A to avoid calculating B. Similarly in the second case the compiler has to test ok to avoid calculating B. But there is no need to test the results of A in ok = A.

In the initial version of the patch I just replaced "return JS_FALSE" by "goto bad". When I discover later that I missed one replacement (probably because it scrolled beyond the top edge of the window), I gave up and rewrote it as in the patch.
(In reply to comment #10)
> (In reply to comment #9)
> > And retesting ok in "ok = ok && ..." after previous
> > successes is unnecessary in the case we want to optimize (no failures).
> 
> I claim a sane compiler would do exactly the same number of tests in
>   ok = A && B
> and
>   ok = A
>   ok = ok && B

I know, that was not my point (I adverted to the equivalence of these forms when I wrote "You clearly want JS2's &&= operator ;-)").

My point was that most SpiderMonkey code breaks on failure to avoid retesting ok on success.  Break meaning 'break', 'goto out', 'goto bad', etc.

> In the initial version of the patch I just replaced "return JS_FALSE" by "goto
> bad". When I discover later that I missed one replacement (probably because it
> scrolled beyond the top edge of the window), I gave up and rewrote it as in the
> patch.

Ok.  I have a taller window ;-).

/be
Comment on attachment 227465 [details] [diff] [review]
Fix

>--- .pc/array_atom_roots.diff/js/src/jsarray.c	2006-06-26 
>+                 * Construct id2 after we got property's value not to worry
>+                 * about getter there triggering GC and collectiong id2.

I think I'd prefer s/got/after we've gotten/ in this comment, and please fix the 'collecting' typo, here and where you've copy/pasted the comment. Other than that, this looks good.
Attachment #227465 - Flags: review?(mrbkap) → review+

Comment 13

11 years ago
Comment on attachment 227518 [details] [diff] [review]
Fix for 1.8.1, 1.8.0 branches

Please address review comments and re-nominate.
Attachment #227518 - Flags: approval1.8.1?
(Assignee)

Comment 14

11 years ago
Created attachment 227578 [details] [diff] [review]
Fix v2

Changes compared with version 1:

1. I reverted to the "break early" style in array_reverse and array_pop to preserve code style.  

2. Comments are shortened but I compensated that by references to the bug.
Attachment #227465 - Attachment is obsolete: true
Attachment #227518 - Attachment is obsolete: true
Attachment #227578 - Flags: superreview?(brendan)
Attachment #227578 - Flags: review?(mrbkap)
Attachment #227518 - Flags: approval1.8.0.5?
(Assignee)

Comment 15

11 years ago
Created attachment 227583 [details] [diff] [review]
Fix v2b

Fixing mistypes in the new comments.
Attachment #227578 - Attachment is obsolete: true
Attachment #227583 - Flags: superreview?(brendan)
Attachment #227583 - Flags: review?(mrbkap)
Attachment #227578 - Flags: superreview?(brendan)
Attachment #227578 - Flags: review?(mrbkap)

Updated

11 years ago
Attachment #227583 - Flags: superreview?(brendan) → superreview+
(Assignee)

Comment 16

11 years ago
Here is a test case for reverse:

var N = 0xFFFFFFFF;
var a = [];
a[N - 1] = 0;

var expected = "GETTER RESULT";

a.__defineGetter__(N - 1, function() {
        delete a[N - 1];
        var tmp = [];
        tmp[N - 2] = 1;

        if (typeof gc == 'function')
                gc();
        for (var i = 0; i != 50000; ++i) {
                var tmp = 1 / 3;
                tmp /= 10;  
        }
        for (var i = 0; i != 1000; ++i) {
                // Make string with 11 characters that would take
                // (11 + 1) * 2 bytes or sizeof(JSAtom) so eventually
                // malloc will ovewrite just freed atoms.
                var tmp2 = Array(12).join(' ');
        }
        return expected;
});

// The following always-throw getter is to stop unshift from doing
// 2^32 iterations.
var toStop = "stringToStop";
a[N - 3] = 0;
a.__defineGetter__(N - 3, function() { throw toStop; });


var good = false;

try {
        a.reverse();
} catch (e) {
        if (e === toStop)
                good = true;
}

print("Good="+good);
Comment on attachment 227583 [details] [diff] [review]
Fix v2b

>+     * When len > JSVAL_INT_MAX + 1 the loop bellow accesses indexes greater

"below".
Attachment #227583 - Flags: review?(mrbkap) → review+
(Assignee)

Comment 18

11 years ago
Created attachment 227711 [details] [diff] [review]
Fix v2c

Patch to commit with the last spelling fixes.
Attachment #227583 - Attachment is obsolete: true
Comment on attachment 227711 [details] [diff] [review]
Fix v2c

approved for 1.8.0 branch, a=dveditz for drivers
Attachment #227711 - Flags: approval1.8.0.5+
(Assignee)

Comment 20

11 years ago
Created attachment 227749 [details] [diff] [review]
Minimal fix

Here is a minimal patch without IndexToId optimization.
Attachment #227711 - Attachment is obsolete: true
Attachment #227749 - Flags: superreview?(brendan)
Attachment #227749 - Flags: review?(mrbkap)
(Assignee)

Comment 21

11 years ago
Note that I go to a vacation on Sanday so effectively I have only Saturday for commits. Thus at best I can land the patch on trunk and redo the version against 1.8.* branch.

Updated

11 years ago
Attachment #227749 - Flags: review?(mrbkap) → review+
Comment on attachment 227749 [details] [diff] [review]
Minimal fix

+                 * Find id2 after OBJ_GET_PROPERTY call as it can invalidate
+                 * ids for large indexes. See bug 341956.

It would be nice to compress this to a one-line comment.  How about

/* Get id after value to avoid nested GC hazards. */

or something like that?

sr=me anyway.

/be
Attachment #227749 - Flags: superreview?(brendan) → superreview+
(Assignee)

Comment 23

11 years ago
Created attachment 227818 [details] [diff] [review]
Minimal fix (patch to commit with shrinked comments)

The patch with reduced comments as Brendan suggested.

I could commit it but according to http://tinderbox.mozilla.org/showbuilds.cgi?tree=Firefox the tree is red due failing build on Mac. Shall I ignore it?
Attachment #227749 - Attachment is obsolete: true
(Assignee)

Comment 24

11 years ago
Created attachment 227820 [details] [diff] [review]
Minimal fix - version for 1.8.0 and 1.8.1 branches

This is a version for 1.8.* branches.
Attachment #227820 - Flags: approval1.8.1?
Attachment #227820 - Flags: approval1.8.0.5?
I asked on irc.mozilla.org #developers, since that channel is "sheriff".  preed said "I think 02 just isn't set to build yet or something. It's taking half of the UB builds that 01 does."  The red balsa seamonkey-ports was due to a gcc bug.

The tree remains open, so I think you should check in.

/be
(Assignee)

Comment 26

11 years ago
I committed the patch from commnet 24 to the trunk.
Status: NEW → RESOLVED
Last Resolved: 11 years ago
Resolution: --- → FIXED
(Assignee)

Comment 27

11 years ago
Please note that until 2006-07-25 I would not be able to commit anything - vacation time.
Comment on attachment 227820 [details] [diff] [review]
Minimal fix - version for 1.8.0 and 1.8.1 branches

a=dveditz for 1.8.0 branch
Attachment #227820 - Flags: approval1.8.0.5? → approval1.8.0.5+
Attachment #227711 - Flags: approval1.8.0.5+
Fix chcked into the 1.8.0 branch.
Keywords: fixed1.8.0.5

Updated

11 years ago
Attachment #227820 - Flags: approval1.8.1? → approval1.8.1+
Flags: blocking1.8.0.5? → blocking1.8.0.5+

Comment 30

11 years ago
Created attachment 228293 [details]
js1_5/GC/regress-341956.js

Updated

11 years ago
Flags: in-testsuite+
(Assignee)

Comment 31

11 years ago
Comment on attachment 228293 [details]
js1_5/GC/regress-341956.js

Note that the test can check that good === true for booletproof checking. Plus it just covers unshift case, but what about the examples for reverse and pop?

Comment 32

11 years ago
Created attachment 228332 [details]
js1_5/GC/regress-341956-01.js

Sorry, I missed that.
Attachment #228293 - Attachment is obsolete: true

Comment 33

11 years ago
Created attachment 228333 [details]
js1_5/GC/regress-341956-02.js

Comment 34

11 years ago
Created attachment 228334 [details]
js1_5/GC/regress-341956-03.js

Updated

11 years ago
Flags: blocking1.8.1? → blocking1.8.1+
Target Milestone: --- → mozilla1.8.1beta1

Updated

11 years ago
Keywords: fixed1.8.1

Comment 35

11 years ago
Tested with the original test version. 
verified fixed 1.8.0.5, 1.9a1 windows/macppc/linux 20060706 builds.

Not Fixed in 1.8.1 20060706. Crashes shell windows, browser windows/macppc/linux.

confirmed that windows browser crashes on all of the new tests 01, 02, and 03 in opt but not debug builds and windows shell crashes on all the new tests for opt and debug.
Status: RESOLVED → VERIFIED
Keywords: fixed1.8.0.5, fixed1.8.1 → verified1.8.0.5

Updated

11 years ago
Target Milestone: mozilla1.8.1beta1 → mozilla1.8.1beta2

Updated

11 years ago
Blocks: 344320

Comment 36

11 years ago
I can't reproduce my crashes on 1.8.1 windows xp in the shell or browser with or without dep enabled using a 2006070707 build. After the qa farm comes back on line tomorrow, I'll rebuild and retest.
Whiteboard: [sg:critical]
Not sure if this problem applies to the aviary/1.7 branch or not.
Flags: blocking1.7.14?
Flags: blocking-aviary1.0.9?
(Assignee)

Comment 38

11 years ago
(In reply to comment #37)
> Not sure if this problem applies to the aviary/1.7 branch or not.
> 

Yes, it does.

Comment 39

11 years ago
no longer crash in 1.8.1
verified fixed 1.8.1 win/mac(tel|ppc)/linux
Keywords: verified1.8.1

Comment 40

11 years ago
Created attachment 232727 [details] [diff] [review]
1.0.x backport

maybe incomplete .. though I hope not.
Group: security

Comment 41

10 years ago
/cvsroot/mozilla/js/tests/js1_5/extensions/regress-341956-01.js,v  <--  regress-341956-01.js

/cvsroot/mozilla/js/tests/js1_5/extensions/regress-341956-02.js,v  <--  regress-341956-02.js

/cvsroot/mozilla/js/tests/js1_5/extensions/regress-341956-03.js,v  <--  regress-341956-03.js
You need to log in before you can comment on or make changes to this bug.