Add Certificate Transparency logs auditing

components/certificate_transparency/single_tree_tracker_unittest.cc

 // 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 <string>
 #include <utility>
 
+#include "base/memory/ptr_util.h"
+#include "base/message_loop/message_loop.h"
+#include "base/run_loop.h"
 #include "base/strings/string_piece.h"
 #include "base/test/histogram_tester.h"
+#include "components/base32/base32.h"
+#include "components/certificate_transparency/log_dns_client.h"
+#include "components/certificate_transparency/mock_log_dns_traffic.h"
+#include "crypto/sha2.h"
+#include "net/base/network_change_notifier.h"
 #include "net/cert/ct_log_verifier.h"
 #include "net/cert/ct_serialization.h"
+#include "net/cert/merkle_tree_leaf.h"
 #include "net/cert/signed_certificate_timestamp.h"
 #include "net/cert/signed_tree_head.h"
 #include "net/cert/x509_certificate.h"
+#include "net/dns/dns_client.h"
+#include "net/log/net_log.h"
 #include "net/test/ct_test_util.h"
 #include "testing/gtest/include/gtest/gtest.h"
 
+using net::ct::SignedCertificateTimestamp;
+using net::ct::SignedTreeHead;
+
 namespace certificate_transparency {
 
 namespace {
 
 const char kCanCheckForInclusionHistogramName[] =
     "Net.CertificateTransparency.CanInclusionCheckSCT";
+const char kInclusionCheckResultHistogramName[] =
+    "Net.CertificateTransparency.InclusionCheckResult";
 
-bool GetOldSignedTreeHead(net::ct::SignedTreeHead* sth) {
-  sth->version = net::ct::SignedTreeHead::V1;
+base::TimeDelta kMoreThanMMD = base::TimeDelta::FromHours(25);
+
+bool GetOldSignedTreeHead(SignedTreeHead* sth) {
+  sth->version = SignedTreeHead::V1;
   sth->timestamp = base::Time::UnixEpoch() +
                    base::TimeDelta::FromMilliseconds(INT64_C(1348589665525));
   sth->tree_size = 12u;
 
   const uint8_t kOldSTHRootHash[] = {
       0x18, 0x04, 0x1b, 0xd4, 0x66, 0x50, 0x83, 0x00, 0x1f, 0xba, 0x8c,
       0x54, 0x11, 0xd2, 0xd7, 0x48, 0xe8, 0xab, 0xbf, 0xdc, 0xdf, 0xd9,
       0x21, 0x8c, 0xb0, 0x2b, 0x68, 0xa7, 0x8e, 0x7d, 0x4c, 0x23};
   memcpy(sth->sha256_root_hash, kOldSTHRootHash, net::ct::kSthRootHashLength);
 
   sth->log_id = net::ct::GetTestPublicKeyId();
 
   const uint8_t kOldSTHSignatureData[] = {
       0x04, 0x03, 0x00, 0x47, 0x30, 0x45, 0x02, 0x20, 0x15, 0x7b, 0x23,
       0x42, 0xa2, 0x5f, 0x88, 0xc9, 0x0b, 0x30, 0xa6, 0xb4, 0x49, 0x50,
       0xb3, 0xab, 0xf5, 0x25, 0xfe, 0x27, 0xf0, 0x3f, 0x9a, 0xbf, 0xc1,
       0x16, 0x5a, 0x7a, 0xc0, 0x62, 0x2b, 0xbb, 0x02, 0x21, 0x00, 0xe6,
       0x57, 0xa3, 0xfe, 0xfc, 0x5a, 0x82, 0x9b, 0x29, 0x46, 0x15, 0x1d,
       0xbc, 0xfd, 0x9e, 0x87, 0x7f, 0xd0, 0x00, 0x5d, 0x62, 0x4f, 0x9a,
       0x1a, 0x9f, 0x20, 0x79, 0xd0, 0xc1, 0x34, 0x2e, 0x08};
   base::StringPiece sp(reinterpret_cast<const char*>(kOldSTHSignatureData),
                        sizeof(kOldSTHSignatureData));
   return DecodeDigitallySigned(&sp, &(sth->signature)) && sp.empty();
 }
 
+scoped_refptr<SignedCertificateTimestamp> GetSCT() {
+  scoped_refptr<SignedCertificateTimestamp> sct;
+
+  // TODO(eranm): Move setting of the origin field to ct_test_util.cc
+  net::ct::GetX509CertSCT(&sct);
+  sct->origin = SignedCertificateTimestamp::SCT_FROM_OCSP_RESPONSE;
+  return sct;
+}
+
+std::string Base32LeafHash(const net::X509Certificate* cert,
+                           const SignedCertificateTimestamp* sct) {
+  net::ct::MerkleTreeLeaf leaf;
+  if (!GetMerkleTreeLeaf(cert, sct, &leaf))
+    return std::string();
+
+  std::string leaf_hash;
+  if (!HashMerkleTreeLeaf(leaf, &leaf_hash))
+    return std::string();
+
+  return base32::Base32Encode(leaf_hash,
+                              base32::Base32EncodePolicy::OMIT_PADDING);
+}
+
+template <typename... T>
+void AssertSCTsMatchingState(SingleTreeTracker* tree_tracker,
+                             net::X509Certificate* chain,
+                             SingleTreeTracker::SCTInclusionStatus status,
+                             T... scts) {

[Ryan Sleevi, 2016/12/14 01:34:15]

This seems like a lot of... undesirable template overhead. What's legal isn't
always what's desirable - from codegen or readability.

I'm trying to parse what this function does (could have used more documentation)
and how it's called (the use of var-args == super subtle about number and
ordering of params)

[Eran Messeri, 2016/12/22 16:12:11]

Added documentation.

I've created this function because I've noticed I repeatedly make assertions
about the state of a group of SCTs in the SingleTreeTracker .

I use a parameter pack because the group is not held in another container - I
could make this function take a list/vector of SCTs and create it each time I
call the funciton, if that's preferable?

+  const int sct_list_size = sizeof...(scts);
+  SignedCertificateTimestamp* sct_list[sct_list_size] = {scts...};
+  for (const auto& sct : sct_list) {
+    EXPECT_EQ(status, tree_tracker->GetLogEntryInclusionStatus(chain, sct))
+        << "SCT age: " << sct->timestamp;
+  }
+};
+
+bool GetSignedTreeHeadForTreeOfSize2(SignedTreeHead* sth) {
+  sth->version = SignedTreeHead::V1;
+  sth->timestamp = base::Time::UnixEpoch() +
+                   base::TimeDelta::FromMilliseconds(INT64_C(1365354256089));

[Ryan Sleevi, 2016/12/14 01:34:16]

Document.

[Eran Messeri, 2016/12/22 16:12:11]

Done.

+  sth->tree_size = 2;
+  const uint8_t kRootHash[] = {0x16, 0x80, 0xbd, 0x5a, 0x1b, 0xc1, 0xb6, 0xcf,
+                               0x1b, 0x7e, 0x77, 0x41, 0xeb, 0xed, 0x86, 0x8b,
+                               0x73, 0x81, 0x87, 0xf5, 0xab, 0x93, 0x6d, 0xb2,
+                               0x0a, 0x79, 0x0d, 0x9e, 0x40, 0x55, 0xc3, 0xe6};

[Ryan Sleevi, 2016/12/14 01:34:16]

Document.

[Eran Messeri, 2016/12/22 16:12:11]

Done.

+  std::string decoded_root_hash(reinterpret_cast<const char*>(kRootHash),
+                                net::ct::kSthRootHashLength);
+
+  memcpy(sth->sha256_root_hash, decoded_root_hash.data(),
+         decoded_root_hash.size());

[Ryan Sleevi, 2016/12/14 01:34:15]

Why is 117-121 necessary? Can't you just copy in directly to the sth?

[Eran Messeri, 2016/12/22 16:12:11]

Not necessary, removed.

+  sth->log_id = net::ct::GetTestPublicKeyId();
+
+  const uint8_t kTreeHeadSignatureData[] = {
+      0x04, 0x03, 0x00, 0x46, 0x30, 0x44, 0x02, 0x20, 0x25, 0xa1, 0x9d,
+      0x7b, 0xf6, 0xe6, 0xfc, 0x47, 0xa7, 0x2d, 0xef, 0x6b, 0xf4, 0x84,
+      0x71, 0xb7, 0x7b, 0x7e, 0xd4, 0x4c, 0x7a, 0x5c, 0x4f, 0x9a, 0xb7,
+      0x04, 0x71, 0x6e, 0xd0, 0xa8, 0x0f, 0x53, 0x02, 0x20, 0x27, 0xe5,
+      0xed, 0x7d, 0xc3, 0x5d, 0x4c, 0xf0, 0x67, 0x35, 0x5d, 0x8a, 0x10,
+      0xae, 0x25, 0x87, 0x1a, 0xef, 0xea, 0xd2, 0xf7, 0xe3, 0x73, 0x2f,
+      0x07, 0xb3, 0x4b, 0xea, 0x5b, 0xdd, 0x81, 0x2d};

[Ryan Sleevi, 2016/12/14 01:34:16]

Document.

[Eran Messeri, 2016/12/22 16:12:12]

Done.

+
+  base::StringPiece sp(reinterpret_cast<const char*>(kTreeHeadSignatureData),
+                       sizeof(kTreeHeadSignatureData));
+  return DecodeDigitallySigned(&sp, &sth->signature);
+}
+
+void FillVectorWithValidAuditProofForTreeOfSize2(
+    std::vector<std::string>* out_proof) {
+  std::string node(crypto::kSHA256Length, '\0');
+  for (size_t i = 0; i < crypto::kSHA256Length; ++i) {
+    node[i] = static_cast<char>(0x0a);
+  }
+  out_proof->push_back(node);
+}
+
 }  // namespace
 
 class SingleTreeTrackerTest : public ::testing::Test {
   void SetUp() override {
     log_ =
         net::CTLogVerifier::Create(net::ct::GetTestPublicKey(), "testlog",
                                    "https://ct.example.com", "dns.example.com");
 
     ASSERT_TRUE(log_);
     ASSERT_EQ(log_->key_id(), net::ct::GetTestPublicKeyId());
 
-    tree_tracker_.reset(new SingleTreeTracker(log_));
     const std::string der_test_cert(net::ct::GetDerEncodedX509Cert());
     chain_ = net::X509Certificate::CreateFromBytes(der_test_cert.data(),
                                                    der_test_cert.length());
     ASSERT_TRUE(chain_.get());
     net::ct::GetX509CertSCT(&cert_sct_);
+    cert_sct_->origin = SignedCertificateTimestamp::SCT_FROM_OCSP_RESPONSE;
+
+    ClearDnsConfig();

[Ryan Sleevi, 2016/12/14 01:34:16]

Why is this necessary? Why can't it just be handled by the ctor (see below)

[Eran Messeri, 2016/12/22 16:12:11]

If I understand correctly, the question is why isn't there a member of type
net::NetworkChangeNotifier that's initialized with
net::NetworkChangeNotifier::CreateMock ? Or do you suggest there'd still be a
member of type std::unique_ptr<net::NetworkChangeNotifier> but it gets
initialized in the c'tor?

[Ryan Sleevi, 2016/12/22 21:33:20]

The latter - initialize the pointer in the ctor, as it doesn't seem to have any
dependencies here re: SetUp and, as a subroutine, doesn't trigger any error
handling anyways.

+    // Default to throttling requests as it means observed log entries will
+    // be frozen in a pending state, simplifying testing of the
+    // SingleTreeTracker.
+    ASSERT_TRUE(ExpectLeafHashRequestAndThrottle(chain_, cert_sct_));
+    CreateTreeTracker();
   }
 
  protected:
+  void ClearDnsConfig() {
+    // Must clear the global one first.
+    net_change_notifier_.reset();
+    net_change_notifier_.reset(net::NetworkChangeNotifier::CreateMock());

[Ryan Sleevi, 2016/12/14 01:34:15]

Every test creates a new instance, so the first .reset() is unnecessary. If the
dtor for net_change_notifier_ doesn't cleanup global state, that sounds like a
bug?

[Eran Messeri, 2016/12/22 16:12:11]

It's true that every test creates a new instance. But in some test cases a
different instance is created (with different DNS expectations), so the previous
one has to be cleared first.
My understanding is that when:
net_change_notifier_.reset(net::NetworkChangeNotifier::CreateMock());
is called, first CreateMock is called to create a new object to pass into the
reset() method, which will delete the old instance and set the new instance
created by CreateMock.

However there's a check in the NetworkChangeNotifier that fails when a new
NetworkChangeNotifier is created when a global one is already set:
https://cs.chromium.org/chromium/src/net/base/network_change_notifier.cc?dr=C...

Which is why I have to reset the previous instance - so the global one gets
nullified, only then a new NetworkChangeNotifier can be created.

I've added comment to that effect.

+
+    mock_dns_.reset(new MockLogDnsTraffic);
+    mock_dns_->InitializeDnsConfig();

[Ryan Sleevi, 2016/12/14 01:34:16]

Do these need to be unique? Can they just be members?

[Eran Messeri, 2016/12/22 16:12:12]

Not sure about the question: Are you suggesting it can be a member of type
MockLogDnsTraffic ?
If so, I'd need a way to either clear the currently-set expectations (to re-use
the member object with some expectations already set) or create an instance
local to the test method (more boilerplate code in each test method).

[Ryan Sleevi, 2016/12/22 21:33:20]

Yes.
I'm not sure I fully understand this comment. I tried re-reading through
mock_log_dns_traffic again, and even after letting it sit for a few hours, I'm
still a bit confused. Mostly, I think MockLogDnsTraffic may be doing too much at
once, which is what creates come of the trouble here, but that's very much a
'hot take'. And while I've got some suggestions on how to perhaps make that code
easier (I think decoupling the 'produce simulated socket events' from 'manage
the DNS config' are probably better things to do here), I more want to make sure
I understand your concern here.

+  }
+
+  void CreateTreeTracker() {

[Ryan Sleevi, 2016/12/14 01:34:16]

Doesn't seem necessary to have this helper function - but am I misreading?

[Eran Messeri, 2016/12/22 16:12:11]

Do you mean it seems like this function is not called? It's used in
TestEntryNotPendingAfterLeafIndexFetchFailure, for example.

More broadly the problem with this test class is that for some tests a simple
configuration of DNS expectation is enough (lines 166-169), but in other tests
another set of DNS expectations is needed.

When a custom set of DNS expectations (and replies) is needed, then they have to
be set on mock_dns_ (of type MockLogDnsTraffic), which *then* is used to create
a DnsClient which will have these expectations/return the specified replies (and
as you can see in CreateTreeTracker a log_dns_client_ is created from the
mock_dns_ instance and a SingleTreeTracker created with it).

That's why it has to manually be reset every time (the other option being to
specify the expected DNS requests / responses in every test case).

[Ryan Sleevi, 2016/12/22 21:33:20]

No. I meant more specifically: It does not seem necessary to uplift this to a
dedicated function, versus putting it in the specific test itself. It seems to
obscure the code under test, rather than help readability - but that's more of a
$.02
I feel that's more desirable, on the basis of the above link, because that's
literally part of your test :)

+    log_dns_client_ = base::MakeUnique<LogDnsClient>(
+        mock_dns_->CreateDnsClient(), net_log_, 1);
+
+    tree_tracker_.reset(new SingleTreeTracker(log_, log_dns_client_.get()));
+  }
+
+  bool ExpectLeafHashRequestAndThrottle(

[Ryan Sleevi, 2016/12/14 01:34:16]

Document

[Eran Messeri, 2016/12/22 16:12:12]

Done, also renamed to ExpectLeafIndexRequestAndThrottle.

+      scoped_refptr<net::X509Certificate> chain,
+      scoped_refptr<SignedCertificateTimestamp> sct) {

[Ryan Sleevi, 2016/12/14 01:34:16]

Doesn't seem like you need to be passing these byval - you're not taking
ownership of them. Pass either by naked pointers or const-ref?

[Eran Messeri, 2016/12/22 16:12:12]

Done (const-ref rather than naked pointers because then I'd have to call .get()
everywhere this method is invoked.).

+    return mock_dns_->ExpectRequestAndSocketError(
+        Base32LeafHash(chain.get(), sct.get()) +
+            ".hash.dns.example."

[Ryan Sleevi, 2016/12/14 01:34:16]

Mostly since you're adding it in this test, I think it's non-obvious the
relationship between all of these "hash.dns.example.com" (with their weird line
breaking - is this cl formatt'd?) and line 153 (which actually sets it up). This
seems like the sort of thing you'd express via two constants.

[Eran Messeri, 2016/12/22 16:12:11]

Fixed throughout by adding a constant for the prefix (kDNSRequestSuffix)
Do you think a constant for the ".hash." portion is also necessary?

[Ryan Sleevi, 2016/12/22 21:33:20]

No, I think you're fine.

+            "com",
+        net::Error::ERR_TEMPORARILY_THROTTLED);
+  }
+
+  base::MessageLoopForIO message_loop_;
+  std::unique_ptr<MockLogDnsTraffic> mock_dns_;
   scoped_refptr<const net::CTLogVerifier> log_;
+  std::unique_ptr<net::NetworkChangeNotifier> net_change_notifier_;
+  std::unique_ptr<LogDnsClient> log_dns_client_;
   std::unique_ptr<SingleTreeTracker> tree_tracker_;
   scoped_refptr<net::X509Certificate> chain_;
-  scoped_refptr<net::ct::SignedCertificateTimestamp> cert_sct_;
+  scoped_refptr<SignedCertificateTimestamp> cert_sct_;
+  net::NetLogWithSource net_log_;
 };
 
 // Test that an SCT is classified as pending for a newer STH if the
 // SingleTreeTracker has not seen any STHs so far.
 TEST_F(SingleTreeTrackerTest, CorrectlyClassifiesUnobservedSCTNoSTH) {
   base::HistogramTester histograms;
   // First make sure the SCT has not been observed at all.
   EXPECT_EQ(
       SingleTreeTracker::SCT_NOT_OBSERVED,
       tree_tracker_->GetLogEntryInclusionStatus(chain_.get(), cert_sct_.get()));
 
   tree_tracker_->OnSCTVerified(chain_.get(), cert_sct_.get());
 
   // Since no STH was provided to the tree_tracker_ the status should be that
   // the SCT is pending a newer STH.
   EXPECT_EQ(
       SingleTreeTracker::SCT_PENDING_NEWER_STH,
       tree_tracker_->GetLogEntryInclusionStatus(chain_.get(), cert_sct_.get()));
 
   // Expect logging of a value indicating a valid STH is required.
   histograms.ExpectTotalCount(kCanCheckForInclusionHistogramName, 1);
   histograms.ExpectBucketCount(kCanCheckForInclusionHistogramName, 0, 1);
 }
 
 // Test that an SCT is classified as pending an inclusion check if the
 // SingleTreeTracker has a fresh-enough STH to check inclusion against.
 TEST_F(SingleTreeTrackerTest, CorrectlyClassifiesUnobservedSCTWithRecentSTH) {
   base::HistogramTester histograms;
   // Provide an STH to the tree_tracker_.
-  net::ct::SignedTreeHead sth;
+  SignedTreeHead sth;
   net::ct::GetSampleSignedTreeHead(&sth);
   tree_tracker_->NewSTHObserved(sth);
 
   // Make sure the SCT status is the same as if there's no STH for
   // this log.
   EXPECT_EQ(
       SingleTreeTracker::SCT_NOT_OBSERVED,
       tree_tracker_->GetLogEntryInclusionStatus(chain_.get(), cert_sct_.get()));
 
   tree_tracker_->OnSCTVerified(chain_.get(), cert_sct_.get());
 
   // The status for this SCT should be 'pending inclusion check' since the STH
   // provided at the beginning of the test is newer than the SCT.
   EXPECT_EQ(
       SingleTreeTracker::SCT_PENDING_INCLUSION_CHECK,
       tree_tracker_->GetLogEntryInclusionStatus(chain_.get(), cert_sct_.get()));
 
   // Exactly one value should be logged, indicating the SCT can be checked for
   // inclusion, as |tree_tracker_| did have a valid STH when it was notified
   // of a new SCT.
   histograms.ExpectTotalCount(kCanCheckForInclusionHistogramName, 1);
   histograms.ExpectBucketCount(kCanCheckForInclusionHistogramName, 2, 1);
+  // Nothing should be logged in the result histogram since inclusion check
+  // didn't finish.
+  histograms.ExpectTotalCount(kInclusionCheckResultHistogramName, 0);
 }
 
 // Test that the SingleTreeTracker correctly queues verified SCTs for inclusion
 // checking such that, upon receiving a fresh STH, it changes the SCT's status
 // from pending newer STH to pending inclusion check.
 TEST_F(SingleTreeTrackerTest, CorrectlyUpdatesSCTStatusOnNewSTH) {
   base::HistogramTester histograms;
   // Report an observed SCT and make sure it's in the pending newer STH
   // state.
   tree_tracker_->OnSCTVerified(chain_.get(), cert_sct_.get());
   EXPECT_EQ(
       SingleTreeTracker::SCT_PENDING_NEWER_STH,
       tree_tracker_->GetLogEntryInclusionStatus(chain_.get(), cert_sct_.get()));
   histograms.ExpectTotalCount(kCanCheckForInclusionHistogramName, 1);
 
   // Provide with a fresh STH
-  net::ct::SignedTreeHead sth;
+  SignedTreeHead sth;
   net::ct::GetSampleSignedTreeHead(&sth);
   tree_tracker_->NewSTHObserved(sth);
 
   // Test that its status has changed.
   EXPECT_EQ(
       SingleTreeTracker::SCT_PENDING_INCLUSION_CHECK,
       tree_tracker_->GetLogEntryInclusionStatus(chain_.get(), cert_sct_.get()));
   // Check that no additional UMA was logged for this case as the histogram is
   // only supposed to measure the state of newly-observed SCTs, not pending
   // ones.
   histograms.ExpectTotalCount(kCanCheckForInclusionHistogramName, 1);
 }
 
 // Test that the SingleTreeTracker does not change an SCT's status if an STH
 // from the log it was issued by is observed, but that STH is too old to check
 // inclusion against.
 TEST_F(SingleTreeTrackerTest, DoesNotUpdatesSCTStatusOnOldSTH) {
   // Notify of an SCT and make sure it's in the 'pending newer STH' state.
   tree_tracker_->OnSCTVerified(chain_.get(), cert_sct_.get());
   EXPECT_EQ(
       SingleTreeTracker::SCT_PENDING_NEWER_STH,
       tree_tracker_->GetLogEntryInclusionStatus(chain_.get(), cert_sct_.get()));
 
   // Provide an old STH for the same log.
-  net::ct::SignedTreeHead sth;
+  SignedTreeHead sth;
   GetOldSignedTreeHead(&sth);
   tree_tracker_->NewSTHObserved(sth);
 
   // Make sure the SCT's state hasn't changed.
   EXPECT_EQ(
       SingleTreeTracker::SCT_PENDING_NEWER_STH,
       tree_tracker_->GetLogEntryInclusionStatus(chain_.get(), cert_sct_.get()));
 }
 
 // Test that the SingleTreeTracker correctly logs that an SCT is pending a new
 // STH, when it has a valid STH,  but the observed SCT is not covered by the
 // STH.
 TEST_F(SingleTreeTrackerTest, LogsUMAForNewSCTAndOldSTH) {
   base::HistogramTester histograms;
   // Provide an old STH for the same log.
-  net::ct::SignedTreeHead sth;
+  SignedTreeHead sth;
   GetOldSignedTreeHead(&sth);
   tree_tracker_->NewSTHObserved(sth);
 
   histograms.ExpectTotalCount(kCanCheckForInclusionHistogramName, 0);
 
   // Notify of an SCT and make sure it's in the 'pending newer STH' state.
   tree_tracker_->OnSCTVerified(chain_.get(), cert_sct_.get());
 
   // Exactly one value should be logged, indicating the SCT cannot be checked
   // for inclusion as the STH is too old.
   histograms.ExpectTotalCount(kCanCheckForInclusionHistogramName, 1);
   histograms.ExpectBucketCount(kCanCheckForInclusionHistogramName, 1, 1);
 }
 
