548495 - Eliminate sources of O(N^2) backtracking in the linebreaker.

Status: RESOLVED FIXED

(Core :: Layout: Text and Fonts, defect)

Description

[Kurt Seifried]

User-Agent:       Mozilla/5.0 (Windows; U; Windows NT 6.1; en-US; rv:1.9.2) Gecko/20100115 Firefox/3.6
Build Identifier: Mozilla/5.0 (Windows; U; Windows NT 6.1; en-US; rv:1.9.2) Gecko/20100115 Firefox/3.6

This was a supposed webkit dos, the file is about a half meg, no actual < or > characters, crashes Firefox 3.6 and 3.5.7 on Windows 7/XP 64 and 32 bit reliably. Turning off CSS causes it to crash slightly slower.

Reproducible: Always

Steps to Reproduce:
1. Open that file, from web server or local file, rename to .txt/,html still crashes Firefox. 
2. 
3.
Actual Results:  
Firefox crashes.

Expected Results:  
Firefox displays file.

Comment 1

[Tyler Downer [He/Him]]

Well, no crash for me with Mozilla/5.0 (Windows; U; Windows NT 6.1; en-US; rv:1.9.3a2pre) Gecko/20100224 Minefield/3.7a2pre ID:20100224060607. I do get a hang, and I have to kill the process though. Please give a stacktrace. https://developer.mozilla.org/En/How_to_get_a_stacktrace_for_a_bug_report

Comment 2

[Kurt Seifried]

Apologies, I didn't realize using the term crash was incorrect within this context. I should have said it hangs (in my case I've let it sit for a while a few times but it never comes back, I have to kill it/etc.).

Comment 3

[Ria Klaassen (not reading all bugmail)]

I can confirm the hang with Mozilla/5.0 (Windows; U; Windows NT 6.0; en-US; rv:1.9.3a2pre) Gecko/20100224 Minefield/3.7a2pre

The hang is present with Firefox 3.0, 3.5. 3.6 and latest trunk, but not with Firefox 2.0. 
With Firefox 2 it breaks the lines and loads instantly.

Comment 4

[Simon Montagu :smontagu]

Regression range is between 2007091804 and 2007091904. http://bonsai.mozilla.org/cvsquery.cgi?treeid=default&module=all&branch=HEAD&branchtype=match&dir=&file=&filetype=match&who=&whotype=match&sortby=Date&hours=2&date=explicit&mindate=2007-09-18+04%3A00&maxdate=2007-09-19+04%3A00&cvsroot=%2Fcvsroot

Masayuki's line-breaking patch looks a possible candidate

Comment 5

[Boris Zbarsky [:bzbarsky]]

So just to make sure I'm reproducing this correctly....

1) I use wget to download http://www.securityfocus.com/data/vulnerabilities/exploits/38398.html to ~/test.html

2) I open ~/test.html in my web browser.

These steps work for me.  No hang.  Firefox 3.6 build on Mac.

This is not the same as the webkit steps to reproduce, which involve copying and pasting the text one sees if one loads that HTML file (which is mostly escapes) and then parsing the resulting file as HTML.  That also works for me.

So which steps are people using, and is this possibly Windows-only?

Comment 6

[Simon Montagu :smontagu]

I don't see the hang either with bz's STR, only when loading directly from securityfocus.com (which serves the file as text/plain), or if I download the file to a .txt file

Comment 7

[Boris Zbarsky [:bzbarsky]]

Aha!  That was the missing bit, ok.  Sounds like they're over-escaping (serving as text/plain _and_ html-escaping), but whatever.

I can reproduce when loading the file as text-plain.  Profile shows 100% of the time spent in ContextualAnalysis(unsigned short, unsigned short, unsigned short, ContextState&).

Comment 8

[Boris Zbarsky [:bzbarsky]]

