[RFC] saturate check_*_overflow() output?

[RFC] saturate check_*_overflow() output?

[Kees Cook]

Hi,

I wonder if we should explicitly saturate the output of the overflow
helpers as a side-effect of overflow detection? (That way the output
is never available with a "bad" value, if the caller fails to check the
result or forgets that *d was written...) since right now, *d will hold
the wrapped value.

Also, if we enable arithmetic overflow detection sanitizers, we're going
to trip over the fallback implementation (since it'll wrap and then do
the overflow test in the macro).

e.g. I'm think of something like this (showing only "mul" here, and
untested):

diff --git a/include/linux/overflow.h b/include/linux/overflow.h
index 93fcef105061..00baf3a75dc7 100644
--- a/include/linux/overflow.h
+++ b/include/linux/overflow.h
@@ -71,12 +71,16 @@
 })
 
 #define check_mul_overflow(a, b, d) ({		\
+	bool __result;				\
 	typeof(a) __a = (a);			\
 	typeof(b) __b = (b);			\
 	typeof(d) __d = (d);			\
 	(void) (&__a == &__b);			\
 	(void) (&__a == __d);			\
-	__builtin_mul_overflow(__a, __b, __d);	\
+	__result = __builtin_mul_overflow(__a, __b, __d);\
+	if (unlikely(__result))			\
+		*__d = type_max(__a);		\
+	__result;				\
 })
 
 #else
@@ -105,15 +109,20 @@
  * If one of a or b is a compile-time constant, this avoids a division.
  */
 #define __unsigned_mul_overflow(a, b, d) ({		\
+	bool __result;					\
 	typeof(a) __a = (a);				\
 	typeof(b) __b = (b);				\
 	typeof(d) __d = (d);				\
 	(void) (&__a == &__b);				\
 	(void) (&__a == __d);				\
-	*__d = __a * __b;				\
-	__builtin_constant_p(__b) ?			\
+	__result = __builtin_constant_p(__b) ?		\
 	  __b > 0 && __a > type_max(typeof(__a)) / __b : \
 	  __a > 0 && __b > type_max(typeof(__b)) / __a;	 \
+	if (unlikely(__result))				\
+		*__d = type_max(typeof(__a));		\
+	else						\
+		*__d = __a * __b;			\
+	__result;
 })
 
 /*
@@ -176,6 +185,7 @@
  */
 
 #define __signed_mul_overflow(a, b, d) ({				\
+	bool __result;							\
 	typeof(a) __a = (a);						\
 	typeof(b) __b = (b);						\
 	typeof(d) __d = (d);						\
@@ -183,10 +193,14 @@
 	typeof(a) __tmin = type_min(typeof(a));				\
 	(void) (&__a == &__b);						\
 	(void) (&__a == __d);						\
-	*__d = (u64)__a * (u64)__b;					\
-	(__b > 0   && (__a > __tmax/__b || __a < __tmin/__b)) ||	\
-	(__b < (typeof(__b))-1  && (__a > __tmin/__b || __a < __tmax/__b)) || \
-	(__b == (typeof(__b))-1 && __a == __tmin);			\
+	__result = (__b > 0   && (__a > __tmax/__b || __a < __tmin/__b)) || \
+		   (__b < (typeof(__b))-1  && (__a > __tmin/__b || __a < __tmax/__b)) || \
+		   (__b == (typeof(__b))-1 && __a == __tmin);		\
+	if (unlikely(__result))						\
+		*__d = type_max(__a);					\
+	else								\
+		*__d = (u64)__a * (u64)__b;				\
+	__result;							\
 })
 
 

Thoughts?

-- 
Kees Cook

Re: [RFC] saturate check_*_overflow() output?

[Rasmus Villemoes]

On 03/08/2020 20.29, Kees Cook wrote:
> Hi,
> 
> I wonder if we should explicitly saturate the output of the overflow
> helpers as a side-effect of overflow detection? 

Please no.

(That way the output
> is never available with a "bad" value, if the caller fails to check the
> result or forgets that *d was written...) since right now, *d will hold
> the wrapped value.

Exactly. I designed the fallback ones so they would have the same
semantics as when using gcc's __builtin_* - though with the "all
operands have same type" restriction, since it would be completely
unwieldy to handle stuff like (s8) + (u64) -> (s32) in macros.

> Also, if we enable arithmetic overflow detection sanitizers, we're going
> to trip over the fallback implementation (since it'll wrap and then do
> the overflow test in the macro).

Huh? The fallback code only ever uses unsigned arithmetic, precisely to
avoid triggering such warnings. Or are you saying there are some
sanitizers out there which also warn for, say, (~0u) + 1u? Yes,
detecting overflow/underflow for a (s32)-(s32)->(s32) without relying on
-fwrapv is a bit messy, but it's done and AFAIK works just fine even
with UBSAN enabled.


