Last Comment Bug 313276 - Unrooted strings in jsstr.c
: Unrooted strings in jsstr.c
Status: VERIFIED FIXED
[sg:critical?]
: js1.6, verified1.7.13, verified1.8
Product: Core
Classification: Components
Component: JavaScript Engine (show other bugs)
: Trunk
: All All
: P1 critical (vote)
: mozilla1.8rc1
Assigned To: Brendan Eich [:brendan]
:
:
Mentors:
Depends on:
Blocks:
  Show dependency treegraph
 
Reported: 2005-10-21 08:44 PDT by Igor Bukanov
Modified: 2011-08-05 21:34 PDT (History)
3 users (show)
dveditz: blocking1.7.13+
dveditz: blocking‑aviary1.0.8+
asa: blocking1.8rc1+
bob: in‑testsuite+
See Also:
Crash Signature:
(edit)
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---


Attachments
simple use of explicit local roots (5.63 KB, patch)
2005-10-22 22:22 PDT, Brendan Eich [:brendan]
no flags Details | Diff | Splinter Review
ecma_3/String/regress-313276.js (2.42 KB, text/plain)
2005-10-22 22:59 PDT, Bob Clary [:bc:]
no flags Details
first patch plus newborn root hacking in str_enumerate and str_resolve (7.03 KB, patch)
2005-10-23 11:03 PDT, Brendan Eich [:brendan]
igor: review+
Details | Diff | Splinter Review
best patch yet, hope this is it for jsstr.c (8.66 KB, patch)
2005-10-23 14:37 PDT, Brendan Eich [:brendan]
igor: review+
shaver: superreview+
dveditz: approval1.8rc1+
Details | Diff | Splinter Review

Description Igor Bukanov 2005-10-21 08:44:08 PDT
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] 2005-10-21 11:42:10 PDT
->brendan. 
Comment 2 Brendan Eich [:brendan] 2005-10-21 12:07:00 PDT
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) 2005-10-21 18:54:21 PDT
This goes back to brendan. Thanks!
Comment 4 Igor Bukanov 2005-10-22 08:30:06 PDT
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] 2005-10-22 22:08:50 PDT
(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] 2005-10-22 22:16:45 PDT
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] 2005-10-22 22:22:06 PDT
Created attachment 200481 [details] [diff] [review]
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:] 2005-10-22 22:59:34 PDT
Created attachment 200482 [details]
ecma_3/String/regress-313276.js
Comment 9 Igor Bukanov 2005-10-23 04:42:01 PDT
(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 2005-10-23 04:45:22 PDT
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] 2005-10-23 10:45:05 PDT
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] 2005-10-23 11:03:36 PDT
Created attachment 200524 [details] [diff] [review]
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 2005-10-23 13:37:47 PDT
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 2005-10-23 13:38:42 PDT
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] 2005-10-23 14:33:46 PDT
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] 2005-10-23 14:37:38 PDT
Created attachment 200552 [details] [diff] [review]
best patch yet, hope this is it for jsstr.c
Comment 17 Igor Bukanov 2005-10-23 14:37:52 PDT
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] 2005-10-23 14:40:37 PDT
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 2005-10-23 14:52:42 PDT
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 -- probably not reading bugmail closely) 2005-10-23 15:27:54 PDT
Comment on attachment 200552 [details] [diff] [review]
best patch yet, hope this is it for jsstr.c

sr=shaver
Comment 21 Brendan Eich [:brendan] 2005-10-23 19:52:12 PDT
(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] 2005-10-23 20:11:26 PDT
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] 2005-10-23 20:37:49 PDT
Comment on attachment 200552 [details] [diff] [review]
best patch yet, hope this is it for jsstr.c

a=dveditz
Comment 24 Brendan Eich [:brendan] 2005-10-23 21:06:29 PDT
Fixed on branch and trunk.

/be
Comment 25 Brendan Eich [:brendan] 2005-10-24 00:09:36 PDT
This fix caused bug 313565.

/be
Comment 26 Igor Bukanov 2005-10-24 00:17:28 PDT
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] 2005-10-24 00:35:06 PDT
(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] 2005-10-24 00:37:07 PDT
Let's take this resolve/enumerate js_ValueToString issue up in the followup bug Igor filed, bug 313567.

/be
Comment 29 Bob Clary [:bc:] 2005-10-25 00:03:58 PDT
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:] 2005-10-25 01:09:28 PDT
(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) 2006-02-14 18:28:18 PST
Fix checked into 1.7 branch.
Comment 32 Bob Clary [:bc:] 2006-02-22 02:49:56 PST
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:] 2006-06-14 16:57:55 PDT
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

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