Add Certificate Transparency logs auditing

components/certificate_transparency/single_tree_tracker.h

 // Copyright 2016 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.
 
 #ifndef COMPONENTS_CERTIFICATE_TRANSPARENCY_SINGLE_TREE_TRACKER_H_
 #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/base/hash_value.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,
 // new SCTs are produced, and eventually, those SCTs are incorporated into the
 // log and a new STH is produced, with there being an inclusion proof between
 // the SCTs and the new STH, and a consistency proof between the old STH and the
 // new STH.
 // This class receives STHs provided by/observed by the embedder, with the
 // assumption that STHs have been checked for consistency already. As SCTs are
 // observed, their status is checked against the latest STH to ensure they were
 // properly logged. If an SCT is newer than the latest STH, then this class
 // verifies that when an STH is observed that should have incorporated those
 // SCTs, the SCTs (and their corresponding entries) are present in the log.
 //
 // To accomplish this, this class needs to be notified of when new SCTs are
 // observed (which it does by implementing net::CTVerifier::Observer) and when
 // new STHs are observed (which it does by implementing net::ct::STHObserver).
 // Once connected to sources providing that data, the status for a given SCT
 // can be queried by calling GetLogEntryInclusionCheck.
 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
     // to is verified (it was never observed via OnSCTVerified), nothing
     // is done with it.
     SCT_NOT_OBSERVED,
 
     // SCT was observed but the STH known to this class is not old
     // enough to check for inclusion, so a newer STH is needed first.
     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.
 
   // TODO(eranm): Extract CTVerifier::Observer to SCTObserver
   // Performs an inclusion check for the given certificate if the latest
   // STH known for this log is older than sct.timestamp + Maximum Merge Delay,
   // enqueues the SCT for future checking later on.
   // Should only be called with SCTs issued by the log this instance tracks.
   // TODO(eranm): Make sure not to perform any synchronous, blocking operation
   // here as this callback is invoked during certificate validation.
   void OnSCTVerified(net::X509Certificate* cert,
                      const net::ct::SignedCertificateTimestamp* sct) override;
 
   // net::ct::STHObserver implementation.
   // After verification of the signature over the |sth|, uses this
   // STH for future inclusion checks.
   // Must only be called for STHs issued by the log this instance tracks.
   void NewSTHObserved(const net::ct::SignedTreeHead& sth) override;
 
   // Returns the status of a given log entry that is assembled from
   // |cert| and |sct|. If |cert| and |sct| were not previously observed,
   // |sct| is not an SCT for |cert| or |sct| is not for this log,
   // SCT_NOT_OBSERVED will be returned.
   SCTInclusionStatus GetLogEntryInclusionStatus(
       net::X509Certificate* cert,
       const net::ct::SignedCertificateTimestamp* sct);
 
  private:
+  struct EntryToAudit;
+  struct EntryAuditState;
+  struct EntryAuditResult {};
+
+  // Less-than comparator that sorts EntryToAudits based on the SCT timestamp,
+  // with smaller (older) SCTs appearing less than larger (newer) SCTs.
+  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.
+  void ProcessPendingEntries();
+
+  // Returns the inclusion status of the given |entry|, similar to
+  // GetLogEntryInclusionStatus(). The |entry| is an internal representation of
+  // a certificate + SCT combination.
+  SCTInclusionStatus GetAuditedEntryInclusionStatus(const EntryToAudit& entry);
+
+  // Processes the result of obtaining an audit proof for |entry|.
+  // * If an audit proof was successfully obtained and validated,
+  //   updates |checked_entries_| so that future calls to
+  //   GetLogEntryInclusionStatus() will indicate the entry's
+  //   inclusion.
+  // * If there was a failure to obtain or validate an inclusion
+  //   proof, removes |entry| from the queue of entries to validate.
+  //   Future calls to GetLogEntryInclusionStatus() will indicate the entry
+  //   has not been observed.
+  void OnAuditProofObtained(const EntryToAudit& entry, int net_error);
+
+  // Clears entries to reduce memory overhead.
+  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_;
+  // Log entries waiting to be checked for inclusion, or being checked for
+  // inclusion, and 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, so the presence
+  // of an entry in |checked_entries_| indicates success.
+  // To extend support for caching failures, a success indicator should be
+  // added to the EntryAuditResult struct.
+  base::MRUCache<net::SHA256HashValue,
+                 EntryAuditResult,
+                 net::SHA256HashValueLessThan>
+      checked_entries_;
+
+  LogDnsClient* dns_client_;
+
+  std::unique_ptr<base::MemoryPressureListener> memory_pressure_listener_;
+
+  base::WeakPtrFactory<SingleTreeTracker> weak_factory_;
 
   DISALLOW_COPY_AND_ASSIGN(SingleTreeTracker);
 };
 
 }  // namespace certificate_transparency
 
 #endif  // COMPONENTS_CERTIFICATE_TRANSPARENCY_SINGLE_TREE_TRACKER_H_