324117 - GC hazard during namespace scanning

Status: VERIFIED FIXED

(Core :: JavaScript Engine, defect)

Description

[Igor Bukanov]

DeutschSchorrWaite from gc.c which used to GC during low stack condition does not scan xml-related objects for their GC things. In particular, it contains the following code in lines 1425 - 1435:

            if (JSVAL_IS_OBJECT(v)) {
                *vp = JSVAL_SETTAG(top, JSVAL_BOOLEAN);
                top = parent;
                if (scope)
                    scope->dswIndex = EncodeDSWIndex(vp, obj->slots);
                goto down;
            }

            /* Handle string and double GC-things. */
            MARK_GC_THING(cx, thing, flagp, NULL);

where goto down caused interpreting v as normal object and scanning only its obj->slots. Since JSVAL_IS_OBJECT returns true for xml objects, xml-specific scanning is ignored. Here is a test case for js-shell to demonstrate the problem:

function prepare(N) 
{
	var xml = <xml/>;
	for (var i = 0; i != 2; ++i) {
        	var ns = new Namespace(""+i);  
		ns.property = {a:1};
        	xml.addNamespace(ns);
	}

	// Prepare list to trigger DeutschSchorrWaite call during GC
	cursor = xml;
	for (var i = 0; i != N; ++i) {
		if (i % 2 == 0) 
			cursor = [ {a: 1}, cursor ];
		else 
			cursor = [ cursor, {a: 1} ];
	}
	return cursor;
}

function check(list, N)
{
	// Extract xml to verify
	for (var i = N; i != 0; --i) {
		list = list[i % 2];
	}
	var xml = list;
	if (typeof xml != "xml")
		return false;
	var array = xml.inScopeNamespaces();
	if (array.length !== 3)
		return false;
	if ('property' in array[0])
		return false;
	if (array[1].property.a !== 1)
		return false;
	if (array[2].property.a !== 1)
		return false;

	return true;
}

var N = 2000;
var list = prepare(N);
gc();
var ok = check(list, N);
print(ok);


When run in the debug build js shell with stack limit set to 100K, it generates segfault:

~/w/js/mozilla/js/src> js -S 102400 test.js
before 40122, after 39915, break 0993a000
Segmentation fault

Since this bug can be used to subvert type of GC references from the script, a script can use this to trigger arbitrary code execution using approach described in https://bugzilla.mozilla.org/show_bug.cgi?id=311497#c10.

Comment 1

[Igor Bukanov]

This bug MAY caused problem in from bug 323153 and from bug 280844 comment 32

Comment 2

[Igor Bukanov]

I was wrong about the nature of the bug. Of cause in the code in DeutschSchorrWaite is correct as at that place only objects can be found. The problem is that namespace objects somehow are not properly accounted for.

Comment 3

[Igor Bukanov]

Even simpler testcase:

function prepare(N) 
{
	var xml = <xml/>;
	var ns1 = new Namespace("text1");  
	var ns2 = new Namespace("text2");  
	xml.addNamespace(ns1);
	xml.addNamespace(ns2);

	// Prepare list to trigger DeutschSchorrWaite call during GC
	cursor = xml;
	for (var i = 0; i != N; ++i) {
		if (i % 2 == 0) 
			cursor = [ {a: 1}, cursor ];
		else 
			cursor = [ cursor, {a: 1} ];
	}
	return cursor;
}

function check(list, N)
{
	// Extract xml to verify
	for (var i = N; i != 0; --i) {
		list = list[i % 2];
	}
	var xml = list;
	if (typeof xml != "xml")
		return false;
	var array = xml.inScopeNamespaces();
	if (array.length !== 3)
		return false;
	if (array[0].uri !== "")
		return false;
	if (array[1].uri !== "text1")
		return false;
	if (array[2].uri !== "text2")
		return false;

	return true;
}

var N = 2000;
var list = prepare(N);
gc();
var ok = check(list, N);
print(ok);

~/w/js/mozilla/js/src> js -S 102400 test.js
before 40104, after 39915, break 09701000
Segmentation fault

Comment 4

