1084280 - Regexp freeze

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Pierre Réveillon]

Attachment: Test case

User Agent: Mozilla/5.0 (X11; Ubuntu; Linux x86_64; rv:32.0) Gecko/20100101 Firefox/32.0
Build ID: 20140924083558

Steps to reproduce:

Applying this Regexp on a very big string:
String.match(/([^\xA9]{400}|^[^\xA9]{0,400})(?:Copyright|\xA9|\(c\))[^\xA9]{0,400}/gi)


Actual results:

Application freeze, with a lot of unresponsive script alerts.


Expected results:

On Firefox 31.2 (and Google Chrome and Safari), it takes a few seconds to get the result.

Comment 1

[Loic]

Regression range:
good=2014-05-27
bad=2014-05-28
http://hg.mozilla.org/mozilla-central/pushloghtml?fromchange=cbe4f69c2e9c&tochange=e017c15325ae

Comment 3

[Loic]

It's not a dupe, this testcase doesn't work in the latest Nightly even with the bugfix from bug 1077514.

Comment 4

[Brian Hackett [Laid off!]]

What happens if you disable the slow script dialog?

Comment 5

[Loic]

I set dom.max_script_run_time from 20 to 50, Nightly is able to produce the result expected but with a major performance drop: duration is longer (it's almost instant in versions before bug 1015677) and Nightly displays the message "Firefox is not responding" (UI totally locked).

Comment 6

[Jan de Mooij [:jandem]]

Brian anything else we can do here? This is blocking 34 so it'd be good if we could get a fix in if possible...

Comment 7

[Brian Hackett [Laid off!]]

I just tried this in a debug OS X x64 debug build and the 'Run test' button pops up a result after a couple seconds.  How do I reproduce this?

Comment 8

[OW]

On a previous Firefox (or Safari... Google Chrome) go to https://bugzilla.mozilla.org/attachment.cgi?id=8506761 and click on Run Test. It takes less than a second. On FF33 or the nightly, if you are lucky, it will take maybe 10 seconds, otherwise you will get the unresponsive script alert.

Comment 9

[Brian Hackett [Laid off!]]

(In reply to OW from comment #8)
> On a previous Firefox (or Safari... Google Chrome) go to
> https://bugzilla.mozilla.org/attachment.cgi?id=8506761 and click on Run
> Test. It takes less than a second. On FF33 or the nightly, if you are lucky,
> it will take maybe 10 seconds, otherwise you will get the unresponsive
> script alert.

I just tried a current build.  See comment 7.

Comment 10

[Ekanan Ketunuti]

hang for me with nightly 36 running on windows 7 x86.

Hang Report #1 (13 seconds)
js::irregexp::InterpretCode<wchar_t>(JSContext *,unsigned char const *,wchar_t const *,unsigned int,unsigned int,js::MatchPairs *) (in xul.pdb)
js::RegExpShared::execute(JSContext *,JS::Handle<JSLinearString *>,unsigned int,js::MatchPairs *) (in xul.pdb)
DoMatchGlobal (in xul.pdb)
js::str_match(JSContext *,unsigned int,JS::Value *) (in xul.pdb)
js::Invoke(JSContext *,JS::CallArgs,js::MaybeConstruct) (in xul.pdb)
Interpret (in xul.pdb)
js::RunScript(JSContext *,js::RunState &) (in xul.pdb)
js::Invoke(JSContext *,JS::CallArgs,js::MaybeConstruct) (in xul.pdb)
js::Invoke(JSContext *,JS::Value const &,JS::Value const &,unsigned int,JS::Value const *,JS::MutableHandle<JS::Value>) (in xul.pdb)
JS::Call(JSContext *,JS::Handle<JS::Value>,JS::Handle<JS::Value>,JS::HandleValueArray const &,JS::MutableHandle<JS::Value>) (in xul.pdb)
mozilla::dom::EventHandlerNonNull::Call(JSContext *,JS::Handle<JS::Value>,mozilla::dom::Event &,JS::MutableHandle<JS::Value>,mozilla::ErrorResult &) (in xul.pdb)
mozilla::dom::EventHandlerNonNull::Call<nsISupports *>(nsISupports * const &,mozilla::dom::Event &,JS::MutableHandle<JS::Value>,mozilla::ErrorResult &,mozilla::dom::CallbackObject::ExceptionHandling) (in xul.pdb)
mozilla::JSEventHandler::HandleEvent(nsIDOMEvent *) (in xul.pdb)
mozilla::EventListenerManager::HandleEventInternal(nsPresContext *,mozilla::WidgetEvent *,nsIDOMEvent * *,mozilla::dom::EventTarget *,nsEventStatus *) (in xul.pdb)
mozilla::EventTargetChainItem::HandleEventTargetChain(nsTArray<mozilla::EventTargetChainItem> &,mozilla::EventChainPostVisitor &,mozilla::EventDispatchingCallback *,mozilla::ELMCreationDetector &) (in xul.pdb)
mozilla::EventDispatcher::Dispatch(nsISupports *,nsPresContext *,mozilla::WidgetEvent *,nsIDOMEvent *,nsEventStatus *,mozilla::EventDispatchingCallback *,nsCOMArray<mozilla::dom::EventTarget> *) (in xul.pdb)
PresShell::HandleEventInternal(mozilla::WidgetEvent *,nsEventStatus *) (in xul.pdb)
PresShell::HandleEventWithTarget(mozilla::WidgetEvent *,nsIFrame *,nsIContent *,nsEventStatus *) (in xul.pdb)
mozilla::EventStateManager::CheckForAndDispatchClick(nsPresContext *,mozilla::WidgetMouseEvent *,nsEventStatus *) (in xul.pdb)
mozilla::EventStateManager::PostHandleEvent(nsPresContext *,mozilla::WidgetEvent *,nsIFrame *,nsEventStatus *) (in xul.pdb)
PresShell::HandleEventInternal(mozilla::WidgetEvent *,nsEventStatus *) (in xul.pdb)
PresShell::HandlePositionedEvent(nsIFrame *,mozilla::WidgetGUIEvent *,nsEventStatus *) (in xul.pdb)
PresShell::HandleEvent(nsIFrame *,mozilla::WidgetGUIEvent *,bool,nsEventStatus *) (in xul.pdb)
nsViewManager::DispatchEvent(mozilla::WidgetGUIEvent *,nsView *,nsEventStatus *) (in xul.pdb)
nsView::HandleEvent(mozilla::WidgetGUIEvent *,bool) (in xul.pdb)
nsWindow::DispatchEvent(mozilla::WidgetGUIEvent *,nsEventStatus &) (in xul.pdb)
nsWindow::DispatchScrollEvent(mozilla::WidgetGUIEvent *) (in xul.pdb)
nsWindow::DispatchMouseEvent(unsigned int,unsigned int,long,bool,short,unsigned short) (in xul.pdb)
nsWindow::ProcessMessage(unsigned int,unsigned int &,long &,long *) (in xul.pdb)
nsWindow::WindowProcInternal(HWND__ *,unsigned int,unsigned int,long) (in xul.pdb)
CallWindowProcCrashProtected (in xul.pdb)
nsWindow::WindowProc(HWND__ *,unsigned int,unsigned int,long) (in xul.pdb)
InternalCallWinProc (in user32.pdb)
UserCallWinProcCheckWow (in user32.pdb)
DispatchMessageWorker (in user32.pdb)
DispatchMessageW (in user32.pdb)
nsAppShell::ProcessNextNativeEvent(bool) (in xul.pdb)
nsBaseAppShell::DoProcessNextNativeEvent(bool,unsigned int) (in xul.pdb)
nsBaseAppShell::OnProcessNextEvent(nsIThreadInternal *,bool,unsigned int) (in xul.pdb)
nsThread::ProcessNextEvent(bool,bool *) (in xul.pdb)
NS_ProcessNextEvent(nsIThread *,bool) (in xul.pdb)
mozilla::ipc::MessagePump::Run(base::MessagePump::Delegate *) (in xul.pdb)
MessageLoop::RunHandler() (in xul.pdb)
MessageLoop::Run() (in xul.pdb)
nsBaseAppShell::Run() (in xul.pdb)
nsAppShell::Run() (in xul.pdb)
nsAppStartup::Run() (in xul.pdb)
XREMain::XRE_mainRun() (in xul.pdb)
XREMain::XRE_main(int,char * * const,nsXREAppData const *) (in xul.pdb)
XRE_main (in xul.pdb)
do_main (in firefox.pdb)
NS_internal_main(int,char * *) (in firefox.pdb)
wmain (in firefox.pdb)
__tmainCRTStartup (in firefox.pdb)
BaseThreadInitThunk (in kernel32.pdb)
__RtlUserThreadStart (in ntdll.pdb)
_RtlUserThreadStart (in ntdll.pdb)

Comment 11

[OW]

(In reply to Brian Hackett (:bhackett) from comment #9)
> (In reply to OW from comment #8)
> > On a previous Firefox (or Safari... Google Chrome) go to
> > https://bugzilla.mozilla.org/attachment.cgi?id=8506761 and click on Run
> > Test. It takes less than a second. On FF33 or the nightly, if you are lucky,
> > it will take maybe 10 seconds, otherwise you will get the unresponsive
> > script alert.
> 
> I just tried a current build.  See comment 7.

Sorry I thought you said you tried a debug build, I simply suggested you can make it happen on the current release version of Firefox 33.0 with OSX 10.9.5 (among other systems and FF versions).

Comment 12

[Loic]

Could it be specific to Windows and Linux? I have some doubts...

Comment 13

[OW]

(In reply to Loic from comment #12)
> Could it be specific to Windows and Linux? I have some doubts...
No, we originally observed it on Mac, in fact, and reproduced it later on other platforms and versions.

Comment 14

[Brian Hackett [Laid off!]]

(In reply to Ekanan Ketunuti from comment #10)
> hang for me with nightly 36 running on windows 7 x86.
> 
> Hang Report #1 (13 seconds)
> js::irregexp::InterpretCode<wchar_t>(JSContext *,unsigned char const
> *,wchar_t const *,unsigned int,unsigned int,js::MatchPairs *) (in xul.pdb)
> js::RegExpShared::execute(JSContext *,JS::Handle<JSLinearString *>,unsigned
> int,js::MatchPairs *) (in xul.pdb)
> DoMatchGlobal (in xul.pdb)
> ...

Is this actually a hang, or do you eventually get the slow script dialog?  (and make sure the slow script dialog is enabled.)  Since your stack is executing irregexp::InterpretCode it seems like the fix in bug 1077514 is working right, as the approach there is to fallback to the irregexp interpreter if a RegExp takes so long to execute that we end up showing the slow script dialog.  The interpreter will complete (and you might get additional slow script dialogs), but it can take a while.

Comment 15

[OW]

On our side we always had a very slow response or the unresponsive script dialog.
I don't know if this will help but we have seen this regression occur with many regexps: It seems to mostly occur when the first term of the pattern allows for matches of variable length. Like if some optimization was missing in the regexp engine, making it go through millions of possibilities.

Comment 16

[OW]

Attachment: Regexp regression - Timed Test Case

Comment 17

[OW]

I added timing in the test case:
https://bugzilla.mozilla.org/attachment.cgi?id=8510856

Here are the results I get on Mac OSX 10.9.5:
Firefox versions 31.2.0 and before: results in 220 to 260ms
Firefox versions from 32.0 to Aurora 35.0a2: no results. unresponsive script dialog
Nightly 36.0a1: results in 11200 to 11400ms

Comment 18

[Ekanan Ketunuti]

I get crash after clicking continue button on slow script dialog.


bp-abb16e5b-8811-4940-9154-6a3702141024
bp-89a0eea6-d0d9-4605-b4dc-d5e0a2141024
bp-4d25ce19-69ee-4947-9add-d43702141024
bp-ab235af8-1e1a-4d0d-b3a3-563c02141024

Comment 19

[Loic]

Same here: https://crash-stats.mozilla.com/report/index/7b747bb0-85d7-4a9c-b340-6290a2141024

Comment 20

[Brian Hackett [Laid off!]]

Hmm, bug 1077514 exposed a pretty big design flaw in our port of irregexp's interpreter.  Since we can handle interrupts during interpreter execution (which is what bug 1077514 is taking advantage of), that interrupt might end up executing other regexps and changing the backtrack stack, so when we get back to the outer interpreter execution the stack is totally messed up.

Comment 21

[Brian Hackett [Laid off!]]

(In reply to OW from comment #17)
> I added timing in the test case:
> https://bugzilla.mozilla.org/attachment.cgi?id=8510856
> 
> Here are the results I get on Mac OSX 10.9.5:
> Firefox versions 31.2.0 and before: results in 220 to 260ms
> Firefox versions from 32.0 to Aurora 35.0a2: no results. unresponsive script
> dialog
> Nightly 36.0a1: results in 11200 to 11400ms

With firefox 32 we moved to another regexp engine, irregexp (which was developed for and is used by Chrome), which is a lot slower on some inputs than JSC, the engine we were previously using (which was developed for and is used by Safari).  There's some more information on this at the link below, but this won't be fixed without an upstream patch for irregexp.

https://code.google.com/p/v8/issues/detail?id=430

Comment 22

[Brian Hackett [Laid off!]]

(In reply to Brian Hackett (:bhackett) from comment #21)
> (In reply to OW from comment #17)
> With firefox 32 we moved to another regexp engine, irregexp (which was
> developed for and is used by Chrome), which is a lot slower on some inputs
> than JSC, the engine we were previously using (which was developed for and
> is used by Safari).

Oops, sorry, the name of Safari's regexp engine is Yarr (hard to keep these straight sometimes).

Comment 23

[Brian Hackett [Laid off!]]

Attachment: fix interpreter stack use

This patch gives executions of the irregexp interpreter their own stack, so that they will not be messed up by reentrant regexp execution.

Comment 24

[OW]

Any help on this issue would be extremely welcome as this is pretty bad news on the Apple platform because of a serious catch 22: 
If I am not mistaken, the developer signature for Apple Maverick and Yosemite doesn't work with Xulrunner before v.35 and complex regexps cease to work after Xulrunner 31. It would not be a problem to wait for a solution to the Regexp regression if we could make a build with a Xulrunner version 31.3 for instance that could be signed for the latest versions of OSX. Otherwise I am not sure where we can go from here.

Comment 25

[Brian Hackett [Laid off!]]

(In reply to OW from comment #24)
> Any help on this issue would be extremely welcome as this is pretty bad news
> on the Apple platform because of a serious catch 22: 
> If I am not mistaken, the developer signature for Apple Maverick and
> Yosemite doesn't work with Xulrunner before v.35 and complex regexps cease
> to work after Xulrunner 31. It would not be a problem to wait for a solution
> to the Regexp regression if we could make a build with a Xulrunner version
> 31.3 for instance that could be signed for the latest versions of OSX.
> Otherwise I am not sure where we can go from here.

Does the ESR release work on Yosemite?  The latest ESR should be based on 31.  If not, you might want to file another bug, as this bug is hidden now since the crash is a security issue.

Comment 26

[OW]

31.2 ESR works on Yosemite but cannot be signed because the new Apple developer signature system is only working on versions higher than 35.
On the other hand, we have tried to apply the patch (thank you) and compile with version 35. It doesn't show the alert anymore but the result is like with Nightly 36.0a1: results in 11828ms
We can open yet another Bug for the Apple signature but this is not very encouraging: "The changes required are very invasive, and we don't feel that they can be safely backported to any earlier version quickly enough without major risk of regressions." ( see https://mail.mozilla.org/pipermail/firefox-dev/2014-August/002127.html )
This means that our choice is either to propose a program that cannot be installed on recent Mac systems without going to the system preferences and deactivate the security, or to accept a 50-fold performance drop. I have to say this is a pretty gloomy perspective...

Comment 27

[Pierre Réveillon]

(In reply to Brian Hackett (:bhackett) from comment #21)
> With firefox 32 we moved to another regexp engine, irregexp (which was
> developed for and is used by Chrome), which is a lot slower on some inputs
> than JSC, the engine we were previously using (which was developed for and
> is used by Safari).  There's some more information on this at the link
> below, but this won't be fixed without an upstream patch for irregexp.
> 
> https://code.google.com/p/v8/issues/detail?id=430

On Google Chrome (37), the timed test case takes only 2 seconds.

Comment 28

[Loic]

I guess now this bug is more about fixing the regexp crash than the performance drop due to the change of the regexp engine in FF.

Comment 29

[OW]

(In reply to Loic from comment #28)
> I guess now this bug is more about fixing the regexp crash than the
> performance drop due to the change of the regexp engine in FF.

I'm not sure I understand what you mean. Loosing 20% in execution time would be sad collateral damage but loosing 5000% seems to me as bad as a crash. It can hardly be called a performance drop, in fact, it is rather like a total collapse. Especially if FF is the only browser impacted.

Comment 30

[Loic]

Of course it's an issue, but it should be handled in another bug report.

Comment 31

[OW]

OK, I understand.
How do we do this? Because in the next ticket, we will also need to put a regexp example and therefore unveil the same security issue.

Comment 32

[Andrew McCreight [:mccr8]]

Based on comment 20 this sounds pretty nasty, and it seems to be fairly discoverable, so I'm going to mark it sec-critical. I'm not sure how easy it would be to actually exploit it, though.

Comment 33

[Brian Hackett [Laid off!]]

Comment on attachment 8511078 [details] [diff] [review]
fix interpreter stack use

[Security approval request comment]
How easily could an exploit be constructed based on the patch?

Not easily.

Do comments in the patch, the check-in comment, or tests included in the patch paint a bulls-eye on the security problem?

No.

Which older supported branches are affected by this flaw?

32+, though versions 32-35 (branches without bug 1077514 fixed) require javascript.options.native_regexp to be false.

If not all supported branches, which bug introduced the flaw?

bug 976446

Do you have backports for the affected branches? If not, how different, hard to create, and risky will they be?

trivial

How likely is this patch to cause regressions; how much testing does it need?

none

Approval Request Comment
[Feature/regressing bug #]: bug 976446
[User impact if declined]: exploitable crashes
[Describe test coverage new/current, TBPL]: none
[Risks and why]: none

Comment 34

[Daniel Veditz [:dveditz]]

Comment on attachment 8511078 [details] [diff] [review]
fix interpreter stack use

sec-approval+
a=dveditz for aurora and beta

Comment 35

[Brian Hackett [Laid off!]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/883218803b63

Comment 36

[OW]

Attachment: Firefox regexp test page 2.html

Here is a new test case of the same kind that takes 90ms in Safari, 170ms in FF31, freezes FF between 32 and 36 and crashes FF Nightly.

Comment 37

[OW]

(Still freezes after patches.)

Comment 38

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/883218803b63

Comment 39

[Loic]

(In reply to OW from comment #36)
> Created attachment 8515136 [details]
> Firefox regexp test page 2.html
> 
> Here is a new test case of the same kind that takes 90ms in Safari, 170ms in
> FF31, freezes FF between 32 and 36 and crashes FF Nightly.

As this bug is fixed, could you file a new bug report, please.

Comment 40

[OW]

There is already another report, public bug 1091459, referring to this one. However as the test case crashes the application I thought it was a good idea to put it here and consider regexps that recently crash Firefox because of irregexp as one issue. Should we create a different report for each? There will be many at this point.

Comment 41

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/releases/mozilla-aurora/rev/f3542301cc8f
https://hg.mozilla.org/releases/mozilla-beta/rev/631a73cdbc91

Comment 42

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/releases/mozilla-b2g34_v2_1/rev/631a73cdbc91

Comment 43

[Matt Wobensmith [:mwobensmith][:matt:]]

I'm able to see a slow script dialog, but no crash. This is goes for all builds, both affected builds and builds that contain the patch. Unless new tests or STR surface, I'm going to have to mark qe-verify- for now.