Add Certificate Transparency logs auditing

components/certificate_transparency/single_tree_tracker.cc

Index: components/certificate_transparency/single_tree_tracker.cc
diff --git a/components/certificate_transparency/single_tree_tracker.cc b/components/certificate_transparency/single_tree_tracker.cc
index 7946208ca753303a7589260e7a60fd34a58bb5e0..868bc208a464f705363bca2c3d97180ca3d818df 100644
--- a/components/certificate_transparency/single_tree_tracker.cc
+++ b/components/certificate_transparency/single_tree_tracker.cc
@@ -4,15 +4,46 @@
 
 #include "components/certificate_transparency/single_tree_tracker.h"
 
+#include <algorithm>
+#include <iterator>
 #include <utility>
 
 #include "net/cert/ct_log_verifier.h"
 #include "net/cert/signed_certificate_timestamp.h"
 #include "net/cert/x509_certificate.h"
 
+using net::ct::LogEntry;
+using net::ct::MerkleTreeLeaf;
 using net::ct::SignedTreeHead;
 
 namespace certificate_transparency {
+bool OrderByTimestamp::operator()(const ObservedLeaf& lhs,

[Ryan Sleevi, 2016/06/30 22:48:19]

Should have had a line break after the namespace

[Eran Messeri, 2016/07/01 13:24:00]

Done.

+                                  const ObservedLeaf& rhs) {
+  const MerkleTreeLeaf& lhs_leaf = lhs.GetLeaf();
+  const MerkleTreeLeaf& rhs_leaf = rhs.GetLeaf();
+  // This comparator should only used for containers where leaves from
+  // different logs are not mixed.
+  DCHECK(lhs_leaf.log_id == rhs_leaf.log_id);

[Ryan Sleevi, 2016/06/30 22:48:19]

DCHECK_EQ

[Eran Messeri, 2016/07/01 13:24:00]

Done.

+
+  if (lhs_leaf.timestamp != rhs_leaf.timestamp)
+    return lhs_leaf.timestamp < rhs_leaf.timestamp;
+
+  // If the condition above is false, then |lhs| and |rhs| are either two
+  // leaves with the same timestamp or the same leaf. Compare the actual
+  // LogEntries to find out.

[Ryan Sleevi, 2016/06/30 22:48:18]

Grammatical comments about position tend to read weird. Be active

// |lhs| and |rhs| are either the same leaf, or they're two entries that
// share the same timestamp.


That said, it's unclear why this comment is even needed. A less-than comparator
has to assume that |lhs| and |rhs| are equal for some inputs, so it's not clear
why it needs stating.

You sort by timestamp. Then contents. Great.

From a design perspective, why isn't the less-than check for LogEntry's a factor
of the LogEntry? Why does it get moved here?

For that matter, why have the comparator here - rather than on the ObservedLeaf
itself?

This generally only needs the separate-comparator if we're ignoring parts of the
structure due to specific reasons.

[Eran Messeri, 2016/07/01 13:24:00]

Removed the comment, since, as you say, it was not adding much.

Since this now compares two MerkleTreeLeaf instances you could argue it should
live there. I don't mind moving it, wondering if we should wait to see if it's
useful for any other user of the MerkleTreeLeaf before moving.

+  const LogEntry& lhs_entry = lhs_leaf.log_entry;
+  const LogEntry& rhs_entry = rhs_leaf.log_entry;
+  if (lhs_entry.type != rhs_entry.type)
+    return lhs_entry.type < rhs_entry.type;
+
+  if (lhs_entry.type == LogEntry::LOG_ENTRY_TYPE_X509)
+    return lhs_entry.leaf_certificate < rhs_entry.leaf_certificate;
+
+  // lhs_entry.type == LOG_ENTRY_TYPE_PRECERT
+  return lhs_entry.tbs_certificate < rhs_entry.tbs_certificate &&
+         net::SHA256HashValueLessThan()(lhs_entry.issuer_key_hash,
+                                        rhs_entry.issuer_key_hash);
+}
 
 SingleTreeTracker::SingleTreeTracker(
     scoped_refptr<const net::CTLogVerifier> ct_log)
@@ -25,26 +56,31 @@ void SingleTreeTracker::OnSCTVerified(
     const net::ct::SignedCertificateTimestamp* sct) {
   DCHECK_EQ(ct_log_->key_id(), sct->log_id);
 
+  MerkleTreeLeaf leaf;
+  if (!GetMerkleTreeLeaf(cert, sct, &leaf))
+    return;
+
+  ObservedLeaf timestamped_leaf(std::move(leaf), base::Time::Now());
+
   // SCT was previously observed, so its status should not be changed.
-  if (entries_status_.find(sct->timestamp) != entries_status_.end())
+  if (EntryPendingNewSTH(timestamped_leaf) ||
+      EntryPendingInclusionProof(timestamped_leaf))
     return;
 
+  const base::TimeDelta kMaximumMergeDelay = base::TimeDelta::FromHours(24);
   // If there isn't a valid STH or the STH is not fresh enough to check
   // inclusion against, store the SCT for future checking and return.
   if (verified_sth_.timestamp.is_null() ||
-      (verified_sth_.timestamp <
-       (sct->timestamp + base::TimeDelta::FromHours(24)))) {
+      (verified_sth_.timestamp < (sct->timestamp + kMaximumMergeDelay))) {
     // TODO(eranm): UMA - how often SCTs have to wait for a newer STH for
     // inclusion check.
-    entries_status_.insert(
-        std::make_pair(sct->timestamp, SCT_PENDING_NEWER_STH));
+    pending_new_sth_.insert(std::move(timestamped_leaf));
     return;
   }
 
-  // TODO(eranm): Check inclusion here.
+  // TODO(eranm): Check inclusion here, see https://crbug.com/624894
   // TODO(eranm): UMA - how often inclusion can be checked immediately.
-  entries_status_.insert(
-      std::make_pair(sct->timestamp, SCT_PENDING_INCLUSION_CHECK));
+  pending_inclusion_check_.insert(std::move(timestamped_leaf));
 }
 
 void SingleTreeTracker::NewSTHObserved(const SignedTreeHead& sth) {
@@ -73,28 +109,54 @@ void SingleTreeTracker::NewSTHObserved(const SignedTreeHead& sth) {
     verified_sth_ = sth;
   }
 
+  if (pending_new_sth_.empty())
+    return;
   // Find out which SCTs can now be checked for inclusion.

[Ryan Sleevi, 2016/06/30 22:48:19]

Use vertical whitespace

[Eran Messeri, 2016/07/01 13:24:00]

Done.

-  // TODO(eranm): Keep two maps of MerkleTreeLeaf instances, one for leaves
-  // pending inclusion checks and one for leaves pending a new STH.
-  // The comparison function between MerkleTreeLeaf instances should use the
-  // timestamp to determine sorting order, so that bulk moving from one
-  // map to the other can happen.
-  auto entry = entries_status_.begin();
-  while (entry != entries_status_.end() &&
-         entry->first < verified_sth_.timestamp) {
-    entry->second = SCT_PENDING_INCLUSION_CHECK;
-    ++entry;
-    // TODO(eranm): Check inclusion here.
-  }
+  auto sth_timestamp_compare = [&sth](const ObservedLeaf& leaf) {
+    return leaf.GetLeaf().timestamp > sth.timestamp;
+  };

[Ryan Sleevi, 2016/06/30 22:48:18]

Don't create a temporary variable for this one call.

[Eran Messeri, 2016/07/01 13:24:00]

Done.

+  auto first_entry_not_included = std::find_if(
+      pending_new_sth_.begin(), pending_new_sth_.end(), sth_timestamp_compare);
+  // Move all entries up to the first entry not covered by this STH to
+  // the set of entries pending inclusion check.

[Ryan Sleevi, 2016/06/30 22:48:19]

Grammatically, this reads weird. "move all entries up to the first entry" can be
parsed as "[move all entries up to] the first entry" or "Begin inclusion checks
for all entries covered by this STH".

I'm suspecting you mean the latter.

[Eran Messeri, 2016/07/01 13:24:00]

Correct, but that piece of code is gone.

+  std::move(pending_new_sth_.begin(), first_entry_not_included,
+            std::inserter(pending_inclusion_check_,
+                          pending_inclusion_check_.begin()));
+  // Clear moved entries.

[Ryan Sleevi, 2016/06/30 22:48:19]

Doesn't add value with the above rewrite

[Eran Messeri, 2016/07/01 13:24:00]

Done.

+  pending_new_sth_.erase(pending_new_sth_.begin(), first_entry_not_included);
+
+  // TODO(eranm): Check inclusion here of entries that can now be checked.
+  // See https://crbug.com/624894
 }
 
 SingleTreeTracker::SCTInclusionStatus
 SingleTreeTracker::GetLogEntryInclusionStatus(
     net::X509Certificate* cert,
     const net::ct::SignedCertificateTimestamp* sct) {
-  auto it = entries_status_.find(sct->timestamp);
+  MerkleTreeLeaf leaf;
+  if (!GetMerkleTreeLeaf(cert, sct, &leaf))
+    return SCT_NOT_OBSERVED;
+
+  // The observation time for this leaf is not relevant as the comparison
+  // function does not take it into account.
+  ObservedLeaf observed_leaf(std::move(leaf), base::Time::UnixEpoch());
+  if (EntryPendingNewSTH(observed_leaf))
+    return SCT_PENDING_NEWER_STH;
+
+  if (EntryPendingInclusionProof(observed_leaf))
+    return SCT_PENDING_INCLUSION_CHECK;
+
+  // TODO(eranm): Look up the result of inclusion check for this leaf.
+
+  return SCT_NOT_OBSERVED;
+}
+
+bool SingleTreeTracker::EntryPendingNewSTH(const ObservedLeaf& leaf) {
+  return pending_new_sth_.find(leaf) != pending_new_sth_.end();
+}
 
-  return it == entries_status_.end() ? SCT_NOT_OBSERVED : it->second;
+bool SingleTreeTracker::EntryPendingInclusionProof(const ObservedLeaf& leaf) {
+  return pending_inclusion_check_.find(leaf) != pending_inclusion_check_.end();
 }
 
 }  // namespace certificate_transparency