What we might do, to deal with the "caller fails to check the result",
is to add a

static inline bool __must_check must_check_overflow(bool b) { return
unlikely(b); }

and wrap all the final "did it overflow" results in that one - perhaps
also for the __builtin_* cases, I don't know if those are automatically
equipped with that attribute. [I also don't know if gcc propagates
likely/unlikely out to the caller, but it shouldn't hurt to have it
there and might improve code gen if it does.]

Rasmus

PS: Another reason not to saturate is that there are two extreme values,
and choosing between them makes the code very messy (especially when
using the __builtins). 5u-10u should saturate to 0u, not UINT_MAX, and
even for for underflowing a signed computation like INT_MIN + (-7); it
makes no sense for that to saturate to INT_MAX.

Re: [RFC] saturate check_*_overflow() output?

[Kees Cook]

On Tue, Aug 04, 2020 at 08:11:45AM +0200, Rasmus Villemoes wrote:
> On 03/08/2020 20.29, Kees Cook wrote:
> > Hi,
> > 
> > I wonder if we should explicitly saturate the output of the overflow
> > helpers as a side-effect of overflow detection? 
> 
> Please no.

I'm entirely on the fence about this, so I'm fine with that answer. (And
I see your PS about why -- thanks!)

> 
> (That way the output
> > is never available with a "bad" value, if the caller fails to check the
> > result or forgets that *d was written...) since right now, *d will hold
> > the wrapped value.
> 
> Exactly. I designed the fallback ones so they would have the same
> semantics as when using gcc's __builtin_* - though with the "all
> operands have same type" restriction, since it would be completely
> unwieldy to handle stuff like (s8) + (u64) -> (s32) in macros.

Right -- a totally sane requirement. :)

> 
> > Also, if we enable arithmetic overflow detection sanitizers, we're going
> > to trip over the fallback implementation (since it'll wrap and then do
> > the overflow test in the macro).
> 
> Huh? The fallback code only ever uses unsigned arithmetic, precisely to
> avoid triggering such warnings. Or are you saying there are some
> sanitizers out there which also warn for, say, (~0u) + 1u? Yes,
> detecting overflow/underflow for a (s32)-(s32)->(s32) without relying on
> -fwrapv is a bit messy, but it's done and AFAIK works just fine even
> with UBSAN enabled.

GCC only has a signed overflow sanitizer. Clang has signed and unsigned.
Dealing with -fwrapv is yet another exercise.

And I can solve this differently, too, with a static inline helper that does
basic mul and carries a no-sanitize attribute.

> What we might do, to deal with the "caller fails to check the result",
> is to add a
> 
> static inline bool __must_check must_check_overflow(bool b) { return
> unlikely(b); }
> 
> and wrap all the final "did it overflow" results in that one - perhaps
> also for the __builtin_* cases, I don't know if those are automatically
> equipped with that attribute. [I also don't know if gcc propagates
> likely/unlikely out to the caller, but it shouldn't hurt to have it
> there and might improve code gen if it does.]

(What is the formal name for the ({ ...; return_value; }) C construct?)

Will that work as a macro return value? If so, that's extremely useful.

> PS: Another reason not to saturate is that there are two extreme values,
> and choosing between them makes the code very messy (especially when
> using the __builtins). 5u-10u should saturate to 0u, not UINT_MAX, and
> even for for underflowing a signed computation like INT_MIN + (-7); it
> makes no sense for that to saturate to INT_MAX.

Ah, gotcha.

-- 
Kees Cook

Re: [RFC] saturate check_*_overflow() output?

[Matthew Wilcox]

On Tue, Aug 04, 2020 at 12:23:03PM -0700, Kees Cook wrote:
> > What we might do, to deal with the "caller fails to check the result",
> > is to add a
> > 
> > static inline bool __must_check must_check_overflow(bool b) { return
> > unlikely(b); }
> > 
> > and wrap all the final "did it overflow" results in that one - perhaps
> > also for the __builtin_* cases, I don't know if those are automatically
> > equipped with that attribute. [I also don't know if gcc propagates
> > likely/unlikely out to the caller, but it shouldn't hurt to have it
> > there and might improve code gen if it does.]
> 
> (What is the formal name for the ({ ...; return_value; }) C construct?)

'Statement Exprs'.

A compound statement enclosed in parentheses may appear as an expression
in GNU C.  This allows you to use loops, switches, and local variables
within an expression.

Re: [RFC] saturate check_*_overflow() output?

[Rasmus Villemoes]

On 04/08/2020 21.23, Kees Cook wrote:
> On Tue, Aug 04, 2020 at 08:11:45AM +0200, Rasmus Villemoes wrote:

