Bug 223787 – Out of memory crash with find('a'.repeat(2**30))

• Status: RESOLVED
• Resolution: FIXED
• Component: HTML Editing

[Ryosuke Niwa]

e.g.

3   0x10d6feeae WebCore::SearchBuffer::SearchBuffer(WTF::String const&, WTF::OptionSet<WebCore::FindOptionFlag>)
4   0x10d6ec876 WebCore::forEachMatch(WebCore::SimpleRange const&, WTF::String const&, WTF::OptionSet<WebCore::FindOptionFlag>, WTF::Function<bool (WebCore::CharacterRange)> const&)
5   0x10d6ed14e WebCore::findPlainText(WebCore::SimpleRange const&, WTF::String const&, WTF::OptionSet<WebCore::FindOptionFlag>)
6   0x10d68978b WebCore::Editor::rangeOfString(WTF::String const&, WTF::Optional<WebCore::SimpleRange> const&, WTF::OptionSet<WebCore::FindOptionFlag>)
7   0x10d689323 WebCore::Editor::findString(WTF::String const&, WTF::OptionSet<WebCore::FindOptionFlag>)
8   0x10dd138c4 WebCore::DOMWindow::find(WTF::String const&, bool, bool, bool, bool, bool, bool) const
9   0x10bd13b7d WebCore::jsDOMWindowInstanceFunctionFind(JSC::JSGlobalObject*, JSC::CallFrame*)
10  0x29de2f601178
11  0x53039faf1 llint_entry
12  0x53038231d vmEntryToJavaScript
13  0x530d43eeb JSC::Interpreter::executeProgram(JSC::SourceCode const&, JSC::JSGlobalObject*, JSC::JSObject*)

<script>
  find('a'.repeat(2**30));
</script>

<rdar://67671004>

[Ryosuke Niwa]

Darin noticed that this is because we allowing 8 times the length of the searching string at the beginning of SearchBuffer in TextIterator.cpp:

m_buffer.reserveInitialCapacity(std::max(targetLength * 8, minimumSearchBufferSize));

That's probably a bit excessive!

[Darin Adler]

There’s a reason we do this (make a large buffer), because of the effect it has on search correctness. The number may not need to be exactly "8 * length" but it does need to be larger than the search string, for context to be handled correctly.

The true issues here are:

1) we have no limit on the size of the search string; no reason for that: we should have one
2) we do this allocation of the search buffer in the "crash if not enough memory is available" mode, not in the "throw an exception if not enough memory is available" or "fail silently if not enough memory is available" modes

[Darin Adler]

I think we should fix this just by dealing with (1), add a string length limit to DOMWindow::find.

[Frédéric Wang (:fredw)]

Created attachment 425397 [details]
Patch

Following suggestion of comment 3.

[Ryosuke Niwa]

Comment on attachment 425397 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=425397&action=review

> Source/WebCore/page/DOMWindow.cpp:1202
> +    // Limit the maximum length to prevent any out-of-memory crash in SearchBuffer::SearchBuffer.
> +    constexpr size_t maximumStringLength = 517888;

Why don't we limit to std::limits<uint16_t>::max() or even std::limits<int16_t>::max()?
This magic number seems arbitrary.

[Ryosuke Niwa]

Comment on attachment 425397 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=425397&action=review

> Source/WebCore/page/DOMWindow.cpp:1203
> +    if (!isCurrentlyDisplayedInFrame() || string.length() > maximumStringLength)

I guess another option is to truncate the first N characters.

[Frédéric Wang (:fredw)]

Comment on attachment 425397 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=425397&action=review

>> Source/WebCore/page/DOMWindow.cpp:1202
>> +    constexpr size_t maximumStringLength = 517888;
> 
> Why don't we limit to std::limits<uint16_t>::max() or even std::limits<int16_t>::max()?
> This magic number seems arbitrary.

Right, actually I had done that initially. According to https://en.cppreference.com/w/c/types/size_t so "The bit width of size_t is not less than 16" so I also had thought about std::limits<uint16_t>::max() / 8.

[Frédéric Wang (:fredw)]

Created attachment 425497 [details]
Patch for landing

[Frédéric Wang (:fredw)]

Comment on attachment 425397 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=425397&action=review

>>> Source/WebCore/page/DOMWindow.cpp:1202
>>> +    constexpr size_t maximumStringLength = 517888;
>> 
>> Why don't we limit to std::limits<uint16_t>::max() or even std::limits<int16_t>::max()?
>> This magic number seems arbitrary.
> 
> Right, actually I had done that initially. According to https://en.cppreference.com/w/c/types/size_t so "The bit width of size_t is not less than 16" so I also had thought about std::limits<uint16_t>::max() / 8.

Done.

>> Source/WebCore/page/DOMWindow.cpp:1203
>> +    if (!isCurrentlyDisplayedInFrame() || string.length() > maximumStringLength)
> 
> I guess another option is to truncate the first N characters.

Do you want that? It looks truncate or substring would require an extra copy, but maybe I'm missing how to create a string view.

[Darin Adler]

Comment on attachment 425397 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=425397&action=review

>>>> Source/WebCore/page/DOMWindow.cpp:1202
>>>> +    constexpr size_t maximumStringLength = 517888;
>>> 
>>> Why don't we limit to std::limits<uint16_t>::max() or even std::limits<int16_t>::max()?
>>> This magic number seems arbitrary.
>> 
>> Right, actually I had done that initially. According to https://en.cppreference.com/w/c/types/size_t so "The bit width of size_t is not less than 16" so I also had thought about std::limits<uint16_t>::max() / 8.
> 
> Done.

