OpenBSD mallocarray

Sure. +1 from me. I don't think we want the M_CANFAIL hack, though.

Best,
Conrad

Ryan Stone

2016-02-01 20:56:20 UTC

Post by Conrad Meyer
Sure. +1 from me. I don't think we want the M_CANFAIL hack, though.
Best,
Conrad

That may be the OpenBSD equivalent of M_NOWAIT.

Mike Belopuhov

2016-02-01 21:02:58 UTC

Post by Conrad Meyer
Sure. +1 from me. I don't think we want the M_CANFAIL hack, though.
Best,
Conrad

That may be the OpenBSD equivalent of M_NOWAIT.

Not quite. From the man page:

M_CANFAIL

In the M_WAITOK case, if not enough memory is available,
return NULL instead of calling panic(9). If mallocarray()
detects an overflow or malloc() detects an excessive
allocation, return NULL instead of calling panic(9).

Cheers,
Mike

Warner Losh

2016-02-01 21:12:20 UTC

Post by Conrad Meyer
Sure. +1 from me. I don't think we want the M_CANFAIL hack, though.
Best,
Conrad

That may be the OpenBSD equivalent of M_NOWAIT.

M_CANFAIL
In the M_WAITOK case, if not enough memory is available,
return NULL instead of calling panic(9). If mallocarray()
detects an overflow or malloc() detects an excessive
allocation, return NULL instead of calling panic(9).

Yea, we donât want it calling panic. Ever. That turns an overflow
into a DoS. Arguments should be properly checked so we can
properly return EINVAL for bat-**** crazy ones. FreeBSDâs malloc
doesnât cave an excessive detector in it.

My concern with this is that we have a number of different allocation
routines in FreeBSD. This only goes after the malloc() vector, and
even then it requires code changes.

At best, CANFAIL is a kludge to fail with a panic instead of an
overflow. Thatâs got to be at most a transient thing until all the
code that it is kludged into with out proper thought is fixed. Iâm not
sure thatâs something that we want to encourage. Iâm all for
safety, but this flag seems both unsafe and unwise.

Warner

Brooks Davis

2016-02-01 22:48:54 UTC

Post by Conrad Meyer
Sure. +1 from me. I don't think we want the M_CANFAIL hack, though.
Best,
Conrad

That may be the OpenBSD equivalent of M_NOWAIT.

Yea, we don???t want it calling panic. Ever. That turns an overflow
into a DoS. Arguments should be properly checked so we can
properly return EINVAL for bat-**** crazy ones. FreeBSD???s malloc
doesn???t cave an excessive detector in it.
My concern with this is that we have a number of different allocation
routines in FreeBSD. This only goes after the malloc() vector, and
even then it requires code changes.
At best, CANFAIL is a kludge to fail with a panic instead of an
overflow. That???s got to be at most a transient thing until all the
code that it is kludged into with out proper thought is fixed. I???m not
sure that???s something that we want to encourage. I???m all for
safety, but this flag seems both unsafe and unwise.

Given that current code could be doing literally anything in the
overflow case (and thanks to modern undefined behavior optimizations is
likely doing something extraordinarily bizarre), I think turning overflows
into panics is a good thing. Yes, you can argue that means you've added
a DoS vector, but best case you had an under allocation and bizarre
memory corruption before. If the default or even only behavior is going
to be that overflow fails then we need a static checker that ensure we
check the return value even in the M_WAITOK. Otherwise there will be
blind conversions of malloc to mallocarray that go unchecked.

-- Brooks

Warner Losh

2016-02-01 23:01:14 UTC

Post by Conrad Meyer
Sure. +1 from me. I don't think we want the M_CANFAIL hack, though.
Best,
Conrad

That may be the OpenBSD equivalent of M_NOWAIT.

Returning NULL should be sufficient. Blind conversion of malloc to
mallocarray in the kernel is also stupid. Intelligent conversion is
needed to ensure that the error conditions are handled correctly.
There's no need for a flag to say 'I am going to do the right thing
if you give me NULL back'. The conversion should do the right
thing when you get NULL back. A quick survey of the current kernel
shows that there's not very many that could be using user defined
values, but does show a large number of places where we could
use this API.

I guess this comes down to 'why is it an unreasonable burden to
test the return value in code that's converted?' We're already changing
the code.

If you absolutely must have a flag, I'd prefer M_CANPANIC or something
that is also easy to add for the 'mindless' case that we can easily
grep for so we know when we're removed all the stupid 'mindless'
cases from the tree.

Warner

Brooks Davis

2016-02-01 23:59:57 UTC

Post by Conrad Meyer
Sure. +1 from me. I don't think we want the M_CANFAIL hack, though.
Best,
Conrad

That may be the OpenBSD equivalent of M_NOWAIT.

On further consideration, I think returning NULL is sufficient since most
of the time failure to check will result in a nearby fault. The main
thing is eliminating the undefined behavior.

-- Brooks

John Baldwin

2016-02-03 19:39:11 UTC

Post by Conrad Meyer
Sure. +1 from me. I don't think we want the M_CANFAIL hack, though.
Best,
Conrad

That may be the OpenBSD equivalent of M_NOWAIT.

Returning NULL should be sufficient. Blind conversion of malloc to
mallocarray in the kernel is also stupid. Intelligent conversion is
needed to ensure that the error conditions are handled correctly.
There's no need for a flag to say 'I am going to do the right thing
if you give me NULL back'. The conversion should do the right
thing when you get NULL back. A quick survey of the current kernel
shows that there's not very many that could be using user defined
values, but does show a large number of places where we could
use this API.
I guess this comes down to 'why is it an unreasonable burden to
test the return value in code that's converted?' We're already changing
the code.
If you absolutely must have a flag, I'd prefer M_CANPANIC or something
that is also easy to add for the 'mindless' case that we can easily
grep for so we know when we're removed all the stupid 'mindless'
cases from the tree.

