64589 - Recursive Javascript/DOM additions crash browser HARD

Status: VERIFIED DUPLICATE of bug 56940

(Core :: JavaScript Engine, defect)

Description

[Chris Casciano]

The dozen line recursive script found here[1] crashes mozilla big time [98/NT4 
& Mac]. It has brought down the entire system when tried on the Mac side. I 
don't know if its the recursion, or the creation of a giant document, but this 
scenario should be handled much better. It's just too easy for a malicious 
script to take out the browser/OS.

[1] http://www.assembler.org/AX/bomb.html - but you might want to use this 
instead - view-source:http://www.assembler.org/AX/bomb.html

Comment 1

[Jonathan S Abrams]

On Mac OS 9.0.4 build 2001010508 their is no crash.  Reporter, which Mac build r
u using?  Clicking on "kill-9" as the script is called results in nothing
happening.  The browser window is blank, and their is no crash or freeze of any
kind.

Comment 2

[Chris Casciano]

I don't know what build it was on the Mac side that did this as that info came
from the author of that page and not me. I will try and get some more info early
this week (next time I talk to the author). On the PC (win98/ build 2001010708)
side I can confirm it is still an issue.

Comment 3

[Keyser Sose]

Confirmed
Platform: PC
OS: Linux 2.2.16
Mozilla: 2001010512

Marking NEW. (although I believe this is a duplicate)

Comment 4

[timeless]

for the record, iepxlore ate 98% of my cpu on this wonderful link.

the remaining 2% was enough to nice the process (it's now using 80% or whatever 
it can get while i happilly use my computer). you could consider this to be a 
dupe of browser should be responsive in most infinte loops. or a dupe of the 
halting problems.  I just watch as memory usage slowly climbs (<22mb ram, and 
only 13mb vm).

oh, and this page actually crashed mdm.exe when i started the debugger (before 
having clicked the link) [Microsoft Debug Manager - handles the 
javascript errors]

Comment 5

[Brendan Eich [:brendan]]

JS protects itself against infinite recursion, eventually -- or did last time I
checked.  The engine will hog cycles until it hits a recursion stopper (either
the branch callback limit, or the internal interpreter-recursion-level counter
limit, or the iterative-call-count limit -- see
http://lxr.mozilla.org/mozilla/source/js/src/jsinterp.c#1137 and below).

But AFAICT, JS isn't running enough to hit its runaway-limiters.  Here's a stack
fragment I got in gdb:

#0  nsCOMPtr<nsIStyleContext>::get (this=0xbffdf0d8)
    at ../../../../dist/include/nsCOMPtr.h:630
#1  0x418547ed in nsCSSFrameConstructor::CreateAnonymousFrames (
    this=0x89f0b58, aPresShell=0x89d68e8, aPresContext=0x8a35ba8,
    aTag=0x8148750, aState=@0xbfffe380, aParent=0x89e4430,
    aNewFrame=0x87a57f0, aChildItems=@0xbffdf170)
    at nsCSSFrameConstructor.cpp:5354
#2  0x41854204 in nsCSSFrameConstructor::ConstructFrameByTag (this=0x89f0b58,
    aPresShell=0x89d68e8, aPresContext=0x8a35ba8, aState=@0xbfffe380,
    aContent=0x89e4430, aParentFrame=0x87a57a4, aTag=0x8148750,
    aNameSpaceID=0, aStyleContext=0x8895f88, aFrameItems=@0xbffdf470)
    at nsCSSFrameConstructor.cpp:5212
#3  0x41859b02 in nsCSSFrameConstructor::ConstructFrameInternal (
    this=0x89f0b58, aPresShell=0x89d68e8, aPresContext=0x8a35ba8,
    aState=@0xbfffe380, aContent=0x89e4430, aParentFrame=0x87a57a4,
    aTag=0x8148750, aNameSpaceID=0, aStyleContext=0x8895f88,
    aFrameItems=@0xbffdf470, aXBLBaseTag=0) at nsCSSFrameConstructor.cpp:7563
#4  0x418595d7 in nsCSSFrameConstructor::ConstructFrame (this=0x89f0b58,
    aPresShell=0x89d68e8, aPresContext=0x8a35ba8, aState=@0xbfffe380,
    aContent=0x89e4430, aParentFrame=0x87a57a4, aFrameItems=@0xbffdf470)
    at nsCSSFrameConstructor.cpp:7482
