Certificate path builder for new certificate verification library

net/cert/internal/path_builder_unittest.cc

Index: net/cert/internal/path_builder_unittest.cc
diff --git a/net/cert/internal/path_builder_unittest.cc b/net/cert/internal/path_builder_unittest.cc
new file mode 100644
index 0000000000000000000000000000000000000000..06dd6488c97c200e9675da7a58da5f3a1da14b87
--- /dev/null
+++ b/net/cert/internal/path_builder_unittest.cc
@@ -0,0 +1,840 @@
+// 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 "net/cert/internal/path_builder.h"
+
+#include "base/base_paths.h"
+#include "base/cancelable_callback.h"
+#include "base/files/file_util.h"
+#include "base/location.h"
+#include "base/path_service.h"
+#include "base/thread_task_runner_handle.h"
+#include "net/base/net_errors.h"
+#include "net/base/test_completion_callback.h"
+#include "net/cert/internal/parse_certificate.h"
+#include "net/cert/internal/parse_name.h"
+#include "net/cert/internal/signature_policy.h"
+#include "net/cert/internal/test_helpers.h"
+#include "net/cert/internal/verify_certificate_chain.h"
+#include "net/cert/pem_tokenizer.h"
+#include "net/der/input.h"
+#include "net/test/cert_test_util.h"
+#include "net/test/test_certificate_data.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace net {
+
+namespace {
+
+// AsyncStaticCertSource always returns its certs asynchronously.
+class AsyncStaticCertSource : public CertSource {
+ public:
+  class StaticAsyncRequest : public Request {
+   public:
+    StaticAsyncRequest(const IssuerCallback& issuers_callback,
+                       CertVector&& issuers)
+        : cancelable_closure_(base::Bind(&StaticAsyncRequest::RunCallback,
+                                         base::Unretained(this))),
+          issuers_callback_(issuers_callback) {
+      issuers_.swap(issuers);
+    }
+    ~StaticAsyncRequest() override {}
+
+    void RunCallback() { issuers_callback_.Run(std::move(issuers_)); }
+    base::Closure callback() { return cancelable_closure_.callback(); }
+
+   private:
+    base::CancelableClosure cancelable_closure_;
+    IssuerCallback issuers_callback_;
+    CertVector issuers_;
+    AsyncStaticCertSource* source_;
+
+    DISALLOW_COPY_AND_ASSIGN(StaticAsyncRequest);
+  };
+
+  AsyncStaticCertSource(const CertVector& certs) : static_cert_source_(certs) {}
+  ~AsyncStaticCertSource() override {}
+
+  void SyncGetIssuersOf(const CertThing* cert, CertVector* issuers) override {}
+  int AsyncGetIssuersOf(const CertThing* cert,
+                        const IssuerCallback& issuers_callback,
+                        std::unique_ptr<Request>* out_req) override {
+    num_async_gets_++;
+    CertVector issuers;
+    static_cert_source_.SyncGetIssuersOf(cert, &issuers);
+    std::unique_ptr<StaticAsyncRequest> req(
+        new StaticAsyncRequest(issuers_callback, std::move(issuers)));
+    base::ThreadTaskRunnerHandle::Get()->PostTask(FROM_HERE, req->callback());
+    *out_req = std::move(req);
+    return ERR_IO_PENDING;
+  }
+  int num_async_gets() const { return num_async_gets_; }
+
+ private:
+  StaticCertSource static_cert_source_;
+
+  int num_async_gets_ = 0;
+};
+
+// Reads a data file from the unit-test data.
+std::string ReadTestFileToString(const std::string& file_name) {
+  // Compute the full path, relative to the src/ directory.
+  base::FilePath src_root;
+  PathService::Get(base::DIR_SOURCE_ROOT, &src_root);
+  base::FilePath filepath = src_root.AppendASCII(file_name);
+
+  // Read the full contents of the file.
+  std::string file_data;
+  if (!base::ReadFileToString(filepath, &file_data)) {
+    ADD_FAILURE() << "Couldn't read file: " << filepath.value();
+    return std::string();
+  }
+
+  return file_data;
+}
+
+// Reads a verify_certificate_chain_unittest-style test case from |file_name|.
+// Test cases are comprised of a certificate chain, trust store, a timestamp to
+// validate at, and the expected result of verification (though the expected
+// result is ignored here).
+void ReadVerifyCertChainTestFromFile(const std::string& file_name,
+                                     std::vector<std::string>* chain,
+                                     scoped_refptr<CertThing>* root,
+                                     der::GeneralizedTime* time) {
+  chain->clear();
+
+  std::string file_data = ReadTestFileToString(file_name);
+
+  std::vector<std::string> pem_headers;
+
+  const char kCertificateHeader[] = "CERTIFICATE";
+  const char kTrustedCertificateHeader[] = "TRUSTED_CERTIFICATE";
+  const char kTimeHeader[] = "TIME";
+
+  pem_headers.push_back(kCertificateHeader);
+  pem_headers.push_back(kTrustedCertificateHeader);
+  pem_headers.push_back(kTimeHeader);
+
+  bool has_time = false;
+
+  PEMTokenizer pem_tokenizer(file_data, pem_headers);
+  while (pem_tokenizer.GetNext()) {
+    const std::string& block_type = pem_tokenizer.block_type();
+    const std::string& block_data = pem_tokenizer.data();
+
+    if (block_type == kCertificateHeader) {
+      chain->push_back(block_data);
+    } else if (block_type == kTrustedCertificateHeader) {
+      *root = CertThing::CreateFromCertificateCopy(block_data);
+      ASSERT_TRUE(*root);
+    } else if (block_type == kTimeHeader) {
+      ASSERT_FALSE(has_time) << "Duplicate " << kTimeHeader;
+      has_time = true;
+      ASSERT_TRUE(der::ParseUTCTime(der::Input(&block_data), time));
+    }
+  }
+
+  ASSERT_TRUE(has_time);
+}
+
+::testing::AssertionResult ReadTestPem(const std::string& file_name,
+                                       const std::string& block_name,
+                                       std::string* result) {
+  const PemBlockMapping mappings[] = {
+      {block_name.c_str(), result},
+  };
+
+  return ReadTestDataFromPemFile(file_name, mappings);
+}
+
+::testing::AssertionResult ReadTestCert(const std::string& file_name,
+                                        scoped_refptr<CertThing>* result) {
+  std::string der;
+  ::testing::AssertionResult r = ReadTestPem(
+      "net/data/ssl/certificates/" + file_name, "CERTIFICATE", &der);
+  if (!r)
+    return r;
+  *result = CertThing::CreateFromCertificateCopy(der);
+  if (!*result)
+    return ::testing::AssertionFailure() << "CreateFromCertificateCopy failed";
+  return ::testing::AssertionSuccess();
+}
+
+std::string DumpCertChain(const std::vector<scoped_refptr<CertThing>>& chain) {
+  std::string s;
+  for (const auto& i : chain) {
+    ParsedCertificate cert;
+    ParsedTbsCertificate tbs;
+    if (!ParseCertificate(i->der_cert(), &cert))  // XXX don't reparse
+      return std::string();
+    if (!ParseTbsCertificate(cert.tbs_certificate_tlv, &tbs))
+      return std::string();
+    RDNSequence subject, issuer;
+    if (!ParseName(tbs.subject_tlv, &subject))
+      return std::string();
+    if (!ParseName(tbs.issuer_tlv, &issuer))
+      return std::string();
+
+    std::string subject_str, issuer_str;
+
+    if (!ConvertToRFC2253(subject, &subject_str))
+      return std::string();
+    if (!ConvertToRFC2253(issuer, &issuer_str))
+      return std::string();
+    if (!s.empty())
+      s += " -> ";
+    s += subject_str + "(" + issuer_str + ")";
+  }
+  return s;
+}
+
+void DumpPathBuilderResults(const CertPathBuilder::Result& result) {
+  DVLOG(1) << "CertPathBuilder results (n=" << result.paths.size() << "):";
+  for (size_t i = 0; i < result.paths.size(); ++i) {
+    DVLOG(1) << " " << i << ((result.best_result_index == i) ? "*" : " ") << " "
+             << result.paths[i]->rv << " "
+             << DumpCertChain(result.paths[i]->path);
+  }
+  // DVLOG(1) << "result path: " << DumpCertChain(result.path);
+}
+
+class PathBuilderMultiRootTest : public ::testing::Test {
+ public:
+  PathBuilderMultiRootTest() : signature_policy_(1024) {}
+
+  void SetUp() override {
+    ASSERT_TRUE(ReadTestCert("multi-root-A-by-B.pem", &a_by_b_));
+    ASSERT_TRUE(ReadTestCert("multi-root-B-by-C.pem", &b_by_c_));
+    ASSERT_TRUE(ReadTestCert("multi-root-B-by-F.pem", &b_by_f_));
+    ASSERT_TRUE(ReadTestCert("multi-root-C-by-D.pem", &c_by_d_));
+    ASSERT_TRUE(ReadTestCert("multi-root-C-by-E.pem", &c_by_e_));
+    ASSERT_TRUE(ReadTestCert("multi-root-D-by-D.pem", &d_by_d_));
+    ASSERT_TRUE(ReadTestCert("multi-root-E-by-E.pem", &e_by_e_));
+    ASSERT_TRUE(ReadTestCert("multi-root-F-by-E.pem", &f_by_e_));
+  }
+
+ protected:
+  scoped_refptr<CertThing> a_by_b_, b_by_c_, b_by_f_, c_by_d_, c_by_e_, d_by_d_,
+      e_by_e_, f_by_e_;
+
+  SimpleSignaturePolicy signature_policy_;
+  der::GeneralizedTime time_ = {2016, 4, 11, 0, 0, 0};
+};
+
+// XXX
+//
+TEST_F(PathBuilderMultiRootTest, Simple) {
+  TrustStore trust_store;
+  trust_store.AddTrustedCertificate(b_by_f_);
+
+  CertPathBuilder::CertSources cert_sources;
+
+  scoped_refptr<CertThing> target_cert(a_by_b_);
+
+  CertPathBuilder::Result result;
+  CertPathBuilder path_builder(std::move(target_cert), cert_sources,
+                               trust_store, &signature_policy_, time_, &result);
+
+  TestCompletionCallback callback;
+  int rv = path_builder.Run(callback.callback());
+
+  DVLOG(1) << "path_builder.Run rv=" << ErrorToString(rv);
+
+  EXPECT_EQ(OK, rv);
+
+  if (rv == ERR_IO_PENDING) {
+    DVLOG(1) << "waiting for async completion...";
+    rv = callback.WaitForResult();
+    DVLOG(1) << "async rv=" << ErrorToString(rv);
+    EXPECT_EQ(OK, rv);
+  }
+
+  // DVLOG(1) << "result path: " << DumpCertChain(result.path);
+  DumpPathBuilderResults(result);
+}
+
+// Test that async cert queries are not made if the path can be successfully
+// built with synchronously available certs.
+TEST_F(PathBuilderMultiRootTest, TriesSyncFirst) {
+  TrustStore trust_store;
+  trust_store.AddTrustedCertificate(e_by_e_);
+
+  CertVector sync_certs;
+  sync_certs.push_back(a_by_b_);
+  // XXX if B(C) is in certs, it may check that path first, which would try to
+  // do async query for issuers of C.
+  // sync_certs.push_back(b_by_c);
+  sync_certs.push_back(b_by_f_);
+  sync_certs.push_back(f_by_e_);
+  StaticCertSource sync_cert_source(sync_certs);
+
+  CertVector async_certs;
+  async_certs.push_back(b_by_c_);
+  async_certs.push_back(c_by_e_);
+  AsyncStaticCertSource async_cert_source(async_certs);
+
+  CertPathBuilder::CertSources cert_sources;
+  cert_sources.push_back(&async_cert_source);
+  cert_sources.push_back(&sync_cert_source);
+
+  scoped_refptr<CertThing> target_cert(a_by_b_);
+
+  CertPathBuilder::Result result;
+  CertPathBuilder path_builder(std::move(target_cert), cert_sources,
+                               trust_store, &signature_policy_, time_, &result);
+
+  TestCompletionCallback callback;
+  int rv = path_builder.Run(callback.callback());
+
+  DVLOG(1) << "path_builder.Run rv=" << ErrorToString(rv);
+
+  EXPECT_EQ(OK, rv);
+
+  if (rv == ERR_IO_PENDING) {
+    DVLOG(1) << "waiting for async completion...";
+    rv = callback.WaitForResult();
+    DVLOG(1) << "async rv=" << ErrorToString(rv);
+    EXPECT_EQ(OK, rv);
+  }
+
+  // DVLOG(1) << "result path: " << DumpCertChain(result.path);
+  DumpPathBuilderResults(result);
+
+  EXPECT_EQ(0, async_cert_source.num_async_gets());
+}
+
+// If async queries are needed, all async sources will be queried
+// simultaneously.
+TEST_F(PathBuilderMultiRootTest, TestAsyncSimultaneous) {
+  TrustStore trust_store;
+  trust_store.AddTrustedCertificate(e_by_e_);
+
+  CertVector sync_certs;
+  sync_certs.push_back(a_by_b_);
+  sync_certs.push_back(b_by_c_);
+  sync_certs.push_back(b_by_f_);
+  StaticCertSource sync_cert_source(sync_certs);
+
+  CertVector async_certs1;
+  async_certs1.push_back(c_by_e_);
+  AsyncStaticCertSource async_cert_source1(async_certs1);
+
+  CertVector async_certs2;
+  async_certs2.push_back(f_by_e_);
+  AsyncStaticCertSource async_cert_source2(async_certs2);
+
+  CertPathBuilder::CertSources cert_sources;
+  cert_sources.push_back(&async_cert_source1);
+  cert_sources.push_back(&async_cert_source2);
+  cert_sources.push_back(&sync_cert_source);
+
+  scoped_refptr<CertThing> target_cert(a_by_b_);
+
+  CertPathBuilder::Result result;
+  CertPathBuilder path_builder(std::move(target_cert), cert_sources,
+                               trust_store, &signature_policy_, time_, &result);
+
+  TestCompletionCallback callback;
+  int rv = path_builder.Run(callback.callback());
+
+  DVLOG(1) << "path_builder.Run rv=" << ErrorToString(rv);
+
+  EXPECT_EQ(ERR_IO_PENDING, rv);
+
+  if (rv == ERR_IO_PENDING) {
+    DVLOG(1) << "waiting for async completion...";
+    rv = callback.WaitForResult();
+    DVLOG(1) << "async rv=" << ErrorToString(rv);
+    EXPECT_EQ(OK, rv);
+  }
+
+  // DVLOG(1) << "result path: " << DumpCertChain(result.path);
+  DumpPathBuilderResults(result);
+
+  EXPECT_EQ(1, async_cert_source1.num_async_gets());
+  EXPECT_EQ(1, async_cert_source2.num_async_gets());
+}
+
+// Test that PathBuilder does not generate longer paths than necessary if one of
+// the supplied certs is itself a trust anchor.
+TEST_F(PathBuilderMultiRootTest, TestLongChain) {
+  // Both D(D) and C(D) are trusted roots.
+  TrustStore trust_store;
+  trust_store.AddTrustedCertificate(d_by_d_);
+  trust_store.AddTrustedCertificate(c_by_d_);
+
+  // Certs A(B), B(C), and C(D) are all supplied.
+  CertVector sync_certs;
+  sync_certs.push_back(a_by_b_);
+  sync_certs.push_back(b_by_c_);
+  sync_certs.push_back(c_by_d_);
+  StaticCertSource sync_cert_source(sync_certs);
+
+  CertPathBuilder::CertSources cert_sources;
+  cert_sources.push_back(&sync_cert_source);
+
+  scoped_refptr<CertThing> target_cert(a_by_b_);
+
+  CertPathBuilder::Result result;
+  CertPathBuilder path_builder(std::move(target_cert), cert_sources,
+                               trust_store, &signature_policy_, time_, &result);
+
+  TestCompletionCallback callback;
+  int rv = path_builder.Run(callback.callback());
+
+  DVLOG(1) << "path_builder.Run rv=" << ErrorToString(rv);
+
+  EXPECT_EQ(OK, rv);
+
+  if (rv == ERR_IO_PENDING) {
+    DVLOG(1) << "waiting for async completion...";
+    rv = callback.WaitForResult();
+    DVLOG(1) << "async rv=" << ErrorToString(rv);
+    EXPECT_EQ(OK, rv);
+  }
+
+  // DVLOG(1) << "result path: " << DumpCertChain(result.path);
+  DumpPathBuilderResults(result);
+
+  // The result path should be A(B) -> B(C) -> C(D)
+  // not the longer but also valid A(B) -> B(C) -> C(D) -> D(D)
+
+  EXPECT_EQ(3U, result.paths[result.best_result_index]->path.size());
+}
+
+// Test that PathBuilder will backtrack and try a different path if the first
+// one doesn't work out.
+TEST_F(PathBuilderMultiRootTest, TestBacktracking) {
+  // Only D(D) is a trusted root.
+  TrustStore trust_store;
+  trust_store.AddTrustedCertificate(d_by_d_);
+
+  // Certs A(B), B(F), and F(E) are supplied synchronously, thus the path
+  // A(B) -> B(F) -> F(E) should be built first, though it won't verify.
+  CertVector sync_certs;
+  sync_certs.push_back(a_by_b_);
+  sync_certs.push_back(b_by_f_);
+  sync_certs.push_back(f_by_e_);
+  StaticCertSource sync_cert_source(sync_certs);
+
+  // Certs B(C), and C(D) are supplied asynchronously, so the path
+  // A(B) -> B(C) -> C(D) -> D(D) should be tried second.
+  CertVector async_certs;
+  async_certs.push_back(b_by_c_);
+  async_certs.push_back(c_by_d_);
+  AsyncStaticCertSource async_cert_source(async_certs);
+
+  CertPathBuilder::CertSources cert_sources;
+  cert_sources.push_back(&sync_cert_source);
+  cert_sources.push_back(&async_cert_source);
+
+  scoped_refptr<CertThing> target_cert(a_by_b_);
+
+  CertPathBuilder::Result result;
+  CertPathBuilder path_builder(std::move(target_cert), cert_sources,
+                               trust_store, &signature_policy_, time_, &result);
+
+  TestCompletionCallback callback;
+  int rv = path_builder.Run(callback.callback());
+
+  DVLOG(1) << "path_builder.Run rv=" << ErrorToString(rv);
+
+  EXPECT_EQ(ERR_IO_PENDING, rv);
+
+  if (rv == ERR_IO_PENDING) {
+    DVLOG(1) << "waiting for async completion...";
+    rv = callback.WaitForResult();
+    DVLOG(1) << "async rv=" << ErrorToString(rv);
+    EXPECT_EQ(OK, rv);
+  }
+
+  // DVLOG(1) << "result path: " << DumpCertChain(result.path);
+  DumpPathBuilderResults(result);
+
+  // The result path should be A(B) -> B(C) -> C(D) -> D(D)
+  ASSERT_EQ(4U, result.paths[result.best_result_index]->path.size());
+  EXPECT_EQ(a_by_b_, result.paths[result.best_result_index]->path[0]);
+  EXPECT_EQ(b_by_c_, result.paths[result.best_result_index]->path[1]);
+  EXPECT_EQ(c_by_d_, result.paths[result.best_result_index]->path[2]);
+  EXPECT_EQ(d_by_d_, result.paths[result.best_result_index]->path[3]);
+}
+
+class PathBuilderKeyRolloverTest : public ::testing::Test {
+ public:
+  PathBuilderKeyRolloverTest() : signature_policy_(1024) {}
+
+  void SetUp() override {
+    std::vector<std::string> path;
+
+    ReadVerifyCertChainTestFromFile(
+        "net/data/verify_certificate_chain_unittest/key-rollover-oldchain.pem",
+        &path, &oldroot_, &time_);
+    ASSERT_EQ(2U, path.size());
+    target_ = CertThing::CreateFromCertificateCopy(path[0]);
+    oldintermediary_ = CertThing::CreateFromCertificateCopy(path[1]);
+    ASSERT_TRUE(target_);
+    ASSERT_TRUE(oldintermediary_);
+
+    ReadVerifyCertChainTestFromFile(
+        "net/data/verify_certificate_chain_unittest/"
+        "key-rollover-longrolloverchain.pem",
+        &path, &oldroot_, &time_);
+    ASSERT_EQ(4U, path.size());
+    newintermediary_ = CertThing::CreateFromCertificateCopy(path[1]);
+    newroot_ = CertThing::CreateFromCertificateCopy(path[2]);
+    newrootrollover_ = CertThing::CreateFromCertificateCopy(path[3]);
+    ASSERT_TRUE(newintermediary_);
+    ASSERT_TRUE(newroot_);
+    ASSERT_TRUE(newrootrollover_);
+  }
+
+ protected:
+  scoped_refptr<CertThing> target_, oldintermediary_, newintermediary_,
+      oldroot_, newroot_, newrootrollover_;
+
+  SimpleSignaturePolicy signature_policy_;
+  der::GeneralizedTime time_;
+};
+
+// Tests that if only the old root cert is trusted, the path builder can build a
+// path through the new intermediate and rollover cert to the old root.
+TEST_F(PathBuilderKeyRolloverTest, TestRolloverOnlyOldRootTrusted) {
+  // Only oldroot is trusted.
+  TrustStore trust_store;
+  trust_store.AddTrustedCertificate(oldroot_);
+
+  // Old intermediary cert is not provided, so the pathbuilder will need to go
+  // through the rollover cert.
+  CertVector sync_certs;
+  sync_certs.push_back(newintermediary_);
+  sync_certs.push_back(newrootrollover_);
+  StaticCertSource sync_cert_source(sync_certs);
+
+  CertPathBuilder::CertSources cert_sources;
+  cert_sources.push_back(&sync_cert_source);
+
+  scoped_refptr<CertThing> target_cert(target_);
+
+  CertPathBuilder::Result result;
+  CertPathBuilder path_builder(std::move(target_cert), cert_sources,
+                               trust_store, &signature_policy_, time_, &result);
+
+  TestCompletionCallback callback;
+  int rv = path_builder.Run(callback.callback());
+
+  DVLOG(1) << "path_builder.Run rv=" << ErrorToString(rv);
+
+  EXPECT_EQ(OK, rv);
+
+  if (rv == ERR_IO_PENDING) {
+    DVLOG(1) << "waiting for async completion...";
+    rv = callback.WaitForResult();
+    DVLOG(1) << "async rv=" << ErrorToString(rv);
+    EXPECT_EQ(OK, rv);
+  }
+
+  DumpPathBuilderResults(result);
+
+  // Path builder will first attempt: target -> newintermediary -> oldroot
+  // but it will fail since newintermediary is signed by newroot.
+  ASSERT_EQ(2U, result.paths.size());
+  EXPECT_EQ(ERR_CERT_AUTHORITY_INVALID, result.paths[0]->rv);
+  ASSERT_EQ(3U, result.paths[0]->path.size());
+  EXPECT_EQ(target_, result.paths[0]->path[0]);
+  EXPECT_EQ(newintermediary_, result.paths[0]->path[1]);
+  EXPECT_EQ(oldroot_, result.paths[0]->path[2]);
+
+  // Path builder will next attempt:
+  // target -> newintermediary -> newrootrollover -> oldroot
+  // which will succeed.
+  EXPECT_EQ(1U, result.best_result_index);
+  EXPECT_EQ(OK, result.paths[1]->rv);
+  ASSERT_EQ(4U, result.paths[1]->path.size());
+  EXPECT_EQ(target_, result.paths[1]->path[0]);
+  EXPECT_EQ(newintermediary_, result.paths[1]->path[1]);
+  EXPECT_EQ(newrootrollover_, result.paths[1]->path[2]);
+  EXPECT_EQ(oldroot_, result.paths[1]->path[3]);
+}
+
+// Tests that if both old and new roots are trusted it can build a path through
+// either.
+// XXX Once prioritzation is implemented, it should test that it always builds
+// the path through the new root.
+TEST_F(PathBuilderKeyRolloverTest, TestRolloverBothRootsTrusted) {
+  // Both oldroot and newroot are trusted.
+  TrustStore trust_store;
+  trust_store.AddTrustedCertificate(oldroot_);
+  trust_store.AddTrustedCertificate(newroot_);
+
+  // Both old and new intermediates + rollover cert are provided.
+  CertVector sync_certs;
+  sync_certs.push_back(oldintermediary_);
+  sync_certs.push_back(newintermediary_);
+  sync_certs.push_back(newrootrollover_);
+  StaticCertSource sync_cert_source(sync_certs);
+
+  CertPathBuilder::CertSources cert_sources;
+  cert_sources.push_back(&sync_cert_source);
+
+  scoped_refptr<CertThing> target_cert(target_);
+
+  CertPathBuilder::Result result;
+  CertPathBuilder path_builder(std::move(target_cert), cert_sources,
+                               trust_store, &signature_policy_, time_, &result);
+
+  TestCompletionCallback callback;
+  int rv = path_builder.Run(callback.callback());
+
+  DVLOG(1) << "path_builder.Run rv=" << ErrorToString(rv);
+
+  EXPECT_EQ(OK, rv);
+
+  if (rv == ERR_IO_PENDING) {
+    DVLOG(1) << "waiting for async completion...";
+    rv = callback.WaitForResult();
+    DVLOG(1) << "async rv=" << ErrorToString(rv);
+    EXPECT_EQ(OK, rv);
+  }
+
+  DumpPathBuilderResults(result);
+
+  // Path builder willattempt one of:
+  // target -> oldintermediary -> oldroot
+  // target -> newintermediary -> newroot
+  // either will succeed.
+  ASSERT_EQ(1U, result.paths.size());
+  EXPECT_EQ(OK, result.paths[0]->rv);
+  ASSERT_EQ(3U, result.paths[0]->path.size());
+  EXPECT_EQ(target_, result.paths[0]->path[0]);
+  // TODO: once we sort input certs on notbefore date, verify that it prefers
+  // newintermediary.
+  if (result.paths[0]->path[1] != newintermediary_) {
+    DVLOG(1) << "USED OLD";
+    EXPECT_EQ(oldintermediary_, result.paths[0]->path[1]);
+    EXPECT_EQ(oldroot_, result.paths[0]->path[2]);
+  } else {
+    DVLOG(1) << "USED NEW";
+    EXPECT_EQ(newintermediary_, result.paths[0]->path[1]);
+    EXPECT_EQ(newroot_, result.paths[0]->path[2]);
+  }
+}
+
+// Tests that the path builder doesn't build longer than necessary paths.
+TEST_F(PathBuilderKeyRolloverTest, TestRolloverLongChain) {
+  // Only oldroot is trusted.
+  TrustStore trust_store;
+  trust_store.AddTrustedCertificate(oldroot_);
+
+  // New intermediate and new root are provided synchronously.
+  CertVector sync_certs;
+  sync_certs.push_back(newintermediary_);
+  sync_certs.push_back(newroot_);
+  StaticCertSource sync_cert_source(sync_certs);
+
+  // Rollover cert is only provided asynchronously. This will force the
+  // pathbuilder to first try building a longer than necessary path.
+  CertVector async_certs;
+  async_certs.push_back(newrootrollover_);
+  AsyncStaticCertSource async_cert_source(async_certs);
+
+  CertPathBuilder::CertSources cert_sources;
+  cert_sources.push_back(&sync_cert_source);
+  cert_sources.push_back(&async_cert_source);
+
+  scoped_refptr<CertThing> target_cert(target_);
+
+  CertPathBuilder::Result result;
+  CertPathBuilder path_builder(std::move(target_cert), cert_sources,
+                               trust_store, &signature_policy_, time_, &result);
+
+  TestCompletionCallback callback;
+  int rv = path_builder.Run(callback.callback());
+
+  DVLOG(1) << "path_builder.Run rv=" << ErrorToString(rv);
+
+  EXPECT_EQ(ERR_IO_PENDING, rv);
+
+  if (rv == ERR_IO_PENDING) {
+    DVLOG(1) << "waiting for async completion...";
+    rv = callback.WaitForResult();
+    DVLOG(1) << "async rv=" << ErrorToString(rv);
+    EXPECT_EQ(OK, rv);
+  }
+
+  DumpPathBuilderResults(result);
+
+  ASSERT_EQ(3U, result.paths.size());
+
+  // Path builder will first attempt: target -> newintermediary -> oldroot
+  // but it will fail since newintermediary is signed by newroot.
+  EXPECT_EQ(ERR_CERT_AUTHORITY_INVALID, result.paths[0]->rv);
+  ASSERT_EQ(3U, result.paths[0]->path.size());
+  EXPECT_EQ(target_, result.paths[0]->path[0]);
+  EXPECT_EQ(newintermediary_, result.paths[0]->path[1]);
+  EXPECT_EQ(oldroot_, result.paths[0]->path[2]);
+
+  // Path builder will next attempt: target -> newintermediary -> newroot ->
+  // oldroot
+  // but it will fail since newroot is self-signed.
+  EXPECT_EQ(ERR_CERT_AUTHORITY_INVALID, result.paths[1]->rv);
+  ASSERT_EQ(4U, result.paths[1]->path.size());
+  EXPECT_EQ(target_, result.paths[1]->path[0]);
+  EXPECT_EQ(newintermediary_, result.paths[1]->path[1]);
+  EXPECT_EQ(newroot_, result.paths[1]->path[2]);
+  EXPECT_EQ(oldroot_, result.paths[1]->path[3]);
+
+  // Path builder will skip:
+  // target -> newintermediary -> newroot -> newrootrollover -> ...
+  // Since newroot and newrootrollover have the same Name+SAN+SPKI.
+
+  // Finally path builder will use:
+  // target -> newintermediary -> newrootrollover -> oldroot
+  EXPECT_EQ(2U, result.best_result_index);
+  EXPECT_EQ(OK, result.paths[2]->rv);
+  ASSERT_EQ(4U, result.paths[2]->path.size());
+  EXPECT_EQ(target_, result.paths[2]->path[0]);
+  EXPECT_EQ(newintermediary_, result.paths[2]->path[1]);
+  EXPECT_EQ(newrootrollover_, result.paths[2]->path[2]);
+  EXPECT_EQ(oldroot_, result.paths[2]->path[3]);
+}
+
+// If the target cert is a trust root, that alone is a valid path.
+TEST_F(PathBuilderKeyRolloverTest, TestEndEntityIsTrustRoot) {
+  // Trust newintermediary.
+  TrustStore trust_store;
+  trust_store.AddTrustedCertificate(newintermediary_);
+
+  // No certsources needed for this test.
+  CertPathBuilder::CertSources cert_sources;
+
+  // Newintermediary is also the target cert.
+  scoped_refptr<CertThing> target_cert(newintermediary_);
+
+  CertPathBuilder::Result result;
+  CertPathBuilder path_builder(std::move(target_cert), cert_sources,
+                               trust_store, &signature_policy_, time_, &result);
+
+  TestCompletionCallback callback;
+  int rv = path_builder.Run(callback.callback());
+
+  DVLOG(1) << "path_builder.Run rv=" << ErrorToString(rv);
+
+  EXPECT_EQ(OK, rv);
+
+  if (rv == ERR_IO_PENDING) {
+    DVLOG(1) << "waiting for async completion...";
+    rv = callback.WaitForResult();
+    DVLOG(1) << "async rv=" << ErrorToString(rv);
+    EXPECT_EQ(OK, rv);
+  }
+
+  DumpPathBuilderResults(result);
+
+  ASSERT_EQ(1U, result.paths.size());
+  EXPECT_EQ(OK, result.paths[0]->rv);
+  ASSERT_EQ(1U, result.paths[0]->path.size());
+  EXPECT_EQ(newintermediary_, result.paths[0]->path[0]);
+}
+
+// If target has same Name+SAN+SPKI as a necessary intermediate, test that a
+// path can still be built.
+TEST_F(PathBuilderKeyRolloverTest,
+       TestEndEntityHasSameNameAndSpkiAsIntermediate) {
+  // Trust oldroot.
+  TrustStore trust_store;
+  trust_store.AddTrustedCertificate(oldroot_);
+
+  // New root rollover is provided synchronously.
+  CertVector sync_certs;
+  sync_certs.push_back(newrootrollover_);
+  StaticCertSource sync_cert_source(sync_certs);
+
+  CertPathBuilder::CertSources cert_sources;
+  cert_sources.push_back(&sync_cert_source);
+
+  // Newroot is the target cert.
+  scoped_refptr<CertThing> target_cert(newroot_);
+
+  CertPathBuilder::Result result;
+  CertPathBuilder path_builder(std::move(target_cert), cert_sources,
+                               trust_store, &signature_policy_, time_, &result);
+
+  TestCompletionCallback callback;
+  int rv = path_builder.Run(callback.callback());
+
+  DVLOG(1) << "path_builder.Run rv=" << ErrorToString(rv);
+
+  EXPECT_EQ(OK, rv);
+
+  if (rv == ERR_IO_PENDING) {
+    DVLOG(1) << "waiting for async completion...";
+    rv = callback.WaitForResult();
+    DVLOG(1) << "async rv=" << ErrorToString(rv);
+    EXPECT_EQ(OK, rv);
+  }
+
+  DumpPathBuilderResults(result);
+
+  ASSERT_FALSE(result.paths.empty());
+  const CertPathBuilder::ResultPath* best_result =
+      result.paths[result.best_result_index].get();
+
+  EXPECT_EQ(OK, best_result->rv);
+  ASSERT_EQ(3U, best_result->path.size());
+  EXPECT_EQ(newroot_, best_result->path[0]);
+  EXPECT_EQ(newrootrollover_, best_result->path[1]);
+  EXPECT_EQ(oldroot_, best_result->path[2]);
+}
+
+// If target has same Name+SAN+SPKI as the trust root, test that a path can
+// still be built.
+TEST_F(PathBuilderKeyRolloverTest,
+       TestEndEntityHasSameNameAndSpkiAsTrustAnchor) {
+  // Trust newrootrollover.
+  TrustStore trust_store;
+  trust_store.AddTrustedCertificate(newrootrollover_);
+
+  // No certsources.
+  CertPathBuilder::CertSources cert_sources;
+
+  // Newroot is the target cert.
+  scoped_refptr<CertThing> target_cert(newroot_);
+
+  CertPathBuilder::Result result;
+  CertPathBuilder path_builder(std::move(target_cert), cert_sources,
+                               trust_store, &signature_policy_, time_, &result);
+
+  TestCompletionCallback callback;
+  int rv = path_builder.Run(callback.callback());
+
+  DVLOG(1) << "path_builder.Run rv=" << ErrorToString(rv);
+
+  EXPECT_EQ(OK, rv);
+
+  if (rv == ERR_IO_PENDING) {
+    DVLOG(1) << "waiting for async completion...";
+    rv = callback.WaitForResult();
+    DVLOG(1) << "async rv=" << ErrorToString(rv);
+    EXPECT_EQ(OK, rv);
+  }
+
+  DumpPathBuilderResults(result);
+
+  ASSERT_FALSE(result.paths.empty());
+  const CertPathBuilder::ResultPath* best_result =
+      result.paths[result.best_result_index].get();
+
+  EXPECT_EQ(OK, best_result->rv);
+  ASSERT_EQ(2U, best_result->path.size());
+  EXPECT_EQ(newroot_, best_result->path[0]);
+  EXPECT_EQ(newrootrollover_, best_result->path[1]);
+}
+
+// TODO:
+//  * cross signing ?
+//  * test of multiple trust anchor matches
+
+}  // namespace
+
+}  // namespace net