Knock out injected safe-browsing prefixes.

The safe-browsing update code has long injected prefixes when a fullhash was
seen.  This causes incorrect behavior.  That case can be detected by observing
prefixes in the same chunk as fullhashes, which cannot be sent by the server.

BUG=361248
R=jar@chromium.org, mattm@chromium.org

Review URL: https://codereview.chromium.org/263833005

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@268815 0039d316-1c4b-4281-b951-d872f2087c98

6 files changed, 290 insertions, 9 deletions

diff --git a/chrome/browser/safe_browsing/prefix_set.h b/chrome/browser/safe_browsing/prefix_set.h
index 3cf6e75..a71ce3ba 100644
--- a/chrome/browser/safe_browsing/prefix_set.h
+++ b/chrome/browser/safe_browsing/prefix_set.h
@@ -91,6 +91,7 @@ class PrefixSet {
   FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, DeleteChunks);
   FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, DetectsCorruption);
   FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, Empty);
+  FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, KnockoutPrefixVolunteers);
   FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, PrefixMinMax);
   FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, SubKnockout);
   FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, Version7);
diff --git a/chrome/browser/safe_browsing/safe_browsing_database.cc b/chrome/browser/safe_browsing/safe_browsing_database.cc
index e1df581..09418a7 100644
--- a/chrome/browser/safe_browsing/safe_browsing_database.cc
+++ b/chrome/browser/safe_browsing/safe_browsing_database.cc
@@ -855,14 +855,10 @@ void SafeBrowsingDatabaseNew::InsertAdd(int chunk_id, SBPrefix host,
       store->WriteAddPrefix(encoded_chunk_id, prefix);
     }
   } else {
-    // Prefixes and hashes.
+    // Full hashes only.
     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);
@@ -930,15 +926,12 @@ void SafeBrowsingDatabaseNew::InsertSub(int chunk_id, SBPrefix host,
       store->WriteSubPrefix(encoded_chunk_id, add_chunk_id, prefix);
     }
   } else {
-    // Prefixes and hashes.
+    // Full hashes only.
     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);
     }
diff --git a/chrome/browser/safe_browsing/safe_browsing_database_unittest.cc b/chrome/browser/safe_browsing/safe_browsing_database_unittest.cc
index 0f433eb..559987c 100644
--- a/chrome/browser/safe_browsing/safe_browsing_database_unittest.cc
+++ b/chrome/browser/safe_browsing/safe_browsing_database_unittest.cc
@@ -41,6 +41,19 @@ std::string HashedIpPrefix(const std::string& ip_prefix, size_t prefix_size) {
   return hash;
 }
 
