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/case_conversion.h"
  13 #include "base/logging.h"
  14 #include "base/message_loop/message_loop.h"
  15 #include "base/metrics/histogram.h"
  16 #include "base/strings/utf_string_conversions.h"
  17 #include "base/time/time.h"
  18 #include "chrome/renderer/safe_browsing/feature_extractor_clock.h"
  19 #include "chrome/renderer/safe_browsing/features.h"
  20 #include "chrome/renderer/safe_browsing/murmurhash3_util.h"
  21 #include "crypto/sha2.h"
  22 #include "third_party/icu/source/common/unicode/ubrk.h"
  23 #include "ui/base/l10n/l10n_util.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 // The maximum size of the negative word cache.
  41 const int PhishingTermFeatureExtractor::kMaxNegativeWordCacheSize = 1000;
  42
  43 // All of the state pertaining to the current feature extraction.
  44 struct PhishingTermFeatureExtractor::ExtractionState {
  45   // Stores up to max_words_per_term_ previous words separated by spaces.
  46   std::string previous_words;
  47
  48   // Stores the sizes of the words in previous_words.  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 previous_words.
  51   std::list<size_t> previous_word_sizes;
  52
  53   // An iterator for word breaking.
  54   UBreakIterator* iterator;
  55
  56   // Our current position in the text that was passed to the ExtractionState
  57   // constructor, speciailly, the most recent break position returned by our
  58   // iterator.
  59   int position;
  60
  61   // True if position has been initialized.
  62   bool position_initialized;
  63
  64   // The time at which we started feature extraction for the current page.
  65   base::TimeTicks start_time;
  66
  67   // The number of iterations we've done for the current extraction.
  68   int num_iterations;
  69
  70   ExtractionState(const string16& text, base::TimeTicks start_time_ticks)
  71       : position(-1),
  72         position_initialized(false),
  73         start_time(start_time_ticks),
  74         num_iterations(0) {
  75     UErrorCode status = U_ZERO_ERROR;
  76     // TODO(bryner): We should pass in the language for the document.
  77     iterator = ubrk_open(UBRK_WORD, NULL,
  78                          text.data(), text.size(),
  79                          &status);
  80     if (U_FAILURE(status)) {
  81       DLOG(ERROR) << "ubrk_open failed: " << status;
  82       iterator = NULL;
  83     }
  84   }
  85
  86   ~ExtractionState() {
  87     if (iterator) {
  88       ubrk_close(iterator);
  89     }
  90   }
  91 };
  92
  93 PhishingTermFeatureExtractor::PhishingTermFeatureExtractor(
  94     const base::hash_set<std::string>* page_term_hashes,
  95     const base::hash_set<uint32>* page_word_hashes,
  96     size_t max_words_per_term,
  97     uint32 murmurhash3_seed,
  98     FeatureExtractorClock* clock)
  99     : page_term_hashes_(page_term_hashes),
 100       page_word_hashes_(page_word_hashes),
 101       max_words_per_term_(max_words_per_term),
 102       murmurhash3_seed_(murmurhash3_seed),
 103       negative_word_cache_(kMaxNegativeWordCacheSize),
 104       clock_(clock),
 105       weak_factory_(this) {
 106   Clear();
 107 }
 108
 109 PhishingTermFeatureExtractor::~PhishingTermFeatureExtractor() {
 110   // The RenderView should have called CancelPendingExtraction() before
 111   // we are destroyed.
 112   CheckNoPendingExtraction();
 113 }
 114
 115 void PhishingTermFeatureExtractor::ExtractFeatures(
 116     const string16* page_text,
 117     FeatureMap* features,
 118     const DoneCallback& done_callback) {
 119   // The RenderView should have called CancelPendingExtraction() before
 120   // starting a new extraction, so DCHECK this.
 121   CheckNoPendingExtraction();
 122   // However, in an opt build, we will go ahead and clean up the pending
 123   // extraction so that we can start in a known state.
 124   CancelPendingExtraction();
 125
 126   page_text_ = page_text;
 127   features_ = features;
 128   done_callback_ = done_callback;
 129
 130   state_.reset(new ExtractionState(*page_text_, clock_->Now()));
 131   base::MessageLoop::current()->PostTask(
 132       FROM_HERE,
 133       base::Bind(&PhishingTermFeatureExtractor::ExtractFeaturesWithTimeout,
 134                  weak_factory_.GetWeakPtr()));
 135 }
 136
 137 void PhishingTermFeatureExtractor::CancelPendingExtraction() {
 138   // Cancel any pending callbacks, and clear our state.
 139   weak_factory_.InvalidateWeakPtrs();
 140   Clear();
 141 }
 142
 143 void PhishingTermFeatureExtractor::ExtractFeaturesWithTimeout() {
 144   DCHECK(state_.get());
 145   ++state_->num_iterations;
 146   base::TimeTicks current_chunk_start_time = clock_->Now();
 147
 148   if (!state_->iterator) {
 149     // We failed to initialize the break iterator, so stop now.
 150     UMA_HISTOGRAM_COUNTS("SBClientPhishing.TermFeatureBreakIterError", 1);
 151     RunCallback(false);
 152     return;
 153   }
 154
 155   if (!state_->position_initialized) {
 156     state_->position = ubrk_first(state_->iterator);
 157     if (state_->position == UBRK_DONE) {
 158       // No words present, so we're done.
 159       RunCallback(true);
 160       return;
 161     }
 162     state_->position_initialized = true;
 163   }
 164
 165   int num_words = 0;
 166   for (int next = ubrk_next(state_->iterator);
 167        next != UBRK_DONE; next = ubrk_next(state_->iterator)) {
 168     if (ubrk_getRuleStatus(state_->iterator) != UBRK_WORD_NONE) {
 169       // next is now positioned at the end of a word.
 170       HandleWord(base::StringPiece16(page_text_->data() + state_->position,
 171                                      next - state_->position));
 172       ++num_words;
 173     }
 174     state_->position = next;
 175
 176     if (num_words >= kClockCheckGranularity) {
 177       num_words = 0;
 178       base::TimeTicks now = clock_->Now();
 179       if (now - state_->start_time >=
 180           base::TimeDelta::FromMilliseconds(kMaxTotalTimeMs)) {
 181         DLOG(ERROR) << "Feature extraction took too long, giving up";
 182         // We expect this to happen infrequently, so record when it does.
 183         UMA_HISTOGRAM_COUNTS("SBClientPhishing.TermFeatureTimeout", 1);
 184         RunCallback(false);
 185         return;
 186       }
 187       base::TimeDelta chunk_elapsed = now - current_chunk_start_time;
 188       if (chunk_elapsed >=
 189           base::TimeDelta::FromMilliseconds(kMaxTimePerChunkMs)) {
 190         // The time limit for the current chunk is up, so post a task to
 191         // continue extraction.
 192         //
 193         // Record how much time we actually spent on the chunk.  If this is
 194         // much higher than kMaxTimePerChunkMs, we may need to adjust the
 195         // clock granularity.
 196         UMA_HISTOGRAM_TIMES("SBClientPhishing.TermFeatureChunkTime",
 197                             chunk_elapsed);
 198         base::MessageLoop::current()->PostTask(
 199             FROM_HERE,
 200             base::Bind(
 201                 &PhishingTermFeatureExtractor::ExtractFeaturesWithTimeout,
 202                 weak_factory_.GetWeakPtr()));
 203         return;
 204       }
 205       // Otherwise, continue.
 206     }
 207   }
 208   RunCallback(true);
 209 }
 210
 211 void PhishingTermFeatureExtractor::HandleWord(
 212     const base::StringPiece16& word) {
 213   // Quickest out if we have seen this word before and know that it's not
 214   // part of any term. This avoids the lowercasing and UTF conversion, both of
 215   // which are relatively expensive.
 216   if (negative_word_cache_.Get(word) != negative_word_cache_.end()) {
 217     // We know we're no longer in a possible n-gram, so clear the previous word
 218     // state.
 219     state_->previous_words.clear();
 220     state_->previous_word_sizes.clear();
 221     return;
 222   }
 223
 224   std::string word_lower = UTF16ToUTF8(base::i18n::ToLower(word));
 225   uint32 word_hash = MurmurHash3String(word_lower, murmurhash3_seed_);
 226
 227   // Quick out if the word is not part of any term, which is the common case.
 228   if (page_word_hashes_->find(word_hash) == page_word_hashes_->end()) {
 229     // Word doesn't exist in our terms so we can clear the n-gram state.
 230     state_->previous_words.clear();
 231     state_->previous_word_sizes.clear();
 232     // Insert into negative cache so that we don't try this again.
 233     negative_word_cache_.Put(word, true);
 234     return;
 235   }
 236
 237   // Find all of the n-grams that we need to check and compute their SHA-256
 238   // hashes.
 239   std::map<std::string /* hash */, std::string /* plaintext */>
 240       hashes_to_check;
 241   hashes_to_check[crypto::SHA256HashString(word_lower)] = word_lower;
 242
 243   // Combine the new word with the previous words to find additional n-grams.
 244   // Note that we don't yet add the new word length to previous_word_sizes,
 245   // since we don't want to compute the hash for the word by itself again.
 246   //
 247   state_->previous_words.append(word_lower);
 248   std::string current_term = state_->previous_words;
 249   for (std::list<size_t>::iterator it = state_->previous_word_sizes.begin();
 250        it != state_->previous_word_sizes.end(); ++it) {
 251     hashes_to_check[crypto::SHA256HashString(current_term)] = current_term;
 252     current_term.erase(0, *it);
 253   }
 254
 255   // Add features for any hashes that match page_term_hashes_.
 256   for (std::map<std::string, std::string>::iterator it =
 257            hashes_to_check.begin();
 258        it != hashes_to_check.end(); ++it) {
 259     if (page_term_hashes_->find(it->first) != page_term_hashes_->end()) {
 260       features_->AddBooleanFeature(features::kPageTerm + it->second);
 261     }
 262   }
 263
 264   // Now that we have handled the current word, we have to add a space at the
 265   // end of it, and add the new word's size (including the space) to
 266   // previous_word_sizes.  Note: it's possible that the document language
 267   // doesn't use ASCII spaces to separate words.  That's fine though, we just
 268   // need to be consistent with how the model is generated.
 269   state_->previous_words.append(" ");
 270   state_->previous_word_sizes.push_back(word_lower.size() + 1);
 271
 272   // Cap the number of previous words.
 273   if (state_->previous_word_sizes.size() >= max_words_per_term_) {
 274     state_->previous_words.erase(0, state_->previous_word_sizes.front());
 275     state_->previous_word_sizes.pop_front();
 276   }
 277 }
 278
 279 void PhishingTermFeatureExtractor::CheckNoPendingExtraction() {
 280   DCHECK(done_callback_.is_null());
 281   DCHECK(!state_.get());
 282   if (!done_callback_.is_null() || state_.get()) {
 283     LOG(ERROR) << "Extraction in progress, missing call to "
 284                << "CancelPendingExtraction";
 285   }
 286 }
 287
 288 void PhishingTermFeatureExtractor::RunCallback(bool success) {
 289   // Record some timing stats that we can use to evaluate feature extraction
 290   // performance.  These include both successful and failed extractions.
 291   DCHECK(state_.get());
 292   UMA_HISTOGRAM_COUNTS("SBClientPhishing.TermFeatureIterations",
 293                        state_->num_iterations);
 294   UMA_HISTOGRAM_TIMES("SBClientPhishing.TermFeatureTotalTime",
 295                       clock_->Now() - state_->start_time);
 296
 297   DCHECK(!done_callback_.is_null());
 298   done_callback_.Run(success);
 299   Clear();
 300 }
 301
 302 void PhishingTermFeatureExtractor::Clear() {
 303   page_text_ = NULL;
 304   features_ = NULL;
 305   done_callback_.Reset();
 306   state_.reset(NULL);
 307   negative_word_cache_.Clear();
 308 }
 309
 310 }  // namespace safe_browsing