src/chrome/renderer/safe_browsing/phishing_term_feature_extractor.cc

   1 // Copyright (c) 2012 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "chrome/renderer/safe_browsing/phishing_term_feature_extractor.h"
   6
   7 #include <list>
   8 #include <map>
   9
  10 #include "base/bind.h"
  11 #include "base/compiler_specific.h"
  12 #include "base/i18n/break_iterator.h"
  13 #include "base/i18n/case_conversion.h"
  14 #include "base/logging.h"
  15 #include "base/memory/scoped_ptr.h"
  16 #include "base/message_loop/message_loop.h"
  17 #include "base/metrics/histogram.h"
  18 #include "base/strings/utf_string_conversions.h"
  19 #include "base/time/time.h"
  20 #include "chrome/renderer/safe_browsing/feature_extractor_clock.h"
  21 #include "chrome/renderer/safe_browsing/features.h"
  22 #include "chrome/renderer/safe_browsing/murmurhash3_util.h"
  23 #include "crypto/sha2.h"
  24
  25 namespace safe_browsing {
  26
  27 // This time should be short enough that it doesn't noticeably disrupt the
  28 // user's interaction with the page.
  29 const int PhishingTermFeatureExtractor::kMaxTimePerChunkMs = 10;
  30
  31 // Experimenting shows that we get a reasonable gain in performance by
  32 // increasing this up to around 10, but there's not much benefit in
  33 // increasing it past that.
  34 const int PhishingTermFeatureExtractor::kClockCheckGranularity = 5;
  35
  36 // This should be longer than we expect feature extraction to take on any
  37 // actual phishing page.
  38 const int PhishingTermFeatureExtractor::kMaxTotalTimeMs = 500;
  39
  40 // All of the state pertaining to the current feature extraction.
  41 struct PhishingTermFeatureExtractor::ExtractionState {
  42   // Stores up to max_words_per_term_ previous words separated by spaces.
  43   std::string previous_words;
  44
  45   // Stores the current shingle after a new word is processed and added in.
  46   std::string current_shingle;
  47
  48   // Stores the sizes of the words in current_shingle. Note: the size includes
  49   // the space after each word. In other words, the sum of all sizes in this
  50   // list is equal to the length of current_shingle.
  51   std::list<size_t> shingle_word_sizes;
  52
  53   // Stores the sizes of the words in previous_words.  Note: the size includes
  54   // the space after each word.  In other words, the sum of all sizes in this
  55   // list is equal to the length of previous_words.
  56   std::list<size_t> previous_word_sizes;
  57
  58   // An iterator for word breaking.
  59   scoped_ptr<base::i18n::BreakIterator> iterator;
  60
  61   // The time at which we started feature extraction for the current page.
  62   base::TimeTicks start_time;
  63
  64   // The number of iterations we've done for the current extraction.
  65   int num_iterations;
  66
  67   ExtractionState(const base::string16& text, base::TimeTicks start_time_ticks)
  68       : start_time(start_time_ticks),
  69         num_iterations(0) {
  70
  71     scoped_ptr<base::i18n::BreakIterator> i(
  72         new base::i18n::BreakIterator(
  73             text, base::i18n::BreakIterator::BREAK_WORD));
  74
  75     if (i->Init()) {
  76       iterator = i.Pass();
  77     } else {
  78       DLOG(ERROR) << "failed to open iterator";
  79     }
  80   }
  81 };
  82
  83 PhishingTermFeatureExtractor::PhishingTermFeatureExtractor(
  84     const base::hash_set<std::string>* page_term_hashes,
  85     const base::hash_set<uint32>* page_word_hashes,
  86     size_t max_words_per_term,
  87     uint32 murmurhash3_seed,
  88     size_t max_shingles_per_page,
  89     size_t shingle_size,
  90     FeatureExtractorClock* clock)
  91     : page_term_hashes_(page_term_hashes),
  92       page_word_hashes_(page_word_hashes),
  93       max_words_per_term_(max_words_per_term),
  94       murmurhash3_seed_(murmurhash3_seed),
  95       max_shingles_per_page_(max_shingles_per_page),
  96       shingle_size_(shingle_size),
  97       clock_(clock),
  98       weak_factory_(this) {
  99   Clear();
 100 }
 101
 102 PhishingTermFeatureExtractor::~PhishingTermFeatureExtractor() {
 103   // The RenderView should have called CancelPendingExtraction() before
 104   // we are destroyed.
 105   CheckNoPendingExtraction();
 106 }
 107
 108 void PhishingTermFeatureExtractor::ExtractFeatures(
 109     const base::string16* page_text,
 110     FeatureMap* features,
 111     std::set<uint32>* shingle_hashes,
 112     const DoneCallback& done_callback) {
 113   // The RenderView should have called CancelPendingExtraction() before
 114   // starting a new extraction, so DCHECK this.
 115   CheckNoPendingExtraction();
 116   // However, in an opt build, we will go ahead and clean up the pending
 117   // extraction so that we can start in a known state.
 118   CancelPendingExtraction();
 119
 120   page_text_ = page_text;
 121   features_ = features;
 122   shingle_hashes_ = shingle_hashes,
 123   done_callback_ = done_callback;
 124
 125   state_.reset(new ExtractionState(*page_text_, clock_->Now()));
 126   base::MessageLoop::current()->PostTask(
 127       FROM_HERE,
 128       base::Bind(&PhishingTermFeatureExtractor::ExtractFeaturesWithTimeout,
 129                  weak_factory_.GetWeakPtr()));
 130 }
 131
 132 void PhishingTermFeatureExtractor::CancelPendingExtraction() {
 133   // Cancel any pending callbacks, and clear our state.
 134   weak_factory_.InvalidateWeakPtrs();
 135   Clear();
 136 }
 137
 138 void PhishingTermFeatureExtractor::ExtractFeaturesWithTimeout() {
 139   DCHECK(state_.get());
 140   ++state_->num_iterations;
 141   base::TimeTicks current_chunk_start_time = clock_->Now();
 142
 143   if (!state_->iterator.get()) {
 144     // We failed to initialize the break iterator, so stop now.
 145     UMA_HISTOGRAM_COUNTS("SBClientPhishing.TermFeatureBreakIterError", 1);
 146     RunCallback(false);
 147     return;
 148   }
 149
 150   int num_words = 0;
 151   while (state_->iterator->Advance()) {
 152     if (state_->iterator->IsWord()) {
 153       const size_t start = state_->iterator->prev();
 154       const size_t length = state_->iterator->pos() - start;
 155       HandleWord(base::StringPiece16(page_text_->data() + start, length));
 156       ++num_words;
 157     }
 158
 159     if (num_words >= kClockCheckGranularity) {
 160       num_words = 0;
 161       base::TimeTicks now = clock_->Now();
 162       if (now - state_->start_time >=
 163           base::TimeDelta::FromMilliseconds(kMaxTotalTimeMs)) {
 164         DLOG(ERROR) << "Feature extraction took too long, giving up";
 165         // We expect this to happen infrequently, so record when it does.
 166         UMA_HISTOGRAM_COUNTS("SBClientPhishing.TermFeatureTimeout", 1);
 167         RunCallback(false);
 168         return;
 169       }
 170       base::TimeDelta chunk_elapsed = now - current_chunk_start_time;
 171       if (chunk_elapsed >=
 172           base::TimeDelta::FromMilliseconds(kMaxTimePerChunkMs)) {
 173         // The time limit for the current chunk is up, so post a task to
 174         // continue extraction.
 175         //
 176         // Record how much time we actually spent on the chunk.  If this is
 177         // much higher than kMaxTimePerChunkMs, we may need to adjust the
 178         // clock granularity.
 179         UMA_HISTOGRAM_TIMES("SBClientPhishing.TermFeatureChunkTime",
 180                             chunk_elapsed);
 181         base::MessageLoop::current()->PostTask(
 182             FROM_HERE,
 183             base::Bind(
 184                 &PhishingTermFeatureExtractor::ExtractFeaturesWithTimeout,
 185                 weak_factory_.GetWeakPtr()));
 186         return;
 187       }
 188       // Otherwise, continue.
 189     }
 190   }
 191   RunCallback(true);
 192 }
 193
 194 void PhishingTermFeatureExtractor::HandleWord(
 195     const base::StringPiece16& word) {
 196   // First, extract shingle hashes.
 197   const std::string& word_lower = base::UTF16ToUTF8(base::i18n::ToLower(word));
 198   state_->current_shingle.append(word_lower + " ");
 199   state_->shingle_word_sizes.push_back(word_lower.size() + 1);
 200   if (state_->shingle_word_sizes.size() == shingle_size_) {
 201     shingle_hashes_->insert(
 202         MurmurHash3String(state_->current_shingle, murmurhash3_seed_));
 203     state_->current_shingle.erase(0, state_->shingle_word_sizes.front());
 204     state_->shingle_word_sizes.pop_front();
 205   }
 206   // Check if the size of shingle hashes is over the limit.
 207   if (shingle_hashes_->size() > max_shingles_per_page_) {
 208     // Pop the largest one.
 209     std::set<uint32>::iterator it = shingle_hashes_->end();
 210     shingle_hashes_->erase(--it);
 211   }
 212
 213   // Next, extract page terms.
 214   uint32 word_hash = MurmurHash3String(word_lower, murmurhash3_seed_);
 215
 216   // Quick out if the word is not part of any term, which is the common case.
 217   if (page_word_hashes_->find(word_hash) == page_word_hashes_->end()) {
 218     // Word doesn't exist in our terms so we can clear the n-gram state.
 219     state_->previous_words.clear();
 220     state_->previous_word_sizes.clear();
 221     return;
 222   }
 223
 224   // Find all of the n-grams that we need to check and compute their SHA-256
 225   // hashes.
 226   std::map<std::string /* hash */, std::string /* plaintext */>
 227       hashes_to_check;
 228   hashes_to_check[crypto::SHA256HashString(word_lower)] = word_lower;
 229
 230   // Combine the new word with the previous words to find additional n-grams.
 231   // Note that we don't yet add the new word length to previous_word_sizes,
 232   // since we don't want to compute the hash for the word by itself again.
 233   //
 234   state_->previous_words.append(word_lower);
 235   std::string current_term = state_->previous_words;
 236   for (std::list<size_t>::iterator it = state_->previous_word_sizes.begin();
 237        it != state_->previous_word_sizes.end(); ++it) {
 238     hashes_to_check[crypto::SHA256HashString(current_term)] = current_term;
 239     current_term.erase(0, *it);
 240   }
 241
 242   // Add features for any hashes that match page_term_hashes_.
 243   for (std::map<std::string, std::string>::iterator it =
 244            hashes_to_check.begin();
 245        it != hashes_to_check.end(); ++it) {
 246     if (page_term_hashes_->find(it->first) != page_term_hashes_->end()) {
 247       features_->AddBooleanFeature(features::kPageTerm + it->second);
 248     }
 249   }
 250
 251   // Now that we have handled the current word, we have to add a space at the
 252   // end of it, and add the new word's size (including the space) to
 253   // previous_word_sizes.  Note: it's possible that the document language
 254   // doesn't use ASCII spaces to separate words.  That's fine though, we just
 255   // need to be consistent with how the model is generated.
 256   state_->previous_words.append(" ");
 257   state_->previous_word_sizes.push_back(word_lower.size() + 1);
 258
 259   // Cap the number of previous words.
 260   if (state_->previous_word_sizes.size() >= max_words_per_term_) {
 261     state_->previous_words.erase(0, state_->previous_word_sizes.front());
 262     state_->previous_word_sizes.pop_front();
 263   }
 264 }
 265
 266 void PhishingTermFeatureExtractor::CheckNoPendingExtraction() {
 267   DCHECK(done_callback_.is_null());
 268   DCHECK(!state_.get());
 269   if (!done_callback_.is_null() || state_.get()) {
 270     LOG(ERROR) << "Extraction in progress, missing call to "
 271                << "CancelPendingExtraction";
 272   }
 273 }
 274
 275 void PhishingTermFeatureExtractor::RunCallback(bool success) {
 276   // Record some timing stats that we can use to evaluate feature extraction
 277   // performance.  These include both successful and failed extractions.
 278   DCHECK(state_.get());
 279   UMA_HISTOGRAM_COUNTS("SBClientPhishing.TermFeatureIterations",
 280                        state_->num_iterations);
 281   UMA_HISTOGRAM_TIMES("SBClientPhishing.TermFeatureTotalTime",
 282                       clock_->Now() - state_->start_time);
 283
 284   DCHECK(!done_callback_.is_null());
 285   done_callback_.Run(success);
 286   Clear();
 287 }
 288
 289 void PhishingTermFeatureExtractor::Clear() {
 290   page_text_ = NULL;
 291   features_ = NULL;
 292   shingle_hashes_ = NULL;
 293   done_callback_.Reset();
 294   state_.reset(NULL);
 295 }
 296
 297 }  // namespace safe_browsing