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..c4e44fa67f5ffd9d838349afd187fae985672e9b
--- /dev/null
+++ b/net/cert/internal/path_builder_unittest.cc
@@ -0,0 +1,719 @@
+// 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 {
+
+// AsyncStaticCertsSource always returns its certs asynchronously.
+class AsyncStaticCertsSource : 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_;
+    AsyncStaticCertsSource* source_;
+
+    DISALLOW_COPY_AND_ASSIGN(StaticAsyncRequest);
+  };
+
+  AsyncStaticCertsSource() {}
+  ~AsyncStaticCertsSource() override {}
+
+  bool Init(std::vector<der::Input> certs) {
+    return static_cert_source_.Init(certs);
+  }
+  bool SyncGetIssuersOf(const CertThing& cert, CertVector* issuers) override {
+    return true;
+  }
+  int AsyncGetIssuersOf(const CertThing& cert,
+                        const IssuerCallback& issuers_callback,
+                        std::unique_ptr<Request>* out_req) override {
+    num_async_gets_++;
+    CertVector issuers;
+    if (!static_cert_source_.SyncGetIssuersOf(cert, &issuers))
+      return ERR_FAILED;
+    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:
+  StaticCertsSource 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,
+                                     std::string* 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 = block_data;
+    } 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,
+                                        std::string* result) {
+  return ReadTestPem("net/data/ssl/certificates/" + file_name, "CERTIFICATE",
+                     result);
+}
+
+std::string DumpCertChain(
+    const std::vector<std::unique_ptr<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:
+  std::string 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};
+};
+
+// Test that async cert queries are not made if the path can be successfully
+// built with synchronously available certs.
+TEST_F(PathBuilderMultiRootTest, TriesSyncFirst) {
+  StaticCertsSource sync_cert_source;
+  AsyncStaticCertsSource async_cert_source;
+
+  TrustStore trust_store;
+  ASSERT_TRUE(trust_store.AddTrustedCertificate(e_by_e_));
+
+  std::vector<der::Input> sync_certs;
+  sync_certs.push_back(der::Input(&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(der::Input(&b_by_c));
+  sync_certs.push_back(der::Input(&b_by_f_));
+  sync_certs.push_back(der::Input(&f_by_e_));
+  ASSERT_TRUE(sync_cert_source.Init(sync_certs));
+
+  std::vector<der::Input> async_certs;
+  async_certs.push_back(der::Input(&b_by_c_));
+  async_certs.push_back(der::Input(&c_by_e_));
+  ASSERT_TRUE(async_cert_source.Init(async_certs));
+
+  CertPathBuilder::CertSources cert_sources;
+  cert_sources.push_back(&async_cert_source);
+  cert_sources.push_back(&sync_cert_source);
+
+  std::unique_ptr<CertThing> target_cert(
+      CertThing::CreateFromCertificateCopy(a_by_b_));
+  ASSERT_TRUE(target_cert);
+
+  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) {
+  StaticCertsSource sync_cert_source;
+  AsyncStaticCertsSource async_cert_source1, async_cert_source2;
+
+  TrustStore trust_store;
+  ASSERT_TRUE(trust_store.AddTrustedCertificate(e_by_e_));
+
+  std::vector<der::Input> sync_certs;
+  sync_certs.push_back(der::Input(&a_by_b_));
+  sync_certs.push_back(der::Input(&b_by_c_));
+  sync_certs.push_back(der::Input(&b_by_f_));
+  ASSERT_TRUE(sync_cert_source.Init(sync_certs));
+
+  std::vector<der::Input> async_certs1;
+  async_certs1.push_back(der::Input(&c_by_e_));
+  ASSERT_TRUE(async_cert_source1.Init(async_certs1));
+
+  std::vector<der::Input> async_certs2;
+  async_certs2.push_back(der::Input(&f_by_e_));
+  ASSERT_TRUE(async_cert_source2.Init(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);
+
+  std::unique_ptr<CertThing> target_cert(
+      CertThing::CreateFromCertificateCopy(a_by_b_));
+  ASSERT_TRUE(target_cert);
+
+  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) {
+  StaticCertsSource sync_cert_source;
+
+  // Both D(D) and C(D) are trusted roots.
+  TrustStore trust_store;
+  ASSERT_TRUE(trust_store.AddTrustedCertificate(d_by_d_));
+  ASSERT_TRUE(trust_store.AddTrustedCertificate(c_by_d_));
+
+  // Certs A(B), B(C), and C(D) are all supplied.
+  std::vector<der::Input> sync_certs;
+  sync_certs.push_back(der::Input(&a_by_b_));
+  sync_certs.push_back(der::Input(&b_by_c_));
+  sync_certs.push_back(der::Input(&c_by_d_));
+  ASSERT_TRUE(sync_cert_source.Init(sync_certs));
+
+  CertPathBuilder::CertSources cert_sources;
+  cert_sources.push_back(&sync_cert_source);
+
+  std::unique_ptr<CertThing> target_cert(
+      CertThing::CreateFromCertificateCopy(a_by_b_));
+  ASSERT_TRUE(target_cert);
+
+  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) {
+  StaticCertsSource sync_cert_source;
+  AsyncStaticCertsSource async_cert_source;
+
+  // Only D(D) is a trusted root.
+  TrustStore trust_store;
+  ASSERT_TRUE(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.
+  std::vector<der::Input> sync_certs;
+  sync_certs.push_back(der::Input(&a_by_b_));
+  sync_certs.push_back(der::Input(&b_by_f_));
+  sync_certs.push_back(der::Input(&f_by_e_));
+  ASSERT_TRUE(sync_cert_source.Init(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.
+  std::vector<der::Input> async_certs;
+  async_certs.push_back(der::Input(&b_by_c_));
+  async_certs.push_back(der::Input(&c_by_d_));
+  ASSERT_TRUE(async_cert_source.Init(async_certs));
+
+  CertPathBuilder::CertSources cert_sources;
+  cert_sources.push_back(&sync_cert_source);
+  cert_sources.push_back(&async_cert_source);
+
+  std::unique_ptr<CertThing> target_cert(
+      CertThing::CreateFromCertificateCopy(a_by_b_));
+  ASSERT_TRUE(target_cert);
+
+  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(der::Input(&a_by_b_),
+            result.paths[result.best_result_index]->path[0]->der_cert());
+  EXPECT_EQ(der::Input(&b_by_c_),
+            result.paths[result.best_result_index]->path[1]->der_cert());
+  EXPECT_EQ(der::Input(&c_by_d_),
+            result.paths[result.best_result_index]->path[2]->der_cert());
+  EXPECT_EQ(der::Input(&d_by_d_),
+            result.paths[result.best_result_index]->path[3]->der_cert());
+}
+
+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_ = path[0];
+    oldintermediary_ = path[1];
+
+    ReadVerifyCertChainTestFromFile(
+        "net/data/verify_certificate_chain_unittest/"
+        "key-rollover-longrolloverchain.pem",
+        &path, &oldroot_, &time_);
+    ASSERT_EQ(4U, path.size());
+    newintermediary_ = path[1];
+    newroot_ = path[2];
+    newrootrollover_ = path[3];
+  }
+
+ protected:
+  std::string 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) {
+  StaticCertsSource sync_cert_source;
+
+  // Only oldroot is trusted.
+  TrustStore trust_store;
+  ASSERT_TRUE(trust_store.AddTrustedCertificate(oldroot_));
+
+  // Old intermediary cert is not provided, so the pathbuilder will need to go
+  // through the rollover cert.
+  std::vector<der::Input> sync_certs;
+  sync_certs.push_back(der::Input(&newintermediary_));
+  sync_certs.push_back(der::Input(&newrootrollover_));
+  ASSERT_TRUE(sync_cert_source.Init(sync_certs));
+
+  CertPathBuilder::CertSources cert_sources;
+  cert_sources.push_back(&sync_cert_source);
+
+  std::unique_ptr<CertThing> target_cert(
+      CertThing::CreateFromCertificateCopy(target_));
+  ASSERT_TRUE(target_cert);
+
+  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(der::Input(&target_), result.paths[0]->path[0]->der_cert());
+  EXPECT_EQ(der::Input(&newintermediary_),
+            result.paths[0]->path[1]->der_cert());
+  EXPECT_EQ(der::Input(&oldroot_), result.paths[0]->path[2]->der_cert());
+
+  // 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(der::Input(&target_), result.paths[1]->path[0]->der_cert());
+  EXPECT_EQ(der::Input(&newintermediary_),
+            result.paths[1]->path[1]->der_cert());
+  EXPECT_EQ(der::Input(&newrootrollover_),
+            result.paths[1]->path[2]->der_cert());
+  EXPECT_EQ(der::Input(&oldroot_), result.paths[1]->path[3]->der_cert());
+}
+
+// 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) {
+  StaticCertsSource sync_cert_source;
+
+  // Both oldroot and newroot are trusted.
+  TrustStore trust_store;
+  ASSERT_TRUE(trust_store.AddTrustedCertificate(oldroot_));
+  ASSERT_TRUE(trust_store.AddTrustedCertificate(newroot_));
+
+  // Both old and new intermediates + rollover cert are provided.
+  std::vector<der::Input> sync_certs;
+  sync_certs.push_back(der::Input(&oldintermediary_));
+  sync_certs.push_back(der::Input(&newintermediary_));
+  sync_certs.push_back(der::Input(&newrootrollover_));
+  ASSERT_TRUE(sync_cert_source.Init(sync_certs));
+
+  CertPathBuilder::CertSources cert_sources;
+  cert_sources.push_back(&sync_cert_source);
+
+  std::unique_ptr<CertThing> target_cert(
+      CertThing::CreateFromCertificateCopy(target_));
+  ASSERT_TRUE(target_cert);
+
+  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(der::Input(&target_), result.paths[0]->path[0]->der_cert());
+  // TODO: once we sort input certs on notbefore date, verify that it prefers
+  // newintermediary.
+  if (result.paths[0]->path[1]->der_cert() != der::Input(&newintermediary_)) {
+    DVLOG(1) << "USED OLD";
+    EXPECT_EQ(der::Input(&oldintermediary_),
+              result.paths[0]->path[1]->der_cert());
+    EXPECT_EQ(der::Input(&oldroot_), result.paths[0]->path[2]->der_cert());
+  } else {
+    DVLOG(1) << "USED NEW";
+    EXPECT_EQ(der::Input(&newintermediary_),
+              result.paths[0]->path[1]->der_cert());
+    EXPECT_EQ(der::Input(&newroot_), result.paths[0]->path[2]->der_cert());
+  }
+}
+
+// Tests that the path builder doesn't build longer than necessary paths.
+// TODO: currently it does. fix that.
+TEST_F(PathBuilderKeyRolloverTest, TestRolloverLongChain) {
+  StaticCertsSource sync_cert_source;
+  AsyncStaticCertsSource async_cert_source;
+
+  // Only oldroot is trusted.
+  TrustStore trust_store;
+  ASSERT_TRUE(trust_store.AddTrustedCertificate(oldroot_));
+
+  // New intermediate and new root are provided synchronously.
+  std::vector<der::Input> sync_certs;
+  sync_certs.push_back(der::Input(&newintermediary_));
+  sync_certs.push_back(der::Input(&newroot_));
+  ASSERT_TRUE(sync_cert_source.Init(sync_certs));
+
+  // Rollover cert is only provided asynchronously. This will force the
+  // pathbuilder to first try building a longer than necessary path.
+  std::vector<der::Input> async_certs;
+  async_certs.push_back(der::Input(&newrootrollover_));
+  ASSERT_TRUE(async_cert_source.Init(async_certs));
+
+  CertPathBuilder::CertSources cert_sources;
+  cert_sources.push_back(&sync_cert_source);
+  cert_sources.push_back(&async_cert_source);
+
+  std::unique_ptr<CertThing> target_cert(
+      CertThing::CreateFromCertificateCopy(target_));
+  ASSERT_TRUE(target_cert);
+
+  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(der::Input(&target_), result.paths[0]->path[0]->der_cert());
+  EXPECT_EQ(der::Input(&newintermediary_),
+            result.paths[0]->path[1]->der_cert());
+  EXPECT_EQ(der::Input(&oldroot_), result.paths[0]->path[2]->der_cert());
+
+  // 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(der::Input(&target_), result.paths[1]->path[0]->der_cert());
+  EXPECT_EQ(der::Input(&newintermediary_),
+            result.paths[1]->path[1]->der_cert());
+  EXPECT_EQ(der::Input(&newroot_), result.paths[1]->path[2]->der_cert());
+  EXPECT_EQ(der::Input(&oldroot_), result.paths[1]->path[3]->der_cert());
+
+  // Finally path builder will use:
+  // target -> newintermediary -> newroot -> newrootrollover -> oldroot
+  // This path is valid, but longer than necessary (no need for newroot to
+  // be in there).
+  //
+  // TODO: once LoopChecker is keyed on Name + SAN + SPKI, it should skip
+  // that path and use:
+  // target -> newintermediary -> newrootrollover -> oldroot
+  EXPECT_EQ(2U, result.best_result_index);
+  EXPECT_EQ(OK, result.paths[2]->rv);
+  ASSERT_EQ(5U, result.paths[2]->path.size());
+  EXPECT_EQ(der::Input(&target_), result.paths[2]->path[0]->der_cert());
+  EXPECT_EQ(der::Input(&newintermediary_),
+            result.paths[2]->path[1]->der_cert());
+  EXPECT_EQ(der::Input(&newroot_), result.paths[2]->path[2]->der_cert());
+  EXPECT_EQ(der::Input(&newrootrollover_),
+            result.paths[2]->path[3]->der_cert());
+  EXPECT_EQ(der::Input(&oldroot_), result.paths[2]->path[4]->der_cert());
+}
+
+// TODO:
+//  * cross signing ?
+//  * test of multiple trust anchor matches
+
+}  // namespace
+
+}  // namespace net