Having M_WAITOK-anything return NULL will be a POLA violation. It doesn't
return NULL for anything else. I think having a separate M_CANFAIL flag
is also rather pointless. If we want to have this, I think it should
work similar to malloc(). M_WAITOK panics if you do stupid things
(malloc(9) does this for sufficiently large overflow when it exhausts kmem
contrary to Warner's earlier claim), M_NOWAIT returns NULL.

In general I think I most prefer Bruce's approach of having a separate macro
to check for overflow explicitly so it can be handled as a separate error.
In particular, if mallocarry(..., M_NOWAIT) fails, is it because of memory
shortage (in which case retrying in the future might be sensible) or is it
due to overflow (in which case it will fail no matter how many times you
retry)? You'd then have to have the macro anyway to differentiate and handle
this case.

Warner also seems to be assuming that we should do check for overflow
explicitly for any user-supplied values before calling malloc() or
malloc()-like things. This means N hand-rolled (and possibly buggy) checks,
or a shared macro to do the check. I think this is another argument in favor
of Bruce's approach. :)

If you go that route, then mallocarray() is really just an assertion
checker. It should only fail because a programmer ommitted an explicit
overflow check for a user-supplied value or screwed up an in-kernel
value. In that case I think panic'ing sooner when the overflow is obvious
is more useful for debugging the error than a NULL pointer deference
some time later (or requests that get retried forever and go possibly
unnoticed).

--
John Baldwin

Warner Losh

2016-02-03 19:43:55 UTC

Post by Conrad Meyer

Post by Conrad Meyer
Sure. +1 from me. I don't think we want the M_CANFAIL hack,

though.

Post by Conrad Meyer
Best,
Conrad

That may be the OpenBSD equivalent of M_NOWAIT.

not

sure that???s something that we want to encourage. I???m all for
safety, but this flag seems both unsafe and unwise.

overflows

Post by Brooks Davis
into panics is a good thing. Yes, you can argue that means you've

added

Post by Brooks Davis
a DoS vector, but best case you had an under allocation and bizarre
memory corruption before. If the default or even only behavior is

going

Post by Brooks Davis
to be that overflow fails then we need a static checker that ensure we
check the return value even in the M_WAITOK. Otherwise there will be
blind conversions of malloc to mallocarray that go unchecked.

Returning NULL should be sufficient. Blind conversion of malloc to
mallocarray in the kernel is also stupid. Intelligent conversion is
needed to ensure that the error conditions are handled correctly.
There's no need for a flag to say 'I am going to do the right thing
if you give me NULL back'. The conversion should do the right
thing when you get NULL back. A quick survey of the current kernel
shows that there's not very many that could be using user defined
values, but does show a large number of places where we could
use this API.
I guess this comes down to 'why is it an unreasonable burden to
test the return value in code that's converted?' We're already changing
the code.
If you absolutely must have a flag, I'd prefer M_CANPANIC or something
that is also easy to add for the 'mindless' case that we can easily
grep for so we know when we're removed all the stupid 'mindless'
cases from the tree.

Exausting kmem isn't influenced by simple args. But I do stand corrected.

Post by Conrad Meyer
In general I think I most prefer Bruce's approach of having a separate macro
to check for overflow explicitly so it can be handled as a separate error.
In particular, if mallocarry(..., M_NOWAIT) fails, is it because of memory
shortage (in which case retrying in the future might be sensible) or is it
due to overflow (in which case it will fail no matter how many times you
retry)? You'd then have to have the macro anyway to differentiate and handle
this case.
Warner also seems to be assuming that we should do check for overflow
explicitly for any user-supplied values before calling malloc() or
malloc()-like things. This means N hand-rolled (and possibly buggy) checks,
or a shared macro to do the check. I think this is another argument in favor
of Bruce's approach. :)

I like Bruce's approach. And it works for more than just malloc.

Post by Conrad Meyer
If you go that route, then mallocarray() is really just an assertion
checker. It should only fail because a programmer ommitted an explicit
overflow check for a user-supplied value or screwed up an in-kernel
value. In that case I think panic'ing sooner when the overflow is obvious
is more useful for debugging the error than a NULL pointer deference
some time later (or requests that get retried forever and go possibly
unnoticed).

That would be fine. On its own, mallocarray() has all the issues we've
talked about.

Warner

Warner Losh

2016-02-01 22:49:14 UTC

Post by C Turt
M_CANFAIL
In the M_WAITOK case, if not enough memory is available,
return NULL instead of calling panic(9). If mallocarray()
detects an overflow or malloc() detects an excessive
allocation, return NULL instead of calling panic(9).

Yea, we don’t want it calling panic. Ever. That turns an overflow
into a DoS.

I disagree. The panic is essentially an assertion that malloc was
passed valid arguments. We have similar invariants assertions
throughout the kernel and it is the only sane thing to do with
overflow + M_WAITOK. M_WAITOK callers today will do something equally
stupid if they get a NULL result from mallocarray().

We only do this for things that can't happen. If the user can trigger this
panic by passing some bogus, unchecked value that doesn't get checked
until here, that's bad. That's fundamentally different than getting
'freeing free inode' from ufs. Users can't trigger the latter.

Arguments should be properly checked

Yes! That's why the assertion is a good thing.

We disagree on this then. This isn't a 'fail safe' this is a 'fail
with denial of system'. that'

At best, CANFAIL is a kludge to fail with a panic instead of an
overflow.

No, that's backwards. In CANFAIL mode, mallocarray returns NULL
instead of panicing immediately. It's a kludge so the caller doesn't
have to do overflow checking.

Then it's a horrible interface. We failed badly with the MPSAFE
interface. It was OK at first, but then when everybody uses it, then
it because obvious that it was the wrong decision.

That’s got to be at most a transient thing until all the
code that it is kludged into with out proper thought is fixed.

You mean the panic? What fallback behavior would you prefer? If the
caller requested an overflowing allocation, there really isn't
anything sane to do besides immediately panic (again, for M_WAITOK).
Even M_NOWAIT callers may or may not do something sane.

I'd prefer that we return NULL. Let the caller decide the policy,
not some stupid thing down in the bowls of malloc because
I forgot to include some stupid new flag.

M_NOWAIT callers know to check for NULL, or they have a bug.
It would be the same for mallocarray: you must check for NULL and
unwind if you get that back. There's no need for the CANFAIL flag
and it's a horrible API.

Warner

Conrad Meyer

2016-02-01 22:57:37 UTC

Yea, we don’t want it calling panic. Ever. That turns an overflow
into a DoS.

We only do this for things that can't happen.

Exactly. malloc requests that overflow a size_t *cannot* happen.
Today they are undefined behavior / at best memory corruption. This
is not something we want users to be able to trigger, ever.

Post by Warner Losh
If the user can trigger this
panic by passing some bogus, unchecked value that doesn't get checked
until here, that's bad.

Agreed.

Post by Warner Losh
That's fundamentally different than getting
'freeing free inode' from ufs. Users can't trigger the latter.

Users must not be able to trigger this panic either.

Post by Warner Losh
We disagree on this then. This isn't a 'fail safe' this is a 'fail
with denial of system'. that'

What is your alternative proposal, in this scenario, that results in
any better result than DoS? Heap corruption and code execution is not
a better result than DoS, IMO. Keep in mind that if the user controls
array size allocation in this scenario, even without the panic they
may DoS the system with a huge-but-smaller-than-size_t kernel memory
allocation.

I'd prefer that we return NULL. Let the caller decide the policy,
not some stupid thing down in the bowls of malloc because
I forgot to include some stupid new flag.

If we don't panic explicitly, we panic implicitly for unfixed M_WAITOK
users of the interface. I think the explicit panic is better, at
least until callers are fixed.

Post by Warner Losh
M_NOWAIT callers know to check for NULL, or they have a bug.

Yes, but it's a different error. E.g. callers cannot handle EAGAIN like EINVAL.

Post by Warner Losh
It would be the same for mallocarray: you must check for NULL and
unwind if you get that back. There's no need for the CANFAIL flag
and it's a horrible API.

I agree CANFAIL is terrible but come down on the opposite side for the
default behavior when given overflowing arguments. Overflowing
arguments should never happen. It is a bogus use of the API.

Best,
Conrad

Bruce Evans

2016-02-02 06:05:18 UTC

Post by Warner Losh
...

Post by Warner Losh
Thatâs got to be at most a transient thing until all the
code that it is kludged into with out proper thought is fixed.

I'd prefer that we return NULL. Let the caller decide the policy,
not some stupid thing down in the bowls of malloc because
I forgot to include some stupid new flag.
M_NOWAIT callers know to check for NULL, or they have a bug.
It would be the same for mallocarray: you must check for NULL and
unwind if you get that back. There's no need for the CANFAIL flag
and it's a horrible API.

The whole API is horrible. It is a wrapper that is intended to make
things simpler, but actually makes them more complicated. It is even
worse than calloc(3) since normal use of malloc(9) is to never fail,
while both malloc(3) and calloc(3) always have failure modes.

It is the array size calculation that can overflow, not the allocation.

First I note how using calloc(3) is only slightly more complicated
unless sloppy error handling is acceptable. Good version that does
checks up front like most malloc(9) users already do, but for malloc(3).

if (size != 0 && SIZE_MAX / size < num)
return (EINVAL);
if (malloc((size_t)size * num) == NULL)
laboriously_handle_error_usually_worse_than_null_ptr_core();

The error "can't happen", and we can make that even more likely by
changing SIZE_MAX to a small value. We should usually change SIZE_MAX
to a small value anyway to limit denials of service to other caleers.

The overflow check can be hidden in a macro (not in an inline function
without expanding everything to uintmax_t), but using the macro isn't
much easier:

#define MALLOC_ARRAY_CHECK(num, size, limit) \
((size) == 0 || limit / (size) >= (num))
...
if (!MALLOC_ARRAY_CHECK(num, size, SIZE_MAX))
return (EINVAL);
if (malloc((size_t)size * num) == NULL)
laboriously_handle_error_usually_worse_than_null_ptr_core();

Sloppy code using calloc():

if (calloc(num, size) == NULL)
laboriously_handle_error_usually_worse_than_null_ptr_core();

Equivalent code using calloc():

if (calloc(num, size) == NULL) {
/*
* calloc() doesn't tell us the precise reason for failure,
* and decoding errno wouldn't be much better than the
* following,
* so if our API is not as bad as that then we must check
* for overflow like we should have done up front.
*/
if (!MALLOC_ARRAY_CHECK(num, size, SIZE_MAX))
return (EINVAL);
laboriously_handle_error_usually_worse_than_null_ptr_core();
}

Using malloc(9) with M_NOWAIT is similar except the error handling must be
even more laborious to be correct. It usually isn't correct, but is more
needed and is sometimes better than a null pointer panic. Using M_WAITOK,
we lose the simpler code that is possible by not having error handling in
every caller. Good version:

if (!MALLOC_ARRAY_CHECK(num, size, my_limit))
return (EINVAL);
ptr = malloc((size_t)size * num, M_FOO, M_WAITOK);

The error handling is obviously neither neither laborious or incorrect.
It is just to handle a DOS from callers.

Worse version: put all the args in a function. Add flags to control
the error handling. I forget the details of mallocarray(). The above
can be done by adding 2 args:

ptr = mymallocarray(num, size, sizelimit, M_FOO, M_WAITOK);
if (ptr == NULL)
return (EINVAL);

This is actually a couple of words less complicated, but also less
clear. It hides the limit check.

Don't forget to expand the types taken by the function to uintmax_t.
Otherwise, overflow may occur when the function is called when the
type of num, size of sizelimit is larger than size_t (most likely
if it is a 64-bit type on a 32-bit arch). The macro handles this
automatically provided size_max <= SIZE_MAX.

Bruce

C Turt

2016-02-11 21:21:42 UTC

I just wanted to post some real world examples of bugs which could be
mitigated with `mallocarray` to attract more interest.

My most meritable example of a real world attack from this behaviour would
be the sys_dynlib_prepare_dlclose kernel exploit for PS4 (PS4 OS is based
on FreeBSD 9.0). You may read my write-up of this exploit here:
http://cturt.github.io/dlclose-overflow.html

The significance of this example is that if a `mallocarray` wrapper was
available, and used here, the bug would not have been exploitable, because
it would have intentionally panicked instead of continuing with an under
allocated buffer.

You may think that this is clearly Sony's fault for not checking the count
at all, and that FreeBSD kernel code would never have a bug like this,
which is why I would like to mention that similar overflows can be possible
even if there initially appear to be sufficient bound checks performed.

There are several pieces of vulnerable code present in FreeBSD kernel
(albeit most of them are triggerable only as root so are not critical),
however I will use the file `/sys/kern/kern_alq.c` to demonstrate. There
are some checks on counts and sizes, but they are insufficient:

[CODE]int
alq_open(struct alq **alqp, const char *file, struct ucred *cred, int cmode,
int size, int count)
{
int ret;

KASSERT((count >= 0), ("%s: count < 0", __func__));

if (count > 0) {
if ((ret = alq_open_flags(alqp, file, cred, cmode,
size*count, 0)) == 0) {
(*alqp)->aq_flags |= AQ_LEGACY;
(*alqp)->aq_entmax = count;
(*alqp)->aq_entlen = size;
}

...

int
alq_open_flags(struct alq **alqp, const char *file, struct ucred *cred, int
cmode,
int size, int flags)
{
...
KASSERT((size > 0), ("%s: size <= 0", __func__));
...
alq->aq_buflen = size;
...
alq->aq_entbuf = malloc(alq->aq_buflen, M_ALD, M_WAITOK|M_ZERO);[/CODE]

The check on `count` being greater than or equal to 0 in `alq_open`, and
the check for `size` being greater than 0 in `alq_open_flags` are cute, but
they don't check for an overflow of `size*count`.

This code path is reachable in several places, such as
`sysctl_debug_ktr_alq_enable`:

[CODE]static int
sysctl_debug_ktr_alq_enable(SYSCTL_HANDLER_ARGS)
{
...
error = alq_open(&ktr_alq, (const char *)ktr_alq_file,
req->td->td_ucred, ALQ_DEFAULT_CMODE,
sizeof(struct ktr_entry), ktr_alq_depth);
[/CODE]

With `ktr_alq_depth` being controllable from userland (but only as root):

[CODE]SYSCTL_INT(_debug_ktr, OID_AUTO, alq_depth, CTLFLAG_RW,
&ktr_alq_depth, 0, "Number of items in the write buffer");[/CODE]

`sizeof(struct ktr_entry)` is 88 bytes. So theoretically if `ktr_alq_depth`
is set to `48806447`, we'll get an allocation of `0x100000028`, which
truncates to 0x28 = 40 bytes. A heap overflow would then possible when this
buffer is iterated over with `aq_entmax` and `aq_entlen`.

Post by C Turt
I've recently started browsing the OpenBSD kernel source code, and have
found the mallocarray function positively wonderful. I would like to
discuss the possibility of getting this into FreeBSD kernel.
For example, many parts of kernel code in FreeBSD use something like
malloc(xxx * sizeof(struct xxx)). If xxx is 64bit and controllable by user,
this allocation can easily overflow, resulting in a heap overflow later on.
The mallocarray is a wrapper for malloc which can be used in this
/*
*
* Permission to use, copy, modify, and distribute this software for any
* purpose with or without fee is hereby granted, provided that the above
* copyright notice and this permission notice appear in all copies.
*
* THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
* WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
* MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
* ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
* WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
* ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
* OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
*/
/*
* This is sqrt(SIZE_MAX+1), as s1*s2 <= SIZE_MAX
* if both s1 < MUL_NO_OVERFLOW and s2 < MUL_NO_OVERFLOW
*/
#define MUL_NO_OVERFLOW (1UL << (sizeof(size_t) * 4))
void *
mallocarray(size_t nmemb, size_t size, int type, int flags)
{
if ((nmemb >= MUL_NO_OVERFLOW || size >= MUL_NO_OVERFLOW) &&
nmemb > 0 && SIZE_MAX / nmemb < size) {
if (flags & M_CANFAIL)
return (NULL);
panic("mallocarray: overflow %zu * %zu", nmemb, size);
}
return (malloc(size * nmemb, type, flags));
}

Warner Losh

2016-02-11 21:36:51 UTC

Post by C Turt
I just wanted to post some real world examples of bugs which could be
mitigated with `mallocarray` to attract more interest.

Letâs play devilâs advocate: since you have to make code changes, how
would mallocarray() be superior to the various MALLOC_OVERFLOW
macro suggestions from earlier in the thread? Given that kernel code is
somewhat different in what it needs to support?

Post by C Turt
My most meritable example of a real world attack from this behaviour would
be the sys_dynlib_prepare_dlclose kernel exploit for PS4 (PS4 OS is based
http://cturt.github.io/dlclose-overflow.html
The significance of this example is that if a `mallocarray` wrapper was
available, and used here, the bug would not have been exploitable, because
it would have intentionally panicked instead of continuing with an under
allocated buffer.

Except that youâd need to change all the code that was imported into
the kernel to use mallocarray. The code Sony imported didnât have it
to start with.

Post by C Turt
You may think that this is clearly Sony's fault for not checking the count
at all, and that FreeBSD kernel code would never have a bug like this,
which is why I would like to mention that similar overflows can be possible
even if there initially appear to be sufficient bound checks performed.
There are several pieces of vulnerable code present in FreeBSD kernel
(albeit most of them are triggerable only as root so are not critical),
however I will use the file `/sys/kern/kern_alq.c` to demonstrate. There
[CODE]int
alq_open(struct alq **alqp, const char *file, struct ucred *cred, int cmode,
int size, int count)
{
int ret;
KASSERT((count >= 0), ("%s: count < 0", __func__));
if (count > 0) {
if ((ret = alq_open_flags(alqp, file, cred, cmode,
size*count, 0)) == 0) {
(*alqp)->aq_flags |= AQ_LEGACY;
(*alqp)->aq_entmax = count;
(*alqp)->aq_entlen = size;
}
...
int
alq_open_flags(struct alq **alqp, const char *file, struct ucred *cred, int
cmode,
int size, int flags)
{
...
KASSERT((size > 0), ("%s: size <= 0", __func__));
...
alq->aq_buflen = size;
...
alq->aq_entbuf = malloc(alq->aq_buflen, M_ALD, M_WAITOK|M_ZERO);[/CODE]
The check on `count` being greater than or equal to 0 in `alq_open`, and
the check for `size` being greater than 0 in `alq_open_flags` are cute, but
they don't check for an overflow of `size*count`.
This code path is reachable in several places, such as
[CODE]static int
sysctl_debug_ktr_alq_enable(SYSCTL_HANDLER_ARGS)
{
...
error = alq_open(&ktr_alq, (const char *)ktr_alq_file,
req->td->td_ucred, ALQ_DEFAULT_CMODE,
sizeof(struct ktr_entry), ktr_alq_depth);
[/CODE]
[CODE]SYSCTL_INT(_debug_ktr, OID_AUTO, alq_depth, CTLFLAG_RW,
&ktr_alq_depth, 0, "Number of items in the write buffer");[/CODE]
`sizeof(struct ktr_entry)` is 88 bytes. So theoretically if `ktr_alq_depth`
is set to `48806447`, we'll get an allocation of `0x100000028`, which
truncates to 0x28 = 40 bytes. A heap overflow would then possible when this
buffer is iterated over with `aq_entmax` and `aq_entlen`.

These are all good finds. And they are all mitigable with the MALLOC_OVERFLOW
macro that was suggested earlier in this thread. Given the unique demands of the
kernel, why should that not be the preferred method of dealing with this stuff?

Warner

_______________________________________________
https://lists.freebsd.org/mailman/listinfo/freebsd-arch

C Turt

2016-02-13 09:18:26 UTC

"Except that you’d need to change all the code that was imported into
the kernel to use mallocarray. The code Sony imported didn’t have it
to start with."

Although most of the PS4 dynamic linker is taken from userland FreeBSD
rtld-elf, the particular system call which contains the overflow,
sys_dynlib_prepare_dlclose, is a Sony extension which was not imported and
so would have been written from scratch with the intention of being kernel
code. Hence, I continue to believe that if it was common practice to use
mallocarray in the kernel, it would likely have been used here.

"These are all good finds. And they are all mitigable with the
MALLOC_OVERFLOW
macro that was suggested earlier in this thread. Given the unique demands
of the
kernel, why should that not be the preferred method of dealing with this
stuff?"

You are absolutely right that macros like MALLOC_OVERFLOW should be the
preferred way of catching integer overflows, and dealing with them
appropriately according to the unique context where the overflow occurs. My
intention isn't to remove checks and rely on mallocarray to deal with them,
it is to have both, such that only if the initial checks are faulty they
will be caught in mallocarray, where the system should then intentionally
chose to panic rather than continue, leading to a probable heap overflow.

The problem I have is that certain parts of FreeBSD kernel flat out don't
live up to FreeBSD's reputation of having clean code written with security
in mind. Look at `huft_build` from `sys/kern/inflate.c`, this has to be the
ugliest function in the whole of FreeBSD kernel, and there is an allocation
with the described pattern:

if ((q = (struct huft *) malloc((z + 1) * sizeof(struct huft), M_GZIP,
M_WAITOK)) ==
(struct huft *) NULL) {

What's more, this code has a history of containing vulnerabilities (
https://www.freebsd.org/security/advisories/FreeBSD-SA-06:21.gzip.asc and
CVE-2009-2624).

`z + 1` should be, and probably is, guaranteed by this code to be within
appropriate bounds. However, my proposal is that pieces of code like this
should be replaced with `mallocarray` so that there is absolutely no way
that this can ever overflow from the multiplication at least.

Although there are many other ways that an allocation like this could
potentially be vulnerable: overflowing from the `+ 1`, or the count being
raced attacked if it wasn't a stack variable, for example, I believe that
using `mallocarray` would be an excellent start in pro-actively increasing
the security and code quality of the FreeBSD kernel.

Post by C Turt
I just wanted to post some real world examples of bugs which could be
mitigated with `mallocarray` to attract more interest.

Let’s play devil’s advocate: since you have to make code changes, how
would mallocarray() be superior to the various MALLOC_OVERFLOW
macro suggestions from earlier in the thread? Given that kernel code is
somewhat different in what it needs to support?

Post by C Turt
My most meritable example of a real world attack from this behaviour

would

Post by C Turt
be the sys_dynlib_prepare_dlclose kernel exploit for PS4 (PS4 OS is based
http://cturt.github.io/dlclose-overflow.html
The significance of this example is that if a `mallocarray` wrapper was
available, and used here, the bug would not have been exploitable,

because

Post by C Turt
it would have intentionally panicked instead of continuing with an under
allocated buffer.

Except that you’d need to change all the code that was imported into
the kernel to use mallocarray. The code Sony imported didn’t have it
to start with.

Post by C Turt
You may think that this is clearly Sony's fault for not checking the

count

Post by C Turt
at all, and that FreeBSD kernel code would never have a bug like this,
which is why I would like to mention that similar overflows can be

possible

Post by C Turt
even if there initially appear to be sufficient bound checks performed.
There are several pieces of vulnerable code present in FreeBSD kernel
(albeit most of them are triggerable only as root so are not critical),
however I will use the file `/sys/kern/kern_alq.c` to demonstrate. There
[CODE]int
alq_open(struct alq **alqp, const char *file, struct ucred *cred, int

cmode,

Post by C Turt
int size, int count)
{
int ret;
KASSERT((count >= 0), ("%s: count < 0", __func__));
if (count > 0) {
if ((ret = alq_open_flags(alqp, file, cred, cmode,
size*count, 0)) == 0) {
(*alqp)->aq_flags |= AQ_LEGACY;
(*alqp)->aq_entmax = count;
(*alqp)->aq_entlen = size;
}
...
int
alq_open_flags(struct alq **alqp, const char *file, struct ucred *cred,

int

Post by C Turt
cmode,
int size, int flags)
{
...
KASSERT((size > 0), ("%s: size <= 0", __func__));
...
alq->aq_buflen = size;
...
alq->aq_entbuf = malloc(alq->aq_buflen, M_ALD, M_WAITOK|M_ZERO);[/CODE]
The check on `count` being greater than or equal to 0 in `alq_open`, and
the check for `size` being greater than 0 in `alq_open_flags` are cute,

but

Post by C Turt
they don't check for an overflow of `size*count`.
This code path is reachable in several places, such as
[CODE]static int
sysctl_debug_ktr_alq_enable(SYSCTL_HANDLER_ARGS)
{
...
error = alq_open(&ktr_alq, (const char *)ktr_alq_file,
req->td->td_ucred, ALQ_DEFAULT_CMODE,
sizeof(struct ktr_entry), ktr_alq_depth);
[/CODE]
[CODE]SYSCTL_INT(_debug_ktr, OID_AUTO, alq_depth, CTLFLAG_RW,
&ktr_alq_depth, 0, "Number of items in the write buffer");[/CODE]
`sizeof(struct ktr_entry)` is 88 bytes. So theoretically if

`ktr_alq_depth`

Post by C Turt
is set to `48806447`, we'll get an allocation of `0x100000028`, which
truncates to 0x28 = 40 bytes. A heap overflow would then possible when

this

Post by C Turt
buffer is iterated over with `aq_entmax` and `aq_entlen`.

These are all good finds. And they are all mitigable with the
MALLOC_OVERFLOW
macro that was suggested earlier in this thread. Given the unique demands of the
kernel, why should that not be the preferred method of dealing with this stuff?
Warner

user,

Post by C Turt
this allocation can easily overflow, resulting in a heap overflow later

on.

Post by C Turt
The mallocarray is a wrapper for malloc which can be used in this
/*
*
* Permission to use, copy, modify, and distribute this software for any
* purpose with or without fee is hereby granted, provided that the above
* copyright notice and this permission notice appear in all copies.
*
* THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL

WARRANTIES

Post by C Turt
* WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
* MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE

FOR

Post by C Turt
* ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
* WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
* ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT

Post by C Turt
* OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
*/
/*
* This is sqrt(SIZE_MAX+1), as s1*s2 <= SIZE_MAX
* if both s1 < MUL_NO_OVERFLOW and s2 < MUL_NO_OVERFLOW
*/
#define MUL_NO_OVERFLOW (1UL << (sizeof(size_t) * 4))
void *
mallocarray(size_t nmemb, size_t size, int type, int flags)
{
if ((nmemb >= MUL_NO_OVERFLOW || size >= MUL_NO_OVERFLOW) &&
nmemb > 0 && SIZE_MAX / nmemb < size) {
if (flags & M_CANFAIL)
return (NULL);
panic("mallocarray: overflow %zu * %zu", nmemb, size);
}
return (malloc(size * nmemb, type, flags));
}

_______________________________________________
https://lists.freebsd.org/mailman/listinfo/freebsd-arch

Warner Losh

2016-02-14 06:03:28 UTC

Post by C Turt
"Except that you’d need to change all the code that was imported into
the kernel to use mallocarray. The code Sony imported didn’t have it
to start with."
Although most of the PS4 dynamic linker is taken from userland FreeBSD
rtld-elf, the particular system call which contains the overflow,
sys_dynlib_prepare_dlclose, is a Sony extension which was not imported and
so would have been written from scratch with the intention of being kernel
code. Hence, I continue to believe that if it was common practice to use
mallocarray in the kernel, it would likely have been used here.
"These are all good finds. And they are all mitigable with the
MALLOC_OVERFLOW
macro that was suggested earlier in this thread. Given the unique demands of the
kernel, why should that not be the preferred method of dealing with this
stuff?"
You are absolutely right that macros like MALLOC_OVERFLOW should be the
preferred way of catching integer overflows, and dealing with them
appropriately according to the unique context where the overflow occurs. My
intention isn't to remove checks and rely on mallocarray to deal with them,
it is to have both, such that only if the initial checks are faulty they
will be caught in mallocarray, where the system should then intentionally
chose to panic rather than continue, leading to a probable heap overflow.

We're already seeing places in the kernel where extra cycles being
uselessly consumed are interfering with performance needed to get to
100Gbps off disks and out the network port. While these code paths are
unlikely to have a malloc in them (since they've been optimized in the push
for 10Gbps and 40Gbps), extra, redundant checks, mindlessly applied
throughout the kernel likely aren't the right answer either.

Post by C Turt
The problem I have is that certain parts of FreeBSD kernel flat out don't
live up to FreeBSD's reputation of having clean code written with security
in mind. Look at `huft_build` from `sys/kern/inflate.c`, this has to be the
ugliest function in the whole of FreeBSD kernel, and there is an allocation
if ((q = (struct huft *) malloc((z + 1) * sizeof(struct huft), M_GZIP,
M_WAITOK)) ==
(struct huft *) NULL) {
What's more, this code has a history of containing vulnerabilities (
https://www.freebsd.org/security/advisories/FreeBSD-SA-06:21.gzip.asc and
CVE-2009-2624).
`z + 1` should be, and probably is, guaranteed by this code to be within
appropriate bounds. However, my proposal is that pieces of code like this
should be replaced with `mallocarray` so that there is absolutely no way
that this can ever overflow from the multiplication at least.

I still maintain that a check before this, or as Ed Shouten has pointed
out, using an API that can do the multiplication and report overflow using
the CPU facilities to do so would be a much better API, we'd address the
performance issues I'm worried about.

Post by C Turt
Although there are many other ways that an allocation like this could
potentially be vulnerable: overflowing from the `+ 1`, or the count being
raced attacked if it wasn't a stack variable, for example, I believe that
using `mallocarray` would be an excellent start in pro-actively increasing
the security and code quality of the FreeBSD kernel.

I've still not seen an argument why this method is superior to the ones
outlined by Bruce Evans or Ed Shouten. You have to change the code anyway,
it would make more sense to make sure that your changes reflect what you
are doing, rather than add an obfuscating function to the mix with a poor
API for the kernel.

Warner

Post by C Turt
I just wanted to post some real world examples of bugs which could be
mitigated with `mallocarray` to attract more interest.

Post by C Turt
My most meritable example of a real world attack from this behaviour

would

Post by C Turt
be the sys_dynlib_prepare_dlclose kernel exploit for PS4 (PS4 OS is

based

Post by C Turt
http://cturt.github.io/dlclose-overflow.html
The significance of this example is that if a `mallocarray` wrapper was
available, and used here, the bug would not have been exploitable,

because

Post by C Turt
it would have intentionally panicked instead of continuing with an under
allocated buffer.

Except that you’d need to change all the code that was imported into
the kernel to use mallocarray. The code Sony imported didn’t have it
to start with.

Post by C Turt
You may think that this is clearly Sony's fault for not checking the

count

Post by C Turt
at all, and that FreeBSD kernel code would never have a bug like this,
which is why I would like to mention that similar overflows can be

possible

cmode,

int

Post by C Turt
cmode,
int size, int flags)
{
...
KASSERT((size > 0), ("%s: size <= 0", __func__));
...
alq->aq_buflen = size;
...
alq->aq_entbuf = malloc(alq->aq_buflen, M_ALD,

M_WAITOK|M_ZERO);[/CODE]

Post by C Turt
The check on `count` being greater than or equal to 0 in `alq_open`, and
the check for `size` being greater than 0 in `alq_open_flags` are cute,

but

Post by C Turt
they don't check for an overflow of `size*count`.
This code path is reachable in several places, such as
[CODE]static int
sysctl_debug_ktr_alq_enable(SYSCTL_HANDLER_ARGS)
{
...
error = alq_open(&ktr_alq, (const char *)ktr_alq_file,
req->td->td_ucred, ALQ_DEFAULT_CMODE,
sizeof(struct ktr_entry), ktr_alq_depth);
[/CODE]
With `ktr_alq_depth` being controllable from userland (but only as
[CODE]SYSCTL_INT(_debug_ktr, OID_AUTO, alq_depth, CTLFLAG_RW,
&ktr_alq_depth, 0, "Number of items in the write buffer");[/CODE]
`sizeof(struct ktr_entry)` is 88 bytes. So theoretically if

`ktr_alq_depth`

Post by C Turt
is set to `48806447`, we'll get an allocation of `0x100000028`, which
truncates to 0x28 = 40 bytes. A heap overflow would then possible when

this

Post by C Turt
buffer is iterated over with `aq_entmax` and `aq_entlen`.

These are all good finds. And they are all mitigable with the
MALLOC_OVERFLOW
macro that was suggested earlier in this thread. Given the unique demands of the
kernel, why should that not be the preferred method of dealing with this stuff?
Warner

user,

Post by C Turt
this allocation can easily overflow, resulting in a heap overflow

later on.

above

Post by C Turt
* copyright notice and this permission notice appear in all copies.
*
* THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL

WARRANTIES

Post by C Turt
* WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
* MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE

FOR

Post by C Turt
* ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY

DAMAGES

Post by C Turt
* WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
* ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT

_______________________________________________
https://lists.freebsd.org/mailman/listinfo/freebsd-arch

Ed Schouten

2016-02-13 13:21:39 UTC

Hi there,

Post by C Turt
if ((nmemb >= MUL_NO_OVERFLOW || size >= MUL_NO_OVERFLOW) &&
nmemb > 0 && SIZE_MAX / nmemb < size) {

In my opinion functions like these are good additions, as long as we
make sure that we stop importing garbage expressions like the one
above. It's already bad enough that we copy-pasted this gobbledygook
into fread(), fwrite(), calloc(), reallocarray(), etc.

Both the latest versions of Clang and GCC support the following builtins:

bool __builtin_add_overflow(type1 a, type2 b, type3 *res);
bool __builtin_sub_overflow(type1 a, type2 b, type3 *res);
bool __builtin_mul_overflow(type1 a, type2 b, type3 *res);

These functions perform addition, subtraction and multiplication,
returning whether overflow has occurred in the process. This is a lot
more efficient (and readable) than the expression above, as it simply
uses the CPU's mul instruction, followed by a jump-on-overflow.

GCC 4.2.1 doesn't support these builtins, but they can easily be
emulated by using static inline functions that use the code above. If
we want them to be type generic, we can use <sys/cdefs.h>'s
__generic(), which either expands to C11's _Generic() or falls back to
GCC's __builtin_types_compatible_p()/__builtin_choose_expr().

I'd say it would make a lot of sense to add a new header file, e.g.
<sys/overflow.h>, that adds compiler-independent wrappers for these
builtins:

#if recent version of GCC/Clang
#define add_overflow(a, b, res) __builtin_add_overflow(a, b, res)
#else
#define add_overflow(a, b, res) (__generic(*(res), unsigned int, ...,
...)(a, b, res))
#endif

--
Ed Schouten <***@nuxi.nl>
Nuxi, 's-Hertogenbosch, the Netherlands
KvK-nr.: 62051717

Bruce Evans

2016-02-13 16:56:20 UTC

Post by Ed Schouten

Post by C Turt
if ((nmemb >= MUL_NO_OVERFLOW || size >= MUL_NO_OVERFLOW) &&
nmemb > 0 && SIZE_MAX / nmemb < size) {

This is a normal well written C expression. It uses a possibly-
excessive micro-optimization to avoid a possibly-slow division. It
is less general then my macro:

#define MALLOC_ARRAY_CHECK(num, size, limit) \
((size) == 0 || limit / (size) >= (num))

My macro shouldn't have MALLOC in its name, since its only relation to
malloc() is that it may be used for bounds checking related to using
malloc().

Post by Ed Schouten
bool __builtin_add_overflow(type1 a, type2 b, type3 *res);
bool __builtin_sub_overflow(type1 a, type2 b, type3 *res);
bool __builtin_mul_overflow(type1 a, type2 b, type3 *res);
These functions perform addition, subtraction and multiplication,
returning whether overflow has occurred in the process. This is a lot
more efficient (and readable) than the expression above, as it simply
uses the CPU's mul instruction, followed by a jump-on-overflow.

Using these functions is gives undefined behaviour. They are in the
implementation namespace and are not documented in any installed
documentation for clang (maybe in info for gcc?). This is a slightly
less efficient and slightly less readable than the first expression
above if the implementation is as you describe. The micro-optimization
in the first expression does work and results in no division in most
cases. It usually takes 2 comparisons and 2 branches instead of 1
multiplication, 1 comparison and 1 branch. The extra comparison is
probably faster than the multiplication unless multiplication takes
only 1 cycle. The compiler might actually actually convert each version
to the other if the version with the multiplication is faster. Or
better, to the in-between version with 2 comparisons and the division
reduced to multiplications.

My macro is more general than this. It allows an arbitrary limit, but
the builtins only check for the overflow threshold. Checks for malloc()
in the kernel always need to use a limit much smaller than the overflow
threshold.

The version in fread.c actually has a further micro-optimizations which
you don't like and style bugs which I don't like:

X /*
X * Check for integer overflow. As an optimization, first check that
X * at least one of {count, size} is at least 2^16, since if both
X * values are less than that, their product can't possible overflow
X * (size_t is always at least 32 bits on FreeBSD).
X */
X if (((count | size) > 0xFFFF) &&
X (count > SIZE_MAX / size)) {

(size != 0 has already been checked for.)

This manually reduces the 2 comparisons and 2 branches to 1 OR, 1 comparison
and 1 branch. Well, I don't like this either. The compiler can do this
strength reduction much more easily than the mul/div ones if it (either
the optimization or the compiler) is any good. It micro-optimization gives
one of the style bugs (a verbose comment to explain it, and duplicating this
comment. The other style bugs are excessive parentheses and unnecessary
line splitting.

Bruce

Warner Losh

2016-02-14 05:53:56 UTC