Certificate Transparency: Start tracking logs' state

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
new file mode 100644
index 0000000000000000000000000000000000000000..f23e6e44f71dab0a4c2d1f4fa51dc72f00e7d67b
--- /dev/null
+++ b/components/certificate_transparency/single_tree_tracker.cc
@@ -0,0 +1,91 @@
+// 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.
+
+#include "components/certificate_transparency/single_tree_tracker.h"
+
+#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::SignedTreeHead;
+
+namespace certificate_transparency {
+
+SingleTreeTracker::SingleTreeTracker(
+    scoped_refptr<const net::CTLogVerifier> ct_log)
+    : ct_log_(ct_log) {}
+
+SingleTreeTracker::~SingleTreeTracker() {}
+
+void SingleTreeTracker::OnSCTVerified(
+    net::X509Certificate* cert,
+    const net::ct::SignedCertificateTimestamp* sct) {
+  CheckLogId(sct->log_id);
+
+  if (entries_status_.find(sct->timestamp) != entries_status_.end())

[Ryan Sleevi, 2016/05/09 17:03:49]

Document why the short-circuit

[Eran Messeri, 2016/05/10 20:01:10]

Done.

+    return;
+
+  if (verified_sth_.timestamp.is_null() ||

[Ryan Sleevi, 2016/05/09 17:03:48]

Document what this conditional is measuring

[Eran Messeri, 2016/05/10 20:01:10]

Done.

+      (verified_sth_.timestamp <
+       (sct->timestamp + base::TimeDelta::FromHours(24)))) {
+    // 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));
+    return;
+  }
+
+  // TODO(eranm): Check inclusion here.
+  // TODO(eranm): UMA - how often inclusion can be checked immediately.
+  entries_status_.insert(
+      std::make_pair(sct->timestamp, SCT_PENDING_INCLUSION_CHECK));
+}
+
+void SingleTreeTracker::NewSTHObserved(const SignedTreeHead& sth) {
+  CheckLogId(sth.log_id);
+
+  if (!ct_log_->VerifySignedTreeHead(sth)) {
+    // This may be caused due to an operational error - STHs supposed to be
+    // validated prior to being pushed via the component updater, so an
+    // invalid STH should never be observed by Chrome clients.

[Ryan Sleevi, 2016/05/09 17:03:48]

So why are we re-checking it here? Why shouldn't this be an implied API contract
enforced at the higher layer?

Why is silently failing on operation error desirable? What are the risks here of
not doing this?

I'm extremely uncomfortable with this because it means extra CPU load for
validating ECDSA signatures; yes, it's per STH, so we would think this would be
small (per component update cycle), but we should be trying to keep things nice
and small.

[Eran Messeri, 2016/05/10 20:01:09]

This is the first time we're verifying the STH on the client side. This could be
an implied API contract, for example by validating STHs in the STHDistributor
before sending them to the STHObservers.
The implication of silently failing on operation error is that all pending SCTs
will wait longer until they can be checked for inclusion. On the other hand, if
the STH received is corrupted somehow and we did not validate it, we might
falsely indicate that some SCTs could not be checked for inclusion (because the
leaf hash was also corrupted, for example).
we could avoid multiple checks of the same STH by checking signatures in the
STHDistributor; Do you prefer that? If so I'll move the code there (but prefer
to do so in a follow-up change as there will be some wiring changes).

+    return;
+  }
+
+  bool sths_for_same_tree = (verified_sth_.tree_size == sth.tree_size);
+  bool received_sth_is_for_larger_tree =
+      (verified_sth_.tree_size > sth.tree_size);
+  bool received_sth_is_newer = (sth.timestamp > verified_sth_.timestamp);

[Ryan Sleevi, 2016/05/09 17:03:49]

Documentation explaining why this matters (either at 56 or at 61; I think 56
might make more sense when coupled with the conditional of 62-65)

[Eran Messeri, 2016/05/10 20:01:10]

Done.

+
+  if (verified_sth_.timestamp.is_null() || received_sth_is_for_larger_tree ||
+      (sths_for_same_tree && received_sth_is_newer)) {
+    verified_sth_ = sth;
+  }
+
+  // Find out which SCTs can now be checked for inclusion.
+  for (auto& entry : entries_status_) {
+    if (entry.first < verified_sth_.timestamp) {
+      entry.second = SCT_PENDING_INCLUSION_CHECK;
+      // TODO(eranm): Check inclusion here.
+    }
+  }

[Ryan Sleevi, 2016/05/09 17:03:49]

These are sorted by timestamp, right? So once you reach a timestamp that is
greater,  you can stop iterating. Or am I missing something?

Doesn't this also mean you're updating entries that are already pending
repeatedly? Shouldn't you move them perhaps from one queue to another? In bulk,
to minimize operations?

[Eran Messeri, 2016/05/10 20:01:10]

Correct - I've changed the code to stop iterating when encountering a timestamp
that's greater than or equal to the STH timestamp.
Yes, I could - once Rob's changes to the MerkleTreeLeaf are in I will have two
maps, one for leaves pending inclusion check and one for tree leaves pending a
newer STH.
I've added a TODO to split this map into two once Rob's changes land. 

+}
+
+SingleTreeTracker::SCTInclusionStatus
+SingleTreeTracker::GetLogEntryInclusionStatus(
+    net::X509Certificate* cert,
+    const net::ct::SignedCertificateTimestamp* sct) {
+  auto it = entries_status_.find(sct->timestamp);
+  if (it == entries_status_.end())
+    return SCT_NOT_OBSERVED;
+
+  return it->second;
+}
+
+void SingleTreeTracker::CheckLogId(const std::string& log_id) {
+  DCHECK_EQ(ct_log_->key_id(), log_id) << "Got called for a different log.";

[Ryan Sleevi, 2016/05/09 17:03:49]

See previous remarks about folding this Check into the methods (e.g. not as a
member method)

It's not clear why this is a programming error / DCHECK worthy, since that
contract is not spelled out in the header at all.

[Eran Messeri, 2016/05/10 20:01:10]

Done.
Documented the contract.

+}
+
+}  // namespace certificate_transparency