Additional validation code for PrefixSet.

chrome/browser/safe_browsing/safe_browsing_database.cc

 // Copyright (c) 2010 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 "base/file_util.h"
 #include "base/metrics/histogram.h"
 #include "base/metrics/stats_counters.h"
 #include "base/time.h"
@@ skipping 160 matching lines @@
   lists->push_back(chunkrange0);
   lists->push_back(chunkrange1);
 }
 
 // Order |SBAddFullHash| on the prefix part.  |SBAddPrefixLess()| from
 // safe_browsing_store.h orders on both chunk-id and prefix.
 bool SBAddFullHashPrefixLess(const SBAddFullHash& a, const SBAddFullHash& b) {
   return a.full_hash.prefix < b.full_hash.prefix;
 }
 
-// Create a |PrefixSet| from a vector of add-prefixes.
-safe_browsing::PrefixSet* CreatePrefixSet(
-    const std::vector<SBAddPrefix>& add_prefixes) {
-  std::vector<SBPrefix> prefixes;
-  for (size_t i = 0; i < add_prefixes.size(); ++i) {
-    prefixes.push_back(add_prefixes[i].prefix);
-  }
-  return new safe_browsing::PrefixSet(prefixes);
-}
-
 // As compared to the bloom filter, PrefixSet should have these
 // properties:
 // - Any bloom filter miss should be a prefix set miss.
 // - Any prefix set hit should be a bloom filter hit.
 // - Bloom filter false positives are prefix set misses.
 // The following is to log actual performance to verify this.
 enum PrefixSetEvent {
   PREFIX_SET_EVENT_HIT,
   PREFIX_SET_EVENT_BLOOM_HIT,
   PREFIX_SET_EVENT_BLOOM_MISS_PREFIX_HIT,
+  PREFIX_SET_EVENT_BLOOM_MISS_PREFIX_HIT_INVALID,

[lzheng, 2011/03/04 00:29:06]

Yeah, much better. 

+  PREFIX_SET_GETPREFIXES_BROKEN,
 
   // Memory space for histograms is determined by the max.  ALWAYS ADD
   // NEW VALUES BEFORE THIS ONE.
   PREFIX_SET_EVENT_MAX
 };
 
 void RecordPrefixSetInfo(PrefixSetEvent event_type) {
   UMA_HISTOGRAM_ENUMERATION("SB2.PrefixSetEvent", event_type,
                             PREFIX_SET_EVENT_MAX);
 }
