Allow for the path builder to limit the number of valid paths.
The existing behaviour of "explore_all_paths" is preserved with
the valid path limits of 0 (unlimited) and 1 (stop after first
valid path). This allows for a later change for portable verify
API to simply specify a desired limit.
SetExploreAllPaths could eventually be deprecated.
Bug: 660
Change-Id: I7a75acbfbee135a1368fe6716eb460af41cdb590
Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/64727
Reviewed-by: David Benjamin <davidben@google.com>
Reviewed-by: Matt Mueller <mattm@google.com>
Commit-Queue: Bob Beck <bbe@google.com>
diff --git a/pki/path_builder.cc b/pki/path_builder.cc
index f89576e..6aa42e7 100644
--- a/pki/path_builder.cc
+++ b/pki/path_builder.cc
@@ -787,8 +787,12 @@
max_path_building_depth_ = limit;
}
+void CertPathBuilder::SetValidPathLimit(size_t limit) {
+ valid_path_limit_ = limit;
+}
+
void CertPathBuilder::SetExploreAllPaths(bool explore_all_paths) {
- explore_all_paths_ = explore_all_paths;
+ valid_path_limit_ = explore_all_paths ? 0 : 1;
}
CertPathBuilder::Result CertPathBuilder::Run() {
@@ -853,10 +857,13 @@
AddResultPath(std::move(result_path));
- if (path_is_good && !explore_all_paths_) {
- out_result_.iteration_count = iteration_count;
- // Found a valid path, return immediately.
- return std::move(out_result_);
+ if (path_is_good) {
+ valid_path_count_++;
+ if (valid_path_limit_ > 0 && valid_path_count_ == valid_path_limit_) {
+ out_result_.iteration_count = iteration_count;
+ // Found enough paths, return immediately.
+ return std::move(out_result_);
+ }
}
// Path did not verify. Try more paths.
}
diff --git a/pki/path_builder.h b/pki/path_builder.h
index 325477b..05999b0 100644
--- a/pki/path_builder.h
+++ b/pki/path_builder.h
@@ -213,10 +213,16 @@
// to root. Setting |limit| to 0 disables this limit, which is the default.
void SetDepthLimit(uint32_t limit);
- // If |explore_all_paths| is false (the default), path building will stop as
- // soon as a valid path is found. If |explore_all_paths| is true, path
- // building will continue until all possible paths have been exhausted (or
- // iteration limit / deadline is exceeded).
+ // Set the limit of valid paths returned by the path builder to |limit|. If
+ // |limit| is non zero, path building will stop once |limit| valid paths have
+ // been found. Setting |limit| to 0 disables the limit, meaning path building
+ // will continue until all possible paths have been exhausted (or iteration
+ // limit / deadline is exceeded). The default limit is 1.
+ void SetValidPathLimit(size_t limit);
+
+ // If |explore_all_paths| is false, this is equivalent to calling
+ // SetValidPathLimit(1). If |explore_all_paths| is true, this is equivalent to
+ // calling SetValidPathLimit(0).
void SetExploreAllPaths(bool explore_all_paths);
// Executes verification of the target certificate.
@@ -241,7 +247,8 @@
const InitialAnyPolicyInhibit initial_any_policy_inhibit_;
uint32_t max_iteration_count_ = 0;
uint32_t max_path_building_depth_ = 0;
- bool explore_all_paths_ = false;
+ size_t valid_path_limit_ = 1;
+ size_t valid_path_count_ = 0;
};
} // namespace bssl
diff --git a/pki/path_builder_unittest.cc b/pki/path_builder_unittest.cc
index c76670d..d231358 100644
--- a/pki/path_builder_unittest.cc
+++ b/pki/path_builder_unittest.cc
@@ -1352,6 +1352,95 @@
}
}
+// Tests that when SetValidPathLimit is used path builder returns the number of
+// valid paths we expect before the valid path limit was reached.
+TEST_F(PathBuilderKeyRolloverTest, ExplorePathsWithPathLimit) {
+ struct Expectation {
+ size_t valid_path_limit;
+ size_t expected_num_paths;
+ } kExpectations[] = {
+ {0, 4}, // No path limit. Three valid, one partial path should be built
+ {1, 1}, // One valid path
+ {2, 3}, // Two valid, one partial
+ {3, 4},
+ {4, 4},
+ {5, 4},
+ };
+
+ // Trust both old and new roots.
+ TrustStoreInMemory trust_store;
+ trust_store.AddTrustAnchor(oldroot_);
+ trust_store.AddTrustAnchor(newroot_);
+
+ // Intermediates and root rollover are all provided synchronously.
+ CertIssuerSourceStatic sync_certs;
+ sync_certs.AddCert(oldintermediate_);
+ sync_certs.AddCert(newintermediate_);
+
+ for (const auto &expectation : kExpectations) {
+ SCOPED_TRACE(expectation.valid_path_limit);
+
+ CertPathBuilder path_builder(
+ target_, &trust_store, &delegate_, time_, KeyPurpose::ANY_EKU,
+ initial_explicit_policy_, user_initial_policy_set_,
+ initial_policy_mapping_inhibit_, initial_any_policy_inhibit_);
+ path_builder.AddCertIssuerSource(&sync_certs);
+
+ // Stop after finding enough valid paths.
+ path_builder.SetValidPathLimit(expectation.valid_path_limit);
+
+ auto result = path_builder.Run();
+
+ EXPECT_TRUE(result.HasValidPath());
+ ASSERT_EQ(expectation.expected_num_paths, result.paths.size());
+
+ if (result.paths.size() > 0) {
+ // Path builder will first build path: target <- newintermediate <-
+ // newroot
+ const auto &path0 = *result.paths[0];
+ EXPECT_TRUE(path0.IsValid());
+ ASSERT_EQ(3U, path0.certs.size());
+ EXPECT_EQ(target_, path0.certs[0]);
+ EXPECT_EQ(newintermediate_, path0.certs[1]);
+ EXPECT_EQ(newroot_, path0.certs[2]);
+ EXPECT_EQ(3U, result.max_depth_seen);
+ }
+
+ if (result.paths.size() > 1) {
+ // Next path: target <- newintermediate <- oldroot
+ const auto &path1 = *result.paths[1];
+ EXPECT_FALSE(path1.IsValid());
+ ASSERT_EQ(3U, path1.certs.size());
+ EXPECT_EQ(target_, path1.certs[0]);
+ EXPECT_EQ(newintermediate_, path1.certs[1]);
+ EXPECT_EQ(oldroot_, path1.certs[2]);
+ EXPECT_EQ(3U, result.max_depth_seen);
+ }
+
+ if (result.paths.size() > 2) {
+ // Next path: target <- oldintermediate <- oldroot
+ const auto &path2 = *result.paths[2];
+ EXPECT_TRUE(path2.IsValid());
+ ASSERT_EQ(3U, path2.certs.size());
+ EXPECT_EQ(target_, path2.certs[0]);
+ EXPECT_EQ(oldintermediate_, path2.certs[1]);
+ EXPECT_EQ(oldroot_, path2.certs[2]);
+ EXPECT_EQ(3U, result.max_depth_seen);
+ }
+
+ if (result.paths.size() > 3) {
+ // Final path: target <- oldintermediate <- newroot
+ const auto &path3 = *result.paths[3];
+ EXPECT_FALSE(path3.IsValid());
+ ASSERT_EQ(3U, path3.certs.size());
+ EXPECT_EQ(target_, path3.certs[0]);
+ EXPECT_EQ(oldintermediate_, path3.certs[1]);
+ EXPECT_EQ(newroot_, path3.certs[2]);
+ EXPECT_EQ(3U, result.max_depth_seen);
+ }
+ }
+}
+
// If the target cert is a trust anchor, however is not itself *signed* by a
// trust anchor, then it is not considered valid (the SPKI and name of the
// trust anchor matches the SPKI and subject of the targe certificate, but the
@@ -2262,7 +2351,7 @@
target, &trust_store, &delegate, verify_time, KeyPurpose::ANY_EKU,
InitialExplicitPolicy::kFalse, {der::Input(kAnyPolicyOid)},
InitialPolicyMappingInhibit::kFalse, InitialAnyPolicyInhibit::kFalse);
- path_builder.SetExploreAllPaths(true);
+ path_builder.SetValidPathLimit(0);
CertPathBuilder::Result result = path_builder.Run();
EXPECT_TRUE(result.HasValidPath());
@@ -2438,7 +2527,7 @@
target, &trust_store, &delegate, verify_time, KeyPurpose::ANY_EKU,
InitialExplicitPolicy::kFalse, {der::Input(kAnyPolicyOid)},
InitialPolicyMappingInhibit::kFalse, InitialAnyPolicyInhibit::kFalse);
- path_builder.SetExploreAllPaths(true);
+ path_builder.SetValidPathLimit(0);
CertPathBuilder::Result result = path_builder.Run();
EXPECT_TRUE(result.HasValidPath());