[Blake Kaplan (:mrbkap) (inactive)]

This sounds like it could be the cause of bug 290020.

Comment 5

[Bob Clary [:bc] (inactive)]

Attachment: e4x/Regress/regress-324117.js

Comment 6

[Igor Bukanov]

Some clarifications:

when I run the test case from comment #3 with the debug build of JS shell with a restricted stack like in:


js -S 100000 test.js

I get:

JS_Assert (
    s=0x80fbe30 "(uint32)2 < JS_MIN(((obj)->map)->freeslot, ((obj)->map)->nslots)", file=0x80fbd0c "jsapi.c", ln=2165) at jsutil.c:62
62          abort();

with the following stack trace:
#0  JS_Assert (
    s=0x80fbe30 "(uint32)2 < JS_MIN(((obj)->map)->freeslot, ((obj)->map)->nslots)", file=0x80fbd0c "jsapi.c", ln=2165) at jsutil.c:62
#1  0x08051bf1 in JS_GetPrivate (cx=0x81178c8, obj=0x8130040) at jsapi.c:2165
#2  0x080e47ee in js_GetXMLNamespaceObject (cx=0x81178c8, ns=0x8130060)
    at jsxml.c:340
#3  0x080f2f25 in xml_inScopeNamespaces (cx=0x81178c8, obj=0x8119778, argc=0, 
    argv=0x812ddb8, rval=0xbf8ec32c) at jsxml.c:6006
#4  0x080870f0 in js_Invoke (cx=0x81178c8, argc=0, flags=0) at jsinterp.c:1246
#5  0x08098541 in js_Interpret (cx=0x81178c8, pc=0x812db40 ":", 
    result=0xbf8eccd8) at jsinterp.c:3884
#6  0x080879a1 in js_Execute (cx=0x81178c8, chain=0x8118e18, script=0x812dc20, 
    down=0x0, flags=0, result=0xbf8edda4) at jsinterp.c:1496
#7  0x080558e5 in JS_ExecuteScript (cx=0x81178c8, obj=0x8118e18, 
    script=0x812dc20, rval=0xbf8edda4) at jsapi.c:4026
#8  0x080495b7 in Process (cx=0x81178c8, obj=0x8118e18, 
    filename=0xbf8efb70 "/home/igor/s/x.js", forceTTY=0) at js.c:224
#9  0x08049db2 in ProcessArgs (cx=0x81178c8, obj=0x8118e18, argv=0xbf8edf18, 
    argc=3) at js.c:477
#10 0x0804cf5c in main (argc=3, argv=0xbf8edf18, envp=0xbf8edf28) at js.c:2614

When I run the test without stack restrictions, it terminates succesfully:

~> js test.js
before 39618, after 39483, break 081ba000
true

That means that the bug is really in xml_DeutschSchorrWaite that most likely does not mark all that it should. So either this has to be fixed or the last patch from bug 324278 should be considered as it removes xml_DeutschSchorrWaite solving the problem.

Comment 7

[Bob Clary [:bc] (inactive)]

no longer crashes in trunk 20060401 win/mac/linux builds. Assuming fixed by bug 324278 as well.

Comment 8

[Igor Bukanov]

This bug can be rather bad if it really GC the live things. While the patch from bug 324278 fixed it, I guess it is out of question to have the patch on branches. So something has to be done about this bug for 1.8*

Comment 9

[Bob Clary [:bc] (inactive)]

ok, reopening, moving to 1.8 and setting some flags to keep on the radar.

Comment 10

[Daniel Veditz [:dveditz]]

No activity, a 1.8.0.4 fix by Monday is extremely unrealistic. Given the scope of the patch in bug 324278 is a safe 1.8.0 fix even possible?

Comment 11

[Brendan Eich [:brendan]]

At some point, yes.  Not for 1.5.0.4.

To decide, someone should take an independent look at the patch -- how easily will it merge onto the 1.8.0 branch?  Were there regressions from its initial landing, any followup patches?  I don't remember, so I'm not saying there were.  I don't have time to look into this before June.

/be

Comment 12

[Igor Bukanov]

