Add Certificate Transparency logs auditing

components/certificate_transparency/single_tree_tracker_unittest.cc

Index: components/certificate_transparency/single_tree_tracker_unittest.cc
diff --git a/components/certificate_transparency/single_tree_tracker_unittest.cc b/components/certificate_transparency/single_tree_tracker_unittest.cc
index 43ea4fd446a7c7c450a8f7b0e0159b95a29bbb22..5235821c497bcaa705a492bf66ba5f5c2065d669 100644
--- a/components/certificate_transparency/single_tree_tracker_unittest.cc
+++ b/components/certificate_transparency/single_tree_tracker_unittest.cc
@@ -7,25 +7,50 @@
 #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;
+using net::ct::GetSampleSignedTreeHead;
+using net::ct::GetTestPublicKeyId;
+using net::ct::GetTestPublicKey;
+using net::ct::kSthRootHashLength;
+using net::ct::GetX509CertSCT;
+
 namespace certificate_transparency {
 
 namespace {
 
 const char kCanCheckForInclusionHistogramName[] =
     "Net.CertificateTransparency.CanInclusionCheckSCT";
+const char kInclusionCheckResultHistogramName[] =
+    "Net.CertificateTransparency.InclusionCheckResult";
+
+const char kDNSRequestSuffix[] = "dns.example.com";
 
-bool GetOldSignedTreeHead(net::ct::SignedTreeHead* sth) {
-  sth->version = net::ct::SignedTreeHead::V1;
+constexpr 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;
@@ -34,9 +59,9 @@ bool GetOldSignedTreeHead(net::ct::SignedTreeHead* sth) {
       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);
+  memcpy(sth->sha256_root_hash, kOldSTHRootHash, kSthRootHashLength);
 
-  sth->log_id = net::ct::GetTestPublicKeyId();
+  sth->log_id = GetTestPublicKeyId();
 
   const uint8_t kOldSTHSignatureData[] = {
       0x04, 0x03, 0x00, 0x47, 0x30, 0x45, 0x02, 0x20, 0x15, 0x7b, 0x23,
@@ -51,35 +76,159 @@ bool GetOldSignedTreeHead(net::ct::SignedTreeHead* sth) {
   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
+  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);
+}
+
+// Assert that the status of each of the SCTs in |scts| in the |tree_tracker|
+// matches |status| (all SCTs are for |chain|).
+template <typename... T>
+void AssertSCTsMatchingState(SingleTreeTracker* tree_tracker,
+                             net::X509Certificate* chain,

[Ryan Sleevi, 2017/01/20 12:53:21]

Did you see the previous remarks (
https://codereview.chromium.org/2017563002/diff/380001/components/certificate...
) ?

[Eran Messeri, 2017/01/23 16:45:47]

My bad, I've missed it, changed to your suggestion from that comment.

+                             SingleTreeTracker::SCTInclusionStatus status,
+                             T... scts) {
+  const size_t 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;
+  }
+};
+
+// Fills in |sth| for a tree of size 2, where the root hash is a hash of
+// the test SCT (from GetX509CertSCT) and another entry,
+// whose hash is '0a' 32 times.
+bool GetSignedTreeHeadForTreeOfSize2(SignedTreeHead* sth) {
+  sth->version = SignedTreeHead::V1;
+  // Timestamp is after the timestamp of the test SCT (GetX509CertSCT)
+  // to indicate it can be audited using this STH.
+  sth->timestamp = base::Time::UnixEpoch() +
+                   base::TimeDelta::FromMilliseconds(INT64_C(1365354256089));
+  sth->tree_size = 2;
+  // Root hash is:
+  // HASH (0x01 || HASH(log entry made of test SCT) || HASH(0x0a * 32))
+  // The proof provided by FillVectorWithValidAuditProofForTreeOfSize2 would
+  // validate with this root hash for the log entry made of the test SCT +
+  // cert.
+  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};
+  memcpy(sth->sha256_root_hash, reinterpret_cast<const char*>(kRootHash),
+         kSthRootHashLength);
+
+  sth->log_id = GetTestPublicKeyId();
+
+  // valid signature over the STH, using the test log key at:
+  // https://github.com/google/certificate-transparency/blob/master/test/testdata/ct-server-key.pem
+  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};
+
+  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");
+        net::CTLogVerifier::Create(GetTestPublicKey(), "testlog",
+                                   "https://ct.example.com", kDNSRequestSuffix);
 
     ASSERT_TRUE(log_);
-    ASSERT_EQ(log_->key_id(), net::ct::GetTestPublicKeyId());
+    ASSERT_EQ(log_->key_id(), 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_);
+    GetX509CertSCT(&cert_sct_);
+    cert_sct_->origin = SignedCertificateTimestamp::SCT_FROM_OCSP_RESPONSE;
+
+    net_change_notifier_ =
+        base::WrapUnique(net::NetworkChangeNotifier::CreateMock());
+    mock_dns_.InitializeDnsConfig();
   }
 
  protected:
