Source code: jsdsi/RProver.java
1 /*
2 * Copyright 2002 Massachusetts Institute of Technology
3 *
4 * Permission to use, copy, modify, and distribute this program for any
5 * purpose and without fee is hereby granted, provided that this
6 * copyright and permission notice appear on all copies and supporting
7 * documentation, the name of M.I.T. not be used in advertising or
8 * publicity pertaining to distribution of the program without specific
9 * prior permission, and notice be given in supporting documentation that
10 * copying and distribution is by permission of M.I.T. M.I.T. makes no
11 * representations about the suitability of this software for any
12 * purpose. It is provided "as is" without express or implied warranty.
13 */
14 package jsdsi;
15
16 import java.util.*;
17
18 /**
19 * A prover that searches subject-to-issuer. Will only access the
20 * <code>CertStore</code> using <code>CompatibleCertSelectors</code>
21 * and <ocde>SubjectCertSelectors</code>.
22 *
23 * @see CertStore
24 * @see CompatibleCertSelector
25 * @see SubjectCertSelector
26 *
27 * @author Sameer Ajmani
28 * @version $Revision: 1.5 $ $Date: 2003/11/24 19:05:56 $
29 */
30 class RProver extends Prover {
31 /**
32 * Certificates from issuers to subject's.
33 */
34 Set loadedReverse = new HashSet();
35
36 /**
37 * Certificates for issuers to local names.
38 */
39 Set loadedCompatible = new HashSet();
40
41 /**
42 * @see jsdsi.Prover#Prover(Cert, CertStore)
43 */
44 RProver(Cert c, java.security.cert.CertStore s) {
45 super(c, s);
46 assert(!(c.getSubject() instanceof Name));
47 }
48
49 /**
50 * @see jsdsi.Prover#makeProof()
51 */
52 Proof makeProof() {
53 try {
54 loadReverse(provee.getSubject());
55 } catch (ProofFoundException e) {
56 return e.getProof();
57 }
58 return null;
59 }
60
61 /**
62 * Loads the certificates for a given subject to this
63 * <code>RProver</code>'s certificates.
64 *
65 * @param s subject to load certificates for.
66 * @return this <code>RProvers</code> set of certificates for
67 * the subject <code>s</code>.
68 * @throws ProofFoundException if a <i>proof is found</i>.
69 */
70 Set loadReverse(Subject s) throws ProofFoundException {
71 CertSelector sel = new SubjectCertSelector(s);
72 return load(loadedReverse, s, sel, reverse);
73 }
74
75 /**
76 * Loads all certificates for a given name-issuer and
77 * name-string (local) to this<code>RProver</code>'s certificates.
78 *
79 * @param n name to load the certificates for.
80 * @return a set of certificates from the issuer of <code>n</code>
81 * for the local name of <code>n</code>.
82 * @throws ProofFoundException if a <i>proof is found</i>.
83 */
84 Set loadCompatible(Name n) throws ProofFoundException {
85 CertSelector sel =
86 new CompatibleCertSelector(n.getIssuer(), n.getNames()[0]);
87 return load(loadedCompatible, n, sel, compatible);
88 }
89
90 /**
91 * @see jsdsi.Prover#insert(Proof)
92 */
93 void insert(Proof p) throws ProofFoundException {
94 //System.out.println("INSERT("+p.hashCode()+"): "+p);
95 if (p.getCert().implies(provee)) {
96 //System.out.println("INSERT("+p.hashCode()+"): found proof!");
97 throw new ProofFoundException(p);
98 }
99 if (!check.get(p.getCert()).isEmpty()) {
100 //System.out.println("INSERT("+p.hashCode()+"): already inserted");
101 return; // already have this proof
102 }
103 check.put(p.getCert(), p);
104
105 try {
106 if (p.getCert().getSubject() instanceof Name) {
107 Name key = ((Name) p.getCert().getSubject()).prefix();
108 compatible.put(key, p);
109 // look up compatible certs, and compose
110 Set values = value.get(key);
111 //System.out.println("INSERT("+p.hashCode()
112 //+"): inserting right-composed "+values.size());
113 Iterator i = values.iterator();
114 while (i.hasNext()) {
115 try {
116 insert(p.compose((Proof) i.next()));
117 } catch (Proof.IncompatibleException e) {
118 throw new Error(e);
119 }
120 }
121 return;
122 }
123
124 if (p.getCert() instanceof NameCert) {
125 Name key = ((NameCert) p.getCert()).getFullName();
126 value.put(key, p);
127 reverse.put(p.getCert().getSubject(), p);
128 // look up compatible certs, and compose
129 Set compats = loadCompatible(key);
130 //System.out.println("INSERT("+p.hashCode()
131 //+"): inserting left-composed "+compats.size());
132 Iterator i = compats.iterator();
133 while (i.hasNext()) {
134 try {
135 insert(((Proof) i.next()).compose(p));
136 } catch (Proof.IncompatibleException e) {
137 throw new Error(e);
138 }
139 }
140 // search backwards to find extended names
141 Subject s = p.getCert().getIssuer();
142 //System.out.println("INSERT("+p.hashCode()
143 //+"): fetching reverse for "+s.hashCode());
144 loadReverse(s);
145 return;
146 }
147
148 if (p.getCert() instanceof AuthCert) {
149 issuer.put(p.getCert().getIssuer(), p);
150 reverse.put(p.getCert().getSubject(), p);
151
152 // TODO: optimize for provee:
153 // p.tag implies provee.tag
154
155 if (((AuthCert) p.getCert()).getPropagate()
156 && (p.getCert().getSubject() instanceof Principal)) {
157 // search forwards locally to find auth chains
158 Set issuers = issuer.get(p.getCert().getSubject());
159 Iterator i = issuers.iterator();
160 while (i.hasNext()) {
161 try {
162 insert(p.compose((Proof) i.next()));
163 } catch (Proof.IncompatibleException e) {
164 throw new Error(e);
165 }
166 }
167 }
168
169 // search backwards locally to find auth chains
170 Set reverses = reverse.get(p.getCert().getIssuer());
171 Iterator i = reverses.iterator();
172 while (i.hasNext()) {
173 try {
174 Proof pf = (Proof) i.next();
175 if ((pf.getCert() instanceof AuthCert)
176 && ((AuthCert) pf.getCert()).getPropagate()
177 && (pf.getCert().getSubject() instanceof Principal)) {
178 insert(pf.compose(p));
179 }
180 } catch (Proof.IncompatibleException e) {
181 throw new Error(e);
182 }
183 }
184
185 // search backwards to find new auths
186 Subject s = p.getCert().getIssuer();
187 //System.out.println("INSERT("+p.hashCode()
188 //+"): fetching reverse for "+s.hashCode());
189 loadReverse(s);
190 return;
191 }
192
193 throw new Error(
194 "unhandled case: " + p.getCert().getClass().getName());
195 } catch (ProofFoundException e) {
196 // invalidate cache
197 check.remove(p.getCert(), p);
198 throw e;
199 }
200 }
201 }