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..d771af8b7d9cf8bd573a1435f58ce7eb3a65fe83 100644
--- a/components/certificate_transparency/single_tree_tracker.h
+++ b/components/certificate_transparency/single_tree_tracker.h
@@ -6,26 +6,36 @@
 #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,
@@ -48,8 +58,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 +70,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 +108,61 @@ 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

[Ryan Sleevi, 2017/01/10 03:15:53]

grammar nit: missing a full-stop here.

// Less-than comparator that sorts EntryToAudits based on the SCT
// timestamp, with smaller (older) SCTs appearing less than larger (newer) SCTs.

[Eran Messeri, 2017/01/17 11:37:57]

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.
+  void ProcessPendingEntries();
+
+  // Identical to the public GetLogEntryInclusionStatus, except it
+  // operates on an |entry| rather than cert, SCT combination.

[Ryan Sleevi, 2017/01/10 03:15:53]

Grammatically, there's an article missing here (unclear if it's "a" or "the" or
requiring a reword)... "rather than the combination of cert and SCT" (for
example)

From a "read the header", it's ambiguous how this relates to
GetLogEntryInclusionStatus, because EntryToAudit is an opaque struct, so the
tuple-comparison is... well, it's not clear how "cert, SCT combination" matches
"EntryToAudit"

Perhaps just describe what this does?

(Note: If you're going to keep the reference to GetLogEntryInclusionStatus in
the comment, include the ()"

[Eran Messeri, 2017/01/17 11:37:57]

Done, PTAL - I've simply explained what it does and ended up referring to
GetLogEntryInclusionStatus().

+  SCTInclusionStatus GetAuditedEntryInclusionStatus(const EntryToAudit& entry);
+
+  // Invoked by the LogDnsClient once an audit proof request was completed.

[Ryan Sleevi, 2017/01/10 03:15:53]

This line describes how it is used, not what it does - and is thus superfluous.

[Eran Messeri, 2017/01/17 11:37:57]

Removed.

+  // Verifies the audit proof and updates the state of the entry accordingly:

[Ryan Sleevi, 2017/01/10 03:15:53]

the audit proof of what? ("of |entry|")

What is "the state of the 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 force this
//   entry to be re-checked.


(Is that correct?)

[Eran Messeri, 2017/01/17 11:37:57]

Replaced my text with yours.
It's mostly correct - if there was failure to obtain or validate an inclusion
proof then future calls to GetLogEntryInclusionStatus will indicate this entry
has not been observed (as we don't have a negative cache, only positive one).

+  // * 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.

[Ryan Sleevi, 2017/01/10 03:15:53]

// Clears entries to reduce memory overhead.

Explanation: What does "callback" mean here in this context? Are you using it a
verb or a noun? Is Clear passive or active voice?

[Eran Messeri, 2017/01/17 11:37:57]

Done.
Should have been more explicit here and indicated this is the callback function
provided to the MemoryPressureListener.

+  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, 2017/01/10 03:15:53]

"Map of" is redundant here

From a header documentation: |pending_entries_| also tracks in-progress entries,
right? Entries waiting to be checked or being checked?

[Eran Messeri, 2017/01/17 11:37:57]

Correct - all entries in this map are waiting to be checked for inclusion or
being checked for inclusion (there are in-progress DNS queries for getting the
inclusion proof).

I've changed the documentation accordingly.

+  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, 2017/01/10 03:15:53]

I'm not sure how to parse this comment.

Either
a) It does, and on failure, the EntryAuditResult struct is filled
b) It doesn't, in which case, the hash value wouldn't be found

[Eran Messeri, 2017/01/17 11:37:57]

I've clarified that currently the presence of an entry in |checked_entries_|
indicates successful inclusion check, and that in order to expand this field to
cache failures, the EntryAuditResult struct has to include a success indicator.

Is that better?

+  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);
 };