java/6 : sun/security/provider/certpath/SunCertPathBuilder.java

SunCertPathBuilder
https://openjdk.java.net/
GPLv2 + Classpath Exception
/*
 * Copyright (c) 2000, 2017, Oracle and/or its affiliates. All rights reserved.
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 *
 * This code is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License version 2 only, as
 * published by the Free Software Foundation.  Oracle designates this
 * particular file as subject to the "Classpath" exception as provided
 * by Oracle in the LICENSE file that accompanied this code.
 *
 * This code is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 * version 2 for more details (a copy is included in the LICENSE file that
 * accompanied this code).
 *
 * You should have received a copy of the GNU General Public License version
 * 2 along with this work; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 * or visit www.oracle.com if you need additional information or have any
 * questions.
 */

package sun.security.provider.certpath;

import java.io.IOException;
import java.security.AccessController;
import java.security.GeneralSecurityException;
import java.security.InvalidAlgorithmParameterException;
import java.security.Principal;
import java.security.PublicKey;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.LinkedList;
import java.util.Set;

import java.security.cert.*;
import java.security.interfaces.DSAPublicKey;

import javax.security.auth.x500.X500Principal;

import sun.security.action.GetBooleanSecurityPropertyAction;
import sun.security.x509.X500Name;
import sun.security.x509.PKIXExtensions;
import sun.security.util.Debug;

This class is able to build certification paths in either the forward
or reverse directions.
 If successful, it returns a certification path which has succesfully
satisfied all the constraints and requirements specified in the
PKIXBuilderParameters object and has been validated according to the PKIX
path validation algorithm defined in RFC 5280.
 This implementation uses a depth-first search approach to finding
certification paths. If it comes to a point in which it cannot find
any more certificates leading to the target OR the path length is too long
it backtracks to previous paths until the target has been found or
all possible paths have been exhausted.
 This implementation is not thread-safe.
Author:      Sean Mullan,      Yassir Elley
Since:       1.4/**
 * This class is able to build certification paths in either the forward
 * or reverse directions.
 *
 * <p> If successful, it returns a certification path which has succesfully
 * satisfied all the constraints and requirements specified in the
 * PKIXBuilderParameters object and has been validated according to the PKIX
 * path validation algorithm defined in RFC 5280.
 *
 * <p> This implementation uses a depth-first search approach to finding
 * certification paths. If it comes to a point in which it cannot find
 * any more certificates leading to the target OR the path length is too long
 * it backtracks to previous paths until the target has been found or
 * all possible paths have been exhausted.
 *
 * <p> This implementation is not thread-safe.
 *
 * @since       1.4
 * @author      Sean Mullan
 * @author      Yassir Elley
 */
public final class SunCertPathBuilder extends CertPathBuilderSpi {

    private static final Debug debug = Debug.getInstance("certpath");

    /*
     * private objects shared by methods
     */
    private PKIXBuilderParameters buildParams;
    private CertificateFactory cf;
    private boolean pathCompleted = false;
    private X500Principal targetSubjectDN;
    private PolicyNode policyTreeResult;
    private TrustAnchor trustAnchor;
    private PublicKey finalPublicKey;
    private X509CertSelector targetSel;
    private List<CertStore> orderedCertStores;
    private boolean onlyEECert = false;

    Create an instance of SunCertPathBuilder.
Throws: CertPathBuilderException – if an error occurs/**
     * Create an instance of <code>SunCertPathBuilder</code>.
     *
     * @throws CertPathBuilderException if an error occurs
     */
    public SunCertPathBuilder() throws CertPathBuilderException {
        try {
            cf = CertificateFactory.getInstance("X.509");
        } catch (CertificateException e) {
            throw new CertPathBuilderException(e);
        }
        onlyEECert = AccessController.doPrivileged(
            new GetBooleanSecurityPropertyAction
                ("com.sun.security.onlyCheckRevocationOfEECert"));
    }