#5  0x4186676b in nsCSSFrameConstructor::ProcessChildren (this=0x89f0b58,
    aPresShell=0x89d68e8, aPresContext=0x8a35ba8, aState=@0xbfffe380,
    aContent=0x89e43f4, aFrame=0x87a57a4, aCanHaveGeneratedContent=1,
    aFrameItems=@0xbffdf470, aParentIsBlock=1, aTableCreator=0x0)
    at nsCSSFrameConstructor.cpp:11417
#6  0x4184e045 in nsCSSFrameConstructor::ConstructTableCellFrame (
    this=0x89f0b58, aPresShell=0x89d68e8, aPresContext=0x8a35ba8,
    aState=@0xbfffe380, aContent=0x89e43f4, aParentFrameIn=0x87a56f4,
    aStyleContext=0x8924bf0, aTableCreator=@0xbffdfbec, aIsPseudo=0,
    aChildItems=@0xbffdf68c, aNewCellOuterFrame=@0xbffdf528,
    aNewCellInnerFrame=@0xbffdf514, aIsPseudoParent=@0xbffdf52c)
    at nsCSSFrameConstructor.cpp:2881
#7  0x4184ec3f in nsCSSFrameConstructor::TableProcessChild (this=0x89f0b58,
    aPresShell=0x89d68e8, aPresContext=0x8a35ba8, aState=@0xbfffe380,
    aChildContent=@0x89e43f4, aParentFrame=0x87a56f4,
    aParentFrameType=0x814e458, aParentStyleContext=0x8924858,
    aTableCreator=@0xbffdfbec, aChildItems=@0xbffdf68c, aCaption=@0xbffdf688)
    at nsCSSFrameConstructor.cpp:3137
#8  0x4184e808 in nsCSSFrameConstructor::TableProcessChildren (this=0x89f0b58,
    aPresShell=0x89d68e8, aPresContext=0x8a35ba8, aState=@0xbfffe380,
    aContent=0x89e43b0, aParentFrame=0x87a56f4, aTableCreator=@0xbffdfbec,
    aChildItems=@0xbffdf68c, aCaption=@0xbffdf688)
    at nsCSSFrameConstructor.cpp:3048
#9  0x4184db39 in nsCSSFrameConstructor::ConstructTableRowFrame (
    this=0x89f0b58, aPresShell=0x89d68e8, aPresContext=0x8a35ba8,
    aState=@0xbfffe380, aContent=0x89e43b0, aParentFrameIn=0x896c4f8,
    aStyleContext=0x8924858, aTableCreator=@0xbffdfbec, aIsPseudo=0,
    aChildItems=@0xbffdf888, aNewFrame=@0xbffdf710,

Probably the generated table has gotten horrendously deep.  Stopping denial of
service attacks is hard precisely because you don't want to deny service to
legitimate service-clients.  Maybe the table code can be paranoid, especially
about generated content coming from the DOM (innerHTML assignment in particular,
as in this case).

Cc'ing jst, reassigning to karnaze; here's the bad function:

var table1 = "<table cellpadding=0 cellspacing=0 border=0><tr><td> ";
var table2 = "</td></tr></table>";
var bigOut1 = new Array();
var bigOut2 = new Array();
var content = "";

function bomb() {
  bigOut1[count] = table1;
  bigOut2[count] = table2;
  for (var i = bigOut1.length-1; i>=0; i--) {
    content = bigOut1[i] + content + bigOut2[i];
  }
  document.getElementById("b0").innerHTML = content;
  count++;
  bomb();
}

/be

Comment 6

[Phil Schwartau]

Setting default component -

Comment 7

[karnaze (gone)]

Moving to mozilla0.9.1. 

Comment 8

[Amarendra Hanumanula]

QA contact update

Comment 9

[karnaze (gone)]

I didn't see any activity until I went to the url without the "view-source" (and 
then hit the link). On a debug WinNT build, I let it run for quite a while and 
every time I broke saw.