>> What we might do, to deal with the "caller fails to check the result",
>> is to add a
>>
>> static inline bool __must_check must_check_overflow(bool b) { return
>> unlikely(b); }
>>
>> and wrap all the final "did it overflow" results in that one - perhaps
>> also for the __builtin_* cases, I don't know if those are automatically
>> equipped with that attribute. [I also don't know if gcc propagates
>> likely/unlikely out to the caller, but it shouldn't hurt to have it
>> there and might improve code gen if it does.]
> 
> (What is the formal name for the ({ ...; return_value; }) C construct?)

https://gcc.gnu.org/onlinedocs/gcc/Statement-Exprs.html

> Will that work as a macro return value? If so, that's extremely useful.

Yes and no. Just wrapping the last expression in the statement
expression with my must_check_overflow(), as in

@@ -67,17 +72,18 @@
        typeof(d) __d = (d);                    \
        (void) (&__a == &__b);                  \
        (void) (&__a == __d);                   \
-       __builtin_sub_overflow(__a, __b, __d);  \
+       must_check_overflow(__builtin_sub_overflow(__a, __b, __d));     \
 })

does not appear to work. For some reason, this can't be (ab)used to
overrule the __must_check this simply:

  - kstrtoint(a, b, c);
  + ({ kstrtoint(a, b, c); });

still gives a warning for kstrtoint(). But failing to use the result of
check_sub_overflow() as patched above does not give a warning.

I'm guessing gcc has some internal very early simplification that
replaces single-expression statement-exprs with just that expression,
and the warn-unused-result triggers later. But as soon as the
statement-expr becomes a little non-trivial (e.g. above), my guess is
that the whole thing gets assigned to some internal "variable"
representing the result, and that assignment then counts as a use of the
return value from must_check_overflow() - cc'ing Segher, as he usually
knows these details.

Anyway, we don't need to apply it to the last expression inside ({}), we
can just pass the whole ({}) to must_check_overflow() as in

-#define check_sub_overflow(a, b, d) ({         \
+#define check_sub_overflow(a, b, d) must_check_overflow(({             \
        typeof(a) __a = (a);                    \
        typeof(b) __b = (b);                    \
        typeof(d) __d = (d);                    \
        (void) (&__a == &__b);                  \
        (void) (&__a == __d);                   \
        __builtin_sub_overflow(__a, __b, __d);  \
-})
+}))

and that's even more natural for the fallback cases which would be

 #define check_sub_overflow(a, b, d)                                    \
+       must_check_overflow(                                            \
        __builtin_choose_expr(is_signed_type(typeof(a)),                \
                        __signed_sub_overflow(a, b, d),                 \
-                       __unsigned_sub_overflow(a, b, d))
+                       __unsigned_sub_overflow(a, b, d)))

(in all cases with some whitespace reflowing).

Rasmus

Re: [RFC] saturate check_*_overflow() output?

[Kees Cook]

On Wed, Aug 05, 2020 at 01:38:58PM +0200, Rasmus Villemoes wrote:
> Anyway, we don't need to apply it to the last expression inside ({}), we
> can just pass the whole ({}) to must_check_overflow() as in
> 
> -#define check_sub_overflow(a, b, d) ({         \
> +#define check_sub_overflow(a, b, d) must_check_overflow(({             \

Oh! Yes, of course. I was blinded by looking inside the macro and not
wanting to spoil the type magic. Yes, that's perfect. I will spin a
patch...

-- 
Kees Cook

Re: [RFC] saturate check_*_overflow() output?

[Segher Boessenkool]

Hi Rasmus,

On Wed, Aug 05, 2020 at 01:38:58PM +0200, Rasmus Villemoes wrote:
> I'm guessing gcc has some internal very early simplification that
> replaces single-expression statement-exprs with just that expression,
> and the warn-unused-result triggers later. But as soon as the
> statement-expr becomes a little non-trivial (e.g. above), my guess is
> that the whole thing gets assigned to some internal "variable"
> representing the result, and that assignment then counts as a use of the
> return value from must_check_overflow() - cc'ing Segher, as he usually
> knows these details.

A statement expression is not a statement (it's an expression), which
turns half of the world upside down.  This GCC extension often has weird
(or at least non-intuitive) side effects, together with other extensions
(like attributes), etc.

This may be a convoluted way of saying "I don't know, look at c/c-decl.c
(and maybe c/c-parser.c) to see if you can find out" ;-)


> Anyway, we don't need to apply it to the last expression inside ({}), we
> can just pass the whole ({}) to must_check_overflow() as in

<snip>

Yes, much nicer :-)  Crisis averted, etc.


Segher