+  void CreateTreeTracker() {
+    log_dns_client_ = base::MakeUnique<LogDnsClient>(
+        mock_dns_.CreateDnsClient(), net_log_, 1);
+
+    tree_tracker_ =
+        base::MakeUnique<SingleTreeTracker>(log_, log_dns_client_.get());
+  }
+
+  void CreateTreeTrackerWithDefaultDnsExpectation() {
+    // Default to throttling requests as it means observed log entries will
+    // be frozen in a pending state, simplifying testing of the
+    // SingleTreeTracker.
+    ASSERT_TRUE(ExpectLeafIndexRequestAndThrottle(chain_, cert_sct_));
+    CreateTreeTracker();
+  }
+
+  // Configured the |mock_dns_| to expect a request for the leaf index
+  // and have th mock DNS client throttle it.
+  bool ExpectLeafIndexRequestAndThrottle(
+      const scoped_refptr<net::X509Certificate>& chain,
+      const scoped_refptr<SignedCertificateTimestamp>& sct) {
+    return mock_dns_.ExpectRequestAndSocketError(
+        Base32LeafHash(chain.get(), sct.get()) + ".hash." + kDNSRequestSuffix,
+        net::Error::ERR_TEMPORARILY_THROTTLED);
+  }
+
+  base::MessageLoopForIO message_loop_;
+  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) {
+  CreateTreeTrackerWithDefaultDnsExpectation();
+
   base::HistogramTester histograms;
   // First make sure the SCT has not been observed at all.
   EXPECT_EQ(
@@ -102,10 +251,12 @@ TEST_F(SingleTreeTrackerTest, CorrectlyClassifiesUnobservedSCTNoSTH) {
 // 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) {
+  CreateTreeTrackerWithDefaultDnsExpectation();
+
   base::HistogramTester histograms;
   // Provide an STH to the tree_tracker_.
-  net::ct::SignedTreeHead sth;
-  net::ct::GetSampleSignedTreeHead(&sth);
+  SignedTreeHead sth;
+  GetSampleSignedTreeHead(&sth);
   tree_tracker_->NewSTHObserved(sth);
 
   // Make sure the SCT status is the same as if there's no STH for
@@ -127,12 +278,17 @@ TEST_F(SingleTreeTrackerTest, CorrectlyClassifiesUnobservedSCTWithRecentSTH) {
   // 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) {
+  CreateTreeTrackerWithDefaultDnsExpectation();
+
   base::HistogramTester histograms;
   // Report an observed SCT and make sure it's in the pending newer STH
   // state.
@@ -143,8 +299,8 @@ TEST_F(SingleTreeTrackerTest, CorrectlyUpdatesSCTStatusOnNewSTH) {
   histograms.ExpectTotalCount(kCanCheckForInclusionHistogramName, 1);
 
   // Provide with a fresh STH
-  net::ct::SignedTreeHead sth;
-  net::ct::GetSampleSignedTreeHead(&sth);
+  SignedTreeHead sth;
+  GetSampleSignedTreeHead(&sth);
   tree_tracker_->NewSTHObserved(sth);
 
   // Test that its status has changed.
@@ -161,6 +317,8 @@ TEST_F(SingleTreeTrackerTest, CorrectlyUpdatesSCTStatusOnNewSTH) {
 // from the log it was issued by is observed, but that STH is too old to check
 // inclusion against.
 TEST_F(SingleTreeTrackerTest, DoesNotUpdatesSCTStatusOnOldSTH) {
+  CreateTreeTrackerWithDefaultDnsExpectation();
+
   // 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(
@@ -168,7 +326,7 @@ TEST_F(SingleTreeTrackerTest, DoesNotUpdatesSCTStatusOnOldSTH) {
       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);
 
@@ -182,9 +340,11 @@ TEST_F(SingleTreeTrackerTest, DoesNotUpdatesSCTStatusOnOldSTH) {
 // STH, when it has a valid STH,  but the observed SCT is not covered by the
 // STH.
 TEST_F(SingleTreeTrackerTest, LogsUMAForNewSCTAndOldSTH) {
+  CreateTreeTrackerWithDefaultDnsExpectation();
+
   base::HistogramTester histograms;
   // Provide an old STH for the same log.
-  net::ct::SignedTreeHead sth;
+  SignedTreeHead sth;
   GetOldSignedTreeHead(&sth);
   tree_tracker_->NewSTHObserved(sth);
 
@@ -199,4 +359,306 @@ TEST_F(SingleTreeTrackerTest, LogsUMAForNewSCTAndOldSTH) {
   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) {
+  ASSERT_TRUE(mock_dns_.ExpectRequestAndSocketError(
+      Base32LeafHash(chain_.get(), cert_sct_.get()) + ".hash." +
+          kDNSRequestSuffix,
+      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;
+  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) {
+  // Return 12 as the index of this leaf.
+  ASSERT_TRUE(mock_dns_.ExpectLeafIndexRequestAndResponse(
+      Base32LeafHash(chain_.get(), cert_sct_.get()) + ".hash." +
+          kDNSRequestSuffix,
+      12));
+  // Expect a request for an inclusion proof for leaf #12 in a tree of size
+  // 21, which is the size of the tree in the STH returned by
+  // GetSampleSignedTreeHead.
+  ASSERT_TRUE(mock_dns_.ExpectRequestAndSocketError(
+      std::string("0.12.21.tree.") + kDNSRequestSuffix,
+      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;
+  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);
+
+  // Return 0 as the index for this leaf, so the proof provided
+  // later on would verify.
+  ASSERT_TRUE(mock_dns_.ExpectLeafIndexRequestAndResponse(
+      Base32LeafHash(chain_.get(), cert_sct_.get()) + ".hash." +
+          kDNSRequestSuffix,
+      0));
+  // The STH (later on) is for a tree of size 2 and the entry has index 0
+  // in the tree, so expect an inclusion proof for entry 0 in a tree
+  // of size 2 (0.0.2).
+  ASSERT_TRUE(mock_dns_.ExpectAuditProofRequestAndResponse(
+      std::string("0.0.2.tree.") + kDNSRequestSuffix, audit_proof.begin(),
+      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, which is for a tree of size 2.
+  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).
+// * 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.
+TEST_F(SingleTreeTrackerTest, TestMultipleEntriesTransitionStateCorrectly) {
+  SignedTreeHead old_sth;
+  GetOldSignedTreeHead(&old_sth);
+
+  SignedTreeHead new_sth;
+  GetSampleSignedTreeHead(&new_sth);
+
+  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.
+  ASSERT_TRUE(ExpectLeafIndexRequestAndThrottle(chain_, oldest_sct));
+  ASSERT_TRUE(
+      ExpectLeafIndexRequestAndThrottle(chain_, not_auditable_by_old_sth_sct));
+  ASSERT_TRUE(
+      ExpectLeafIndexRequestAndThrottle(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);
+
+  ASSERT_TRUE(mock_dns_.ExpectLeafIndexRequestAndResponse(
+      Base32LeafHash(chain_.get(), cert_sct_.get()) + ".hash." +
+          kDNSRequestSuffix,
+      0));
+  ASSERT_TRUE(mock_dns_.ExpectAuditProofRequestAndResponse(
+      std::string("0.0.2.tree.") + kDNSRequestSuffix, 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." +
+          kDNSRequestSuffix,
+      1));
+  ASSERT_TRUE(mock_dns_.ExpectAuditProofRequestAndResponse(
+      std::string("0.1.2.tree.") + kDNSRequestSuffix, 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()));
+
+  // Process pending DNS queries so later assertions are on handling
+  // of the entries based on replies received.
+  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;
+  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_ =
+      base::WrapUnique(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