313276 - Unrooted strings in jsstr.c

Status: VERIFIED FIXED

(Core :: JavaScript Engine, defect, P1)

Description

[Igor Bukanov]

The following functions in jsstr.c do not root the results of js_ValueToString
before calling GC-triggering operations:

str_substring
str_decodeURI
str_decodeURI_Component
str_encodeURI
str_encodeURI_Component

The encode/decode cases is only exploitable if one can create a situation when
GC is triggered in js_NewString that is called later in Decode/Encode after the
return from js_ValueToString. 

The case of str_substring is trivially exploitable to read arbitrary region in
address space via JSString->double subversion like the following example
demonstrates:

obj = {
	toString: function() {
		return "*TEST*".substr(1, 4);
	}
};

var TMP = 1e200;

likeZero = {
	valueOf: function() {
		if (typeof gc == "function") gc();
		for (var i = 0; i != 40000; ++i) {
			var tmp = 2 / TMP;
			tmp = null;
		}
		return 0;	
	}
}

var expected = "TEST";
var actual = String.prototype.substr.call(obj, likeZero);

print("Substring length: "+actual.length);
print(expected === actual);

On my box executing it gives in js shell:
 
before 3690, after 3654, break 08a40000
Substring length: 357496748
Segmentation fault

where 357496748 comes from 1e-200 interpreted as JSString.

Comment 1

[Asa Dotzler [:asa]]

->brendan. 

Comment 2

[Brendan Eich [:brendan]]

Asa: I'm relying on mrbkap (thanks and praise to him) for fixing.  This may not
be fair (hey, I didn't write str_decodeURI, str_decodeURI_Component,
str_encodeURI, or str_encodeURI_Component -- mccabe or rogerl did), but that's
life.  I am to blame for the lack of automatic local roots.

FYI for future reassigning.

/be

Comment 3

[Blake Kaplan (:mrbkap) (inactive)]

This goes back to brendan. Thanks!

Comment 4

[Igor Bukanov]

str_resolve and str_enumerate in jsstr.c also do not root results of
js_ValueToString which bring them to the same company where str_decodeURL etc.
are. That is, they are exploitable only if js_NewDependentString that follows
js_ValueToString would cause GC.

Comment 5

[Brendan Eich [:brendan]]

