Knock out injected safe-browsing prefixes.

chrome/browser/safe_browsing/safe_browsing_database.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/browser/safe_browsing/safe_browsing_database.h"
 
 #include <algorithm>
 #include <iterator>
 
 #include "base/bind.h"
@@ skipping 167 matching lines @@
       if (prefix == iter->prefix &&
           GetListIdBit(iter->chunk_id) == list_bit) {
         prefix_hits->push_back(prefix);
         found_match = true;
       }
     }
   }
   return found_match;
 }
 
+// Order |SBFullHash| on the prefix part.  This differs from SBFullHashLess on
+// little-endian platforms.
+bool SBFullHashPrefixLess(const SBFullHash& a, const SBFullHash& b) {
+  return a.prefix < b.prefix;
+}
+
+// Remove items from |full_hashes| which have no prefix match in |db_hashes|.
+// |db_hashes| should be ordered by prefix.
+void TrimFullHashesByPrefix(
+    const std::vector<SBAddFullHash>& db_hashes,
+    std::vector<SBFullHash>* full_hashes) {
+  std::sort(full_hashes->begin(), full_hashes->end(), SBFullHashPrefixLess);
+
+  // |db_iter| steps through |db_hashes|.
+  std::vector<SBAddFullHash>::const_iterator db_iter = db_hashes.begin();
+
+  // |check_iter| steps through |full_hashes|, |out_iter| only steps forward
+  // when retaining values.
+  std::vector<SBFullHash>::iterator check_iter = full_hashes->begin();
+  std::vector<SBFullHash>::iterator out_iter = full_hashes->begin();
+
+  // Process until the end of either vector.  If |db_hashes| ends first, then
+  // the remaining elements of |full_hashes| cannot match.
+  while (check_iter != full_hashes->end() && db_iter != db_hashes.end()) {
+    // Bump |db_iter| forward until the first element which is not less than
+    // |check_iter|.
+    while (db_iter != db_hashes.end() &&
+           db_iter->full_hash.prefix < check_iter->prefix) {
+      ++db_iter;
+    }
+
+    // Keep |check_iter| if the prefix is equal to |db_iter|.
+    if (db_iter != db_hashes.end() &&
+        check_iter->prefix == db_iter->full_hash.prefix) {
+      *out_iter = *check_iter;
+      out_iter++;
+    }
+
+    check_iter++;
+  }
+
+  // Erase any elements which did not match.
+  full_hashes->erase(out_iter, full_hashes->end());
+}
+
 // Find the entries in |full_hashes| with prefix in |prefix_hits|, and
 // add them to |full_hits| if not expired.  "Not expired" is when
 // either |last_update| was recent enough, or the item has been
 // received recently enough.  Expired items are not deleted because a
 // future update may make them acceptable again.
 //
 // For efficiency reasons the code walks |prefix_hits| and
 // |full_hashes| in parallel, so they must be sorted by prefix.
 void GetCachedFullHashesForBrowse(const std::vector<SBPrefix>& prefix_hits,
                                   const std::vector<SBAddFullHash>& full_hashes,
@@ skipping 499 matching lines @@
   size_t miss_count = 0;
   for (size_t i = 0; i < full_hashes.size(); ++i) {
     const SBPrefix prefix = full_hashes[i].prefix;
     if (browse_prefix_set_->Exists(prefix)) {
       prefix_hits->push_back(prefix);
       if (prefix_miss_cache_.count(prefix) > 0)
         ++miss_count;
     }
   }
 
+  // Older code injected a prefix for each fullhash, which is now stripped on
+  // update.  Temporarily inject the removed |prefix_hits| to match the previous
+  // code's results.  The prefix-set check is to allow reads from older
+  // databases (where the set contains the prefix) to match reads from updated
+  // databases (where the set does not contain the prefix) until this code is
+  // replaced.
+  //
+  // See <http://crbug.com/361248>
+  TrimFullHashesByPrefix(full_browse_hashes_, &full_hashes);
+  for (size_t i = 0; i < full_hashes.size(); ++i) {
+    const SBPrefix prefix = full_hashes[i].prefix;
+    if (!browse_prefix_set_->Exists(prefix)) {
+      prefix_hits->push_back(prefix);
+      if (prefix_miss_cache_.count(prefix) > 0)
+        ++miss_count;
+    }
+  }
+
   // If all the prefixes are cached as 'misses', don't issue a GetHash.
   if (miss_count == prefix_hits->size())
     return false;
 
   // Find the matching full-hash results.  |full_browse_hashes_| are from the
   // database, |pending_browse_hashes_| are from GetHash requests between
   // updates.
   std::sort(prefix_hits->begin(), prefix_hits->end());
 
   GetCachedFullHashesForBrowse(*prefix_hits, full_browse_hashes_,
@@ skipping 155 matching lines @@
     for (int i = 0; i < count; i++) {
       const SBPrefix prefix = entry->PrefixAt(i);
       STATS_COUNTER("SB.PrefixAdd", 1);
       store->WriteAddPrefix(encoded_chunk_id, prefix);
     }
   } else {
     // Prefixes and hashes.
     const base::Time receive_time = base::Time::Now();
     for (int i = 0; i < count; ++i) {
       const SBFullHash full_hash = entry->FullHashAt(i);
-      const SBPrefix prefix = full_hash.prefix;
-
-      STATS_COUNTER("SB.PrefixAdd", 1);
-      store->WriteAddPrefix(encoded_chunk_id, prefix);
 
       STATS_COUNTER("SB.PrefixAddFull", 1);
       store->WriteAddHash(encoded_chunk_id, receive_time, full_hash);
     }
   }
 }
 
 // Helper to iterate over all the entries in the hosts in |chunks| and
 // add them to the store.
 void SafeBrowsingDatabaseNew::InsertAddChunks(
@@ skipping 53 matching lines @@
       STATS_COUNTER("SB.PrefixSub", 1);
       store->WriteSubPrefix(encoded_chunk_id, add_chunk_id, prefix);
     }
   } else {
     // Prefixes and hashes.
     for (int i = 0; i < count; ++i) {
       const SBFullHash full_hash = entry->FullHashAt(i);
       const int add_chunk_id =
           EncodeChunkId(entry->ChunkIdAtPrefix(i), list_id);
 
-      STATS_COUNTER("SB.PrefixSub", 1);
-      store->WriteSubPrefix(encoded_chunk_id, add_chunk_id, full_hash.prefix);
-
       STATS_COUNTER("SB.PrefixSubFull", 1);
       store->WriteSubHash(encoded_chunk_id, add_chunk_id, full_hash);
     }
   }
 }
 
 // Helper to iterate over all the entries in the hosts in |chunks| and
 // add them to the store.
 void SafeBrowsingDatabaseNew::InsertSubChunks(
     safe_browsing_util::ListType list_id,
@@ skipping 711 matching lines @@
   base::AutoLock locked(lookup_lock_);
   ip_blacklist_.swap(new_blacklist);
 }
 
 bool SafeBrowsingDatabaseNew::IsMalwareIPMatchKillSwitchOn() {
   SBFullHash malware_kill_switch = SBFullHashForString(kMalwareIPKillSwitchUrl);
   std::vector<SBFullHash> full_hashes;
   full_hashes.push_back(malware_kill_switch);
   return ContainsWhitelistedHashes(csd_whitelist_, full_hashes);
 }