+// Test that an entry transitions to the "not found" state if the LogDnsClient
+// fails to get a leaf index.
+TEST_F(SingleTreeTrackerTest, TestEntryNotPendingAfterLeafIndexFetchFailure) {
+  ClearDnsConfig();

[Ryan Sleevi, 2016/12/14 01:34:16]

Unnecessary?

[Eran Messeri, 2016/12/22 16:12:11]

Done.

+  ASSERT_TRUE(mock_dns_->ExpectRequestAndSocketError(
+      Base32LeafHash(chain_.get(), cert_sct_.get()) + ".hash.dns.example."
+                                                      "com",
+      net::Error::ERR_FAILED));
+
+  CreateTreeTracker();
+
+  tree_tracker_->OnSCTVerified(chain_.get(), cert_sct_.get());
+  EXPECT_EQ(
+      SingleTreeTracker::SCT_PENDING_NEWER_STH,
+      tree_tracker_->GetLogEntryInclusionStatus(chain_.get(), cert_sct_.get()));
+
+  // Provide with a fresh STH
+  SignedTreeHead sth;
+  net::ct::GetSampleSignedTreeHead(&sth);
+  tree_tracker_->NewSTHObserved(sth);
+  base::RunLoop().RunUntilIdle();
+
+  EXPECT_EQ(
+      SingleTreeTracker::SCT_NOT_OBSERVED,
+      tree_tracker_->GetLogEntryInclusionStatus(chain_.get(), cert_sct_.get()));
+}
+
+// Test that an entry transitions to the "not found" state if the LogDnsClient
+// succeeds to get a leaf index but fails to get an inclusion proof.
+TEST_F(SingleTreeTrackerTest, TestEntryNotPendingAfterInclusionCheckFailure) {
+  ClearDnsConfig();

[Ryan Sleevi, 2016/12/14 01:34:16]

Unnecessary?

[Eran Messeri, 2016/12/22 16:12:11]

Acknowledged, see explanation below why we need to call ClearDnsConfig in every
test case where different DNS expectations have to be set.

+  ASSERT_TRUE(mock_dns_->ExpectLeafIndexRequestAndResponse(
+      Base32LeafHash(chain_.get(), cert_sct_.get()) + ".hash.dns.example."
+                                                      "com",
+      12));
+  ASSERT_TRUE(mock_dns_->ExpectRequestAndSocketError(
+      "0.12.21.tree.dns.example.com", net::Error::ERR_FAILED));

[Ryan Sleevi, 2016/12/14 01:34:16]

Document why 0.12.21 is meaningful here.

[Eran Messeri, 2016/12/22 16:12:12]

Done.

+
+  CreateTreeTracker();
+
+  tree_tracker_->OnSCTVerified(chain_.get(), cert_sct_.get());
+  EXPECT_EQ(
+      SingleTreeTracker::SCT_PENDING_NEWER_STH,
+      tree_tracker_->GetLogEntryInclusionStatus(chain_.get(), cert_sct_.get()));
+
+  // Provide with a fresh STH
+  SignedTreeHead sth;
+  net::ct::GetSampleSignedTreeHead(&sth);
+  tree_tracker_->NewSTHObserved(sth);
+  base::RunLoop().RunUntilIdle();
+
+  EXPECT_EQ(
+      SingleTreeTracker::SCT_NOT_OBSERVED,
+      tree_tracker_->GetLogEntryInclusionStatus(chain_.get(), cert_sct_.get()));
+}
+
+// Test that an entry transitions to the "included" state if the LogDnsClient
+// succeeds to get a leaf index and an inclusion proof.
+TEST_F(SingleTreeTrackerTest, TestEntryIncludedAfterInclusionCheckSuccess) {
+  std::vector<std::string> audit_proof;
+  FillVectorWithValidAuditProofForTreeOfSize2(&audit_proof);
+
+  ClearDnsConfig();

[Ryan Sleevi, 2016/12/14 01:34:16]

Unnecessary?

[Eran Messeri, 2016/12/22 16:12:12]

Acknowledged, see explanation below.

+  ASSERT_TRUE(mock_dns_->ExpectLeafIndexRequestAndResponse(
+      Base32LeafHash(chain_.get(), cert_sct_.get()) + ".hash.dns.example."
+                                                      "com",
+      0));
+  ASSERT_TRUE(mock_dns_->ExpectAuditProofRequestAndResponse(
+      "0.0.2.tree.dns.example.com", audit_proof.begin(),

[Ryan Sleevi, 2016/12/14 01:34:16]

Document why 0.0.2 is meaningful here

[Eran Messeri, 2016/12/22 16:12:11]

Done.

+      audit_proof.begin() + 1));
+
+  CreateTreeTracker();
+
+  tree_tracker_->OnSCTVerified(chain_.get(), cert_sct_.get());
+  EXPECT_EQ(
+      SingleTreeTracker::SCT_PENDING_NEWER_STH,
+      tree_tracker_->GetLogEntryInclusionStatus(chain_.get(), cert_sct_.get()));
+
+  // Provide with a fresh STH
+  SignedTreeHead sth;
+  ASSERT_TRUE(GetSignedTreeHeadForTreeOfSize2(&sth));
+  ASSERT_TRUE(log_->VerifySignedTreeHead(sth));
+
+  tree_tracker_->NewSTHObserved(sth);
+  base::RunLoop().RunUntilIdle();
+
+  EXPECT_EQ(
+      SingleTreeTracker::SCT_INCLUDED_IN_LOG,
+      tree_tracker_->GetLogEntryInclusionStatus(chain_.get(), cert_sct_.get()));
+}
+
+// Test that pending entries transition states correctly according to the
+// STHs provided:
+// * Start without an STH.
+// * Add a collection of entries with mixed timestamps (i.e. SCTs not added
+// in the order of their timestamps).

