The branch master has been updated via 87fd67d997b236d1202546345d18384a968c9206 (commit) via d362db7cd1cc46462e0dd3bbccd5c279f2b2ccc8 (commit) via 8347bfa04fc62dcf684b8a43905709fa18f6a3b1 (commit) via bc4efcb0d0740467f1b8b536677a2886c2445c80 (commit) via cccfc668286cc1010911c28ea1e76be7e1eac3e7 (commit) via b037e3637a492fefe22b5fb12d7206afe6754ccd (commit) from 00cf3a2d30fc7642bf9f816a7c545115985a8c0c (commit)
- Log ----------------------------------------------------------------- commit 87fd67d997b236d1202546345d18384a968c9206 Author: Pauli <pa...@openssl.org> Date: Thu Nov 11 10:45:42 2021 +1000 x509: use safe maths calls for overflow detection Reviewed-by: Tomas Mraz <to...@openssl.org> (Merged from https://github.com/openssl/openssl/pull/16930) commit d362db7cd1cc46462e0dd3bbccd5c279f2b2ccc8 Author: Pauli <pa...@openssl.org> Date: Thu Nov 11 06:38:27 2021 +1000 run-checker: add CI to test safe_math without compiler support. Reviewed-by: Tomas Mraz <to...@openssl.org> (Merged from https://github.com/openssl/openssl/pull/16930) commit 8347bfa04fc62dcf684b8a43905709fa18f6a3b1 Author: Pauli <pa...@openssl.org> Date: Wed Nov 10 15:40:00 2021 +1000 stack: increase the reallocation ratio This change increases the reallocation ratio from 1.5 to 1.6. Reviewed-by: Tomas Mraz <to...@openssl.org> (Merged from https://github.com/openssl/openssl/pull/16930) commit bc4efcb0d0740467f1b8b536677a2886c2445c80 Author: Pauli <pa...@openssl.org> Date: Thu Oct 28 09:21:40 2021 +1000 test: add unit tests for integer overflow helpers Reviewed-by: Tomas Mraz <to...@openssl.org> (Merged from https://github.com/openssl/openssl/pull/16930) commit cccfc668286cc1010911c28ea1e76be7e1eac3e7 Author: Pauli <pa...@openssl.org> Date: Thu Oct 28 09:21:19 2021 +1000 doc: document the internal integer overflow helpers Reviewed-by: Tomas Mraz <to...@openssl.org> (Merged from https://github.com/openssl/openssl/pull/16930) commit b037e3637a492fefe22b5fb12d7206afe6754ccd Author: Pauli <pa...@openssl.org> Date: Thu Oct 28 09:20:03 2021 +1000 header: add integer overflow helper functions Define a number of helper functions that ease the difficulty of detecting integer overflows. Reviewed-by: Tomas Mraz <to...@openssl.org> (Merged from https://github.com/openssl/openssl/pull/16930) ----------------------------------------------------------------------- Summary of changes: .github/workflows/run-checker-daily.yml | 1 + crypto/stack/stack.c | 30 ++- crypto/x509/v3_ncons.c | 11 +- doc/internal/man3/OSSL_SAFE_MATH_SIGNED.pod | 104 +++++++ include/internal/safe_math.h | 405 ++++++++++++++++++++++++++++ test/build.info | 6 +- test/safe_math_test.c | 340 +++++++++++++++++++++++ 7 files changed, 880 insertions(+), 17 deletions(-) create mode 100644 doc/internal/man3/OSSL_SAFE_MATH_SIGNED.pod create mode 100644 include/internal/safe_math.h create mode 100644 test/safe_math_test.c diff --git a/.github/workflows/run-checker-daily.yml b/.github/workflows/run-checker-daily.yml index 0937d2f57d..d16eb41dab 100644 --- a/.github/workflows/run-checker-daily.yml +++ b/.github/workflows/run-checker-daily.yml @@ -127,6 +127,7 @@ jobs: no-zlib, enable-zlib-dynamic, no-zlib-dynamic, + -DOPENSSL_NO_BUILTIN_OVERFLOW_CHECKING ] runs-on: ubuntu-latest steps: diff --git a/crypto/stack/stack.c b/crypto/stack/stack.c index 3d8e4746cf..c06af85e33 100644 --- a/crypto/stack/stack.c +++ b/crypto/stack/stack.c @@ -10,10 +10,13 @@ #include <stdio.h> #include "internal/cryptlib.h" #include "internal/numbers.h" +#include "internal/safe_math.h" #include <openssl/stack.h> #include <errno.h> #include <openssl/e_os2.h> /* For ossl_inline */ +OSSL_SAFE_MATH_SIGNED(int, int) + /* * The initial number of nodes in the array. */ @@ -138,32 +141,35 @@ OPENSSL_STACK *OPENSSL_sk_new(OPENSSL_sk_compfunc c) /* * Calculate the array growth based on the target size. * - * The growth fraction is a rational number and is defined by a numerator + * The growth factor is a rational number and is defined by a numerator * and a denominator. According to Andrew Koenig in his paper "Why Are * Vectors Efficient?" from JOOP 11(5) 1998, this factor should be less * than the golden ratio (1.618...). * - * We use 3/2 = 1.5 for simplicity of calculation and overflow checking. - * Another option 8/5 = 1.6 allows for slightly faster growth, although safe - * computation is more difficult. + * Considering only the Fibonacci ratios less than the golden ratio, the + * number of steps from the minimum allocation to integer overflow is: + * factor decimal growths + * 3/2 1.5 51 + * 8/5 1.6 45 + * 21/13 1.615... 44 * - * The limit to avoid overflow is spot on. The modulo three correction term - * ensures that the limit is the largest number than can be expanded by the - * growth factor without exceeding the hard limit. + * All larger factors have the same number of growths. * - * Do not call it with |current| lower than 2, or it will infinitely loop. + * 3/2 and 8/5 have nice power of two shifts, so seem like a good choice. */ static ossl_inline int compute_growth(int target, int current) { - const int limit = (max_nodes / 3) * 2 + (max_nodes % 3 ? 1 : 0); + int err = 0; while (current < target) { - /* Check to see if we're at the hard limit */ if (current >= max_nodes) return 0; - /* Expand the size by a factor of 3/2 if it is within range */ - current = current < limit ? current + current / 2 : max_nodes; + current = safe_muldiv_int(current, 8, 5, &err); + if (err) + return 0; + if (current > max_nodes) + current = max_nodes; } return current; } diff --git a/crypto/x509/v3_ncons.c b/crypto/x509/v3_ncons.c index 70a7e8304e..c9e66a0f3b 100644 --- a/crypto/x509/v3_ncons.c +++ b/crypto/x509/v3_ncons.c @@ -9,6 +9,7 @@ #include "internal/cryptlib.h" #include "internal/numbers.h" +#include "internal/safe_math.h" #include <stdio.h> #include "crypto/asn1.h" #include <openssl/asn1t.h> @@ -20,6 +21,8 @@ #include "crypto/punycode.h" #include "ext_dat.h" +OSSL_SAFE_MATH_SIGNED(int, int) + static void *v2i_NAME_CONSTRAINTS(const X509V3_EXT_METHOD *method, X509V3_CTX *ctx, STACK_OF(CONF_VALUE) *nval); @@ -222,16 +225,16 @@ static int print_nc_ipadd(BIO *bp, ASN1_OCTET_STRING *ip) static int add_lengths(int *out, int a, int b) { + int err = 0; + /* sk_FOO_num(NULL) returns -1 but is effectively 0 when iterating. */ if (a < 0) a = 0; if (b < 0) b = 0; - if (a > INT_MAX - b) - return 0; - *out = a + b; - return 1; + *out = safe_add_int(a, b, &err); + return !err; } /*- diff --git a/doc/internal/man3/OSSL_SAFE_MATH_SIGNED.pod b/doc/internal/man3/OSSL_SAFE_MATH_SIGNED.pod new file mode 100644 index 0000000000..43f9ab34cc --- /dev/null +++ b/doc/internal/man3/OSSL_SAFE_MATH_SIGNED.pod @@ -0,0 +1,104 @@ +=pod + +=head1 NAME + +OSSL_SAFE_MATH_SIGNED, OSSL_SAFE_MATH_UNSIGNED, +safe_add_TYPE, safe_sub_TYPE, safe_mul_TYPE, safe_div_TYPE, safe_mod_TYPE, +safe_neg_TYPE +- create helper functions to safely perform non-overflowing integer operations + +=head1 SYNOPSIS + +=for openssl generic + + #include "internal/safe_math.h" + + OSSL_SAFE_MATH_SIGNED(NAME, TYPE) + OSSL_SAFE_MATH_UNSIGNED(NAME, TYPE) + + TYPE safe_add_TYPE(TYPE a, TYPE b, int *err); + TYPE safe_sub_TYPE(TYPE a, TYPE b, int *err); + TYPE safe_mul_TYPE(TYPE a, TYPE b, int *err); + TYPE safe_div_TYPE(TYPE a, TYPE b, int *err); + TYPE safe_mod_TYPE(TYPE a, TYPE b, int *err); + TYPE safe_muldiv_TYPE(TYPE a, TYPE b, TYPE c, int *err); + TYPE safe_neg_TYPE(TYPE a, int *err); + TYPE safe_abs_TYPE(TYPE a, int *err); + +=head1 DESCRIPTION + +Define helper functions to assist with handling integer overflow detection. +All of these functions perform an arithmetic operation on its arguments and +return the result of the operation. If the operation cannot be +correctly represented, the error I<err> flag is set. No behaviour that is +undefined as per the C standard will take place. + +OSSL_SAFE_MATH_SIGNED() creates helper functions for the B<I<TYPE>> with the +suffix B<I<NAME>>. + +OSSL_SAFE_MATH_UNSIGNED() creates helper functions for the B<I<TYPE>> with the +suffix B<I<NAME>>. + +safe_add_TYPE() adds the two arguments I<a> and I<b> together. + +safe_sub_TYPE() subtracts I<b> from I<a>. + +safe_mul_TYPE() multiplies the two arguments I<a> and I<b> together. + +safe_div_TYPE() divides I<a> by I<b>. + +safe_mod_TYPE() calculates the remainder when I<a> is divided by I<b>. + +safe_muldiv_TYPE() multiplies I<a> and I<b> together and divides the +result by I<c>. + +safe_neg_TYPE() calculates the negation of I<a>. + +safe_abs_TYPE() calculates the absolute value of I<a>. + +=head1 NOTES + +The safe_muldiv_TYPE() function is not perfect. There exist inputs where +a valid result could be computed with infinite length integers but this +function returns an error condition. Such instances should, however, +be rare in practice. The converse is not true. An invalid result will +always be flagged as an error. + +=head1 RETURN VALUES + +All these functions return the result of the operation, if the operation +is well defined. They return an arbitrary value if not. + +=head1 EXAMPLES + +This example is of a function that computes the size of a record that +has a four byte element count which is followed by that many elements. +It returns zero on overflow. + + OSSL_SAFE_MATH_UNSIGNED(sizet, size_t, SIZE_MAX) + + size_t compute_record_size(uint32_t n) + { + int err = 0; + size_t result, product; + + product = safe_mul_sizet(n, sizeof(struct widget), &err); + result = safe_add_sizet(product, sizeof(n), &err); + + return err ? 0 : result; + } + +=head1 HISTORY + +The functions described here were all added in OpenSSL 3.1. + +=head1 COPYRIGHT + +Copyright 2021 The OpenSSL Project Authors. All Rights Reserved. + +Licensed under the Apache License 2.0 (the "License"). You may not use +this file except in compliance with the License. You can obtain a copy +in the file LICENSE in the source distribution or at +L<https://www.openssl.org/source/license.html>. + +=cut diff --git a/include/internal/safe_math.h b/include/internal/safe_math.h new file mode 100644 index 0000000000..85c6147e55 --- /dev/null +++ b/include/internal/safe_math.h @@ -0,0 +1,405 @@ +/* + * Copyright 2021 The OpenSSL Project Authors. All Rights Reserved. + * + * Licensed under the Apache License 2.0 (the "License"). You may not use + * this file except in compliance with the License. You can obtain a copy + * in the file LICENSE in the source distribution or at + * https://www.openssl.org/source/license.html + */ + +#ifndef OSSL_INTERNAL_SAFE_MATH_H +# define OSSL_INTERNAL_SAFE_MATH_H +# pragma once + +# include <openssl/e_os2.h> /* For 'ossl_inline' */ + +# ifndef OPENSSL_NO_BUILTIN_OVERFLOW_CHECKING +# ifdef __has_builtin +# define has(func) __has_builtin(func) +# elif __GNUC__ > 5 +# define has(func) 1 +# endif +# endif /* OPENSSL_NO_BUILTIN_OVERFLOW_CHECKING */ + +# ifndef has +# define has(func) 0 +# endif + +/* + * Safe addition helpers + */ +# if has(__builtin_add_overflow) +# define OSSL_SAFE_MATH_ADDS(type_name, type, min, max) \ + static ossl_inline ossl_unused type safe_add_ ## type_name(type a, \ + type b, \ + int *err) \ + { \ + type r; \ + \ + if (!__builtin_add_overflow(a, b, &r)) \ + return r; \ + *err |= 1; \ + return a < 0 ? min : max; \ + } + +# define OSSL_SAFE_MATH_ADDU(type_name, type, max) \ + static ossl_inline ossl_unused type safe_add_ ## type_name(type a, \ + type b, \ + int *err) \ + { \ + type r; \ + \ + if (!__builtin_add_overflow(a, b, &r)) \ + return r; \ + *err |= 1; \ + return a + b; \ + } + +# else /* has(__builtin_add_overflow) */ +# define OSSL_SAFE_MATH_ADDS(type_name, type, min, max) \ + static ossl_inline ossl_unused type safe_add_ ## type_name(type a, \ + type b, \ + int *err) \ + { \ + if ((a < 0) ^ (b < 0) \ + || (a > 0 && b <= max - a) \ + || (a < 0 && b >= min - a) \ + || a == 0) \ + return a + b; \ + *err |= 1; \ + return a < 0 ? min : max; \ + } + +# define OSSL_SAFE_MATH_ADDU(type_name, type, max) \ + static ossl_inline ossl_unused type safe_add_ ## type_name(type a, \ + type b, \ + int *err) \ + { \ + if (b > max - a) \ + *err |= 1; \ + return a + b; \ + } +# endif /* has(__builtin_add_overflow) */ + +/* + * Safe subtraction helpers + */ +# if has(__builtin_sub_overflow) +# define OSSL_SAFE_MATH_SUBS(type_name, type, min, max) \ + static ossl_inline ossl_unused type safe_sub_ ## type_name(type a, \ + type b, \ + int *err) \ + { \ + type r; \ + \ + if (!__builtin_sub_overflow(a, b, &r)) \ + return r; \ + *err |= 1; \ + return a < 0 ? min : max; \ + } + +# else /* has(__builtin_sub_overflow) */ +# define OSSL_SAFE_MATH_SUBS(type_name, type, min, max) \ + static ossl_inline ossl_unused type safe_sub_ ## type_name(type a, \ + type b, \ + int *err) \ + { \ + if (!((a < 0) ^ (b < 0)) \ + || (b > 0 && a >= min + b) \ + || (b < 0 && a <= max + b) \ + || b == 0) \ + return a - b; \ + *err |= 1; \ + return a < 0 ? min : max; \ + } + +# endif /* has(__builtin_sub_overflow) */ + +# define OSSL_SAFE_MATH_SUBU(type_name, type) \ + static ossl_inline ossl_unused type safe_sub_ ## type_name(type a, \ + type b, \ + int *err) \ + { \ + if (b > a) \ + *err |= 1; \ + return a - b; \ + } + +/* + * Safe multiplication helpers + */ +# if has(__builtin_mul_overflow) +# define OSSL_SAFE_MATH_MULS(type_name, type, min, max) \ + static ossl_inline ossl_unused type safe_mul_ ## type_name(type a, \ + type b, \ + int *err) \ + { \ + type r; \ + \ + if (!__builtin_mul_overflow(a, b, &r)) \ + return r; \ + *err |= 1; \ + return (a < 0) ^ (b < 0) ? min : max; \ + } + +# define OSSL_SAFE_MATH_MULU(type_name, type, max) \ + static ossl_inline ossl_unused type safe_mul_ ## type_name(type a, \ + type b, \ + int *err) \ + { \ + type r; \ + \ + if (!__builtin_mul_overflow(a, b, &r)) \ + return r; \ + *err |= 1; \ + return a * b; \ + } + +# else /* has(__builtin_mul_overflow) */ +# define OSSL_SAFE_MATH_MULS(type_name, type, min, max) \ + static ossl_inline ossl_unused type safe_mul_ ## type_name(type a, \ + type b, \ + int *err) \ + { \ + if (a == 0 || b == 0) \ + return 0; \ + if (a == 1) \ + return b; \ + if (b == 1) \ + return a; \ + if (a != min && b != min) { \ + const type x = a < 0 ? -a : a; \ + const type y = b < 0 ? -b : b; \ + \ + if (x <= max / y) \ + return a * b; \ + } \ + *err |= 1; \ + return (a < 0) ^ (b < 0) ? min : max; \ + } + +# define OSSL_SAFE_MATH_MULU(type_name, type, max) \ + static ossl_inline ossl_unused type safe_mul_ ## type_name(type a, \ + type b, \ + int *err) \ + { \ + if (a > max / b) \ + *err |= 1; \ + return a * b; \ + } +# endif /* has(__builtin_mul_overflow) */ + +/* + * Safe division helpers + */ +# define OSSL_SAFE_MATH_DIVS(type_name, type, min, max) \ + static ossl_inline ossl_unused type safe_div_ ## type_name(type a, \ + type b, \ + int *err) \ + { \ + if (b == 0) { \ + *err |= 1; \ + return a < 0 ? min : max; \ + } \ + if (b == -1 && a == min) { \ + *err |= 1; \ + return max; \ + } \ + return a / b; \ + } + +# define OSSL_SAFE_MATH_DIVU(type_name, type, max) \ + static ossl_inline ossl_unused type safe_div_ ## type_name(type a, \ + type b, \ + int *err) \ + { \ + if (b != 0) \ + return a / b; \ + *err |= 1; \ + return max; \ + } + +/* + * Safe modulus helpers + */ +# define OSSL_SAFE_MATH_MODS(type_name, type, min, max) \ + static ossl_inline ossl_unused type safe_mod_ ## type_name(type a, \ + type b, \ + int *err) \ + { \ + if (b == 0) { \ + *err |= 1; \ + return 0; \ + } \ + if (b == -1 && a == min) { \ + *err |= 1; \ + return max; \ + } \ + return a % b; \ + } + +# define OSSL_SAFE_MATH_MODU(type_name, type) \ + static ossl_inline ossl_unused type safe_mod_ ## type_name(type a, \ + type b, \ + int *err) \ + { \ + if (b != 0) \ + return a % b; \ + *err |= 1; \ + return 0; \ + } + +/* + * Safe negation helpers + */ +# define OSSL_SAFE_MATH_NEGS(type_name, type, min) \ + static ossl_inline ossl_unused type safe_neg_ ## type_name(type a, \ + int *err) \ + { \ + if (a != min) \ + return -a; \ + *err |= 1; \ + return min; \ + } + +# define OSSL_SAFE_MATH_NEGU(type_name, type) \ + static ossl_inline ossl_unused type safe_neg_ ## type_name(type a, \ + int *err) \ + { \ + if (a == 0) \ + return a; \ + *err |= 1; \ + return 1 + ~a; \ + } + +/* + * Safe absolute value helpers + */ +# define OSSL_SAFE_MATH_ABSS(type_name, type, min) \ + static ossl_inline ossl_unused type safe_abs_ ## type_name(type a, \ + int *err) \ + { \ + if (a != min) \ + return a < 0 ? -a : a; \ + *err |= 1; \ + return min; \ + } + +# define OSSL_SAFE_MATH_ABSU(type_name, type) \ + static ossl_inline ossl_unused type safe_abs_ ## type_name(type a, \ + int *err) \ + { \ + return a; \ + } + +/* + * Safe fused multiply divide helpers + * + * These are a bit obscure: + * . They begin by checking the denominator for zero and getting rid of this + * corner case. + * + * . Second is an attempt to do the multiplication directly, if it doesn't + * overflow, the quotient is returned (for signed values there is a + * potential problem here which isn't present for unsigned). + * + * . Finally, the multiplication/division is transformed so that the larger + * of the numerators is divided first. This requires a remainder + * correction: + * + * a b / c = (a / c) b + (a mod c) b / c, where a > b + * + * The individual operations need to be overflow checked (again signed + * being more problematic). + * + * The algorithm used is not perfect but it should be "good enough". + */ +# define OSSL_SAFE_MATH_MULDIVS(type_name, type, max) \ + static ossl_inline ossl_unused type safe_muldiv_ ## type_name(type a, \ + type b, \ + type c, \ + int *err) \ + { \ + int e2 = 0; \ + type q, r, x, y; \ + \ + if (c == 0) { \ + *err |= 1; \ + return a == 0 || b == 0 ? 0 : max; \ + } \ + x = safe_mul_ ## type_name(a, b, &e2); \ + if (!e2) \ + return safe_div_ ## type_name(x, c, err); \ + if (b > a) { \ + x = b; \ + b = a; \ + a = x; \ + } \ + q = safe_div_ ## type_name(a, c, err); \ + r = safe_mod_ ## type_name(a, c, err); \ + x = safe_mul_ ## type_name(r, b, err); \ + y = safe_mul_ ## type_name(q, b, err); \ + q = safe_div_ ## type_name(x, c, err); \ + return safe_add_ ## type_name(y, q, err); \ + } + +# define OSSL_SAFE_MATH_MULDIVU(type_name, type, max) \ + static ossl_inline ossl_unused type safe_muldiv_ ## type_name(type a, \ + type b, \ + type c, \ + int *err) \ + { \ + int e2 = 0; \ + type x, y; \ + \ + if (c == 0) { \ + *err |= 1; \ + return a == 0 || b == 0 ? 0 : max; \ + } \ + x = safe_mul_ ## type_name(a, b, &e2); \ + if (!e2) \ + return x / c; \ + if (b > a) { \ + x = b; \ + b = a; \ + a = x; \ + } \ + x = safe_mul_ ## type_name(a % c, b, err); \ + y = safe_mul_ ## type_name(a / c, b, err); \ + return safe_add_ ## type_name(y, x / c, err); \ + } + +/* Calculate ranges of types */ +# define OSSL_SAFE_MATH_MINS(type) ((type)1 << (sizeof(type) * 8 - 1)) +# define OSSL_SAFE_MATH_MAXS(type) (~OSSL_SAFE_MATH_MINS(type)) +# define OSSL_SAFE_MATH_MAXU(type) (~(type)0) + +/* + * Wrapper macros to create all the functions of a given type + */ +# define OSSL_SAFE_MATH_SIGNED(type_name, type) \ + OSSL_SAFE_MATH_ADDS(type_name, type, OSSL_SAFE_MATH_MINS(type), \ + OSSL_SAFE_MATH_MAXS(type)) \ + OSSL_SAFE_MATH_SUBS(type_name, type, OSSL_SAFE_MATH_MINS(type), \ + OSSL_SAFE_MATH_MAXS(type)) \ + OSSL_SAFE_MATH_MULS(type_name, type, OSSL_SAFE_MATH_MINS(type), \ + OSSL_SAFE_MATH_MAXS(type)) \ + OSSL_SAFE_MATH_DIVS(type_name, type, OSSL_SAFE_MATH_MINS(type), \ + OSSL_SAFE_MATH_MAXS(type)) \ + OSSL_SAFE_MATH_MODS(type_name, type, OSSL_SAFE_MATH_MINS(type), \ + OSSL_SAFE_MATH_MAXS(type)) \ + OSSL_SAFE_MATH_MULDIVS(type_name, type, OSSL_SAFE_MATH_MAXS(type)) \ + OSSL_SAFE_MATH_NEGS(type_name, type, OSSL_SAFE_MATH_MINS(type)) \ + OSSL_SAFE_MATH_ABSS(type_name, type, OSSL_SAFE_MATH_MINS(type)) + +# define OSSL_SAFE_MATH_UNSIGNED(type_name, type) \ + OSSL_SAFE_MATH_ADDU(type_name, type, OSSL_SAFE_MATH_MAXU(type)) \ + OSSL_SAFE_MATH_SUBU(type_name, type) \ + OSSL_SAFE_MATH_MULU(type_name, type, OSSL_SAFE_MATH_MAXU(type)) \ + OSSL_SAFE_MATH_DIVU(type_name, type, OSSL_SAFE_MATH_MAXU(type)) \ + OSSL_SAFE_MATH_MODU(type_name, type) \ + OSSL_SAFE_MATH_MULDIVU(type_name, type, OSSL_SAFE_MATH_MAXU(type)) \ + OSSL_SAFE_MATH_NEGU(type_name, type) \ + OSSL_SAFE_MATH_ABSU(type_name, type) + +#endif /* OSSL_INTERNAL_SAFE_MATH_H */ diff --git a/test/build.info b/test/build.info index 0f379e11e2..bc8d400232 100644 --- a/test/build.info +++ b/test/build.info @@ -45,7 +45,7 @@ IF[{- !$disabled{tests} -}] evp_fetch_prov_test v3nametest v3ext \ crltest danetest bad_dtls_test lhash_test sparse_array_test \ conf_include_test params_api_test params_conversion_test \ - constant_time_test verify_extra_test clienthellotest \ + constant_time_test safe_math_test verify_extra_test clienthellotest \ packettest asynctest secmemtest srptest memleaktest stack_test \ dtlsv1listentest ct_test threadstest afalgtest d2i_test \ ssl_test_ctx_test ssl_test x509aux cipherlist_test asynciotest \ @@ -245,6 +245,10 @@ IF[{- !$disabled{tests} -}] INCLUDE[constant_time_test]=../include ../apps/include DEPEND[constant_time_test]=../libcrypto libtestutil.a + SOURCE[safe_math_test]=safe_math_test.c + INCLUDE[safe_math_test]=../include ../apps/include + DEPEND[safe_math_test]=../libcrypto libtestutil.a + SOURCE[verify_extra_test]=verify_extra_test.c INCLUDE[verify_extra_test]=../include ../apps/include DEPEND[verify_extra_test]=../libcrypto libtestutil.a diff --git a/test/safe_math_test.c b/test/safe_math_test.c new file mode 100644 index 0000000000..da50ec816b --- /dev/null +++ b/test/safe_math_test.c @@ -0,0 +1,340 @@ +/* + * Copyright 2021 The OpenSSL Project Authors. All Rights Reserved. + * + * Licensed under the Apache License 2.0 (the "License"). You may not use + * this file except in compliance with the License. You can obtain a copy + * in the file LICENSE in the source distribution or at + * https://www.openssl.org/source/license.html + */ + +#include <stdio.h> +#include <stdlib.h> + +/* + * Uncomment this if the fallback non-builtin overflow checking is to + * be tested. + */ +/*#define OPENSSL_NO_BUILTIN_OVERFLOW_CHECKING*/ + +#include "internal/nelem.h" +#include "internal/safe_math.h" +#include "testutil.h" + +/* Create the safe math instances we're interested in */ +OSSL_SAFE_MATH_SIGNED(int, int) +OSSL_SAFE_MATH_UNSIGNED(uint, unsigned int) +OSSL_SAFE_MATH_UNSIGNED(size_t, size_t) + +static const struct { + int a, b; + int sum_err, sub_err, mul_err, div_err, mod_err, neg_a_err, neg_b_err; + int abs_a_err, abs_b_err; +} test_ints[] = { + { 1, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, + { -1, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, + { 1, -3, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, + { -1, -3, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, + { INT_MAX, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0 }, + { INT_MAX, 2, 1, 0, 1, 0, 0, 0, 0, 0, 0 }, + { INT_MIN, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0 }, + { 1, INT_MIN, 0, 1, 0, 0, 0, 0, 1, 0, 1 }, + { INT_MIN, 2, 0, 1, 1, 0, 0, 1, 0, 1, 0 }, + { 2, INT_MIN, 0, 1, 1, 0, 0, 0, 1, 0, 1 }, + { INT_MIN, -1, 1, 0, 1, 1, 1, 1, 0, 1, 0 }, + { INT_MAX, INT_MIN, 0, 1, 1, 0, 0, 0, 1, 0, 1 }, + { INT_MIN, INT_MAX, 0, 1, 1, 0, 0, 1, 0, 1, 0 }, + { 3, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0 }, +}; + +static int test_int_ops(int n) +{ + int err, r; + const int a = test_ints[n].a, b = test_ints[n].b; + + err = 0; + r = safe_add_int(a, b, &err); + if (!TEST_int_eq(err, test_ints[n].sum_err) + || (!err && !TEST_int_eq(r, a + b))) + goto err; + + err = 0; + r = safe_sub_int(a, b, &err); + if (!TEST_int_eq(err, test_ints[n].sub_err) + || (!err && !TEST_int_eq(r, a - b))) + goto err; + + err = 0; + r = safe_mul_int(a, b, &err); + if (!TEST_int_eq(err, test_ints[n].mul_err) + || (!err && !TEST_int_eq(r, a * b))) + goto err; + + err = 0; + r = safe_div_int(a, b, &err); + if (!TEST_int_eq(err, test_ints[n].div_err) + || (!err && !TEST_int_eq(r, a / b))) + goto err; + + err = 0; + r = safe_mod_int(a, b, &err); + if (!TEST_int_eq(err, test_ints[n].mod_err) + || (!err && !TEST_int_eq(r, a % b))) + goto err; + + err = 0; + r = safe_neg_int(a, &err); + if (!TEST_int_eq(err, test_ints[n].neg_a_err) + || (!err && !TEST_int_eq(r, -a))) + goto err; + + err = 0; + r = safe_neg_int(b, &err); + if (!TEST_int_eq(err, test_ints[n].neg_b_err) + || (!err && !TEST_int_eq(r, -b))) + goto err; + + err = 0; + r = safe_abs_int(a, &err); + if (!TEST_int_eq(err, test_ints[n].abs_a_err) + || (!err && !TEST_int_eq(r, a < 0 ? -a : a))) + goto err; + + err = 0; + r = safe_abs_int(b, &err); + if (!TEST_int_eq(err, test_ints[n].abs_b_err) + || (!err && !TEST_int_eq(r, b < 0 ? -b : b))) + goto err; + return 1; + err: + TEST_info("a = %d b = %d r = %d err = %d", a, b, r, err); + return 0; +} + +static const struct { + unsigned int a, b; + int sum_err, sub_err, mul_err, div_err, mod_err; +} test_uints[] = { + { 3, 1, 0, 0, 0, 0, 0 }, + { 1, 3, 0, 1, 0, 0, 0 }, + { UINT_MAX, 1, 1, 0, 0, 0, 0 }, + { UINT_MAX, 2, 1, 0, 1, 0, 0 }, + { 1, UINT_MAX, 1, 1, 0, 0, 0 }, + { 2, UINT_MAX, 1, 1, 1, 0, 0 }, + { UINT_MAX, 0, 0, 0, 0, 1, 1 }, +}; + +static int test_uint_ops(int n) +{ + int err; + unsigned int r; + const unsigned int a = test_uints[n].a, b = test_uints[n].b; + + err = 0; + r = safe_add_uint(a, b, &err); + if (!TEST_int_eq(err, test_uints[n].sum_err) + || (!err && !TEST_uint_eq(r, a + b))) + goto err; + + err = 0; + r = safe_sub_uint(a, b, &err); + if (!TEST_int_eq(err, test_uints[n].sub_err) + || (!err && !TEST_uint_eq(r, a - b))) + goto err; + + err = 0; + r = safe_mul_uint(a, b, &err); + if (!TEST_int_eq(err, test_uints[n].mul_err) + || (!err && !TEST_uint_eq(r, a * b))) + goto err; + + err = 0; + r = safe_div_uint(a, b, &err); + if (!TEST_int_eq(err, test_uints[n].div_err) + || (!err && !TEST_uint_eq(r, a / b))) + goto err; + + err = 0; + r = safe_mod_uint(a, b, &err); + if (!TEST_int_eq(err, test_uints[n].mod_err) + || (!err && !TEST_uint_eq(r, a % b))) + goto err; + + err = 0; + r = safe_neg_uint(a, &err); + if (!TEST_int_eq(err, a != 0) || (!err && !TEST_uint_eq(r, 0))) + goto err; + + err = 0; + r = safe_neg_uint(b, &err); + if (!TEST_int_eq(err, b != 0) || (!err && !TEST_uint_eq(r, 0))) + goto err; + + err = 0; + r = safe_abs_uint(a, &err); + if (!TEST_int_eq(err, 0) || !TEST_uint_eq(r, a)) + goto err; + + err = 0; + r = safe_abs_uint(b, &err); + if (!TEST_int_eq(err, 0) || !TEST_uint_eq(r, b)) + goto err; + return 1; + err: + TEST_info("a = %u b = %u r = %u err = %d", a, b, r, err); + return 0; +} + +static const struct { + size_t a, b; + int sum_err, sub_err, mul_err, div_err, mod_err; +} test_size_ts[] = { + { 3, 1, 0, 0, 0, 0, 0 }, + { 1, 3, 0, 1, 0, 0, 0 }, + { SIZE_MAX, 1, 1, 0, 0, 0, 0 }, + { SIZE_MAX, 2, 1, 0, 1, 0, 0 }, + { 1, SIZE_MAX, 1, 1, 0, 0, 0 }, + { 2, SIZE_MAX, 1, 1, 1, 0, 0 }, + { 11, 0, 0, 0, 0, 1, 1 }, +}; + +static int test_size_t_ops(int n) +{ + int err; + size_t r; + const size_t a = test_size_ts[n].a, b = test_size_ts[n].b; + + err = 0; + r = safe_add_size_t(a, b, &err); + if (!TEST_int_eq(err, test_size_ts[n].sum_err) + || (!err && !TEST_size_t_eq(r, a + b))) + goto err; + + err = 0; + r = safe_sub_size_t(a, b, &err); + if (!TEST_int_eq(err, test_size_ts[n].sub_err) + || (!err && !TEST_size_t_eq(r, a - b))) + goto err; + + err = 0; + r = safe_mul_size_t(a, b, &err); + if (!TEST_int_eq(err, test_size_ts[n].mul_err) + || (!err && !TEST_size_t_eq(r, a * b))) + goto err; + + err = 0; + r = safe_div_size_t(a, b, &err); + if (!TEST_int_eq(err, test_uints[n].div_err) + || (!err && !TEST_size_t_eq(r, a / b))) + goto err; + + err = 0; + r = safe_mod_size_t(a, b, &err); + if (!TEST_int_eq(err, test_size_ts[n].mod_err) + || (!err && !TEST_size_t_eq(r, a % b))) + goto err; + + err = 0; + r = safe_neg_size_t(a, &err); + if (!TEST_int_eq(err, a != 0) || (!err && !TEST_size_t_eq(r, 0))) + goto err; + + err = 0; + r = safe_neg_size_t(b, &err); + if (!TEST_int_eq(err, b != 0) || (!err && !TEST_size_t_eq(r, 0))) + goto err; + + err = 0; + r = safe_abs_size_t(a, &err); + if (!TEST_int_eq(err, 0) || !TEST_size_t_eq(r, a)) + goto err; + + err = 0; + r = safe_abs_size_t(b, &err); + if (!TEST_int_eq(err, 0) || !TEST_size_t_eq(r, b)) + goto err; + return 1; + err: + TEST_info("a = %zu b = %zu r = %zu err = %d", a, b, r, err); + return 0; +} + +static const struct { + int a, b, c; + int err; +} test_muldiv_ints[] = { + { 3, 1, 2, 0 }, + { 1, 3, 2, 0 }, + { -3, 1, 2, 0 }, + { 1, 3, -2, 0 }, + { INT_MAX, INT_MAX, INT_MAX, 0 }, + { INT_MIN, INT_MIN, INT_MAX, 1 }, + { INT_MIN, INT_MIN, INT_MIN, 0 }, + { INT_MAX, 2, 4, 0 }, + { 8, INT_MAX, 4, 1 }, + { INT_MAX, 8, 4, 1 }, + { INT_MIN, 2, 4, 1 }, + { 8, INT_MIN, 4, 1 }, + { INT_MIN, 8, 4, 1 }, + { 3, 4, 0, 1 }, +}; + +static int test_int_muldiv(int n) +{ + int err = 0; + int r, real = 0; + const int a = test_muldiv_ints[n].a; + const int b = test_muldiv_ints[n].b; + const int c = test_muldiv_ints[n].c; + + r = safe_muldiv_int(a, b, c, &err); + if (c != 0) + real = (int)((int64_t)a * (int64_t)b / (int64_t)c); + if (!TEST_int_eq(err, test_muldiv_ints[n].err) + || (!err && !TEST_int_eq(r, real))) { + TEST_info("%d * %d / %d r = %d err = %d", a, b, c, r, err); + return 0; + } + return 1; +} + +static const struct { + unsigned int a, b, c; + int err; +} test_muldiv_uints[] = { + { 3, 1, 2, 0 }, + { 1, 3, 2, 0 }, + { UINT_MAX, UINT_MAX, UINT_MAX, 0 }, + { UINT_MAX, 2, 4, 0 }, + { 8, UINT_MAX, 4, 1 }, + { UINT_MAX, 8, 4, 1 }, + { 3, 4, 0, 1 }, +}; + +static int test_uint_muldiv(int n) +{ + int err = 0; + unsigned int r, real = 0; + const unsigned int a = test_muldiv_uints[n].a; + const unsigned int b = test_muldiv_uints[n].b; + const unsigned int c = test_muldiv_uints[n].c; + + r = safe_muldiv_uint(a, b, c, &err); + if (c != 0) + real = (unsigned int)((uint64_t)a * (uint64_t)b / (uint64_t)c); + if (!TEST_int_eq(err, test_muldiv_uints[n].err) + || (!err && !TEST_uint_eq(r, real))) { + TEST_info("%u * %u / %u r = %u err = %d", a, b, c, r, err); + return 0; + } + return 1; +} + +int setup_tests(void) +{ + ADD_ALL_TESTS(test_int_ops, OSSL_NELEM(test_ints)); + ADD_ALL_TESTS(test_uint_ops, OSSL_NELEM(test_uints)); + ADD_ALL_TESTS(test_size_t_ops, OSSL_NELEM(test_size_ts)); + ADD_ALL_TESTS(test_int_muldiv, OSSL_NELEM(test_muldiv_ints)); + ADD_ALL_TESTS(test_uint_muldiv, OSSL_NELEM(test_muldiv_uints)); + return 1; +}