Besides finding out what causes the crash, there is another trivial way to fix the bug for branches: one just disables DeutschSchorrWaite in jsxml.c.

Given the recursion checks in XML parser, it is hard to see how one can accidentally build XML structs that overflow the stack during GC. On the other if one wants to cause stack overflow deliberately, then xml_DeutschSchorrWaite does not help as examples in bug 324278 demonstrates and real bug reports from bug  	323252 shows. 

Comment 13

[Igor Bukanov]

Attachment: "Fix"

Patch for branches to remove xml_DeutschSchorrWaite assuming the stack overflow that happens in any case without trunk-only changes from bug 324278 is better then botched heap.

Comment 14

[Igor Bukanov]

Attachment: diff -b version of "Fix"

Comment 15

[Daniel Veditz [:dveditz]]

Comment on attachment 225425 [details] [diff] [review]
"Fix"

approved for 1.8.0 branch, a=dveditz for drivers

Comment 16

[Igor Bukanov]

I committed the patch from comment 13 to MOZILLA_1_8_BRANCH

Comment 17

[Igor Bukanov]

I committed the patch from comment 13 to MOZILLA_1_8_0_BRANCH

Comment 18

[Bob Clary [:bc] (inactive)]

I crash during the browser test in all branches and platforms both opt and debug but can't get a stack. Be sure to install venkman to get the jsd GC call. 

Comment 19

[Igor Bukanov]