    Attempts to build a certification path using the Sun build
algorithm from a trusted anchor(s) to a target subject, which must both
be specified in the input parameter set. By default, this method will
attempt to build in the forward direction. In order to build in the
reverse direction, the caller needs to pass in an instance of
SunCertPathBuilderParameters with the buildForward flag set to false.
The certification path that is constructed is validated
according to the PKIX specification.
Params: params – the parameter set for building a path. Must be an instance
 of PKIXBuilderParameters.
Throws: CertPathBuilderException – Exception thrown if builder is
 unable to build a complete certification path from the trusted anchor(s)
 to the target subject.
InvalidAlgorithmParameterException – if the given parameters are
 inappropriate for this certification path builder.
Returns: a certification path builder result./**
     * Attempts to build a certification path using the Sun build
     * algorithm from a trusted anchor(s) to a target subject, which must both
     * be specified in the input parameter set. By default, this method will
     * attempt to build in the forward direction. In order to build in the
     * reverse direction, the caller needs to pass in an instance of
     * SunCertPathBuilderParameters with the buildForward flag set to false.
     *
     * <p>The certification path that is constructed is validated
     * according to the PKIX specification.
     *
     * @param params the parameter set for building a path. Must be an instance
     *  of <code>PKIXBuilderParameters</code>.
     * @return a certification path builder result.
     * @exception CertPathBuilderException Exception thrown if builder is
     *  unable to build a complete certification path from the trusted anchor(s)
     *  to the target subject.
     * @throws InvalidAlgorithmParameterException if the given parameters are
     *  inappropriate for this certification path builder.
     */
    public CertPathBuilderResult engineBuild(CertPathParameters params)
        throws CertPathBuilderException, InvalidAlgorithmParameterException {

        if (debug != null) {
            debug.println("SunCertPathBuilder.engineBuild(" + params + ")");
        }

        if (!(params instanceof PKIXBuilderParameters)) {
            throw new InvalidAlgorithmParameterException("inappropriate " +
                "parameter type, must be an instance of PKIXBuilderParameters");
        }

        boolean buildForward = true;
        if (params instanceof SunCertPathBuilderParameters) {
            buildForward =
                ((SunCertPathBuilderParameters)params).getBuildForward();
        }

        buildParams = (PKIXBuilderParameters)params;

        /* Check mandatory parameters */

        // Make sure that none of the trust anchors include name constraints
        // (not supported).
        for (TrustAnchor anchor : buildParams.getTrustAnchors()) {
            if (anchor.getNameConstraints() != null) {
                throw new InvalidAlgorithmParameterException
                    ("name constraints in trust anchor not supported");
            }
        }

        CertSelector sel = buildParams.getTargetCertConstraints();
        if (!(sel instanceof X509CertSelector)) {
            throw new InvalidAlgorithmParameterException("the "
                + "targetCertConstraints parameter must be an "
                + "X509CertSelector");
        }
        targetSel = (X509CertSelector)sel;
        targetSubjectDN = targetSel.getSubject();
        if (targetSubjectDN == null) {
            X509Certificate targetCert = targetSel.getCertificate();
            if (targetCert != null) {
                targetSubjectDN = targetCert.getSubjectX500Principal();
            }
        }
        // reorder CertStores so that local CertStores are tried first
        orderedCertStores =
            new ArrayList<CertStore>(buildParams.getCertStores());
        Collections.sort(orderedCertStores, new CertStoreComparator());
        if (targetSubjectDN == null) {
            targetSubjectDN = getTargetSubjectDN(orderedCertStores, targetSel);
        }
        if (targetSubjectDN == null) {
            throw new InvalidAlgorithmParameterException
                ("Could not determine unique target subject");
        }

        List<List<Vertex>> adjList = new ArrayList<List<Vertex>>();
        CertPathBuilderResult result =
            buildCertPath(buildForward, false, adjList);
        if (result == null) {
            if (debug != null) {
                debug.println("SunCertPathBuilder.engineBuild: 2nd pass");
            }
            // try again
            adjList.clear();
            result = buildCertPath(buildForward, true, adjList);
            if (result == null) {
                throw new SunCertPathBuilderException("unable to find valid "
                    + "certification path to requested target",
                    new AdjacencyList(adjList));
            }
        }
        return result;
    }