14.3%	14.3%	0x11103438		dec      dword ptr [ebp-80]		Loop start[8]	
And the specific part of that function that takes up the time (sorry about the assembly; Shark's refusing to show me the source):

14.3% dec  dword ptr [ebp-80] Loop start[8]	
14.7% cmp  byte ptr [eax-2], byte 61			
0.4%  jz   _ZL18ContextualAnalysistttR12ContextState+753>			
0.0%  sub  eax, byte 2			
0.0%  mov  edx, dword ptr [ebp-80]			
56.2% test edx, edx			
14.3% jnz  <_ZL18ContextualAnalysistttR12ContextState+2008> Loop end[8]	

That jz is jumping to somewhere way before this code.

Comment 9

[Boris Zbarsky [:bzbarsky]]

Aha!  The relevant loop is inlined from HasCharacterAlready, with '=' as aCh (see the cmp instruction):

628   PRBool HasCharacterAlready(PRUnichar aCh) {
629     // Be careful for the index being unsigned.
630     for (PRUint32 i = mIndex; i > 0; --i) {
631       if (GetCharAt(i - 1) == aCh)
632         return PR_TRUE;
633     }
634     return PR_FALSE;
635   }

The jz is the |return PR_TRUE|.

The caller here is in ContextualAnalysis and looks like this:

723   } else if (cur == U_AMPERSAND || cur == U_SEMICOLON) {
724     // If this may be a separator of params of URL, we should break after.
725     if (!aState.UseConservativeBreaking(1) &&
726         aState.HasCharacterAlready(U_EQUAL))
727       return CLASS_CLOSE;

So every time we see an '&' or ';' we start scanning backwards from that point until we get to an '=' or to the beginning of the buffer.  In this case, there are lots of '&' and ';' but not '=', so we keep scanning back to buffer start all the time.  That makes the whole operation effectively O(N^2) in number of characters (and in particular makes the number of iterations of that loop O(N^2) in number of characters), and said number is 500,000 or so.  500,000^2 == 250,000,000,000, we and I would surprised if we can execute that loop faster than about 1ns per iteration, which gives us 250s as a lower bound for the entire operation.

Comment 10

[Boris Zbarsky [:bzbarsky]]

It looks like HasCharacterAlready is only called for U_EQUAL, U_SLASH, U_BACKSLASH.

Comment 11

[Boris Zbarsky [:bzbarsky]]

Attachment: Testcase text file (WILL HANG YOUR BROWSER)

Comment 12

[Boris Zbarsky [:bzbarsky]]

Attachment: Proposed fix

Comment 13

[Boris Zbarsky [:bzbarsky]]

Attachment: diff -w for review

Comment 14

[Masayuki Nakano [:masayuki] (he/him)(JST, +0900)]

Comment on attachment 428954 [details] [diff] [review]
diff -w for review

Looks great, thank you for your work!

Comment 15

[Boris Zbarsky [:bzbarsky]]

Pushed http://hg.mozilla.org/mozilla-central/rev/c1cfc1bf7e52

Not sure how to write a test for this that will pass reliably...

Masayuki Nakano, do you think this patch is safe enough for the branches?

Comment 16

[Masayuki Nakano [:masayuki] (he/him)(JST, +0900)]

(In reply to comment #15)
> Pushed http://hg.mozilla.org/mozilla-central/rev/c1cfc1bf7e52
> 
> Not sure how to write a test for this that will pass reliably...
> 
> Masayuki Nakano, do you think this patch is safe enough for the branches?

I think so, the line-breading is tested in http://mxr.mozilla.org/mozilla-central/source/layout/reftests/line-breaking/ . If all tests passed, it doesn't break most features (https://wiki.mozilla.org/Gecko:Line_Breaking)

Comment 17

[Boris Zbarsky [:bzbarsky]]

Er, in fact I was sure I had tested those... but I clearly hadn't.  Patch coming up to fix the issue this patch introduced due to notifying on slashes before checking for them.

Comment 18

[Boris Zbarsky [:bzbarsky]]

I pushed http://hg.mozilla.org/mozilla-central/rev/4e1b68ecf126 to fix that test failure.  Will attach that for review in a second.

Comment 19

[Boris Zbarsky [:bzbarsky]]

Attachment: Said diff

Comment 20

[Masayuki Nakano [:masayuki] (he/him)(JST, +0900)]

Comment on attachment 429285 [details] [diff] [review]
Said diff

thanks, and sorry for miscatch the mistake.

Comment 21

[Boris Zbarsky [:bzbarsky]]

Attachment: roll-up fix for branches

This applies to both the 1.9.1 and 1.9.2 branches.  Should be safe (or at least passes tests!) and eliminates a possible hang.

Comment 22

[Kurt Seifried]

Can Mozilla please assign a CVE to this for tracking (congrats on you guys getting CNA status!).

Comment 23

[Boris Zbarsky [:bzbarsky]]

I'm not sure why this needs a CVE id, but ccing dveditz...

Comment 24

[Kurt Seifried]

Because it's a pretty effective DoS (you typically have to forcibly kill firefox, then restart it, kill it again, restart it, get the tab that shows which screens you want to load or not, uncheck the bad one, and then you're back to normal).

Comment 25

[Tyler Downer [He/Him]]

That technically isn't a DoS, it's a hang. Not an exact DoS from firefox.

Comment 26

[Boris Zbarsky [:bzbarsky]]

I don't believe we typically assign CVEs to performance issues, though.  Anyway, dveditz is the one who'd know about that.

Comment 27

[Kurt Seifried]

CVE-2009-0773 crash
CVE-2009-1392 crash
CVE-2009-1827 hang
CVE-2009-1828 hang

You have in the last year (and before that as well).

Comment 28

[Boris Zbarsky [:bzbarsky]]

Both of those CVEs are about infinite loops.  There's no infinite loop in this bug; the browser becomes responsive after a minute or two of pegging the CPU.

Comment 29

[Boris Zbarsky [:bzbarsky]]

Well, more like 5-6 minutes, rather.  But definitely finite time.

Comment 30

[Daniel Veditz [:dveditz]]

Comment on attachment 429289 [details] [diff] [review]
roll-up fix for branches

Approved for 1.9.1.9 and 1.9.2.2, a=dveditz for release-drivers

Comment 31

[Boris Zbarsky [:bzbarsky]]

Pushed:
  http://hg.mozilla.org/releases/mozilla-1.9.2/rev/ae59a9d6b719
  http://hg.mozilla.org/releases/mozilla-1.9.1/rev/9e1581c8f9f9

Comment 33

[Carsten Book [:Tomcat]]

verified for 1.9.2-2 with Windows 7 Mozilla/5.0 (Windows; U; Windows NT 6.1; en-US; rv:1.9.2.2) Gecko/20100316 Firefox/3.6.2 - no hang on testcase file --> verfied 1.9.2