2011-02-03 Adam Barth <abarth@webkit.org>

        Reviewed by Eric Seidel.

        Make XSSFilter go fast by adding a SuffixTree
        https://bugs.webkit.org/show_bug.cgi?id=53665

        The SuffixTree lets us quickly reject snippets if the POST data is
        large (because we can avoid a linear scan over the POST data).

        * html/parser/XSSFilter.cpp:
        (WebCore::XSSFilter::init):
        (WebCore::XSSFilter::isContainedInRequest):
        * html/parser/XSSFilter.h:

git-svn-id: http://svn.webkit.org/repository/webkit/trunk@77560 268f45cc-cd09-0410-ab3c-d52691b4dbfc

diff --git a/Source/WebCore/ChangeLog b/Source/WebCore/ChangeLog
index ed82ef815449f06d3911ae175ea9714fe0c52478..263418f8d55687cb57baf1285dfa62dce4958d11 100644 (file)
--- a/Source/WebCore/ChangeLog
+++ b/Source/WebCore/ChangeLog
@@ -1,3 +1,18 @@
+2011-02-03  Adam Barth  <abarth@webkit.org>
+
+        Reviewed by Eric Seidel.
+
+        Make XSSFilter go fast by adding a SuffixTree
+        https://bugs.webkit.org/show_bug.cgi?id=53665
+
+        The SuffixTree lets us quickly reject snippets if the POST data is
+        large (because we can avoid a linear scan over the POST data).
+
+        * html/parser/XSSFilter.cpp:
+        (WebCore::XSSFilter::init):
+        (WebCore::XSSFilter::isContainedInRequest):
+        * html/parser/XSSFilter.h:
+
 2011-02-03  Mihai Parparita  <mihaip@chromium.org>
 
         Reviewed by Alexey Proskuryakov.

diff --git a/Source/WebCore/html/parser/XSSFilter.cpp b/Source/WebCore/html/parser/XSSFilter.cpp
index c0bee0eb863b9c64873e2b3dd5272ae0897c7811..71a23d9f799edfa74c5dc5873dc52cdab487f1b0 100644 (file)
--- a/Source/WebCore/html/parser/XSSFilter.cpp
+++ b/Source/WebCore/html/parser/XSSFilter.cpp
@@ -142,6 +142,9 @@ XSSFilter::XSSFilter(HTMLDocumentParser* parser)
 
 void XSSFilter::init()
 {
+    const size_t miniumLengthForSuffixTree = 512; // FIXME: Tune this parameter.
+    const int suffixTreeDepth = 5;
+
     ASSERT(m_state == Uninitialized);
     m_state = Initial;
 
@@ -174,6 +177,8 @@ void XSSFilter::init()
             m_decodedHTTPBody = decodeURL(httpBody->flattenToString(), encoding);
             if (m_decodedHTTPBody.find(isRequiredForInjection, 0) == notFound)
                 m_decodedHTTPBody = String();
+            if (m_decodedHTTPBody.length() >= miniumLengthForSuffixTree)
+                m_decodedHTTPBodySuffixTree = adoptPtr(new SuffixTree<ASCIICodebook>(m_decodedHTTPBody, suffixTreeDepth));
         }
     }
 
@@ -427,8 +432,11 @@ bool XSSFilter::isContainedInRequest(const String& snippet)
     ASSERT(!snippet.isEmpty());
     String canonicalizedSnippet = canonicalize(snippet);
     ASSERT(!canonicalizedSnippet.isEmpty());
-    return m_decodedURL.find(canonicalizedSnippet, 0, false) != notFound
-        || m_decodedHTTPBody.find(canonicalizedSnippet, 0, false) != notFound;
+    if (m_decodedURL.find(canonicalizedSnippet, 0, false) != notFound)
+        return true;
+    if (m_decodedHTTPBodySuffixTree && !m_decodedHTTPBodySuffixTree->mightContain(canonicalizedSnippet))
+        return false;
+    return m_decodedHTTPBody.find(canonicalizedSnippet, 0, false) != notFound;
 }
 
 bool XSSFilter::isSameOriginResource(const String& url)

diff --git a/Source/WebCore/html/parser/XSSFilter.h b/Source/WebCore/html/parser/XSSFilter.h
index 22296e1d377ac913f32adb6f2759dccf3d57bd38..2c7d42885d9636709f7887b2944da14fc6baacce 100644 (file)
--- a/Source/WebCore/html/parser/XSSFilter.h
+++ b/Source/WebCore/html/parser/XSSFilter.h
@@ -28,6 +28,7 @@
 
 #include "HTMLToken.h"
 #include "HTTPParsers.h"
+#include "SuffixTree.h"
 
 namespace WebCore {
 
@@ -75,6 +76,7 @@ private:
 
     String m_decodedURL;
     String m_decodedHTTPBody;
+    OwnPtr<SuffixTree<ASCIICodebook> > m_decodedHTTPBodySuffixTree;
 
     State m_state;
     String m_cachedSnippet;