Extracting page shingle hashes for similarity detection.

chrome/renderer/safe_browsing/phishing_term_feature_extractor.cc

 // Copyright (c) 2012 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "chrome/renderer/safe_browsing/phishing_term_feature_extractor.h"
 
 #include <list>
 #include <map>
 
 #include "base/bind.h"
@@ skipping 27 matching lines @@
 const int PhishingTermFeatureExtractor::kMaxTotalTimeMs = 500;
 
 // The maximum size of the negative word cache.
 const int PhishingTermFeatureExtractor::kMaxNegativeWordCacheSize = 1000;
 
 // All of the state pertaining to the current feature extraction.
 struct PhishingTermFeatureExtractor::ExtractionState {
   // Stores up to max_words_per_term_ previous words separated by spaces.
   std::string previous_words;
 
+  // Stores the current shingle after a new word is processed and added in.
+  std::string current_shingle;
+
+  // Stores the sizes of the words in current_shingle. Note: the size includes
+  // the space after each word. In other words, the sum of all sizes in this
+  // list is equal to the length of current_shingle.
+  std::list<size_t> shingle_word_sizes;
+
   // Stores the sizes of the words in previous_words.  Note: the size includes
   // the space after each word.  In other words, the sum of all sizes in this
   // list is equal to the length of previous_words.
   std::list<size_t> previous_word_sizes;
 
   // An iterator for word breaking.
   UBreakIterator* iterator;
 
   // Our current position in the text that was passed to the ExtractionState
   // constructor, speciailly, the most recent break position returned by our
@@ skipping 30 matching lines @@
       ubrk_close(iterator);
     }
   }
 };
 
 PhishingTermFeatureExtractor::PhishingTermFeatureExtractor(
     const base::hash_set<std::string>* page_term_hashes,
     const base::hash_set<uint32>* page_word_hashes,
     size_t max_words_per_term,
     uint32 murmurhash3_seed,
+    size_t max_shingles_per_page,
+    size_t shingle_size,
     FeatureExtractorClock* clock)
     : page_term_hashes_(page_term_hashes),
       page_word_hashes_(page_word_hashes),
       max_words_per_term_(max_words_per_term),
       murmurhash3_seed_(murmurhash3_seed),
+      max_shingles_per_page_(max_shingles_per_page),
+      shingle_size_(shingle_size),
       negative_word_cache_(kMaxNegativeWordCacheSize),
       clock_(clock),
       weak_factory_(this) {
   Clear();
 }
 
 PhishingTermFeatureExtractor::~PhishingTermFeatureExtractor() {
   // The RenderView should have called CancelPendingExtraction() before
   // we are destroyed.
   CheckNoPendingExtraction();
 }
 
 void PhishingTermFeatureExtractor::ExtractFeatures(
     const base::string16* page_text,
     FeatureMap* features,
+    std::set<uint32>* shingle_hashes,
     const DoneCallback& done_callback) {
   // The RenderView should have called CancelPendingExtraction() before
   // starting a new extraction, so DCHECK this.
   CheckNoPendingExtraction();
   // However, in an opt build, we will go ahead and clean up the pending
   // extraction so that we can start in a known state.
   CancelPendingExtraction();
 
   page_text_ = page_text;
   features_ = features;
+  shingle_hashes_ = shingle_hashes,
   done_callback_ = done_callback;
 
   state_.reset(new ExtractionState(*page_text_, clock_->Now()));
   base::MessageLoop::current()->PostTask(
       FROM_HERE,
       base::Bind(&PhishingTermFeatureExtractor::ExtractFeaturesWithTimeout,
                  weak_factory_.GetWeakPtr()));
 }
 
 void PhishingTermFeatureExtractor::CancelPendingExtraction() {
@@ skipping 65 matching lines @@
         return;
       }
       // Otherwise, continue.
     }
   }
   RunCallback(true);
 }
 
 void PhishingTermFeatureExtractor::HandleWord(
     const base::StringPiece16& word) {
+  // First, extract shingle hashes. We check the size of shingle_hashes_ first
+  // to skip as soon as we reach |max_shingles_per_page_|.
+  std::string word_lower;
+  if (shingle_hashes_->size() < max_shingles_per_page_) {

[noelutz, 2014/05/06 21:40:18]

I think we want to keep the min 200 shingles so that code isn't quite right. 
You should always add the new shingle and then remove the largest one if we have
more than max_shingles_per_page_ shingles in the set.

[zysxqn, 2014/05/07 19:29:19]

I know on the server side experiment we use min 200 hashes. But for the sake of
computing similarity I don't see any problem with keeping first 200 hashes, as
long as the extracting logic is the same among all pages. Am I miss anything?

[zysxqn, 2014/05/09 21:34:24]

Done.

[mattm, 2014/05/09 23:28:10]

Have you tested if doing it for the whole text has any notable performance
impact? (Not just the hashing, but the extra lowercasing and utf conversions
which are called expensive below.)

[noelutz, 2014/05/10 01:01:20]

+1 on performance testing.  Could you add a histogram measuring how much time we
spend doing that?

+    word_lower = base::UTF16ToUTF8(base::i18n::ToLower(word));
+    state_->current_shingle.append(word_lower + " ");
+    state_->shingle_word_sizes.push_back(word_lower.size() + 1);
+    if (state_->shingle_word_sizes.size() == shingle_size_) {
+      shingle_hashes_->insert(
+          MurmurHash3String(state_->current_shingle, murmurhash3_seed_));
+      state_->current_shingle.erase(0, state_->shingle_word_sizes.front());
+      state_->shingle_word_sizes.pop_front();
+    }
+  }
+
+  // Next, extract page terms.
+  //
   // Quickest out if we have seen this word before and know that it's not
   // part of any term. This avoids the lowercasing and UTF conversion, both of
   // which are relatively expensive.
   if (negative_word_cache_.Get(word) != negative_word_cache_.end()) {
     // We know we're no longer in a possible n-gram, so clear the previous word
     // state.
     state_->previous_words.clear();
     state_->previous_word_sizes.clear();
     return;
   }
 
-  std::string word_lower = base::UTF16ToUTF8(base::i18n::ToLower(word));
+  if (word_lower.empty()) {
+    word_lower = base::UTF16ToUTF8(base::i18n::ToLower(word));
+  }
   uint32 word_hash = MurmurHash3String(word_lower, murmurhash3_seed_);
 
   // Quick out if the word is not part of any term, which is the common case.
   if (page_word_hashes_->find(word_hash) == page_word_hashes_->end()) {
     // Word doesn't exist in our terms so we can clear the n-gram state.
     state_->previous_words.clear();
     state_->previous_word_sizes.clear();
     // Insert into negative cache so that we don't try this again.
     negative_word_cache_.Put(word, true);
     return;
@@ skipping 60 matching lines @@
                       clock_->Now() - state_->start_time);
 
   DCHECK(!done_callback_.is_null());
   done_callback_.Run(success);
   Clear();
 }
 
 void PhishingTermFeatureExtractor::Clear() {
   page_text_ = NULL;
   features_ = NULL;
+  shingle_hashes_ = NULL;
   done_callback_.Reset();
   state_.reset(NULL);
   negative_word_cache_.Clear();
 }
 
 }  // namespace safe_browsing