More fine-grained pruning in safe browsing incident reporting service.

chrome/browser/safe_browsing/incident_reporting_service.cc

 // Copyright 2014 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/incident_reporting_service.h"
 
 #include <math.h>
 
 #include <algorithm>
 #include <vector>
 
+#include "base/hash.h"
 #include "base/metrics/histogram.h"
 #include "base/prefs/pref_service.h"
+#include "base/prefs/scoped_user_pref_update.h"
 #include "base/process/process_info.h"
 #include "base/stl_util.h"
+#include "base/strings/string_number_conversions.h"
 #include "base/threading/sequenced_worker_pool.h"
+#include "base/values.h"
 #include "chrome/browser/browser_process.h"
 #include "chrome/browser/chrome_notification_types.h"
 #include "chrome/browser/prefs/tracked/tracked_preference_validation_delegate.h"
 #include "chrome/browser/profiles/profile.h"
 #include "chrome/browser/safe_browsing/database_manager.h"
 #include "chrome/browser/safe_browsing/environment_data_collection.h"
 #include "chrome/browser/safe_browsing/incident_report_uploader_impl.h"
 #include "chrome/browser/safe_browsing/preference_validation_delegate.h"
 #include "chrome/browser/safe_browsing/safe_browsing_service.h"
 #include "chrome/common/pref_names.h"
@@ skipping 11 matching lines @@
   // the histogram.
   TRACKED_PREFERENCE = 1,
   NUM_INCIDENT_TYPES
 };
 
 enum IncidentDisposition {
   DROPPED,
   ACCEPTED,
 };
 
+// The state persisted for a specific instance of an incident to enable pruning
+// of previously-reported incidents.
+struct PersistentIncidentState {
+  // The type of the incident.
+  IncidentType type;
+
+  // The key for a specific instance of an incident.
+  std::string key;
+
+  // A hash digest representing a specific instance of an incident.
+  uint32_t digest;
+};

[Scott Hess - ex-Googler, 2014/07/23 22:05:51]

Is there any system to how these are organized?  They don't seem to be
alphabetic or anything like that, nor do they seem to be grouped by related
types.

[grt (UTC plus 2), 2014/07/24 18:58:40]

I was attempting to roughly follow the declaration order
(http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml?showone=Declar...),
but I see that kDefaultUploadDelayMs ended up between types. Ooops. I've moved
things a bit (see reply below) and added a few more comments.

+
 const int64 kDefaultUploadDelayMs = 1000 * 60;  // one minute
 
+// Handlers for a specific type of incident.
+struct IncidentTypeHandlers {
+  // The type of incident to which these handlers apply.
+  IncidentType type;
+
+  // A function that returns a unique key representing an incident.
+  std::string (*get_key_fn)(const ClientIncidentReport_IncidentData&);
+
+  // A function that returns a hash digest of an incident's data.
+  uint32_t (*get_digest_fn)(const ClientIncidentReport_IncidentData&);
+};
+
+// Forward declarations of incident type handler functions.
+std::string GetTrackedPreferenceIncidentKey(
+    const ClientIncidentReport_IncidentData& incident_data);
+uint32_t GetTrackedPreferenceIncidentDigest(
+    const ClientIncidentReport_IncidentData& incident_data);
+
+// The collection of handlers for all incident types.
+const IncidentTypeHandlers kIncidentTypeHandlers[] = {
+    {TRACKED_PREFERENCE,
+     &GetTrackedPreferenceIncidentKey,
+     &GetTrackedPreferenceIncidentDigest},
+};
+
+// Returns the type of incident contained in |incident_data|.
+IncidentType GetIncidentType(
+    const ClientIncidentReport_IncidentData& incident_data) {
+  // Add logic once other types are supported.
+  DCHECK(incident_data.has_tracked_preference());
+
+  return TRACKED_PREFERENCE;
+}
+
+// Returns the handlers for a given type of incident.
+const IncidentTypeHandlers* GetIncidentTypeHandlers(IncidentType type) {

[Scott Hess - ex-Googler, 2014/07/23 22:05:50]

This seems like a kind of elaborate setup to replace a function something like:

std::pair<std::string,uint32_t> GetIncidentInfo(IncidentType type) {
  switch(type) {
    case TRACKED_PREFERENCE:
      return std::make_pair(path(), HashMessage(tracked_preference()));
    //...
  }
}
// Or have each case vector to a helper fn, with this fn replacing the table.

Neither the CL description nor the associated bug gives me any context for
assuming that there will just happen to be appropriate callbacks out in the wild
generating the right key and digest, so is there something else driving all of
the indirections?

[grt (UTC plus 2), 2014/07/24 18:58:40]

There will be more incident types in the future. I thought the data-driven
approach would scale better, and makes it clear to developers what two bits of
functionality they need to provide. To make this even more explicit, I've moved
the incident-specific bits into their own file (with their own tests).

[Scott Hess - ex-Googler, 2014/07/24 21:22:19]

I like the tests, my main complaint here was mostly about creating a system
which looks a lot like what vtables already do.  I'm still not 100% convinced
that editing "a table of unique types plus function pointers which someone loops
over" is really an improvement over editing "a function with a switch
statement", regardless of where the functions either setup calls out to live,
but you'll be owning the code, so ...

[grt (UTC plus 2), 2014/07/24 22:58:11]

You've convinced me. While I liked the idea that developers would only need to
touch one thing to add support for new types, it seems that it's complex to at
least one developer-who-is-not-the-implementor, so it's better to go with
something more simple. let me know what you think.

+  for (size_t i = 0; i < arraysize(kIncidentTypeHandlers); ++i) {
+    if (kIncidentTypeHandlers[i].type == type)
+      return &kIncidentTypeHandlers[i];
+  }
+  NOTREACHED();
+  return NULL;
+}
+
+// Computes a simple hash digest over the serialized form of |message|.
+uint32_t HashMessage(const google::protobuf::MessageLite& message) {
+  std::string message_string;
+  if (!message.SerializeToString(&message_string)) {
+    NOTREACHED();
+    return 0;
+  }
+  return base::Hash(message_string);
+}