memset() line 108
_free_dbg_lk(void * 0x0563c8d8, int 1) line 1082 + 28 bytes
_free_dbg(void * 0x0563c8d8, int 1) line 970 + 13 bytes
free(void * 0x0563c8d8) line 926 + 11 bytes
js_FinalizeStringRT(JSRuntime * 0x00da6980, JSString * 0x00dd45b0) line 2346 + 
13 bytes
js_FinalizeString(JSContext * 0x01345e70, JSString * 0x00dd45b0) line 2335 + 16 
bytes
js_GC(JSContext * 0x01345e70, unsigned int 1) line 1218 + 11 bytes
js_AllocGCThing(JSContext * 0x01345e70, unsigned int 1) line 497 + 11 bytes
js_NewString(JSContext * 0x01345e70, unsigned short * 0x09b2a2f0, unsigned int 
104583, unsigned int 0) line 2250 + 15 bytes
js_Interpret(JSContext * 0x01345e70, long * 0x0012fc88) line 2124 + 25 bytes
js_Execute(JSContext * 0x01345e70, JSObject * 0x00dabcc0, JSScript * 0x0136ce70, 
JSStackFrame * 0x00000000, unsigned int 0, long * 0x0012fc88) line 956 + 13 
bytes
JS_EvaluateUCScriptForPrincipals(JSContext * 0x01345e70, JSObject * 0x00dabcc0, 
JSPrincipals * 0x0128d910, const unsigned short * 0x0012fd80, unsigned int 21, 
const char * 0x00000000, unsigned int 0, long * 0x0012fc88) line 3222 + 25 bytes
nsJSContext::EvaluateString(nsJSContext * const 0x01344580, const 
basic_nsAReadableString<unsigned short> & {...}, void * 0x00dabcc0, nsIPrincipal 
* 0x0128d90c, const char * 0x00000000, unsigned int 0, const char * 0x00000000, 
basic_nsAWritableString<unsigned short> & {...}, int * 0x02fafce4) line 609 + 68 
bytes
nsEvaluateStringProxy::EvaluateString(nsEvaluateStringProxy * const 0x0136c0a0, 
char * * 0x02fafce0, int * 0x02fafce4) line 167 + 64 bytes
XPTC_InvokeByIndex(nsISupports * 0x0136c0a0, unsigned int 4, unsigned int 2, 
nsXPTCVariant * 0x0136f590) line 139
EventHandler(PLEvent * 0x0136f5e0) line 509 + 41 bytes
PL_HandleEvent(PLEvent * 0x0136f5e0) line 588 + 10 bytes
PL_ProcessPendingEvents(PLEventQueue * 0x012d0370) line 518 + 9 bytes
_md_EventReceiverProc(HWND__ * 0x0002036c, unsigned int 49297, unsigned int 0, 
long 19727216) line 1069 + 9 bytes
USER32! DispatchMessageWorker@8 + 135 bytes
USER32! DispatchMessageA@4 + 11 bytes
nsNativeViewerApp::Run() line 84
main(int 1, char * * 0x00ba5e60) line 157 + 11 bytes
mainCRTStartup() line 338 + 17 bytes
KERNEL

I was hoping to see a crash, but got the impression I never would since the 
memory usage went way up (but not enough to run out of VM) and then down. I'm 
not sure what the status of our memory pressure API is, but if there were a test 
case that did run out of memory, that would be the solution. Reassigning to js 
engine component to take a look.

Comment 10

[Phil Schwartau]

These bugs may be of related interest:  

            bug 21762  tracking: poor performance using DHTML 
            bug 65509  Very slow javascript pulldown menu
            bug 64516  95-99% CPU usage for dhtml "snow effect" 
            bug 40711  Compare rendering performance with IE5 

Comment 11

[Phil Schwartau]

Attachment: HTML testcase with UBound=50 on bomb() recursion

Comment 12

[Phil Schwartau]

NOTE: the above testcase uses document.getElementById() to display 
      its output, so it will not run in a non-W3C-compliant browser. 


This testcase only allows the bomb() function to recurse 50 times.
Click the "TEST" link, and wait a few seconds for the test to complete.
I made it to show how the double looping in the bomb() function looks.


It also shows that the variable "content" grows in length by a fixed amount
on each iteration of the double loop; namely, 71. This represents the sum
of the 53 characters contained in the the string variable "table1", and the 
18 characters contained in the variable "table2", which get concatenated 
to the content variable at each iteration.


