Add Certificate Transparency logs auditing

components/certificate_transparency/single_tree_tracker.h

Index: components/certificate_transparency/single_tree_tracker.h
diff --git a/components/certificate_transparency/single_tree_tracker.h b/components/certificate_transparency/single_tree_tracker.h
index f7afe72c3b449ed80396f12f54744cce005f38cf..8c14e4c7a650223600f4f4dc17fadc169e06c07c 100644
--- a/components/certificate_transparency/single_tree_tracker.h
+++ b/components/certificate_transparency/single_tree_tracker.h
@@ -6,26 +6,35 @@
 #define COMPONENTS_CERTIFICATE_TRANSPARENCY_SINGLE_TREE_TRACKER_H_
 
 #include <map>
+#include <memory>
 #include <string>
 
+#include "base/containers/mru_cache.h"
+#include "base/memory/memory_pressure_monitor.h"
 #include "base/memory/ref_counted.h"
-#include "base/time/time.h"
+#include "base/memory/weak_ptr.h"
 #include "net/cert/ct_verifier.h"
 #include "net/cert/signed_tree_head.h"
 #include "net/cert/sth_observer.h"
 
 namespace net {
+
 class CTLogVerifier;
 class X509Certificate;
 
 namespace ct {
+
+struct MerkleAuditProof;
 struct SignedCertificateTimestamp;
+
 }  // namespace ct
 
 }  // namespace net
 
 namespace certificate_transparency {
 
+class LogDnsClient;
+
 // Tracks the state of an individual Certificate Transparency Log's Merkle Tree.
 // A CT Log constantly issues Signed Tree Heads, for which every older STH must
 // be incorporated into the current/newer STH. As new certificates are logged,
@@ -48,8 +57,6 @@ namespace certificate_transparency {
 class SingleTreeTracker : public net::CTVerifier::Observer,
                           public net::ct::STHObserver {
  public:
-  // TODO(eranm): This enum will expand to include check success/failure,
-  // see crbug.com/506227
   enum SCTInclusionStatus {
     // SCT was not observed by this class and is not currently pending
     // inclusion check. As there's no evidence the SCT this status relates
@@ -62,11 +69,15 @@ class SingleTreeTracker : public net::CTVerifier::Observer,
     SCT_PENDING_NEWER_STH,
 
     // SCT is known and there's a new-enough STH to check inclusion against.
-    // Actual inclusion check has to be performed.
-    SCT_PENDING_INCLUSION_CHECK
+    // It's in the process of being checked for inclusion.
+    SCT_PENDING_INCLUSION_CHECK,
+
+    // Inclusion check succeeded.
+    SCT_INCLUDED_IN_LOG,
   };
 
-  explicit SingleTreeTracker(scoped_refptr<const net::CTLogVerifier> ct_log);
+  SingleTreeTracker(scoped_refptr<const net::CTLogVerifier> ct_log,
+                    LogDnsClient* dns_client);
   ~SingleTreeTracker() override;
 
   // net::ct::CTVerifier::Observer implementation.
@@ -96,17 +107,55 @@ class SingleTreeTracker : public net::CTVerifier::Observer,
       const net::ct::SignedCertificateTimestamp* sct);
 
  private:
+  struct EntryToAudit;
+  struct EntryAuditState;
+
+  // Orders instances by the timestamp of the SCT they contain.

[Ryan Sleevi, 2016/11/14 05:03:28]

nit: What sort of ordering? :)

// Less-than comparator that orders entries from the oldest SCT timestamp to the
newest SCT timestamp

?

[Eran Messeri, 2016/11/16 14:24:11]

Done.

+  struct OrderByTimestamp {
+    bool operator()(const EntryToAudit& lhs, const EntryToAudit& rhs) const;
+  };
+
+  // Requests an inclusion proof for each of the entries in |pending_entries_|
+  // (until throttled by the LogDnsClient).

[Ryan Sleevi, 2016/11/14 05:03:28]

nit: is the parenthetical necessary? Seems significant - not incidental.

[Eran Messeri, 2016/11/16 14:24:11]

Done.

+  // NOTE: See the EntryAuditState documentation on the different states
+  // an entry can be at.
+  void ProcessPendingEntries();
+
+  // Identical to the public GetLogEntryInclusionStatus, except it
+  // operates on an |entry| rather than cert, SCT combination.
+  SCTInclusionStatus GetLogEntryInclusionStatus(const EntryToAudit& entry);

[Ryan Sleevi, 2016/11/14 05:03:28]

Given the public/private split and subtlety, I don't think this meets the
criteria of
https://google.github.io/styleguide/cppguide.html#Function_Overloading and
should be renamed

GetAuditedEntryInclusionStatus ?

[Eran Messeri, 2016/11/16 14:24:10]

Done.

+
+  // LogDnsClient callbacks

[Ryan Sleevi, 2016/11/14 05:03:28]

nit: I haven't really seen comments like this (e.g. "callbacks"). It doesn't
tell me what this does/what it's for (other than documenting an implementation
detail).

