Source code: jsdsi/Prover.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.security.cert.*;
17 import java.util.*;
18
19 /**
20 * Given a statement (a <code>Cert</code>) and a <code>CertStore</code>,
21 * attempts to construct a <code>Proof</code> that the statement holds using
22 * certificates from the store.
23 *
24 * @author Sameer Ajmani
25 * @version $Revision: 1.3 $ $Date: 2003/11/24 17:04:32 $
26 */
27 abstract class Prover {
28 /**
29 * Thrown when the Prover <i>finds a proof</i>. This is an abuse of
30 * exceptions, but it makes it easy to return a proof from deep
31 * within a recursive call. Ugly, but effective.
32 *
33 * @author Sameer Ajmani
34 * @version $Revision: 1.3 $ $Date: 2003/11/24 17:04:32 $
35 */
36 static class ProofFoundException extends Exception {
37 Proof proof;
38 ProofFoundException(Proof p) {
39 super("found proof: " + p);
40 proof = p;
41 }
42 Proof getProof() {
43 return proof;
44 }
45 }
46
47 /**
48 * Statement to prove.
49 */
50 Cert provee;
51
52 /**
53 * The <code>CertStore</code> used by this <code>Proof</code>.
54 */
55 java.security.cert.CertStore store;
56
57 /**
58 * cert -> set of proof(cert)
59 */
60 MultiMap check = new MultiMap();
61
62 /**
63 * name -> set of proof(name -> principal)
64 */
65 MultiMap value = new MultiMap();
66
67 /**
68 * name -> set of proof(LHS -> name+X)
69 */
70 MultiMap compatible = new MultiMap();
71 // name -> set of proof(LHS -> name+X)
72
73 /**
74 * issuer -> set of proof(issuer -> RHS)
75 */
76 MultiMap issuer = new MultiMap();
77
78 /**
79 * subject -> set of proof(LHS -> subject)
80 */
81 MultiMap reverse = new MultiMap();
82 // subject -> set of proof(LHS -> subject)
83
84 /**
85 * Number of certs fetched from cert store.
86 */
87 private int numFetched = 0;
88
89 /**
90 * Returns the number of certificates fetched from the cert-store.
91 *
92 * @return the number of certificates fetched from the cert-store.
93 */
94 int getNumFetched() {
95 return numFetched;
96 }
97
98 /**
99 * Creates a new <code>Prover</code> from a given <code>Cert</code> and
100 * a given <code>CertStore</code>.
101 *
102 * @param c <code>Cert</code> for this prover.
103 * @param s <code>CertStore</code> for this prover.
104 */
105 Prover(Cert c, java.security.cert.CertStore s) {
106 provee = c;
107 store = s;
108 }
109
110 /**
111 * Indicates if there has already be an attempt to find a proof.
112 */
113 private boolean attempted = false;
114
115 /**
116 * The proof found by this prover.
117 */
118 private Proof proof; // the proof; null if no proof found
119
120 /**
121 * Returns the proof found by this prover.
122 *
123 * @return the proof found by this prover.
124 */
125 public final Proof getProof() {
126 if (!attempted) {
127 attempted = true;
128 proof = makeProof();
129 }
130 return proof;
131 }
132
133 /**
134 * Creates a new <code>Proof</code>.
135 *
136 * @return a new <code>Proof</code>.
137 */
138 abstract Proof makeProof();
139
140 /**
141 * Inserts the certificates of a given <code>Proof</code> to this
142 * <code>Proof</code>.
143 *
144 * @param p <code>Proof</code> containing certificates to add to
145 * this <code>Proof</code>.
146 * @throws ProofFoundException if a <i>proof is found</i>.
147 */
148 abstract void insert(Proof p) throws ProofFoundException;
149
150 /**
151 * Provides new certificates for this prover. Adds the given certificates
152 * to the certificates already used.
153 *
154 * @param certs certificates to add to the prover.
155 * @throws ProofFoundException if a <i>proof is found</i> while
156 * adding the certificates.
157 */
158 void insertCertificates(Collection certs) throws ProofFoundException {
159 // insert stored proofs
160 //System.out.println("INSERT: inserting certs "+certs.size());
161 Iterator i = certs.iterator();
162 while (i.hasNext()) {
163 insert(new Proof((Certificate) i.next()));
164 }
165 }
166
167 /**
168 * If a given set does not contain a given object, all certficates
169 * from the cert-store for a given <code>CertSelector</code> will
170 * be added to this proof's certificates.
171 *
172 * @param cache set with objects.
173 * @param key key to search in <code>cache</code>.
174 * @param sel cert selector to add certificates from to this proof's
175 * certificates.
176 * @param map multi-map with sets stored for keys.
177 * @return the set stored in <code>map</code> for <code>key</code> if
178 * no error occures.
179 * @throws ProofFoundException if a <i>proof is found</i>.
180 */
181 Set load(Set cache, Object key, CertSelector sel, MultiMap map)
182 throws ProofFoundException {
183 try {
184 if (!cache.contains(key)) {
185 cache.add(key);
186 // fetch stored proofs
187 try {
188 Collection stored = store.getCertificates(sel);
189 numFetched += stored.size();
190 insertCertificates(stored);
191 } catch (CertStoreException e) {
192 throw new Error(e);
193 }
194 }
195 return map.get(key);
196 } catch (ProofFoundException e) {
197 // invalidate cache
198 cache.remove(key);
199 throw e;
200 }
201 }
202 }