OSX/sec/securityd/nameconstraints.c

   1 /*
   2  * Copyright (c) 2015 Apple Inc. All Rights Reserved.
   3  *
   4  * @APPLE_LICENSE_HEADER_START@
   5  *
   6  * This file contains Original Code and/or Modifications of Original Code
   7  * as defined in and that are subject to the Apple Public Source License
   8  * Version 2.0 (the 'License'). You may not use this file except in
   9  * compliance with the License. Please obtain a copy of the License at
  10  * http://www.opensource.apple.com/apsl/ and read it before using this
  11  * file.
  12  *
  13  * The Original Code and all software distributed under the License are
  14  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  15  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  16  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  17  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  18  * Please see the License for the specific language governing rights and
  19  * limitations under the License.
  20  *
  21  * @APPLE_LICENSE_HEADER_END@
  22  */
  23
  24 /*
  25  * nameconstraints.c - rfc5280 section 4.2.1.10 and later name constraints implementation.
  26  */
  27
  28 #include "nameconstraints.h"
  29 #include <AssertMacros.h>
  30 #include <utilities/SecCFWrappers.h>
  31 #include <Security/SecCertificateInternal.h>
  32 #include <securityd/SecPolicyServer.h>
  33 #include <libDER/asn1Types.h>
  34
  35 /* RFC 5280 Section 4.2.1.10:
  36  For URIs, the constraint applies to the host part of the name.  The
  37  constraint MUST be specified as a fully qualified domain name and MAY
  38  specify a host or a domain.  Examples would be "host.example.com" and
  39  ".example.com".  When the constraint begins with a period, it MAY be
  40  expanded with one or more labels.  That is, the constraint
  41  ".example.com" is satisfied by both host.example.com and
  42  my.host.example.com.  However, the constraint ".example.com" is not
  43  satisfied by "example.com".  When the constraint does not begin with
  44  a period, it specifies a host.
  45  */
  46 static bool SecURIMatch(CFStringRef URI, CFStringRef hostname) {
  47     bool result = false;
  48     CFStringRef URI_hostname =  NULL;
  49     CFCharacterSetRef port_or_path_separator = NULL;
  50     /* URI must have scheme specified */
  51     CFRange URI_scheme = CFStringFind(URI, CFSTR("://"), 0);
  52     require_quiet(URI_scheme.location != kCFNotFound, out);
  53
  54     /* Remove scheme prefix and port or resource path suffix */
  55     CFRange URI_hostname_range = { URI_scheme.location + URI_scheme.length,
  56         CFStringGetLength(URI) - URI_scheme.location - URI_scheme.length };
  57     port_or_path_separator = CFCharacterSetCreateWithCharactersInString(kCFAllocatorDefault, CFSTR(":/"));
  58     CFRange separator = {kCFNotFound, 0};
  59     if(CFStringFindCharacterFromSet(URI, port_or_path_separator, URI_hostname_range, 0, &separator)) {
  60         URI_hostname_range.length -= (CFStringGetLength(URI) - separator.location);
  61     }
  62     URI_hostname = CFStringCreateWithSubstring(kCFAllocatorDefault, URI, URI_hostname_range);
  63
  64     /* Hostname in URI must not begin with '.' */
  65     require_quiet('.' != CFStringGetCharacterAtIndex(URI_hostname, 0), out);
  66
  67     CFIndex ulength = CFStringGetLength(URI_hostname);
  68     CFIndex hlength = CFStringGetLength(hostname);
  69     require_quiet(ulength >= hlength, out);
  70     CFRange compare_range = { 0, hlength };
  71
  72     /* Allow one or more preceding labels */
  73     if ('.' == CFStringGetCharacterAtIndex(hostname, 0)) {
  74         compare_range.location = ulength - hlength;
  75     }
  76
  77     if(kCFCompareEqualTo == CFStringCompareWithOptions(URI_hostname,
  78                                                        hostname,
  79                                                        compare_range,
  80                                                        kCFCompareCaseInsensitive)) {
  81         result = true;
  82     }
  83
  84 out:
  85     CFReleaseNull(port_or_path_separator);
  86     CFReleaseNull(URI_hostname);
  87     return result;
  88 }
  89
  90 /* RFC 5280 Section 4.2.1.10:
  91  A name constraint for Internet mail addresses MAY specify a
  92  particular mailbox, all addresses at a particular host, or all
  93  mailboxes in a domain.  To indicate a particular mailbox, the
  94  constraint is the complete mail address.  For example,
  95  "root@example.com" indicates the root mailbox on the host
  96  "example.com".  To indicate all Internet mail addresses on a
  97  particular host, the constraint is specified as the host name.  For
  98  example, the constraint "example.com" is satisfied by any mail
  99  address at the host "example.com".  To specify any address within a
 100  domain, the constraint is specified with a leading period (as with
 101  URIs).
 102  */
 103 static bool SecRFC822NameMatch(CFStringRef emailAddress, CFStringRef constraint) {
 104     CFRange mailbox_range = CFStringFind(constraint,CFSTR("@"),0);
 105
 106     /* Constraint specifies a particular mailbox. Perform full comparison. */
 107     if (mailbox_range.location != kCFNotFound) {
 108         if (!CFStringCompare(emailAddress, constraint, kCFCompareCaseInsensitive)) {
 109             return true;
 110         }
 111         else return false;
 112     }
 113
 114     mailbox_range = CFStringFind(emailAddress, CFSTR("@"), 0);
 115     require_quiet(mailbox_range.location != kCFNotFound, out);
 116     CFRange hostname_range = {mailbox_range.location + 1,
 117         CFStringGetLength(emailAddress) - mailbox_range.location - 1 };
 118
 119     /* Constraint specificies a particular host. Compare hostname of address. */
 120     if ('.' != CFStringGetCharacterAtIndex(constraint, 0)) {
 121         if (!CFStringCompareWithOptions(emailAddress, constraint, hostname_range, kCFCompareCaseInsensitive)) {
 122             return true;
 123         }
 124         else return false;
 125     }
 126
 127     /* Constraint specificies a domain. Match hostname of address to domain name. */
 128     require_quiet('.' != CFStringGetCharacterAtIndex(emailAddress, mailbox_range.location +1), out);
 129     if (CFStringHasSuffix(emailAddress, constraint)) {
 130         return true;
 131     }
 132
 133 out:
 134     return false;
 135 }
 136
 137 static bool nc_compare_directoryNames(const DERItem *certName, const DERItem *subtreeName) {
 138     /* Get content of certificate name and subtree name */
 139     DERDecodedInfo certName_content;
 140     require_noerr_quiet(DERDecodeItem(certName, &certName_content), out);
 141
 142     DERDecodedInfo subtreeName_content;
 143     require_noerr_quiet(DERDecodeItem(subtreeName, &subtreeName_content), out);
 144
 145     if (certName->length > subtreeName->length) {
 146         if(0 == memcmp(certName_content.content.data,
 147                        subtreeName_content.content.data,
 148                        subtreeName_content.content.length)) {
 149             return true;
 150         }
 151     }
 152
 153 out:
 154     return false;
 155 }
 156
 157 static bool nc_compare_DNSNames(const DERItem *certName, const DERItem *subtreeName) {
 158     bool result = false;
 159     CFStringRef subtreeName_with_wildcard = NULL;
 160     CFStringRef certName_str = CFStringCreateWithBytes(kCFAllocatorDefault,
 161                                                        certName->data, certName->length,
 162                                                        kCFStringEncodingUTF8, FALSE);
 163     CFStringRef subtreeName_str = CFStringCreateWithBytes(kCFAllocatorDefault,
 164                                                           subtreeName->data, subtreeName->length,
 165                                                           kCFStringEncodingUTF8, FALSE);
 166     require_quiet(certName_str, out);
 167     require_quiet(subtreeName_str, out);
 168     /*
 169      * We'll also compose a string with a preceding wildcard label since:
 170      *      "Any DNS name that can be constructed by simply adding zero or more labels to
 171      *      the left-hand side of the name satisfies the name constraint."
 172      */
 173     subtreeName_with_wildcard = CFStringCreateWithFormat(kCFAllocatorDefault,
 174                                                          NULL,
 175                                                          CFSTR("*.%s"),
 176                                                          CFStringGetCStringPtr(subtreeName_str,
 177                                                                                kCFStringEncodingUTF8));
 178     require_quiet(subtreeName_with_wildcard, out);
 179
 180     if (SecDNSMatch(certName_str, subtreeName_str) || SecDNSMatch(certName_str, subtreeName_with_wildcard)) {
 181         result = true;
 182     }
 183
 184 out:
 185     CFReleaseNull(certName_str) ;
 186     CFReleaseNull(subtreeName_str);
 187     CFReleaseNull(subtreeName_with_wildcard);
 188     return result;
 189 }
 190
 191 static bool nc_compare_URIs(const DERItem *certName, const DERItem *subtreeName) {
 192     bool result = false;
 193     CFStringRef certName_str = CFStringCreateWithBytes(kCFAllocatorDefault,
 194                                                        certName->data, certName->length,
 195                                                        kCFStringEncodingUTF8, FALSE);
 196     CFStringRef subtreeName_str = CFStringCreateWithBytes(kCFAllocatorDefault,
 197                                                           subtreeName->data, subtreeName->length,
 198                                                           kCFStringEncodingUTF8, FALSE);
 199     require_quiet(certName_str, out);
 200     require_quiet(subtreeName_str, out);
 201
 202     if (SecURIMatch(certName_str, subtreeName_str)) {
 203         result = true;
 204     }
 205
 206 out:
 207     CFReleaseNull(certName_str);
 208     CFReleaseNull(subtreeName_str);
 209     return result;
 210 }
 211
 212 static bool nc_compare_RFC822Names(const DERItem *certName, const DERItem *subtreeName) {
 213     bool result = false;
 214     CFStringRef certName_str = CFStringCreateWithBytes(kCFAllocatorDefault,
 215                                                        certName->data, certName->length,
 216                                                        kCFStringEncodingUTF8, FALSE);
 217     CFStringRef subtreeName_str = CFStringCreateWithBytes(kCFAllocatorDefault,
 218                                                           subtreeName->data, subtreeName->length,
 219                                                           kCFStringEncodingUTF8, FALSE);
 220     require_quiet(certName_str, out);
 221     require_quiet(subtreeName_str, out);
 222
 223     if (SecRFC822NameMatch(certName_str, subtreeName_str)) {
 224         result = true;
 225     }
 226
 227 out:
 228     CFReleaseNull(certName_str);
 229     CFReleaseNull(subtreeName_str);
 230     return result;
 231 }
 232
 233 static bool nc_compare_IPAddresses(const DERItem *certAddr, const DERItem *subtreeAddr) {
 234     bool result = false;
 235
 236     /* Verify Subtree Address has correct number of bytes for IP and mask */
 237     require_quiet((subtreeAddr->length == 8) || (subtreeAddr->length == 32), out);
 238     /* Verify Cert Address has correct number of bytes for IP */
 239     require_quiet((certAddr->length == 4) || (certAddr->length ==16), out);
 240     /* Verify Subtree Address and Cert Address are the same version */
 241     require_quiet(subtreeAddr->length == 2*certAddr->length, out);
 242
 243     DERByte * mask = subtreeAddr->data + certAddr->length;
 244     for (DERSize i = 0; i < certAddr->length; i++) {
 245         if((subtreeAddr->data[i] & mask[i]) != (certAddr->data[i] & mask[i])) {
 246             return false;
 247         }
 248     }
 249     return true;
 250
 251 out:
 252     return result;
 253 }
 254
 255 typedef struct {
 256     bool present;
 257     bool isMatch;
 258 } match_t;
 259
 260 typedef struct {
 261     const SecCEGeneralNameType gnType;
 262     const DERItem *cert_item;
 263     match_t *match;
 264 } nc_match_context_t;
 265
 266 typedef struct {
 267     const CFArrayRef subtrees;
 268     match_t *match;
 269 } nc_san_match_context_t;
 270
 271 static OSStatus nc_compare_subtree(void *context, SecCEGeneralNameType gnType, const DERItem *generalName) {
 272     nc_match_context_t *item_context = context;
 273     if (item_context && gnType == item_context->gnType
 274         && item_context->match && item_context->cert_item) {
 275
 276         item_context->match->present = true;
 277         /*
 278          * We set isMatch such that if there are multiple subtrees of the same type, matching to any one
 279          * of them is considered a match.
 280          */
 281         switch (gnType) {
 282             case GNT_DirectoryName: {
 283                 item_context->match->isMatch |= nc_compare_directoryNames(item_context->cert_item, generalName);
 284                 return errSecSuccess;
 285             }
 286             case GNT_DNSName: {
 287                 item_context->match->isMatch |= nc_compare_DNSNames(item_context->cert_item, generalName);
 288                 return errSecSuccess;
 289             }
 290             case GNT_URI: {
 291                 item_context->match->isMatch |= nc_compare_URIs(item_context->cert_item, generalName);
 292                 return errSecSuccess;
 293             }
 294             case GNT_RFC822Name: {
 295                 item_context->match->isMatch |= nc_compare_RFC822Names(item_context->cert_item, generalName);
 296                 return errSecSuccess;
 297             }
 298             case  GNT_IPAddress: {
 299                 item_context->match->isMatch |= nc_compare_IPAddresses(item_context->cert_item, generalName);
 300                 return errSecSuccess;
 301             }
 302             default: {
 303                 /* If the name form is not supported, reject the certificate. */
 304                 return errSecInvalidCertificate;
 305             }
 306         }
 307     }
 308
 309     return errSecInvalidCertificate;
 310 }
 311
 312 static void nc_decode_and_compare_subtree(const void *value, void *context) {
 313     CFDataRef subtree = value;
 314     nc_match_context_t *match_context = context;
 315     if(subtree) {
 316         /* convert subtree to DERItem */
 317         const DERItem general_name = { (unsigned char *)CFDataGetBytePtr(subtree), CFDataGetLength(subtree) };
 318         DERDecodedInfo general_name_content;
 319         require_noerr_quiet(DERDecodeItem(&general_name, &general_name_content),out);
 320
 321         OSStatus status = SecCertificateParseGeneralNameContentProperty(general_name_content.tag,
 322                                                                         &general_name_content.content,
 323                                                                         match_context,
 324                                                                         nc_compare_subtree);
 325         if (status == errSecInvalidCertificate) {
 326             secdebug("policy","can't parse general name or not a type we support");
 327         }
 328     }
 329 out:
 330     return;
 331 }
 332
 333 static bool isEmptySubject(CFDataRef subject) {
 334     const DERItem subject_der = { (unsigned char *)CFDataGetBytePtr(subject), CFDataGetLength(subject) };
 335
 336     /* Get content of certificate name */
 337     DERDecodedInfo subject_content;
 338     require_noerr_quiet(DERDecodeItem(&subject_der, &subject_content), out);
 339     if (subject_content.content.length) return false;
 340
 341 out:
 342     return true;
 343 }
 344
 345 static bool nc_compare_subject_to_subtrees(CFDataRef subject, CFArrayRef subtrees) {
 346     /* An empty subject name is considered a match */
 347     if (isEmptySubject(subject))
 348         return true;
 349
 350     CFIndex num_trees = CFArrayGetCount(subtrees);
 351     CFRange range = { 0, num_trees };
 352     const DERItem subject_der = { (unsigned char *)CFDataGetBytePtr(subject), CFDataGetLength(subject) };
 353     match_t match = { false, false };
 354     nc_match_context_t context = {GNT_DirectoryName, &subject_der, &match};
 355     CFArrayApplyFunction(subtrees, range, nc_decode_and_compare_subtree, &context);
 356
 357     /* If no directory name amongst the subtrees, then return success. */
 358     if (!match.present) return true;
 359     else return match.isMatch;
 360 }
 361
 362 static void nc_compare_RFC822Name_to_subtrees(const void *value, void *context) {
 363     CFStringRef rfc822Name = value;
 364     nc_san_match_context_t *san_context = context;
 365     CFArrayRef subtrees = NULL;
 366     if (san_context) {
 367         subtrees = san_context->subtrees;
 368     }
 369     if (subtrees) {
 370         CFIndex num_trees = CFArrayGetCount(subtrees);
 371         CFRange range = { 0, num_trees };
 372         match_t match = { false, false };
 373         const DERItem addr = { (unsigned char *)CFStringGetCStringPtr(rfc822Name, kCFStringEncodingUTF8),
 374                               CFStringGetLength(rfc822Name) };
 375         nc_match_context_t match_context = {GNT_RFC822Name, &addr, &match};
 376         CFArrayApplyFunction(subtrees, range, nc_decode_and_compare_subtree, &match_context);
 377
 378         /*
 379          * We set the SAN context match struct as follows:
 380          * 'present' is true if there's any subtree of the same type as any SAN
 381          * 'match' is false if the present type(s) is/are not supported or the subtree(s) and SAN(s) don't match.
 382          * Note: the state of 'match' is meaningless without 'present' also being true.
 383          */
 384         if (match.present && san_context->match) {
 385             san_context->match->present = true;
 386             san_context->match->isMatch &= match.isMatch;
 387         }
 388     }
 389
 390 }
 391
 392 static OSStatus nc_compare_subjectAltName_to_subtrees(void *context, SecCEGeneralNameType gnType, const DERItem *generalName) {
 393     nc_san_match_context_t *san_context = context;
 394     CFArrayRef subtrees = NULL;
 395     if (san_context) {
 396         subtrees = san_context->subtrees;
 397     }
 398     if (subtrees) {
 399         CFIndex num_trees = CFArrayGetCount(subtrees);
 400         CFRange range = { 0, num_trees };
 401         match_t match = { false, false };
 402         nc_match_context_t match_context = {gnType, generalName, &match};
 403         CFArrayApplyFunction(subtrees, range, nc_decode_and_compare_subtree, &match_context);
 404
 405         /*
 406          * We set the SAN context match struct as follows:
 407          * 'present' is true if there's any subtree of the same type as any SAN
 408          * 'match' is false if the present type(s) is/are not supported or the subtree(s) and SAN(s) don't match.
 409          * Note: the state of 'match' is meaningless without 'present' also being true.
 410          */
 411         if (match.present && san_context->match) {
 412             san_context->match->present = true;
 413             san_context->match->isMatch &= match.isMatch;
 414         }
 415
 416         return errSecSuccess;
 417     }
 418
 419     return errSecInvalidCertificate;
 420 }
 421
 422 OSStatus SecNameContraintsMatchSubtrees(SecCertificateRef certificate, CFArrayRef subtrees, bool *matched) {
 423     CFDataRef subject = NULL;
 424     OSStatus status = errSecSuccess;
 425     CFArrayRef rfc822Names = NULL;
 426
 427     require_action_quiet(subject = SecCertificateCopySubjectSequence(certificate),
 428                          out,
 429                          status = errSecInvalidCertificate);
 430     const DERItem *subjectAltNames = SecCertificateGetSubjectAltName(certificate);
 431
 432     /* Reject certificates with neither Subject Name nor SubjectAltName */
 433     require_action_quiet(!isEmptySubject(subject) || subjectAltNames, out, *matched = false);
 434
 435     /* Verify that the subject name is within any of the subtrees for X.500 distinguished names */
 436     require_action_quiet(nc_compare_subject_to_subtrees(subject,subtrees), out, *matched = false);
 437
 438     match_t san_match = { false, true };
 439     nc_san_match_context_t san_context = {subtrees, &san_match};
 440
 441     /* If there are no subjectAltNames, then determine if there's a matching emailAddress in the Subject */
 442     if (!subjectAltNames) {
 443         rfc822Names = SecCertificateCopyRFC822Names(certificate);
 444         /* If there's also no emailAddress field then subject match is enough. */
 445         require_action_quiet(rfc822Names, out, *matched = true);
 446         CFRange range = { 0 , CFArrayGetCount(rfc822Names) };
 447         CFArrayApplyFunction(rfc822Names, range, nc_compare_RFC822Name_to_subtrees, &san_context);
 448
 449         if (san_match.present && !san_match.isMatch) {
 450             *matched = false;
 451         }
 452         else {
 453             *matched = true;
 454         }
 455     }
 456     else {
 457         /* And verify that each of the alternative names in the subjectAltName extension (critical or non-critical)
 458          * is within any of the subtrees for that name type. */
 459         status = SecCertificateParseGeneralNames(subjectAltNames,
 460                                                  &san_context,
 461                                                  nc_compare_subjectAltName_to_subtrees);
 462         /* If failed to parse or failed to match SAN(s) to subtree(s) of same type */
 463         if((status != errSecSuccess) || (san_match.present && !san_match.isMatch)) {
 464             *matched = false;
 465         }
 466         else {
 467             *matched = true;
 468         }
 469     }
 470
 471 out:
 472     CFReleaseNull(subject);
 473     CFReleaseNull(rfc822Names);
 474     return status;
 475 }
 476
 477 /* The recommended processing algorithm states:
 478  *    If permittedSubtrees is present in the certificate, set the permitted_subtrees state variable to the intersection
 479  *    of its previous value and the value indicated in the extension field.
 480  * However, in practice, certs are issued with permittedSubtrees whose intersection would be the empty set. Wherever
 481  * a new permittedSubtree is a subset of an existing subtree, we'll replace the existing subtree; otherwise, we just
 482  * append the new subtree.
 483  */
 484 static void nc_intersect_tree_with_subtrees (const void *value, void *context) {
 485     CFDataRef new_subtree = value;
 486     CFMutableArrayRef *existing_subtrees = context;
 487
 488     if (!new_subtree || !*existing_subtrees) return;
 489
 490     /* convert new subtree to DERItem */
 491     const DERItem general_name = { (unsigned char *)CFDataGetBytePtr(new_subtree), CFDataGetLength(new_subtree) };
 492     DERDecodedInfo general_name_content;
 493     if(DR_Success != DERDecodeItem(&general_name, &general_name_content)) return;
 494
 495     SecCEGeneralNameType gnType;
 496     DERItem *new_subtree_item = &general_name_content.content;
 497
 498     /* Attempt to intersect if one of the supported types: DirectoryName and DNSName.
 499      * Otherwise, just append the new tree.
 500      */
 501     switch (general_name_content.tag) {
 502         case ASN1_CONTEXT_SPECIFIC | 2: {
 503             gnType = GNT_DNSName;
 504             break;
 505         }
 506         case ASN1_CONTEXT_SPECIFIC | ASN1_CONSTRUCTED | 4: {
 507             gnType = GNT_DirectoryName;
 508             break;
 509         }
 510         default: {
 511             CFArrayAppendValue(*existing_subtrees, new_subtree);
 512             return;
 513         }
 514     }
 515
 516     CFIndex subtreeIX;
 517     CFIndex num_existing_subtrees = CFArrayGetCount(*existing_subtrees);
 518     match_t match = { false, false };
 519     nc_match_context_t match_context = { gnType, new_subtree_item, &match};
 520     for (subtreeIX = 0; subtreeIX < num_existing_subtrees; subtreeIX++) {
 521         CFDataRef candidate_subtree = CFArrayGetValueAtIndex(*existing_subtrees, subtreeIX);
 522         /* Convert candidate subtree to DERItem */
 523         const DERItem candidate = { (unsigned char *)CFDataGetBytePtr(candidate_subtree), CFDataGetLength(candidate_subtree) };
 524         DERDecodedInfo candidate_content;
 525         /* We could probably just delete any subtrees in the array that don't decode */
 526         if(DR_Success != DERDecodeItem(&candidate, &candidate_content)) continue;
 527
 528         OSStatus status = SecCertificateParseGeneralNameContentProperty(candidate_content.tag,
 529                                                                         &candidate_content.content,
 530                                                                         &match_context,
 531                                                                         nc_compare_subtree);
 532         if((status == errSecSuccess) && match.present && match.isMatch) {
 533             break;
 534         }
 535     }
 536     if (subtreeIX == num_existing_subtrees) {
 537         /* No matches found. Append new subtree */
 538         CFArrayAppendValue(*existing_subtrees, new_subtree);
 539     }
 540     else {
 541         CFArraySetValueAtIndex(*existing_subtrees, subtreeIX, new_subtree);
 542     }
 543     return;
 544
 545 }
 546
 547 void SecNameConstraintsIntersectSubtrees(CFMutableArrayRef subtrees_state, CFArrayRef subtrees_new) {
 548     assert(subtrees_state);
 549     assert(subtrees_new);
 550
 551     CFIndex num_new_trees = CFArrayGetCount(subtrees_new);
 552     CFRange range = { 0, num_new_trees };
 553     CFArrayApplyFunction(subtrees_new, range, nc_intersect_tree_with_subtrees, &subtrees_state);
 554 }