[Ryan Sleevi, 2016/12/14 01:34:16]

Follow markdown style indents
* Add a ...
  in the order of their timestamps.

[Eran Messeri, 2016/12/22 16:12:11]

Done.

+// * Provide an STH that covers some of the entries, test these are audited.
+// * Provide another STH that covers more of the entries, test that the entries
+// already audited are not audited again and that those that need to be
+// audited are audited, while those that are not covered by that STH are
+// not audited.

[Ryan Sleevi, 2016/12/14 01:34:15]

Is it wholly necessary to test this, as large as you've done? It doesn't seem
like it's testing the interface contract, or at best, that it's testing multiple
aspects of the interface contract. That seems to make it much more complex to
read, parse, and understand - and I'm curious if you can simplify this.

[Eran Messeri, 2016/12/22 16:12:12]

I acknowledge this is a large and complex test. And there are other tests that
test particular aspects of the interface contract.
However, because of the use of a data structure with custom/complex comparator
in the code-under-test, I didn't feel comfortable not having that test.
Ultimately the goal of tests is to provide confidence in the correctness of the
code-under-test, and I wouldn't have enough confidence in that code unless I
exercised it in that particular way.

+TEST_F(SingleTreeTrackerTest, TestMultipleEntriesTransitionStateCorrectly) {
+  SignedTreeHead old_sth;
+  GetOldSignedTreeHead(&old_sth);
+
+  SignedTreeHead new_sth;
+  net::ct::GetSampleSignedTreeHead(&new_sth);

[Ryan Sleevi, 2016/12/14 01:34:15]

You removed other net::ct:: qualifications, but added it here (e.g. see line
187)

[Eran Messeri, 2016/12/22 16:12:12]

Done.

+
+  base::TimeDelta kLessThanMMD = base::TimeDelta::FromHours(23);
+
+  // Assert the gap between the two timestamps is big enough so that
+  // all assumptions below on which SCT can be audited with the
+  // new STH are true.
+  ASSERT_LT(old_sth.timestamp + (kMoreThanMMD * 2), new_sth.timestamp);
+
+  // Oldest SCT - auditable by the old and new STHs.
+  scoped_refptr<SignedCertificateTimestamp> oldest_sct(GetSCT());
+  oldest_sct->timestamp = old_sth.timestamp - kMoreThanMMD;
+
+  // SCT that's older than the old STH's timestamp but by less than the MMD,
+  // so not auditable by old STH.
+  scoped_refptr<SignedCertificateTimestamp> not_auditable_by_old_sth_sct(
+      GetSCT());
+  not_auditable_by_old_sth_sct->timestamp = old_sth.timestamp - kLessThanMMD;
+
+  // SCT that's newer than the old STH's timestamp so is only auditable by
+  // the new STH.
+  scoped_refptr<SignedCertificateTimestamp> newer_than_old_sth_sct(GetSCT());
+  newer_than_old_sth_sct->timestamp = old_sth.timestamp + kLessThanMMD;
+
+  // SCT that's older than the new STH's timestamp but by less than the MMD,
+  // so isn't auditable by the new STH.
+  scoped_refptr<SignedCertificateTimestamp> not_auditable_by_new_sth_sct(
+      GetSCT());
+  not_auditable_by_new_sth_sct->timestamp = new_sth.timestamp - kLessThanMMD;
+
+  // SCT that's newer than the new STH's timestamp so isn't auditable by the
+  // the new STH.
+  scoped_refptr<SignedCertificateTimestamp> newer_than_new_sth_sct(GetSCT());
+  newer_than_new_sth_sct->timestamp = new_sth.timestamp + kLessThanMMD;
+
+  // Set up DNS expectations based on inclusion proof request order.
+  ClearDnsConfig();

[Ryan Sleevi, 2016/12/14 01:34:15]

This is the only one that seems 'necessary' (e.g. it happens elsewhere), but it
could entirely be an incorrect read based on the surrounding code (which looks
like, on quick visual scan, only to be setting up temporary variables)

[Eran Messeri, 2016/12/22 16:12:11]

Trying to clarify the relationship between the mock_dns_,  net_change_notifier_,
log_dns_client and tree_tracker_:

tree_tracker_ takes a LogDnsClient in the c'tor (does not take ownership),
which, for tests, has to be configured with expected requests and replies.
The MockLogDnsTraffic creates such a LogDnsClient, after the expectations have
been set on the MockLogDnsTraffic instance. That instance is not (currently)
re-usable. A new one has to be created to clear existing expectations.

InitializeDnsConfig has to be called to configure the "global" dns configuration
and prevent it from actually sending DNS queries.
Since InitializeDnsConfig calls DnsChangeNotifier::SetInitialDnsConfig, which
asserts no config previously existed, then the NetworkChangeNotifier has to also
be reset and a new one (which did not have any dns config previously) created.

That's why every time unique DNS expectations are needed in a test method we
have to clear the DNS config.

+  ASSERT_TRUE(ExpectLeafHashRequestAndThrottle(chain_, oldest_sct));
+  ASSERT_TRUE(
+      ExpectLeafHashRequestAndThrottle(chain_, not_auditable_by_old_sth_sct));
+  ASSERT_TRUE(ExpectLeafHashRequestAndThrottle(chain_, newer_than_old_sth_sct));
+  CreateTreeTracker();
+
+  // Add SCTs in mixed order.
+  tree_tracker_->OnSCTVerified(chain_.get(), newer_than_new_sth_sct.get());
+  tree_tracker_->OnSCTVerified(chain_.get(), oldest_sct.get());
+  tree_tracker_->OnSCTVerified(chain_.get(),
+                               not_auditable_by_new_sth_sct.get());
+  tree_tracker_->OnSCTVerified(chain_.get(), newer_than_old_sth_sct.get());
+  tree_tracker_->OnSCTVerified(chain_.get(),
+                               not_auditable_by_old_sth_sct.get());
+
+  // Ensure all are in the PENDING_NEWER_STH state.
+  AssertSCTsMatchingState<SignedCertificateTimestamp*>(
+      tree_tracker_.get(), chain_.get(),
+      SingleTreeTracker::SCT_PENDING_NEWER_STH, oldest_sct.get(),
+      not_auditable_by_old_sth_sct.get(), newer_than_old_sth_sct.get(),
+      not_auditable_by_new_sth_sct.get(), newer_than_new_sth_sct.get());
+
+  // Provide the old STH, ensure only the oldest one is auditable.
+  tree_tracker_->NewSTHObserved(old_sth);
+  // Ensure all but the oldest are in the PENDING_NEWER_STH state.
+  AssertSCTsMatchingState<SignedCertificateTimestamp*>(
+      tree_tracker_.get(), chain_.get(),
+      SingleTreeTracker::SCT_PENDING_INCLUSION_CHECK, oldest_sct.get());
+
+  AssertSCTsMatchingState<SignedCertificateTimestamp*>(
+      tree_tracker_.get(), chain_.get(),
+      SingleTreeTracker::SCT_PENDING_NEWER_STH,
+      not_auditable_by_old_sth_sct.get(), newer_than_old_sth_sct.get(),
+      not_auditable_by_new_sth_sct.get(), newer_than_new_sth_sct.get());
+
+  // Provide the newer one, ensure two more are auditable but the
+  // rest aren't.
+  tree_tracker_->NewSTHObserved(new_sth);
+
+  AssertSCTsMatchingState<SignedCertificateTimestamp*>(
+      tree_tracker_.get(), chain_.get(),
+      SingleTreeTracker::SCT_PENDING_INCLUSION_CHECK, oldest_sct.get(),
+      not_auditable_by_old_sth_sct.get(), newer_than_old_sth_sct.get());
+
+  AssertSCTsMatchingState<SignedCertificateTimestamp*>(
+      tree_tracker_.get(), chain_.get(),
+      SingleTreeTracker::SCT_PENDING_NEWER_STH,
+      not_auditable_by_new_sth_sct.get(), newer_than_new_sth_sct.get());
+}
+
+// Test that if a request for an entry is throttled, it remains in a
+// pending state.
+
+// Test that if several entries are throttled, when the LogDnsClient notifies
+// of un-throttling all entries are handled.
+TEST_F(SingleTreeTrackerTest, TestThrottledEntryGetsHandledAfterUnthrottling) {
+  std::vector<std::string> audit_proof;
+  FillVectorWithValidAuditProofForTreeOfSize2(&audit_proof);
+
+  ClearDnsConfig();

[Ryan Sleevi, 2016/12/14 01:34:15]

Unnecessary?

[Eran Messeri, 2016/12/22 16:12:11]

Acknowledged, see above.

+  ASSERT_TRUE(mock_dns_->ExpectLeafIndexRequestAndResponse(
+      Base32LeafHash(chain_.get(), cert_sct_.get()) + ".hash.dns.example."
+                                                      "com",
+      0));
+  ASSERT_TRUE(mock_dns_->ExpectAuditProofRequestAndResponse(
+      "0.0.2.tree.dns.example.com", audit_proof.begin(),
+      audit_proof.begin() + 1));
+
+  scoped_refptr<SignedCertificateTimestamp> second_sct(GetSCT());
+  second_sct->timestamp -= base::TimeDelta::FromHours(1);
+
+  // Process request for |second_sct|
+  ASSERT_TRUE(mock_dns_->ExpectLeafIndexRequestAndResponse(
+      Base32LeafHash(chain_.get(), second_sct.get()) + ".hash.dns.example."
+                                                       "com",
+      1));
+  ASSERT_TRUE(mock_dns_->ExpectAuditProofRequestAndResponse(
+      "0.1.2.tree.dns.example.com", audit_proof.begin(),
+      audit_proof.begin() + 1));
+
+  CreateTreeTracker();
+
+  SignedTreeHead sth;
+  ASSERT_TRUE(GetSignedTreeHeadForTreeOfSize2(&sth));
+  tree_tracker_->NewSTHObserved(sth);
+
+  tree_tracker_->OnSCTVerified(chain_.get(), cert_sct_.get());
+  tree_tracker_->OnSCTVerified(chain_.get(), second_sct.get());
+
+  // Both entries should be in the pending state, the first because the
+  // LogDnsClient did not invoke the callback yet, the second one because
+  // the LogDnsClient is "busy" with the first entry and so would throttle.
+  ASSERT_EQ(
+      SingleTreeTracker::SCT_PENDING_INCLUSION_CHECK,
+      tree_tracker_->GetLogEntryInclusionStatus(chain_.get(), cert_sct_.get()));
+  ASSERT_EQ(SingleTreeTracker::SCT_PENDING_INCLUSION_CHECK,
+            tree_tracker_->GetLogEntryInclusionStatus(chain_.get(),
+                                                      second_sct.get()));
+
+  // Pump the message loop.

[Ryan Sleevi, 2016/12/14 01:34:16]

It's obvious from line 579 that the message loop will be pumped - and thus, as a
comment, is unnecessary (which you seem to have omitted from line 420)

What's not obvious is why. :)

[Eran Messeri, 2016/12/22 16:12:11]

Done - replaced the comment.

+  base::RunLoop().RunUntilIdle();
+
+  // Check that the first sct is included in the log.
+  ASSERT_EQ(
+      SingleTreeTracker::SCT_INCLUDED_IN_LOG,
+      tree_tracker_->GetLogEntryInclusionStatus(chain_.get(), cert_sct_.get()));
+
+  // Check that the second SCT got an invalid proof and is not included, rather
+  // than being in the pending state.
+  ASSERT_EQ(SingleTreeTracker::SCT_NOT_OBSERVED,
+            tree_tracker_->GetLogEntryInclusionStatus(chain_.get(),
+                                                      second_sct.get()));
+}
+
+// Test that proof fetching failure due to DNS config errors is handled
+// correctly:
+//   (1) Entry removed from pending queue.
+//   (2) UMA logged
+TEST_F(SingleTreeTrackerTest,
+       TestProofLookupDueToBadDNSConfigHandledCorrectly) {
+  base::HistogramTester histograms;
+  // Provide an STH to the tree_tracker_.
+  SignedTreeHead sth;
+  net::ct::GetSampleSignedTreeHead(&sth);
+
+  // Clear existing DNS configuration, so that the DnsClient created
+  // by the MockLogDnsTraffic has no valid DnsConfig.
+  net_change_notifier_.reset();
+  net_change_notifier_.reset(net::NetworkChangeNotifier::CreateMock());
+  CreateTreeTracker();
+
+  tree_tracker_->NewSTHObserved(sth);
+  tree_tracker_->OnSCTVerified(chain_.get(), cert_sct_.get());
+
+  // Make sure the SCT status indicates the entry has been removed from
+  // the SingleTreeTracker's internal queue as the DNS lookup failed
+  // synchronously.
+  EXPECT_EQ(
+      SingleTreeTracker::SCT_NOT_OBSERVED,
+      tree_tracker_->GetLogEntryInclusionStatus(chain_.get(), cert_sct_.get()));
+
+  // Exactly one value should be logged, indicating the SCT can be checked for
+  // inclusion, as |tree_tracker_| did have a valid STH when it was notified
+  // of a new SCT.
+  histograms.ExpectTotalCount(kCanCheckForInclusionHistogramName, 1);
+  histograms.ExpectBucketCount(kCanCheckForInclusionHistogramName, 2, 1);
+  // Failure due to DNS configuration should be logged in the result histogram.
+  histograms.ExpectTotalCount(kInclusionCheckResultHistogramName, 1);
+  histograms.ExpectBucketCount(kInclusionCheckResultHistogramName, 3, 1);
+}
+
 }  // namespace certificate_transparency