Cleanup histograms tracking prefix-set issues in safe-browsing.

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 218 matching lines @@
   return a.full_hash.prefix < b.full_hash.prefix;
 }
 
 // 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,
+  // Hits to prefix set and bloom filter.
+  PREFIX_SET_HIT,
+  PREFIX_SET_BLOOM_HIT,
+  // These were to track bloom misses which hit the prefix set, with
+  // _INVALID to track where the item didn't appear to actually be in
+  // the prefix set.  _INVALID was never hit.
+  PREFIX_SET_BLOOM_MISS_PREFIX_SET_HIT,
+  PREFIX_SET_BLOOM_MISS_PREFIX_SET_HIT_INVALID_OBSOLETE,
+  // GetPrefixes() after creation failed to get the same prefixes.
   PREFIX_SET_GETPREFIXES_BROKEN,
-  PREFIX_SET_GETPREFIXES_BROKEN_SIZE,
-  PREFIX_SET_GETPREFIXES_FIRST_BROKEN,
-  PREFIX_SET_SBPREFIX_WAS_BROKEN,
-  PREFIX_SET_GETPREFIXES_BROKEN_SORTING,
-  PREFIX_SET_GETPREFIXES_BROKEN_DUPLICATION,
-  PREFIX_SET_GETPREFIX_UNSORTED_IS_DELTA,
-  PREFIX_SET_GETPREFIX_UNSORTED_IS_INDEX,
-  PREFIX_SET_GETPREFIX_CHECKSUM_MISMATCH,
+  // Fine-grained tests which didn't provide any good direction.
+  PREFIX_SET_GETPREFIXES_BROKEN_SIZE_OBSOLETE,
+  PREFIX_SET_GETPREFIXES_FIRST_BROKEN_OBSOLETE,
+  PREFIX_SET_SBPREFIX_WAS_BROKEN_OBSOLETE,
+  PREFIX_SET_GETPREFIXES_BROKEN_SORTING_OBSOLETE,
+  PREFIX_SET_GETPREFIXES_BROKEN_DUPLICATION_OBSOLETE,
+  PREFIX_SET_GETPREFIXES_UNSORTED_IS_DELTA_OBSOLETE,
+  PREFIX_SET_GETPREFIXES_UNSORTED_IS_INDEX_OBSOLETE,
+  // Failed checksum when creating prefix set.
+  PREFIX_SET_CREATE_PREFIX_SET_CHECKSUM,
 
   // 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);
 }
 
+// Helper to reduce code duplication.
+safe_browsing::PrefixSet* CreateEmptyPrefixSet() {
+  return new safe_browsing::PrefixSet(std::vector<SBPrefix>());
+}
+
 // Generate a |PrefixSet| instance from the contents of
 // |add_prefixes|.  Additionally performs various checks to make sure
