Certificate path builder for new certificate verification library

Certificate path builder for new certificate verification library

Builds paths from a target certificate to a trust anchor and attempts to verify them according to RFC 5280. Supports asynchronous intermediate lookups (eg, AIA fetching) and backtracking.

This implementation uses a depth-first strategy which is simple and uses minimal resources, but may not be optimal.

BUG=410574
Committed: https://crrev.com/76f636098ccda9f283614545352b4964e7ec2b5c
Cr-Commit-Position: refs/heads/master@{#404239}

[mattm, 2016-04-26 02:22:28]

Patchset #1 (id:1) has been deleted

[mattm, 2016-04-26 02:25:04]

mattm@chromium.org changed reviewers:
+ eroman@chromium.org, rsleevi@chromium.org

[mattm, 2016-04-26 02:25:04]

This is my WIP path builder code if you want to do some high-level review &
comments. Don't worry about doing a full review yet.

[eroman, 2016-04-26 19:30:41]

Thanks Matt!

I realize this is still an early WIP, but figured I would post some initial
thoughts.

Also could you give a high level description of the intended design and
layering?

  * I expect we want to more strongly define the abstraction around where/when
parsing happens, and where any parsed results are stored -- what is currently
being touched on by "CertThing". I have some more comments on this.

 * Do we want to use net-errors for the internal functions/state machine? Partly
bias, but I have grown to hate //net's use of "int", and keep encountering bugs
resulting from type confusion (i.e. is it an error, is it a byte count, what
does 0 mean, etc.). I expect we don't want to depend on those error codes anyway
for when we some day split out of //net.

 * Testing and public interface -- We should probably test all of the existing
VerifyCertificateChain() tests with the path building code. And jumble the input
paths given. In fact I imagine we can just get rid of the old
VerifyCertificateChain() interface, since that is really just a specialized case
of path building which just looks for the trust anchor (and requires correct
ordering of certificates). I imagine as we go deeper on this more of the
verification logic it currently encompasses will be baked into the building
logic.

[mattm, 2016-04-26 21:26:02]

On 2016/04/26 19:30:41, eroman wrote:
> Thanks Matt!
> 
> I realize this is still an early WIP, but figured I would post some initial
> thoughts.
> 
> Also could you give a high level description of the intended design and
> layering?


CertPathBuilder is the main interface. The caller is passes in the target cert
to verify, some number of CertSources and the TrustStore. The interface allows
for synchronous or asynchronous completion. In the asnychronous case, destroying
the CertPathBuilder before it is finished should release any resources and
cancel any outstanding asynchronous requests.

Example CertSources would be the intermediates from the SSL handshake, AIA
fetcher, cached certs from previous requests, certs from OS cert store. Each
CertSource can return results either synchronously or asynchronously. This
allows a two stage approach where the path builder can try synchronously
available paths before waiting on async ones.

The CertPathBuilder has an output Result which contains the attempted paths,
result codes, and would contain the error details for each path once that’s
ready. The intent is to by default just return a single result path, but have a
debug/test flag that enumerates and returns all possible paths (not implemented
yet).

Internally the CertPathBuilder just uses a CertPathIter to loop through possible
paths, test each one, and return once it found a valid path or runs out of
possible paths.

The CertPathIter iterates through possible paths in a depth first search, and
returns the paths that might be valid (those that end with a cert that issuer
matches a trust anchor). (There are some comments in the code about that design
choice. I’m considering switching it to build the path including the trust
anchor instead of looping through the possible trust anchors in
CertPathBuilder.)

CertPathIter maintains a “current path” which is actually a vector of
CertIssuersIter. It will continue adding more CertIssuersIters onto the path as
it descends the tree in a DFS. That means that even though at each level it will
try synchronously available issuers before async ones, it might still do async
queries even though some other possible path could have been built entirely
synchronously.

CertPathIter uses LoopChecker to avoid building paths that contain the same cert
twice.

CertIssuersIter is just responsible for finding and returning the issuers of a
given cert. It does this in two stages, first returning only synchronously
available certs, and then re-querying all the CertSources for async certs. There
is a TODO to add sorting/prioritization to the order the issuers are returned. 


>   * I expect we want to more strongly define the abstraction around where/when
> parsing happens, and where any parsed results are stored -- what is currently
> being touched on by "CertThing". I have some more comments on this.

Yeah, that’s an area that needs more work. The current WIP isn’t a final
solution there. I wanted to avoid refcounting and unnecessary copying, but it
could still use some improvements. Happy to discuss ideas.

>  * Do we want to use net-errors for the internal functions/state machine?
Partly
> bias, but I have grown to hate //net's use of "int", and keep encountering
bugs
> resulting from type confusion (i.e. is it an error, is it a byte count, what
> does 0 mean, etc.). I expect we don't want to depend on those error codes
anyway
> for when we some day split out of //net.

That’s a good thought. I’m not that happy with using the net-error codes either.

>  * Testing and public interface -- We should probably test all of the existing
> VerifyCertificateChain() tests with the path building code. And jumble the
input
> paths given. In fact I imagine we can just get rid of the old
> VerifyCertificateChain() interface, since that is really just a specialized
case
> of path building which just looks for the trust anchor (and requires correct
> ordering of certificates). I imagine as we go deeper on this more of the
> verification logic it currently encompasses will be baked into the building
> logic.

Running against the VerifyCertificateChain tests sounds like a good idea.

Replacing VerifyCertificateChain also sounds reasonable, though one difference
is that it is always synchronous. I guess CertPathBuilder should also be
synchronous if you don’t pass in any async-capable CertSources. Dunno if we
should declare that officially or just require anyone using it to handle async
results?

[eroman, 2016-04-26 22:10:11]

https://codereview.chromium.org/1923433002/diff/20001/net/cert/internal/path_...
File net/cert/internal/path_builder.cc (right):

https://codereview.chromium.org/1923433002/diff/20001/net/cert/internal/path_...
net/cert/internal/path_builder.cc:544: for (auto& trust_anchor :
matching_anchors) {
How does this work when the target cert being verified is a trust anchor itself?

I could envision handling the trust anchors more generally as part of building
out the path (you also mention something like this higher up).

  (1) Lookup the trustedness of current certificate in trust store -- it may be
{trusted, distrusted, unknown}. If it is actively trusted/untrusted then can
stop looking for issuers.

  (2) Otherwise try to find an issuer. Look for an issuer in all the cert
sources, _including_ the trust store.

  (3) go to (1)


In the case where the issuer came from trust store in step (2) you basically
already know its trustedness. But conceptually I think that loop works.

https://codereview.chromium.org/1923433002/diff/20001/net/cert/internal/path_...
net/cert/internal/path_builder.cc:554: next_path_.pop_back();
Here it looks to be popping the trust anchor out of the path -- why?

 definitely believe we want to keep the trust anchor as part of the path.

Both internally in the code (so any hooks can operate on the root like any other
cert), but especially so for the public API, since callers may want to see what
trust anchor the path chained up to.

Since we are requiring trust anchors be certificates, we can do this, and don't
need some other separate representation for the resulting trust anchor.

https://codereview.chromium.org/1923433002/diff/20001/net/cert/internal/path_...
File net/cert/internal/path_builder.h (right):

https://codereview.chromium.org/1923433002/diff/20001/net/cert/internal/path_...
net/cert/internal/path_builder.h:153: const der::GeneralizedTime& time_;
Why a const reference? This seems like a problem since operation is async.

[mattm, 2016-04-26 22:54:16]

https://codereview.chromium.org/1923433002/diff/20001/net/cert/internal/path_...
File net/cert/internal/path_builder.cc (right):

https://codereview.chromium.org/1923433002/diff/20001/net/cert/internal/path_...
net/cert/internal/path_builder.cc:544: for (auto& trust_anchor :
matching_anchors) {
On 2016/04/26 22:10:10, eroman wrote:
> How does this work when the target cert being verified is a trust anchor
itself?

Yeah, that would be an issue with this approach.

> I could envision handling the trust anchors more generally as part of building
> out the path (you also mention something like this higher up).
> 
>   (1) Lookup the trustedness of current certificate in trust store -- it may
be
> {trusted, distrusted, unknown}. If it is actively trusted/untrusted then can
> stop looking for issuers.
> 
>   (2) Otherwise try to find an issuer. Look for an issuer in all the cert
> sources, _including_ the trust store.
> 
>   (3) go to (1)
> 
> 
> In the case where the issuer came from trust store in step (2) you basically
> already know its trustedness. But conceptually I think that loop works.

yeah, that is one of the alternate approaches I was considering. The one issue I
thought might occur is with LoopChecker preventing the trust anchor from being
added to the chain (eg if the target cert had same Name+SAN+SPKI as a trust
anchor, but was a different cert which wasn't in the trust store). (This would
be once LoopChecker is updated to use Name+SAN+SPKI instead of the full cert
DER.)

https://codereview.chromium.org/1923433002/diff/20001/net/cert/internal/path_...
net/cert/internal/path_builder.cc:554: next_path_.pop_back();
On 2016/04/26 22:10:10, eroman wrote:
> Here it looks to be popping the trust anchor out of the path -- why?
> 
>  definitely believe we want to keep the trust anchor as part of the path.
> 
> Both internally in the code (so any hooks can operate on the root like any
other
> cert), but especially so for the public API, since callers may want to see
what
> trust anchor the path chained up to.
> 
> Since we are requiring trust anchors be certificates, we can do this, and
don't
> need some other separate representation for the resulting trust anchor.

AddResultPath makes a copy of the path which is what actually gets returned, the
popping here is just to prepare the next_path_ for the next iteration of the
loop.

https://codereview.chromium.org/1923433002/diff/20001/net/cert/internal/path_...
File net/cert/internal/path_builder.h (right):

https://codereview.chromium.org/1923433002/diff/20001/net/cert/internal/path_...
net/cert/internal/path_builder.h:153: const der::GeneralizedTime& time_;
On 2016/04/26 22:10:11, eroman wrote:
> Why a const reference? This seems like a problem since operation is async.

Good catch. Just a bad copy/paste.

[Ryan Sleevi, 2016-05-04 02:42:42]

Some general musings; I haven't looked as in depth as I want, but the highlevel
approach you're taking sounds pretty solid.

https://codereview.chromium.org/1923433002/diff/80001/net/cert/internal/path_...
File net/cert/internal/path_builder.h (right):

https://codereview.chromium.org/1923433002/diff/80001/net/cert/internal/path_...
net/cert/internal/path_builder.h:24: using IssuerCallback =
base::Callback<void(CertVector)>;
Musing outloud: Should we return an explicit CertVector, or should there be a
CertSource iterator returned? I'm wondering if that would save us anything, in
the end, and maybe I've been thinking too much about promises/generators lately.
(Soon! C++14! Exciting!)

https://codereview.chromium.org/1923433002/diff/80001/net/cert/internal/path_...
net/cert/internal/path_builder.h:47: std::unique_ptr<Request>* out_req) = 0;
Musing outloud: Do we need two methods, or should we just have one method, in
which |out_req| was optional. If nullptr, only synchronous results are allowed.

https://codereview.chromium.org/1923433002/diff/80001/net/cert/internal/path_...
net/cert/internal/path_builder.h:50: class NET_EXPORT StaticCertSource : public
CertSource {
Musing outloud: Does it make sense to have an aggregate CertSource that
encompasses all of the logic for interrogating a collection of CertSources? This
means that you could change the CertPath builder interface to take a single
CertSource, or you could create different CertSources for different purposes
(here's the TA CertSource vs Intermediate?).

It also means you can, arguably, implement the sync/async distinction easier -
the CollectionCertSource (I suck at naming) could interrogate all of its
CertSources statically first, and asynchronously)

https://codereview.chromium.org/1923433002/diff/80001/net/cert/internal/path_...
net/cert/internal/path_builder.h:68: };
There's a part of me that leans to suggest separating these out to individual
files as we proceed.

https://codereview.chromium.org/1923433002/diff/80001/net/cert/internal/path_...
net/cert/internal/path_builder.h:73: // * intermediates in OS cert store
(async?)
Aye

https://codereview.chromium.org/1923433002/diff/80001/net/cert/internal/path_...
net/cert/internal/path_builder.h:123: Result* result);
I'm wondering whether we should have a CertPathBuilderBuilder (OK, bad name). I
just imagine that there will be a growing set of parameters to CertPathBuilder
as things grow - visitors for debugging interfaces, callbacks for application
policy, etc - that rather than pass all in the Ctor, we have something that
builds an object and then we run.

(To that end, I'm not even sure if we need to break it out into a Builder, per
se, vs SetFoo/SetBar and then validate consistency in the Run() call; the
Builder just helps separate out parameter validation from execution)

For example, what happens if you supply a null |cert|, or an empty trust_store,
etc.

[mattm, 2016-05-04 23:21:16]

https://codereview.chromium.org/1923433002/diff/80001/net/cert/internal/path_...
File net/cert/internal/path_builder.h (right):

https://codereview.chromium.org/1923433002/diff/80001/net/cert/internal/path_...
net/cert/internal/path_builder.h:24: using IssuerCallback =
base::Callback<void(CertVector)>;
On 2016/05/04 02:42:42, Ryan Sleevi wrote:
> Musing outloud: Should we return an explicit CertVector, or should there be a
> CertSource iterator returned? I'm wondering if that would save us anything, in
> the end, and maybe I've been thinking too much about promises/generators
lately.
> (Soon! C++14! Exciting!)

Hm, could perhaps avoid some copies? It's always hard to figure out exactly how
much copying goes on in running a callback. I've given this a shot. (I made the
Request object have a GetNext method, as a bonus the callback returns the same
Request pointer in case the caller wants to keep track of which request
completed.)