[Scott Hess - ex-Googler, 2014/07/23 22:05:51]

This seems questionable, to me.  I think that if you serialize a message where
an optional value is not set, that will be different from if you serialize a
message where an optional value is set to the default value.  In which case the
resulting hash will also be different.

[grt (UTC plus 2), 2014/07/24 18:58:40]

Ah, yes. I hadn't thought about optional values when I was weighing this
approach. I guess it'll be a bit more work for creators of new incident types.

[Scott Hess - ex-Googler, 2014/07/24 21:22:19]

It's plausible that the code paths which lead here will always set things in the
same way, so that there is no practical possibility of divergence, or it could
always be detected and cleaned up easily.  It is also possible that these should
actually be treated as different values (effectively undef differs from a set
value).  I don't understand your overall scheme well enough to know if these
things matter.

[grt (UTC plus 2), 2014/07/24 22:58:11]

I'm conflicted about this. In the current implementation for the one existing
incident, there's no problem with the simple serialization (i've reverted the
impl to this). I'll make myself a per-file owner so I'm sure to verify future
implementations.

+
+// Returns the path of the tracked preference.
+std::string GetTrackedPreferenceIncidentKey(
+    const ClientIncidentReport_IncidentData& incident_data) {
+  DCHECK(incident_data.has_tracked_preference());
+  return incident_data.tracked_preference().path();
+}
+
+// Returns a digest computed over the tracked preference incident data.
+uint32_t GetTrackedPreferenceIncidentDigest(
+    const ClientIncidentReport_IncidentData& incident_data) {
+  DCHECK(incident_data.has_tracked_preference());
+  return HashMessage(incident_data.tracked_preference());
+}
+
+// Logs the type of incident in |incident_data| to a user metrics histogram.
 void LogIncidentDataType(
     IncidentDisposition disposition,
     const ClientIncidentReport_IncidentData& incident_data) {
-  IncidentType type = TRACKED_PREFERENCE;
-
-  // Add a switch statement once other types are supported.
-  DCHECK(incident_data.has_tracked_preference());
-
+  IncidentType type = GetIncidentType(incident_data);
   if (disposition == ACCEPTED) {
     UMA_HISTOGRAM_ENUMERATION("SBIRS.Incident", type, NUM_INCIDENT_TYPES);
   } else {
     DCHECK_EQ(disposition, DROPPED);
     UMA_HISTOGRAM_ENUMERATION("SBIRS.DroppedIncident", type,
                               NUM_INCIDENT_TYPES);
   }
 }
 
