Crash with large switch statement [@ js_Interpret]

VERIFIED FIXED

Status

()

defect
--
critical
VERIFIED FIXED
12 years ago
8 years ago

People

(Reporter: cbook, Assigned: igor)

Tracking

(4 keywords)

Trunk
Points:
---
Bug Flags:
blocking1.8.1.12 +
wanted1.8.1.x +
blocking1.8.0.next +
in-testsuite +
in-litmus -

Firefox Tracking Flags

(Not tracked)

Details

(Whiteboard: [sg:critical], crash signature, )

Attachments

(9 attachments, 5 obsolete attachments)

40.11 KB, text/html
Details
36.50 KB, text/html
Details
5.12 KB, patch
brendan
: review+
beltzner
: approvalM9+
brendan
: approval1.9+
Details | Diff | Splinter Review
38.18 KB, text/plain
Details
37.43 KB, text/plain
Details
5.14 KB, patch
igor
: review+
Details | Diff | Splinter Review
1.15 KB, text/plain
Details
5.30 KB, patch
igor
: review+
Details | Diff | Splinter Review
2.14 KB, patch
Details | Diff | Splinter Review
Mozilla/5.0 (Windows; U; Windows NT 5.2; en-US; rv:1.9a9pre) Gecko/2007092705 Minefield/3.0a9pre ID:2007092705 and latest 1.8 Nightly Crash when http://www.investors.com/newsResearchAnalysis.asp is loaded

http://crash-stats.mozilla.com/report/index/c621f76b-6f9a-11dc-b93c-001a4bd43ed6?date=2007-09-30-21

Stack of Crashing Thread
frame 	signature 	source
0 	js_Interpret 	mozilla/js/src/jsinterp.c:4515
1 	js_Execute 	mozilla/js/src/jsinterp.c:1622
2 	JS_EvaluateUCScriptForPrincipals 	mozilla/js/src/jsapi.c:4878
3 	nsJSContext::EvaluateString(nsAString_internal const&, void*, nsIPrincipal*, char const*, unsigned int, unsigned int, nsAString_internal*, int*) 	mozilla/dom/src/base/nsJSEnvironment.cpp:1389
4 	nsScriptLoader::EvaluateScript(nsScriptLoadRequest*, nsString const&) 	mozilla/content/base/src/nsScriptLoader.cpp:607
5 	nsScriptLoader::ProcessRequest(nsScriptLoadRequest*) 	mozilla/content/base/src/nsScriptLoader.cpp:521
6 	nsScriptLoader::ProcessScriptElement(nsIScriptElement*) 	mozilla/content/base/src/nsScriptLoader.cpp:486
7 	nsScriptElement::MaybeProcessScript() 	mozilla/content/base/src/nsScriptElement.cpp:188
8 	nsHTMLScriptElement::MaybeProcessScript() 	mozilla/content/html/content/src/nsHTMLScriptElement.cpp:536
9 	nsHTMLScriptElement::DoneAddingChildren(int) 	mozilla/content/html/content/src/nsHTMLScriptElement.cpp:482
10 	HTMLContentSink::ProcessSCRIPTEndTag(nsGenericHTMLElement*, int) 	mozilla/content/html/document/src/nsHTMLContentSink.cpp:3141
11 	SinkContext::CloseContainer(nsHTMLTag, int) 	mozilla/content/html/document/src/nsHTMLContentSink.cpp:1008
12 	HTMLContentSink::CloseContainer(nsHTMLTag) 	mozilla/content/html/document/src/nsHTMLContentSink.cpp:2406
13 	CNavDTD::CloseContainer(nsHTMLTag, int) 	mozilla/parser/htmlparser/src/CNavDTD.cpp:2686
14 	CNavDTD::HandleEndToken(CToken*) 	mozilla/parser/htmlparser/src/CNavDTD.cpp:1590
15 	CNavDTD::HandleToken(CToken*, nsIParser*) 	mozilla/parser/htmlparser/src/CNavDTD.cpp:705
16 	CNavDTD::BuildModel(nsIParser*, nsITokenizer*, nsITokenObserver*, nsIContentSink*) 	mozilla/parser/htmlparser/src/CNavDTD.cpp:331
17 	nsParser::BuildModel() 	mozilla/parser/htmlparser/src/nsParser.cpp:1717
18 	nsParser::ResumeParse(int, int, int) 	mozilla/parser/htmlparser/src/nsParser.cpp:1594
19 	nsParser::ContinueInterruptedParsing() 	mozilla/parser/htmlparser/src/nsParser.cpp:1118
20 	nsContentSink::ContinueInterruptedParsingIfEnabled() 	mozilla/content/base/src/nsContentSink.cpp:1494
21 	nsRunnableMethod<nsContentSink>::Run() 	nsThreadUtils.h:261
22 	nsThread::ProcessNextEvent(int, int*) 	mozilla/xpcom/threads/nsThread.cpp:490
23 	NS_ProcessNextEvent_P(nsIThread*, int) 	nsThreadUtils.cpp:227
24 	nsBaseAppShell::Run() 	mozilla/widget/src/xpwidgets/nsBaseAppShell.cpp:154
25 	nsAppStartup::Run() 	mozilla/toolkit/components/startup/src/nsAppStartup.cpp:170
26 	XRE_main 	mozilla/toolkit/xre/nsAppRunner.cpp:3114
27 	main 	mozilla/browser/app/nsBrowserApp.cpp:153
28 	WinMain 	mozilla/browser/app/nsBrowserApp.cpp:166
29 	__tmainCRTStartup 	crtexe.c:589
30 	kernel32.dll@0x27d29
Flags: blocking1.8.1.8?
Flags: blocking-firefox3?
Duplicate of this bug: 398122
I see this crash on Mac as well - Changing to all and noting that is crashes the latest Bon Echo branch as well.
OS: Windows Server 2003 → All
Hardware: PC → All
I don't think we can block 1.8.1.8 on this since we don't even have the beginnings of a fix.