https://codereview.chromium.org/1923433002/diff/80001/net/cert/internal/path_...
net/cert/internal/path_builder.h:47: std::unique_ptr<Request>* out_req) = 0;
On 2016/05/04 02:42:42, Ryan Sleevi wrote:
> Musing outloud: Do we need two methods, or should we just have one method, in
> which |out_req| was optional. If nullptr, only synchronous results are
allowed.

Did consider that, the question then is when doing the async phase do you just
re-get all the sync results and throw them away when de-duping? Or keep a list
of the sources that didn't return results synchronously and only try those ones?

https://codereview.chromium.org/1923433002/diff/80001/net/cert/internal/path_...
net/cert/internal/path_builder.h:50: class NET_EXPORT StaticCertSource : public
CertSource {
On 2016/05/04 02:42:41, Ryan Sleevi wrote:
> Musing outloud: Does it make sense to have an aggregate CertSource that
> encompasses all of the logic for interrogating a collection of CertSources?
This
> means that you could change the CertPath builder interface to take a single
> CertSource, or you could create different CertSources for different purposes
> (here's the TA CertSource vs Intermediate?).
> 
> It also means you can, arguably, implement the sync/async distinction easier -
> the CollectionCertSource (I suck at naming) could interrogate all of its
> CertSources statically first, and asynchronously)

One issue is that CertIssuersIter currently handles each CertSource async
request independently, so it can continue processing as soon as any one of them
completes. If we aggregated them into a collection of certsources it would need
a different interface that can have multiple async callbacks. CertIssuersIter
would still need the logic of handling the multiple callbacks, so I'm not sure
it would clean things up there.

It could be worth considering if it enables a cleaner interface for creating a
CertPathBuilder, though I'm not immediately clear if it does. Probably will
become more obvious once we have more CertSource implementations and see what
the code looks like.

https://codereview.chromium.org/1923433002/diff/80001/net/cert/internal/path_...
net/cert/internal/path_builder.h:68: };
On 2016/05/04 02:42:42, Ryan Sleevi wrote:
> There's a part of me that leans to suggest separating these out to individual
> files as we proceed.

I'll look at sorting out the file layout some in another patchset.

https://codereview.chromium.org/1923433002/diff/80001/net/cert/internal/path_...
net/cert/internal/path_builder.h:123: Result* result);
On 2016/05/04 02:42:42, Ryan Sleevi wrote:
> I'm wondering whether we should have a CertPathBuilderBuilder (OK, bad name).
I
> just imagine that there will be a growing set of parameters to CertPathBuilder
> as things grow - visitors for debugging interfaces, callbacks for application
> policy, etc - that rather than pass all in the Ctor, we have something that
> builds an object and then we run.
> 
> (To that end, I'm not even sure if we need to break it out into a Builder, per
> se, vs SetFoo/SetBar and then validate consistency in the Run() call; the
> Builder just helps separate out parameter validation from execution)
> 
> For example, what happens if you supply a null |cert|, or an empty
trust_store,
> etc.