    private CertPathBuilderResult buildCertPath(boolean buildForward,
        boolean searchAllCertStores, List<List<Vertex>> adjList)
        throws CertPathBuilderException {

        // Init shared variables and build certification path
        pathCompleted = false;
        trustAnchor = null;
        finalPublicKey = null;
        policyTreeResult = null;
        LinkedList<X509Certificate> certPathList =
            new LinkedList<X509Certificate>();
        try {
            if (buildForward) {
                buildForward(adjList, certPathList, searchAllCertStores);
            } else {
                buildReverse(adjList, certPathList);
            }
        } catch (Exception e) {
            if (debug != null) {
                debug.println("SunCertPathBuilder.engineBuild() exception in "
                    + "build");
                e.printStackTrace();
            }
            throw new SunCertPathBuilderException("unable to find valid "
                + "certification path to requested target", e,
                new AdjacencyList(adjList));
        }

        // construct SunCertPathBuilderResult
        try {
            if (pathCompleted) {
                if (debug != null)
                    debug.println("SunCertPathBuilder.engineBuild() "
                                  + "pathCompleted");

                // we must return a certpath which has the target
                // as the first cert in the certpath - i.e. reverse
                // the certPathList
                Collections.reverse(certPathList);

                return new SunCertPathBuilderResult(
                    cf.generateCertPath(certPathList), this.trustAnchor,
                    policyTreeResult, finalPublicKey,
                    new AdjacencyList(adjList));
            }
        } catch (Exception e) {
            if (debug != null) {
                debug.println("SunCertPathBuilder.engineBuild() exception "
                              + "in wrap-up");
                e.printStackTrace();
            }
            throw new SunCertPathBuilderException("unable to find valid "
                + "certification path to requested target", e,
                new AdjacencyList(adjList));
        }

        return null;
    }

    /*
     * Private build reverse method.
     *
     */
    private void buildReverse(List<List<Vertex>> adjacencyList,
        LinkedList<X509Certificate> certPathList) throws Exception
    {
        if (debug != null) {
            debug.println("SunCertPathBuilder.buildReverse()...");
            debug.println("SunCertPathBuilder.buildReverse() InitialPolicies: "
                + buildParams.getInitialPolicies());
        }

        ReverseState currentState = new ReverseState();
        /* Initialize adjacency list */
        adjacencyList.clear();
        adjacencyList.add(new LinkedList<Vertex>());

        /*
         * Perform a search using each trust anchor, until a valid
         * path is found
         */
        Iterator<TrustAnchor> iter = buildParams.getTrustAnchors().iterator();
        while (iter.hasNext()) {
            TrustAnchor anchor = iter.next();
            /* check if anchor satisfies target constraints */
            if (anchorIsTarget(anchor, targetSel)) {
                this.trustAnchor = anchor;
                this.pathCompleted = true;
                this.finalPublicKey = anchor.getTrustedCert().getPublicKey();
                break;
            }

            /* Initialize current state */
            currentState.initState(buildParams.getMaxPathLength(),
                       buildParams.isExplicitPolicyRequired(),
                       buildParams.isPolicyMappingInhibited(),
                       buildParams.isAnyPolicyInhibited(),
                       buildParams.getCertPathCheckers());
            currentState.updateState(anchor);
            // init the crl checker
            currentState.crlChecker =
                new CrlRevocationChecker(null, buildParams, null, onlyEECert);
            currentState.algorithmChecker = new AlgorithmChecker(anchor, null);
            currentState.untrustedChecker = new UntrustedChecker();
            try {
                depthFirstSearchReverse(null, currentState,
                new ReverseBuilder(buildParams, targetSubjectDN), adjacencyList,
                certPathList);
            } catch (Exception e) {
                // continue on error if more anchors to try
                if (iter.hasNext())
                    continue;
                else
                    throw e;
            }

            // break out of loop if search is successful
            if (pathCompleted) {
                break;
            }
        }

        if (debug != null) {
            debug.println("SunCertPathBuilder.buildReverse() returned from "
                + "depthFirstSearchReverse()");
            debug.println("SunCertPathBuilder.buildReverse() "
                + "certPathList.size: " + certPathList.size());
        }
    }

