diff mbox series

[rdma-next,v4,2/3] test_overflow: Add shift overflow tests

Message ID 20180801212541.22889-3-keescook@chromium.org (mailing list archive)
State Accepted
Delegated to: Jason Gunthorpe
Headers show
Series overflow.h: Add left-shift helper | expand

Commit Message

Kees Cook Aug. 1, 2018, 9:25 p.m. UTC 
This adds overflow tests for the new check_shift_overflow() helper to
validate overflow, signedness glitches, storage glitches, etc.

Co-developed-by: Rasmus Villemoes <linux@rasmusvillemoes.dk>
Signed-off-by: Kees Cook <keescook@chromium.org>
---
 lib/test_overflow.c | 198 +++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 197 insertions(+), 1 deletion(-)

Comments

Rasmus Villemoes Aug. 6, 2018, 10:54 p.m. UTC | #1 
On 2018-08-01 23:25, Kees Cook wrote:
> This adds overflow tests for the new check_shift_overflow() helper to
> validate overflow, signedness glitches, storage glitches, etc.
> 

Just a few random comments, not really anything worth a v5 by itself.
IOW, I can live with this being sent upstream during next merge window.

> Co-developed-by: Rasmus Villemoes <linux@rasmusvillemoes.dk>
> Signed-off-by: Kees Cook <keescook@chromium.org>
> ---
> +static int __init test_overflow_shift(void)
> +{
> +	int err = 0;
> +
> +/* Args are: value, shift, type, expected result, overflow expected */
> +#define TEST_ONE_SHIFT(a, s, t, expect, of) ({				\
> +	int __failed = 0;						\
> +	typeof(a) __a = (a);						\
> +	typeof(s) __s = (s);						\
> +	t __e = (expect);						\
> +	t __d;								\
> +	bool __of = check_shl_overflow(__a, __s, &__d);			\
> +	if (__of != of) {						\
> +		pr_warn("expected (%s)(%s << %s) to%s overflow\n",	\
> +			#t, #a, #s, of ? "" : " not");			\
> +		__failed = 1;						\
> +	} else if (!__of && __d != __e) {				\
> +		pr_warn("expected (%s)(%s << %s) == %s\n",		\
> +			#t, #a, #s, #expect);				\
> +		if ((t)-1 < 0)						\
> +			pr_warn("got %lld\n", (s64)__d);		\
> +		else							\
> +			pr_warn("got %llu\n", (u64)__d);		\
> +		__failed = 1;						\
> +	}								\
> +	if (!__failed)							\
> +		pr_info("ok: (%s)(%s << %s) == %s\n", #t, #a, #s,	\
> +			of ? "overflow" : #expect);			\

Isn't that a bit much, one pr_info for every test case (especially with
the number of test cases you've done, and thanks for that btw.)? For the
others, there's just one "doing nnn tests". It's harder here because we
can only let the tests count themselves, but we could have
TEST_ONE_SHIFT do exactly that and then print a pr_info at the end (or
pr_warn if any failed).

[Or, if we're willing to do something a bit ugly, forward-declaring
file-scope statics is actually allowed, and can be combined with
__COUNTER__...

#define foo() printf("test number %d\n", __COUNTER__)

static int start;
static int end;

static int start = __COUNTER__;
void t(void)
{
	printf("Will do %d tests\n", end - start);
	foo();
	foo();
}
static int end = __COUNTER__ - 1;

the expansion of TEST_ONE_SHIFT wouldn't have to use __COUNTER__ in any
meaningful way. This of course goes out the window if
check_shl_overflow is robustified with UNIQUE_ID. There's even a way to
work around that, but I'd better stop here.]


> +	__failed;							\
> +})
> +
> +	err |= TEST_ONE_SHIFT(1, 0, int, 1 << 0, false);
> +	err |= TEST_ONE_SHIFT(1, 16, int, 1 << 16, false);
> +	err |= TEST_ONE_SHIFT(1, 30, int, 1 << 30, false);
> +	err |= TEST_ONE_SHIFT(1, 0, s32, 1 << 0, false);
> +	err |= TEST_ONE_SHIFT(1, 16, s32, 1 << 16, false);
> +	err |= TEST_ONE_SHIFT(1, 30, s32, 1 << 30, false);

I don't see much point in doing both int and s32 as they are AFAIK
unconditionally the same on all architectures. Similarly for unsigned
int/u32.

> +
> +	/* Overflow: shifted at or beyond entire type's bit width. */
> +	err |= TEST_ONE_SHIFT(0, 8, u8, 0, true);
> +	err |= TEST_ONE_SHIFT(0, 9, u8, 0, true);

Hmm, seeing these I'd actually rather we didn't base the upper bound for
the shift count on sizeof(*d) but rather used a fixed 64, since that's
what we use for the temporary variable, and capping the shift count is
mostly for avoiding UB in the implementation. For any non-zero input
value, a shift count greater than 8 would still report overflow because
of the truncation.

More generally, I think that if the actual C expression

  a << s

doesn't invoke UB (i.e., a is non-negative and s is sane according to
the type of a), no bits are lots during the shift, and the result fits
in *d, we should not report overflow. Hence we should not impose
arbitrary limits on s just because the destination happens to be u8.
That some shift count/destination type combos then happen to guarantee
overflow for all but an input of 0 is just the way the math works.

> +
> +	/*
> +	 * Corner case: for unsigned types, we fail when we've shifted
> +	 * through the entire width of bits. For signed types, we might
> +	 * want to match this behavior, but that would mean noticing if
> +	 * we shift through all but the signed bit, and this is not
> +	 * currently detected (but we'll notice an overflow into the
> +	 * signed bit). So, for now, we will test this condition but
> +	 * mark it as not expected to overflow.
> +	 */
> +	err |= TEST_ONE_SHIFT(0, 7, s8, 0, false);
> +	err |= TEST_ONE_SHIFT(0, 15, s16, 0, false);
> +	err |= TEST_ONE_SHIFT(0, 31, int, 0, false);
> +	err |= TEST_ONE_SHIFT(0, 31, s32, 0, false);
> +	err |= TEST_ONE_SHIFT(0, 63, s64, 0, false);

I can't really see how this is a "corner case". For an s8 destination
and a shift count of, say, 4, there happens to be 8 input values that
won't lead to "overflow". When the shift count is 7, there's 1 input
value that won't lead to "overflow". So?

Rasmus
--
To unsubscribe from this list: send the line "unsubscribe linux-rdma" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
diff mbox series

Patch

diff --git a/lib/test_overflow.c b/lib/test_overflow.c
index 2278fe05a1b0..fc680562d8b6 100644
--- a/lib/test_overflow.c
+++ b/lib/test_overflow.c
@@ -252,7 +252,8 @@  static int __init test_ ## t ## _overflow(void) {			\
 	int err = 0;							\
 	unsigned i;							\
 									\
-	pr_info("%-3s: %zu tests\n", #t, ARRAY_SIZE(t ## _tests));	\
+	pr_info("%-3s: %zu arithmetic tests\n", #t,			\
+		ARRAY_SIZE(t ## _tests));				\
 	for (i = 0; i < ARRAY_SIZE(t ## _tests); ++i)			\
 		err |= do_test_ ## t(&t ## _tests[i]);			\
 	return err;							\
@@ -287,6 +288,200 @@  static int __init test_overflow_calculation(void)
 	return err;
 }
 
+static int __init test_overflow_shift(void)
+{
+	int err = 0;
+
+/* Args are: value, shift, type, expected result, overflow expected */
+#define TEST_ONE_SHIFT(a, s, t, expect, of) ({				\
+	int __failed = 0;						\
+	typeof(a) __a = (a);						\
+	typeof(s) __s = (s);						\
+	t __e = (expect);						\
+	t __d;								\
+	bool __of = check_shl_overflow(__a, __s, &__d);			\
+	if (__of != of) {						\
+		pr_warn("expected (%s)(%s << %s) to%s overflow\n",	\
+			#t, #a, #s, of ? "" : " not");			\
+		__failed = 1;						\
+	} else if (!__of && __d != __e) {				\
+		pr_warn("expected (%s)(%s << %s) == %s\n",		\
+			#t, #a, #s, #expect);				\
+		if ((t)-1 < 0)						\
+			pr_warn("got %lld\n", (s64)__d);		\
+		else							\
+			pr_warn("got %llu\n", (u64)__d);		\
+		__failed = 1;						\
+	}								\
+	if (!__failed)							\
+		pr_info("ok: (%s)(%s << %s) == %s\n", #t, #a, #s,	\
+			of ? "overflow" : #expect);			\
+	__failed;							\
+})
+
+	/* Sane shifts. */
+	err |= TEST_ONE_SHIFT(1, 0, u8, 1 << 0, false);
+	err |= TEST_ONE_SHIFT(1, 4, u8, 1 << 4, false);
+	err |= TEST_ONE_SHIFT(1, 7, u8, 1 << 7, false);
+	err |= TEST_ONE_SHIFT(0xF, 4, u8, 0xF << 4, false);
+	err |= TEST_ONE_SHIFT(1, 0, u16, 1 << 0, false);
+	err |= TEST_ONE_SHIFT(1, 10, u16, 1 << 10, false);
+	err |= TEST_ONE_SHIFT(1, 15, u16, 1 << 15, false);
+	err |= TEST_ONE_SHIFT(0xFF, 8, u16, 0xFF << 8, false);
+	err |= TEST_ONE_SHIFT(1, 0, int, 1 << 0, false);
+	err |= TEST_ONE_SHIFT(1, 16, int, 1 << 16, false);
+	err |= TEST_ONE_SHIFT(1, 30, int, 1 << 30, false);
+	err |= TEST_ONE_SHIFT(1, 0, s32, 1 << 0, false);
+	err |= TEST_ONE_SHIFT(1, 16, s32, 1 << 16, false);
+	err |= TEST_ONE_SHIFT(1, 30, s32, 1 << 30, false);
+	err |= TEST_ONE_SHIFT(1, 0, unsigned int, 1U << 0, false);
+	err |= TEST_ONE_SHIFT(1, 20, unsigned int, 1U << 20, false);
+	err |= TEST_ONE_SHIFT(1, 31, unsigned int, 1U << 31, false);
+	err |= TEST_ONE_SHIFT(0xFFFFU, 16, unsigned int, 0xFFFFU << 16, false);
+	err |= TEST_ONE_SHIFT(1, 0, u32, 1U << 0, false);
+	err |= TEST_ONE_SHIFT(1, 20, u32, 1U << 20, false);
+	err |= TEST_ONE_SHIFT(1, 31, u32, 1U << 31, false);
+	err |= TEST_ONE_SHIFT(0xFFFFU, 16, u32, 0xFFFFU << 16, false);
+	err |= TEST_ONE_SHIFT(1, 0, u64, 1ULL << 0, false);
+	err |= TEST_ONE_SHIFT(1, 40, u64, 1ULL << 40, false);
+	err |= TEST_ONE_SHIFT(1, 63, u64, 1ULL << 63, false);
+	err |= TEST_ONE_SHIFT(0xFFFFFFFFULL, 32, u64,
+			      0xFFFFFFFFULL << 32, false);
+
+	/* Sane shift: start and end with 0, without a too-wide shift. */
+	err |= TEST_ONE_SHIFT(0, 7, u8, 0, false);
+	err |= TEST_ONE_SHIFT(0, 15, u16, 0, false);
+	err |= TEST_ONE_SHIFT(0, 31, unsigned int, 0, false);
+	err |= TEST_ONE_SHIFT(0, 31, u32, 0, false);
+	err |= TEST_ONE_SHIFT(0, 63, u64, 0, false);
+
+	/* Sane shift: start and end with 0, without reaching signed bit. */
+	err |= TEST_ONE_SHIFT(0, 6, s8, 0, false);
+	err |= TEST_ONE_SHIFT(0, 14, s16, 0, false);
+	err |= TEST_ONE_SHIFT(0, 30, int, 0, false);
+	err |= TEST_ONE_SHIFT(0, 30, s32, 0, false);
+	err |= TEST_ONE_SHIFT(0, 62, s64, 0, false);
+
+	/* Overflow: shifted the bit off the end. */
+	err |= TEST_ONE_SHIFT(1, 8, u8, 0, true);
+	err |= TEST_ONE_SHIFT(1, 16, u16, 0, true);
+	err |= TEST_ONE_SHIFT(1, 32, unsigned int, 0, true);
+	err |= TEST_ONE_SHIFT(1, 32, u32, 0, true);
+	err |= TEST_ONE_SHIFT(1, 64, u64, 0, true);
+
+	/* Overflow: shifted into the signed bit. */
+	err |= TEST_ONE_SHIFT(1, 7, s8, 0, true);
+	err |= TEST_ONE_SHIFT(1, 15, s16, 0, true);
+	err |= TEST_ONE_SHIFT(1, 31, int, 0, true);
+	err |= TEST_ONE_SHIFT(1, 31, s32, 0, true);
+	err |= TEST_ONE_SHIFT(1, 63, s64, 0, true);
+
+	/* Overflow: high bit falls off unsigned types. */
+	/* 10010110 */
+	err |= TEST_ONE_SHIFT(150, 1, u8, 0, true);
+	/* 1000100010010110 */
+	err |= TEST_ONE_SHIFT(34966, 1, u16, 0, true);
+	/* 10000100000010001000100010010110 */
+	err |= TEST_ONE_SHIFT(2215151766U, 1, u32, 0, true);
+	err |= TEST_ONE_SHIFT(2215151766U, 1, unsigned int, 0, true);
+	/* 1000001000010000010000000100000010000100000010001000100010010110 */
+	err |= TEST_ONE_SHIFT(9372061470395238550ULL, 1, u64, 0, true);
+
+	/* Overflow: bit shifted into signed bit on signed types. */
+	/* 01001011 */
+	err |= TEST_ONE_SHIFT(75, 1, s8, 0, true);
+	/* 0100010001001011 */
+	err |= TEST_ONE_SHIFT(17483, 1, s16, 0, true);
+	/* 01000010000001000100010001001011 */
+	err |= TEST_ONE_SHIFT(1107575883, 1, s32, 0, true);
+	err |= TEST_ONE_SHIFT(1107575883, 1, int, 0, true);
+	/* 0100000100001000001000000010000001000010000001000100010001001011 */
+	err |= TEST_ONE_SHIFT(4686030735197619275LL, 1, s64, 0, true);
+
+	/* Overflow: bit shifted past signed bit on signed types. */
+	/* 01001011 */
+	err |= TEST_ONE_SHIFT(75, 2, s8, 0, true);
+	/* 0100010001001011 */
+	err |= TEST_ONE_SHIFT(17483, 2, s16, 0, true);
+	/* 01000010000001000100010001001011 */
+	err |= TEST_ONE_SHIFT(1107575883, 2, s32, 0, true);
+	err |= TEST_ONE_SHIFT(1107575883, 2, int, 0, true);
+	/* 0100000100001000001000000010000001000010000001000100010001001011 */
+	err |= TEST_ONE_SHIFT(4686030735197619275LL, 2, s64, 0, true);
+
+	/* Overflow: values larger than destination type. */
+	err |= TEST_ONE_SHIFT(0x100, 0, u8, 0, true);
+	err |= TEST_ONE_SHIFT(0xFF, 0, s8, 0, true);
+	err |= TEST_ONE_SHIFT(0x10000U, 0, u16, 0, true);
+	err |= TEST_ONE_SHIFT(0xFFFFU, 0, s16, 0, true);
+	err |= TEST_ONE_SHIFT(0x100000000ULL, 0, u32, 0, true);
+	err |= TEST_ONE_SHIFT(0x100000000ULL, 0, unsigned int, 0, true);
+	err |= TEST_ONE_SHIFT(0xFFFFFFFFUL, 0, s32, 0, true);
+	err |= TEST_ONE_SHIFT(0xFFFFFFFFUL, 0, int, 0, true);
+	err |= TEST_ONE_SHIFT(0xFFFFFFFFFFFFFFFFULL, 0, s64, 0, true);
+
+	/* Nonsense: negative initial value. */
+	err |= TEST_ONE_SHIFT(-1, 0, s8, 0, true);
+	err |= TEST_ONE_SHIFT(-1, 0, u8, 0, true);
+	err |= TEST_ONE_SHIFT(-5, 0, s16, 0, true);
+	err |= TEST_ONE_SHIFT(-5, 0, u16, 0, true);
+	err |= TEST_ONE_SHIFT(-10, 0, int, 0, true);
+	err |= TEST_ONE_SHIFT(-10, 0, unsigned int, 0, true);
+	err |= TEST_ONE_SHIFT(-100, 0, s32, 0, true);
+	err |= TEST_ONE_SHIFT(-100, 0, u32, 0, true);
+	err |= TEST_ONE_SHIFT(-10000, 0, s64, 0, true);
+	err |= TEST_ONE_SHIFT(-10000, 0, u64, 0, true);
+
+	/* Nonsense: negative shift values. */
+	err |= TEST_ONE_SHIFT(0, -5, s8, 0, true);
+	err |= TEST_ONE_SHIFT(0, -5, u8, 0, true);
+	err |= TEST_ONE_SHIFT(0, -10, s16, 0, true);
+	err |= TEST_ONE_SHIFT(0, -10, u16, 0, true);
+	err |= TEST_ONE_SHIFT(0, -15, int, 0, true);
+	err |= TEST_ONE_SHIFT(0, -15, unsigned int, 0, true);
+	err |= TEST_ONE_SHIFT(0, -20, s32, 0, true);
+	err |= TEST_ONE_SHIFT(0, -20, u32, 0, true);
+	err |= TEST_ONE_SHIFT(0, -30, s64, 0, true);
+	err |= TEST_ONE_SHIFT(0, -30, u64, 0, true);
+
+	/* Overflow: shifted at or beyond entire type's bit width. */
+	err |= TEST_ONE_SHIFT(0, 8, u8, 0, true);
+	err |= TEST_ONE_SHIFT(0, 9, u8, 0, true);
+	err |= TEST_ONE_SHIFT(0, 8, s8, 0, true);
+	err |= TEST_ONE_SHIFT(0, 9, s8, 0, true);
+	err |= TEST_ONE_SHIFT(0, 16, u16, 0, true);
+	err |= TEST_ONE_SHIFT(0, 17, u16, 0, true);
+	err |= TEST_ONE_SHIFT(0, 16, s16, 0, true);
+	err |= TEST_ONE_SHIFT(0, 17, s16, 0, true);
+	err |= TEST_ONE_SHIFT(0, 32, u32, 0, true);
+	err |= TEST_ONE_SHIFT(0, 33, u32, 0, true);
+	err |= TEST_ONE_SHIFT(0, 32, int, 0, true);
+	err |= TEST_ONE_SHIFT(0, 33, int, 0, true);
+	err |= TEST_ONE_SHIFT(0, 32, s32, 0, true);
+	err |= TEST_ONE_SHIFT(0, 33, s32, 0, true);
+	err |= TEST_ONE_SHIFT(0, 64, u64, 0, true);
+	err |= TEST_ONE_SHIFT(0, 65, u64, 0, true);
+	err |= TEST_ONE_SHIFT(0, 64, s64, 0, true);
+	err |= TEST_ONE_SHIFT(0, 65, s64, 0, true);
+
+	/*
+	 * Corner case: for unsigned types, we fail when we've shifted
+	 * through the entire width of bits. For signed types, we might
+	 * want to match this behavior, but that would mean noticing if
+	 * we shift through all but the signed bit, and this is not
+	 * currently detected (but we'll notice an overflow into the
+	 * signed bit). So, for now, we will test this condition but
+	 * mark it as not expected to overflow.
+	 */
+	err |= TEST_ONE_SHIFT(0, 7, s8, 0, false);
+	err |= TEST_ONE_SHIFT(0, 15, s16, 0, false);
+	err |= TEST_ONE_SHIFT(0, 31, int, 0, false);
+	err |= TEST_ONE_SHIFT(0, 31, s32, 0, false);
+	err |= TEST_ONE_SHIFT(0, 63, s64, 0, false);
+
+	return err;
+}
+
 /*
  * Deal with the various forms of allocator arguments. See comments above
  * the DEFINE_TEST_ALLOC() instances for mapping of the "bits".
@@ -397,6 +592,7 @@  static int __init test_module_init(void)
 	int err = 0;
 
 	err |= test_overflow_calculation();
+	err |= test_overflow_shift();
 	err |= test_overflow_allocation();
 
 	if (err) {