PrefixSet as an alternate to BloomFilter for safe-browsing.

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"
 #include "base/message_loop.h"
 #include "base/process_util.h"
 #include "base/sha2.h"
 #include "chrome/browser/safe_browsing/bloom_filter.h"
+#include "chrome/browser/safe_browsing/prefix_set.h"
 #include "chrome/browser/safe_browsing/safe_browsing_store_file.h"
 #include "chrome/browser/safe_browsing/safe_browsing_store_sqlite.h"
 #include "chrome/browser/safe_browsing/safe_browsing_util.h"
 #include "googleurl/src/gurl.h"
 
 namespace {
 
 // Filename suffix for the bloom filter.
 const FilePath::CharType kBloomFilterFile[] = FILE_PATH_LITERAL(" Filter 2");
 // Filename suffix for download store.
@@ skipping 147 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 {

[lzheng, 2011/02/05 01:03:42]

I found we've never record how many look ups we encountered. Should we do that?
Otherwise, we never know the actual false positive rate is encountered by bloom
filter. 

[Scott Hess - ex-Googler, 2011/02/07 19:20:23]

It should be a couple orders of magnitude higher than the other values, so it
might blow out the metrics.

This specific histogram is to make sure that PrefixSet matches the results of
BloomFilter as expected.  It should go away when the BloomFilter goes away.  So
we could add another histogram, but probably somewhere else.

I _think_ SB2.FilterCheck might be sufficient already.  It histograms
time-to-check, but the dashboard also shows number of records.  For 2/2/11,
SB2.FilterCheck shows 3700x as many hits as SB2.GetHash200+SB2.GetHash204, which
seems like a reasonable number.

+  PREFIX_SET_EVENT_HIT,
+  PREFIX_SET_EVENT_BLOOM_HIT,
+  PREFIX_SET_EVENT_BLOOM_MISS_PREFIX_HIT,
+
+  // 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);
+}
+
 }  // namespace
 
 // The default SafeBrowsingDatabaseFactory.
 class SafeBrowsingDatabaseFactoryImpl : public SafeBrowsingDatabaseFactory {
  public:
   virtual SafeBrowsingDatabase* CreateSafeBrowsingDatabase(
       bool enable_download_protection) {
     if (enable_download_protection) {
       // Create database with browse url store and download store.
       return new SafeBrowsingDatabaseNew(new SafeBrowsingStoreFile,
@@ skipping 132 matching lines @@
 
   // Reset objects in memory.
   {
     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>()));
   }
 
   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,
     std::vector<SBFullHashResult>* full_hits,
     base::Time last_update) {
   // Clear the results first.
   matching_list->clear();
   prefix_hits->clear();
   full_hits->clear();
 
   std::vector<SBPrefix> prefixes;
   BrowsePrefixesToCheck(url, &prefixes);
   if (prefixes.empty())
     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());
 
   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.
+      DCHECK(!found);
+      if (found)
+        RecordPrefixSetInfo(PREFIX_SET_EVENT_BLOOM_MISS_PREFIX_HIT);
     }
   }
 
   // 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 386 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);
   }
 
+  scoped_ptr<safe_browsing::PrefixSet>
+      prefix_set(CreatePrefixSet(add_prefixes));
+
   // 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);
 
     // TODO(shess): If |CacheHashResults()| is posted between the
     // earlier lock and this clear, those pending hashes will be lost.
     // It could be fixed by only removing hashes which were collected
     // at the earlier point.  I believe that is fail-safe as-is (the
     // hash will be fetched again).
     pending_browse_hashes_.clear();
     prefix_miss_cache_.clear();
     browse_bloom_filter_.swap(filter);
+    prefix_set_.swap(prefix_set);
   }
 
   const base::TimeDelta bloom_gen = base::Time::Now() - before;
 
   // Persist the bloom filter to disk.  Since only this thread changes
   // |browse_bloom_filter_|, there is no need to lock.
   WriteBloomFilter();
 
   // Gather statistics.
   if (got_counters && metric->GetIOCounters(&io_after)) {
@@ skipping 63 matching lines @@
     return;
   }
 
   const base::TimeTicks before = base::TimeTicks::Now();
   browse_bloom_filter_ = BloomFilter::LoadFile(bloom_filter_filename_);
   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));
 }
 
 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);
 }