Regexp freeze

RESOLVED FIXED in Firefox 34, Firefox OS v2.1

Status

()

Core
JavaScript Engine
RESOLVED FIXED
3 years ago
3 years ago

People

(Reporter: Pierre Réveillon, Assigned: bhackett)

Tracking

({regression, sec-critical, testcase})

32 Branch
mozilla36
regression, sec-critical, testcase
Points:
---
Dependency tree / graph
Bug Flags:
qe-verify -

Firefox Tracking Flags

(firefox33 disabled, firefox34 fixed, firefox35+ fixed, firefox36+ fixed, firefox-esr31 unaffected, b2g-v1.4 disabled, b2g-v2.0 disabled, b2g-v2.0M disabled, b2g-v2.1 fixed, b2g-v2.2 fixed)

Details

(Whiteboard: Fx 32-35 requires non-default pref to be vulnerable, crash signature)

Attachments

(4 attachments)

(Reporter)

Description

3 years ago
Created attachment 8506761 [details]
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.
(Reporter)

Updated

3 years ago
OS: Linux → All
Hardware: x86_64 → All
Version: 33 Branch → 32 Branch
(Reporter)

Updated

3 years ago
Component: General → JavaScript Engine

Comment 1

3 years ago
Regression range:
good=2014-05-27
bad=2014-05-28
http://hg.mozilla.org/mozilla-central/pushloghtml?fromchange=cbe4f69c2e9c&tochange=e017c15325ae
Blocks: 1015677
Status: UNCONFIRMED → NEW
status-firefox33: --- → affected
tracking-firefox34: --- → ?
tracking-firefox35: --- → ?
tracking-firefox36: --- → ?
Ever confirmed: true
Flags: needinfo?(bhackett1024)
Keywords: regression, testcase
(Assignee)

Updated

3 years ago
Status: NEW → RESOLVED
Last Resolved: 3 years ago
Flags: needinfo?(bhackett1024)
Resolution: --- → DUPLICATE
Duplicate of bug: 1077514

Comment 3

3 years ago
It's not a dupe, this testcase doesn't work in the latest Nightly even with the bugfix from bug 1077514.
Status: RESOLVED → REOPENED
Resolution: DUPLICATE → ---
(Assignee)

Comment 4

3 years ago
What happens if you disable the slow script dialog?

Comment 5

3 years ago
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).
status-firefox34: --- → affected
status-firefox35: --- → affected
status-firefox36: --- → affected
tracking-firefox34: ? → +
tracking-firefox35: ? → +
tracking-firefox36: ? → +
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...
Flags: needinfo?(bhackett1024)
(Assignee)

Comment 7

3 years ago
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?
Flags: needinfo?(bhackett1024)

Comment 8

3 years ago
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.
(Assignee)

Comment 9

3 years ago
(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

3 years ago
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

3 years ago
(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

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

Comment 13

3 years ago
(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.
(Assignee)

Comment 14

3 years ago
(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

3 years ago
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

3 years ago
Created attachment 8510856 [details]
Regexp regression - Timed Test Case

Comment 17

3 years ago
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

3 years ago
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
Crash Signature: [@ RegExpStackCursor::push(int)] [@ js::irregexp::InterpretCode<wchar_t>(JSContext*, unsigned char const*, wchar_t const*, unsigned int, unsigned int, js::MatchPairs*) ]
Flags: needinfo?(bhackett1024)

Comment 19

3 years ago
Same here: https://crash-stats.mozilla.com/report/index/7b747bb0-85d7-4a9c-b340-6290a2141024
(Assignee)

Comment 20

3 years ago
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.
Group: core-security
(Assignee)

Comment 21

3 years ago
(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
Flags: needinfo?(bhackett1024)
(Assignee)

Comment 22

3 years ago
(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).
(Assignee)

Comment 23

3 years ago
Created attachment 8511078 [details] [diff] [review]
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.
Assignee: nobody → bhackett1024
Attachment #8511078 - Flags: review?(jdemooij)

Comment 24

3 years ago
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.
(Assignee)

Comment 25

3 years ago
(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.

Updated

3 years ago
Attachment #8511078 - Flags: review?(jdemooij) → review+

Comment 26

3 years ago
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...
(Reporter)

Comment 27

3 years ago
(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

3 years ago
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

3 years ago
(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

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

Comment 31

3 years ago
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.
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.
Keywords: sec-critical
(Assignee)

Comment 33

3 years ago
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
Attachment #8511078 - Flags: sec-approval?
Attachment #8511078 - Flags: approval-mozilla-beta?
Attachment #8511078 - Flags: approval-mozilla-aurora?
(Reporter)

Updated

3 years ago
Blocks: 1091459
Blocks: 976446
status-b2g-v1.4: --- → disabled
status-b2g-v2.0: --- → disabled
status-b2g-v2.0M: --- → disabled
status-b2g-v2.1: --- → disabled
status-b2g-v2.2: --- → affected
status-firefox33: affected → disabled
status-firefox34: affected → disabled
status-firefox35: affected → disabled
status-firefox-esr31: --- → unaffected
tracking-firefox34: + → ---
Whiteboard: Fx 32-35 requires non-default pref to be vulnerable
Comment on attachment 8511078 [details] [diff] [review]
fix interpreter stack use

sec-approval+
a=dveditz for aurora and beta
Attachment #8511078 - Flags: sec-approval?
Attachment #8511078 - Flags: sec-approval+
Attachment #8511078 - Flags: approval-mozilla-beta?
Attachment #8511078 - Flags: approval-mozilla-beta+
Attachment #8511078 - Flags: approval-mozilla-aurora?
Attachment #8511078 - Flags: approval-mozilla-aurora+
(Assignee)

Comment 35

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

Comment 36

3 years ago
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.

Comment 37

3 years ago
(Still freezes after patches.)
https://hg.mozilla.org/mozilla-central/rev/883218803b63
Status: REOPENED → RESOLVED
Last Resolved: 3 years ago3 years ago
status-b2g-v2.2: affected → fixed
status-firefox34: disabled → affected
status-firefox35: disabled → affected
status-firefox36: affected → fixed
Resolution: --- → FIXED
Target Milestone: --- → mozilla36

Comment 39

3 years ago
(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

3 years ago
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.
https://hg.mozilla.org/releases/mozilla-aurora/rev/f3542301cc8f
https://hg.mozilla.org/releases/mozilla-beta/rev/631a73cdbc91
status-firefox34: affected → fixed
status-firefox35: affected → fixed
https://hg.mozilla.org/releases/mozilla-b2g34_v2_1/rev/631a73cdbc91
status-b2g-v2.1: disabled → fixed
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.
Flags: qe-verify-
Group: core-security
You need to log in before you can comment on or make changes to this bug.