I don’t care deeply about this, but fo me the largest 16-bit or 15-bit value is also arbitrary, and worse, implies this is about some 16-bit issues somewhere in the code. Hiding the magic number behind a formula doesn’t make it any less an arbitrary number. I would prefer a rationale comment that explains why the number is not too low. The current comment explains only why we have a limit, but a better one also says why this is a good choice for that limit.

>>> Source/WebCore/page/DOMWindow.cpp:1203
>>> +    if (!isCurrentlyDisplayedInFrame() || string.length() > maximumStringLength)
>> 
>> I guess another option is to truncate the first N characters.
> 
> Do you want that? It looks truncate or substring would require an extra copy, but maybe I'm missing how to create a string view.

I prefer failing. Creating a StringView is really easy but I don’t think it would enhance any user’s experience. “Searching for the wrong thing.”

[Frédéric Wang (:fredw)]

Comment on attachment 425397 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=425397&action=review

>>>>> Source/WebCore/page/DOMWindow.cpp:1202
>>>>> +    constexpr size_t maximumStringLength = 517888;
>>>> 
>>>> Why don't we limit to std::limits<uint16_t>::max() or even std::limits<int16_t>::max()?
>>>> This magic number seems arbitrary.
>>> 
>>> Right, actually I had done that initially. According to https://en.cppreference.com/w/c/types/size_t so "The bit width of size_t is not less than 16" so I also had thought about std::limits<uint16_t>::max() / 8.
>> 
>> Done.
> 
> I don’t care deeply about this, but fo me the largest 16-bit or 15-bit value is also arbitrary, and worse, implies this is about some 16-bit issues somewhere in the code. Hiding the magic number behind a formula doesn’t make it any less an arbitrary number. I would prefer a rationale comment that explains why the number is not too low. The current comment explains only why we have a limit, but a better one also says why this is a good choice for that limit.

I agree, but I'm not sure what an explanation would be... Even the min buffer size is currently 8192 which corresponds to a string of length 1024. This already looks like a quite big to me to be honest.... Maybe argue that pages are generally a few kbytes, so something like 64 * 1024 makes sense?

[Darin Adler]

Comment on attachment 425397 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=425397&action=review

>>>>>> Source/WebCore/page/DOMWindow.cpp:1202
>>>>>> +    constexpr size_t maximumStringLength = 517888;
>>>>> 
>>>>> Why don't we limit to std::limits<uint16_t>::max() or even std::limits<int16_t>::max()?
>>>>> This magic number seems arbitrary.
>>>> 
>>>> Right, actually I had done that initially. According to https://en.cppreference.com/w/c/types/size_t so "The bit width of size_t is not less than 16" so I also had thought about std::limits<uint16_t>::max() / 8.
>>> 
>>> Done.
>> 
>> I don’t care deeply about this, but fo me the largest 16-bit or 15-bit value is also arbitrary, and worse, implies this is about some 16-bit issues somewhere in the code. Hiding the magic number behind a formula doesn’t make it any less an arbitrary number. I would prefer a rationale comment that explains why the number is not too low. The current comment explains only why we have a limit, but a better one also says why this is a good choice for that limit.
> 
> I agree, but I'm not sure what an explanation would be... Even the min buffer size is currently 8192 which corresponds to a string of length 1024. This already looks like a quite big to me to be honest.... Maybe argue that pages are generally a few kbytes, so something like 64 * 1024 makes sense?

Since the search buffer allocates memory much larger than the string being searched for, can’t have too massive a limit. It doesn’t seem necessary to support searching for super giant search strings like entire webpages. Most searches are for a phrase or a paragraph not “search“ for an entire document. Thus this number seems reasonable. Something along those lines is the thinking; not sure how to write a succinct comment.

[Frédéric Wang (:fredw)]

Created attachment 425519 [details]
Patch for landing

[Darin Adler]

Comment on attachment 425519 [details]
Patch for landing

View in context: https://bugs.webkit.org/attachment.cgi?id=425519&action=review

> LayoutTests/ChangeLog:11
> +        * editing/find/find-long-string-crash-expected.txt: Added.
> +        * editing/find/find-long-string-crash.html: Added.

Seems like eventually we should also add a test with a string of the maximum length to make sure the search works, and a string just over the maximum length to make sure it does nothing as expected.

[Ryosuke Niwa]

There is no security concern here. Moving out of the security component.

[Frédéric Wang (:fredw)]

Created attachment 425609 [details]
Patch for landing

[Frédéric Wang (:fredw)]

Comment on attachment 425519 [details]
Patch for landing

View in context: https://bugs.webkit.org/attachment.cgi?id=425519&action=review

>> LayoutTests/ChangeLog:11
>> +        * editing/find/find-long-string-crash.html: Added.
> 
> Seems like eventually we should also add a test with a string of the maximum length to make sure the search works, and a string just over the maximum length to make sure it does nothing as expected.

OK, done in the last patch uploaded.

[Frédéric Wang (:fredw)]

Created attachment 425683 [details]
Patch for landing

fix the path to the JS resources

[Darin Adler]

Comment on attachment 425683 [details]
Patch for landing

View in context: https://bugs.webkit.org/attachment.cgi?id=425683&action=review

> Source/WebCore/page/DOMWindow.cpp:1203
> +    constexpr size_t maximumStringLength = std::numeric_limits<uint16_t>::max();

Small nitpick that we don’t have to fix before landing: WTF::String lengths are not size_t, they are unsigned. But the type of this constant really doesn’t matter at all. I’d suggest auto instead of size_t. Or unsigned would also be OK. No real problem using size_t, but no need for a 64-bit constant for this purpose.

[Frédéric Wang (:fredw)]

Created attachment 425725 [details]
Patch for landing

[EWS]

Committed r275818 (236388@main): <https://commits.webkit.org/236388@main>

All reviewed patches have been landed. Closing bug and clearing flags on attachment 425725 [details].