1 /*
2 * Copyright (c) 2000, 2016, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23 import static sun.security.x509.GeneralNameInterface.NAME_DIRECTORY;
24 import static sun.security.x509.NameConstraintsExtension.EXCLUDED_SUBTREES;
25 import static sun.security.x509.NameConstraintsExtension.PERMITTED_SUBTREES;
26
27 import java.io.ByteArrayInputStream;
28 import java.io.ByteArrayOutputStream;
29 import java.io.IOException;
30 import java.io.InputStream;
31 import java.math.BigInteger;
32 import java.security.GeneralSecurityException;
33 import java.security.KeyFactory;
34 import java.security.PublicKey;
35 import java.security.cert.CertificateException;
36 import java.security.cert.CertificateFactory;
37 import java.security.cert.X509CertSelector;
38 import java.security.cert.X509Certificate;
39 import java.security.spec.X509EncodedKeySpec;
40 import java.util.Base64;
41 import java.util.Calendar;
42 import java.util.Date;
43 import java.util.HashSet;
44 import java.util.Iterator;
45 import java.util.List;
46 import java.util.Set;
47
48 import sun.security.util.DerInputStream;
49 import sun.security.util.DerOutputStream;
50 import sun.security.util.DerValue;
51 import sun.security.util.ObjectIdentifier;
52 import sun.security.x509.AlgorithmId;
53 import sun.security.x509.AuthorityKeyIdentifierExtension;
54 import sun.security.x509.CertificatePoliciesExtension;
55 import sun.security.x509.DNSName;
56 import sun.security.x509.GeneralName;
57 import sun.security.x509.GeneralNameInterface;
58 import sun.security.x509.GeneralNames;
59 import sun.security.x509.GeneralSubtree;
60 import sun.security.x509.GeneralSubtrees;
61 import sun.security.x509.KeyIdentifier;
62 import sun.security.x509.NameConstraintsExtension;
63 import sun.security.x509.PolicyInformation;
64 import sun.security.x509.PrivateKeyUsageExtension;
65 import sun.security.x509.SubjectAlternativeNameExtension;
66 import sun.security.x509.X500Name;
67
68 /*
69 * @test
70 * @bug 8074931
71 * @summary This class tests the X509CertSelector. The tests check particular criteria
72 * by setting them to a value that should match our test certificate and
73 * ensuring that they do match, then setting them to a value that should not
74 * match our test certificate and ensuring that they do not match.
75 */
76 public class X509CertSelectorTest {
77 /*
78 Certificate:
79 Data:
80 Version: 3 (0x2)
81 Serial Number: 954172088 (0x38df82b8)
82 Signature Algorithm: dsaWithSHA1
83 Issuer: C=us, O=sun, OU=testing
84 Validity
85 Not Before: Mar 27 15:48:08 2000 GMT
86 Not After : Jun 25 14:48:08 2000 GMT
87 Subject: C=us, O=sun, OU=testing, CN=mullan
88 Subject Public Key Info:
89 Public Key Algorithm: dsaEncryption
90 pub: 0
91 P: 0
92 Q: 0
93 G: 0
94 X509v3 extensions:
95 X509v3 Name Constraints: critical
96 0D.B0@.>1.0...U....us1.0
97 ..U.
98 ..sun1.0...U....testing1.0
99 ..U....mullan
100 X509v3 Subject Key Identifier:
101 56:E8:88:AE:9D:B5:3F:2B:CB:A0:4C:4B:E2:87:53:07:33:77:1B:DF
102 X509v3 Authority Key Identifier:
103 keyid:8E:DD:AF:6F:EE:02:12:F4:61:E9:2F:E3:64:1A:6F:71:32:25:20:C0
104
105 X509v3 Subject Alternative Name:
106 email:mullan@east.sun.com
107 X509v3 Private Key Usage Period:
108 Not Before: Jan 1 05:00:00 2000 GMT, Not After: Jan 1 05:00:00 2001 GMT
109 X509v3 Key Usage: critical
110 Digital Signature
111 X509v3 Certificate Policies:
112 0$0\..*...0.0...+.......0..
113 Testing...
114 Signature Algorithm: dsaWithSHA1
115 r:
116 44:c7:35:40:5d:6c:28:75:7f:73:b2:f8:0d:72:6c:
117 09:65:b8:81:14
118 s:
119 76:79:f5:c7:37:3b:0d:9b:db:70:2f:20:80:36:e3:
120 80:e8:a6:c6:71
121 */
122 private static final String testCert =
123 "-----BEGIN CERTIFICATE-----\n" +
124 "MIICLjCCAeygAwIBAgIEON+CuDALBgcqhkjOOAQDBQAwLTELMAkGA1UEBhMCdXMx\n" +
125 "DDAKBgNVBAoTA3N1bjEQMA4GA1UECxMHdGVzdGluZzAeFw0wMDAzMjcxNTQ4MDha\n" +
126 "Fw0wMDA2MjUxNDQ4MDhaMD4xCzAJBgNVBAYTAnVzMQwwCgYDVQQKEwNzdW4xEDAO\n" +
127 "BgNVBAsTB3Rlc3RpbmcxDzANBgNVBAMTBm11bGxhbjAcMBQGByqGSM44BAEwCQIB\n" +
128 "AAIBAAIBAAMEAAIBAKOCASMwggEfMFAGA1UdHgEB/wRGMESgQjBApD4xCzAJBgNV\n" +
129 "BAYTAnVzMQwwCgYDVQQKEwNzdW4xEDAOBgNVBAsTB3Rlc3RpbmcxDzANBgNVBAMT\n" +
130 "Bm11bGxhbjAdBgNVHQ4EFgQUVuiIrp21PyvLoExL4odTBzN3G98wHwYDVR0jBBgw\n" +
131 "FoAUjt2vb+4CEvRh6S/jZBpvcTIlIMAwHgYDVR0RBBcwFYETbXVsbGFuQGVhc3Qu\n" +
132 "c3VuLmNvbTArBgNVHRAEJDAigA8yMDAwMDEwMTA1MDAwMFqBDzIwMDEwMTAxMDUw\n" +
133 "MDAwWjAPBgNVHQ8BAf8EBQMDB4AAMC0GA1UdIAQmMCQwIgYEKoSAADAaMBgGCCsG\n" +
134 "AQUFBwICMAwSClRlc3RpbmcuLi4wCwYHKoZIzjgEAwUAAy8AMCwCFETHNUBdbCh1\n" +
135 "f3Oy+A1ybAlluIEUAhR2efXHNzsNm9twLyCANuOA6KbGcQ==\n" +
136 "-----END CERTIFICATE-----\n" +
137 "";
138
139 private static final String testKey =
140 "MIIBtjCCASsGByqGSM44BAEwggEeAoGBAIVWPEkcxbxhQRCqVzg55tNqbP5j0K4kdu4bkmXvfqC5\n" +
141 "+qA75DvnfzsOJseb+9AuKXWk/DvCzFDmrY1YaU3scZC3OQEO9lEO3F4VDKOaudY6OT1SI22pAIwz\n" +
142 "j5pvq+i7zOp4xUqkQUeh/4iQSfxOT5UrFGjkcbnbpVkCXD/GxAz7AhUAjtnm3dVIddUUHl6wxpZ7\n" +
143 "GcA6gSsCgYAf/PXzQtemgIDjpFrNNSgTEKkLposBXKatAM+gUKlMUjf8SQvquqPxDtRrscGjXkoL\n" +
144 "oTkaR7/akULYFpBvUcFkeIFiCnJg8M9XhCWdLvn9MPt+jR2oxookvCb9xLtD6WvIM/wd/nZ1iK4u\n" +
145 "iY1+q85xvns/Awbtwl7oZDAwE2TUKAOBhAACgYBDc9UZ+3xsZubUZvRG5cpyJceYpJp2exOPVJXn\n" +
146 "jR4CcR+cT9bAJpFSxqE/8KtNHXxHdu4f3DU67IMOVDpugzihyzXJvNm3w2H9x+6xczHG2wjvAJeh\n" +
147 "X62EWbUatxPXFAoVKZWuUbaYaZzdWBDtNRrCuKKsLo0GFy8g2BZISuD3jw==\n" +
148 "";
149
150 // Certificate to run tests on
151 private final X509Certificate cert;
152
153 public static void main(String[] args) throws Exception {
154 X509CertSelectorTest test = new X509CertSelectorTest();
155 test.doTest();
156 }
157
158 public X509CertSelectorTest() throws CertificateException, IOException {
159 cert = (X509Certificate) CertificateFactory.getInstance("X.509")
160 .generateCertificate(new ByteArrayInputStream(testCert.getBytes()));
161 }
162
163 // Runs the test.
164 private void doTest() throws Exception {
165 System.out.println("START OF TESTS FOR " + "X509CertSelector");
166
167 testSerialNumber();
168 testIssuer();
169 testSubjectKeyIdentifier();
170 testAuthorityKeyIdentifier();
171 testCertificateValid();
172 testPrivateKeyValid();
173 testSubjectPublicKeyAlgID();
174 testKeyUsage();
175 testSubjectAltName();
176 testPolicy();
177 testPathToName();
178 testSubject();
179 testSubjectPublicKey();
180 testNameConstraints();
181 testBasicConstraints();
182 testCertificate();
183 }
184
185 // Tests matching on the serial number contained in the certificate.
186 private void testSerialNumber() {
187 System.out.println("X.509 Certificate Match on serialNumber");
188 // bad match
189 X509CertSelector selector = new X509CertSelector();
190 selector.setSerialNumber(new BigInteger("999999999"));
191 checkMatch(selector, cert, false);
192
193 // good match
194 selector.setSerialNumber(cert.getSerialNumber());
195 checkMatch(selector, cert, true);
196 }
197
198 // Tests matching on the issuer name contained in the certificate.
199 private void testIssuer() throws IOException {
200 System.out.println("X.509 Certificate Match on issuer");
201 // bad match
202 X509CertSelector selector = new X509CertSelector();
203 selector.setIssuer("ou=bogus,ou=east,o=sun,c=us");
204 checkMatch(selector, cert, false);
205
206 // good match
207 selector.setIssuer((cert.getIssuerX500Principal()).getName("RFC2253"));
208 checkMatch(selector, cert, true);
209 }
210
211 /*
212 * Tests matching on the subject key identifier contained in the
213 * certificate.
214 */
215 private void testSubjectKeyIdentifier() throws IOException {
216 System.out.println("X.509 Certificate Match on subjectKeyIdentifier");
217 // bad match
218 X509CertSelector selector = new X509CertSelector();
219 byte[] b = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
220 selector.setSubjectKeyIdentifier(b);
221 checkMatch(selector, cert, false);
222
223 // good match
224 DerInputStream in = new DerInputStream(cert.getExtensionValue("2.5.29.14"));
225 byte[] encoded = in.getOctetString();
226 selector.setSubjectKeyIdentifier(encoded);
227 checkMatch(selector, cert, true);
228 }
229
230 /*
231 * Tests matching on the authority key identifier contained in the
232 * certificate.
233 */
234 private void testAuthorityKeyIdentifier() throws IOException {
235 System.out.println("X.509 Certificate Match on authorityKeyIdentifier");
236 // bad match
237 X509CertSelector selector = new X509CertSelector();
238 byte[] b = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
239 AuthorityKeyIdentifierExtension a = new AuthorityKeyIdentifierExtension(new KeyIdentifier(b), null, null);
240 selector.setAuthorityKeyIdentifier(a.getExtensionValue());
241 checkMatch(selector, cert, false);
242
243 // good match
244 DerInputStream in = new DerInputStream(cert.getExtensionValue("2.5.29.35"));
245 byte[] encoded = in.getOctetString();
246 selector.setAuthorityKeyIdentifier(encoded);
247 checkMatch(selector, cert, true);
248 }
249
250 /*
251 * Tests matching on the certificate validity component contained in the
252 * certificate.
253 */
254 private void testCertificateValid() {
255 System.out.println("X.509 Certificate Match on certificateValid");
256 // bad match
257 X509CertSelector selector = new X509CertSelector();
258 Calendar cal = Calendar.getInstance();
259 cal.set(1968, 12, 31);
260 selector.setCertificateValid(cal.getTime());
261 checkMatch(selector, cert, false);
262
263 // good match
264 selector.setCertificateValid(cert.getNotBefore());
265 checkMatch(selector, cert, true);
266 }
267
268 /*
269 * Tests matching on the private key validity component contained in the
270 * certificate.
271 */
272 private void testPrivateKeyValid() throws IOException, CertificateException {
273 System.out.println("X.509 Certificate Match on privateKeyValid");
274 // bad match
275 X509CertSelector selector = new X509CertSelector();
276 Calendar cal = Calendar.getInstance();
277 cal.set(1968, 12, 31);
278 selector.setPrivateKeyValid(cal.getTime());
279 checkMatch(selector, cert, false);
280
281 // good match
282 DerInputStream in = new DerInputStream(cert.getExtensionValue("2.5.29.16"));
283 byte[] encoded = in.getOctetString();
284 PrivateKeyUsageExtension ext = new PrivateKeyUsageExtension(false, encoded);
285 Date validDate = (Date) ext.get(PrivateKeyUsageExtension.NOT_BEFORE);
286 selector.setPrivateKeyValid(validDate);
287 checkMatch(selector, cert, true);
288
289 }
290
291 private ObjectIdentifier getCertPubKeyAlgOID(X509Certificate xcert) throws IOException {
292 byte[] encodedKey = xcert.getPublicKey().getEncoded();
293 DerValue val = new DerValue(encodedKey);
294 if (val.tag != DerValue.tag_Sequence) {
295 throw new RuntimeException("invalid key format");
296 }
297
298 return AlgorithmId.parse(val.data.getDerValue()).getOID();
299 }
300
301 /*
302 * Tests matching on the subject public key algorithm ID component contained
303 * in the certificate.
304 */
305 private void testSubjectPublicKeyAlgID() throws IOException {
306 System.out.println("X.509 Certificate Match on subjectPublicKeyAlgID");
307 // bad match
308 X509CertSelector selector = new X509CertSelector();
309 selector.setSubjectPublicKeyAlgID("2.5.29.14");
310 checkMatch(selector, cert, false);
311
312 // good match
313 selector.setSubjectPublicKeyAlgID(getCertPubKeyAlgOID(cert).toString());
314 checkMatch(selector, cert, true);
315
316 }
317
318 // Tests matching on the key usage extension contained in the certificate.
319 private void testKeyUsage() {
320 System.out.println("X.509 Certificate Match on keyUsage");
321 // bad match
322 X509CertSelector selector = new X509CertSelector();
323 boolean[] keyUsage = { true, false, true, false, true, false, true, false };
324 selector.setKeyUsage(keyUsage);
325 System.out.println("Selector = " + selector.toString());
326 checkMatch(selector, cert, false);
327
328 // good match
329 selector.setKeyUsage(cert.getKeyUsage());
330 System.out.println("Selector = " + selector.toString());
331 checkMatch(selector, cert, true);
332 }
333
334 /*
335 * Tests matching on the subject alternative name extension contained in the
336 * certificate.
337 */
338 private void testSubjectAltName() throws IOException {
339 System.out.println("X.509 Certificate Match on subjectAltName");
340 // bad match
341 X509CertSelector selector = new X509CertSelector();
342 GeneralNameInterface dnsName = new DNSName("foo.com");
343 DerOutputStream tmp = new DerOutputStream();
344 dnsName.encode(tmp);
345 selector.addSubjectAlternativeName(2, tmp.toByteArray());
346 checkMatch(selector, cert, false);
347
348 // good match
349 DerInputStream in = new DerInputStream(cert.getExtensionValue("2.5.29.17"));
350 byte[] encoded = in.getOctetString();
351 SubjectAlternativeNameExtension ext = new SubjectAlternativeNameExtension(false, encoded);
352 GeneralNames names = (GeneralNames) ext.get(SubjectAlternativeNameExtension.SUBJECT_NAME);
353 GeneralName name = (GeneralName) names.get(0);
354 selector.setSubjectAlternativeNames(null);
355 DerOutputStream tmp2 = new DerOutputStream();
356 name.getName().encode(tmp2);
357 selector.addSubjectAlternativeName(name.getType(), tmp2.toByteArray());
358 checkMatch(selector, cert, true);
359
360 // good match 2 (matches at least one)
361 selector.setMatchAllSubjectAltNames(false);
362 selector.addSubjectAlternativeName(2, "foo.com");
363 checkMatch(selector, cert, true);
364 }
365
366 /*
367 * Tests matching on the policy constraints extension contained in the
368 * certificate.
369 */
370 private void testPolicy() throws IOException {
371 System.out.println("X.509 Certificate Match on certificatePolicies");
372 // test encoding of CertificatePoliciesExtension because we wrote the
373 // code
374 // bad match
375 X509CertSelector selector = new X509CertSelector();
376 Set<String> s = new HashSet<>();
377 s.add(new String("1.2.5.7.68"));
378 selector.setPolicy(s);
379 checkMatch(selector, cert, false);
380
381 // good match
382 DerInputStream in = new DerInputStream(cert.getExtensionValue("2.5.29.32"));
383 CertificatePoliciesExtension ext = new CertificatePoliciesExtension(false, in.getOctetString());
384 List<PolicyInformation> policies = ext.get(CertificatePoliciesExtension.POLICIES);
385 // match on the first policy id
386 PolicyInformation policyInfo = (PolicyInformation) policies.get(0);
387 s.clear();
388 s.add(policyInfo.getPolicyIdentifier().getIdentifier().toString());
389 selector.setPolicy(s);
390 checkMatch(selector, cert, true);
391 }
392
393 /*
394 * Tests matching on the name constraints extension contained in the
395 * certificate.
396 */
397 private void testPathToName() throws IOException {
398 System.out.println("X.509 Certificate Match on pathToName");
399
400 X509CertSelector selector = null;
401 DerInputStream in = new DerInputStream(cert.getExtensionValue("2.5.29.30"));
402 byte[] encoded = in.getOctetString();
403 NameConstraintsExtension ext = new NameConstraintsExtension(false, encoded);
404 GeneralSubtrees permitted = (GeneralSubtrees) ext.get(PERMITTED_SUBTREES);
405 GeneralSubtrees excluded = (GeneralSubtrees) ext.get(EXCLUDED_SUBTREES);
406
407 // bad matches on pathToName within excluded subtrees
408 if (excluded != null) {
409 Iterator<GeneralSubtree> e = excluded.iterator();
410 while (e.hasNext()) {
411 GeneralSubtree tree = e.next();
412 if (tree.getName().getType() == NAME_DIRECTORY) {
413 X500Name excludedDN1 = new X500Name(tree.getName().toString());
414 X500Name excludedDN2 = new X500Name("CN=Bogus, " + tree.getName().toString());
415 DerOutputStream derDN1 = new DerOutputStream();
416 DerOutputStream derDN2 = new DerOutputStream();
417 excludedDN1.encode(derDN1);
418 excludedDN2.encode(derDN2);
419 selector = new X509CertSelector();
420 selector.addPathToName(NAME_DIRECTORY, derDN1.toByteArray());
421 checkMatch(selector, cert, false);
422 selector.setPathToNames(null);
423 selector.addPathToName(NAME_DIRECTORY, derDN2.toByteArray());
424 checkMatch(selector, cert, false);
425 }
426 }
427 }
428
429 // good matches on pathToName within permitted subtrees
430 if (permitted != null) {
431 Iterator<GeneralSubtree> e = permitted.iterator();
432 while (e.hasNext()) {
433 GeneralSubtree tree = e.next();
434 if (tree.getName().getType() == NAME_DIRECTORY) {
435 X500Name permittedDN1 = new X500Name(tree.getName().toString());
436 X500Name permittedDN2 = new X500Name("CN=good, " + tree.getName().toString());
437 DerOutputStream derDN1 = new DerOutputStream();
438 DerOutputStream derDN2 = new DerOutputStream();
439 permittedDN1.encode(derDN1);
440 permittedDN2.encode(derDN2);
441 selector = new X509CertSelector();
442 selector.addPathToName(NAME_DIRECTORY, derDN1.toByteArray());
443 checkMatch(selector, cert, true);
444 selector.setPathToNames(null);
445 selector.addPathToName(NAME_DIRECTORY, derDN2.toByteArray());
446 checkMatch(selector, cert, true);
447 }
448 }
449 }
450 }
451
452 // Tests matching on the subject name contained in the certificate.
453 private void testSubject() throws IOException {
454 System.out.println("X.509 Certificate Match on subject");
455 // bad match
456 X509CertSelector selector = new X509CertSelector();
457 selector.setSubject("ou=bogus,ou=east,o=sun,c=us");
458 checkMatch(selector, cert, false);
459
460 // good match
461 selector.setSubject(cert.getSubjectX500Principal().getName("RFC2253"));
462 checkMatch(selector, cert, true);
463 }
464
465 // Tests matching on the subject public key contained in the certificate.
466 private void testSubjectPublicKey() throws IOException, GeneralSecurityException {
467 System.out.println("X.509 Certificate Match on subject public key");
468 // bad match
469 X509CertSelector selector = new X509CertSelector();
470 X509EncodedKeySpec keySpec = new X509EncodedKeySpec(
471 Base64.getMimeDecoder().decode(testKey.getBytes()));
472 KeyFactory keyFactory = KeyFactory.getInstance("DSA");
473 PublicKey pubKey = keyFactory.generatePublic(keySpec);
474 selector.setSubjectPublicKey(pubKey);
475 checkMatch(selector, cert, false);
476
477 // good match
478 selector.setSubjectPublicKey(cert.getPublicKey());
479 checkMatch(selector, cert, true);
480 }
481
482 // Tests matching on the name constraints contained in the certificate.
483 private void testNameConstraints() throws IOException {
484 System.out.println("X.509 Certificate Match on name constraints");
485 // bad match
486 GeneralSubtrees subjectTree = new GeneralSubtrees();
487 subjectTree.add(getGeneralSubtree((X500Name) cert.getSubjectDN()));
488 NameConstraintsExtension ext = new NameConstraintsExtension((GeneralSubtrees) null, subjectTree);
489 X509CertSelector selector = new X509CertSelector();
490 selector.setNameConstraints(ext.getExtensionValue());
491 checkMatch(selector, cert, false);
492
493 // good match
494 ext = new NameConstraintsExtension(subjectTree, null);
495 selector.setNameConstraints(ext.getExtensionValue());
496 checkMatch(selector, cert, true);
497 }
498
499 // Tests matching on basic constraints.
500 private void testBasicConstraints() {
501 System.out.println("X.509 Certificate Match on basic constraints");
502 // bad match
503 X509CertSelector selector = new X509CertSelector();
504 int mpl = cert.getBasicConstraints();
505 selector.setBasicConstraints(0);
506 checkMatch(selector, cert, false);
507
508 // good match
509 selector.setBasicConstraints(mpl);
510 checkMatch(selector, cert, true);
511 }
512
513 // Tests certificateEquals criterion
514 private void testCertificate() {
515 System.out.println("X.509 Certificate Match on certificateEquals criterion");
516
517 X509CertSelector selector = new X509CertSelector();
518 // good match
519 selector.setCertificate(cert);
520 checkMatch(selector, cert, true);
521 }
522
523 private void checkMatch(X509CertSelector selector, X509Certificate cert, boolean match) {
524 boolean result = selector.match(cert);
525 if (match != result)
526 throw new RuntimeException(selector + " match " + cert + " is " + result + ", but expect " + match);
527 }
528
529 private static GeneralSubtree getGeneralSubtree(GeneralNameInterface gni) {
530 // Create a new GeneralSubtree with the specified name, 0 base, and
531 // unlimited length
532 GeneralName gn = new GeneralName(gni);
533 GeneralSubtree subTree = new GeneralSubtree(gn, 0, -1);
534 return subTree;
535 }
536 }