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..7ba00fad47199f414044b03e8054b2f51c0eb168 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,66 @@ class SingleTreeTracker : public net::CTVerifier::Observer,
       const net::ct::SignedCertificateTimestamp* sct);
 
  private:
+  struct EntryToAudit;
+  struct EntryAuditState;
+  struct EntryAuditResult;
+
+  // Less-than comparator that orders entries from the oldest SCT timestamp to
+  // the newest SCT timestamp
+  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.
+  // NOTE: See the EntryAuditState documentation on the different states
+  // an entry can be at.

[Ryan Sleevi, 2016/12/22 21:33:21]

Considering that EntryAuditState is in the .cc file, I suspect we can ditch this
NOTE entirely. If you absolutely, positively feel it's necessary, perhaps it's
more suitable to being moved to the .cc, per the "Function Definitions" section
of https://google.github.io/styleguide/cppguide.html#Function_Comments

[Eran Messeri, 2017/01/03 23:07:41]

Done - removed the NOTE.

+  void ProcessPendingEntries();
+
+  // Identical to the public GetLogEntryInclusionStatus, except it
+  // operates on an |entry| rather than cert, SCT combination.
+  SCTInclusionStatus GetAuditedEntryInclusionStatus(const EntryToAudit& entry);
+
+  // Invoked by the LogDnsClient once an audit proof request was completed.
+  // Verifies the audit proof and updates the state of the entry accordingly:
+  // * If the audit proof was obtained successfully and validated, then
+  //   calls to GetLogEntryInclusionStatus with this entry will indicate
+  //   that the entry is included.
+  // * If there was a failure to obtain the inclusion proof or it did not
+  //   validate, it is removed from the internal queue and considered to be
+  //   un-audited.
+  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.
+  std::map<EntryToAudit, EntryAuditState, OrderByTimestamp> pending_entries_;
+
+  // A cache of leaf hashes identifying entries which were checked for
+  // inclusion (the key is the Leaf Hash of the log entry).
+  // NOTE: The current implementation does not cache failures, the
+  // EntryAuditResult
+  // struct is empty.

[Ryan Sleevi, 2016/12/22 21:33:21]

wrapping?

[Eran Messeri, 2017/01/03 23:07:41]

Done.

+  // TODO(eranm): The std::string type is used as the key for the MRUCache
+  // because it is not possible to use the SHA256HashValue class directly
+  // (see https://crbug.com/665735). Once that's possible, switch to using
+  // SHA256HashValue as the key type, thus sparing copying the hash value.
+  base::MRUCache<std::string, EntryAuditResult> checked_entries_;
+
+  // A DNS client for querying the log.

[Ryan Sleevi, 2016/12/22 21:33:21]

This seems to be more descriptive of "what it is" (e.g. it's a redundant
comment) rather than "what it does" -
https://google.github.io/styleguide/cppguide.html#Variable_Comments

"However, if the type and name suffice (int num_events_;), no comment is
needed."

(This is a relatively recent-ish update to the style guide -
https://github.com/google/styleguide/commit/f15e633de5b716a966504e0652fb0c85c...
- so you no longer have to worry about me nagging :P)

[Eran Messeri, 2017/01/03 23:07:41]

Done - per your recommendation & the recent update to the style guide, removed
the comment.

+  LogDnsClient* dns_client_;
+
+  std::unique_ptr<base::MemoryPressureListener> memory_pressure_listener_;
+
+  base::WeakPtrFactory<SingleTreeTracker> weak_factory_;
 
   DISALLOW_COPY_AND_ASSIGN(SingleTreeTracker);
 };