// Invoked when [X], does [Y]

might be more useful here. Just going from the header.

[Eran Messeri, 2016/11/16 14:24:10]

Done.

+  void OnAuditProofObtained(const EntryToAudit* entry, int net_error);
+
+  // Clear entries on low memory notifications callback.
+  void OnMemoryPressure(
+      base::MemoryPressureListener::MemoryPressureLevel memory_pressure_level);
+
   // Holds the latest STH fetched and verified for this log.
   net::ct::SignedTreeHead verified_sth_;
 
   // The log being tracked.
   scoped_refptr<const net::CTLogVerifier> ct_log_;
 
-  // List of log entries pending inclusion check.
-  // TODO(eranm): Rather than rely on the timestamp, extend to to use the
-  // whole MerkleTreeLeaf (RFC6962, section 3.4.) as a key. See
-  // https://crbug.com/506227#c22 and https://crbug.com/613495
-  std::map<base::Time, SCTInclusionStatus> entries_status_;
+  // Map of *pending* log entries to their state.

[Ryan Sleevi, 2016/11/14 05:03:28]

nit: omit *

[Eran Messeri, 2016/11/16 14:24:11]

Done.

+  std::map<EntryToAudit, EntryAuditState, OrderByTimestamp> pending_entries_;
+
+  // A cache of hashes identifying entries which were checked for inclusion.
+  // For a given entry, the 'true' value in the cache indicates successful
+  // inclusion check, 'false' indicates inclusion check failure.
+  // NOTE: The current implementation does not cache failures, so all
+  // values are expected to be 'true'.

[Ryan Sleevi, 2016/11/14 05:03:28]

So why store by bool, and not an empty no-op class?

[Eran Messeri, 2016/11/16 14:24:10]

Done, I hope: I've added a struct (EntryAuditResult) with no fields as the value
type.

+  // TODO(eranm): Use SHA256HashValue as the key to the MRUCache once it is
+  // possible to provide a comparator for it to the MRUCache.

[Ryan Sleevi, 2016/11/14 05:03:28]

Is there a bug #? Is there an explanation about why that would or would not be
desirable? Is there a context for why you're using SHA256 as the hash versus
something else?

[Eran Messeri, 2016/11/16 14:24:10]

Done:
(1) Explicitly state that  the hash here is the leaf hash of the entry, which is
already calculated and is the way to uniquely identify entries in the tree.
(2) Filed a bug (and added a link from here) explaining why the SHA256HashValue
type can't be used in the MRUCache.

+  base::MRUCache<std::string, bool> checked_entries_;
+
+  // A DNS client for querying the log.
+  LogDnsClient* dns_client_;
+
+  std::unique_ptr<base::MemoryPressureListener> memory_pressure_listener_;
+
+  base::WeakPtrFactory<SingleTreeTracker> weak_factory_;
 
   DISALLOW_COPY_AND_ASSIGN(SingleTreeTracker);
 };