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..2e4888c44190b053eb24c28cf4d5cec5b0f2c2fc 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,16 @@ 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 inclusion checking - getting a leaf index
+    // or the inclusion proof itself.
+    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 +108,72 @@ class SingleTreeTracker : public net::CTVerifier::Observer,
       const net::ct::SignedCertificateTimestamp* sct);
 
  private:

[Ryan Sleevi, 2016/09/22 07:08:29]

In general, whenever there's a significant expansion of the "private" section of
a class, it generally is something that you can expect I'll flag as a design
smell :)

Anything that requires a lot of private: implementation generally signals that
1) The implementing class itself is large and complex and may be violating the
Single Responsibility Principle
2) All consumers are implicitly being made dependent on the implementation
details of this class, since they'd have to be recompiled any time this header
changes. That's usually a red flag

That's not to say private methods are forbidden, by no means, just that you're
going to get a lot of extra scrutiny from me ;)

[Eran Messeri, 2016/09/22 20:10:21]

Acknowledged and partially addressed: To address your other comments I've
removed two private methods, FetchIndexForEntry and FetchInclusionForEntry. The
rest is mostly callbacks.

If there are other  private methods that you think could be removed, do point
them out.
In that case I've encapsulated the different states for entries in the .cc.
If we change the LogDnsClient to have a single method that returns the inclusion
proof and leaf index, then the size of the private section is cut by a third -
maybe even more if throttling is synchronous (then the entry does not a state at
all).

+  struct EntryToAudit;
+  struct EntryAuditState;
+
+  // Orders instances by the timestamp of the SCT they contain.
+  struct OrderByTimestamp {
+    bool operator()(const EntryToAudit& lhs, const EntryToAudit& rhs) const;
+  };
+
+  using EntriesMap = std::map<EntryToAudit, EntryAuditState, OrderByTimestamp>;

[Ryan Sleevi, 2016/09/22 07:08:29]

Does this typedef (which is, effectively, only used once) provide value? Why?
Seems like we could just defer all this to the pending_entries_ and use auto /
typename when appropriate.

std::map<EntryToAudit, EntryAuditState, OrderByTimestamp> entries_map_;

[Eran Messeri, 2016/09/22 20:10:21]

It does not - removed.

+
+  // Requests the leaf index for the given entry from the LogDnsClient.
+  void FetchIndexForEntry(const EntryToAudit& entry);
+
+  // Requests an inclusion proof for the leaf denoted by |leaf_index| in
+  // a tree of size |tree_size|.
+  void FetchInclusionForEntry(const EntryToAudit& entry,
+                              uint64_t leaf_index,
+                              uint64_t tree_size);
+
+  // Issues an index fetching request or an inclusion proof request for
+  // the first entry pending in |pending_entries_|.
+  // NOTE: See the EntryAuditState documentation on the different states
+  // an entry can be at.
+  // TODO(eranm): Re-consider a proper state machine for this class once
+  // LogDnsClient reports throttling synchronously.
+  void ProcessPendingEntries();
+
+  // Identical to the public GetLogEntryInclusionStatus, except it
+  // operates on an |entry| rather than cert, SCT combination.
+  SCTInclusionStatus GetLogEntryInclusionStatus(const EntryToAudit& entry);
+
+  // LogDnsClient callbacks
+  void OnLeafIndexObtained(const EntryToAudit* entry,
+                           int net_error,
+                           uint64_t leaf_index);
+  void OnAuditProofObtained(const EntryToAudit* entry,
+                            uint64_t tree_size,
+                            int net_error,
+                            std::unique_ptr<net::ct::MerkleAuditProof> proof);
+
+  // 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.
+  EntriesMap 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'.
+  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);
 };