+// Add a host-level entry.
+void InsertAddChunkHostPrefix(SBChunk* chunk,
+                              int chunk_number,
+                              const std::string& host_name) {
+  chunk->chunk_number = chunk_number;
+  chunk->is_add = true;
+  SBChunkHost host;
+  host.host = SBPrefixForString(host_name);
+  host.entry = SBEntry::Create(SBEntry::ADD_PREFIX, 0);
+  host.entry->set_chunk_id(chunk->chunk_number);
+  chunk->hosts.push_back(host);
+}
+
 // Same as InsertAddChunkHostPrefixUrl, but with pre-computed
 // prefix values.
 void InsertAddChunkHostPrefixValue(SBChunk* chunk,
@@ -1860,3 +1873,85 @@ TEST_F(SafeBrowsingDatabaseTest, MalwareIpBlacklist) {
   EXPECT_TRUE(database_->ContainsMalwareIP("192.1.255.255"));
   EXPECT_FALSE(database_->ContainsMalwareIP("192.2.0.0"));
 }
+
+TEST_F(SafeBrowsingDatabaseTest, ContainsBrowseURL) {
+  std::vector<SBListChunkRanges> lists;
+  EXPECT_TRUE(database_->UpdateStarted(&lists));
+
+  // Add a host-level hit.
+  {
+    SBChunkList chunks;
+    SBChunk chunk;
+    InsertAddChunkHostPrefix(&chunk, 1, "www.evil.com/");
+    chunks.push_back(chunk);
+    database_->InsertChunks(safe_browsing_util::kMalwareList, chunks);
+  }
+
+  // Add a specific fullhash.
+  static const char kWhateverMalware[] = "www.whatever.com/malware.html";
+  {
+    SBChunkList chunks;
+    SBChunk chunk;
+    InsertAddChunkHostFullHashes(&chunk, 2, "www.whatever.com/",
+                                 kWhateverMalware);
+    chunks.push_back(chunk);
+    database_->InsertChunks(safe_browsing_util::kMalwareList, chunks);
+  }
+
+  // Add a fullhash which has a prefix collision for a known url.
+  static const char kExampleFine[] = "www.example.com/fine.html";
+  static const char kExampleCollision[] =
+      "www.example.com/3123364814/malware.htm";
+  ASSERT_EQ(SBPrefixForString(kExampleFine),
+            SBPrefixForString(kExampleCollision));
+  {
+    SBChunkList chunks;
+    SBChunk chunk;
+    InsertAddChunkHostFullHashes(&chunk, 3, "www.example.com/",
+                                 kExampleCollision);
+    chunks.push_back(chunk);
+    database_->InsertChunks(safe_browsing_util::kMalwareList, chunks);
+  }
+
+  database_->UpdateFinished(true);
+
+  const Time now = Time::Now();
+  std::vector<SBFullHashResult> cached_hashes;
+  std::vector<SBPrefix> prefix_hits;
+
+  // Anything will hit the host prefix.
+  EXPECT_TRUE(database_->ContainsBrowseUrl(
+      GURL("http://www.evil.com/malware.html"),
+      &prefix_hits, &cached_hashes, now));
+  ASSERT_EQ(1U, prefix_hits.size());
+  EXPECT_EQ(SBPrefixForString("www.evil.com/"), prefix_hits[0]);
+  EXPECT_TRUE(cached_hashes.empty());
+
+  // Hit the specific URL prefix.
+  EXPECT_TRUE(database_->ContainsBrowseUrl(
+      GURL(std::string("http://") + kWhateverMalware),
+      &prefix_hits, &cached_hashes, now));
+  ASSERT_EQ(1U, prefix_hits.size());
+  EXPECT_EQ(SBPrefixForString(kWhateverMalware), prefix_hits[0]);
+  EXPECT_TRUE(cached_hashes.empty());
+
+  // Other URLs at that host are fine.
+  EXPECT_FALSE(database_->ContainsBrowseUrl(
+      GURL("http://www.whatever.com/fine.html"),
+      &prefix_hits, &cached_hashes, now));
+  EXPECT_TRUE(prefix_hits.empty());
+  EXPECT_TRUE(cached_hashes.empty());
+
+  // Hit the specific URL full hash.
+  EXPECT_TRUE(database_->ContainsBrowseUrl(
+      GURL(std::string("http://") + kExampleCollision),
+      &prefix_hits, &cached_hashes, now));
+  ASSERT_EQ(1U, prefix_hits.size());
+  EXPECT_EQ(SBPrefixForString(kExampleCollision), prefix_hits[0]);
+  EXPECT_TRUE(cached_hashes.empty());
+
+  // This prefix collides, but no full hash match.
+  EXPECT_FALSE(database_->ContainsBrowseUrl(
+      GURL(std::string("http://") + kExampleFine),
+      &prefix_hits, &cached_hashes, now));
+}
diff --git a/chrome/browser/safe_browsing/safe_browsing_store.cc b/chrome/browser/safe_browsing/safe_browsing_store.cc
index e4c15e7..b0f6a2a 100644
--- a/chrome/browser/safe_browsing/safe_browsing_store.cc
+++ b/chrome/browser/safe_browsing/safe_browsing_store.cc
@@ -7,6 +7,7 @@
 #include <algorithm>
 
 #include "base/logging.h"
+#include "base/metrics/histogram.h"
 
 namespace {
 
@@ -88,6 +89,48 @@ void RemoveDeleted(ItemsT* items, const base::hash_set<int32>& del_set) {
   items->erase(end_iter, items->end());
 }
 
+// Remove prefixes which are in the same chunk as their fullhash.  This was a
+// mistake in earlier implementations.
+template <typename HashesT, typename PrefixesT>
+size_t KnockoutPrefixVolunteers(const HashesT& full_hashes,
+                                PrefixesT* prefixes) {
+  typename PrefixesT::iterator prefixes_process = prefixes->begin();
+  typename PrefixesT::iterator prefixes_out = prefixes->begin();
+  typename HashesT::const_iterator hashes_process = full_hashes.begin();
+
+  size_t skipped_count = 0;
+
+  while (hashes_process != full_hashes.end()) {
+    // Scan prefixes forward until an item is not less than the current hash.
+    while (prefixes_process != prefixes->end() &&
+           SBAddPrefixLess(*prefixes_process, *hashes_process)) {
+      if (prefixes_process != prefixes_out) {
+        *prefixes_out = *prefixes_process;
+      }
+      prefixes_out++;
+      prefixes_process++;
+    }
+
+    // If the current hash is also not less than the prefix, that implies they
+    // are equal.  Skip the prefix.
+    if (prefixes_process != prefixes->end() &&
+        !SBAddPrefixLess(*hashes_process, *prefixes_process)) {
+      skipped_count++;
+      prefixes_process++;
+    }
+
+    hashes_process++;
+  }
+
+  // If any prefixes were skipped, copy over the tail and erase the excess.
+  if (prefixes_process != prefixes_out) {
+    prefixes_out = std::copy(prefixes_process, prefixes->end(), prefixes_out);
+    prefixes->erase(prefixes_out, prefixes->end());
+  }
+
+  return skipped_count;
+}
+
 }  // namespace
 
 void SBProcessSubs(SBAddPrefixes* add_prefixes,
@@ -111,6 +154,17 @@ void SBProcessSubs(SBAddPrefixes* add_prefixes,
   DCHECK(sorted(sub_full_hashes->begin(), sub_full_hashes->end(),
                 SBAddPrefixHashLess<SBSubFullHash,SBSubFullHash>));
 
+  // Earlier database code added prefixes when it saw fullhashes.  The protocol
+  // should never send a chunk of mixed prefixes and fullhashes, the following
+  // removes any such cases which are seen.
+  // TODO(shess): Remove this code once most databases have been processed.
+  // Chunk churn should clean up anyone left over.  This only takes a few ms to
+  // run through my current database, so it doesn't seem worthwhile to do much
+  // more than that.
+  size_t skipped = KnockoutPrefixVolunteers(*add_full_hashes, add_prefixes);
+  skipped += KnockoutPrefixVolunteers(*sub_full_hashes, sub_prefixes);
+  UMA_HISTOGRAM_COUNTS("SB2.VolunteerPrefixesRemoved", skipped);
+
   // Factor out the prefix subs.
   KnockoutSubs(sub_prefixes, add_prefixes,
                SBAddPrefixLess<SBAddPrefix,SBSubPrefix>,
diff --git a/chrome/browser/safe_browsing/safe_browsing_store_file_unittest.cc b/chrome/browser/safe_browsing/safe_browsing_store_file_unittest.cc
index 55437ee..99e6587 100644
--- a/chrome/browser/safe_browsing/safe_browsing_store_file_unittest.cc
+++ b/chrome/browser/safe_browsing/safe_browsing_store_file_unittest.cc
@@ -896,4 +896,77 @@ TEST_F(SafeBrowsingStoreFileTest, Version8) {
 }
 #endif
 
+// Test that when the v8 golden file is updated, the add prefix injected from
+// the full hash is removed.  All platforms generating v8 files are
+// little-endian, so there is no point to testing this transition if/when a
+// big-endian port is added.
+#if defined(ARCH_CPU_LITTLE_ENDIAN)
+TEST_F(SafeBrowsingStoreFileTest, KnockoutPrefixVolunteers) {
+  store_.reset();
+
+  // Copy the golden file into temporary storage.  The golden file contains:
+  // - Add chunk kAddChunk1 containing kHash1.prefix and kHash2.
+  // - Sub chunk kSubChunk1 containing kHash3.
+  const char kBasename[] = "FileStoreVersion8";
+  base::FilePath golden_path;
+  ASSERT_TRUE(PathService::Get(chrome::DIR_TEST_DATA, &golden_path));
+  golden_path = golden_path.AppendASCII("SafeBrowsing");
+  golden_path = golden_path.AppendASCII(kBasename);
+  ASSERT_TRUE(base::CopyFile(golden_path, filename_));
+
+  // Reset the store to make sure it re-reads the file.
+  store_.reset(new SafeBrowsingStoreFile());
+  store_->Init(filename_,
+               base::Bind(&SafeBrowsingStoreFileTest::OnCorruptionDetected,
+                          base::Unretained(this)));
+
+  // Check that the expected prefixes and hashes are in place.
+  {
+    SBAddPrefixes add_prefixes;
+    EXPECT_TRUE(store_->GetAddPrefixes(&add_prefixes));
+    ASSERT_EQ(2U, add_prefixes.size());
+    EXPECT_EQ(kAddChunk1, add_prefixes[0].chunk_id);
+    EXPECT_EQ(kHash1.prefix, add_prefixes[0].prefix);
+    EXPECT_EQ(kAddChunk1, add_prefixes[1].chunk_id);
+    EXPECT_EQ(kHash2.prefix, add_prefixes[1].prefix);
+
+    std::vector<SBAddFullHash> add_hashes;
+    EXPECT_TRUE(store_->GetAddFullHashes(&add_hashes));
+    ASSERT_EQ(1U, add_hashes.size());
+    EXPECT_EQ(kAddChunk1, add_hashes[0].chunk_id);
+    EXPECT_TRUE(SBFullHashEqual(kHash2, add_hashes[0].full_hash));
+  }
+
+  // Update the store.
+  {
+    EXPECT_TRUE(store_->BeginUpdate());
+
+    safe_browsing::PrefixSetBuilder builder;
+    std::vector<SBAddFullHash> add_full_hashes_result;
+    ASSERT_TRUE(store_->FinishUpdate(&builder, &add_full_hashes_result));
+  }
+
+  // Reset the store to make sure it re-reads the file.
+  store_.reset(new SafeBrowsingStoreFile());
+  store_->Init(filename_,
+               base::Bind(&SafeBrowsingStoreFileTest::OnCorruptionDetected,
+                          base::Unretained(this)));
+
+  // |kHash2.prefix| should have dropped.
+  {
+    SBAddPrefixes add_prefixes;
+    EXPECT_TRUE(store_->GetAddPrefixes(&add_prefixes));
+    ASSERT_EQ(1U, add_prefixes.size());
+    EXPECT_EQ(kAddChunk1, add_prefixes[0].chunk_id);
+    EXPECT_EQ(kHash1.prefix, add_prefixes[0].prefix);
+
+    std::vector<SBAddFullHash> add_hashes;
+    EXPECT_TRUE(store_->GetAddFullHashes(&add_hashes));
+    ASSERT_EQ(1U, add_hashes.size());
+    EXPECT_EQ(kAddChunk1, add_hashes[0].chunk_id);
+    EXPECT_TRUE(SBFullHashEqual(kHash2, add_hashes[0].full_hash));
+  }
+}
+#endif
+
 }  // namespace safe_browsing
diff --git a/chrome/browser/safe_browsing/safe_browsing_store_unittest.cc b/chrome/browser/safe_browsing/safe_browsing_store_unittest.cc
index c1214e7..3e2494d 100644
--- a/chrome/browser/safe_browsing/safe_browsing_store_unittest.cc
+++ b/chrome/browser/safe_browsing/safe_browsing_store_unittest.cc
@@ -307,4 +307,69 @@ TEST(SafeBrowsingStoreTest, Y2K38) {
     << " (int32)time_t is running out.";
 }
 
+// Test that prefixes which were injected from full hashes are being removed.
+// This was a mistake in earlier versions of the code.
+TEST(SafeBrowsingStoreTest, KnockoutPrefixVolunteers) {
+  const base::Time kNow = base::Time::Now();
+
+  // Construct some full hashes which share prefix with another.
+  const SBFullHash kHash1mod1 = ModifyHashAfterPrefix(kHash1, 1);
+  const SBFullHash kHash2mod1 = ModifyHashAfterPrefix(kHash2, 1);
+
+  SBAddPrefixes add_prefixes;
+  std::vector<SBAddFullHash> add_hashes;
+  SBSubPrefixes sub_prefixes;
+  std::vector<SBSubFullHash> sub_hashes;
+
+  // Full hashes for an add chunk will have had the prefix injected.
+  add_hashes.push_back(SBAddFullHash(kAddChunk1, kNow, kHash1));
+  add_hashes.push_back(SBAddFullHash(kAddChunk1, kNow, kHash1mod1));
+  add_prefixes.push_back(SBAddPrefix(kAddChunk1, kHash1.prefix));
+
+  // Other full hashes or prefixes are not affected.
+  add_hashes.push_back(SBAddFullHash(kAddChunk1, kNow, kHash3));
+  add_prefixes.push_back(SBAddPrefix(kAddChunk2, kHash4.prefix));
+
+  // Full hashes for a sub chunk will have had the prefix injected.
+  sub_hashes.push_back(SBSubFullHash(kSubChunk1, kAddChunk1, kHash2));
+  sub_hashes.push_back(SBSubFullHash(kSubChunk1, kAddChunk1, kHash2mod1));
+  sub_prefixes.push_back(SBSubPrefix(kSubChunk1, kAddChunk1, kHash2.prefix));
+
+  // Other full hashes or prefixes are not affected.
+  sub_hashes.push_back(SBSubFullHash(kSubChunk1, kAddChunk1, kHash5));
+  sub_prefixes.push_back(SBSubPrefix(kSubChunk2, kAddChunk2, kHash6.prefix));
+
+  const base::hash_set<int32> no_deletions;
+  ProcessHelper(&add_prefixes, &sub_prefixes, &add_hashes, &sub_hashes,
+                no_deletions, no_deletions);
+
+  ASSERT_EQ(1U, add_prefixes.size());
+  EXPECT_EQ(kAddChunk2, add_prefixes[0].chunk_id);
+  EXPECT_EQ(kHash4.prefix, add_prefixes[0].prefix);
+
+  ASSERT_EQ(3U, add_hashes.size());
+  EXPECT_EQ(kAddChunk1, add_hashes[0].chunk_id);
+  EXPECT_TRUE(SBFullHashEqual(kHash1mod1, add_hashes[0].full_hash));
+  EXPECT_EQ(kAddChunk1, add_hashes[1].chunk_id);
+  EXPECT_TRUE(SBFullHashEqual(kHash1, add_hashes[1].full_hash));
+  EXPECT_EQ(kAddChunk1, add_hashes[2].chunk_id);
+  EXPECT_TRUE(SBFullHashEqual(kHash3, add_hashes[2].full_hash));
+
+  ASSERT_EQ(1U, sub_prefixes.size());
+  EXPECT_EQ(kSubChunk2, sub_prefixes[0].chunk_id);
+  EXPECT_EQ(kAddChunk2, sub_prefixes[0].add_chunk_id);
+  EXPECT_EQ(kHash6.prefix, sub_prefixes[0].add_prefix);
+
+  ASSERT_EQ(3U, sub_hashes.size());
+  EXPECT_EQ(kSubChunk1, sub_hashes[0].chunk_id);
+  EXPECT_EQ(kAddChunk1, sub_hashes[0].add_chunk_id);
+  EXPECT_TRUE(SBFullHashEqual(kHash5, sub_hashes[0].full_hash));
+  EXPECT_EQ(kSubChunk1, sub_hashes[1].chunk_id);
+  EXPECT_EQ(kAddChunk1, sub_hashes[1].add_chunk_id);
+  EXPECT_TRUE(SBFullHashEqual(kHash2mod1, sub_hashes[1].full_hash));
+  EXPECT_EQ(kSubChunk1, sub_hashes[2].chunk_id);
+  EXPECT_EQ(kAddChunk1, sub_hashes[2].add_chunk_id);
+  EXPECT_TRUE(SBFullHashEqual(kHash2, sub_hashes[2].full_hash));
+}
+
 }  // namespace