    /*
     * Private build forward method.
     */
    private void buildForward(List<List<Vertex>> adjacencyList,
        LinkedList<X509Certificate> certPathList, boolean searchAllCertStores)
        throws GeneralSecurityException, IOException
    {
        if (debug != null) {
            debug.println("SunCertPathBuilder.buildForward()...");
        }

        /* Initialize current state */
        ForwardState currentState = new ForwardState();
        currentState.initState(buildParams.getCertPathCheckers());

        /* Initialize adjacency list */
        adjacencyList.clear();
        adjacencyList.add(new LinkedList<Vertex>());

        // init the crl checker
        currentState.crlChecker
            = new CrlRevocationChecker(null, buildParams, null, onlyEECert);
        currentState.untrustedChecker = new UntrustedChecker();

        depthFirstSearchForward(targetSubjectDN, currentState,
          new ForwardBuilder
              (buildParams, targetSubjectDN, searchAllCertStores, onlyEECert),
          adjacencyList, certPathList);
    }

    /*
     * This method performs a depth first search for a certification
     * path while building forward which meets the requirements set in
     * the parameters object.
     * It uses an adjacency list to store all certificates which were
     * tried (i.e. at one time added to the path - they may not end up in
     * the final path if backtracking occurs). This information can
     * be used later to debug or demo the build.
     *
     * See "Data Structure and Algorithms, by Aho, Hopcroft, and Ullman"
     * for an explanation of the DFS algorithm.
     *
     * @param dN the distinguished name being currently searched for certs
     * @param currentState the current PKIX validation state
     */
    void depthFirstSearchForward(X500Principal dN, ForwardState currentState,
        ForwardBuilder builder, List<List<Vertex>> adjList,
        LinkedList<X509Certificate> certPathList)
        throws GeneralSecurityException, IOException
    {
        //XXX This method should probably catch & handle exceptions

        if (debug != null) {
            debug.println("SunCertPathBuilder.depthFirstSearchForward(" + dN
                + ", " + currentState.toString() + ")");
        }

        /*
         * Find all the certificates issued to dN which
         * satisfy the PKIX certification path constraints.
         */
        List<Vertex> vertices = addVertices
           (builder.getMatchingCerts(currentState, orderedCertStores), adjList);
        if (debug != null) {
            debug.println("SunCertPathBuilder.depthFirstSearchForward(): "
                + "certs.size=" + vertices.size());
        }

        /*
         * For each cert in the collection, verify anything
         * that hasn't been checked yet (signature, revocation, etc)
         * and check for loops. Call depthFirstSearchForward()
         * recursively for each good cert.
         */

               vertices:
        for (Vertex vertex : vertices) {
            /**
             * Restore state to currentState each time through the loop.
             * This is important because some of the user-defined
             * checkers modify the state, which MUST be restored if
             * the cert eventually fails to lead to the target and
             * the next matching cert is tried.
             */
            ForwardState nextState = (ForwardState) currentState.clone();
            X509Certificate cert = (X509Certificate) vertex.getCertificate();

            try {
                builder.verifyCert(cert, nextState, certPathList);
            } catch (GeneralSecurityException gse) {
                if (debug != null) {
                    debug.println("SunCertPathBuilder.depthFirstSearchForward()"
                        + ": validation failed: " + gse);
                    gse.printStackTrace();
                }
                vertex.setThrowable(gse);
                continue;
            }

            /*
             * Certificate is good.
             * If cert completes the path,
             *    process userCheckers that don't support forward checking
             *    and process policies over whole path
             *    and backtrack appropriately if there is a failure
             * else if cert does not complete the path,
             *    add it to the path
             */
            if (builder.isPathCompleted(cert)) {

                BasicChecker basicChecker = null;
                if (debug != null)
                    debug.println("SunCertPathBuilder.depthFirstSearchForward()"
                        + ": commencing final verification");

                ArrayList<X509Certificate> appendedCerts =
                    new ArrayList<X509Certificate>(certPathList);

                /*
                 * if the trust anchor selected is specified as a trusted
                 * public key rather than a trusted cert, then verify this
                 * cert (which is signed by the trusted public key), but
                 * don't add it yet to the certPathList
                 */
                if (builder.trustAnchor.getTrustedCert() == null) {
                    appendedCerts.add(0, cert);
                }

                HashSet<String> initExpPolSet = new HashSet<String>(1);
                initExpPolSet.add(PolicyChecker.ANY_POLICY);

                PolicyNodeImpl rootNode = new PolicyNodeImpl(null,
                    PolicyChecker.ANY_POLICY, null, false, initExpPolSet, false);

                PolicyChecker policyChecker
                    = new PolicyChecker(buildParams.getInitialPolicies(),
                                appendedCerts.size(),
                                buildParams.isExplicitPolicyRequired(),
                                buildParams.isPolicyMappingInhibited(),
                                buildParams.isAnyPolicyInhibited(),
                                buildParams.getPolicyQualifiersRejected(),
                                rootNode);

                List<PKIXCertPathChecker> userCheckers = new
                    ArrayList<PKIXCertPathChecker>
                        (buildParams.getCertPathCheckers());
                int mustCheck = 0;
                userCheckers.add(mustCheck, policyChecker);
                mustCheck++;

                String variant = null;

                if (buildParams instanceof  PKIXExtendedParameters) {
                    variant = ((PKIXExtendedParameters)buildParams).getVariant();
                }

                // add the algorithm checker
                userCheckers.add(mustCheck,
                        new AlgorithmChecker(builder.trustAnchor,
                                buildParams.getDate(), variant));
                mustCheck++;

                if (nextState.keyParamsNeeded()) {
                    PublicKey rootKey = cert.getPublicKey();
                    if (builder.trustAnchor.getTrustedCert() == null) {
                        rootKey = builder.trustAnchor.getCAPublicKey();
                        if (debug != null)
                            debug.println(
                                "SunCertPathBuilder.depthFirstSearchForward " +
                                "using buildParams public key: " +
                                rootKey.toString());
                    }
                    TrustAnchor anchor = new TrustAnchor
                        (cert.getSubjectX500Principal(), rootKey, null);

                    // add the basic checker
                    basicChecker = new BasicChecker(anchor,
                                           builder.date,
                                           buildParams.getSigProvider(),
                                           true);
                    userCheckers.add(mustCheck, basicChecker);
                    mustCheck++;

                    // add the crl revocation checker
                    if (buildParams.isRevocationEnabled()) {
                        userCheckers.add(mustCheck, new CrlRevocationChecker
                            (anchor, buildParams, null, onlyEECert));
                        mustCheck++;
                    }
                }
                // Why we don't need BasicChecker and CrlRevocationChecker
                // if nextState.keyParamsNeeded() is false?

                for (int i=0; i<appendedCerts.size(); i++) {
                    X509Certificate currCert = appendedCerts.get(i);
                    if (debug != null)
                        debug.println("current subject = "
                                      + currCert.getSubjectX500Principal());
                    Set<String> unresCritExts =
                        currCert.getCriticalExtensionOIDs();
                    if (unresCritExts == null) {
                        unresCritExts = Collections.<String>emptySet();
                    }

                    for (int j=0; j<userCheckers.size(); j++) {
                        PKIXCertPathChecker currChecker = userCheckers.get(j);
                        if (j < mustCheck ||
                            !currChecker.isForwardCheckingSupported()) {
                            if (i == 0) {
                                currChecker.init(false);

                                // The user specified
                                // AlgorithmChecker may not be
                                // able to set the trust anchor until now.
                                if (j >= mustCheck &&
                                    currChecker instanceof AlgorithmChecker) {
                                    ((AlgorithmChecker)currChecker).
                                        trySetTrustAnchor(builder.trustAnchor);
                                }
                            }

                            try {
                                currChecker.check(currCert, unresCritExts);
                            } catch (CertPathValidatorException cpve) {
                                if (debug != null)
                                    debug.println
                                    ("SunCertPathBuilder.depthFirstSearchForward(): " +
                                    "final verification failed: " + cpve);
                                vertex.setThrowable(cpve);
                                continue vertices;
                            }
                        }
                    }

                    /*
                     * Remove extensions from user checkers that support
                     * forward checking. After this step, we will have
                     * removed all extensions that all user checkers
                     * are capable of processing.
                     */
                    for (PKIXCertPathChecker checker :
                         buildParams.getCertPathCheckers())
                    {
                        if (checker.isForwardCheckingSupported()) {
                            Set<String> suppExts =
                                checker.getSupportedExtensions();
                            if (suppExts != null) {
                                unresCritExts.removeAll(suppExts);
                            }
                        }
                    }

                    if (!unresCritExts.isEmpty()) {
                        unresCritExts.remove
                            (PKIXExtensions.BasicConstraints_Id.toString());
                        unresCritExts.remove
                            (PKIXExtensions.NameConstraints_Id.toString());
                        unresCritExts.remove
                            (PKIXExtensions.CertificatePolicies_Id.toString());
                        unresCritExts.remove
                            (PKIXExtensions.PolicyMappings_Id.toString());
                        unresCritExts.remove
                            (PKIXExtensions.PolicyConstraints_Id.toString());
                        unresCritExts.remove
                            (PKIXExtensions.InhibitAnyPolicy_Id.toString());
                        unresCritExts.remove(PKIXExtensions.
                            SubjectAlternativeName_Id.toString());
                        unresCritExts.remove
                            (PKIXExtensions.KeyUsage_Id.toString());
                        unresCritExts.remove
                            (PKIXExtensions.ExtendedKeyUsage_Id.toString());

                        if (!unresCritExts.isEmpty()) {
                            throw new CertPathValidatorException("unrecognized "
                                + "critical extension(s)");
                        }
                    }
                }
                if (debug != null)
                    debug.println("SunCertPathBuilder.depthFirstSearchForward()"
                        + ": final verification succeeded - path completed!");
                pathCompleted = true;

                /*
                 * if the user specified a trusted public key rather than
                 * trusted certs, then add this cert (which is signed by
                 * the trusted public key) to the certPathList
                 */
                if (builder.trustAnchor.getTrustedCert() == null)
                    builder.addCertToPath(cert, certPathList);
                // Save the trust anchor
                this.trustAnchor = builder.trustAnchor;

                /*
                 * Extract and save the final target public key
                 */
                if (basicChecker != null) {
                    finalPublicKey = basicChecker.getPublicKey();
                } else {
                    Certificate finalCert;
                    if (certPathList.size() == 0) {
                        finalCert = builder.trustAnchor.getTrustedCert();
                    } else {
                        finalCert = certPathList.get(certPathList.size()-1);
                    }
                    finalPublicKey = finalCert.getPublicKey();
                }

                policyTreeResult = policyChecker.getPolicyTree();
                return;
            } else {
                builder.addCertToPath(cert, certPathList);
            }

            /* Update the PKIX state */
            nextState.updateState(cert);

            /*
             * Append an entry for cert in adjacency list and
             * set index for current vertex.
             */
            adjList.add(new LinkedList<Vertex>());
            vertex.setIndex(adjList.size() - 1);

            /* recursively search for matching certs at next dN */
            depthFirstSearchForward(cert.getIssuerX500Principal(),
                nextState, builder, adjList, certPathList);

            /*
             * If path has been completed, return ASAP!
             */
            if (pathCompleted) {
                return;
            } else {
                /*
                 * If we get here, it means we have searched all possible
                 * certs issued by the dN w/o finding any matching certs.
                 * This means we have to backtrack to the previous cert in
                 * the path and try some other paths.
                 */
                if (debug != null)
                    debug.println("SunCertPathBuilder.depthFirstSearchForward()"
                        + ": backtracking");
                builder.removeFinalCertFromPath(certPathList);
            }
        }
    }