(In reply to comment #18)
> I crash during the browser test in all branches and platforms both opt and
> debug but can't get a stack. Be sure to install venkman to get the jsd GC call. 
> 

Do you mean you see crashes on branches but not on the trunk with the test cases? If so, then this is expected if the crashes are stack oveflows. The testcases show that it is not possible to have a self contained Deutsch-Schorr-Waite algorithm for XML objects to prevent infinite recursion in the engine. One need a global solution like one implemented on trunk, see bug 324278. 

The problem was that Deutsch-Schorr-Waite for XML itself contained a bug so that code was removed for the price of stack overflows with deliberately constructed XML. That is in my opinion a better solution then having GC hazard. On any sane platform that would run Firefox a stack overflow is just a denial-of-service not worse then for (;;) alert(); 

Comment 20

[Bob Clary [:bc] (inactive)]

I meant crashes 1.8 branches and trunk.

Comment 21

[Bob Clary [:bc] (inactive)]

stack on winxp trunk:

 	js3250.dll!js_SearchScope(JSScope * scope=0x05fb1c58, long id=0x020f2b18, int adding=0x00000000)  Line 254 + 0x19 bytes	C

 	js3250.dll!js_Mark(JSContext * cx=0x00fb4d68, JSObject * obj=0x05faf040, void * arg=0x00000000)  Line 4522 + 0x1d bytes	C

>	js3250.dll!MarkGCThingChildren(JSContext * cx=0x00fb4d68, void * thing=0x05faf040, unsigned char * flagp=0x05faeff8, int shouldCheckRecursion=0x00000001)  Line 1627 + 0x25 bytes	C

 	js3250.dll!MarkGCThingChildren(JSContext * cx=0x00fb4d68, void * thing=0x05faf040, unsigned char * flagp=0x05faeff8, int shouldCheckRecursion=0x00000001)  Line 1649 + 0x13 bytes	C

with the last frame repeated.

Comment 22

[Bob Clary [:bc] (inactive)]

setting a conditional breakpoint in for cx->stackLimit == 0

>	js3250.dll!MarkGCThingChildren(JSContext * cx=0x00fb4d68, void * thing=0x03c9cd70, unsigned char * flagp=0x03c9dc96, int shouldCheckRecursion=0x00000001)  Line 1593	C
 	js3250.dll!js_MarkGCThing(JSContext * cx=0x00fb4d68, void * thing=0x03c9cd70)  Line 2008 + 0x13 bytes	C
 	js3250.dll!gc_root_marker(JSDHashTable * table=0x00fb0094, JSDHashEntryHdr * hdr=0x03f1b040, unsigned long num=0x00000000, void * arg=0x00fb4d68)  Line 2072 + 0x10 bytes	C
 	js3250.dll!JS_DHashTableEnumerate(JSDHashTable * table=0x00fb0094, JSDHashOperator (JSDHashTable *, JSDHashEntryHdr *, unsigned long, void *)* etor=0x0046d580, void * arg=0x00fb4d68)  Line 674 + 0x19 bytes	C
 	js3250.dll!js_GC(JSContext * cx=0x00fb4d68, unsigned int gcflags=0x00000000)  Line 2378 + 0x15 bytes	C
 	js3250.dll!js_ForceGC(JSContext * cx=0x00fb4d68, unsigned int gcflags=0x00000000)  Line 2098 + 0xd bytes	C
 	js3250.dll!JS_GC(JSContext * cx=0x00fb4d68)  Line 1907 + 0xb bytes	C
 	jsd3250.dll!jsdService::GC()  Line 2722 + 0xa bytes	C++

Comment 23

[Bob Clary [:bc] (inactive)]

full stack

>	js3250.dll!MarkGCThingChildren(JSContext * cx=0x03c3d988, void * thing=0x043184a8, unsigned char * flagp=0x04318395, int shouldCheckRecursion=0x00000001)  Line 1593	C
 	js3250.dll!js_MarkGCThing(JSContext * cx=0x03c3d988, void * thing=0x043184a8)  Line 2008 + 0x13 bytes	C
 	js3250.dll!gc_root_marker(JSDHashTable * table=0x00fc7824, JSDHashEntryHdr * hdr=0x04938d50, unsigned long num=0x00000000, void * arg=0x03c3d988)  Line 2072 + 0x10 bytes	C
 	js3250.dll!JS_DHashTableEnumerate(JSDHashTable * table=0x00fc7824, JSDHashOperator (JSDHashTable *, JSDHashEntryHdr *, unsigned long, void *)* etor=0x0046d580, void * arg=0x03c3d988)  Line 674 + 0x19 bytes	C
 	js3250.dll!js_GC(JSContext * cx=0x03c3d988, unsigned int gcflags=0x00000000)  Line 2378 + 0x15 bytes	C
 	js3250.dll!js_ForceGC(JSContext * cx=0x03c3d988, unsigned int gcflags=0x00000000)  Line 2098 + 0xd bytes	C
 	js3250.dll!JS_GC(JSContext * cx=0x03c3d988)  Line 1907 + 0xb bytes	C
 	jsd3250.dll!jsdService::GC()  Line 2722 + 0xa bytes	C++
 	xpcom_core.dll!XPTC_InvokeByIndex(nsISupports * that=0x00000024, unsigned int methodIndex=0x00000000, unsigned int paramCount=0x0012e9c8, nsXPTCVariant * params=0x00fce37c)  Line 102	C++
 	xpc3250.dll!XPCWrappedNative::CallMethod(XPCCallContext & ccx={...}, XPCWrappedNative::CallMode mode=0x00000024)  Line 2154 + 0x1e bytes	C++
 	xpc3250.dll!XPCWrappedNative::CallMethod(XPCCallContext & ccx={...}, XPCWrappedNative::CallMode mode=CALL_METHOD)  Line 2154 + 0x1e bytes	C++
 	xpc3250.dll!XPC_WN_CallMethod(JSContext * cx=0x046162f8, JSObject * obj=0x07a704c0, unsigned int argc=0x00000000, long * argv=0x04ef8e74, long * vp=0x0012ec94)  Line 1450 + 0xe bytes	C++
 	js3250.dll!js_Invoke(JSContext * cx=0x046162f8, unsigned int argc=0x00000000, unsigned int flags=0x00000000)  Line 1328 + 0x20 bytes	C
 	js3250.dll!js_Interpret(JSContext * cx=0x046162f8, unsigned char * pc=0x04f03098, long * result=0x0012f730)  Line 4021 + 0xf bytes	C
 	js3250.dll!js_Execute(JSContext * cx=0x046162f8, JSObject * chain=0x04d320e0, JSScript * script=0x04ef8aa0, JSStackFrame * down=0x00000000, unsigned int flags=0x00000000, long * result=0x0012f85c)  Line 1573 + 0x13 bytes	C
 	js3250.dll!JS_EvaluateUCScriptForPrincipals(JSContext * cx=0x046162f8, JSObject * obj=0x04d320e0, JSPrincipals * principals=0x03c71454, const unsigned short * chars=0x04f03320, unsigned int length=0x00000be9, const char * filename=0x04eff910, unsigned int lineno=0x00000001, long * rval=0x0012f85c)  Line 4293 + 0x19 bytes	C
 	gklayout.dll!nsJSContext::EvaluateString(const nsAString_internal & aScript={...}, void * aScopeObject=0x04d320e0, nsIPrincipal * aPrincipal=0x03c71450, const char * aURL=0x04eff910, unsigned int aLineNo=0x00000001, unsigned int aVersion=0x00001000, nsAString_internal * aRetValue=0x00000000, int * aIsUndefined=0x0012f950)  Line 1247 + 0x43 bytes	C++
 	gklayout.dll!nsScriptLoader::EvaluateScript(nsScriptLoadRequest * aRequest=0x04effc68, const nsString & aScript={...})  Line 800 + 0x63 bytes	C++
 	gklayout.dll!nsScriptLoader::ProcessRequest(nsScriptLoadRequest * aRequest=0x04effc68)  Line 704 + 0x13 bytes	C++
 	gklayout.dll!nsScriptLoader::OnStreamComplete(nsIStreamLoader * aLoader=0x04eee3f8, nsISupports * aContext=0x04effc68, unsigned int aStatus=0x00000000, unsigned int stringLen=0x00000be9, const unsigned char * string=0x04ef0010)  Line 1065	C++
 	necko.dll!nsStreamLoader::OnStopRequest(nsIRequest * request=0x04eee038, nsISupports * ctxt=0x04effc68, unsigned int aStatus=0x00000000)  Line 117	C++
 	necko.dll!nsHttpChannel::OnStopRequest(nsIRequest * request=0x048985b8, nsISupports * ctxt=0x04effc68, unsigned int status=0x00000000)  Line 4053	C++
 	necko.dll!nsInputStreamPump::OnStateStop()  Line 567	C++
 	necko.dll!nsInputStreamPump::OnInputStreamReady(nsIAsyncInputStream * stream=0x04f00508)  Line 391 + 0xb bytes	C++
 	xpcom_core.dll!nsInputStreamReadyEvent::Run()  Line 112	C++
 	xpcom_core.dll!nsThread::ProcessNextEvent(int mayWait=0x00000001, int * result=0x0012fc34)  Line 483	C++
 	xpcom_core.dll!NS_ProcessNextEvent_P(nsIThread * thread=0x00b08ee8, int mayWait=0x00000001)  Line 225 + 0x16 bytes	C++
 	gkwidget.dll!nsBaseAppShell::Run()  Line 153 + 0xc bytes	C++
 	tkitcmps.dll!nsAppStartup::Run()  Line 171 + 0x1c bytes	C++
 	xul.dll!XRE_main(int argc=0x00000003, char * * argv=0x00b08180, const nsXREAppData * aAppData=0x004036b0)  Line 2349 + 0x25 bytes	C++
 	firefox.exe!main(int argc=0x00000003, char * * argv=0x00b08180)  Line 61 + 0x13 bytes	C++
 	firefox.exe!__tmainCRTStartup()  Line 586 + 0x19 bytes	C
 	firefox.exe!mainCRTStartup()  Line 403	C
 	kernel32.dll!_BaseProcessStart@4()  + 0x23 bytes	

Comment 24

[Bob Clary [:bc] (inactive)]

My crashes are probably bug 342737 due to use of jsd's GC. Disabling jsd does not crash windows 1.8.0.5, 1.8.1, 1.9a1 debug builds. I'll retest this evening, but verifying until then.

Comment 25

[Bob Clary [:bc] (inactive)]

/cvsroot/mozilla/js/tests/e4x/GC/regress-324117.js,v  <--  regress-324117.js