Can you try to save the page locally (complete) and see if the crash is still reproducible? If so then zip that and attach to the bug, just in case the investorsdaily page changes. Reproducible testcases are like gold, don't lose this one.
Flags: blocking1.8.1.8? → wanted1.8.1.x+
Posted file saved webpage (obsolete) —
Attachment #283078 - Attachment is obsolete: true
Posted file smaller testcase (crashes on load) (obsolete) —
I'm not sure whether this is minimal, but reducing the size of the switch statement any further seems to cause the crash to disappear.
Attachment #283079 - Attachment is obsolete: true
I crash with relatively recent trunk and 1.8 branch builds, on Windows.
Assignee: nobody → general
Component: General → JavaScript Engine
Flags: blocking-firefox3?
Product: Firefox → Core
QA Contact: general → general
Flags: blocking1.9?
Keywords: testcase
I don't crash if I pass arguments to long_switch that don't match a "case" in the switch, or if I remove some of the duplicated statements inside the switches.
Summary: Crash on Load [@ js_Interpret] → Crash with large switch statement [@ js_Interpret]
Regressed when?

/be
(In reply to comment #10)
> Regressed when?
> 
> /be
> 
I'll look for that later today
sorry, i'm unable to reproduce the crash on either of the 2 pages so i can't get a regressionwindow.
I tried with both my daily and a new profile, no crash.
the 3rd testcase crashes on all my builds, all the way back till 20060401
Posted file simplified testcase
I've looked at the disassembly of this testcase and the previous one and here's what happening AFAICS:

1. During compilation, if a JSOP_LOOKUPSWITCH is generated inside a JSOP_LOOKUPSWITCHX more than 32KB after the JSOP_LOOKUPSWITCHX opcode, then SpiderMonkey will erronously emit 32-bit offsets for the JSOP_LOOKUPSWITCH!
2. When the interpreter executes this JSOP_LOOKUPSWITCH and finds the match, these 32 bit offsets are looked up with GET_JUMP_OFFSET (the 16-bit version).
3. This leads to len == 0 in jsinterp.c line 4534. 
4. len is added to the current PC, which means the same JSOP_LOOKUPSWITCH is executed again, but this time it will pop some random garbage from the stack and use that garbage as its lval. This crashes sooner or later...

I could try to locate the bug in the emitter but I don't know this code at all so don't hold your breath; it could take ages. Perhaps this information is enough for one of the regulars to come up with a quick fix.
That analysis was a bit wrong, let's try again. If the switch statement (doesn't matter if it uses lookupswitch or tableswitch) comes more than 32K after the start of the function, then all jump offsets are 0. These 32K code can be anything, it's only important that cg->spanDeps is not null, then js_SetJumpOffset generates 0 offsets.
Attachment #283125 - Attachment is obsolete: true
Posted file another testcase
Switch statements in large functions is quite broken. In this testcase the switch can't be reached but its mere presence causes the emitter to generate the wrong bytecode for the 'if' statement. It should be 'ifeqx 32804', but it is 'ifeq 14' instead.