NOTE: in the testcase, I DELETED this line from the bomb() function: 

         document.getElementById("b0").innerHTML = content;

So now it only has to do with string concatenation, as far as I can tell.


I have the UBound on recursion set to 50. If you want to experiment, 
save the testcase locally and change the UBound variable. Watch out!!!
If it's set to 100, for example, we run into the memory problems in the 
original report. With a high UBound you may also need to increase the 
rows attribute in the <TEXTAREA> element...


Since the growth of the content string is linear, this bug differs from
bug 40391, "JS + on long strings freezes mozilla, horks win98". 
In that bug's testcase, the string lengths grow exponentially.


Perhaps this bug is related to bug 56940: 

        "O(n**2) and O(n**3) growth too easy with JS string concat"  - ?

Comment 13

[Brendan Eich [:brendan]]

Unless we need another bug on DOM problems, I think this is a dup of bug 56940.
Phil, what do you say?  Mark dup if you agree.

/be

Comment 14

[Phil Schwartau]

Attachment: JS shell testcase. Load it via load() and do e.g. test(50)

Comment 15

[Phil Schwartau]

Attachment: JS Shell testcase. Even simpler: all Array() objects removed

Comment 16

[Phil Schwartau]

Even with these simplifed JS Shell testcases, we see the same behavior
as originally reported in the bug. Here, of course, the DOM plays no role. 
I also had to convince myself that the Array() objects were not the problem; 
hence the second JS Shell testcase where they have been removed. Here is 
the bomb() function from this last testcase: 


function bomb() 
{
  for (i=count; i>=0; i--)
  {
    content = table1 + content + table2;
    j++; 
  }

  if (++count < UBound) 
    bomb();
}


Here, the variable j is just keeping track of total loop iterations.
The variables "table1", "table2" are same strings as in the original
testcase at the give URL above: 

table1 = '<table cellpadding=0 cellspacing=0 border=0><tr><td> ';
table2 = '</td></tr></table>';


Thus, in this last incarnation of the test, at each iteration we are simply 
doing string concatenation of global variables: 


             content = table1 + content + table2


We run out of memory as originally reported in this bug -
 

Comment 17

[Phil Schwartau]

Attachment: Results of the two JS Shell tests on my WinNT box

Comment 18

[Phil Schwartau]

If you look at the test results, you will see little difference between the
two testcases. We run out of memory at just about the same spot. 

It is interesting to look at the relationship between the time to completion 
and the total number of iterations. For example, from the second test:


js> test(20)
UBound on bomb() recursion is set to 20
time = 46ms
Total number of iterations = 210
content.length = 14910

js> test(30)
UBound on bomb() recursion is set to 30
time = 203ms
Total number of iterations = 465
content.length = 33015



Since we have eliminated DOM objects from the test, and Array objects, 
I suppose there is only one further issue aside from string concatenation: 
does this bug reveal something inefficient about function recursion in JS? 


I agree with Brendan's opinion at 2001-03-25 15:55 above, and will mark
this as a duplicate of bug 56940, 

        "O(n**2) and O(n**3) growth too easy with JS string concat"



*** This bug has been marked as a duplicate of 56940 ***

Comment 19

[Phil Schwartau]

Attachment: JS shell testcase. Simplest: double loop, not recursion

Comment 20

[Phil Schwartau]

Attachment: Results of the simplest JS shell test on my WinNT box

Comment 21

[Phil Schwartau]

The results from the third and simplest JS shell testcase above are 
virtually the same as from the first and second. We run out of memory 
at roughly the same spot. Here is the bomb() function this time: 


function bomb() 
{
  for (count=0; count<UBound; count++)
  {
    for (i=count; i>=0; i--)
    {
      content = table1 + content + table2;
      j++; 
    }
  }
}


In this version, there are none of these features of the original testcase:

1. DOM objects
2. Array objects
3. Function recursion


We have reduced the testcase to loop iteration and string concatenation. 
Since the results have been materially the same every time, this provides 
further evidence that the issue in this bug is string concatenation - 

Comment 22

[Christian Holler (:decoder)]

A testcase for this bug was already added in the original bug (bug 56940).