Title: [237909] trunk/Source/WebCore
- Revision
- 237909
- Author
- [email protected]
- Date
- 2018-11-06 19:12:18 -0800 (Tue, 06 Nov 2018)
Log Message
Post too much text to iFrame could crash webkit
https://bugs.webkit.org/show_bug.cgi?id=190947
<rdar://problem/45678231>
Reviewed by Geoffrey Garen.
Optimize SuffixTree (Which is used by XSSAuditor) to stop storing each Node's
children as a static array of 128 pointers and use a dynamic array (vector)
instead. This uses way less memory. Also make SuffixTree and SuffixTree::Node
as fast allocated for performance. This part of the change is based on the
following Blink change:
- https://chromium.googlesource.com/chromium/src.git/+/6ca590e1c7edaa7c56cac9e3e3c39cf398ca8d4d
Also update the XSSAuditor to construct the SuffixTree lazily since there are
many cases (including the one in this bug) where we were spending a significant
amount of time building the SuffixTree and then never querying it.
* html/parser/XSSAuditor.cpp:
(WebCore::XSSAuditor::init):
(WebCore::XSSAuditor::decodedHTTPBodySuffixTree):
(WebCore::XSSAuditor::isContainedInRequest):
* html/parser/XSSAuditor.h:
* platform/text/SuffixTree.h:
(WebCore::SuffixTree::mightContain):
(WebCore::SuffixTree::Node::Node):
(WebCore::SuffixTree::Node::~Node):
(WebCore::SuffixTree::Node::find):
(WebCore::SuffixTree::Node::end):
(WebCore::SuffixTree::build):
(WebCore::SuffixTree<Codebook>::Node::childAt):
(WebCore::SuffixTree::Node::at): Deleted.
Modified Paths
Diff
Modified: trunk/Source/WebCore/ChangeLog (237908 => 237909)
--- trunk/Source/WebCore/ChangeLog 2018-11-07 02:31:30 UTC (rev 237908)
+++ trunk/Source/WebCore/ChangeLog 2018-11-07 03:12:18 UTC (rev 237909)
@@ -1,3 +1,37 @@
+2018-11-06 Chris Dumez <[email protected]>
+
+ Post too much text to iFrame could crash webkit
+ https://bugs.webkit.org/show_bug.cgi?id=190947
+ <rdar://problem/45678231>
+
+ Reviewed by Geoffrey Garen.
+
+ Optimize SuffixTree (Which is used by XSSAuditor) to stop storing each Node's
+ children as a static array of 128 pointers and use a dynamic array (vector)
+ instead. This uses way less memory. Also make SuffixTree and SuffixTree::Node
+ as fast allocated for performance. This part of the change is based on the
+ following Blink change:
+ - https://chromium.googlesource.com/chromium/src.git/+/6ca590e1c7edaa7c56cac9e3e3c39cf398ca8d4d
+
+ Also update the XSSAuditor to construct the SuffixTree lazily since there are
+ many cases (including the one in this bug) where we were spending a significant
+ amount of time building the SuffixTree and then never querying it.
+
+ * html/parser/XSSAuditor.cpp:
+ (WebCore::XSSAuditor::init):
+ (WebCore::XSSAuditor::decodedHTTPBodySuffixTree):
+ (WebCore::XSSAuditor::isContainedInRequest):
+ * html/parser/XSSAuditor.h:
+ * platform/text/SuffixTree.h:
+ (WebCore::SuffixTree::mightContain):
+ (WebCore::SuffixTree::Node::Node):
+ (WebCore::SuffixTree::Node::~Node):
+ (WebCore::SuffixTree::Node::find):
+ (WebCore::SuffixTree::Node::end):
+ (WebCore::SuffixTree::build):
+ (WebCore::SuffixTree<Codebook>::Node::childAt):
+ (WebCore::SuffixTree::Node::at): Deleted.
+
2018-11-06 Youenn Fablet <[email protected]>
Support onremovetrack for RTCPeerConnection removed tracks
Modified: trunk/Source/WebCore/html/parser/XSSAuditor.cpp (237908 => 237909)
--- trunk/Source/WebCore/html/parser/XSSAuditor.cpp 2018-11-07 02:31:30 UTC (rev 237908)
+++ trunk/Source/WebCore/html/parser/XSSAuditor.cpp 2018-11-07 03:12:18 UTC (rev 237909)
@@ -274,9 +274,6 @@
void XSSAuditor::init(Document* document, XSSAuditorDelegate* auditorDelegate)
{
- const size_t minimumLengthForSuffixTree = 512; // FIXME: Tune this parameter.
- const int suffixTreeDepth = 5;
-
ASSERT(isMainThread());
if (m_state == Initialized)
return;
@@ -316,7 +313,6 @@
if (m_decodedURL.find(isRequiredForInjection) == notFound)
m_decodedURL = String();
- String httpBodyAsString;
if (RefPtr<DocumentLoader> documentLoader = document->frame()->loader().documentLoader()) {
String headerValue = documentLoader->response().httpHeaderField(HTTPHeaderName::XXSSProtection);
String errorDetails;
@@ -344,13 +340,11 @@
auditorDelegate->setReportURL(reportURL.isolatedCopy());
RefPtr<FormData> httpBody = documentLoader->originalRequest().httpBody();
if (httpBody && !httpBody->isEmpty()) {
- httpBodyAsString = httpBody->flattenToString();
+ String httpBodyAsString = httpBody->flattenToString();
if (!httpBodyAsString.isEmpty()) {
m_decodedHTTPBody = canonicalize(httpBodyAsString, TruncationStyle::None);
if (m_decodedHTTPBody.find(isRequiredForInjection) == notFound)
m_decodedHTTPBody = String();
- if (m_decodedHTTPBody.length() >= minimumLengthForSuffixTree)
- m_decodedHTTPBodySuffixTree = std::make_unique<SuffixTree<ASCIICodebook>>(m_decodedHTTPBody, suffixTreeDepth);
}
}
}
@@ -711,6 +705,16 @@
return result;
}
+SuffixTree<ASCIICodebook>* XSSAuditor::decodedHTTPBodySuffixTree()
+{
+ const unsigned minimumLengthForSuffixTree = 512; // FIXME: Tune this parameter.
+ const unsigned suffixTreeDepth = 5;
+
+ if (!m_decodedHTTPBodySuffixTree && m_decodedHTTPBody.length() >= minimumLengthForSuffixTree)
+ m_decodedHTTPBodySuffixTree = std::make_unique<SuffixTree<ASCIICodebook>>(m_decodedHTTPBody, suffixTreeDepth);
+ return m_decodedHTTPBodySuffixTree.get();
+}
+
bool XSSAuditor::isContainedInRequest(const String& decodedSnippet)
{
if (decodedSnippet.isEmpty())
@@ -717,7 +721,8 @@
return false;
if (m_decodedURL.containsIgnoringASCIICase(decodedSnippet))
return true;
- if (m_decodedHTTPBodySuffixTree && !m_decodedHTTPBodySuffixTree->mightContain(decodedSnippet))
+ auto* decodedHTTPBodySuffixTree = this->decodedHTTPBodySuffixTree();
+ if (decodedHTTPBodySuffixTree && !decodedHTTPBodySuffixTree->mightContain(decodedSnippet))
return false;
return m_decodedHTTPBody.containsIgnoringASCIICase(decodedSnippet);
}
Modified: trunk/Source/WebCore/html/parser/XSSAuditor.h (237908 => 237909)
--- trunk/Source/WebCore/html/parser/XSSAuditor.h 2018-11-07 02:31:30 UTC (rev 237908)
+++ trunk/Source/WebCore/html/parser/XSSAuditor.h 2018-11-07 03:12:18 UTC (rev 237909)
@@ -102,6 +102,8 @@
bool isContainedInRequest(const String&);
bool isLikelySafeResource(const String& url);
+ SuffixTree<ASCIICodebook>* decodedHTTPBodySuffixTree();
+
URL m_documentURL;
bool m_isEnabled;
Modified: trunk/Source/WebCore/platform/text/SuffixTree.h (237908 => 237909)
--- trunk/Source/WebCore/platform/text/SuffixTree.h 2018-11-07 02:31:30 UTC (rev 237908)
+++ trunk/Source/WebCore/platform/text/SuffixTree.h 2018-11-07 03:12:18 UTC (rev 237909)
@@ -23,8 +23,7 @@
* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
-#ifndef SuffixTree_h
-#define SuffixTree_h
+#pragma once
#include <wtf/Vector.h>
#include <wtf/text/WTFString.h>
@@ -45,6 +44,8 @@
template<typename Codebook>
class SuffixTree {
+ WTF_MAKE_FAST_ALLOCATED;
+ WTF_MAKE_NONCOPYABLE(SuffixTree)
public:
SuffixTree(const String& text, unsigned depth)
: m_depth(depth)
@@ -58,9 +59,10 @@
Node* current = &m_root;
int limit = std::min(m_depth, query.length());
for (int i = 0; i < limit; ++i) {
- current = current->at(Codebook::codeWord(query[i]));
- if (!current)
+ auto it = current->find(Codebook::codeWord(query[i]));
+ if (it == current->end())
return false;
+ current = it->node;
}
return true;
}
@@ -67,28 +69,40 @@
private:
class Node {
+ WTF_MAKE_FAST_ALLOCATED;
public:
Node(bool isLeaf = false)
- : m_children(Codebook::codeSize, 0)
- , m_isLeaf(isLeaf)
+ : m_isLeaf(isLeaf)
{
}
~Node()
{
- for (unsigned i = 0; i < m_children.size(); ++i) {
- Node* child = m_children.at(i);
+ for (auto& entry : m_children) {
+ auto* child = entry.node;
if (child && !child->m_isLeaf)
delete child;
}
}
- Node*& at(int codeWord) { return m_children.at(codeWord); }
+ Node*& childAt(int codeWord);
+ auto find(int codeWord)
+ {
+ return std::find_if(m_children.begin(), m_children.end(), [codeWord](auto& entry) {
+ return entry.codeWord == codeWord;
+ });
+ }
+
+ auto end() { return m_children.end(); }
+
private:
- typedef Vector<Node*, Codebook::codeSize> ChildrenVector;
+ struct ChildWithCodeWord {
+ int codeWord;
+ Node* node;
+ };
- ChildrenVector m_children;
+ Vector<ChildWithCodeWord> m_children;
bool m_isLeaf;
};
@@ -99,7 +113,7 @@
unsigned limit = std::min(base + m_depth, text.length());
for (unsigned offset = 0; base + offset < limit; ++offset) {
ASSERT(current != &m_leaf);
- Node*& child = current->at(Codebook::codeWord(text[base + offset]));
+ Node*& child = current->childAt(Codebook::codeWord(text[base + offset]));
if (!child)
child = base + offset + 1 == limit ? &m_leaf : new Node();
current = child;
@@ -116,6 +130,14 @@
Node m_leaf;
};
+template<typename Codebook>
+inline auto SuffixTree<Codebook>::Node::childAt(int codeWord) -> Node*&
+{
+ auto it = find(codeWord);
+ if (it != m_children.end())
+ return it->node;
+ m_children.append(ChildWithCodeWord { codeWord, nullptr });
+ return m_children.last().node;
+}
+
} // namespace WebCore
-
-#endif // SuffixTree_h
_______________________________________________
webkit-changes mailing list
[email protected]
https://lists.webkit.org/mailman/listinfo/webkit-changes
