Re: [PATCH v2 2/5] overflow: Expand check_add_overflow() for pointer addition
From: Przemek Kitszel
Date: Thu Feb 01 2024 - 04:19:39 EST
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@xxxxxxxxx>
Cc: "Gustavo A. R. Silva" <gustavoars@xxxxxxxxxx>
Cc: Andrew Morton <akpm@xxxxxxxxxxxxxxxxxxxx>
Cc: Nathan Chancellor <nathan@xxxxxxxxxx>
Cc: Nick Desaulniers <ndesaulniers@xxxxxxxxxx>
Cc: Bill Wendling <morbo@xxxxxxxxxx>
Cc: Justin Stitt <justinstitt@xxxxxxxxxx>
Cc: llvm@xxxxxxxxxxxxxxx
Cc: linux-hardening@xxxxxxxxxxxxxxx
Signed-off-by: Kees Cook <keescook@xxxxxxxxxxxx>
---
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),