+// Computes the persistent state for an incident.
+PersistentIncidentState ComputeIncidentState(
+    const ClientIncidentReport_IncidentData& incident) {
+  PersistentIncidentState state;
+
+  state.type = GetIncidentType(incident);
+  const IncidentTypeHandlers* handlers = GetIncidentTypeHandlers(state.type);
+  state.key = handlers->get_key_fn(incident);
+  state.digest = handlers->get_digest_fn(incident);
+
+  return state;
+}
+
+// Returns true if the incident described by |state| has already been reported
+// based on the bookkeeping in the |incidents_sent| preference dictionary.
+bool IncidentHasBeenReported(const base::DictionaryValue* incidents_sent,
+                             const PersistentIncidentState& state) {
+  const base::DictionaryValue* type_dict = NULL;
+  std::string digest_string;
+  uint32_t digest = 0;
+  return (incidents_sent &&
+          incidents_sent->GetDictionaryWithoutPathExpansion(
+              base::IntToString(state.type), &type_dict) &&
+          type_dict->GetStringWithoutPathExpansion(state.key, &digest_string) &&
+          base::StringToUint(digest_string, &digest) &&
+          digest == state.digest);

[Scott Hess - ex-Googler, 2014/07/23 22:05:51]

Could the last two lines be:
    digest_string == base::UintToString(state.digest)
?  It is possible that the round trip back to uint32_t will give different
results, in which case this will never return true, even though the code below
keeps setting the string from the digest.

[grt (UTC plus 2), 2014/07/24 18:58:40]

Rock on.
I didn't realize there was ambiguity in the uint->string->uint dance. I've tried
it with all values I could come up with (2^32 of 'em), and they all round-trip
safely. What am I missing?

[Scott Hess - ex-Googler, 2014/07/24 21:22:19]

I wouldn't expect there to be any cases where things won't round-trip correctly,
just the observation that all uint32_t can be represented by std::string but not
all std::string can be represented by uint32_t.

[Maybe I've written too many conversions over the years and now am all calcified
:-).]

[grt (UTC plus 2), 2014/07/24 22:58:11]

Ah. I'm not concerned about that. If code outside of this module diddles with
the preference such that the string cannot be turned back into the correct int,
the right thing to do is to treat that as the incident not having been reported.
This is exactly what will happen. I appreciate the scrutiny.

+}
+
+// Marks the incidents described by |states| as having been reported
+// in |incidents_set|.
+void MarkIncidentsAsReported(const std::vector<PersistentIncidentState>& states,
+                             base::DictionaryValue* incidents_sent) {
+  for (size_t i = 0; i < states.size(); ++i) {
+    const PersistentIncidentState& data = states[i];
+    base::DictionaryValue* type_dict = NULL;
+    const std::string type_string(base::IntToString(data.type));
+    if (!incidents_sent->GetDictionaryWithoutPathExpansion(type_string,
+                                                           &type_dict)) {
+      type_dict = new base::DictionaryValue();
+      incidents_sent->SetWithoutPathExpansion(type_string, type_dict);
+    }
+    type_dict->SetStringWithoutPathExpansion(data.key,
+                                             base::UintToString(data.digest));
+  }
+}
+
 }  // namespace
 
 struct IncidentReportingService::ProfileContext {
   ProfileContext();
   ~ProfileContext();
 
   // The incidents collected for this profile pending creation and/or upload.
   ScopedVector<ClientIncidentReport_IncidentData> incidents;
 
   // False until PROFILE_ADDED notification is received.
   bool added;
 
  private:
   DISALLOW_COPY_AND_ASSIGN(ProfileContext);
 };
 
 class IncidentReportingService::UploadContext {
  public:
+  typedef std::map<Profile*, std::vector<PersistentIncidentState> >
+      PersistentIncidentStateCollection;
+
   explicit UploadContext(scoped_ptr<ClientIncidentReport> report);
   ~UploadContext();
 
   // The report being uploaded.
   scoped_ptr<ClientIncidentReport> report;
 
   // The uploader in use. This is NULL until the CSD killswitch is checked.
   scoped_ptr<IncidentReportUploader> uploader;
 
-  // The set of profiles from which incidents in |report| originated.
-  std::vector<Profile*> profiles;
+  // A mapping of profiles to the data to be persisted upon successful upload.
+  PersistentIncidentStateCollection profiles_to_state;
 
  private:
   DISALLOW_COPY_AND_ASSIGN(UploadContext);
 };
 
 IncidentReportingService::ProfileContext::ProfileContext() : added() {
 }
 
 IncidentReportingService::ProfileContext::~ProfileContext() {
 }
