Certificate path builder for new certificate verification library

net/cert/internal/path_builder.cc

Index: net/cert/internal/path_builder.cc
diff --git a/net/cert/internal/path_builder.cc b/net/cert/internal/path_builder.cc
new file mode 100644
index 0000000000000000000000000000000000000000..863d8506b22d38673eaf18db08302484d934c34f
--- /dev/null
+++ b/net/cert/internal/path_builder.cc
@@ -0,0 +1,628 @@
+// 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 <set>
+#include <unordered_set>
+
+#include "base/callback_helpers.h"
+#include "base/memory/ptr_util.h"
+#include "net/base/net_errors.h"
+#include "net/cert/internal/cert_issuer_source.h"
+#include "net/cert/internal/parse_certificate.h"
+#include "net/cert/internal/parse_name.h"  // For CertDebugString.
+#include "net/cert/internal/signature_policy.h"
+#include "net/cert/internal/trust_store.h"
+#include "net/cert/internal/verify_certificate_chain.h"
+#include "net/cert/internal/verify_name_match.h"
+#include "net/der/parser.h"
+#include "net/der/tag.h"
+
+namespace net {
+
+namespace {
+
+using CertIssuerSources = std::vector<CertIssuerSource*>;
+
+// TODO(mattm): decide how much debug logging to keep.
+std::string CertDebugString(const ParsedCertificate* cert) {
+  RDNSequence subject, issuer;
+  std::string subject_str, issuer_str;
+  if (!ParseName(cert->tbs().subject_tlv, &subject) ||
+      !ConvertToRFC2253(subject, &subject_str))
+    subject_str = "???";
+  if (!ParseName(cert->tbs().issuer_tlv, &issuer) ||
+      !ConvertToRFC2253(issuer, &issuer_str))
+    issuer_str = "???";
+
+  return subject_str + "(" + issuer_str + ")";
+}
+
+// CertIssuersIter iterates through the intermediates from |cert_issuer_sources|
+// which may be issuers of |cert|.
+class CertIssuersIter {
+ public:
+  // Constructs the CertIssuersIter. |*cert_issuer_sources| must be valid for
+  // the lifetime of the CertIssuersIter.
+  CertIssuersIter(scoped_refptr<ParsedCertificate> cert,
+                  CertIssuerSources* cert_issuer_sources,
+                  const TrustStore& trust_store);
+
+  // Gets the next candidate issuer. If an issuer is ready synchronously, SYNC
+  // is returned and the cert is stored in |*out_cert|.  If an issuer is not
+  // ready, ASYNC is returned and |callback| will be called once |*out_cert| has
+  // been set. If |callback| is null, always completes synchronously.
+  //
+  // In either case, if all issuers have been exhausted, |*out_cert| is cleared.
+  CompletionStatus GetNextIssuer(scoped_refptr<ParsedCertificate>* out_cert,
+                                 const base::Closure& callback);
+
+  // Returns the |cert| for which issuers are being retrieved.
+  const ParsedCertificate* cert() const { return cert_.get(); }
+  scoped_refptr<ParsedCertificate> reference_cert() const { return cert_; }
+
+ private:
+  void GotAsyncCerts(CertIssuerSource::Request* request);
+
+  scoped_refptr<ParsedCertificate> cert_;
+  CertIssuerSources* cert_issuer_sources_;
+
+  // The list of issuers for |cert_|. This is added to incrementally (first
+  // synchronous results, then possibly multiple times as asynchronous results
+  // arrive.) The issuers may be re-sorted each time new issuers are added, but
+  // only the results from |cur_| onwards should be sorted, since the earlier
+  // results were already returned.
+  // Elements should not be removed from |issuers_| once added, since
+  // |present_issuers_| will point to data owned by the certs.
+  ParsedCertificateList issuers_;
+  // The index of the next cert in |issuers_| to return.
+  size_t cur_ = 0;
+  // Set of DER-encoded values for the certs in |issuers_|. Used to prevent
+  // duplicates. This is based on the full DER of the cert to allow different
+  // versions of the same certificate to be tried in different candidate paths.
+  // This points to data owned by |issuers_|.
+  std::unordered_set<base::StringPiece, base::StringPieceHash> present_issuers_;
+
+  // Tracks whether asynchronous requests have been made yet.
+  bool did_async_query_ = false;
+  // If asynchronous requests were made, how many of them are still outstanding?
+  size_t pending_async_results_;
+  // Owns the Request objects for any asynchronous requests so that they will be
+  // cancelled if CertIssuersIter is destroyed.
+  std::vector<std::unique_ptr<CertIssuerSource::Request>>
+      pending_async_requests_;
+
+  // When GetNextIssuer was called and returned asynchronously, |*out_cert_| is
+  // where the result will be stored, and |callback_| will be run when the
+  // result is ready.
+  scoped_refptr<ParsedCertificate>* out_cert_;
+  base::Closure callback_;
+
+  DISALLOW_COPY_AND_ASSIGN(CertIssuersIter);
+};
+
+CertIssuersIter::CertIssuersIter(scoped_refptr<ParsedCertificate> in_cert,
+                                 CertIssuerSources* cert_issuer_sources,
+                                 const TrustStore& trust_store)
+    : cert_(in_cert), cert_issuer_sources_(cert_issuer_sources) {
+  DVLOG(1) << "CertIssuersIter(" << CertDebugString(cert()) << ") created";
+  trust_store.FindTrustAnchorsByNormalizedName(in_cert->normalized_issuer(),
+                                               &issuers_);
+  // Insert matching roots into |present_issuers_| in case they also are
+  // returned by a CertIssuerSource. It is assumed
+  // FindTrustAnchorsByNormalizedName does not itself return dupes.
+  for (const auto& root : issuers_)
+    present_issuers_.insert(root->der_cert().AsStringPiece());
+
+  for (auto* cert_issuer_source : *cert_issuer_sources_) {
+    ParsedCertificateList new_issuers;
+    cert_issuer_source->SyncGetIssuersOf(cert(), &new_issuers);
+    for (scoped_refptr<ParsedCertificate>& issuer : new_issuers) {
+      if (present_issuers_.find(issuer->der_cert().AsStringPiece()) !=
+          present_issuers_.end())
+        continue;
+      present_issuers_.insert(issuer->der_cert().AsStringPiece());
+      issuers_.push_back(std::move(issuer));
+    }
+  }
+  // TODO(mattm): sort by notbefore, etc (eg if cert issuer matches a trust
+  // anchor subject (or is a trust anchor), that should be sorted higher too.
+  // See big list of possible sorting hints in RFC 4158.)
+  // (Update PathBuilderKeyRolloverTest.TestRolloverBothRootsTrusted once that
+  // is done)
+}
+
+CompletionStatus CertIssuersIter::GetNextIssuer(
+    scoped_refptr<ParsedCertificate>* out_cert,
+    const base::Closure& callback) {
+  // Should not be called again while already waiting for an async result.
+  DCHECK(callback_.is_null());
+
+  if (cur_ < issuers_.size()) {
+    DVLOG(1) << "CertIssuersIter(" << CertDebugString(cert())
+             << "): returning item " << cur_ << " of " << issuers_.size();
+    // Still have issuers that haven't been returned yet, return one of them.
+    // A reference to the returned issuer is retained, since |present_issuers_|
+    // points to data owned by it.
+    *out_cert = issuers_[cur_++];
+    return CompletionStatus::SYNC;
+  }
+  if (did_async_query_) {
+    if (pending_async_results_ == 0) {
+      DVLOG(1) << "CertIssuersIter(" << CertDebugString(cert())
+               << ") Reached the end of all available issuers.";
+      // Reached the end of all available issuers.
+      *out_cert = nullptr;
+      return CompletionStatus::SYNC;
+    }
+
+    DVLOG(1) << "CertIssuersIter(" << CertDebugString(cert())
+             << ") Still waiting for async results from other "
+                "CertIssuerSources.";
+    // Still waiting for async results from other CertIssuerSources.
+    out_cert_ = out_cert;
+    callback_ = callback;
+    return CompletionStatus::ASYNC;
+  }
+  // Reached the end of synchronously gathered issuers.
+
+  if (callback.is_null()) {
+    // Synchronous-only mode, don't try to query async sources.
+    *out_cert = nullptr;
+    return CompletionStatus::SYNC;
+  }
+
+  // Now issue request(s) for async ones (AIA, etc).
+  did_async_query_ = true;
+  pending_async_results_ = 0;
+  for (auto* cert_issuer_source : *cert_issuer_sources_) {
+    std::unique_ptr<CertIssuerSource::Request> request;
+    cert_issuer_source->AsyncGetIssuersOf(
+        cert(),
+        base::Bind(&CertIssuersIter::GotAsyncCerts, base::Unretained(this)),
+        &request);
+    if (request) {
+      DVLOG(1) << "AsyncGetIssuersOf(" << CertDebugString(cert())
+               << ") pending...";
+      pending_async_results_++;
+      pending_async_requests_.push_back(std::move(request));
+    }
+  }
+
+  if (pending_async_results_ == 0) {
+    DVLOG(1) << "CertIssuersIter(" << CertDebugString(cert())
+             << ") No cert sources have async results.";
+    // No cert sources have async results.
+    *out_cert = nullptr;
+    return CompletionStatus::SYNC;
+  }
+
+  DVLOG(1) << "CertIssuersIter(" << CertDebugString(cert())
+           << ") issued AsyncGetIssuersOf call(s) (n=" << pending_async_results_
+           << ")";
+  out_cert_ = out_cert;
+  callback_ = callback;
+  return CompletionStatus::ASYNC;
+}
+
+void CertIssuersIter::GotAsyncCerts(CertIssuerSource::Request* request) {
+  DVLOG(1) << "CertIssuersIter::GotAsyncCerts(" << CertDebugString(cert())
+           << ")";
+  while (true) {
+    scoped_refptr<ParsedCertificate> cert;
+    CompletionStatus status = request->GetNext(&cert);
+    if (!cert) {
+      if (status == CompletionStatus::SYNC) {
+        // Request is exhausted, no more results pending from that
+        // CertIssuerSource.
+        DCHECK_GT(pending_async_results_, 0U);
+        pending_async_results_--;
+      }
+      break;
+    }
+    DCHECK_EQ(status, CompletionStatus::SYNC);
+    if (present_issuers_.find(cert->der_cert().AsStringPiece()) !=
+        present_issuers_.end())
+      continue;
+    present_issuers_.insert(cert->der_cert().AsStringPiece());
+    issuers_.push_back(std::move(cert));
+  }
+
+  // TODO(mattm): re-sort remaining elements of issuers_ (remaining elements may
+  // be more than the ones just inserted, depending on |cur_| value).
+
+  // Notify that more results are available, if necessary.
+  if (!callback_.is_null()) {
+    if (cur_ < issuers_.size()) {
+      DVLOG(1) << "CertIssuersIter(" << CertDebugString(cert())
+               << "): async returning item " << cur_ << " of "
+               << issuers_.size();
+      *out_cert_ = std::move(issuers_[cur_++]);
+      base::ResetAndReturn(&callback_).Run();
+    } else if (pending_async_results_ == 0) {
+      DVLOG(1) << "CertIssuersIter(" << CertDebugString(cert())
+               << "): async returning empty result";
+      *out_cert_ = nullptr;
+      base::ResetAndReturn(&callback_).Run();
+    } else {
+      DVLOG(1) << "CertIssuersIter(" << CertDebugString(cert())
+               << "): empty result, but other async results "
+                  "pending, waiting..";
+    }
+  }
+}
+
+// CertIssuerIterPath tracks which certs are present in the path and prevents
+// paths from being built which repeat any certs (including different versions
+// of the same cert, based on Subject+SubjectAltName+SPKI).
+class CertIssuerIterPath {
+ public:
+  // Returns true if |cert| is already present in the path.
+  bool IsPresent(const ParsedCertificate* cert) const {
+    return present_certs_.find(GetKey(cert)) != present_certs_.end();
+  }
+
+  // Appends |cert_issuers_iter| to the path. The cert referred to by
+  // |cert_issuers_iter| must not be present in the path already.
+  void Append(std::unique_ptr<CertIssuersIter> cert_issuers_iter) {
+    bool added =
+        present_certs_.insert(GetKey(cert_issuers_iter->cert())).second;
+    DCHECK(added);
+    cur_path_.push_back(std::move(cert_issuers_iter));
+  }
+
+  // Pops the last CertIssuersIter off the path.
+  void Pop() {
+    size_t num_erased = present_certs_.erase(GetKey(cur_path_.back()->cert()));
+    DCHECK_EQ(num_erased, 1U);
+    cur_path_.pop_back();
+  }
+
+  // Copies the ParsedCertificate elements of the current path to |*out_path|.
+  void CopyPath(ParsedCertificateList* out_path) {
+    out_path->clear();
+    for (const auto& node : cur_path_)
+      out_path->push_back(node->reference_cert());
+  }
+
+  // Returns true if the path is empty.
+  bool Empty() const { return cur_path_.empty(); }
+
+  // Returns the last CertIssuersIter in the path.
+  CertIssuersIter* back() { return cur_path_.back().get(); }
+
+  std::string PathDebugString() {
+    std::string s;
+    for (const auto& node : cur_path_) {
+      if (!s.empty())
+        s += " <- ";
+      s += CertDebugString(node->cert());
+    }
+    return s;
+  }
+
+ private:
+  using Key =
+      std::tuple<base::StringPiece, base::StringPiece, base::StringPiece>;
+
+  static Key GetKey(const ParsedCertificate* cert) {
+    // TODO(mattm): ideally this would use a normalized version of
+    // SubjectAltName, but it's not that important just for LoopChecker.
+    //
+    // Note that subject_alt_names_extension().value will be empty if the cert
+    // had no SubjectAltName extension, so there is no need for a condition on
+    // has_subject_alt_names().
+    return Key(cert->normalized_subject().AsStringPiece(),
+               cert->subject_alt_names_extension().value.AsStringPiece(),
+               cert->tbs().spki_tlv.AsStringPiece());
+  }
+
+  std::vector<std::unique_ptr<CertIssuersIter>> cur_path_;
+
+  // This refers to data owned by |cur_path_|.
+  // TODO(mattm): use unordered_set. Requires making a hash function for Key.
+  std::set<Key> present_certs_;
+};
+
+}  // namespace
+
+// CertPathIter generates possible paths from |cert| to a trust anchor in
+// |trust_store|, using intermediates from the |cert_issuer_source| objects if
+// necessary.
+class CertPathIter {
+ public:
+  CertPathIter(scoped_refptr<ParsedCertificate> cert,
+               const TrustStore* trust_store);
+
+  // Adds a CertIssuerSource to provide intermediates for use in path building.
+  // The |*cert_issuer_source| must remain valid for the lifetime of the
+  // CertPathIter.
+  void AddCertIssuerSource(CertIssuerSource* cert_issuer_source);
+
+  // Gets the next candidate path. If a path is ready synchronously, SYNC is
+  // returned and the path is stored in |*path|.  If a path is not ready,
+  // ASYNC is returned and |callback| will be called once |*path| has been set.
+  // In either case, if all paths have been exhausted, |*path| is cleared.
+  CompletionStatus GetNextPath(ParsedCertificateList* path,
+                               const base::Closure& callback);
+
+ private:
+  enum State {
+    STATE_NONE,
+    STATE_GET_NEXT_ISSUER,
+    STATE_GET_NEXT_ISSUER_COMPLETE,
+    STATE_RETURN_A_PATH,
+    STATE_BACKTRACK,
+  };
+
+  CompletionStatus DoLoop(bool allow_async);
+
+  CompletionStatus DoGetNextIssuer(bool allow_async);
+  CompletionStatus DoGetNextIssuerComplete();
+  CompletionStatus DoBackTrack();
+
+  void HandleGotNextIssuer(void);
+
+  // Stores the next candidate issuer certificate, until it is used during the
+  // STATE_GET_NEXT_ISSUER_COMPLETE step.
+  scoped_refptr<ParsedCertificate> next_cert_;
+  // The current path being explored, made up of CertIssuerIters. Each node
+  // keeps track of the state of searching for issuers of that cert, so that
+  // when backtracking it can resume the search where it left off.
+  CertIssuerIterPath cur_path_;
+  // The CertIssuerSources for retrieving candidate issuers.
+  CertIssuerSources cert_issuer_sources_;
+  // The TrustStore for checking if a path ends in a trust anchor.
+  const TrustStore* trust_store_;
+  // The output variable for storing the next candidate path, which the client
+  // passes in to GetNextPath. Only used for a single path output.
+  ParsedCertificateList* out_path_;
+  // The callback to be called if an async lookup generated a candidate path.
+  base::Closure callback_;
+  // Current state of the state machine.
+  State next_state_;
+
+  DISALLOW_COPY_AND_ASSIGN(CertPathIter);
+};
+
+CertPathIter::CertPathIter(scoped_refptr<ParsedCertificate> cert,
+                           const TrustStore* trust_store)
+    : next_cert_(std::move(cert)),
+      trust_store_(trust_store),
+      next_state_(STATE_GET_NEXT_ISSUER_COMPLETE) {}
+
+void CertPathIter::AddCertIssuerSource(CertIssuerSource* cert_issuer_source) {
+  cert_issuer_sources_.push_back(cert_issuer_source);
+}
+
+CompletionStatus CertPathIter::GetNextPath(ParsedCertificateList* path,
+                                           const base::Closure& callback) {
+  out_path_ = path;
+  out_path_->clear();
+  CompletionStatus rv = DoLoop(!callback.is_null());
+  if (rv == CompletionStatus::ASYNC) {
+    callback_ = callback;
+  } else {
+    // Clear the reference to the output parameter as a precaution.
+    out_path_ = nullptr;
+  }
+  return rv;
+}
+
+CompletionStatus CertPathIter::DoLoop(bool allow_async) {
+  CompletionStatus result = CompletionStatus::SYNC;
+  do {
+    State state = next_state_;
+    next_state_ = STATE_NONE;
+    switch (state) {
+      case STATE_NONE:
+        NOTREACHED();
+        break;
+      case STATE_GET_NEXT_ISSUER:
+        result = DoGetNextIssuer(allow_async);
+        break;
+      case STATE_GET_NEXT_ISSUER_COMPLETE:
+        result = DoGetNextIssuerComplete();
+        break;
+      case STATE_RETURN_A_PATH:
+        // If the returned path did not verify, keep looking for other paths
+        // (the trust root is not part of cur_path_, so don't need to
+        // backtrack).
+        next_state_ = STATE_GET_NEXT_ISSUER;
+        result = CompletionStatus::SYNC;
+        break;
+      case STATE_BACKTRACK:
+        result = DoBackTrack();
+        break;
+    }
+  } while (result == CompletionStatus::SYNC && next_state_ != STATE_NONE &&
+           next_state_ != STATE_RETURN_A_PATH);
+
+  return result;
+}
+
+CompletionStatus CertPathIter::DoGetNextIssuer(bool allow_async) {
+  next_state_ = STATE_GET_NEXT_ISSUER_COMPLETE;
+  CompletionStatus rv = cur_path_.back()->GetNextIssuer(
+      &next_cert_, allow_async ? base::Bind(&CertPathIter::HandleGotNextIssuer,
+                                            base::Unretained(this))
+                               : base::Closure());
+  return rv;
+}
+
+CompletionStatus CertPathIter::DoGetNextIssuerComplete() {
+  if (next_cert_) {
+    // Skip this cert if it is already in the chain.
+    if (cur_path_.IsPresent(next_cert_.get())) {
+      next_state_ = STATE_GET_NEXT_ISSUER;
+      return CompletionStatus::SYNC;
+    }
+    // If the cert matches a trust root, this is a (possibly) complete path.
+    // Signal readiness. Don't add it to cur_path_, since that would cause an
+    // unnecessary lookup of issuers of the trust root.
+    if (trust_store_->IsTrustedCertificate(next_cert_.get())) {
+      DVLOG(1) << "CertPathIter IsTrustedCertificate("
+               << CertDebugString(next_cert_.get()) << ") = true";
+      next_state_ = STATE_RETURN_A_PATH;
+      cur_path_.CopyPath(out_path_);
+      out_path_->push_back(std::move(next_cert_));
+      next_cert_ = nullptr;
+      return CompletionStatus::SYNC;
+    }
+
+    cur_path_.Append(base::WrapUnique(new CertIssuersIter(
+        std::move(next_cert_), &cert_issuer_sources_, *trust_store_)));
+    next_cert_ = nullptr;
+    DVLOG(1) << "CertPathIter cur_path_ = " << cur_path_.PathDebugString();
+    // Continue descending the tree.
+    next_state_ = STATE_GET_NEXT_ISSUER;
+  } else {
+    // TODO(mattm): should also include such paths in CertPathBuilder::Result,
+    // maybe with a flag to enable it. Or use a visitor pattern so the caller
+    // can decide what to do with any failed paths.
+    // No more issuers for current chain, go back up and see if there are any
+    // more for the previous cert.
+    next_state_ = STATE_BACKTRACK;
+  }
+  return CompletionStatus::SYNC;
+}
+
+CompletionStatus CertPathIter::DoBackTrack() {
+  DVLOG(1) << "CertPathIter backtracking...";
+  cur_path_.Pop();
+  if (cur_path_.Empty()) {
+    // Exhausted all paths.
+    next_state_ = STATE_NONE;
+  } else {
+    // Continue exploring issuers of the previous path.
+    next_state_ = STATE_GET_NEXT_ISSUER;
+  }
+  return CompletionStatus::SYNC;
+}
+
+void CertPathIter::HandleGotNextIssuer(void) {
+  DCHECK(!callback_.is_null());
+  CompletionStatus rv = DoLoop(true /* allow_async */);
+  if (rv == CompletionStatus::SYNC) {
+    // Clear the reference to the output parameter as a precaution.
+    out_path_ = nullptr;
+    base::ResetAndReturn(&callback_).Run();
+  }
+}
+
+CertPathBuilder::ResultPath::ResultPath() = default;
+CertPathBuilder::ResultPath::~ResultPath() = default;
+CertPathBuilder::Result::Result() = default;
+CertPathBuilder::Result::~Result() = default;
+
+CertPathBuilder::CertPathBuilder(scoped_refptr<ParsedCertificate> cert,
+                                 const TrustStore* trust_store,
+                                 const SignaturePolicy* signature_policy,
+                                 const der::GeneralizedTime& time,
+                                 Result* result)
+    : cert_path_iter_(new CertPathIter(std::move(cert), trust_store)),
+      trust_store_(trust_store),
+      signature_policy_(signature_policy),
+      time_(time),
+      next_state_(STATE_NONE),
+      out_result_(result) {}
+
+CertPathBuilder::~CertPathBuilder() {}
+
+void CertPathBuilder::AddCertIssuerSource(
+    CertIssuerSource* cert_issuer_source) {
+  cert_path_iter_->AddCertIssuerSource(cert_issuer_source);
+}
+
+CompletionStatus CertPathBuilder::Run(const base::Closure& callback) {
+  DCHECK_EQ(STATE_NONE, next_state_);
+  next_state_ = STATE_GET_NEXT_PATH;
+  CompletionStatus rv = DoLoop(!callback.is_null());
+
+  if (rv == CompletionStatus::ASYNC)
+    callback_ = callback;
+
+  return rv;
+}
+
+CompletionStatus CertPathBuilder::DoLoop(bool allow_async) {
+  CompletionStatus result = CompletionStatus::SYNC;
+
+  do {
+    State state = next_state_;
+    next_state_ = STATE_NONE;
+    switch (state) {
+      case STATE_NONE:
+        NOTREACHED();
+        break;
+      case STATE_GET_NEXT_PATH:
+        result = DoGetNextPath(allow_async);
+        break;
+      case STATE_GET_NEXT_PATH_COMPLETE:
+        result = DoGetNextPathComplete();
+        break;
+    }
+  } while (result == CompletionStatus::SYNC && next_state_ != STATE_NONE);
+
+  return result;
+}
+
+CompletionStatus CertPathBuilder::DoGetNextPath(bool allow_async) {
+  next_state_ = STATE_GET_NEXT_PATH_COMPLETE;
+  CompletionStatus rv = cert_path_iter_->GetNextPath(
+      &next_path_, allow_async ? base::Bind(&CertPathBuilder::HandleGotNextPath,
+                                            base::Unretained(this))
+                               : base::Closure());
+  return rv;
+}
+
+void CertPathBuilder::HandleGotNextPath() {
+  DCHECK(!callback_.is_null());
+  CompletionStatus rv = DoLoop(true /* allow_async */);
+  if (rv == CompletionStatus::SYNC)
+    base::ResetAndReturn(&callback_).Run();
+}
+
+CompletionStatus CertPathBuilder::DoGetNextPathComplete() {
+  if (next_path_.empty()) {
+    // No more paths to check, signal completion.
+    next_state_ = STATE_NONE;
+    return CompletionStatus::SYNC;
+  }
+
+  bool verify_result = VerifyCertificateChainAssumingTrustedRoot(
+      next_path_, *trust_store_, signature_policy_, time_);
+  DVLOG(1) << "CertPathBuilder VerifyCertificateChain result = "
+           << verify_result;
+  AddResultPath(next_path_, verify_result);
+
+  if (verify_result) {
+    // Found a valid path, return immediately.
+    // TODO(mattm): add debug/test mode that tries all possible paths.
+    next_state_ = STATE_NONE;
+    return CompletionStatus::SYNC;
+  }
+
+  // Path did not verify. Try more paths. If there are no more paths, the result
+  // will be returned next time DoGetNextPathComplete is called with next_path_
+  // empty.
+  next_state_ = STATE_GET_NEXT_PATH;
+  return CompletionStatus::SYNC;
+}
+
+void CertPathBuilder::AddResultPath(const ParsedCertificateList& path,
+                                    bool is_success) {
+  std::unique_ptr<ResultPath> result_path(new ResultPath());
+  // TODO(mattm): better error reporting.
+  result_path->error = is_success ? OK : ERR_CERT_AUTHORITY_INVALID;
+  // TODO(mattm): set best_result_index based on number or severity of errors.
+  if (result_path->error == OK)
+    out_result_->best_result_index = out_result_->paths.size();
+  // TODO(mattm): add flag to only return a single path or all attempted paths?
+  result_path->path = path;
+  out_result_->paths.push_back(std::move(result_path));
+}
+
+}  // namespace net