I like the idea. For now I changed it so the constructor takes the required args
and then there are setters for the optional ones. (Right now just CertSources.)

[mattm, 2016-06-08 00:29:33]

Description was changed from

==========
*WIP* Certificate path builder

BUG=410574
==========

to

==========
Certificate path builder

BUG=410574
==========

[mattm, 2016-06-08 00:31:54]

I think this is ready for another look.

(Note: it shows as dependent on https://codereview.chromium.org/2036033002/ but
the ordering of the two CLs doesn't actually matter.)

[eroman, 2016-06-17 01:03:23]

https://codereview.chromium.org/1923433002/diff/450001/components/cast_certif...
File components/cast_certificate/cast_cert_validator.cc (right):

https://codereview.chromium.org/1923433002/diff/450001/components/cast_certif...
components/cast_certificate/cast_cert_validator.cc:287: for (size_t i = 1; i <
input_chain.size(); ++i)
Given how this works now, I think we should probably just retire |input_chain|
and |ref_checker| and simplify things a bit.

https://codereview.chromium.org/1923433002/diff/450001/components/cast_certif...
components/cast_certificate/cast_cert_validator.cc:296: net::CertPathBuilder
path_builder(input_chain.front(), &CastTrustStore::Get(),
There needs to also ensure somewhere that !input_chain.empty() -- before this
was being done internal to VerifyCertificateChain().

https://codereview.chromium.org/1923433002/diff/450001/components/cast_certif...
components/cast_certificate/cast_cert_validator.cc:301: DCHECK(rv ==
net::CompletionStatus::SYNC);
nit: DCHECK_EQ()

https://codereview.chromium.org/1923433002/diff/450001/components/cast_certif...
components/cast_certificate/cast_cert_validator.cc:302: if (result.result() !=
net::OK)
How about abstracting this with result.IsSuccess() or some such thing?

https://codereview.chromium.org/1923433002/diff/450001/net/cert/internal/path...
File net/cert/internal/path_builder.cc (right):

https://codereview.chromium.org/1923433002/diff/450001/net/cert/internal/path...
net/cert/internal/path_builder.cc:31: std::string CertDebugString(const
ParsedCertificate* cert) {
Is this temporary, or intended to be long lived? If temporary add a TODO to
remove it.

https://codereview.chromium.org/1923433002/diff/450001/net/cert/internal/path...
net/cert/internal/path_builder.cc:98: // In either case, if all issuers have
been exhausted, |*out_cert| is cleared.
This should also document that |callback| can be null to select synchronous-only
mode.

https://codereview.chromium.org/1923433002/diff/450001/net/cert/internal/path...
net/cert/internal/path_builder.cc:104: scoped_refptr<ParsedCertificate>
reference_cert() const { return cert_; }
Having both cert() and reference_cert() seems unnecessary. How about just making
cert() a non-const pointer?

https://codereview.chromium.org/1923433002/diff/450001/net/cert/internal/path...
net/cert/internal/path_builder.cc:113: // synchronous, results, then possibly
multiple times as asynchronous results
synchronous, results --> synchronous results

https://codereview.chromium.org/1923433002/diff/450001/net/cert/internal/path...
net/cert/internal/path_builder.cc:116: // results were already returned.
Is it also important that this never be shrunk? (present_issuers_ depends on its
contents right)?

https://codereview.chromium.org/1923433002/diff/450001/net/cert/internal/path...
net/cert/internal/path_builder.cc:122: std::unordered_set<base::StringPiece,
base::StringPieceHash> present_issuers_;
How does this relate to the looper checks for duplicates? (different notions of
equality).

https://codereview.chromium.org/1923433002/diff/450001/net/cert/internal/path...
net/cert/internal/path_builder.cc:127: int pending_async_results_;
Does this ever go negative?

https://codereview.chromium.org/1923433002/diff/450001/net/cert/internal/path...
net/cert/internal/path_builder.cc:206: // Synchonous-only mode, don't try to
query async sources.
typeo

https://codereview.chromium.org/1923433002/diff/450001/net/cert/internal/path...
net/cert/internal/path_builder.cc:258: DCHECK(status == CompletionStatus::SYNC);
dcheck_eq

https://codereview.chromium.org/1923433002/diff/450001/net/cert/internal/path...
net/cert/internal/path_builder.cc:259: issuers_.push_back(std::move(cert));
Why doesn't present_issuers_ need to be updated?

https://codereview.chromium.org/1923433002/diff/450001/net/cert/internal/path...
net/cert/internal/path_builder.cc:271: *out_cert_ = std::move(issuers_[cur_++]);
I don't understand the ownership model between issuers_ and present_issuers_.

My understanding is present_issuers_ points to the DER data, kept alive by
issuers.

If however we give up our reference to the cert here, then there is no guarantee
that data will remain alive.

https://codereview.chromium.org/1923433002/diff/450001/net/cert/internal/path...
net/cert/internal/path_builder.cc:305: const TrustStore* trust_store);
my suggestion is to save this as a const reference (style guide doesn't actually
forbid that).

https://codereview.chromium.org/1923433002/diff/450001/net/cert/internal/path...
net/cert/internal/path_builder.cc:364: callback_ = callback;
Can you also null out_path_ in the sync case? (as a precaution).

https://codereview.chromium.org/1923433002/diff/450001/net/cert/internal/path...
net/cert/internal/path_builder.cc:403: &next_cert_, allow_async ?
base::Bind(&CertPathIter::HandleGotNextIssuer,
would it be better to bind this just once?

https://codereview.chromium.org/1923433002/diff/450001/net/cert/internal/path...
File net/cert/internal/path_builder.h (right):

https://codereview.chromium.org/1923433002/diff/450001/net/cert/internal/path...
net/cert/internal/path_builder.h:32: class NET_EXPORT CertPathBuilder {
Please provide some documentation on the role of this class.

https://codereview.chromium.org/1923433002/diff/450001/net/cert/internal/path...
net/cert/internal/path_builder.h:34: struct NET_EXPORT ResultPath {
Please document

https://codereview.chromium.org/1923433002/diff/450001/net/cert/internal/path...
net/cert/internal/path_builder.h:38:
std::vector<scoped_refptr<ParsedCertificate>> path;
Please document order, and where the target certificate and trust anchor appear.

https://codereview.chromium.org/1923433002/diff/450001/net/cert/internal/path...
net/cert/internal/path_builder.h:39: int rv;
Please document the domain of this error.

https://codereview.chromium.org/1923433002/diff/450001/net/cert/internal/path...
net/cert/internal/path_builder.h:47: int result() {
const?

https://codereview.chromium.org/1923433002/diff/450001/net/cert/internal/path...
net/cert/internal/path_builder.h:48: if (paths.empty())
Would it be worthwhile to instead use:

if (best_result_index >= paths.size())

https://codereview.chromium.org/1923433002/diff/450001/net/cert/internal/path...
net/cert/internal/path_builder.h:55: // Index into |paths|. Before use,
|paths.empty()| must be checked.
or should the recommendation be best_result_index < paths.size() ?

https://codereview.chromium.org/1923433002/diff/450001/net/cert/internal/path...
net/cert/internal/path_builder.h:83: void AddCertIssuerSource(CertIssuerSource*
cert_issuer_source);
todo: interface is a bit squirly (destruction, completion, don't call twice,
etc.)

https://codereview.chromium.org/1923433002/diff/450001/net/cert/internal/path...
net/cert/internal/path_builder.h:85: // Begins verification of |cert|. If the
return value is SYNC then the
nit: It is unclear what |cert| is here (it was the |cert| passed in to ctor).

https://codereview.chromium.org/1923433002/diff/450001/net/cert/internal/path...
net/cert/internal/path_builder.h:93: CompletionStatus Run(const base::Closure&
callback);
Please also mention somewhere:
  * The cancellation semantics -- is it ok to delete CertPathBuilder while a
request is in progress
  * That this is not intended for multiple requests (Run() should not be called
multiple times).

https://codereview.chromium.org/1923433002/diff/450001/net/cert/internal/path...
File net/cert/internal/path_builder_pkits_unittest.cc (right):

https://codereview.chromium.org/1923433002/diff/450001/net/cert/internal/path...
net/cert/internal/path_builder_pkits_unittest.cc:96: if (rv ==
CompletionStatus::ASYNC) {
Is this exercised currently?

[mattm, 2016-06-18 03:45:52]

Patchset #24 (id:470001) has been deleted

[mattm, 2016-06-18 04:28:56]

https://codereview.chromium.org/1923433002/diff/450001/components/cast_certif...
File components/cast_certificate/cast_cert_validator.cc (right):

https://codereview.chromium.org/1923433002/diff/450001/components/cast_certif...
components/cast_certificate/cast_cert_validator.cc:287: for (size_t i = 1; i <
input_chain.size(); ++i)
On 2016/06/17 01:03:22, eroman wrote:
> Given how this works now, I think we should probably just retire |input_chain|
> and |ref_checker| and simplify things a bit.

Done.

https://codereview.chromium.org/1923433002/diff/450001/components/cast_certif...
components/cast_certificate/cast_cert_validator.cc:296: net::CertPathBuilder
path_builder(input_chain.front(), &CastTrustStore::Get(),
On 2016/06/17 01:03:21, eroman wrote:
> There needs to also ensure somewhere that !input_chain.empty() -- before this
> was being done internal to VerifyCertificateChain().

Done.

https://codereview.chromium.org/1923433002/diff/450001/components/cast_certif...
components/cast_certificate/cast_cert_validator.cc:301: DCHECK(rv ==
net::CompletionStatus::SYNC);
On 2016/06/17 01:03:21, eroman wrote:
> nit: DCHECK_EQ()

Done.

https://codereview.chromium.org/1923433002/diff/450001/components/cast_certif...
components/cast_certificate/cast_cert_validator.cc:302: if (result.result() !=
net::OK)
On 2016/06/17 01:03:22, eroman wrote:
> How about abstracting this with result.IsSuccess() or some such thing?

Done.

https://codereview.chromium.org/1923433002/diff/450001/net/cert/internal/path...
File net/cert/internal/path_builder.cc (right):

https://codereview.chromium.org/1923433002/diff/450001/net/cert/internal/path...
net/cert/internal/path_builder.cc:31: std::string CertDebugString(const
ParsedCertificate* cert) {
On 2016/06/17 01:03:22, eroman wrote:
> Is this temporary, or intended to be long lived? If temporary add a TODO to
> remove it.

I added a TODO to decide whether or not it should be ;)

https://codereview.chromium.org/1923433002/diff/450001/net/cert/internal/path...
net/cert/internal/path_builder.cc:98: // In either case, if all issuers have
been exhausted, |*out_cert| is cleared.
On 2016/06/17 01:03:22, eroman wrote:
> This should also document that |callback| can be null to select
synchronous-only
> mode.

Done.

https://codereview.chromium.org/1923433002/diff/450001/net/cert/internal/path...
net/cert/internal/path_builder.cc:104: scoped_refptr<ParsedCertificate>
reference_cert() const { return cert_; }
On 2016/06/17 01:03:22, eroman wrote:
> Having both cert() and reference_cert() seems unnecessary. How about just
making
> cert() a non-const pointer?

The style guide prohibits taking a reference from a pointer to a refcounted
object.
(https://www.chromium.org/developers/coding-style#TOC-Object-ownership-and-cal...)

https://codereview.chromium.org/1923433002/diff/450001/net/cert/internal/path...
net/cert/internal/path_builder.cc:113: // synchronous, results, then possibly
multiple times as asynchronous results
On 2016/06/17 01:03:22, eroman wrote:
> synchronous, results --> synchronous results

Done.

https://codereview.chromium.org/1923433002/diff/450001/net/cert/internal/path...
net/cert/internal/path_builder.cc:116: // results were already returned.
On 2016/06/17 01:03:22, eroman wrote:
> Is it also important that this never be shrunk? (present_issuers_ depends on
its
> contents right)?

yes.. (replied in more depth below)

https://codereview.chromium.org/1923433002/diff/450001/net/cert/internal/path...
net/cert/internal/path_builder.cc:122: std::unordered_set<base::StringPiece,
base::StringPieceHash> present_issuers_;
On 2016/06/17 01:03:22, eroman wrote:
> How does this relate to the looper checks for duplicates? (different notions
of
> equality).

LoopChecker avoids repeating different versions of the same cert in the same
path, while CertIssuerIter wants to return different versions of the same cert
so they can be tried in different candidate paths. Expanded the comments about
this.

https://codereview.chromium.org/1923433002/diff/450001/net/cert/internal/path...
net/cert/internal/path_builder.cc:127: int pending_async_results_;
On 2016/06/17 01:03:22, eroman wrote:
> Does this ever go negative?

nope. Changed to unsigned.

https://codereview.chromium.org/1923433002/diff/450001/net/cert/internal/path...
net/cert/internal/path_builder.cc:206: // Synchonous-only mode, don't try to
query async sources.
On 2016/06/17 01:03:22, eroman wrote:
> typeo

Done.

https://codereview.chromium.org/1923433002/diff/450001/net/cert/internal/path...
net/cert/internal/path_builder.cc:258: DCHECK(status == CompletionStatus::SYNC);
On 2016/06/17 01:03:22, eroman wrote:
> dcheck_eq

Done.

https://codereview.chromium.org/1923433002/diff/450001/net/cert/internal/path...
net/cert/internal/path_builder.cc:259: issuers_.push_back(std::move(cert));
On 2016/06/17 01:03:22, eroman wrote:
> Why doesn't present_issuers_ need to be updated?

Good catch. Fixed.

https://codereview.chromium.org/1923433002/diff/450001/net/cert/internal/path...
net/cert/internal/path_builder.cc:271: *out_cert_ = std::move(issuers_[cur_++]);
On 2016/06/17 01:03:22, eroman wrote:
> I don't understand the ownership model between issuers_ and present_issuers_.
> 
> My understanding is present_issuers_ points to the DER data, kept alive by
> issuers.
> 
> If however we give up our reference to the cert here, then there is no
guarantee
> that data will remain alive.

yes, good catch. I think this doesn't come up in current tests since something 
else always holds refs. But that's not guaranteed. I'll change it to keep
holding a reference.

https://codereview.chromium.org/1923433002/diff/450001/net/cert/internal/path...
net/cert/internal/path_builder.cc:305: const TrustStore* trust_store);
On 2016/06/17 01:03:22, eroman wrote:
> my suggestion is to save this as a const reference (style guide doesn't
actually
> forbid that).

It does suggest to use const pointer if a pointer/ref to the object is saved
though. (http://google.github.io/styleguide/cppguide.html#Reference_Arguments)

https://codereview.chromium.org/1923433002/diff/450001/net/cert/internal/path...
net/cert/internal/path_builder.cc:364: callback_ = callback;
On 2016/06/17 01:03:22, eroman wrote:
> Can you also null out_path_ in the sync case? (as a precaution).

Done.

https://codereview.chromium.org/1923433002/diff/450001/net/cert/internal/path...
net/cert/internal/path_builder.cc:403: &next_cert_, allow_async ?
base::Bind(&CertPathIter::HandleGotNextIssuer,
On 2016/06/17 01:03:22, eroman wrote:
> would it be better to bind this just once?

Hm, is Bind that expensive? Seems like premature optimization at first glance.

https://codereview.chromium.org/1923433002/diff/450001/net/cert/internal/path...
File net/cert/internal/path_builder.h (right):

https://codereview.chromium.org/1923433002/diff/450001/net/cert/internal/path...
net/cert/internal/path_builder.h:32: class NET_EXPORT CertPathBuilder {
On 2016/06/17 01:03:22, eroman wrote:
> Please provide some documentation on the role of this class.

Done.

https://codereview.chromium.org/1923433002/diff/450001/net/cert/internal/path...
net/cert/internal/path_builder.h:34: struct NET_EXPORT ResultPath {
On 2016/06/17 01:03:22, eroman wrote:
> Please document

Done.

https://codereview.chromium.org/1923433002/diff/450001/net/cert/internal/path...
net/cert/internal/path_builder.h:38:
std::vector<scoped_refptr<ParsedCertificate>> path;
On 2016/06/17 01:03:23, eroman wrote:
> Please document order, and where the target certificate and trust anchor
appear.

Done.

https://codereview.chromium.org/1923433002/diff/450001/net/cert/internal/path...
net/cert/internal/path_builder.h:39: int rv;
On 2016/06/17 01:03:23, eroman wrote:
> Please document the domain of this error.

Done.

https://codereview.chromium.org/1923433002/diff/450001/net/cert/internal/path...
net/cert/internal/path_builder.h:47: int result() {
On 2016/06/17 01:03:23, eroman wrote:
> const?

Done.

https://codereview.chromium.org/1923433002/diff/450001/net/cert/internal/path...
net/cert/internal/path_builder.h:48: if (paths.empty())
On 2016/06/17 01:03:23, eroman wrote:
> Would it be worthwhile to instead use:
> 
> if (best_result_index >= paths.size())

My thought was it's a bug if paths is not empty but best_result_index_ doesn't
have a valid value, so doing the test that way just hides the bug..

https://codereview.chromium.org/1923433002/diff/450001/net/cert/internal/path...
net/cert/internal/path_builder.h:83: void AddCertIssuerSource(CertIssuerSource*
cert_issuer_source);
On 2016/06/17 01:03:22, eroman wrote:
> todo: interface is a bit squirly (destruction, completion, don't call twice,
> etc.)

Is this a leftover comment? since AddCertIssuerSource can be called twice..

https://codereview.chromium.org/1923433002/diff/450001/net/cert/internal/path...
net/cert/internal/path_builder.h:85: // Begins verification of |cert|. If the
return value is SYNC then the
On 2016/06/17 01:03:23, eroman wrote:
> nit: It is unclear what |cert| is here (it was the |cert| passed in to ctor).

Done.

https://codereview.chromium.org/1923433002/diff/450001/net/cert/internal/path...
net/cert/internal/path_builder.h:93: CompletionStatus Run(const base::Closure&
callback);
On 2016/06/17 01:03:22, eroman wrote:
> Please also mention somewhere:
>   * The cancellation semantics -- is it ok to delete CertPathBuilder while a
> request is in progress
>   * That this is not intended for multiple requests (Run() should not be
called
> multiple times).

Done.

https://codereview.chromium.org/1923433002/diff/450001/net/cert/internal/path...
File net/cert/internal/path_builder_pkits_unittest.cc (right):

https://codereview.chromium.org/1923433002/diff/450001/net/cert/internal/path...
net/cert/internal/path_builder_pkits_unittest.cc:96: if (rv ==
CompletionStatus::ASYNC) {
On 2016/06/17 01:03:23, eroman wrote:
> Is this exercised currently?

nope. Changed to just do synchronous-only in this test.

[eroman, 2016-06-20 19:54:19]

https://codereview.chromium.org/1923433002/diff/450001/net/cert/internal/path...
File net/cert/internal/path_builder.h (right):

https://codereview.chromium.org/1923433002/diff/450001/net/cert/internal/path...
net/cert/internal/path_builder.h:83: void AddCertIssuerSource(CertIssuerSource*
cert_issuer_source);
On 2016/06/18 04:28:56, mattm wrote:
> On 2016/06/17 01:03:22, eroman wrote:
> > todo: interface is a bit squirly (destruction, completion, don't call twice,
> > etc.)
> 
> Is this a leftover comment? since AddCertIssuerSource can be called twice..

Yes sorry, disregard this.

I was a TODO for myself when reviewing, as I didn't understand how everything
fit together. I tend to do a quick pass through CLs leaving notes for myself on
what to look at in more detail, and then do another pass to resolve what I
wanted to dig deeper on.

In this case I forgot to delete this before publishing :)

[eroman, 2016-06-27 19:58:52]

https://codereview.chromium.org/1923433002/diff/530001/components/cast_certif...
File components/cast_certificate/cast_cert_validator.cc (right):

https://codereview.chromium.org/1923433002/diff/530001/components/cast_certif...
components/cast_certificate/cast_cert_validator.cc:267: bool
VerifyDeviceCert(const std::vector<std::string>& certs,
Can you update the documentation in
components/cast_certificate/cast_cert_validator.h to indicate the weaker
requirements on |certs| now? (Or if you don't want to change the API guarantees
yet for full path building then leave a TODO).

https://codereview.chromium.org/1923433002/diff/530001/components/cast_certif...
components/cast_certificate/cast_cert_validator.cc:285: for (size_t i = 1; i <
certs.size(); ++i) {
optional: How about starting at i=0 and handle the target cert in here too? It
avoids duplicating the ugly calls to CreateFromCertificateData(), and the return
false above.

https://codereview.chromium.org/1923433002/diff/530001/components/cast_certif...
components/cast_certificate/cast_cert_validator.cc:299: // Do RFC 5280
compatible certificate verification using the two Cast
Should this comment be expanded to mention path building?

https://codereview.chromium.org/1923433002/diff/530001/net/cert/internal/path...
File net/cert/internal/path_builder.cc (right):

https://codereview.chromium.org/1923433002/diff/530001/net/cert/internal/path...
net/cert/internal/path_builder.cc:55: // The |cert| data is not copied, Remove
must be called before the |cert| data
These interdependencies are really hard to understand when reviewing (the
various use of non-owning StringPiece).

I am concerned that we will change code and cause a user-after-free at some
point.

Do you have a suggestion on making this more robust to changes?

https://codereview.chromium.org/1923433002/diff/530001/net/cert/internal/path...
net/cert/internal/path_builder.cc:59: if (present_certs_.find(key) !=
present_certs_.end())
Don't think the .find() is needed here, set insertion already returns that.
Can prolly be a one-liner:

return present_certs_.insert(GetKey()).second;

https://codereview.chromium.org/1923433002/diff/530001/net/cert/internal/path...
File net/cert/internal/path_builder.h (right):

https://codereview.chromium.org/1923433002/diff/530001/net/cert/internal/path...
net/cert/internal/path_builder.h:56: // A net error code result of attempting to
verify this path.
I personally find these blocks of text easier when there are spaces between
chunks. Not sure what the style guide says on this, so don't want to come across
as a jerk pointing these out everywhere I see them in case it is purely an
optional stylistic thing.

https://codereview.chromium.org/1923433002/diff/530001/net/cert/internal/path...
net/cert/internal/path_builder.h:59: int rv = ERR_UNEXPECTED;
instead of "rv" how about "error" or "status" or "result".  Result::result()
suggests this should be called "result"

https://codereview.chromium.org/1923433002/diff/530001/net/cert/internal/path...
net/cert/internal/path_builder.h:62: // Provides the results of the path
building attempt.
How about expanding this:

Provides the overall result of path building. This includes the paths that were
attempted.

https://codereview.chromium.org/1923433002/diff/530001/net/cert/internal/path...
net/cert/internal/path_builder.h:97:
CertPathBuilder(scoped_refptr<ParsedCertificate> cert,
What is the design tradeoff for having the parameters in ctor rather than Run()
?

https://codereview.chromium.org/1923433002/diff/530001/net/cert/internal/path...
net/cert/internal/path_builder.h:127: // and the output Result will be in an
undefined state.
How about deleting CertPathBuilder within the completion callback, is that
permitted by the API?

https://codereview.chromium.org/1923433002/diff/530001/net/cert/internal/path...
net/cert/internal/path_builder.h:145: bool result);
can you rename "result" to something more like "success" / "is_success"

https://codereview.chromium.org/1923433002/diff/530001/net/cert/internal/path...
net/cert/internal/path_builder.h:154:
std::vector<scoped_refptr<ParsedCertificate>> next_path_;
Please document this.

https://codereview.chromium.org/1923433002/diff/530001/net/cert/internal/path...
File net/cert/internal/path_builder_pkits_unittest.cc (right):

https://codereview.chromium.org/1923433002/diff/530001/net/cert/internal/path...
net/cert/internal/path_builder_pkits_unittest.cc:51: using CertVector =
std::vector<scoped_refptr<ParsedCertificate>>;
This seems generally useful enough to have a net::ParsedCertificateList

(We already have a net::CertificateList for X509Certificate).

[mattm, 2016-06-27 23:43:02]

Patchset #27 (id:550001) has been deleted

[mattm, 2016-06-27 23:43:15]

Patchset #27 (id:570001) has been deleted

[mattm, 2016-06-27 23:45:45]

https://codereview.chromium.org/1923433002/diff/530001/components/cast_certif...
File components/cast_certificate/cast_cert_validator.cc (right):

https://codereview.chromium.org/1923433002/diff/530001/components/cast_certif...
components/cast_certificate/cast_cert_validator.cc:267: bool
VerifyDeviceCert(const std::vector<std::string>& certs,
On 2016/06/27 19:58:52, eroman wrote:
> Can you update the documentation in
> components/cast_certificate/cast_cert_validator.h to indicate the weaker
> requirements on |certs| now? (Or if you don't want to change the API
guarantees
> yet for full path building then leave a TODO).

Done.

https://codereview.chromium.org/1923433002/diff/530001/components/cast_certif...
components/cast_certificate/cast_cert_validator.cc:285: for (size_t i = 1; i <
certs.size(); ++i) {
On 2016/06/27 19:58:52, eroman wrote:
> optional: How about starting at i=0 and handle the target cert in here too? It
> avoids duplicating the ugly calls to CreateFromCertificateData(), and the
return
> false above.

Done.

https://codereview.chromium.org/1923433002/diff/530001/components/cast_certif...
components/cast_certificate/cast_cert_validator.cc:299: // Do RFC 5280
compatible certificate verification using the two Cast
On 2016/06/27 19:58:52, eroman wrote:
> Should this comment be expanded to mention path building?

Done.

https://codereview.chromium.org/1923433002/diff/530001/net/cert/internal/path...
File net/cert/internal/path_builder.cc (right):

https://codereview.chromium.org/1923433002/diff/530001/net/cert/internal/path...
net/cert/internal/path_builder.cc:55: // The |cert| data is not copied, Remove
must be called before the |cert| data
On 2016/06/27 19:58:52, eroman wrote:
> These interdependencies are really hard to understand when reviewing (the
> various use of non-owning StringPiece).
> 
> I am concerned that we will change code and cause a user-after-free at some
> point.
> 
> Do you have a suggestion on making this more robust to changes?

I gave it a shot. Changed this class to also manage the
std::vector<std::unique_ptr<CertIssuersIter>>, thus it can ensure that the two
containers are consistent.

https://codereview.chromium.org/1923433002/diff/530001/net/cert/internal/path...
net/cert/internal/path_builder.cc:59: if (present_certs_.find(key) !=
present_certs_.end())
On 2016/06/27 19:58:52, eroman wrote:
> Don't think the .find() is needed here, set insertion already returns that.
> Can prolly be a one-liner:
> 
> return present_certs_.insert(GetKey()).second;

Acknowledged. (Bit different in new code.)

https://codereview.chromium.org/1923433002/diff/530001/net/cert/internal/path...
File net/cert/internal/path_builder.h (right):

https://codereview.chromium.org/1923433002/diff/530001/net/cert/internal/path...
net/cert/internal/path_builder.h:56: // A net error code result of attempting to
verify this path.
On 2016/06/27 19:58:52, eroman wrote:
> I personally find these blocks of text easier when there are spaces between
> chunks. Not sure what the style guide says on this, so don't want to come
across
> as a jerk pointing these out everywhere I see them in case it is purely an
> optional stylistic thing.

Done.

https://codereview.chromium.org/1923433002/diff/530001/net/cert/internal/path...
net/cert/internal/path_builder.h:59: int rv = ERR_UNEXPECTED;
On 2016/06/27 19:58:52, eroman wrote:
> instead of "rv" how about "error" or "status" or "result".  Result::result()
> suggests this should be called "result"

Yeah I should have renamed this. Though I didn't really like the Result::result
name either. Maybe I'll change them both.

https://codereview.chromium.org/1923433002/diff/530001/net/cert/internal/path...
net/cert/internal/path_builder.h:62: // Provides the results of the path
building attempt.
On 2016/06/27 19:58:52, eroman wrote:
> How about expanding this:
> 
> Provides the overall result of path building. This includes the paths that
were
> attempted.

Done.

https://codereview.chromium.org/1923433002/diff/530001/net/cert/internal/path...
net/cert/internal/path_builder.h:97:
CertPathBuilder(scoped_refptr<ParsedCertificate> cert,
On 2016/06/27 19:58:52, eroman wrote:
> What is the design tradeoff for having the parameters in ctor rather than
Run()
> ?

They're all stored in members so putting in the constructor seemed natural, but
I don't have a strong feeling one way or another. I guess putting in the
constructor also reinforces that the object is only used for a single
verification, whereas if they were passed in to Run() someone might think they
could call it again with different args.

https://codereview.chromium.org/1923433002/diff/530001/net/cert/internal/path...
net/cert/internal/path_builder.h:127: // and the output Result will be in an
undefined state.
On 2016/06/27 19:58:52, eroman wrote:
> How about deleting CertPathBuilder within the completion callback, is that
> permitted by the API?

Yes, added that to the comment.

https://codereview.chromium.org/1923433002/diff/530001/net/cert/internal/path...
net/cert/internal/path_builder.h:145: bool result);
On 2016/06/27 19:58:52, eroman wrote:
> can you rename "result" to something more like "success" / "is_success"

Done.

https://codereview.chromium.org/1923433002/diff/530001/net/cert/internal/path...
net/cert/internal/path_builder.h:154:
std::vector<scoped_refptr<ParsedCertificate>> next_path_;
On 2016/06/27 19:58:52, eroman wrote:
> Please document this.

Done.

https://codereview.chromium.org/1923433002/diff/530001/net/cert/internal/path...
File net/cert/internal/path_builder_pkits_unittest.cc (right):

https://codereview.chromium.org/1923433002/diff/530001/net/cert/internal/path...
net/cert/internal/path_builder_pkits_unittest.cc:51: using CertVector =
std::vector<scoped_refptr<ParsedCertificate>>;
On 2016/06/27 19:58:52, eroman wrote:
> This seems generally useful enough to have a net::ParsedCertificateList
> 
> (We already have a net::CertificateList for X509Certificate).

Done.

[eroman, 2016-07-01 23:49:29]

Thanks Matt for bearing through this long review!

 * Can you update the CL description with more details on what this implements
(and how).

I have some more design comments, but I think it will be more productive to
address any further feedback from me in follow-up CLs and get this one landed
sooner rather than later :)

LGTM.

https://codereview.chromium.org/1923433002/diff/590001/components/cast_certif...
File components/cast_certificate/cast_cert_validator.h (right):

https://codereview.chromium.org/1923433002/diff/590001/components/cast_certif...
components/cast_certificate/cast_cert_validator.h:58: //   * |certs[1..n-1]| are
intermediates certificates to use in path building.
"Their ordering does not matter".

https://codereview.chromium.org/1923433002/diff/590001/net/cert/internal/cert...
File net/cert/internal/cert_issuer_source.h (right):

https://codereview.chromium.org/1923433002/diff/590001/net/cert/internal/cert...
net/cert/internal/cert_issuer_source.h:18: using ParsedCertificateList =
std::vector<scoped_refptr<ParsedCertificate>>;
Are you duplicating the definition here to avoid #include-ing
parsed_certificate.h?

I think it would be better to just #include it and have the one definition.

https://codereview.chromium.org/1923433002/diff/590001/net/cert/internal/path...
File net/cert/internal/path_builder.cc (right):

https://codereview.chromium.org/1923433002/diff/590001/net/cert/internal/path...
net/cert/internal/path_builder.cc:347: // ASYNC is returned and
|async_ready_callback| will be called once
|callback|

https://codereview.chromium.org/1923433002/diff/590001/net/cert/internal/path...
net/cert/internal/path_builder.cc:370: scoped_refptr<ParsedCertificate>
next_cert_;
Please add descriptions for these. Especially |cur_path_| which is not obvious
(it is not a cert path, but rather ordered list of iterators).

https://codereview.chromium.org/1923433002/diff/590001/net/cert/internal/path...
net/cert/internal/path_builder.cc:428: result = DoBackTrack();
DESIGN: This does a depth-first exploration of the
paths. So it may block waiting for retrieving (async) issuers even
though another path could be explored that does not require blocking
right?

I don't want to block you landing this CL -- we can continue exploring this
as a follow-up, since having something landed is more useful for
collaboration.

But here are my thoughts...

The current design if I understand looks sort of like this:
   
{cert_issuers_iter1, cert_issuers_iter2, ..., cert_issuers_iterN}

A single certificate is pulled from each cert_issuers_iter, added
to the path, and then the subsequent issuers added. Once all the issuers
have been consumed the array unwinds (backtracks) and continues building
forward again.

The downsides of this approach are:
  * Necessarily depth first exploration, even when some issuers in the
    path may require waiting for async retrieval.
  * Prioritization is done by which issuer to explore next, not by which
    path to continue building next.

I could imagine instead keeping a work queue of:
   {<partial path>, <async_issuers iterator>}.

Then exploring the graph using a work queue similar to:

 {
   {partial_path1, cert_issuers_iter1},
   {partial_path2, cert_issuers_iter2},
   ..
   {partial_pathN, cert_issuers_iterN},
 }

 The builder would select the highest priority partial_path from that set,
 and try to get the next cert in the path from the issuers iterator. As it
 gets results synchronously/asynchronously it adds corresponding partial
 paths to the work queue, and can keep expanding the highest priority partial
path of the work queue.

In this manner the cert_issuers_iterator wouldn't really need to worry about
sorting
its results anymore, as we would do it in the builder instead.

One downside of this approach is it necessarily uses more memory, since all the
partial_paths may have redundant leading paths (in the worst case would expand
the entire tree breadth-first) and store all those paths in memory.

On the other hand it gives more flexibility to avoid ever waiting for AIA
fetches, and to do prioritization on other factors.

https://codereview.chromium.org/1923433002/diff/590001/net/cert/internal/path...
net/cert/internal/path_builder.cc:453: // If the cert matches a trust root, this
is a (possible) complete path.
(possible) --> (possibly)

https://codereview.chromium.org/1923433002/diff/590001/net/cert/internal/path...
net/cert/internal/path_builder.cc:615: for (const auto& cert : path)
Instead of looping can this be: result_path->path = path

https://codereview.chromium.org/1923433002/diff/590001/net/cert/internal/path...
File net/cert/internal/path_builder.h (right):

https://codereview.chromium.org/1923433002/diff/590001/net/cert/internal/path...
net/cert/internal/path_builder.h:31: using ParsedCertificateList =
std::vector<scoped_refptr<ParsedCertificate>>;
Same here -- I think #include is better than duplication. If really concerned
about including can extract to parsed_certificate_list.h

https://codereview.chromium.org/1923433002/diff/590001/net/cert/internal/path...
File net/cert/internal/path_builder_unittest.cc (right):

https://codereview.chromium.org/1923433002/diff/590001/net/cert/internal/path...
net/cert/internal/path_builder_unittest.cc:45: ParsedCertificateList&& issuers)
side-comment: Seems legit, although not sure if style guide allows for this yet.

https://codereview.chromium.org/1923433002/diff/590001/net/cert/internal/path...
net/cert/internal/path_builder_unittest.cc:125: std::vector<std::string>* chain,
Should we randomize the order of the intermediates in some some place before
instantiating the certissuerssources ?

https://codereview.chromium.org/1923433002/diff/590001/net/cert/internal/path...
net/cert/internal/path_builder_unittest.cc:269: sync_certs.AddCert(a_by_b_);
Does this have an effect on path building, or just included as an extra?

https://codereview.chromium.org/1923433002/diff/590001/net/cert/internal/path...
net/cert/internal/path_builder_unittest.cc:274: async_certs.AddCert(b_by_c_);
What would happen if b_by_c were returned synchronously first?

I think in that case we would do the async c_by_e instead of finding the
synchronous path b_by_f right?

https://codereview.chromium.org/1923433002/diff/590001/net/cert/internal/path...
net/cert/internal/path_builder_unittest.cc:451: scoped_refptr<ParsedCertificate>
target_, oldintermediary_, newintermediary_,
nit: one per line

https://codereview.chromium.org/1923433002/diff/590001/net/cert/internal/path...
net/cert/internal/path_builder_unittest.cc:465: // Old intermediary cert is not
provided, so the pathbuilder will need to go
Not sure if one is more correct than another,
but I think the more common naming is "intermediate" rather than "intermediary".

(Even though in my own test data I have apparently been typing intermediary).

https://codereview.chromium.org/1923433002/diff/590001/net/cert/internal/trus...
File net/cert/internal/trust_store.h (right):

https://codereview.chromium.org/1923433002/diff/590001/net/cert/internal/trus...
net/cert/internal/trust_store.h:22: using ParsedCertificateList =
std::vector<scoped_refptr<ParsedCertificate>>;
same comment as earlier.

https://codereview.chromium.org/1923433002/diff/590001/net/cert/internal/veri...
File net/cert/internal/verify_certificate_chain.h (right):

https://codereview.chromium.org/1923433002/diff/590001/net/cert/internal/veri...
net/cert/internal/verify_certificate_chain.h:24: using ParsedCertificateList =
std::vector<scoped_refptr<ParsedCertificate>>;
Same comment as earlier.

[mattm, 2016-07-02 01:15:52]

Description was changed from

==========
Certificate path builder

BUG=410574
==========

to

==========
Certificate path builder for new certificate verification library

Builds paths from a target certificate to a trust anchor and attempts to verify
them according to RFC 5280. Supports asynchronous intermediate lookups (eg, AIA
fetching) and backtracking.

BUG=410574
==========

[mattm, 2016-07-02 02:18:59]

Description was changed from

==========
Certificate path builder for new certificate verification library

Builds paths from a target certificate to a trust anchor and attempts to verify
them according to RFC 5280. Supports asynchronous intermediate lookups (eg, AIA
fetching) and backtracking.

BUG=410574
==========

to

==========
Certificate path builder for new certificate verification library

Builds paths from a target certificate to a trust anchor and attempts to verify
them according to RFC 5280. Supports asynchronous intermediate lookups (eg, AIA
fetching) and backtracking.

This implementation uses a depth-first strategy which is simple and uses minimal
resources, but may not be optimal.

BUG=410574
==========

[mattm, 2016-07-02 02:21:52]

https://codereview.chromium.org/1923433002/diff/590001/components/cast_certif...
File components/cast_certificate/cast_cert_validator.h (right):

https://codereview.chromium.org/1923433002/diff/590001/components/cast_certif...
components/cast_certificate/cast_cert_validator.h:58: //   * |certs[1..n-1]| are
intermediates certificates to use in path building.
On 2016/07/01 23:49:29, eroman wrote:
> "Their ordering does not matter".

Done.

https://codereview.chromium.org/1923433002/diff/590001/net/cert/internal/cert...
File net/cert/internal/cert_issuer_source.h (right):

https://codereview.chromium.org/1923433002/diff/590001/net/cert/internal/cert...
net/cert/internal/cert_issuer_source.h:18: using ParsedCertificateList =
std::vector<scoped_refptr<ParsedCertificate>>;
On 2016/07/01 23:49:29, eroman wrote:
> Are you duplicating the definition here to avoid #include-ing
> parsed_certificate.h?

Yeah.
 
> I think it would be better to just #include it and have the one definition.

Done.

https://codereview.chromium.org/1923433002/diff/590001/net/cert/internal/path...
File net/cert/internal/path_builder.cc (right):

https://codereview.chromium.org/1923433002/diff/590001/net/cert/internal/path...
net/cert/internal/path_builder.cc:347: // ASYNC is returned and
|async_ready_callback| will be called once
On 2016/07/01 23:49:29, eroman wrote:
> |callback|

Done.

https://codereview.chromium.org/1923433002/diff/590001/net/cert/internal/path...
net/cert/internal/path_builder.cc:370: scoped_refptr<ParsedCertificate>
next_cert_;
On 2016/07/01 23:49:29, eroman wrote:
> Please add descriptions for these. Especially |cur_path_| which is not obvious
> (it is not a cert path, but rather ordered list of iterators).

Done.

https://codereview.chromium.org/1923433002/diff/590001/net/cert/internal/path...
net/cert/internal/path_builder.cc:428: result = DoBackTrack();
On 2016/07/01 23:49:29, eroman wrote:
> DESIGN: This does a depth-first exploration of the
> paths. So it may block waiting for retrieving (async) issuers even
> though another path could be explored that does not require blocking
> right?

Correct.

> I don't want to block you landing this CL -- we can continue exploring this
> as a follow-up, since having something landed is more useful for
> collaboration.
> 
> But here are my thoughts...
> 
> The current design if I understand looks sort of like this:
>    
> {cert_issuers_iter1, cert_issuers_iter2, ..., cert_issuers_iterN}
> 
> A single certificate is pulled from each cert_issuers_iter, added
> to the path, and then the subsequent issuers added. Once all the issuers
> have been consumed the array unwinds (backtracks) and continues building
> forward again.
> 
> The downsides of this approach are:
>   * Necessarily depth first exploration, even when some issuers in the
>     path may require waiting for async retrieval.
>   * Prioritization is done by which issuer to explore next, not by which
>     path to continue building next.
> 
> I could imagine instead keeping a work queue of:
>    {<partial path>, <async_issuers iterator>}.
> 
> Then exploring the graph using a work queue similar to:
> 
>  {
>    {partial_path1, cert_issuers_iter1},
>    {partial_path2, cert_issuers_iter2},
>    ..
>    {partial_pathN, cert_issuers_iterN},
>  }
> 
>  The builder would select the highest priority partial_path from that set,
>  and try to get the next cert in the path from the issuers iterator. As it
>  gets results synchronously/asynchronously it adds corresponding partial
>  paths to the work queue, and can keep expanding the highest priority partial
> path of the work queue.
> 
> In this manner the cert_issuers_iterator wouldn't really need to worry about
> sorting
> its results anymore, as we would do it in the builder instead.
> 
> One downside of this approach is it necessarily uses more memory, since all
the
> partial_paths may have redundant leading paths (in the worst case would expand
> the entire tree breadth-first) and store all those paths in memory.
> 
> On the other hand it gives more flexibility to avoid ever waiting for AIA
> fetches, and to do prioritization on other factors.

Yeah, we can certainly consider something like that. I wanted to get something
working so we can make some progress without trying to get the most optimal and
complex solution right out of the gate :)  Though in some ways that approach is
simpler since there is no explicit backtracking step. Just sticking things in
the queue and pulling things out, so that is nice.

https://codereview.chromium.org/1923433002/diff/590001/net/cert/internal/path...
net/cert/internal/path_builder.cc:453: // If the cert matches a trust root, this
is a (possible) complete path.
On 2016/07/01 23:49:29, eroman wrote:
> (possible) --> (possibly)

Done.

https://codereview.chromium.org/1923433002/diff/590001/net/cert/internal/path...
net/cert/internal/path_builder.cc:615: for (const auto& cert : path)
On 2016/07/01 23:49:29, eroman wrote:
> Instead of looping can this be: result_path->path = path

Done.

https://codereview.chromium.org/1923433002/diff/590001/net/cert/internal/path...
File net/cert/internal/path_builder.h (right):

https://codereview.chromium.org/1923433002/diff/590001/net/cert/internal/path...
net/cert/internal/path_builder.h:31: using ParsedCertificateList =
std::vector<scoped_refptr<ParsedCertificate>>;
On 2016/07/01 23:49:29, eroman wrote:
> Same here -- I think #include is better than duplication. If really concerned
> about including can extract to parsed_certificate_list.h

Done.

https://codereview.chromium.org/1923433002/diff/590001/net/cert/internal/path...
File net/cert/internal/path_builder_unittest.cc (right):

https://codereview.chromium.org/1923433002/diff/590001/net/cert/internal/path...
net/cert/internal/path_builder_unittest.cc:45: ParsedCertificateList&& issuers)
On 2016/07/01 23:49:29, eroman wrote:
> side-comment: Seems legit, although not sure if style guide allows for this
yet.

seems to be: https://chromium-cpp.appspot.com/  (Rvalue References section)

https://codereview.chromium.org/1923433002/diff/590001/net/cert/internal/path...
net/cert/internal/path_builder_unittest.cc:125: std::vector<std::string>* chain,
On 2016/07/01 23:49:29, eroman wrote:
> Should we randomize the order of the intermediates in some some place before
> instantiating the certissuerssources ?

Probably not actual randomization (since even if it did find a problem, no one
likes flakiness), but some tests that intentionally try different orders is a
reasonable idea. I added a simple one.

https://codereview.chromium.org/1923433002/diff/590001/net/cert/internal/path...
net/cert/internal/path_builder_unittest.cc:269: sync_certs.AddCert(a_by_b_);
On 2016/07/01 23:49:29, eroman wrote:
> Does this have an effect on path building, or just included as an extra?

No effect. I don't remember if that was on purpose or not.. I'll just remove it.

https://codereview.chromium.org/1923433002/diff/590001/net/cert/internal/path...
net/cert/internal/path_builder_unittest.cc:274: async_certs.AddCert(b_by_c_);
On 2016/07/01 23:49:29, eroman wrote:
> What would happen if b_by_c were returned synchronously first?
> 
> I think in that case we would do the async c_by_e instead of finding the
> synchronous path b_by_f right?

Yes.

https://codereview.chromium.org/1923433002/diff/590001/net/cert/internal/path...
net/cert/internal/path_builder_unittest.cc:451: scoped_refptr<ParsedCertificate>
target_, oldintermediary_, newintermediary_,
On 2016/07/01 23:49:29, eroman wrote:
> nit: one per line

Done.

https://codereview.chromium.org/1923433002/diff/590001/net/cert/internal/path...
net/cert/internal/path_builder_unittest.cc:465: // Old intermediary cert is not
provided, so the pathbuilder will need to go
On 2016/07/01 23:49:29, eroman wrote:
> Not sure if one is more correct than another,
> but I think the more common naming is "intermediate" rather than
"intermediary".
> 
> (Even though in my own test data I have apparently been typing intermediary).

Done.

https://codereview.chromium.org/1923433002/diff/590001/net/cert/internal/trus...
File net/cert/internal/trust_store.h (right):

https://codereview.chromium.org/1923433002/diff/590001/net/cert/internal/trus...
net/cert/internal/trust_store.h:22: using ParsedCertificateList =
std::vector<scoped_refptr<ParsedCertificate>>;
On 2016/07/01 23:49:29, eroman wrote:
> same comment as earlier.

Done.

https://codereview.chromium.org/1923433002/diff/590001/net/cert/internal/veri...
File net/cert/internal/verify_certificate_chain.h (right):

https://codereview.chromium.org/1923433002/diff/590001/net/cert/internal/veri...
net/cert/internal/verify_certificate_chain.h:24: using ParsedCertificateList =
std::vector<scoped_refptr<ParsedCertificate>>;
On 2016/07/01 23:49:29, eroman wrote:
> Same comment as earlier.

Done.

[mattm, 2016-07-02 02:23:32]

mattm@chromium.org changed reviewers:
+ sheretov@chromium.org

[mattm, 2016-07-02 02:23:34]

sheretov: please review cast changes, thanks!

[sheretov, 2016-07-07 15:38:55]

components/cast_certificate/ changes lgtm

[eroman, 2016-07-07 18:15:40]

The CQ bit was checked by eroman@chromium.org

[eroman, 2016-07-07 18:15:41]

The patchset sent to the CQ was uploaded after l-g-t-m from eroman@chromium.org
Link to the patchset: https://codereview.chromium.org/1923433002/#ps630001
(title: "changes for review comment #20")

[commit-bot: I haz the power, 2016-07-07 18:16:44]

CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-07-07 22:05:51]

Description was changed from

==========
Certificate path builder for new certificate verification library

Builds paths from a target certificate to a trust anchor and attempts to verify
them according to RFC 5280. Supports asynchronous intermediate lookups (eg, AIA
fetching) and backtracking.

This implementation uses a depth-first strategy which is simple and uses minimal
resources, but may not be optimal.

BUG=410574
==========

to

==========
Certificate path builder for new certificate verification library

Builds paths from a target certificate to a trust anchor and attempts to verify
them according to RFC 5280. Supports asynchronous intermediate lookups (eg, AIA
fetching) and backtracking.

This implementation uses a depth-first strategy which is simple and uses minimal
resources, but may not be optimal.

BUG=410574
==========

[commit-bot: I haz the power, 2016-07-07 22:05:53]

Committed patchset #29 (id:630001)

[commit-bot: I haz the power, 2016-07-07 22:08:51]

Description was changed from

==========
Certificate path builder for new certificate verification library

Builds paths from a target certificate to a trust anchor and attempts to verify
them according to RFC 5280. Supports asynchronous intermediate lookups (eg, AIA
fetching) and backtracking.

This implementation uses a depth-first strategy which is simple and uses minimal
resources, but may not be optimal.

BUG=410574
==========

to

==========
Certificate path builder for new certificate verification library

Builds paths from a target certificate to a trust anchor and attempts to verify
them according to RFC 5280. Supports asynchronous intermediate lookups (eg, AIA
fetching) and backtracking.

This implementation uses a depth-first strategy which is simple and uses minimal
resources, but may not be optimal.

BUG=410574

Committed: https://crrev.com/76f636098ccda9f283614545352b4964e7ec2b5c
Cr-Commit-Position: refs/heads/master@{#404239}
==========

[commit-bot: I haz the power, 2016-07-07 22:08:52]

Patchset 29 (id:??) landed as
https://crrev.com/76f636098ccda9f283614545352b4964e7ec2b5c
Cr-Commit-Position: refs/heads/master@{#404239}