@@ skipping 148 matching lines @@
   if (it == profiles_.end())
     return;
 
   // TODO(grt): Persist incidents for upload on future profile load.
 
   // Forget about this profile. Incidents not yet sent for upload are lost.
   // No new incidents will be accepted for it.
   delete it->second;
   profiles_.erase(it);
 
-  // Remove the association with this profile from any pending uploads.
-  for (size_t i = 0; i < uploads_.size(); ++i) {
-    UploadContext* upload = uploads_[i];
-    std::vector<Profile*>::iterator it =
-        std::find(upload->profiles.begin(), upload->profiles.end(), profile);
-    if (it != upload->profiles.end()) {
-      *it = upload->profiles.back();
-      upload->profiles.resize(upload->profiles.size() - 1);
-      break;
-    }
-  }
+  // Remove the association with this profile from all pending uploads.
+  for (size_t i = 0; i < uploads_.size(); ++i)
+    uploads_[i]->profiles_to_state.erase(profile);
 }
 
 void IncidentReportingService::AddIncident(
     Profile* profile,
     scoped_ptr<ClientIncidentReport_IncidentData> incident_data) {
   DCHECK(thread_checker_.CalledOnValidThread());
   // Incidents outside the context of a profile are not supported at the moment.
   DCHECK(profile);
 
   ProfileContext* context = GetProfileContext(profile);
@@ skipping 224 matching lines @@
   if (g_browser_process->local_state()->FindPreference(
           prefs::kMetricsReportingEnabled)) {
     process->set_metrics_consent(g_browser_process->local_state()->GetBoolean(
         prefs::kMetricsReportingEnabled));
   }
 
   // Check for extended consent in any profile while collecting incidents.
   process->set_extended_consent(false);
   // Collect incidents across all profiles participating in safe browsing. Drop
   // incidents if the profile stopped participating before collection completed.
-  // Prune incidents if the profile has already submitted any incidents.
-  // Associate the participating profiles with the upload.
+  // Prune previously submitted incidents.
+  // Associate the profiles and their incident data with the upload.
   size_t prune_count = 0;
-  std::vector<Profile*> profiles;
+  std::map<Profile*, std::vector<PersistentIncidentState> > profiles_to_state;

[Scott Hess - ex-Googler, 2014/07/23 22:05:51]

PersistentIncidentStateCollection?  The code belows swaps this with one of
those, so it should probalby use the same typedef, either as-is or lifted to the
anon namespace.

[grt (UTC plus 2), 2014/07/24 18:58:40]

Done.

   for (ProfileContextCollection::iterator scan = profiles_.begin();
        scan != profiles_.end();
        ++scan) {
     PrefService* prefs = scan->first->GetPrefs();
     if (process &&
         prefs->GetBoolean(prefs::kSafeBrowsingExtendedReportingEnabled)) {
       process->set_extended_consent(true);
       process = NULL;  // Don't check any more once one is found.
     }
     ProfileContext* context = scan->second;
     if (context->incidents.empty())
       continue;
     if (!prefs->GetBoolean(prefs::kSafeBrowsingEnabled)) {
       for (size_t i = 0; i < context->incidents.size(); ++i) {
         LogIncidentDataType(DROPPED, *context->incidents[i]);
       }
       context->incidents.clear();
-    } else if (prefs->GetBoolean(prefs::kSafeBrowsingIncidentReportSent)) {
-      // Prune all incidents.
-      // TODO(grt): Only prune previously submitted incidents;
-      // http://crbug.com/383043.
-      prune_count += context->incidents.size();
+      continue;
+    }
+    std::vector<PersistentIncidentState> states;
+    const base::DictionaryValue* incidents_sent =
+        prefs->GetDictionary(prefs::kSafeBrowsingIncidentsSent);
+    // Prep persistent data and prune any incidents already sent.
+    for (size_t i = 0; i < context->incidents.size(); ++i) {
+      ClientIncidentReport_IncidentData* incident = context->incidents[i];
+      const PersistentIncidentState state = ComputeIncidentState(*incident);
+      if (IncidentHasBeenReported(incidents_sent, state)) {
+        ++prune_count;
+        delete context->incidents[i];
+        context->incidents[i] = NULL;
+      } else {
+        states.push_back(state);
+      }
+    }
+    if (prefs->GetBoolean(prefs::kSafeBrowsingIncidentReportSent)) {
+      // Prune all incidents as if they had been reported, migrating to the new
+      // technique. TODO(grt): remove this branch after it has shipped.
+      for (size_t i = 0; i < context->incidents.size(); ++i) {
+        if (context->incidents[i])
+          ++prune_count;
+      }
       context->incidents.clear();
+      prefs->ClearPref(prefs::kSafeBrowsingIncidentReportSent);
+      DictionaryPrefUpdate pref_update(prefs,
+                                       prefs::kSafeBrowsingIncidentsSent);
+      MarkIncidentsAsReported(states, pref_update.Get());
     } else {
       for (size_t i = 0; i < context->incidents.size(); ++i) {
         ClientIncidentReport_IncidentData* incident = context->incidents[i];
-        LogIncidentDataType(ACCEPTED, *incident);
-        // Ownership of the incident is passed to the report.
-        report->mutable_incident()->AddAllocated(incident);
+        if (incident) {
+          LogIncidentDataType(ACCEPTED, *incident);
+          // Ownership of the incident is passed to the report.
+          report->mutable_incident()->AddAllocated(incident);
+        }
       }
       context->incidents.weak_clear();
-      profiles.push_back(scan->first);
+      std::vector<PersistentIncidentState>& profile_states =
+          profiles_to_state[scan->first];
+      profile_states.swap(states);
     }
   }
 
   const int count = report->incident_size();
   // Abandon the request if all incidents were dropped with none pruned.
   if (!count && !prune_count)
     return;
 
   UMA_HISTOGRAM_COUNTS_100("SBIRS.IncidentCount", count + prune_count);
 
   {
     double prune_pct = static_cast<double>(prune_count);
     prune_pct = prune_pct * 100.0 / (count + prune_count);
     prune_pct = round(prune_pct);
     UMA_HISTOGRAM_PERCENTAGE("SBIRS.PruneRatio", static_cast<int>(prune_pct));
   }
   // Abandon the report if all incidents were pruned.
   if (!count)
     return;
 
   scoped_ptr<UploadContext> context(new UploadContext(report.Pass()));
-  context->profiles.swap(profiles);
+  context->profiles_to_state.swap(profiles_to_state);
   if (!database_manager_) {
     // No database manager during testing. Take ownership of the context and
     // continue processing.
     UploadContext* temp_context = context.get();
     uploads_.push_back(context.release());
     IncidentReportingService::OnKillSwitchResult(temp_context, false);
   } else {
     if (content::BrowserThread::PostTaskAndReplyWithResult(
             content::BrowserThread::IO,
             FROM_HERE,
@@ skipping 34 matching lines @@
                            scoped_ptr<ClientIncidentResponse>());
     }
   } else {
     OnReportUploadResult(context,
                          IncidentReportUploader::UPLOAD_SUPPRESSED,
                          scoped_ptr<ClientIncidentResponse>());
   }
 }
 
 void IncidentReportingService::HandleResponse(const UploadContext& context) {
-  for (size_t i = 0; i < context.profiles.size(); ++i) {
-    context.profiles[i]->GetPrefs()->SetBoolean(
-        prefs::kSafeBrowsingIncidentReportSent, true);
+  for (UploadContext::PersistentIncidentStateCollection::const_iterator scan =
+           context.profiles_to_state.begin();
+       scan != context.profiles_to_state.end();
+       ++scan) {
+    DictionaryPrefUpdate pref_update(scan->first->GetPrefs(),
+                                     prefs::kSafeBrowsingIncidentsSent);
+    MarkIncidentsAsReported(scan->second, pref_update.Get());
   }
 }
 
 void IncidentReportingService::OnReportUploadResult(
     UploadContext* context,
     IncidentReportUploader::Result result,
     scoped_ptr<ClientIncidentResponse> response) {
   DCHECK(thread_checker_.CalledOnValidThread());
 
   UMA_HISTOGRAM_ENUMERATION(
@@ skipping 29 matching lines @@
       if (!profile->IsOffTheRecord())
         OnProfileDestroyed(profile);
       break;
     }
     default:
       break;
   }
 }
 
 }  // namespace safe_browsing