(In reply to comment #4)
> str_resolve and str_enumerate in jsstr.c also do not root results of
> js_ValueToString which bring them to the same company where str_decodeURL etc.
> are. That is, they are exploitable only if js_NewDependentString that follows
> js_ValueToString would cause GC.

These are ok.

First, it would be the OBJ_DEFINE_PROPERTY, or some later operation that might GC, that would cause the js_ValueToString(cx, OBJECT_TO_JSVAL(obj)) result to be collected, if it had no other strong refs.  This is because that result is protected by the newborn string across the js_NewDependentString call, even though that call may overwrite that newborn (if both strings are the same GCX_* type).

Second, in these cases (str_resolve and str_enumerate), js_NewDependentString creates a rooted new string that strongly refs its base string, the result of the js_ValueToString.  So the chain of refs from newborn for dependent, through dependent base, keeps the first string alive.  Once the property value being defined is committed, the dependent is protected by more than *its* newborn.

/be

Comment 6

[Brendan Eich [:brendan]]

str_substring uses the argv[-1] explicit local root to protect the result of its js_ValueToString(cx, OBJECT_TO_JSVAL(obj)), so it is ok.

There are a number of other bad native methods than the Edition 3 encode/decode URi ones, however.  Patch anon.

/be

Comment 7

[Brendan Eich [:brendan]]

Attachment: simple use of explicit local roots

per http://www.mozilla.org/js/spidermonkey/gctips.html -- sigh.  Fragile model that is easy to forget to use.  We will put it to rest on the trunk shortly.  This is good for 1.8.  mrbkap feel free to review as well.

/be

Comment 8

[Bob Clary [:bc] (inactive)]

Attachment: ecma_3/String/regress-313276.js

Comment 9

[Igor Bukanov]

(In reply to comment #5)
> These are ok.

Counter example:

var prepared_string = String(1);
String(2); // to remove prepared_string from newborn

var strObj = new String("");
strObj.toString  = function() {
	var tmp = prepared_string;
	prepared_string = null;
	return tmp;
}

var not_one_count = 0;
for each (var s in strObj) { 
	if (s !== '1') 
	        ++not_one_count;
}

print("not_one_count="+not_one_count);

If I recompile js shell with TOO_MUCH_GC defined, its execution instead of printing expected 1 coming from "toString" property, produces on my box:

Assertion failure: flags != GCF_FINAL, at jsgc.c:1040
Trace/breakpoint trap

Comment 10

[Igor Bukanov]

Comment on attachment 200481 [details] [diff] [review]
simple use of explicit local roots

The patch does not solve all the problems per comment 9 :(

Comment 11

[Brendan Eich [:brendan]]

Comment on attachment 200481 [details] [diff] [review]
simple use of explicit local roots

This patch is correct, but insufficient.  The str_enumerate and str_resolve problems Igor points out (old-borns cut off from the live thing graph) remain.  New patch to fix those in addition, I hope.

/be

Comment 12

[Brendan Eich [:brendan]]

Attachment: first patch plus newborn root hacking in str_enumerate and str_resolve

The alternative is the cx->lastInvokeResult root Igor proposed, which we were trying not to take for 1.8/fx1.5 for fear of entrainment problems, and assuming we can spot-fix problems more safely.  Not clear that is a good assumption, but here are two more spot (hack) fixes, plus the saner explicit local root fixes from the first patch.

/be

Comment 13

[Igor Bukanov]

With the patch applied only the following functions in jsstr.c contain calls to ValueToString without immediate rooting of the result:

str_getProperty -- this is safe
str_localeCompare -- safe if cx->localeCallbacks->localeCompare safe
match_or_replace -- need some time to check
find_replen      -- need some time to check

But perhaps it is better to add explicit rooting in all the places just to make sure?

Comment 14

[Igor Bukanov]

Unrelated to the bug curiosity question: why str_getProperty, str_enumerate and str_resolve use ValueToString and not simply OBJ_GET_SLOT(cx, obj, JSSLOT_PRIVATE) like str_valueOf and str_toString do?

Comment 15

[Brendan Eich [:brendan]]

I fixed str_localeCompare to root thatStr using argv[0] -- thanks.

(In reply to comment #14)
> Unrelated to the bug curiosity question: why str_getProperty, str_enumerate and
> str_resolve use ValueToString and not simply OBJ_GET_SLOT(cx, obj,
> JSSLOT_PRIVATE) like str_valueOf and str_toString do?

Good question.  Only the getter (and a setter, if there were one) needs to be generic:

s = new String('hello');
o = {__proto__: s};
print(o[0]);

You can inspect the engine for resolve/newresolve and enumerate calls and show that their obj param is guaranteed to be of the class whose hook is being called -- not so with getters and setters.

Thanks, an even better patch coming up.

/be

Comment 16

[Brendan Eich [:brendan]]

Attachment: best patch yet, hope this is it for jsstr.c

Comment 17

[Igor Bukanov]

Comment on attachment 200524 [details] [diff] [review]
first patch plus newborn root hacking in str_enumerate and str_resolve

If remaining cases turned out to be problematic, I will report them as a separated bug.

Comment 18

[Brendan Eich [:brendan]]

Comment on attachment 200524 [details] [diff] [review]
first patch plus newborn root hacking in str_enumerate and str_resolve

Igor, if you are convinced the next patch is better, please r+ it and I'll check it into the trunk.  Thanks,

/be

Comment 19

[Igor Bukanov]

Comment on attachment 200552 [details] [diff] [review]
best patch yet, hope this is it for jsstr.c

Yes, this is better :)

Although IMO even for getProperty for consistency it would be better to get length from the string from the private slot of the right string, this is unrelated 100% to this bug.

Comment 20

[Mike Shaver (:shaver emeritus)]

Comment on attachment 200552 [details] [diff] [review]
best patch yet, hope this is it for jsstr.c

sr=shaver

Comment 21

[Brendan Eich [:brendan]]

(In reply to comment #19)
> (From update of attachment 200552 [details] [diff] [review] [edit])
> Yes, this is better :)
> 
> Although IMO even for getProperty for consistency it would be better to get
> length from the string from the private slot of the right string, this is
> unrelated 100% to this bug.

ECMA-262 makes most string and array methods generic, so any object can use 'em (via Function.prototype.call/.apply, or in SpiderMonkey now via generic static methods of the same name, e.g. String.slice).  So str_getProperty does likewise and converts from object to string.

Fixed on trunk.

/be

Comment 22

[Brendan Eich [:brendan]]

Comment on attachment 200552 [details] [diff] [review]
best patch yet, hope this is it for jsstr.c

Time is running out for tonight.

/be

Comment 23

[Daniel Veditz [:dveditz]]

Comment on attachment 200552 [details] [diff] [review]
best patch yet, hope this is it for jsstr.c

a=dveditz

Comment 24

[Brendan Eich [:brendan]]

Fixed on branch and trunk.

/be

Comment 25

[Brendan Eich [:brendan]]

This fix caused bug 313565.

/be

Comment 26

[Igor Bukanov]

Comment on attachment 200552 [details] [diff] [review]
best patch yet, hope this is it for jsstr.c

>@@ -543,19 +550,20 @@ str_enumerate(JSContext *cx, JSObject *o
...
>-    str = js_ValueToString(cx, OBJECT_TO_JSVAL(obj));
>+    str = (JSString *) JS_GetPrivate(cx, obj);
...
>@@ -570,19 +578,20 @@ str_resolve(JSContext *cx, JSObject *obj
>             JSObject **objp)
> {
...
>-    str = js_ValueToString(cx, OBJECT_TO_JSVAL(obj));
>+    str = (JSString *) JS_GetPrivate(cx, obj);

Note that this is a change in functinality if someone relied on the ability to redefine String object "string" value. But why would anybody want this?

Comment 27

[Brendan Eich [:brendan]]

(In reply to comment #26)
> (From update of attachment 200552 [details] [diff] [review] [edit])
> >@@ -543,19 +550,20 @@ str_enumerate(JSContext *cx, JSObject *o
> ...
> >-    str = js_ValueToString(cx, OBJECT_TO_JSVAL(obj));
> >+    str = (JSString *) JS_GetPrivate(cx, obj);
> ...
> >@@ -570,19 +578,20 @@ str_resolve(JSContext *cx, JSObject *obj
> >             JSObject **objp)
> > {
> ...
> >-    str = js_ValueToString(cx, OBJECT_TO_JSVAL(obj));
> >+    str = (JSString *) JS_GetPrivate(cx, obj);

First, this was just totally broken: JS_GetPrivate returns null for any private data slot value that's not int-tagged.  OBJ_GET_SLOT(cx, obj, JSSLOT_PRIVATE) and then JSVAL_TO_STRING if not JSVAL_VOID would be required.

> Note that this is a change in functinality if someone relied on the ability to
> redefine String object "string" value. But why would anybody want this?

I don't think any Firefox code does, based on some debugging code I've added.  But who knows?  Compatibility is king.  I don't think we can change this.  At least, not right not for Mozilla1.8/Firefox1.5/JS1.6.

/be

Comment 28

[Brendan Eich [:brendan]]

Let's take this resolve/enumerate js_ValueToString issue up in the followup bug Igor filed, bug 313567.

/be

Comment 29

[Bob Clary [:bc] (inactive)]

on winxp

1.8b5_2005102412:  ecma_3/String/regress-313276.js failed, 
Expected exit code 0, got 3

STATUS: Root strings
before 5346, after 5283, break 00000000
STATUS: Substring length: 4
./ecma_3/shell.js:101: TypeError: msg.split is not a function 

1.9a1_2005102413: crashed.

Comment 30

[Bob Clary [:bc] (inactive)]

(In reply to comment #29)
The failure in the testcase on branch is bug in the testcase line 69 where it passes a boolean to the printStatus function.

After repulling and rebuilding the shell, I can not reproduce the crash.

Sorry for the false alarm.

Comment 31

[Blake Kaplan (:mrbkap) (inactive)]

Fix checked into 1.7 branch.

Comment 32

[Bob Clary [:bc] (inactive)]

v ff on 1.7.13, 1.8.0.1, 1.8, 1.9a1 on windows/linux/mac 20060221 builds, moz on 1.7.13 on windows 20060221 builds.

Comment 33

[Bob Clary [:bc] (inactive)]

RCS file: /cvsroot/mozilla/js/tests/js1_5/GC/regress-313276.js,v
done
Checking in regress-313276.js;
/cvsroot/mozilla/js/tests/js1_5/GC/regress-313276.js,v  <--  regress-313276.js
initial revision: 1.1
done