    /*
     * This method performs a depth first search for a certification
     * path while building reverse which meets the requirements set in
     * the parameters object.
     * It uses an adjacency list to store all certificates which were
     * tried (i.e. at one time added to the path - they may not end up in
     * the final path if backtracking occurs). This information can
     * be used later to debug or demo the build.
     *
     * See "Data Structure and Algorithms, by Aho, Hopcroft, and Ullman"
     * for an explanation of the DFS algorithm.
     *
     * @param dN the distinguished name being currently searched for certs
     * @param currentState the current PKIX validation state
     */
    void depthFirstSearchReverse(X500Principal dN, ReverseState currentState,
        ReverseBuilder builder, List<List<Vertex>> adjList,
        LinkedList<X509Certificate> certPathList)
        throws GeneralSecurityException, IOException
    {
        if (debug != null)
            debug.println("SunCertPathBuilder.depthFirstSearchReverse(" + dN
                + ", " + currentState.toString() + ")");

        /*
         * Find all the certificates issued by dN which
         * satisfy the PKIX certification path constraints.
         */
        List<Vertex> vertices = addVertices
           (builder.getMatchingCerts(currentState, orderedCertStores), adjList);
        if (debug != null)
            debug.println("SunCertPathBuilder.depthFirstSearchReverse(): "
                + "certs.size=" + vertices.size());

        /*
         * For each cert in the collection, verify anything
         * that hasn't been checked yet (signature, revocation, etc)
         * and check for loops. Call depthFirstSearchReverse()
         * recursively for each good cert.
         */
        for (Vertex vertex : vertices) {
            /**
             * Restore state to currentState each time through the loop.
             * This is important because some of the user-defined
             * checkers modify the state, which MUST be restored if
             * the cert eventually fails to lead to the target and
             * the next matching cert is tried.
             */
            ReverseState nextState = (ReverseState) currentState.clone();
            X509Certificate cert = (X509Certificate) vertex.getCertificate();
            try {
                builder.verifyCert(cert, nextState, certPathList);
            } catch (GeneralSecurityException gse) {
                if (debug != null)
                    debug.println("SunCertPathBuilder.depthFirstSearchReverse()"
                        + ": validation failed: " + gse);
                vertex.setThrowable(gse);
                continue;
            }

            /*
             * Certificate is good, add it to the path (if it isn't a
             * self-signed cert) and update state
             */
            if (!currentState.isInitial())
                builder.addCertToPath(cert, certPathList);
            // save trust anchor
            this.trustAnchor = currentState.trustAnchor;

            /*
             * Check if path is completed, return ASAP if so.
             */
            if (builder.isPathCompleted(cert)) {
                if (debug != null)
                    debug.println("SunCertPathBuilder.depthFirstSearchReverse()"
                        + ": path completed!");
                pathCompleted = true;

                PolicyNodeImpl rootNode = nextState.rootNode;

                if (rootNode == null)
                    policyTreeResult = null;
                else {
                    policyTreeResult = rootNode.copyTree();
                    ((PolicyNodeImpl)policyTreeResult).setImmutable();
                }

                /*
                 * Extract and save the final target public key
                 */
                finalPublicKey = cert.getPublicKey();
                if (finalPublicKey instanceof DSAPublicKey &&
                    ((DSAPublicKey)finalPublicKey).getParams() == null)
                {
                    finalPublicKey =
                        BasicChecker.makeInheritedParamsKey
                            (finalPublicKey, currentState.pubKey);
                }

                return;
            }

            /* Update the PKIX state */
            nextState.updateState(cert);

            /*
             * Append an entry for cert in adjacency list and
             * set index for current vertex.
             */
            adjList.add(new LinkedList<Vertex>());
            vertex.setIndex(adjList.size() - 1);

            /* recursively search for matching certs at next dN */
            depthFirstSearchReverse(cert.getSubjectX500Principal(), nextState,
                builder, adjList, certPathList);

            /*
             * If path has been completed, return ASAP!
             */
            if (pathCompleted) {
                return;
            } else {
                /*
                 * If we get here, it means we have searched all possible
                 * certs issued by the dN w/o finding any matching certs. This
                 * means we have to backtrack to the previous cert in the path
                 * and try some other paths.
                 */
                if (debug != null)
                    debug.println("SunCertPathBuilder.depthFirstSearchReverse()"
                        + ": backtracking");
                if (!currentState.isInitial())
                    builder.removeFinalCertFromPath(certPathList);
            }
        }
        if (debug != null)
            debug.println("SunCertPathBuilder.depthFirstSearchReverse() all "
                + "certs in this adjacency list checked");
    }

