From e59165a1e3df2f1cbe223406ea4fb40025e54d8a Mon Sep 17 00:00:00 2001 From: Niels Provos Date: Tue, 12 May 2026 09:44:12 -0700 Subject: [PATCH] crypto/x509: replace O(N^2) RFC 3779 canonicalisation merge with linear sweep ASIdentifierChoice_canonize and IPAddressOrRanges_canonize previously merged adjacent entries with an in-place loop that called sk_..._delete() after each merge, making the merge O(N^2) due to the per-merge stack shift. Replace the merge with a single linear sweep using a write index distinct from the read cursor: mergeable entries fold into the previous output's upper bound in O(1), non-mergeable entries are slid forward into the write slot, and the source slot is set to NULL so the ASN.1 free machinery cannot double-free on a subsequent abort. Canonicalisation is now O(N log N) overall, bounded by the existing sort. Mixed-state-on-error safety is provided by the caller's normal teardown path: OPENSSL_sk_pop unlinks without freeing, OPENSSL_sk_set replaces without freeing the displaced value, and ossl_asn1_item_embed_free no-ops on NULL slots, so returning early on an inner failure leaves the stack in a state that the choice's normal free path handles cleanly. New regression tests in test/v3ext.c at N=8192 cover the all-merge, no-merge, interleaved (slide-forward), range-merge, overlap-mid-sweep, and inverted-range-mid-sweep paths; the mixed-state teardown invariant is exercised under ASan + UBSan. Reviewed-by: Paul Dale Reviewed-by: Bob Beck MergeDate: Fri Jul 3 19:20:01 2026 (Merged from https://github.com/openssl/openssl/pull/31147) --- crypto/x509/v3_addr.c | 123 +++++---- crypto/x509/v3_asid.c | 198 ++++++++------ test/v3ext.c | 598 ++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 789 insertions(+), 130 deletions(-) diff --git a/crypto/x509/v3_addr.c b/crypto/x509/v3_addr.c index 1e0d94babf1..bdaa74a0d1c 100644 --- a/crypto/x509/v3_addr.c +++ b/crypto/x509/v3_addr.c @@ -760,6 +760,7 @@ int X509v3_addr_is_canonical(IPAddrBlocks *addr) aors = f->ipAddressChoice->u.addressesOrRanges; if (sk_IPAddressOrRange_num(aors) == 0) return 0; + for (j = 0; j < sk_IPAddressOrRange_num(aors) - 1; j++) { IPAddressOrRange *a = sk_IPAddressOrRange_value(aors, j); IPAddressOrRange *b = sk_IPAddressOrRange_value(aors, j + 1); @@ -814,78 +815,106 @@ int X509v3_addr_is_canonical(IPAddrBlocks *addr) /* * Whack an IPAddressOrRanges into canonical form. + * + * After the initial sort, the merge runs as a single linear sweep + * over the list using a write index. Adjacent entries are folded + * into the previous output by replacing it with a freshly built + * merged range; both old entries are then freed and the source slot + * is left NULL so the asn1 free machinery does not double-free on a + * subsequent abort. Total cost is O(N log N) sort + O(N) merge, + * with no stack deletes inside the loop. */ static int IPAddressOrRanges_canonize(IPAddressOrRanges *aors, const unsigned afi) { - int i, j, length = length_from_afi(afi); + int length = length_from_afi(afi); + int read, write = 0, n; - /* - * Sort the IPAddressOrRanges sequence. - */ sk_IPAddressOrRange_sort(aors); + n = sk_IPAddressOrRange_num(aors); /* - * Clean up representation issues, punt on duplicates or overlaps. + * Error paths below all `return 0` directly. Slots at + * [write..read-1] are NULL (from earlier iterations) and slots at + * [read..n-1] still hold their original entries; the caller's + * normal teardown walks the whole stack and frees each non-NULL + * slot safely, so leaving the stack in this mixed state is sound. */ - for (i = 0; i < sk_IPAddressOrRange_num(aors) - 1; i++) { - IPAddressOrRange *a = sk_IPAddressOrRange_value(aors, i); - IPAddressOrRange *b = sk_IPAddressOrRange_value(aors, i + 1); - unsigned char a_min[ADDR_RAW_BUF_LEN], a_max[ADDR_RAW_BUF_LEN]; - unsigned char b_min[ADDR_RAW_BUF_LEN], b_max[ADDR_RAW_BUF_LEN]; + for (read = 0; read < n; read++) { + IPAddressOrRange *cur = sk_IPAddressOrRange_value(aors, read); + unsigned char c_min[ADDR_RAW_BUF_LEN], c_max[ADDR_RAW_BUF_LEN]; - if (!extract_min_max(a, a_min, a_max, length) || !extract_min_max(b, b_min, b_max, length)) + if (!extract_min_max(cur, c_min, c_max, length)) return 0; /* - * Punt inverted ranges. + * Punt inverted range. */ - if (memcmp(a_min, a_max, length) > 0 || memcmp(b_min, b_max, length) > 0) + if (memcmp(c_min, c_max, length) > 0) return 0; - /* - * Punt overlaps. - */ - if (memcmp(a_max, b_min, length) >= 0) - return 0; + if (write > 0) { + IPAddressOrRange *prev = sk_IPAddressOrRange_value(aors, + write - 1); + unsigned char p_min[ADDR_RAW_BUF_LEN], p_max[ADDR_RAW_BUF_LEN]; + unsigned char c_min_minus_one[ADDR_RAW_BUF_LEN]; + int j; - /* - * Merge if a and b are adjacent. We check for - * adjacency by subtracting one from b_min first. - */ - for (j = length - 1; j >= 0 && b_min[j]-- == 0x00; j--) - ; - if (memcmp(a_max, b_min, length) == 0) { - IPAddressOrRange *merged; + if (!extract_min_max(prev, p_min, p_max, length)) + return 0; - if (!make_addressRange(&merged, a_min, b_max, length)) + /* + * Reject overlap with the previous accepted entry. + */ + if (memcmp(p_max, c_min, length) >= 0) return 0; - (void)sk_IPAddressOrRange_set(aors, i, merged); - (void)sk_IPAddressOrRange_delete(aors, i + 1); - IPAddressOrRange_free(a); - IPAddressOrRange_free(b); - --i; - continue; - } - } - /* - * Check for inverted final range. - */ - j = sk_IPAddressOrRange_num(aors) - 1; - { - IPAddressOrRange *a = sk_IPAddressOrRange_value(aors, j); + /* + * Adjacency test: does c_min - 1 equal p_max? Work on a + * scratch copy so the original c_min stays intact for use + * as the lower bound if we end up keeping cur. + */ + memcpy(c_min_minus_one, c_min, length); + for (j = length - 1; + j >= 0 && c_min_minus_one[j]-- == 0x00; + j--) + ; + if (memcmp(p_max, c_min_minus_one, length) == 0) { + IPAddressOrRange *merged; - if (a != NULL && a->type == IPAddressOrRange_addressRange) { - unsigned char a_min[ADDR_RAW_BUF_LEN], a_max[ADDR_RAW_BUF_LEN]; + if (!make_addressRange(&merged, p_min, c_max, length)) + return 0; + /* + * Replace prev with merged, free the originals, and + * NULL the source slot so the stack does not retain a + * second reference to cur. + */ + (void)sk_IPAddressOrRange_set(aors, write - 1, merged); + IPAddressOrRange_free(prev); + IPAddressOrRange_free(cur); + (void)sk_IPAddressOrRange_set(aors, read, NULL); + continue; + } + } - if (!extract_min_max(a, a_min, a_max, length)) - return 0; - if (memcmp(a_min, a_max, length) > 0) - return 0; + /* + * Keep cur. Slide it forward into the write slot if we have + * fallen behind, and NULL the source slot to avoid duplicate + * ownership. + */ + if (write != read) { + (void)sk_IPAddressOrRange_set(aors, write, cur); + (void)sk_IPAddressOrRange_set(aors, read, NULL); } + write++; } + /* + * Compaction succeeded: every slot at [write..n-1] is NULL, so + * popping the tail leaves the canonicalised list at [0..write-1]. + */ + while (sk_IPAddressOrRange_num(aors) > write) + (void)sk_IPAddressOrRange_pop(aors); return 1; } diff --git a/crypto/x509/v3_asid.c b/crypto/x509/v3_asid.c index 8470e0f134d..c00ded15f9e 100644 --- a/crypto/x509/v3_asid.c +++ b/crypto/x509/v3_asid.c @@ -347,13 +347,22 @@ int X509v3_asid_is_canonical(ASIdentifiers *asid) /* * Whack an ASIdentifierChoice into canonical form. + * + * After the initial sort, the merge runs as a single linear sweep + * over the list using a write index. Each entry is examined once; + * adjacent / mergeable entries extend the previous output's upper + * bound in O(1) and the source slot is left NULL so the asn1 free + * machinery does not double-free on a subsequent abort. Total cost + * is O(N log N) sort + O(N) merge, with no stack deletes inside the + * loop. */ static int ASIdentifierChoice_canonize(ASIdentifierChoice *choice) { ASN1_INTEGER *a_max_plus_one = NULL; ASN1_INTEGER *orig; BIGNUM *bn = NULL; - int i, ret = 0; + int read, write = 0, n; + int ret = 0; /* * Nothing to do for empty element or inheritance. @@ -370,112 +379,135 @@ static int ASIdentifierChoice_canonize(ASIdentifierChoice *choice) } /* - * We have a non-empty list. Sort it. + * Sort the list, then merge in a single sweep using a write index. */ sk_ASIdOrRange_sort(choice->u.asIdsOrRanges); + n = sk_ASIdOrRange_num(choice->u.asIdsOrRanges); - /* - * Now check for errors and suboptimal encoding, rejecting the - * former and fixing the latter. - */ - for (i = 0; i < sk_ASIdOrRange_num(choice->u.asIdsOrRanges) - 1; i++) { - ASIdOrRange *a = sk_ASIdOrRange_value(choice->u.asIdsOrRanges, i); - ASIdOrRange *b = sk_ASIdOrRange_value(choice->u.asIdsOrRanges, i + 1); - ASN1_INTEGER *a_min = NULL, *a_max = NULL, *b_min = NULL, *b_max = NULL; + for (read = 0; read < n; read++) { + ASIdOrRange *cur = sk_ASIdOrRange_value(choice->u.asIdsOrRanges, read); + ASN1_INTEGER *c_min = NULL, *c_max = NULL; - if (!extract_min_max(a, &a_min, &a_max) - || !extract_min_max(b, &b_min, &b_max)) + if (!extract_min_max(cur, &c_min, &c_max)) goto done; /* - * Make sure we're properly sorted (paranoia). + * Punt inverted range. */ - if (!ossl_assert(ASN1_INTEGER_cmp(a_min, b_min) <= 0)) + if (ASN1_INTEGER_cmp(c_min, c_max) > 0) goto done; - /* - * Punt inverted ranges. - */ - if (ASN1_INTEGER_cmp(a_min, a_max) > 0 || ASN1_INTEGER_cmp(b_min, b_max) > 0) - goto done; + if (write > 0) { + ASIdOrRange *prev = sk_ASIdOrRange_value(choice->u.asIdsOrRanges, + write - 1); + ASN1_INTEGER *p_min = NULL, *p_max = NULL; - /* - * Check for overlaps. - */ - if (ASN1_INTEGER_cmp(a_max, b_min) >= 0) { - ERR_raise(ERR_LIB_X509V3, X509V3_R_EXTENSION_VALUE_ERROR); - goto done; - } + if (!extract_min_max(prev, &p_min, &p_max)) + goto done; - /* - * Calculate a_max + 1 to check for adjacency. - */ - if ((bn == NULL && (bn = BN_new()) == NULL) || ASN1_INTEGER_to_BN(a_max, bn) == NULL || !BN_add_word(bn, 1)) { - ERR_raise(ERR_LIB_X509V3, ERR_R_BN_LIB); - goto done; - } + /* + * Make sure we're properly sorted (paranoia). + */ + if (!ossl_assert(ASN1_INTEGER_cmp(p_min, c_min) <= 0)) + goto done; - if ((a_max_plus_one = BN_to_ASN1_INTEGER(bn, orig = a_max_plus_one)) == NULL) { - a_max_plus_one = orig; - ERR_raise(ERR_LIB_X509V3, ERR_R_ASN1_LIB); - goto done; - } + /* + * Reject overlap with the previous accepted entry. + */ + if (ASN1_INTEGER_cmp(p_max, c_min) >= 0) { + ERR_raise(ERR_LIB_X509V3, X509V3_R_EXTENSION_VALUE_ERROR); + goto done; + } - /* - * If a and b are adjacent, merge them. - */ - if (ASN1_INTEGER_cmp(a_max_plus_one, b_min) == 0) { - ASRange *r; - switch (a->type) { - case ASIdOrRange_id: - if ((r = OPENSSL_malloc(sizeof(*r))) == NULL) - goto done; - r->min = a_min; - r->max = b_max; - a->type = ASIdOrRange_range; - a->u.range = r; - break; - case ASIdOrRange_range: - ASN1_INTEGER_free(a->u.range->max); - a->u.range->max = b_max; - break; + /* + * Calculate p_max + 1 to check for adjacency. + */ + if ((bn == NULL && (bn = BN_new()) == NULL) + || ASN1_INTEGER_to_BN(p_max, bn) == NULL + || !BN_add_word(bn, 1)) { + ERR_raise(ERR_LIB_X509V3, ERR_R_BN_LIB); + goto done; } - switch (b->type) { - case ASIdOrRange_id: - b->u.id = NULL; - break; - case ASIdOrRange_range: - b->u.range->max = NULL; - break; + if ((a_max_plus_one = BN_to_ASN1_INTEGER(bn, + orig = a_max_plus_one)) + == NULL) { + a_max_plus_one = orig; + ERR_raise(ERR_LIB_X509V3, ERR_R_ASN1_LIB); + goto done; + } + + /* + * If prev and cur are adjacent, fold cur into prev. + */ + if (ASN1_INTEGER_cmp(a_max_plus_one, c_min) == 0) { + ASRange *r; + + switch (prev->type) { + case ASIdOrRange_id: + if ((r = OPENSSL_malloc(sizeof(*r))) == NULL) + goto done; + r->min = p_min; + r->max = c_max; + prev->type = ASIdOrRange_range; + prev->u.range = r; + break; + case ASIdOrRange_range: + ASN1_INTEGER_free(prev->u.range->max); + prev->u.range->max = c_max; + break; + } + /* + * Detach c_max from cur so freeing cur does not free + * the value we just transferred to prev. + */ + switch (cur->type) { + case ASIdOrRange_id: + cur->u.id = NULL; + break; + case ASIdOrRange_range: + cur->u.range->max = NULL; + break; + } + ASIdOrRange_free(cur); + /* + * NULL the source slot so any later teardown does not + * walk a freed pointer. We do not advance `write`. + */ + (void)sk_ASIdOrRange_set(choice->u.asIdsOrRanges, read, NULL); + continue; } - ASIdOrRange_free(b); - (void)sk_ASIdOrRange_delete(choice->u.asIdsOrRanges, i + 1); - i--; - continue; } - } - /* - * Check for final inverted range. - */ - i = sk_ASIdOrRange_num(choice->u.asIdsOrRanges) - 1; - { - ASIdOrRange *a = sk_ASIdOrRange_value(choice->u.asIdsOrRanges, i); - ASN1_INTEGER *a_min, *a_max; - if (a != NULL && a->type == ASIdOrRange_range) { - if (!extract_min_max(a, &a_min, &a_max) - || ASN1_INTEGER_cmp(a_min, a_max) > 0) - goto done; + /* + * Keep cur. Slide it forward into the write slot if we have + * fallen behind, and NULL the source slot to avoid duplicate + * ownership. + */ + if (write != read) { + (void)sk_ASIdOrRange_set(choice->u.asIdsOrRanges, write, cur); + (void)sk_ASIdOrRange_set(choice->u.asIdsOrRanges, read, NULL); } + write++; } - /* Paranoia */ - if (!ossl_assert(ASIdentifierChoice_is_canonical(choice))) - goto done; - ret = 1; done: + /* + * On success every slot at [write..n-1] is NULL, so popping the + * tail leaves the canonicalised list at [0..write-1]. On error we + * leave the tail untouched; the slots are either NULL (from earlier + * iterations) or original entries the loop never reached, both of + * which the caller's ASIdentifierChoice_free path handles safely. + */ + if (ret) { + while (sk_ASIdOrRange_num(choice->u.asIdsOrRanges) > write) + (void)sk_ASIdOrRange_pop(choice->u.asIdsOrRanges); + /* Paranoia */ + if (!ossl_assert(ASIdentifierChoice_is_canonical(choice))) + ret = 0; + } + ASN1_INTEGER_free(a_max_plus_one); BN_free(bn); return ret; diff --git a/test/v3ext.c b/test/v3ext.c index 2e852804ee3..e2b64411977 100644 --- a/test/v3ext.c +++ b/test/v3ext.c @@ -417,6 +417,595 @@ static int test_ext_syntax(void) return testresult; } +/* + * Number of entries the large-canonize regression tests construct. + * Chosen well above the legacy 4096 cap and large enough that the + * previous O(N^2) merge would be visibly slow under any sanitiser + * configuration, while still small enough to keep CI cost negligible + * with the linear merge. + */ +#define V3EXT_TEST_LARGE_N 8192 + +/* + * Build an ASIdentifiers extension containing V3EXT_TEST_LARGE_N + * adjacent single integers (1, 2, 3, ...), exercise canonize, and + * verify that the entire list collapses to one ASIdOrRange_range and + * that the post-canonize result reports canonical. Stresses the + * linear merge path that replaced the quadratic in-place delete. + */ +static int test_asid_large_canonize_merge(void) +{ + ASIdentifiers *asid = NULL; + ASN1_INTEGER *val = NULL; + int i; + int testresult = 0; + + if (!TEST_ptr(asid = ASIdentifiers_new())) + goto err; + + for (i = 0; i < V3EXT_TEST_LARGE_N; i++) { + if (!TEST_ptr(val = ASN1_INTEGER_new()) + || !TEST_true(ASN1_INTEGER_set_int64(val, (int64_t)(i + 1)))) + goto err; + if (!TEST_true(X509v3_asid_add_id_or_range(asid, V3_ASID_ASNUM, + val, NULL))) + goto err; + /* Ownership of val transferred on success. */ + val = NULL; + } + + if (!TEST_int_eq(sk_ASIdOrRange_num(asid->asnum->u.asIdsOrRanges), + V3EXT_TEST_LARGE_N)) + goto err; + + if (!TEST_true(X509v3_asid_canonize(asid))) + goto err; + + /* The whole list must collapse to a single merged range [1, N]. */ + if (!TEST_int_eq(sk_ASIdOrRange_num(asid->asnum->u.asIdsOrRanges), 1)) + goto err; + { + ASIdOrRange *aor = sk_ASIdOrRange_value(asid->asnum->u.asIdsOrRanges, + 0); + int64_t got_min = 0, got_max = 0; + + if (!TEST_ptr(aor) || !TEST_int_eq(aor->type, ASIdOrRange_range)) + goto err; + if (!TEST_true(ASN1_INTEGER_get_int64(&got_min, aor->u.range->min)) + || !TEST_int64_t_eq(got_min, 1) + || !TEST_true(ASN1_INTEGER_get_int64(&got_max, aor->u.range->max)) + || !TEST_int64_t_eq(got_max, (int64_t)V3EXT_TEST_LARGE_N)) + goto err; + } + + if (!TEST_int_eq(X509v3_asid_is_canonical(asid), 1)) + goto err; + + testresult = 1; +err: + ASN1_INTEGER_free(val); + ASIdentifiers_free(asid); + return testresult; +} + +/* + * Build an ASIdentifiers extension containing V3EXT_TEST_LARGE_N + * non-mergeable single integers (1, 3, 5, ...). After canonize the + * list must be unchanged in length, every entry must remain an id + * with its original value (none silently merged or transformed), and + * is_canonical must report canonical -- i.e. the large list is + * accepted on its merits with no arbitrary cap kicking in. + */ +static int test_asid_large_canonize_no_merge(void) +{ + ASIdentifiers *asid = NULL; + ASN1_INTEGER *val = NULL; + int i; + int testresult = 0; + + if (!TEST_ptr(asid = ASIdentifiers_new())) + goto err; + + for (i = 0; i < V3EXT_TEST_LARGE_N; i++) { + if (!TEST_ptr(val = ASN1_INTEGER_new()) + || !TEST_true(ASN1_INTEGER_set_int64(val, (int64_t)(2 * i + 1)))) + goto err; + if (!TEST_true(X509v3_asid_add_id_or_range(asid, V3_ASID_ASNUM, + val, NULL))) + goto err; + val = NULL; + } + + if (!TEST_true(X509v3_asid_canonize(asid))) + goto err; + + if (!TEST_int_eq(sk_ASIdOrRange_num(asid->asnum->u.asIdsOrRanges), + V3EXT_TEST_LARGE_N)) + goto err; + + /* + * Every entry must still be a single id with its original value; + * adjacent ids should NOT have been merged. + */ + for (i = 0; i < V3EXT_TEST_LARGE_N; i++) { + ASIdOrRange *aor = sk_ASIdOrRange_value(asid->asnum->u.asIdsOrRanges, + i); + int64_t got = 0; + + if (!TEST_ptr(aor) + || !TEST_int_eq(aor->type, ASIdOrRange_id) + || !TEST_true(ASN1_INTEGER_get_int64(&got, aor->u.id)) + || !TEST_int64_t_eq(got, (int64_t)(2 * i + 1))) + goto err; + } + + if (!TEST_int_eq(X509v3_asid_is_canonical(asid), 1)) + goto err; + + testresult = 1; +err: + ASN1_INTEGER_free(val); + ASIdentifiers_free(asid); + return testresult; +} + +/* + * Build an IPAddrBlocks with a single IPv4 family carrying + * V3EXT_TEST_LARGE_N adjacent /32 host prefixes starting at 1.0.0.1 + * (deliberately offset by one from the prefix-aligned 1.0.0.0 so the + * merged span [1.0.0.1, 1.0.32.0] cannot be expressed as a single + * prefix and stays an IPAddressOrRange_addressRange). After canonize + * the family must contain exactly one IPAddressOrRange of type + * addressRange covering the whole block, and is_canonical must + * accept it. Stresses the linear merge path in v3_addr.c. + */ +static int test_addr_large_canonize_merge(void) +{ + IPAddrBlocks *addr = NULL; + int i; + int testresult = 0; + + if (!TEST_ptr(addr = sk_IPAddressFamily_new_null())) + goto end; + + for (i = 0; i < V3EXT_TEST_LARGE_N; i++) { + unsigned char ip[4]; + unsigned int v = 0x01000001u + (unsigned int)i; /* 1.0.0.1 + i */ + + ip[0] = (unsigned char)((v >> 24) & 0xFF); + ip[1] = (unsigned char)((v >> 16) & 0xFF); + ip[2] = (unsigned char)((v >> 8) & 0xFF); + ip[3] = (unsigned char)(v & 0xFF); + if (!TEST_true(X509v3_addr_add_prefix(addr, IANA_AFI_IPV4, NULL, + ip, 32))) + goto end; + } + + if (!TEST_true(X509v3_addr_canonize(addr))) + goto end; + + if (!TEST_int_eq(sk_IPAddressFamily_num(addr), 1)) + goto end; + { + IPAddressFamily *f = sk_IPAddressFamily_value(addr, 0); + IPAddressOrRange *aor; + unsigned char got_min[4], got_max[4]; + unsigned int expected_max = 0x01000001u + V3EXT_TEST_LARGE_N - 1; + unsigned char want_min[4] = { 0x01, 0x00, 0x00, 0x01 }; + unsigned char want_max[4]; + + want_max[0] = (unsigned char)((expected_max >> 24) & 0xFF); + want_max[1] = (unsigned char)((expected_max >> 16) & 0xFF); + want_max[2] = (unsigned char)((expected_max >> 8) & 0xFF); + want_max[3] = (unsigned char)(expected_max & 0xFF); + + if (!TEST_ptr(f) + || !TEST_int_eq(f->ipAddressChoice->type, + IPAddressChoice_addressesOrRanges) + || !TEST_int_eq(sk_IPAddressOrRange_num( + f->ipAddressChoice->u.addressesOrRanges), + 1)) + goto end; + + aor = sk_IPAddressOrRange_value(f->ipAddressChoice->u.addressesOrRanges, + 0); + if (!TEST_ptr(aor) + || !TEST_int_eq(aor->type, IPAddressOrRange_addressRange)) + goto end; + if (!TEST_int_eq(X509v3_addr_get_range(aor, IANA_AFI_IPV4, + got_min, got_max, sizeof(got_min)), + 4) + || !TEST_mem_eq(got_min, 4, want_min, 4) + || !TEST_mem_eq(got_max, 4, want_max, 4)) + goto end; + } + + if (!TEST_int_eq(X509v3_addr_is_canonical(addr), 1)) + goto end; + + testresult = 1; +end: + sk_IPAddressFamily_pop_free(addr, IPAddressFamily_free); + return testresult; +} + +/* + * Interleaved merge / no-merge pattern, exercising the slide-forward + * arm of the linear-sweep compaction in ASIdentifierChoice_canonize. + * + * We build pairs of adjacent integers separated by gaps: (1, 2), (5, 6), + * (9, 10), ... Each pair merges to a single range, so the canonical + * output has exactly V3EXT_TEST_LARGE_N / 2 entries. Critically, after + * the second element of every pair merges into the first the merge + * loop's `write` index falls behind `read`; the *next* (non-mergeable) + * pair-start must then be slid forward into slot `write` and the source + * slot at `read` must be NULL'd. This is the path with no coverage in + * the all-merge or all-no-merge tests. + */ +static int test_asid_interleaved_canonize(void) +{ + ASIdentifiers *asid = NULL; + ASN1_INTEGER *val = NULL; + int i; + int expected = V3EXT_TEST_LARGE_N / 2; + int testresult = 0; + + if (!TEST_ptr(asid = ASIdentifiers_new())) + goto err; + + for (i = 0; i < V3EXT_TEST_LARGE_N; i++) { + /* Pair starts at 4*p, then 4*p+1; the next pair starts at 4*(p+1). */ + int pair = i / 2; + int within = i % 2; + int64_t v = 4 * (int64_t)pair + within + 1; + + if (!TEST_ptr(val = ASN1_INTEGER_new()) + || !TEST_true(ASN1_INTEGER_set_int64(val, v))) + goto err; + if (!TEST_true(X509v3_asid_add_id_or_range(asid, V3_ASID_ASNUM, + val, NULL))) + goto err; + val = NULL; + } + + if (!TEST_true(X509v3_asid_canonize(asid))) + goto err; + + if (!TEST_int_eq(sk_ASIdOrRange_num(asid->asnum->u.asIdsOrRanges), + expected)) + goto err; + + /* Every entry must now be a 2-wide range (the merge result of a pair). */ + for (i = 0; i < expected; i++) { + ASIdOrRange *aor = sk_ASIdOrRange_value(asid->asnum->u.asIdsOrRanges, i); + + if (!TEST_ptr(aor) || !TEST_int_eq(aor->type, ASIdOrRange_range)) + goto err; + } + + if (!TEST_int_eq(X509v3_asid_is_canonical(asid), 1)) + goto err; + + testresult = 1; +err: + ASN1_INTEGER_free(val); + ASIdentifiers_free(asid); + return testresult; +} + +/* + * IP-address counterpart to test_asid_interleaved_canonize: pairs of + * adjacent /32 prefixes separated by a gap of 2, so each pair merges + * but the next pair-start must be slid forward. + */ +static int test_addr_interleaved_canonize(void) +{ + IPAddrBlocks *addr = NULL; + int i; + int expected = V3EXT_TEST_LARGE_N / 2; + int testresult = 0; + + if (!TEST_ptr(addr = sk_IPAddressFamily_new_null())) + goto end; + + for (i = 0; i < V3EXT_TEST_LARGE_N; i++) { + unsigned char ip[4]; + unsigned int pair = (unsigned int)(i / 2); + unsigned int within = (unsigned int)(i % 2); + unsigned int v = 0x01000000u + 4u * pair + within; + + ip[0] = (unsigned char)((v >> 24) & 0xFF); + ip[1] = (unsigned char)((v >> 16) & 0xFF); + ip[2] = (unsigned char)((v >> 8) & 0xFF); + ip[3] = (unsigned char)(v & 0xFF); + if (!TEST_true(X509v3_addr_add_prefix(addr, IANA_AFI_IPV4, NULL, + ip, 32))) + goto end; + } + + if (!TEST_true(X509v3_addr_canonize(addr))) + goto end; + + if (!TEST_int_eq(sk_IPAddressFamily_num(addr), 1)) + goto end; + { + IPAddressFamily *f = sk_IPAddressFamily_value(addr, 0); + + if (!TEST_ptr(f) + || !TEST_int_eq(f->ipAddressChoice->type, + IPAddressChoice_addressesOrRanges) + || !TEST_int_eq(sk_IPAddressOrRange_num( + f->ipAddressChoice->u.addressesOrRanges), + expected)) + goto end; + } + + if (!TEST_int_eq(X509v3_addr_is_canonical(addr), 1)) + goto end; + + testresult = 1; +end: + sk_IPAddressFamily_pop_free(addr, IPAddressFamily_free); + return testresult; +} + +/* + * Trigger an overlap-detection error partway through the linear + * merge. The first V3EXT_TEST_LARGE_N / 2 entries are adjacent and + * mergeable; entry K is a duplicate of entry K-1 (overlap). The + * canonize call must return 0, and the caller's normal teardown of + * the choice must safely free the stack -- some slots hold merged + * results, some hold NULL (from earlier merges), and some hold + * originals that the loop never reached. ASan / UBSan-instrumented + * builds will catch any double-free or use-after-free in the + * teardown that the mixed-state-on-error invariant claims to avoid. + */ +static int test_asid_canonize_error_midsweep(void) +{ + ASIdentifiers *asid = NULL; + ASN1_INTEGER *val = NULL; + int i; + int n = V3EXT_TEST_LARGE_N; + int k = n / 2; + int testresult = 0; + + if (!TEST_ptr(asid = ASIdentifiers_new())) + goto err; + + for (i = 0; i < n; i++) { + /* + * Entries 1..k are 1,2,...,k (all adjacent). + * Entry k+1 duplicates entry k (overlap, triggers the error). + * Remaining entries are far away so they sort after the overlap. + */ + int64_t v; + + if (i < k) + v = (int64_t)i + 1; + else if (i == k) + v = (int64_t)k; /* duplicate, overlap */ + else + v = (int64_t)i + 1000000; /* far suffix, untouched */ + + if (!TEST_ptr(val = ASN1_INTEGER_new()) + || !TEST_true(ASN1_INTEGER_set_int64(val, v))) + goto err; + if (!TEST_true(X509v3_asid_add_id_or_range(asid, V3_ASID_ASNUM, + val, NULL))) + goto err; + val = NULL; + } + + /* canonize must reject overlap. */ + if (!TEST_int_eq(X509v3_asid_canonize(asid), 0)) + goto err; + + /* + * Successful return below relies on ASIdentifiers_free walking + * the partially-compacted stack without UAF or double-free. + * Under ASan / UBSan that walk is the actual test. + */ + testresult = 1; +err: + ASN1_INTEGER_free(val); + ASIdentifiers_free(asid); + return testresult; +} + +/* + * Trigger an overlap-detection error partway through the linear merge + * in IPAddressOrRanges_canonize. Construct a list whose first half is + * adjacent and mergeable, with a duplicate at position k that hits the + * overlap check after a series of merges has driven write < read. + * The canonize call must return 0, and the family's normal teardown + * (sk_IPAddressFamily_pop_free) must safely walk the partially + * compacted stack -- ASan / UBSan catches any double-free or UAF the + * mixed-state-on-error invariant would otherwise miss. Because the + * v3_addr.c canonize uses direct `return 0` rather than a `done:` + * cleanup label, the teardown invariant for this file is different + * from the asid path and warrants its own coverage. + */ +static int test_addr_canonize_error_midsweep(void) +{ + IPAddrBlocks *addr = NULL; + int i; + int n = V3EXT_TEST_LARGE_N; + int k = n / 2; + int testresult = 0; + + if (!TEST_ptr(addr = sk_IPAddressFamily_new_null())) + goto end; + + for (i = 0; i < n; i++) { + unsigned char ip[4]; + unsigned int v; + + if (i < k) + v = 0x01000000u + (unsigned int)i; /* adjacent /32 prefixes */ + else if (i == k) + v = 0x01000000u + (unsigned int)(k - 1); /* duplicate, overlap */ + else + v = 0x02000000u + (unsigned int)i; /* far suffix, untouched */ + + ip[0] = (unsigned char)((v >> 24) & 0xFF); + ip[1] = (unsigned char)((v >> 16) & 0xFF); + ip[2] = (unsigned char)((v >> 8) & 0xFF); + ip[3] = (unsigned char)(v & 0xFF); + if (!TEST_true(X509v3_addr_add_prefix(addr, IANA_AFI_IPV4, NULL, + ip, 32))) + goto end; + } + + /* canonize must reject overlap. */ + if (!TEST_int_eq(X509v3_addr_canonize(addr), 0)) + goto end; + + /* + * Successful return below relies on sk_IPAddressFamily_pop_free + * walking the partially-compacted aors stack without UAF or + * double-free. Under ASan / UBSan that walk is the actual test. + */ + testresult = 1; +end: + sk_IPAddressFamily_pop_free(addr, IPAddressFamily_free); + return testresult; +} + +/* + * Exercise the merge arm where `cur` is itself a range (rather than a + * single integer), hitting the `case ASIdOrRange_range` detach branch + * in ASIdentifierChoice_canonize. Build adjacent 2-wide ranges + * [1,2], [3,4], [5,6], ... which all fold into a single big range + * [1, 2 * V3EXT_TEST_LARGE_N]. + */ +static int test_asid_range_merge_canonize(void) +{ + ASIdentifiers *asid = NULL; + ASN1_INTEGER *minv = NULL, *maxv = NULL; + int i; + int testresult = 0; + + if (!TEST_ptr(asid = ASIdentifiers_new())) + goto err; + + for (i = 0; i < V3EXT_TEST_LARGE_N; i++) { + if (!TEST_ptr(minv = ASN1_INTEGER_new()) + || !TEST_true(ASN1_INTEGER_set_int64(minv, + (int64_t)(2 * i + 1))) + || !TEST_ptr(maxv = ASN1_INTEGER_new()) + || !TEST_true(ASN1_INTEGER_set_int64(maxv, + (int64_t)(2 * i + 2)))) + goto err; + if (!TEST_true(X509v3_asid_add_id_or_range(asid, V3_ASID_ASNUM, + minv, maxv))) + goto err; + minv = maxv = NULL; + } + + if (!TEST_true(X509v3_asid_canonize(asid))) + goto err; + + if (!TEST_int_eq(sk_ASIdOrRange_num(asid->asnum->u.asIdsOrRanges), 1)) + goto err; + { + ASIdOrRange *aor = sk_ASIdOrRange_value(asid->asnum->u.asIdsOrRanges, + 0); + int64_t got_min = 0, got_max = 0; + + if (!TEST_ptr(aor) || !TEST_int_eq(aor->type, ASIdOrRange_range)) + goto err; + /* + * The merged range must cover [1, 2 * V3EXT_TEST_LARGE_N]; + * incorrect max-propagation would still leave a single range + * but with a truncated upper bound. + */ + if (!TEST_true(ASN1_INTEGER_get_int64(&got_min, aor->u.range->min)) + || !TEST_int64_t_eq(got_min, 1) + || !TEST_true(ASN1_INTEGER_get_int64(&got_max, aor->u.range->max)) + || !TEST_int64_t_eq(got_max, (int64_t)(2 * V3EXT_TEST_LARGE_N))) + goto err; + } + + if (!TEST_int_eq(X509v3_asid_is_canonical(asid), 1)) + goto err; + + testresult = 1; +err: + ASN1_INTEGER_free(minv); + ASN1_INTEGER_free(maxv); + ASIdentifiers_free(asid); + return testresult; +} + +/* + * Trigger the inverted-range guard partway through the linear merge + * in ASIdentifierChoice_canonize. The first half of the list is + * well-formed adjacent integers; entry k is an explicitly inverted + * range (min = 1000, max = 100). X509v3_asid_add_id_or_range does + * not validate min <= max for ranges, so the bad entry is admitted + * into the list, and canonize must detect it on the sweep. The + * teardown under ASan / UBSan verifies that the early-exit path + * leaves the asIdsOrRanges stack in a freeable state. + * + * The addr-side counterpart of this branch (v3_addr.c:849) is not + * reachable through the public API: make_addressRange refuses to + * construct an inverted IPAddressOrRange in the first place. The + * guard remains as defence against a DER-decoded extension that + * carries inverted min/max bit strings; exercising it from C would + * require hand-building an IPAddressOrRange, which would bind the + * test to internal ASN.1 layout. + */ +static int test_asid_canonize_inverted_midsweep(void) +{ + ASIdentifiers *asid = NULL; + ASN1_INTEGER *val = NULL, *minv = NULL, *maxv = NULL; + int i; + int n = V3EXT_TEST_LARGE_N; + int k = n / 2; + int testresult = 0; + + if (!TEST_ptr(asid = ASIdentifiers_new())) + goto err; + + for (i = 0; i < n; i++) { + if (i == k) { + /* Inverted range: min=1000, max=100. */ + if (!TEST_ptr(minv = ASN1_INTEGER_new()) + || !TEST_true(ASN1_INTEGER_set_int64(minv, 1000)) + || !TEST_ptr(maxv = ASN1_INTEGER_new()) + || !TEST_true(ASN1_INTEGER_set_int64(maxv, 100))) + goto err; + if (!TEST_true(X509v3_asid_add_id_or_range(asid, V3_ASID_ASNUM, + minv, maxv))) + goto err; + minv = maxv = NULL; + } else { + int64_t v = (i < k) ? (int64_t)i + 1 + : (int64_t)i + 1000000; /* far suffix */ + + if (!TEST_ptr(val = ASN1_INTEGER_new()) + || !TEST_true(ASN1_INTEGER_set_int64(val, v))) + goto err; + if (!TEST_true(X509v3_asid_add_id_or_range(asid, V3_ASID_ASNUM, + val, NULL))) + goto err; + val = NULL; + } + } + + /* canonize must reject the inverted entry. */ + if (!TEST_int_eq(X509v3_asid_canonize(asid), 0)) + goto err; + + testresult = 1; +err: + ASN1_INTEGER_free(val); + ASN1_INTEGER_free(minv); + ASN1_INTEGER_free(maxv); + ASIdentifiers_free(asid); + return testresult; +} + static int test_addr_subset(void) { int i; @@ -480,6 +1069,15 @@ int setup_tests(void) ADD_TEST(test_ext_syntax); ADD_TEST(test_addr_fam_len); ADD_TEST(test_addr_subset); + ADD_TEST(test_asid_large_canonize_merge); + ADD_TEST(test_asid_large_canonize_no_merge); + ADD_TEST(test_addr_large_canonize_merge); + ADD_TEST(test_asid_interleaved_canonize); + ADD_TEST(test_addr_interleaved_canonize); + ADD_TEST(test_asid_canonize_error_midsweep); + ADD_TEST(test_addr_canonize_error_midsweep); + ADD_TEST(test_asid_range_merge_canonize); + ADD_TEST(test_asid_canonize_inverted_midsweep); #endif /* OPENSSL_NO_RFC3779 */ return 1; } -- 2.47.3