-// that the resulting prefix set is valid, so that the
-// PREFIX_SET_EVENT_BLOOM_MISS_PREFIX_HIT_INVALID histogram in
+// that the resulting prefix set is valid, so that histograms in
 // ContainsBrowseUrl() can be trustworthy.
 safe_browsing::PrefixSet* PrefixSetFromAddPrefixes(
     const SBAddPrefixes& add_prefixes) {
   // TODO(shess): If |add_prefixes| were sorted by the prefix, it
   // could be passed directly to |PrefixSet()|, removing the need for
   // |prefixes|.  For now, |prefixes| is useful while debugging
   // things.
   std::vector<SBPrefix> prefixes;
   prefixes.reserve(add_prefixes.size());
   for (SBAddPrefixes::const_iterator iter = add_prefixes.begin();
        iter != add_prefixes.end(); ++iter) {
     prefixes.push_back(iter->prefix);
   }
 
   std::sort(prefixes.begin(), prefixes.end());
   prefixes.erase(std::unique(prefixes.begin(), prefixes.end()),
                  prefixes.end());
 
   scoped_ptr<safe_browsing::PrefixSet>
       prefix_set(new safe_browsing::PrefixSet(prefixes));
 
   std::vector<SBPrefix> restored;
   prefix_set->GetPrefixes(&restored);
 
   // Expect them to be equal.
   if (restored.size() == prefixes.size() &&
       std::equal(prefixes.begin(), prefixes.end(), restored.begin()))
     return prefix_set.release();
 
-  // Log BROKEN for continuity with previous release, and SIZE to
-  // distinguish which test failed.
+  // NOTE(shess): Past histograms have indicated that in a given day,
+  // about 1 in 100,000 updates result in a PrefixSet which was
+  // inconsistent relative to the BloomFilter.  Windows is about 5x
+  // more likely to build an inconsistent PrefixSet than Mac.  A
+  // number of developers have reviewed the code, and I ran extensive
+  // fuzzing with random data, so at this point I'm trying to
+  // demonstrate memory corruption.
+  //
+  // Other findings from past instrumentation:
+  // - half of one percent of brokenness cases implied duplicate items
+  //   in |prefixes|.  Per the code above, this should not be
+  //   possible.
+  // - about 1/20 of broken cases happened more than once for a given
+  //   user.  Note that empty updates generally don't hit this code at
+  //   all, so that may not imply a specific input pattern breaking things.
+  // - about 1/3 of broken cases show a checksum mismatch between the
+  //   checksum calculated while creating |prefix_set| and the
+  //   checksum calculated immediately after creation.  This is almost
+  //   certainly memory corruption.
   NOTREACHED();
   RecordPrefixSetInfo(PREFIX_SET_GETPREFIXES_BROKEN);
-  if (restored.size() != prefixes.size())
-    RecordPrefixSetInfo(PREFIX_SET_GETPREFIXES_BROKEN_SIZE);
 
-  // Try to distinguish between updates from one broken user and a
-  // distributed problem.
-  static bool logged_broken = false;
-  if (!logged_broken) {
-    RecordPrefixSetInfo(PREFIX_SET_GETPREFIXES_FIRST_BROKEN);
-    logged_broken = true;
-  }
+  // Broken because internal memory was corrupted during construction.
+  if (!prefix_set->CheckChecksum())
+    RecordPrefixSetInfo(PREFIX_SET_CREATE_PREFIX_SET_CHECKSUM);
 
-  // This seems so very very unlikely.  But if it ever were true, then
-  // it could explain why GetPrefixes() seemed broken.
-  if (sizeof(int) != sizeof(int32))
-    RecordPrefixSetInfo(PREFIX_SET_SBPREFIX_WAS_BROKEN);
+  // TODO(shess): Test whether |prefixes| changed during construction.
 
-  // Check if memory was corrupted during construction.
-  if (!prefix_set->CheckChecksum())
-    RecordPrefixSetInfo(PREFIX_SET_GETPREFIX_CHECKSUM_MISMATCH);
-
-  // Check whether |restored| is unsorted, or has duplication.
-  if (restored.size()) {
-    size_t unsorted_count = 0;
-    bool duplicates = false;
-    SBPrefix prev = restored[0];
-    for (size_t i = 0; i < restored.size(); prev = restored[i], ++i) {
-      if (prev > restored[i]) {
-        unsorted_count++;
-        UMA_HISTOGRAM_COUNTS("SB2.PrefixSetUnsortedDifference",
-                             prev - restored[i]);
-
-        // When unsorted, how big is the set, and how far are we into
-        // it.  If the set is very small or large, that might inform
-        // pursuit of a degenerate case.  If the percentage is close
-        // to 0%, 100%, or 50%, then there might be an interesting
-        // degenerate case to explore.
-        UMA_HISTOGRAM_COUNTS("SB2.PrefixSetUnsortedSize", restored.size());
-        UMA_HISTOGRAM_PERCENTAGE("SB2.PrefixSetUnsortedPercent",
-                                 i * 100 / restored.size());
-
-        if (prefix_set->IsDeltaAt(i)) {
-          RecordPrefixSetInfo(PREFIX_SET_GETPREFIX_UNSORTED_IS_DELTA);
-
-          // Histograms require memory on the order of the number of
-          // buckets, making high-precision logging expensive.  For
-          // now aim for a sense of the range of the problem.
-          UMA_HISTOGRAM_CUSTOM_COUNTS("SB2.PrefixSetUnsortedDelta",
-                                      prefix_set->DeltaAt(i), 1, 0xFFFF, 50);
-        } else {
-          RecordPrefixSetInfo(PREFIX_SET_GETPREFIX_UNSORTED_IS_INDEX);
-        }
-      }
-      if (prev == restored[i])
-        duplicates = true;
-    }
-
-    // Record findings.
-    if (unsorted_count) {
-      RecordPrefixSetInfo(PREFIX_SET_GETPREFIXES_BROKEN_SORTING);
-      UMA_HISTOGRAM_COUNTS_100("SB2.PrefixSetUnsorted", unsorted_count);
-    }
-    if (duplicates)
-      RecordPrefixSetInfo(PREFIX_SET_GETPREFIXES_BROKEN_DUPLICATION);
-
-    // Fix the problems noted.  If |restored| was unsorted, then
-    // |duplicates| may give a false negative.
-    if (unsorted_count)
-      std::sort(restored.begin(), restored.end());
-    if (unsorted_count || duplicates)
-      restored.erase(std::unique(restored.begin(), restored.end()),
-                     restored.end());
-  }
-
-  // NOTE(shess): The following could be done using a single
-  // uber-loop, but it's complicated by needing multiple parallel
-  // iterators.  Didn't seem worthwhile for something that will only
-  // live for a short period and only fires for one in a million
-  // updates.
-
-  // Find elements in |restored| which are not in |prefixes|.
-  std::vector<SBPrefix> difference;
-  std::set_difference(restored.begin(), restored.end(),
-                      prefixes.begin(), prefixes.end(),
-                      std::back_inserter(difference));
-  if (difference.size())
-    UMA_HISTOGRAM_COUNTS_100("SB2.PrefixSetRestoredExcess", difference.size());
-
-  // Find elements in |prefixes| which are not in |restored|.
-  difference.clear();
-  std::set_difference(prefixes.begin(), prefixes.end(),
-                      restored.begin(), restored.end(),
-                      std::back_inserter(difference));
-  if (difference.size())
-    UMA_HISTOGRAM_COUNTS_100("SB2.PrefixSetRestoredShortfall",
-                             difference.size());
-
-  return prefix_set.release();
+  return CreateEmptyPrefixSet();
 }
 
 }  // namespace
 
 // The default SafeBrowsingDatabaseFactory.
 class SafeBrowsingDatabaseFactoryImpl : public SafeBrowsingDatabaseFactory {
  public:
   virtual SafeBrowsingDatabase* CreateSafeBrowsingDatabase(
       bool enable_download_protection,
       bool enable_client_side_whitelist,
@@ skipping 202 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(new safe_browsing::PrefixSet(std::vector<SBPrefix>()));
+    prefix_set_.reset(CreateEmptyPrefixSet());
   }
   // Wants to acquire the lock itself.
   WhitelistEverything(&csd_whitelist_);
   WhitelistEverything(&download_whitelist_);
 
   return true;
 }
 
 // TODO(lzheng): Remove matching_list, it is not used anywhere.
 bool SafeBrowsingDatabaseNew::ContainsBrowseUrl(
@@ skipping 17 matching lines @@
   base::AutoLock locked(lookup_lock_);
 
   if (!browse_bloom_filter_.get())
     return false;
   DCHECK(prefix_set_.get());
 
   // |prefix_set_| is empty until the first update, only log info if
   // not empty.
   const bool prefix_set_empty = !prefix_set_->GetSize();
 
-  // 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 < full_hashes.size(); ++i) {
     bool found = prefix_set_->Exists(full_hashes[i].prefix);
 
     if (browse_bloom_filter_->Exists(full_hashes[i].prefix)) {
       if (!prefix_set_empty) {
-        RecordPrefixSetInfo(PREFIX_SET_EVENT_BLOOM_HIT);
+        RecordPrefixSetInfo(PREFIX_SET_BLOOM_HIT);
+        // This should be less than PREFIX_SET_BLOOM_HIT by the
+        // false positive rate.
         if (found)
-          RecordPrefixSetInfo(PREFIX_SET_EVENT_HIT);
+          RecordPrefixSetInfo(PREFIX_SET_HIT);
       }
       prefix_hits->push_back(full_hashes[i].prefix);
       if (prefix_miss_cache_.count(full_hashes[i].prefix) > 0)
         ++miss_count;
     } else {
-      // 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.
+      // Bloom filter misses should never be in prefix set.
       DCHECK(!found);
-      if (found && !prefix_set_empty) {
-        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(),
-                               full_hashes[i].prefix)) {
-          RecordPrefixSetInfo(PREFIX_SET_EVENT_BLOOM_MISS_PREFIX_HIT);
-        } else {
-          RecordPrefixSetInfo(PREFIX_SET_EVENT_BLOOM_MISS_PREFIX_HIT_INVALID);
-        }
-      }
+      if (found)
+        RecordPrefixSetInfo(PREFIX_SET_BLOOM_MISS_PREFIX_SET_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 674 matching lines @@
 
   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);
 
   // Use an empty prefix set until the first update.
-  prefix_set_.reset(new safe_browsing::PrefixSet(std::vector<SBPrefix>()));
+  prefix_set_.reset(CreateEmptyPrefixSet());
 }
 
 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 64 matching lines @@
   if (std::binary_search(new_whitelist.begin(), new_whitelist.end(),
                          kill_switch)) {
     // The kill switch is whitelisted hence we whitelist all URLs.
     WhitelistEverything(whitelist);
   } else {
     base::AutoLock locked(lookup_lock_);
     whitelist->second = false;
     whitelist->first.swap(new_whitelist);
   }
 }