    /*
     * Adds a collection of matching certificates to the
     * adjacency list.
     */
    private List<Vertex> addVertices(Collection<X509Certificate> certs,
        List<List<Vertex>> adjList) {
        List<Vertex> l = adjList.get(adjList.size() - 1);

        for (X509Certificate cert : certs) {
           Vertex v = new Vertex(cert);
           l.add(v);
        }

        return l;
    }

    Returns true if trust anchor certificate matches specified
certificate constraints.
/**
     * Returns true if trust anchor certificate matches specified
     * certificate constraints.
     */
    private boolean anchorIsTarget(TrustAnchor anchor, X509CertSelector sel) {
        X509Certificate anchorCert = anchor.getTrustedCert();
        if (anchorCert != null) {
            return sel.match(anchorCert);
        }
        return false;
    }

    Comparator that orders CertStores so that local CertStores come before
remote CertStores.
/**
     * Comparator that orders CertStores so that local CertStores come before
     * remote CertStores.
     */
    private static class CertStoreComparator implements Comparator<CertStore> {
        public int compare(CertStore store1, CertStore store2) {
            if (Builder.isLocalCertStore(store1)) {
                return -1;
            } else {
                return 1;
            }
        }
    }

    Returns the target subject DN from the first X509Certificate that
is fetched that matches the specified X509CertSelector.
/**
     * Returns the target subject DN from the first X509Certificate that
     * is fetched that matches the specified X509CertSelector.
     */
    private X500Principal getTargetSubjectDN(List<CertStore> stores,
        X509CertSelector targetSel) {
        for (CertStore store : stores) {
            try {
                Collection<? extends Certificate> targetCerts =
                    (Collection<? extends Certificate>)
                        store.getCertificates(targetSel);
                if (!targetCerts.isEmpty()) {
                    X509Certificate targetCert =
                        (X509Certificate)targetCerts.iterator().next();
                    return targetCert.getSubjectX500Principal();
                }
            } catch (CertStoreException e) {
                // ignore but log it
                if (debug != null) {
                    debug.println("SunCertPathBuilder.getTargetSubjectDN: " +
                        "non-fatal exception retrieving certs: " + e);
                    e.printStackTrace();
                }
            }
        }
        return null;
    }
}
Params:	params – the parameter set for building a path. Must be an instance of `PKIXBuilderParameters`.
Throws:	CertPathBuilderException – Exception thrown if builder is unable to build a complete certification path from the trusted anchor(s) to the target subject. InvalidAlgorithmParameterException – if the given parameters are inappropriate for this certification path builder.
Returns:	a certification path builder result.
/

java/ 6/ sun/security/provider/certpath/SunCertPathBuilder.java
