| Message ID | 20240130220614.1154497-2-keescook@chromium.org (mailing list archive) |
|---|---|
| State | Superseded |
| Headers | show |
| Series | overflow: Introduce wrapping helpers | expand |
On 30/01/2024 23.06, Kees Cook wrote: > The check_add_overflow() helper is mostly a wrapper around > __builtin_add_overflow(), but GCC and Clang refuse to operate on pointer > arguments that would normally be allowed if the addition were open-coded. > > For example, we have many places where pointer overflow is tested: > > struct foo *ptr; > ... > /* Check for overflow */ > if (ptr + count < ptr) ... > > And in order to avoid running into the overflow sanitizers in the > future, we need to rewrite these "intended" overflow checks: > > if (check_add_overflow(ptr, count, &result)) ... > > Frustratingly the argument type validation for __builtin_add_overflow() > is done before evaluating __builtin_choose_expr(), so for arguments to > be valid simultaneously for sizeof(*p) (when p may not be a pointer), > and __builtin_add_overflow(a, ...) (when a may be a pointer), we must > introduce wrappers that always produce a specific type (but they are > only used in the places where the bogus arguments will be ignored). > > To test whether a variable is a pointer or not, introduce the __is_ptr() > helper, which uses __builtin_classify_type() to find arrays and pointers > (via the new __is_ptr_or_array() helper), and then decays arrays into > pointers (via the new __decay() helper), to distinguish pointers from > arrays. > > Additionally update the unit tests to cover pointer addition. > > Cc: Rasmus Villemoes <rasmus.villemoes@prevas.dk> > Cc: "Gustavo A. R. Silva" <gustavoars@kernel.org> > Cc: Andrew Morton <akpm@linux-foundation.org> > Cc: Nathan Chancellor <nathan@kernel.org> > Cc: Nick Desaulniers <ndesaulniers@google.com> > Cc: Bill Wendling <morbo@google.com> > Cc: Justin Stitt <justinstitt@google.com> > Cc: llvm@lists.linux.dev > Cc: linux-hardening@vger.kernel.org > Signed-off-by: Kees Cook <keescook@chromium.org> > --- > include/linux/compiler_types.h | 10 +++++ > include/linux/overflow.h | 44 ++++++++++++++++++- > lib/overflow_kunit.c | 77 ++++++++++++++++++++++++++++++---- > 3 files changed, 120 insertions(+), 11 deletions(-) > > diff --git a/include/linux/compiler_types.h b/include/linux/compiler_types.h > index 6f1ca49306d2..d27b58fddfaa 100644 > --- a/include/linux/compiler_types.h > +++ b/include/linux/compiler_types.h > @@ -375,6 +375,16 @@ struct ftrace_likely_data { > /* Are two types/vars the same type (ignoring qualifiers)? */ > #define __same_type(a, b) __builtin_types_compatible_p(typeof(a), typeof(b)) > > +/* Is variable addressable? */ > +#define __is_ptr_or_array(p) (__builtin_classify_type(p) == 5) That magic constant is a bit ugly, but I don't think there's a better way. However, a comment saying "pointer_type_class in gcc/typeclass.h in gcc source code" or something like that might help. Do we know for sure that clang uses the same value? I can't find it documented anywhere. __check_ptr_add_overflow() - Calculate pointer addition with overflow checking > + * @a: pointer addend > + * @b: numeric addend > + * @d: pointer to store sum > + * > + * Returns 0 on success, 1 on wrap-around. > + * > + * Do not use this function directly, use check_add_overflow() instead. > + * > + * *@d holds the results of the attempted addition, which may wrap-around. > + */ > +#define __check_ptr_add_overflow(a, b, d) \ > + ({ \ > + typeof(a) __a = (a); \ > + typeof(b) __b = (b); \ > + size_t __bytes; \ > + bool __overflow; \ > + \ > + /* we want to perform the wrap-around, but retain the result */ \ > + __overflow = __builtin_mul_overflow(sizeof(*(__a)), __b, &__bytes); \ > + __builtin_add_overflow((unsigned long)(__a), __bytes, (unsigned long *)(d)) || \ > + __overflow; \ > + }) So I've tried to wrap my head around all these layers of macros, and it seems ok. However, here I'm a bit worried that there's no type checking of the destination. In particular, the user could perhaps end up doing check_add_overflow(p, x, p) which will go horribly wrong. Do we have any infrastructure for testing "this should fail to compile"? It would be good to have, not just for this, but in general for checking our sanity checks. Another thing is that this will always fail with negative offsets (if b has signed type and a negative value, the multiplication won't fit in an unsigned type). I think __bytes should be ptrdiff_t. Rasmus
On 1/30/24 23:06, Kees Cook wrote: > The check_add_overflow() helper is mostly a wrapper around > __builtin_add_overflow(), but GCC and Clang refuse to operate on pointer > arguments that would normally be allowed if the addition were open-coded. > > For example, we have many places where pointer overflow is tested: > > struct foo *ptr; > ... > /* Check for overflow */ > if (ptr + count < ptr) ... > > And in order to avoid running into the overflow sanitizers in the > future, we need to rewrite these "intended" overflow checks: > > if (check_add_overflow(ptr, count, &result)) ... > > Frustratingly the argument type validation for __builtin_add_overflow() > is done before evaluating __builtin_choose_expr(), so for arguments to > be valid simultaneously for sizeof(*p) (when p may not be a pointer), > and __builtin_add_overflow(a, ...) (when a may be a pointer), we must > introduce wrappers that always produce a specific type (but they are > only used in the places where the bogus arguments will be ignored). > > To test whether a variable is a pointer or not, introduce the __is_ptr() > helper, which uses __builtin_classify_type() to find arrays and pointers > (via the new __is_ptr_or_array() helper), and then decays arrays into > pointers (via the new __decay() helper), to distinguish pointers from > arrays. This is (not just commit msg but together with impl), at first glance, too complicated for regular developers to grasp (that is perhaps fine), but could we make it simpler by, say _Generic() or other trick? > > Additionally update the unit tests to cover pointer addition. > > Cc: Rasmus Villemoes <rasmus.villemoes@prevas.dk> > Cc: "Gustavo A. R. Silva" <gustavoars@kernel.org> > Cc: Andrew Morton <akpm@linux-foundation.org> > Cc: Nathan Chancellor <nathan@kernel.org> > Cc: Nick Desaulniers <ndesaulniers@google.com> > Cc: Bill Wendling <morbo@google.com> > Cc: Justin Stitt <justinstitt@google.com> > Cc: llvm@lists.linux.dev > Cc: linux-hardening@vger.kernel.org > Signed-off-by: Kees Cook <keescook@chromium.org> > --- > include/linux/compiler_types.h | 10 +++++ > include/linux/overflow.h | 44 ++++++++++++++++++- > lib/overflow_kunit.c | 77 ++++++++++++++++++++++++++++++---- > 3 files changed, 120 insertions(+), 11 deletions(-) > > diff --git a/include/linux/compiler_types.h b/include/linux/compiler_types.h > index 6f1ca49306d2..d27b58fddfaa 100644 > --- a/include/linux/compiler_types.h > +++ b/include/linux/compiler_types.h > @@ -375,6 +375,16 @@ struct ftrace_likely_data { > /* Are two types/vars the same type (ignoring qualifiers)? */ > #define __same_type(a, b) __builtin_types_compatible_p(typeof(a), typeof(b)) > > +/* Is variable addressable? */ > +#define __is_ptr_or_array(p) (__builtin_classify_type(p) == 5) > + > +/* Return an array decayed to a pointer. */ > +#define __decay(p) \ > + (&*__builtin_choose_expr(__is_ptr_or_array(p), p, NULL)) > + > +/* Report if variable is a pointer type. */ > +#define __is_ptr(p) __same_type(p, __decay(p)) > + > /* > * __unqual_scalar_typeof(x) - Declare an unqualified scalar type, leaving > * non-scalar types unchanged. > diff --git a/include/linux/overflow.h b/include/linux/overflow.h > index 4e741ebb8005..210e5602e89b 100644 > --- a/include/linux/overflow.h > +++ b/include/linux/overflow.h > @@ -51,6 +51,43 @@ static inline bool __must_check __must_check_overflow(bool overflow) > return unlikely(overflow); > } > > +/* Always produce an integral variable expression. */ > +#define __filter_integral(x) \ > + __builtin_choose_expr(!__is_ptr(x), (x), 0) > + > +/* Always produce a pointer value. */ > +#define __filter_ptr(x) \ > + __builtin_choose_expr(__is_ptr(x), (x), NULL) > + > +/* Always produce a pointer to an integral value. */ > +#define __filter_ptrint(x) \ > + __builtin_choose_expr(!__is_ptr(*(x)), x, &(int){ 0 }) > + > +/** > + * __check_ptr_add_overflow() - Calculate pointer addition with overflow checking > + * @a: pointer addend > + * @b: numeric addend > + * @d: pointer to store sum > + * > + * Returns 0 on success, 1 on wrap-around. > + * > + * Do not use this function directly, use check_add_overflow() instead. > + * > + * *@d holds the results of the attempted addition, which may wrap-around. > + */ > +#define __check_ptr_add_overflow(a, b, d) \ > + ({ \ > + typeof(a) __a = (a); \ > + typeof(b) __b = (b); \ > + size_t __bytes; \ > + bool __overflow; \ > + \ > + /* we want to perform the wrap-around, but retain the result */ \ > + __overflow = __builtin_mul_overflow(sizeof(*(__a)), __b, &__bytes); \ > + __builtin_add_overflow((unsigned long)(__a), __bytes, (unsigned long *)(d)) || \ > + __overflow; \ > + }) > + > /** > * check_add_overflow() - Calculate addition with overflow checking > * @a: first addend > @@ -61,8 +98,11 @@ static inline bool __must_check __must_check_overflow(bool overflow) > * > * *@d holds the results of the attempted addition, which may wrap-around. > */ > -#define check_add_overflow(a, b, d) \ > - __must_check_overflow(__builtin_add_overflow(a, b, d)) > +#define check_add_overflow(a, b, d) \ > + __must_check_overflow(__builtin_choose_expr(__is_ptr(a), \ > + __check_ptr_add_overflow(__filter_ptr(a), b, d), \ > + __builtin_add_overflow(__filter_integral(a), b, \ > + __filter_ptrint(d)))) > > /** > * check_sub_overflow() - Calculate subtraction with overflow checking > diff --git a/lib/overflow_kunit.c b/lib/overflow_kunit.c > index c527f6b75789..2d106e880956 100644 > --- a/lib/overflow_kunit.c > +++ b/lib/overflow_kunit.c > @@ -45,13 +45,18 @@ > # define SKIP_64_ON_32(t) do { } while (0) > #endif > > -#define DEFINE_TEST_ARRAY_TYPED(t1, t2, t) \ > - static const struct test_ ## t1 ## _ ## t2 ## __ ## t { \ > +#define DEFINE_TEST_ARRAY_NAMED_TYPED(n1, n2, n, t1, t2, t) \ > + static const struct test_ ## n1 ## _ ## n2 ## __ ## n { \ > t1 a; \ > t2 b; \ > - t sum, diff, prod; \ > + t sum; \ > + t diff; \ > + t prod; \ > bool s_of, d_of, p_of; \ > - } t1 ## _ ## t2 ## __ ## t ## _tests[] > + } n1 ## _ ## n2 ## __ ## n ## _tests[] > + > +#define DEFINE_TEST_ARRAY_TYPED(t1, t2, t) \ > + DEFINE_TEST_ARRAY_NAMED_TYPED(t1, t2, t, t1, t2, t) > > #define DEFINE_TEST_ARRAY(t) DEFINE_TEST_ARRAY_TYPED(t, t, t) > > @@ -251,8 +256,10 @@ DEFINE_TEST_ARRAY(s64) = { > }; > > #define check_one_op(t, fmt, op, sym, a, b, r, of) do { \ > - int _a_orig = a, _a_bump = a + 1; \ > - int _b_orig = b, _b_bump = b + 1; \ > + typeof(a + 0) _a_orig = a; \ > + typeof(a + 0) _a_bump = a + 1; \ > + typeof(b + 0) _b_orig = b; \ > + typeof(b + 0) _b_bump = b + 1; \ > bool _of; \ > t _r; \ > \ > @@ -260,13 +267,13 @@ DEFINE_TEST_ARRAY(s64) = { > KUNIT_EXPECT_EQ_MSG(test, _of, of, \ > "expected "fmt" "sym" "fmt" to%s overflow (type %s)\n", \ > a, b, of ? "" : " not", #t); \ > - KUNIT_EXPECT_EQ_MSG(test, _r, r, \ > + KUNIT_EXPECT_TRUE_MSG(test, _r == r, \ > "expected "fmt" "sym" "fmt" == "fmt", got "fmt" (type %s)\n", \ > a, b, r, _r, #t); \ > /* Check for internal macro side-effects. */ \ > _of = check_ ## op ## _overflow(_a_orig++, _b_orig++, &_r); \ > - KUNIT_EXPECT_EQ_MSG(test, _a_orig, _a_bump, "Unexpected " #op " macro side-effect!\n"); \ > - KUNIT_EXPECT_EQ_MSG(test, _b_orig, _b_bump, "Unexpected " #op " macro side-effect!\n"); \ > + KUNIT_EXPECT_TRUE_MSG(test, _a_orig == _a_bump, "Unexpected " #op " macro side-effect!\n"); \ > + KUNIT_EXPECT_TRUE_MSG(test, _b_orig == _b_bump, "Unexpected " #op " macro side-effect!\n"); \ > } while (0) > > #define DEFINE_TEST_FUNC_TYPED(n, t, fmt) \ > @@ -333,6 +340,55 @@ DEFINE_TEST_ARRAY_TYPED(int, int, u8) = { > }; > DEFINE_TEST_FUNC_TYPED(int_int__u8, u8, "%d"); > > +#define DEFINE_TEST_PTR_FUNC_TYPED(n, t, fmt) \ > +static void do_ptr_test_ ## n(struct kunit *test, const struct test_ ## n *p) \ > +{ \ > + /* we're only doing single-direction sums, no product or division */ \ > + check_one_op(t, fmt, add, "+", p->a, p->b, p->sum, p->s_of);\ > +} \ > + \ > +static void n ## _overflow_test(struct kunit *test) { \ > + unsigned i; \ > + \ > + for (i = 0; i < ARRAY_SIZE(n ## _tests); ++i) \ > + do_ptr_test_ ## n(test, &n ## _tests[i]); \ > + kunit_info(test, "%zu %s arithmetic tests finished\n", \ > + ARRAY_SIZE(n ## _tests), #n); \ > +} > + > +DEFINE_TEST_ARRAY_NAMED_TYPED(void, int, void, void *, int, void *) = { > + {NULL, 0, NULL, NULL, NULL, false, false, false}, > + {(void *)0x30, 0x10, (void *)0x40, NULL, NULL, false, false, false}, > + {(void *)ULONG_MAX, 0, (void *)ULONG_MAX, NULL, NULL, false, false, false}, > + {(void *)ULONG_MAX, 1, NULL, NULL, NULL, true, false, false}, > + {(void *)ULONG_MAX, INT_MAX, (void *)(INT_MAX - 1), NULL, NULL, true, false, false}, > +}; > +DEFINE_TEST_PTR_FUNC_TYPED(void_int__void, void *, "%lx"); > + > +struct _sized { > + int a; > + char b; > +}; > + > +DEFINE_TEST_ARRAY_NAMED_TYPED(sized, int, sized, struct _sized *, int, struct _sized *) = { > + {NULL, 0, NULL, NULL, NULL, false, false, false}, > + {NULL, 1, (struct _sized *)(sizeof(struct _sized)), NULL, NULL, false, false, false}, > + {NULL, 0x10, (struct _sized *)(sizeof(struct _sized) * 0x10), NULL, NULL, false, false, false}, > + {(void *)(ULONG_MAX - sizeof(struct _sized)), 1, (struct _sized *)ULONG_MAX, NULL, NULL, false, false, false}, > + {(void *)(ULONG_MAX - sizeof(struct _sized) + 1), 1, NULL, NULL, NULL, true, false, false}, > + {(void *)(ULONG_MAX - sizeof(struct _sized) + 1), 2, (struct _sized *)(sizeof(struct _sized)), NULL, NULL, true, false, false}, > + {(void *)(ULONG_MAX - sizeof(struct _sized) + 1), 3, (struct _sized *)(sizeof(struct _sized) * 2), NULL, NULL, true, false, false}, > +}; > +DEFINE_TEST_PTR_FUNC_TYPED(sized_int__sized, struct _sized *, "%lx"); > + > +DEFINE_TEST_ARRAY_NAMED_TYPED(sized, size_t, sized, struct _sized *, size_t, struct _sized *) = { > + {NULL, 0, NULL, NULL, NULL, false, false, false}, > + {NULL, 1, (struct _sized *)(sizeof(struct _sized)), NULL, NULL, false, false, false}, > + {NULL, 0x10, (struct _sized *)(sizeof(struct _sized) * 0x10), NULL, NULL, false, false, false}, > + {NULL, SIZE_MAX - 10, (struct _sized *)18446744073709551528UL, NULL, NULL, true, false, false}, > +}; > +DEFINE_TEST_PTR_FUNC_TYPED(sized_size_t__sized, struct _sized *, "%zu"); > + > /* Args are: value, shift, type, expected result, overflow expected */ > #define TEST_ONE_SHIFT(a, s, t, expect, of) do { \ > typeof(a) __a = (a); \ > @@ -1122,6 +1178,9 @@ static struct kunit_case overflow_test_cases[] = { > KUNIT_CASE(s32_s32__s32_overflow_test), > KUNIT_CASE(u64_u64__u64_overflow_test), > KUNIT_CASE(s64_s64__s64_overflow_test), > + KUNIT_CASE(void_int__void_overflow_test), > + KUNIT_CASE(sized_int__sized_overflow_test), > + KUNIT_CASE(sized_size_t__sized_overflow_test), > KUNIT_CASE(u32_u32__int_overflow_test), > KUNIT_CASE(u32_u32__u8_overflow_test), > KUNIT_CASE(u8_u8__int_overflow_test),
On Thu, Feb 01, 2024 at 10:19:15AM +0100, Przemek Kitszel wrote: > On 1/30/24 23:06, Kees Cook wrote: > > The check_add_overflow() helper is mostly a wrapper around > > __builtin_add_overflow(), but GCC and Clang refuse to operate on pointer > > arguments that would normally be allowed if the addition were open-coded. > > > > For example, we have many places where pointer overflow is tested: > > > > struct foo *ptr; > > ... > > /* Check for overflow */ > > if (ptr + count < ptr) ... > > > > And in order to avoid running into the overflow sanitizers in the > > future, we need to rewrite these "intended" overflow checks: > > > > if (check_add_overflow(ptr, count, &result)) ... > > > > Frustratingly the argument type validation for __builtin_add_overflow() > > is done before evaluating __builtin_choose_expr(), so for arguments to > > be valid simultaneously for sizeof(*p) (when p may not be a pointer), > > and __builtin_add_overflow(a, ...) (when a may be a pointer), we must > > introduce wrappers that always produce a specific type (but they are > > only used in the places where the bogus arguments will be ignored). > > > > To test whether a variable is a pointer or not, introduce the __is_ptr() > > helper, which uses __builtin_classify_type() to find arrays and pointers > > (via the new __is_ptr_or_array() helper), and then decays arrays into > > pointers (via the new __decay() helper), to distinguish pointers from > > arrays. > > This is (not just commit msg but together with impl), at first glance, too > complicated for regular developers to grasp (that is perhaps fine), > but could we make it simpler by, say _Generic() or other trick? I haven't been able to find a way to do this, unfortunately. :( I would *love* to find something simpler, but it eludes me.
On Wed, Jan 31, 2024 at 09:35:35AM +0100, Rasmus Villemoes wrote: > On 30/01/2024 23.06, Kees Cook wrote: > > [...] > > diff --git a/include/linux/compiler_types.h b/include/linux/compiler_types.h > > index 6f1ca49306d2..d27b58fddfaa 100644 > > --- a/include/linux/compiler_types.h > > +++ b/include/linux/compiler_types.h > > @@ -375,6 +375,16 @@ struct ftrace_likely_data { > > /* Are two types/vars the same type (ignoring qualifiers)? */ > > #define __same_type(a, b) __builtin_types_compatible_p(typeof(a), typeof(b)) > > > > +/* Is variable addressable? */ > > +#define __is_ptr_or_array(p) (__builtin_classify_type(p) == 5) > > That magic constant is a bit ugly, but I don't think there's a better > way. However, a comment saying "pointer_type_class in gcc/typeclass.h in > gcc source code" or something like that might help. Do we know for sure > that clang uses the same value? I can't find it documented anywhere. Very true. Offlist, Keith Packard suggested I switch to this, so we can avoid the constant: +#define __is_ptr_or_array(p) (__builtin_classify_type(p) == \ __builtin_classify_type(NULL)) > > __check_ptr_add_overflow() - Calculate pointer addition with overflow > checking > > + * @a: pointer addend > > + * @b: numeric addend > > + * @d: pointer to store sum > > + * > > + * Returns 0 on success, 1 on wrap-around. > > + * > > + * Do not use this function directly, use check_add_overflow() instead. > > + * > > + * *@d holds the results of the attempted addition, which may wrap-around. > > + */ > > +#define __check_ptr_add_overflow(a, b, d) \ > > + ({ \ > > + typeof(a) __a = (a); \ > > + typeof(b) __b = (b); \ > > + size_t __bytes; \ > > + bool __overflow; \ > > + \ > > + /* we want to perform the wrap-around, but retain the result */ \ > > + __overflow = __builtin_mul_overflow(sizeof(*(__a)), __b, &__bytes); \ > > + __builtin_add_overflow((unsigned long)(__a), __bytes, (unsigned long *)(d)) || \ > > + __overflow; \ > > + }) > > So I've tried to wrap my head around all these layers of macros, and it > seems ok. However, here I'm a bit worried that there's no type checking > of the destination. In particular, the user could perhaps end up doing > > check_add_overflow(p, x, p) I tried to make sure the top-level filtering would require a pointer to an integral type. I'm sure there is a way to foot-gun it, if one tries hard enough. :) > > which will go horribly wrong. Do we have any infrastructure for testing > "this should fail to compile"? It would be good to have, not just for > this, but in general for checking our sanity checks. > > Another thing is that this will always fail with negative offsets (if b > has signed type and a negative value, the multiplication won't fit in an > unsigned type). I think __bytes should be ptrdiff_t. Ew. A negative "add"... yes. I'll take a closer look. Thanks for the review! As it turns out, I may not need this patch at all yet, so I may hold off on it until I can prove that we really will need it. -Kees
diff --git a/include/linux/compiler_types.h b/include/linux/compiler_types.h index 6f1ca49306d2..d27b58fddfaa 100644 --- a/include/linux/compiler_types.h +++ b/include/linux/compiler_types.h @@ -375,6 +375,16 @@ struct ftrace_likely_data { /* Are two types/vars the same type (ignoring qualifiers)? */ #define __same_type(a, b) __builtin_types_compatible_p(typeof(a), typeof(b)) +/* Is variable addressable? */ +#define __is_ptr_or_array(p) (__builtin_classify_type(p) == 5) + +/* Return an array decayed to a pointer. */ +#define __decay(p) \ + (&*__builtin_choose_expr(__is_ptr_or_array(p), p, NULL)) + +/* Report if variable is a pointer type. */ +#define __is_ptr(p) __same_type(p, __decay(p)) + /* * __unqual_scalar_typeof(x) - Declare an unqualified scalar type, leaving * non-scalar types unchanged. diff --git a/include/linux/overflow.h b/include/linux/overflow.h index 4e741ebb8005..210e5602e89b 100644 --- a/include/linux/overflow.h +++ b/include/linux/overflow.h @@ -51,6 +51,43 @@ static inline bool __must_check __must_check_overflow(bool overflow) return unlikely(overflow); } +/* Always produce an integral variable expression. */ +#define __filter_integral(x) \ + __builtin_choose_expr(!__is_ptr(x), (x), 0) + +/* Always produce a pointer value. */ +#define __filter_ptr(x) \ + __builtin_choose_expr(__is_ptr(x), (x), NULL) + +/* Always produce a pointer to an integral value. */ +#define __filter_ptrint(x) \ + __builtin_choose_expr(!__is_ptr(*(x)), x, &(int){ 0 }) + +/** + * __check_ptr_add_overflow() - Calculate pointer addition with overflow checking + * @a: pointer addend + * @b: numeric addend + * @d: pointer to store sum + * + * Returns 0 on success, 1 on wrap-around. + * + * Do not use this function directly, use check_add_overflow() instead. + * + * *@d holds the results of the attempted addition, which may wrap-around. + */ +#define __check_ptr_add_overflow(a, b, d) \ + ({ \ + typeof(a) __a = (a); \ + typeof(b) __b = (b); \ + size_t __bytes; \ + bool __overflow; \ + \ + /* we want to perform the wrap-around, but retain the result */ \ + __overflow = __builtin_mul_overflow(sizeof(*(__a)), __b, &__bytes); \ + __builtin_add_overflow((unsigned long)(__a), __bytes, (unsigned long *)(d)) || \ + __overflow; \ + }) + /** * check_add_overflow() - Calculate addition with overflow checking * @a: first addend @@ -61,8 +98,11 @@ static inline bool __must_check __must_check_overflow(bool overflow) * * *@d holds the results of the attempted addition, which may wrap-around. */ -#define check_add_overflow(a, b, d) \ - __must_check_overflow(__builtin_add_overflow(a, b, d)) +#define check_add_overflow(a, b, d) \ + __must_check_overflow(__builtin_choose_expr(__is_ptr(a), \ + __check_ptr_add_overflow(__filter_ptr(a), b, d), \ + __builtin_add_overflow(__filter_integral(a), b, \ + __filter_ptrint(d)))) /** * check_sub_overflow() - Calculate subtraction with overflow checking diff --git a/lib/overflow_kunit.c b/lib/overflow_kunit.c index c527f6b75789..2d106e880956 100644 --- a/lib/overflow_kunit.c +++ b/lib/overflow_kunit.c @@ -45,13 +45,18 @@ # define SKIP_64_ON_32(t) do { } while (0) #endif -#define DEFINE_TEST_ARRAY_TYPED(t1, t2, t) \ - static const struct test_ ## t1 ## _ ## t2 ## __ ## t { \ +#define DEFINE_TEST_ARRAY_NAMED_TYPED(n1, n2, n, t1, t2, t) \ + static const struct test_ ## n1 ## _ ## n2 ## __ ## n { \ t1 a; \ t2 b; \ - t sum, diff, prod; \ + t sum; \ + t diff; \ + t prod; \ bool s_of, d_of, p_of; \ - } t1 ## _ ## t2 ## __ ## t ## _tests[] + } n1 ## _ ## n2 ## __ ## n ## _tests[] + +#define DEFINE_TEST_ARRAY_TYPED(t1, t2, t) \ + DEFINE_TEST_ARRAY_NAMED_TYPED(t1, t2, t, t1, t2, t) #define DEFINE_TEST_ARRAY(t) DEFINE_TEST_ARRAY_TYPED(t, t, t) @@ -251,8 +256,10 @@ DEFINE_TEST_ARRAY(s64) = { }; #define check_one_op(t, fmt, op, sym, a, b, r, of) do { \ - int _a_orig = a, _a_bump = a + 1; \ - int _b_orig = b, _b_bump = b + 1; \ + typeof(a + 0) _a_orig = a; \ + typeof(a + 0) _a_bump = a + 1; \ + typeof(b + 0) _b_orig = b; \ + typeof(b + 0) _b_bump = b + 1; \ bool _of; \ t _r; \ \ @@ -260,13 +267,13 @@ DEFINE_TEST_ARRAY(s64) = { KUNIT_EXPECT_EQ_MSG(test, _of, of, \ "expected "fmt" "sym" "fmt" to%s overflow (type %s)\n", \ a, b, of ? "" : " not", #t); \ - KUNIT_EXPECT_EQ_MSG(test, _r, r, \ + KUNIT_EXPECT_TRUE_MSG(test, _r == r, \ "expected "fmt" "sym" "fmt" == "fmt", got "fmt" (type %s)\n", \ a, b, r, _r, #t); \ /* Check for internal macro side-effects. */ \ _of = check_ ## op ## _overflow(_a_orig++, _b_orig++, &_r); \ - KUNIT_EXPECT_EQ_MSG(test, _a_orig, _a_bump, "Unexpected " #op " macro side-effect!\n"); \ - KUNIT_EXPECT_EQ_MSG(test, _b_orig, _b_bump, "Unexpected " #op " macro side-effect!\n"); \ + KUNIT_EXPECT_TRUE_MSG(test, _a_orig == _a_bump, "Unexpected " #op " macro side-effect!\n"); \ + KUNIT_EXPECT_TRUE_MSG(test, _b_orig == _b_bump, "Unexpected " #op " macro side-effect!\n"); \ } while (0) #define DEFINE_TEST_FUNC_TYPED(n, t, fmt) \ @@ -333,6 +340,55 @@ DEFINE_TEST_ARRAY_TYPED(int, int, u8) = { }; DEFINE_TEST_FUNC_TYPED(int_int__u8, u8, "%d"); +#define DEFINE_TEST_PTR_FUNC_TYPED(n, t, fmt) \ +static void do_ptr_test_ ## n(struct kunit *test, const struct test_ ## n *p) \ +{ \ + /* we're only doing single-direction sums, no product or division */ \ + check_one_op(t, fmt, add, "+", p->a, p->b, p->sum, p->s_of);\ +} \ + \ +static void n ## _overflow_test(struct kunit *test) { \ + unsigned i; \ + \ + for (i = 0; i < ARRAY_SIZE(n ## _tests); ++i) \ + do_ptr_test_ ## n(test, &n ## _tests[i]); \ + kunit_info(test, "%zu %s arithmetic tests finished\n", \ + ARRAY_SIZE(n ## _tests), #n); \ +} + +DEFINE_TEST_ARRAY_NAMED_TYPED(void, int, void, void *, int, void *) = { + {NULL, 0, NULL, NULL, NULL, false, false, false}, + {(void *)0x30, 0x10, (void *)0x40, NULL, NULL, false, false, false}, + {(void *)ULONG_MAX, 0, (void *)ULONG_MAX, NULL, NULL, false, false, false}, + {(void *)ULONG_MAX, 1, NULL, NULL, NULL, true, false, false}, + {(void *)ULONG_MAX, INT_MAX, (void *)(INT_MAX - 1), NULL, NULL, true, false, false}, +}; +DEFINE_TEST_PTR_FUNC_TYPED(void_int__void, void *, "%lx"); + +struct _sized { + int a; + char b; +}; + +DEFINE_TEST_ARRAY_NAMED_TYPED(sized, int, sized, struct _sized *, int, struct _sized *) = { + {NULL, 0, NULL, NULL, NULL, false, false, false}, + {NULL, 1, (struct _sized *)(sizeof(struct _sized)), NULL, NULL, false, false, false}, + {NULL, 0x10, (struct _sized *)(sizeof(struct _sized) * 0x10), NULL, NULL, false, false, false}, + {(void *)(ULONG_MAX - sizeof(struct _sized)), 1, (struct _sized *)ULONG_MAX, NULL, NULL, false, false, false}, + {(void *)(ULONG_MAX - sizeof(struct _sized) + 1), 1, NULL, NULL, NULL, true, false, false}, + {(void *)(ULONG_MAX - sizeof(struct _sized) + 1), 2, (struct _sized *)(sizeof(struct _sized)), NULL, NULL, true, false, false}, + {(void *)(ULONG_MAX - sizeof(struct _sized) + 1), 3, (struct _sized *)(sizeof(struct _sized) * 2), NULL, NULL, true, false, false}, +}; +DEFINE_TEST_PTR_FUNC_TYPED(sized_int__sized, struct _sized *, "%lx"); + +DEFINE_TEST_ARRAY_NAMED_TYPED(sized, size_t, sized, struct _sized *, size_t, struct _sized *) = { + {NULL, 0, NULL, NULL, NULL, false, false, false}, + {NULL, 1, (struct _sized *)(sizeof(struct _sized)), NULL, NULL, false, false, false}, + {NULL, 0x10, (struct _sized *)(sizeof(struct _sized) * 0x10), NULL, NULL, false, false, false}, + {NULL, SIZE_MAX - 10, (struct _sized *)18446744073709551528UL, NULL, NULL, true, false, false}, +}; +DEFINE_TEST_PTR_FUNC_TYPED(sized_size_t__sized, struct _sized *, "%zu"); + /* Args are: value, shift, type, expected result, overflow expected */ #define TEST_ONE_SHIFT(a, s, t, expect, of) do { \ typeof(a) __a = (a); \ @@ -1122,6 +1178,9 @@ static struct kunit_case overflow_test_cases[] = { KUNIT_CASE(s32_s32__s32_overflow_test), KUNIT_CASE(u64_u64__u64_overflow_test), KUNIT_CASE(s64_s64__s64_overflow_test), + KUNIT_CASE(void_int__void_overflow_test), + KUNIT_CASE(sized_int__sized_overflow_test), + KUNIT_CASE(sized_size_t__sized_overflow_test), KUNIT_CASE(u32_u32__int_overflow_test), KUNIT_CASE(u32_u32__u8_overflow_test), KUNIT_CASE(u8_u8__int_overflow_test),
The check_add_overflow() helper is mostly a wrapper around __builtin_add_overflow(), but GCC and Clang refuse to operate on pointer arguments that would normally be allowed if the addition were open-coded. For example, we have many places where pointer overflow is tested: struct foo *ptr; ... /* Check for overflow */ if (ptr + count < ptr) ... And in order to avoid running into the overflow sanitizers in the future, we need to rewrite these "intended" overflow checks: if (check_add_overflow(ptr, count, &result)) ... Frustratingly the argument type validation for __builtin_add_overflow() is done before evaluating __builtin_choose_expr(), so for arguments to be valid simultaneously for sizeof(*p) (when p may not be a pointer), and __builtin_add_overflow(a, ...) (when a may be a pointer), we must introduce wrappers that always produce a specific type (but they are only used in the places where the bogus arguments will be ignored). To test whether a variable is a pointer or not, introduce the __is_ptr() helper, which uses __builtin_classify_type() to find arrays and pointers (via the new __is_ptr_or_array() helper), and then decays arrays into pointers (via the new __decay() helper), to distinguish pointers from arrays. Additionally update the unit tests to cover pointer addition. Cc: Rasmus Villemoes <rasmus.villemoes@prevas.dk> Cc: "Gustavo A. R. Silva" <gustavoars@kernel.org> Cc: Andrew Morton <akpm@linux-foundation.org> Cc: Nathan Chancellor <nathan@kernel.org> Cc: Nick Desaulniers <ndesaulniers@google.com> Cc: Bill Wendling <morbo@google.com> Cc: Justin Stitt <justinstitt@google.com> Cc: llvm@lists.linux.dev Cc: linux-hardening@vger.kernel.org Signed-off-by: Kees Cook <keescook@chromium.org> --- include/linux/compiler_types.h | 10 +++++ include/linux/overflow.h | 44 ++++++++++++++++++- lib/overflow_kunit.c | 77 ++++++++++++++++++++++++++++++---- 3 files changed, 120 insertions(+), 11 deletions(-)