With this trick an attacker could get the engine to execute arbitrary bytecodes so this might be security sensitive?
(In reply to comment #17)
> With this trick an attacker could get the engine to execute arbitrary bytecodes
> so this might be security sensitive?

Yes, this is a security hazard.
Assignee: general → igor
Group: security
Flags: blocking1.8.1.10+
Whiteboard: [sg:critical]
here is a test case for the shell:

var N = 6000;

// Array(N).join('a.x;') generates (N+1)*(5+1) bytes in bytecode
// where 5 comes getargprop and one from pop.

var src = 'if (a) {'+Array(N).join('a.x;')+'return "Bug"; }'+
          'return 1; '+
          ' switch (a) { case 1: ; case 2: return; }';

var f = Function('a', src);

var result = f(false);
if (result !== 1)
    throw "Bogus compilation is detected";
Posted patch fix v1 (obsolete) — Splinter Review
The reason for the bug is that EmitSwitch from jsemit.c calls js_SetJumpOffset on the switch jumps without making sure that span dependencies are added for the jumps. js_SetJumpOffset only adds span dependencies for the already emitted code on the first big jump when cg->spanDeps is null. Thus when cg->spanDeps is not null before the switch (this is exactly the situation that the test case triggers) the code must call AddSpanDep on all the jumps. 

Without the fix the code will treat 0 recorded at the jump offset as an index into the first span dependency record eventually overwriting it with the relative jumps for the switch.
Attachment #287014 - Flags: review?(brendan)
Attachment #287014 - Flags: approvalM9?
Attachment #287014 - Flags: approval1.9?
(In reply to comment #17)
> Created an attachment (id=286699) [details]
> another testcase

Thanks for the test cases! With them fixing the bug was just a matter of spending time.
Status: NEW → ASSIGNED
Comment on attachment 287014 [details] [diff] [review]
fix v1

Can't approve unreviewed patches :(
Attachment #287014 - Flags: approvalM9?
Attachment #287014 - Flags: approval1.9?
Would it be too optimistic to leave the request flags, in the hopes that brendan -will- approve this patch soon?  :)
(In reply to comment #23)
> Would it be too optimistic to leave the request flags, in the hopes that
> brendan -will- approve this patch soon?  :)

Clearing the flag allows drivers to keep the outstanding request list minimal, which makes it easier to notice new additions and track progress of approval triage.
(In reply to comment #24)
> Clearing the flag allows drivers to keep the outstanding request list minimal,
> which makes it easier to notice new additions and track progress of approval
> triage.

So the right thing to do is to set blocking flags for the bug which has already been done.
Comment on attachment 287014 [details] [diff] [review]
fix v1

>+AddSwitchSpanDep(JSContext *cx, JSCodeGenerator *cg, jsbytecode *pc)

Call this AddSwitchSpanDeps.

>+{
>+    JSOp op;
>+    jsbytecode *pc2;
>+    ptrdiff_t off;
>+    jsint low, high;
>+    uintN njumps, indexLen;

Nutty style consistency rule would favor indexlen (since Len is not a word, it's not Length) here.

>         /*
>          * After this point, all control flow involving JSOP_TABLESWITCH
>          * must set ok and goto out to exit this function.  To keep things
>          * simple, all switchOp cases exit that way.
>          */
>+

Not sure that blank line is worth it.

>+        if (cg->spanDeps) {
>+            /*
>+             * We already generated at least one big jump so we must
>+             * explicitly add span dependencies for the switch jumps.
>+             * Called below js_SetJumpOffset can only do it when patching

Comma aftert "Called below", could even say "When called below, ..." here.

r/a=me.

/be
Attachment #287014 - Flags: review?(brendan)
Attachment #287014 - Flags: review+
Attachment #287014 - Flags: approval1.9+
Posted patch fix v2Splinter Review
The previous version of my patch has a bug in AddSwitchSpanDeps where it returns JS_FALSE, not -1, to indicate a failure. In the new version I, besides addressing the nits, use jsbytecode * as a return type for the function to simplify BuildSpanDepTable.
Attachment #287014 - Attachment is obsolete: true
Attachment #287339 - Flags: review?(brendan)
Comment on attachment 287339 [details] [diff] [review]
fix v2

Good for M9 if there's time.

/be
Attachment #287339 - Flags: review?(brendan)
Attachment #287339 - Flags: review+
Attachment #287339 - Flags: approvalM9?
Attachment #287339 - Flags: approval1.9+
Comment on attachment 287339 [details] [diff] [review]
fix v2

a=endgame drivers for M9
Attachment #287339 - Flags: approvalM9? → approvalM9+
I checked in the patch from comment 27 to the CVS trunk:

http://bonsai.mozilla.org/cvsquery.cgi?module=PhoenixTinderbox&branch=HEAD&cvsroot=%2Fcvsroot&date=explicit&mindate=1194378060&maxdate=1194378091&who=igor%mir2.org
Status: ASSIGNED → RESOLVED
Closed: 12 years ago
Resolution: --- → FIXED
Flags: in-testsuite+
Flags: in-litmus-
verified fixed 1.9.0 linux|mac|win
Status: RESOLVED → VERIFIED
Do we need a separate patch for the 1.8 branch or does this one apply? If this one works please ask for approval1.8.1.12 on it, or else please create the branch version of this patch.
Whiteboard: [sg:critical] → [sg:critical] need patch for 1.8
This is hand-merge of the trunk fix.
1.8.1 version of the fix required a hand merge as a trunk version uses UINT16_LEN and INDEX_LEN constants that do not exist on 1.8.1 branch.
Comment on attachment 294254 [details] [diff] [review]
fix for 1.8.1 v1

r+ is based on triviality of hand-merge.
Attachment #294254 - Flags: review+
Attachment #294254 - Flags: approval1.8.1.12?
Comment on attachment 294254 [details] [diff] [review]
fix for 1.8.1 v1

approved for 1.8.1.12, a=dveditz for release-drivers
Attachment #294254 - Flags: approval1.8.1.12? → approval1.8.1.12+
I checked in the patch from comment 35 to MOZILLA_1_8_BRANCH:

Checking in jsemit.c;
/cvsroot/mozilla/js/src/jsemit.c,v  <--  jsemit.c
new revision: 3.128.2.74; previous revision: 3.128.2.73
done
Keywords: fixed1.8.1.12
Whiteboard: [sg:critical] need patch for 1.8 → [sg:critical]
verified fixed 1.8.1 linux/mac/win
Group: security
distro patch block 1.8.0.15
Flags: blocking1.8.0.15+
Posted patch for 1.8.0Splinter Review
igor, please review if this patch still makes sense on the 1.8.0 branch.
Attachment #308877 - Flags: review?(igor)
(In reply to comment #42)
> Created an attachment (id=308877) [details]
> for 1.8.0
> 
> igor, please review if this patch still makes sense on the 1.8.0 branch.

Could you attach a plain diff between 1.8.1 and 1.8.0 versions? 
Comment on attachment 310208 [details] [diff] [review]
diff between 1.8.1 and 1.8.0 version of this patch


if that helps i can also post an excerpt of the diffed code section _after_ applying the 1.8.0 patch
Attachment #310208 - Flags: review?(igor)
ok, now i see what you ment by _plain_ diff.
Attachment #310208 - Attachment is obsolete: true
Attachment #310213 - Flags: review?(igor)
Attachment #310208 - Flags: review?(igor)
Attachment #308877 - Flags: review?(igor) → review+
Comment on attachment 310213 [details] [diff] [review]
1.8.1 to 1.8.0 diff (plain style)

This is a helper attachment and should not bear any flags.
Attachment #310213 - Flags: review?(igor)
Comment on attachment 308877 [details] [diff] [review]
for 1.8.0

a=asac for 1.8.0.15
Attachment #308877 - Flags: approval1.8.0.15+
Committed to the 1.8.0 branch
Keywords: fixed1.8.0.15
/cvsroot/mozilla/js/tests/js1_5/Regress/regress-398085-01.js,v  <--  regress-398085-01.js
initial revision: 1.1
/cvsroot/mozilla/js/tests/js1_5/Regress/regress-398085-02.js,v  <--  regress-398085-02.js
initial revision: 1.1
Crash Signature: [@ js_Interpret]
Flags: blocking1.9?
You need to log in before you can comment on or make changes to this bug.