Track false-positive in SafeBrowsing's bloom filter.

Track the number of times when a prefix has a hit in the bloom filter,
but the prefix does not exist in the data used to create the bloom
filter.

BUG=64988
TEST=none

Review URL: http://codereview.chromium.org/5546001

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

9 files changed, 91 insertions, 7 deletions

diff --git a/chrome/browser/safe_browsing/safe_browsing_database.cc b/chrome/browser/safe_browsing/safe_browsing_database.cc
index e741c60..49c8101 100644
--- a/chrome/browser/safe_browsing/safe_browsing_database.cc
+++ b/chrome/browser/safe_browsing/safe_browsing_database.cc
@@ -546,7 +546,7 @@ void SafeBrowsingDatabaseNew::UpdateFinished(bool update_succeeded) {
 
   std::vector<SBAddPrefix> add_prefixes;
   std::vector<SBAddFullHash> add_full_hashes;
-  if (!store_->FinishUpdate(pending_add_hashes,
+  if (!store_->FinishUpdate(pending_add_hashes, prefix_miss_cache_,
                             &add_prefixes, &add_full_hashes)) {
     RecordFailure(FAILURE_DATABASE_UPDATE_FINISH);
     return;
diff --git a/chrome/browser/safe_browsing/safe_browsing_store.cc b/chrome/browser/safe_browsing/safe_browsing_store.cc
index ea5d4f5..c699c13 100644
--- a/chrome/browser/safe_browsing/safe_browsing_store.cc
+++ b/chrome/browser/safe_browsing/safe_browsing_store.cc
@@ -6,6 +6,8 @@
 
 #include <algorithm>
 
+#include "base/metrics/histogram.h"
+
 namespace {
 
 // Find items matching between |subs| and |adds|, and remove them,
@@ -119,8 +121,49 @@ void RemoveDeleted(std::vector<T>* vec, const base::hash_set<int32>& del_set) {
   vec->erase(add_iter, vec->end());
 }
 
+enum MissTypes {
+  MISS_TYPE_ALL,
+  MISS_TYPE_FALSE,
+
+  // Always at the end.
+  MISS_TYPE_MAX
+};
+
 }  // namespace
 
+void SBCheckPrefixMisses(const std::vector<SBAddPrefix>& add_prefixes,
+                         const std::set<SBPrefix>& prefix_misses) {
+  if (prefix_misses.empty())
+    return;
+
+  // Record a hit for all prefixes which missed when sent to the
+  // server.
+  for (size_t i = 0; i < prefix_misses.size(); ++i) {
+    UMA_HISTOGRAM_ENUMERATION("SB2.BloomFilterFalsePositives",
+                              MISS_TYPE_ALL, MISS_TYPE_MAX);
+  }
+
+  // Collect the misses which are not present in |add_prefixes|.
+  // Since |add_prefixes| can contain multiple copies of the same
+  // prefix, it is not sufficient to count the number of elements
+  // present in both collections.
+  std::set<SBPrefix> false_misses(prefix_misses.begin(), prefix_misses.end());
+  for (size_t i = 0; i < add_prefixes.size(); ++i) {
+    // |erase()| on an absent element should cost like |find()|.
+    false_misses.erase(add_prefixes[i].prefix);
+  }
+
+  // Record a hit for prefixes which we shouldn't have sent in the
+  // first place.
+  for (size_t i = 0; i < false_misses.size(); ++i) {
+    UMA_HISTOGRAM_ENUMERATION("SB2.BloomFilterFalsePositives",
+                              MISS_TYPE_FALSE, MISS_TYPE_MAX);
+  }
+
+  // Divide |MISS_TYPE_FALSE| by |MISS_TYPE_ALL| to get the
+  // bloom-filter false-positive rate.
+}
+
 void SBProcessSubs(std::vector<SBAddPrefix>* add_prefixes,
                    std::vector<SBSubPrefix>* sub_prefixes,
                    std::vector<SBAddFullHash>* add_full_hashes,
diff --git a/chrome/browser/safe_browsing/safe_browsing_store.h b/chrome/browser/safe_browsing/safe_browsing_store.h
index 418c55f..86eb9a1 100644
--- a/chrome/browser/safe_browsing/safe_browsing_store.h
+++ b/chrome/browser/safe_browsing/safe_browsing_store.h
@@ -6,6 +6,7 @@
 #define CHROME_BROWSER_SAFE_BROWSING_SAFE_BROWSING_STORE_H_
 #pragma once
 
+#include <set>
 #include <vector>
 
 #include "base/basictypes.h"
@@ -145,6 +146,11 @@ void SBProcessSubs(std::vector<SBAddPrefix>* add_prefixes,
                    const base::hash_set<int32>& add_chunks_deleted,
                    const base::hash_set<int32>& sub_chunks_deleted);
 
+// Records a histogram of the number of items in |prefix_misses| which
+// are not in |add_prefixes|.
+void SBCheckPrefixMisses(const std::vector<SBAddPrefix>& add_prefixes,
+                         const std::set<SBPrefix>& prefix_misses);
+
 // TODO(shess): This uses int32 rather than int because it's writing
 // specifically-sized items to files.  SBPrefix should likewise be
 // explicitly sized.
@@ -212,9 +218,12 @@ class SafeBrowsingStore {
   // |pending_adds| is the set of full hashes which have been received
   // since the previous update, and is provided as a convenience
   // (could be written via WriteAddHash(), but that would flush the
-  // chunk to disk).
+  // chunk to disk).  |prefix_misses| is the set of prefixes where the
+  // |GetHash()| request returned no full hashes, used for diagnostic
+  // purposes.
   virtual bool FinishUpdate(
       const std::vector<SBAddFullHash>& pending_adds,
+      const std::set<SBPrefix>& prefix_misses,
       std::vector<SBAddPrefix>* add_prefixes_result,
       std::vector<SBAddFullHash>* add_full_hashes_result) = 0;
 
diff --git a/chrome/browser/safe_browsing/safe_browsing_store_file.cc b/chrome/browser/safe_browsing/safe_browsing_store_file.cc
index 493e397..f03080b 100644
--- a/chrome/browser/safe_browsing/safe_browsing_store_file.cc
+++ b/chrome/browser/safe_browsing/safe_browsing_store_file.cc
@@ -437,6 +437,7 @@ bool SafeBrowsingStoreFile::FinishChunk() {
 
 bool SafeBrowsingStoreFile::DoUpdate(
     const std::vector<SBAddFullHash>& pending_adds,
+    const std::set<SBPrefix>& prefix_misses,
     std::vector<SBAddPrefix>* add_prefixes_result,
     std::vector<SBAddFullHash>* add_full_hashes_result) {
   DCHECK(old_store_.get() || file_.get() || empty_);
@@ -577,6 +578,10 @@ bool SafeBrowsingStoreFile::DoUpdate(
   add_full_hashes.insert(add_full_hashes.end(),
                          pending_adds.begin(), pending_adds.end());
 
+  // Check how often a prefix was checked which wasn't in the
+  // database.
+  SBCheckPrefixMisses(add_prefixes, prefix_misses);
+
   // Knock the subs from the adds and process deleted chunks.
   SBProcessSubs(&add_prefixes, &sub_prefixes,
                 &add_full_hashes, &sub_full_hashes,
@@ -658,9 +663,10 @@ bool SafeBrowsingStoreFile::DoUpdate(
 
 bool SafeBrowsingStoreFile::FinishUpdate(
     const std::vector<SBAddFullHash>& pending_adds,
+    const std::set<SBPrefix>& prefix_misses,
     std::vector<SBAddPrefix>* add_prefixes_result,
     std::vector<SBAddFullHash>* add_full_hashes_result) {
-  bool ret = DoUpdate(pending_adds,
+  bool ret = DoUpdate(pending_adds, prefix_misses,
                       add_prefixes_result, add_full_hashes_result);
 
   if (!ret) {
diff --git a/chrome/browser/safe_browsing/safe_browsing_store_file.h b/chrome/browser/safe_browsing/safe_browsing_store_file.h
index 0875cc8..95dc030 100644
--- a/chrome/browser/safe_browsing/safe_browsing_store_file.h
+++ b/chrome/browser/safe_browsing/safe_browsing_store_file.h
@@ -137,9 +137,11 @@ class SafeBrowsingStoreFile : public SafeBrowsingStore {
 
   virtual bool BeginUpdate();
   virtual bool DoUpdate(const std::vector<SBAddFullHash>& pending_adds,
+                        const std::set<SBPrefix>& prefix_misses,
                         std::vector<SBAddPrefix>* add_prefixes_result,
                         std::vector<SBAddFullHash>* add_full_hashes_result);
   virtual bool FinishUpdate(const std::vector<SBAddFullHash>& pending_adds,
+                            const std::set<SBPrefix>& prefix_misses,
                             std::vector<SBAddPrefix>* add_prefixes_result,
                             std::vector<SBAddFullHash>* add_full_hashes_result);
   virtual bool CancelUpdate();
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 74dfc4f..452a52e 100644
--- a/chrome/browser/safe_browsing/safe_browsing_store_file_unittest.cc
+++ b/chrome/browser/safe_browsing/safe_browsing_store_file_unittest.cc
@@ -99,10 +99,11 @@ TEST_F(SafeBrowsingStoreFileTest, DetectsCorruption) {
 
   // Can successfully open and read the store.
   std::vector<SBAddFullHash> pending_adds;
+  std::set<SBPrefix> prefix_misses;
   std::vector<SBAddPrefix> orig_prefixes;
   std::vector<SBAddFullHash> orig_hashes;
   EXPECT_TRUE(test_store.BeginUpdate());
-  EXPECT_TRUE(test_store.FinishUpdate(pending_adds,
+  EXPECT_TRUE(test_store.FinishUpdate(pending_adds, prefix_misses,
                                       &orig_prefixes, &orig_hashes));
   EXPECT_GT(orig_prefixes.size(), 0U);
   EXPECT_GT(orig_hashes.size(), 0U);
@@ -125,7 +126,7 @@ TEST_F(SafeBrowsingStoreFileTest, DetectsCorruption) {
   std::vector<SBAddFullHash> add_hashes;
   corruption_detected_ = false;
   EXPECT_TRUE(test_store.BeginUpdate());
-  EXPECT_FALSE(test_store.FinishUpdate(pending_adds,
+  EXPECT_FALSE(test_store.FinishUpdate(pending_adds, prefix_misses,
                                        &add_prefixes, &add_hashes));
   EXPECT_TRUE(corruption_detected_);
   EXPECT_EQ(add_prefixes.size(), 0U);
@@ -178,9 +179,11 @@ void LoadStore(SafeBrowsingStore* store) {
   EXPECT_TRUE(store->FinishChunk());
 
   std::vector<SBAddFullHash> pending_adds;
+  std::set<SBPrefix> prefix_misses;
   std::vector<SBAddPrefix> add_prefixes;
   std::vector<SBAddFullHash> add_hashes;
-  EXPECT_TRUE(store->FinishUpdate(pending_adds, &add_prefixes, &add_hashes));
+  EXPECT_TRUE(store->FinishUpdate(pending_adds, prefix_misses,
+                                  &add_prefixes, &add_hashes));
   EXPECT_EQ(3U, add_prefixes.size());
 }
 
@@ -221,9 +224,11 @@ void UpdateStore(SafeBrowsingStore* store) {
   store->DeleteAddChunk(kAddChunk2);
 
   std::vector<SBAddFullHash> pending_adds;
+  std::set<SBPrefix> prefix_misses;
   std::vector<SBAddPrefix> add_prefixes;
   std::vector<SBAddFullHash> add_hashes;
-  EXPECT_TRUE(store->FinishUpdate(pending_adds, &add_prefixes, &add_hashes));
+  EXPECT_TRUE(store->FinishUpdate(pending_adds, prefix_misses,
+                                  &add_prefixes, &add_hashes));
   EXPECT_EQ(2U, add_prefixes.size());
 }
 
diff --git a/chrome/browser/safe_browsing/safe_browsing_store_sqlite.cc b/chrome/browser/safe_browsing/safe_browsing_store_sqlite.cc
index 8deeff4..d687570 100644
--- a/chrome/browser/safe_browsing/safe_browsing_store_sqlite.cc
+++ b/chrome/browser/safe_browsing/safe_browsing_store_sqlite.cc
@@ -645,6 +645,7 @@ bool SafeBrowsingStoreSqlite::DoUpdate(
 
 bool SafeBrowsingStoreSqlite::FinishUpdate(
     const std::vector<SBAddFullHash>& pending_adds,
+    const std::set<SBPrefix>& prefix_misses,
     std::vector<SBAddPrefix>* add_prefixes_result,
     std::vector<SBAddFullHash>* add_full_hashes_result) {
   bool ret = DoUpdate(pending_adds,
diff --git a/chrome/browser/safe_browsing/safe_browsing_store_sqlite.h b/chrome/browser/safe_browsing/safe_browsing_store_sqlite.h
index 60e7fda..9093c4a 100644
--- a/chrome/browser/safe_browsing/safe_browsing_store_sqlite.h
+++ b/chrome/browser/safe_browsing/safe_browsing_store_sqlite.h
@@ -64,7 +64,10 @@ class SafeBrowsingStoreSqlite : public SafeBrowsingStore {
   virtual bool DoUpdate(const std::vector<SBAddFullHash>& pending_adds,
                         std::vector<SBAddPrefix>* add_prefixes_result,
                         std::vector<SBAddFullHash>* add_full_hashes_result);
+  // NOTE: |prefix_misses| is ignored, as it will be handled in
+  // |SafeBrowsingStoreFile::DoUpdate()|.
   virtual bool FinishUpdate(const std::vector<SBAddFullHash>& pending_adds,
+                            const std::set<SBPrefix>& prefix_misses,
                             std::vector<SBAddPrefix>* add_prefixes_result,
                             std::vector<SBAddFullHash>* add_full_hashes_result);
   virtual bool CancelUpdate();
diff --git a/chrome/browser/safe_browsing/safe_browsing_store_unittest_helper.cc b/chrome/browser/safe_browsing/safe_browsing_store_unittest_helper.cc
index d8ae136..b88efe7 100644
--- a/chrome/browser/safe_browsing/safe_browsing_store_unittest_helper.cc
+++ b/chrome/browser/safe_browsing/safe_browsing_store_unittest_helper.cc
@@ -44,10 +44,12 @@ void SafeBrowsingStoreTestEmpty(SafeBrowsingStore* store) {
   EXPECT_FALSE(store->CheckSubChunk(-1));
 
   std::vector<SBAddFullHash> pending_adds;
+  std::set<SBPrefix> prefix_misses;
   std::vector<SBAddPrefix> add_prefixes_result;
   std::vector<SBAddFullHash> add_full_hashes_result;
 
   EXPECT_TRUE(store->FinishUpdate(pending_adds,
+                                  prefix_misses,
                                   &add_prefixes_result,
                                   &add_full_hashes_result));
   EXPECT_TRUE(add_prefixes_result.empty());
@@ -87,10 +89,12 @@ void SafeBrowsingStoreTestStorePrefix(SafeBrowsingStore* store) {
   EXPECT_EQ(kSubChunk1, chunks[0]);
 
   std::vector<SBAddFullHash> pending_adds;
+  std::set<SBPrefix> prefix_misses;
   std::vector<SBAddPrefix> add_prefixes_result;
   std::vector<SBAddFullHash> add_full_hashes_result;
 
   EXPECT_TRUE(store->FinishUpdate(pending_adds,
+                                  prefix_misses,
                                   &add_prefixes_result,
                                   &add_full_hashes_result));
 
@@ -124,6 +128,7 @@ void SafeBrowsingStoreTestStorePrefix(SafeBrowsingStore* store) {
   EXPECT_TRUE(store->CheckSubChunk(kSubChunk1));
 
   EXPECT_TRUE(store->FinishUpdate(pending_adds,
+                                  prefix_misses,
                                   &add_prefixes_result,
                                   &add_full_hashes_result));
 
@@ -157,10 +162,12 @@ void SafeBrowsingStoreTestSubKnockout(SafeBrowsingStore* store) {
   EXPECT_TRUE(store->FinishChunk());
 
   std::vector<SBAddFullHash> pending_adds;
+  std::set<SBPrefix> prefix_misses;
   std::vector<SBAddPrefix> add_prefixes_result;
   std::vector<SBAddFullHash> add_full_hashes_result;
 
   EXPECT_TRUE(store->FinishUpdate(pending_adds,
+                                  prefix_misses,
                                   &add_prefixes_result,
                                   &add_full_hashes_result));
 
@@ -181,6 +188,7 @@ void SafeBrowsingStoreTestSubKnockout(SafeBrowsingStore* store) {
   EXPECT_TRUE(store->FinishChunk());
 
   EXPECT_TRUE(store->FinishUpdate(pending_adds,
+                                  prefix_misses,
                                   &add_prefixes_result,
                                   &add_full_hashes_result));
   EXPECT_EQ(1U, add_prefixes_result.size());
@@ -199,6 +207,7 @@ void SafeBrowsingStoreTestSubKnockout(SafeBrowsingStore* store) {
   EXPECT_TRUE(store->FinishChunk());
 
   EXPECT_TRUE(store->FinishUpdate(pending_adds,
+                                  prefix_misses,
                                   &add_prefixes_result,
                                   &add_full_hashes_result));
   ASSERT_EQ(2U, add_prefixes_result.size());
@@ -257,10 +266,12 @@ void SafeBrowsingStoreTestDeleteChunks(SafeBrowsingStore* store) {
   EXPECT_TRUE(store->CheckSubChunk(kSubChunk2));
 
   std::vector<SBAddFullHash> pending_adds;
+  std::set<SBPrefix> prefix_misses;
   std::vector<SBAddPrefix> add_prefixes_result;
   std::vector<SBAddFullHash> add_full_hashes_result;
 
   EXPECT_TRUE(store->FinishUpdate(pending_adds,
+                                  prefix_misses,
                                   &add_prefixes_result,
                                   &add_full_hashes_result));
 
@@ -286,6 +297,7 @@ void SafeBrowsingStoreTestDeleteChunks(SafeBrowsingStore* store) {
   add_prefixes_result.clear();
   add_full_hashes_result.clear();
   EXPECT_TRUE(store->FinishUpdate(pending_adds,
+                                  prefix_misses,
                                   &add_prefixes_result,
                                   &add_full_hashes_result));
 
@@ -298,6 +310,7 @@ void SafeBrowsingStoreTestDeleteChunks(SafeBrowsingStore* store) {
   add_prefixes_result.clear();
   add_full_hashes_result.clear();
   EXPECT_TRUE(store->FinishUpdate(pending_adds,
+                                  prefix_misses,
                                   &add_prefixes_result,
                                   &add_full_hashes_result));
   EXPECT_TRUE(add_prefixes_result.empty());
@@ -323,10 +336,12 @@ void SafeBrowsingStoreTestDelete(SafeBrowsingStore* store,
   EXPECT_TRUE(store->FinishChunk());
 
   std::vector<SBAddFullHash> pending_adds;
+  std::set<SBPrefix> prefix_misses;
   std::vector<SBAddPrefix> add_prefixes_result;
   std::vector<SBAddFullHash> add_full_hashes_result;
 
   EXPECT_TRUE(store->FinishUpdate(pending_adds,
+                                  prefix_misses,
                                   &add_prefixes_result,
                                   &add_full_hashes_result));