Allow the TrustStore interface to return matching intermediates, and identify distrusted certs.

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
index 291bcf5360643b4a7a76bc85273fe430c41cae70..7f4284b2f0fc85226aa44ba4d1f138db80c7eb07 100644
--- a/net/cert/internal/path_builder.cc
+++ b/net/cert/internal/path_builder.cc
@@ -40,24 +40,36 @@ std::string CertDebugString(const ParsedCertificate* cert) {
   return subject_str + "(" + issuer_str + ")";
 }
 
-// This structure contains either a ParsedCertificate or a TrustAnchor. It is
-// used to describe the result of getting a certificate's issuer, which may
-// either be another certificate, or a trust anchor.
-struct CertificateOrTrustAnchor {
-  CertificateOrTrustAnchor() {}
-
-  explicit CertificateOrTrustAnchor(scoped_refptr<ParsedCertificate> cert)
-      : cert(std::move(cert)) {}
+// This structure describes a certificate and its trust level. Note that |cert|
+// may be null to indicate an "empty" entry.
+struct IssuerEntry {
+  scoped_refptr<ParsedCertificate> cert;
+  CertificateTrust trust;
+};
 
-  explicit CertificateOrTrustAnchor(scoped_refptr<TrustAnchor> anchor)
-      : anchor(std::move(anchor)) {}
+// Simple comparator of IssuerEntry that defines the order in which issuers
+// should be explored. It puts trust anchors ahead of unknown or distrusted
+// ones.
+struct IssuerEntryComparator {
+  bool operator()(const IssuerEntry& issuer1, const IssuerEntry& issuer2) {
+    return CertificateTrustToOrder(issuer1.trust) <
+           CertificateTrustToOrder(issuer2.trust);
+  }
 
-  bool IsTrustAnchor() const { return anchor.get() != nullptr; }
-  bool IsCertificate() const { return cert.get() != nullptr; }
-  bool IsEmpty() const { return !IsTrustAnchor() && !IsCertificate(); }
+  static int CertificateTrustToOrder(const CertificateTrust& trust) {
+    switch (trust.type) {
+      case CertificateTrustType::TRUSTED_ANCHOR:
+      case CertificateTrustType::TRUSTED_ANCHOR_WITH_CONSTRAINTS:
+        return 1;
+      case CertificateTrustType::UNSPECIFIED:
+        return 2;
+      case CertificateTrustType::DISTRUSTED:
+        return 4;
+    }
 
-  scoped_refptr<ParsedCertificate> cert;
-  scoped_refptr<TrustAnchor> anchor;
+    NOTREACHED();
+    return 5;
+  }
 };
 
 // CertIssuersIter iterates through the intermediates from |cert_issuer_sources|
@@ -72,7 +84,7 @@ class CertIssuersIter {
 
   // Gets the next candidate issuer, or clears |*out| when all issuers have been
   // exhausted.
-  void GetNextIssuer(CertificateOrTrustAnchor* out);
+  void GetNextIssuer(IssuerEntry* out);
 
   // Returns the |cert| for which issuers are being retrieved.
   const ParsedCertificate* cert() const { return cert_.get(); }
@@ -85,15 +97,14 @@ class CertIssuersIter {
   // Returns true if |issuers_| contains unconsumed certificates.
   bool HasCurrentIssuer() const { return cur_issuer_ < issuers_.size(); }
 
+  // Sorts the remaining entries in |issuers_| in the preferred order to
+  // explore. Does not change the ordering for indices before cur_issuer_.
+  void SortRemainingIssuers();
+
   scoped_refptr<ParsedCertificate> cert_;
   CertIssuerSources* cert_issuer_sources_;
   const TrustStore* trust_store_;
 
-  // The list of trust anchors that match the issuer name for |cert_|.
-  TrustAnchors anchors_;
-  // The index of the next trust anchor in |anchors_| to return.
-  size_t cur_anchor_ = 0;
-
   // 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
@@ -101,9 +112,12 @@ class CertIssuersIter {
   // 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_;
+  std::vector<IssuerEntry> issuers_;
   // The index of the next cert in |issuers_| to return.
   size_t cur_issuer_ = 0;
+  // Set to true whenever new issuers are appended at the end, to indicate the
+  // ordering needs to be checked.
+  bool issuers_needs_sort_ = false;
 
   // 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
@@ -133,36 +147,17 @@ CertIssuersIter::CertIssuersIter(scoped_refptr<ParsedCertificate> in_cert,
   DVLOG(1) << "CertIssuersIter(" << CertDebugString(cert()) << ") created";
 }
 
-void CertIssuersIter::GetNextIssuer(CertificateOrTrustAnchor* out) {
+void CertIssuersIter::GetNextIssuer(IssuerEntry* out) {
   if (!did_initial_query_) {
     did_initial_query_ = true;
-    trust_store_->FindTrustAnchorsForCert(cert_, &anchors_);
-
     for (auto* cert_issuer_source : *cert_issuer_sources_) {
       ParsedCertificateList new_issuers;
       cert_issuer_source->SyncGetIssuersOf(cert(), &new_issuers);
       AddIssuers(std::move(new_issuers));
     }
-    DVLOG(1) << anchors_.size() << " sync anchors, " << issuers_.size()
-             << " sync issuers";
-    // 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)
-  }
-
-  // Return possible trust anchors first.
-  if (cur_anchor_ < anchors_.size()) {
-    DVLOG(1) << "CertIssuersIter(" << CertDebugString(cert())
-             << "): returning anchor " << cur_anchor_ << " of "
-             << anchors_.size();
-    // Still have anchors that haven't been returned yet, return one of them.
-    *out = CertificateOrTrustAnchor(anchors_[cur_anchor_++]);
-    return;
   }
 
-  // If there aren't any issuers left, block until async results are ready.
+  // If there aren't any issuers, block until async results are ready.
   if (!HasCurrentIssuer()) {
     if (!did_async_issuer_query_) {
       // Now issue request(s) for async ones (AIA, etc).
@@ -186,20 +181,22 @@ void CertIssuersIter::GetNextIssuer(CertificateOrTrustAnchor* out) {
   }
 
   if (HasCurrentIssuer()) {
+    SortRemainingIssuers();
+
     DVLOG(1) << "CertIssuersIter(" << CertDebugString(cert())
              << "): returning issuer " << cur_issuer_ << " 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 = CertificateOrTrustAnchor(issuers_[cur_issuer_++]);
+    // Still have issuers that haven't been returned yet, return the highest
+    // priority one (head of remaining list). A reference to the returned issuer
+    // is retained, since |present_issuers_| points to data owned by it.
+    *out = issuers_[cur_issuer_++];
     return;
   }
 
   DVLOG(1) << "CertIssuersIter(" << CertDebugString(cert())
            << ") Reached the end of all available issuers.";
   // Reached the end of all available issuers.
-  *out = CertificateOrTrustAnchor();
+  *out = IssuerEntry();
 }
 
 void CertIssuersIter::AddIssuers(ParsedCertificateList new_issuers) {
@@ -208,7 +205,14 @@ void CertIssuersIter::AddIssuers(ParsedCertificateList new_issuers) {
         present_issuers_.end())
       continue;
     present_issuers_.insert(issuer->der_cert().AsStringPiece());
-    issuers_.push_back(std::move(issuer));
+
+    // Look up the trust for this issuer.
+    IssuerEntry entry;
+    entry.cert = std::move(issuer);
+    trust_store_->GetTrust(entry.cert, &entry.trust);
+
+    issuers_.push_back(std::move(entry));
+    issuers_needs_sort_ = true;
   }
 }
 
@@ -227,6 +231,21 @@ void CertIssuersIter::DoAsyncIssuerQuery() {
   }
 }
 
+void CertIssuersIter::SortRemainingIssuers() {
+  // 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)
+  if (!issuers_needs_sort_)
+    return;
+
+  std::stable_sort(issuers_.begin() + cur_issuer_, issuers_.end(),
+                   IssuerEntryComparator());
+
+  issuers_needs_sort_ = false;
+}
+
 // 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).
@@ -305,7 +324,7 @@ CertPath::CertPath() = default;
 CertPath::~CertPath() = default;
 
 void CertPath::Clear() {
-  trust_anchor = nullptr;
+  last_cert_trust = CertificateTrust::ForUnspecified();
   certs.clear();
 }
 
@@ -313,6 +332,23 @@ bool CertPath::IsEmpty() const {
   return certs.empty();
 }
 
+const ParsedCertificate* CertPath::GetTrustedCert() const {
+  if (certs.empty())
+    return nullptr;
+
+  switch (last_cert_trust.type) {
+    case CertificateTrustType::TRUSTED_ANCHOR:
+    case CertificateTrustType::TRUSTED_ANCHOR_WITH_CONSTRAINTS:
+      return certs.back().get();
+    case CertificateTrustType::UNSPECIFIED:
+    case CertificateTrustType::DISTRUSTED:
+      return nullptr;
+  }
+
+  NOTREACHED();
+  return nullptr;
+}
+
 // CertPathIter generates possible paths from |cert| to a trust anchor in
 // |trust_store|, using intermediates from the |cert_issuer_source| objects if
 // necessary.
@@ -345,7 +381,7 @@ class CertPathIter {
 
   // Stores the next candidate issuer, until it is used during the
   // STATE_GET_NEXT_ISSUER_COMPLETE step.
-  CertificateOrTrustAnchor next_issuer_;
+  IssuerEntry next_issuer_;
   // 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.
@@ -365,9 +401,11 @@ class CertPathIter {
 
 CertPathIter::CertPathIter(scoped_refptr<ParsedCertificate> cert,
                            const TrustStore* trust_store)
-    : next_issuer_(std::move(cert)),
-      trust_store_(trust_store),
-      next_state_(STATE_GET_NEXT_ISSUER_COMPLETE) {}
+    : trust_store_(trust_store), next_state_(STATE_GET_NEXT_ISSUER_COMPLETE) {
+  // Initialize |next_issuer_| to the target certificate.
+  next_issuer_.cert = std::move(cert);
+  trust_store_->GetTrust(next_issuer_.cert, &next_issuer_.trust);
+}
 
 void CertPathIter::AddCertIssuerSource(CertIssuerSource* cert_issuer_source) {
   cert_issuer_sources_.push_back(cert_issuer_source);
@@ -406,42 +444,57 @@ void CertPathIter::GetNextPath(CertPath* path) {
 }
 
 void CertPathIter::DoGetNextIssuer() {
-  next_state_ = STATE_GET_NEXT_ISSUER_COMPLETE;
-  cur_path_.back()->GetNextIssuer(&next_issuer_);
+  if (cur_path_.Empty()) {
+    // Exhausted all paths.
+    next_state_ = STATE_NONE;
+  } else {
+    next_state_ = STATE_GET_NEXT_ISSUER_COMPLETE;
+    cur_path_.back()->GetNextIssuer(&next_issuer_);
+  }
 }
 
 void CertPathIter::DoGetNextIssuerComplete() {
-  // If the issuer is a trust anchor signal readiness.
-  if (next_issuer_.IsTrustAnchor()) {
-    DVLOG(1) << "CertPathIter got anchor("
-             << CertDebugString(next_issuer_.anchor->cert().get());
-    next_state_ = STATE_RETURN_A_PATH;
-    cur_path_.CopyPath(&out_path_->certs);
-    out_path_->trust_anchor = std::move(next_issuer_.anchor);
-    next_issuer_ = CertificateOrTrustAnchor();
-    return;
-  }
-
-  if (next_issuer_.IsCertificate()) {
-    // Skip this cert if it is already in the chain.
-    if (cur_path_.IsPresent(next_issuer_.cert.get())) {
-      next_state_ = STATE_GET_NEXT_ISSUER;
-      return;
-    }
-
-    cur_path_.Append(base::MakeUnique<CertIssuersIter>(
-        std::move(next_issuer_.cert), &cert_issuer_sources_, trust_store_));
-    next_issuer_ = CertificateOrTrustAnchor();
-    DVLOG(1) << "CertPathIter cur_path_ = " << cur_path_.PathDebugString();
-    // Continue descending the tree.
-    next_state_ = STATE_GET_NEXT_ISSUER;
-  } else {
+  if (!next_issuer_.cert) {
     // 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;
+  }
+
+  switch (next_issuer_.trust.type) {
+    // If the trust for this issuer is "known" (either becuase it is distrusted,
+    // or because it is trusted) then stop building and return the path.
+    case CertificateTrustType::DISTRUSTED:
+    case CertificateTrustType::TRUSTED_ANCHOR:
+    case CertificateTrustType::TRUSTED_ANCHOR_WITH_CONSTRAINTS: {
+      // If the issuer has a known trust level, can stop building the path.
+      DVLOG(1) << "CertPathIter got anchor: "
+               << CertDebugString(next_issuer_.cert.get());
+      next_state_ = STATE_RETURN_A_PATH;
+      cur_path_.CopyPath(&out_path_->certs);
+      out_path_->certs.push_back(std::move(next_issuer_.cert));
+      out_path_->last_cert_trust = next_issuer_.trust;
+      next_issuer_ = IssuerEntry();
+      break;
+    }
+    case CertificateTrustType::UNSPECIFIED: {
+      // Skip this cert if it is already in the chain.
+      if (cur_path_.IsPresent(next_issuer_.cert.get())) {
+        next_state_ = STATE_GET_NEXT_ISSUER;
+        break;
+      }
+
+      cur_path_.Append(base::MakeUnique<CertIssuersIter>(
+          std::move(next_issuer_.cert), &cert_issuer_sources_, trust_store_));
+      next_issuer_ = IssuerEntry();
+      DVLOG(1) << "CertPathIter cur_path_ = " << cur_path_.PathDebugString();
+      // Continue descending the tree.
+      next_state_ = STATE_GET_NEXT_ISSUER;
+      break;
+    }
   }
 }
 
@@ -461,8 +514,7 @@ CertPathBuilder::ResultPath::ResultPath() = default;
 CertPathBuilder::ResultPath::~ResultPath() = default;
 
 bool CertPathBuilder::ResultPath::IsValid() const {
-  return !path.certs.empty() && path.trust_anchor &&
-         !errors.ContainsHighSeverityErrors();
+  return path.GetTrustedCert() && !errors.ContainsHighSeverityErrors();
 }
 
 CertPathBuilder::Result::Result() = default;
@@ -488,7 +540,7 @@ bool CertPathBuilder::Result::HasValidPath() const {
 }
 
 CertPathBuilder::CertPathBuilder(scoped_refptr<ParsedCertificate> cert,
-                                 const TrustStore* trust_store,
+                                 TrustStore* trust_store,
                                  const SignaturePolicy* signature_policy,
                                  const der::GeneralizedTime& time,
                                  KeyPurpose key_purpose,
@@ -498,7 +550,10 @@ CertPathBuilder::CertPathBuilder(scoped_refptr<ParsedCertificate> cert,
       time_(time),
       key_purpose_(key_purpose),
       next_state_(STATE_NONE),
-      out_result_(result) {}
+      out_result_(result) {
+  // The TrustStore also implements the CertIssuerSource interface.
+  AddCertIssuerSource(trust_store);
+}
 
 CertPathBuilder::~CertPathBuilder() {}
 
@@ -543,13 +598,15 @@ void CertPathBuilder::DoGetNextPathComplete() {
 
   // Verify the entire certificate chain.
   auto result_path = base::MakeUnique<ResultPath>();
-  bool verify_result = VerifyCertificateChain(
-      next_path_.certs, next_path_.trust_anchor.get(), signature_policy_, time_,
-      key_purpose_, &result_path->errors);
+  VerifyCertificateChain(next_path_.certs, next_path_.last_cert_trust,
+                         signature_policy_, time_, key_purpose_,
+                         &result_path->errors);
+  bool verify_result = !result_path->errors.ContainsHighSeverityErrors();
+
   DVLOG(1) << "CertPathBuilder VerifyCertificateChain result = "
-           << verify_result;
+           << verify_result << "\n"
+           << result_path->errors.ToDebugString(next_path_.certs);
   result_path->path = next_path_;
-  DCHECK_EQ(verify_result, !result_path->errors.ContainsHighSeverityErrors());
   AddResultPath(std::move(result_path));
 
   if (verify_result) {