@@ skipping 143 matching lines @@
   {
     base::AutoLock locked(lookup_lock_);
     full_browse_hashes_.clear();
     pending_browse_hashes_.clear();
     prefix_miss_cache_.clear();
     // TODO(shess): This could probably be |bloom_filter_.reset()|.
     browse_bloom_filter_ = new BloomFilter(BloomFilter::kBloomFilterMinSize *
                                            BloomFilter::kBloomFilterSizeRatio);
     // TODO(shess): It is simpler for the code to assume that presence
     // of a bloom filter always implies presence of a prefix set.
-    prefix_set_.reset(CreatePrefixSet(std::vector<SBAddPrefix>()));
+    prefix_set_.reset(new safe_browsing::PrefixSet(std::vector<SBPrefix>()));
   }
 
   return true;
 }
 
 // TODO(lzheng): Remove matching_list, it is not used anywhere.
 bool SafeBrowsingDatabaseNew::ContainsBrowseUrl(
     const GURL& url,
     std::string* matching_list,
     std::vector<SBPrefix>* prefix_hits,
@@ skipping 10 matching lines @@
     return false;
 
   // This function is called on the I/O thread, prevent changes to
   // bloom filter and caches.
   base::AutoLock locked(lookup_lock_);
 
   if (!browse_bloom_filter_.get())
     return false;
   DCHECK(prefix_set_.get());
 
+  // Used to double-check in case of a hit mis-match.
+  std::vector<SBPrefix> restored;
+
   size_t miss_count = 0;
   for (size_t i = 0; i < prefixes.size(); ++i) {
     bool found = prefix_set_->Exists(prefixes[i]);
 
     if (browse_bloom_filter_->Exists(prefixes[i])) {
       RecordPrefixSetInfo(PREFIX_SET_EVENT_BLOOM_HIT);
       if (found)
         RecordPrefixSetInfo(PREFIX_SET_EVENT_HIT);
       prefix_hits->push_back(prefixes[i]);
       if (prefix_miss_cache_.count(prefixes[i]) > 0)
         ++miss_count;
     } else {
-      // Bloom filter misses should never be in prefix set.
+      // Bloom filter misses should never be in prefix set.  Re-create
+      // the original prefixes and manually search for it, to check if
+      // there's a bug with how |Exists()| is implemented.
+      // |UpdateBrowseStore()| previously verified that
+      // |GetPrefixes()| returns the same prefixes as were passed to
+      // the constructor.
       DCHECK(!found);
-      if (found)
-        RecordPrefixSetInfo(PREFIX_SET_EVENT_BLOOM_MISS_PREFIX_HIT);
+      if (found) {
+        if (restored.empty())
+          prefix_set_->GetPrefixes(&restored);
+
+        // If the item is not in the re-created list, then there is an
+        // error in |PrefixSet::Exists()|.  If the item is in the
+        // re-created list, then the bloom filter was wrong.
+        if (std::binary_search(restored.begin(), restored.end(), prefixes[i])) {
+          RecordPrefixSetInfo(PREFIX_SET_EVENT_BLOOM_MISS_PREFIX_HIT);
+        } else {
+          RecordPrefixSetInfo(PREFIX_SET_EVENT_BLOOM_MISS_PREFIX_HIT_INVALID);
+        }
+      }
     }
   }
 
   // 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.
@@ skipping 415 matching lines @@
   // Create and populate |filter| from |add_prefixes|.
   // TODO(shess): The bloom filter doesn't need to be a
   // scoped_refptr<> for this code.  Refactor that away.
   const int filter_size =
       BloomFilter::FilterSizeForKeyCount(add_prefixes.size());
   scoped_refptr<BloomFilter> filter(new BloomFilter(filter_size));
   for (size_t i = 0; i < add_prefixes.size(); ++i) {
     filter->Insert(add_prefixes[i].prefix);
   }
 
+  std::vector<SBPrefix> prefixes;
+  for (size_t i = 0; i < add_prefixes.size(); ++i) {
+    prefixes.push_back(add_prefixes[i].prefix);
+  }
+  std::sort(prefixes.begin(), prefixes.end());
   scoped_ptr<safe_browsing::PrefixSet>
-      prefix_set(CreatePrefixSet(add_prefixes));
+      prefix_set(new safe_browsing::PrefixSet(prefixes));
+
+  // Verify that |GetPrefixes()| returns the same set of prefixes as
+  // was passed to the constructor.
+  std::vector<SBPrefix> restored;
+  prefix_set->GetPrefixes(&restored);
+  prefixes.erase(std::unique(prefixes.begin(), prefixes.end()), prefixes.end());
+  if (restored.size() != prefixes.size() ||
+      !std::equal(prefixes.begin(), prefixes.end(), restored.begin())) {
+    NOTREACHED();
+    RecordPrefixSetInfo(PREFIX_SET_GETPREFIXES_BROKEN);
+  }
 
   // This needs to be in sorted order by prefix for efficient access.
   std::sort(add_full_hashes.begin(), add_full_hashes.end(),
             SBAddFullHashPrefixLess);
 
   // Swap in the newly built filter and cache.
   {
     base::AutoLock locked(lookup_lock_);
     full_browse_hashes_.swap(add_full_hashes);
 
@@ skipping 87 matching lines @@
   DVLOG(1) << "SafeBrowsingDatabaseNew read bloom filter in "
            << (base::TimeTicks::Now() - before).InMilliseconds() << " ms";
 
   if (!browse_bloom_filter_.get())
     RecordFailure(FAILURE_DATABASE_FILTER_READ);
 
   // Manually re-generate the prefix set from the main database.
   // TODO(shess): Write/read for prefix set.
   std::vector<SBAddPrefix> add_prefixes;
   browse_store_->GetAddPrefixes(&add_prefixes);
-  prefix_set_.reset(CreatePrefixSet(add_prefixes));
+  std::vector<SBPrefix> prefixes;
+  for (size_t i = 0; i < add_prefixes.size(); ++i) {
+    prefixes.push_back(add_prefixes[i].prefix);
+  }
+  std::sort(prefixes.begin(), prefixes.end());
+  prefix_set_.reset(new safe_browsing::PrefixSet(prefixes));
+
+  // Double-check the prefixes so that the
+  // PREFIX_SET_EVENT_BLOOM_MISS_PREFIX_HIT_INVALID histogram in
+  // ContainsBrowseUrl() can be trustworthy.
+  std::vector<SBPrefix> restored;
+  prefix_set_->GetPrefixes(&restored);
+  std::set<SBPrefix> unique(prefixes.begin(), prefixes.end());
+  if (restored.size() != unique.size() ||
+      !std::equal(unique.begin(), unique.end(), restored.begin())) {
+    NOTREACHED();
+    RecordPrefixSetInfo(PREFIX_SET_GETPREFIXES_BROKEN);
+  }
 }
 
 bool SafeBrowsingDatabaseNew::Delete() {
   DCHECK_EQ(creation_loop_, MessageLoop::current());
 
   const bool r1 = browse_store_->Delete();
   if (!r1)
     RecordFailure(FAILURE_DATABASE_STORE_DELETE);
 
   const bool r2 = download_store_.get() ? download_store_->Delete() : true;
@@ skipping 13 matching lines @@
     return;
 
   const base::TimeTicks before = base::TimeTicks::Now();
   const bool write_ok = browse_bloom_filter_->WriteFile(bloom_filter_filename_);
   DVLOG(1) << "SafeBrowsingDatabaseNew wrote bloom filter in "
            << (base::TimeTicks::Now() - before).InMilliseconds() << " ms";
 
   if (!write_ok)
     RecordFailure(FAILURE_DATABASE_FILTER_WRITE);
 }