OpenBSD mallocarray

classic Classic list List threaded Threaded
21 messages Options
12
Reply | Threaded
Open this post in threaded view
|

OpenBSD mallocarray

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
situations to detect an integer overflow before allocating:

/*
 * Copyright (c) 2008 Otto Moerbeek <[hidden email]>
 *
 * 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));
}
_______________________________________________
[hidden email] mailing list
https://lists.freebsd.org/mailman/listinfo/freebsd-arch
To unsubscribe, send any mail to "[hidden email]"
Reply | Threaded
Open this post in threaded view
|

Re: OpenBSD mallocarray

Conrad Meyer-2
On Mon, Feb 1, 2016 at 11:57 AM, C Turt <[hidden email]> wrote:
> 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.
>
> ...
>
> The mallocarray is a wrapper for malloc which can be used in this
> situations to detect an integer overflow before allocating:

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

Best,
Conrad
_______________________________________________
[hidden email] mailing list
https://lists.freebsd.org/mailman/listinfo/freebsd-arch
To unsubscribe, send any mail to "[hidden email]"
Reply | Threaded
Open this post in threaded view
|

Re: OpenBSD mallocarray

Ryan Stone-2
On Mon, Feb 1, 2016 at 3:16 PM, Conrad Meyer <[hidden email]> wrote:

>
> 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.
_______________________________________________
[hidden email] mailing list
https://lists.freebsd.org/mailman/listinfo/freebsd-arch
To unsubscribe, send any mail to "[hidden email]"
Reply | Threaded
Open this post in threaded view
|

Re: OpenBSD mallocarray

Mike Belopuhov
On Mon, Feb 01, 2016 at 15:56 -0500, Ryan Stone wrote:

> On Mon, Feb 1, 2016 at 3:16 PM, Conrad Meyer <[hidden email]> wrote:
>
> >
> > 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
_______________________________________________
[hidden email] mailing list
https://lists.freebsd.org/mailman/listinfo/freebsd-arch
To unsubscribe, send any mail to "[hidden email]"
Reply | Threaded
Open this post in threaded view
|

Re: OpenBSD mallocarray

Warner Losh

> On Feb 1, 2016, at 2:02 PM, Mike Belopuhov <[hidden email]> wrote:
>
> On Mon, Feb 01, 2016 at 15:56 -0500, Ryan Stone wrote:
>> On Mon, Feb 1, 2016 at 3:16 PM, Conrad Meyer <[hidden email]> wrote:
>>
>>>
>>> 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).
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


signature.asc (859 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: OpenBSD mallocarray

Conrad Meyer-2
On Mon, Feb 1, 2016 at 1:12 PM, Warner Losh <[hidden email]> wrote:

>
>> On Feb 1, 2016, at 2:02 PM, Mike Belopuhov <[hidden email]> wrote:
>> 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).
>
> 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().

> Arguments should be properly checked

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

> 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.

> 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.

Best,
Conrad
_______________________________________________
[hidden email] mailing list
https://lists.freebsd.org/mailman/listinfo/freebsd-arch
To unsubscribe, send any mail to "[hidden email]"
Reply | Threaded
Open this post in threaded view
|

Re: OpenBSD mallocarray

Brooks Davis-2
In reply to this post by Warner Losh
On Mon, Feb 01, 2016 at 02:12:20PM -0700, Warner Losh wrote:

>
> > On Feb 1, 2016, at 2:02 PM, Mike Belopuhov <[hidden email]> wrote:
> >
> > On Mon, Feb 01, 2016 at 15:56 -0500, Ryan Stone wrote:
> >> On Mon, Feb 1, 2016 at 3:16 PM, Conrad Meyer <[hidden email]> wrote:
> >>
> >>>
> >>> 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).
>
> 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

signature.asc (484 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: OpenBSD mallocarray

Warner Losh
In reply to this post by Conrad Meyer-2
On Mon, Feb 1, 2016 at 3:19 PM, Conrad Meyer <[hidden email]> wrote:

> On Mon, Feb 1, 2016 at 1:12 PM, Warner Losh <[hidden email]> wrote:
> >
> >> On Feb 1, 2016, at 2:02 PM, Mike Belopuhov <[hidden email]> wrote:
> >> 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).
> >
> > 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
_______________________________________________
[hidden email] mailing list
https://lists.freebsd.org/mailman/listinfo/freebsd-arch
To unsubscribe, send any mail to "[hidden email]"
Reply | Threaded
Open this post in threaded view
|

Re: OpenBSD mallocarray

Conrad Meyer-2
On Mon, Feb 1, 2016 at 2:49 PM, Warner Losh <[hidden email]> wrote:

> On Mon, Feb 1, 2016 at 3:19 PM, Conrad Meyer <[hidden email]> wrote:
>> On Mon, Feb 1, 2016 at 1:12 PM, Warner Losh <[hidden email]> wrote:
>> > 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.

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.

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

Agreed.

> 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.

> 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.

>> 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.

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.

> 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.

> 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
_______________________________________________
[hidden email] mailing list
https://lists.freebsd.org/mailman/listinfo/freebsd-arch
To unsubscribe, send any mail to "[hidden email]"
Reply | Threaded
Open this post in threaded view
|

Re: OpenBSD mallocarray

Warner Losh
In reply to this post by Brooks Davis-2
On Mon, Feb 1, 2016 at 3:48 PM, Brooks Davis <[hidden email]> wrote:

> On Mon, Feb 01, 2016 at 02:12:20PM -0700, Warner Losh wrote:
> >
> > > On Feb 1, 2016, at 2:02 PM, Mike Belopuhov <[hidden email]> wrote:
> > >
> > > On Mon, Feb 01, 2016 at 15:56 -0500, Ryan Stone wrote:
> > >> On Mon, Feb 1, 2016 at 3:16 PM, Conrad Meyer <[hidden email]> wrote:
> > >>
> > >>>
> > >>> 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).
> >
> > 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.
>

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
_______________________________________________
[hidden email] mailing list
https://lists.freebsd.org/mailman/listinfo/freebsd-arch
To unsubscribe, send any mail to "[hidden email]"
Reply | Threaded
Open this post in threaded view
|

Re: OpenBSD mallocarray

Brooks Davis-2
On Mon, Feb 01, 2016 at 04:01:14PM -0700, Warner Losh wrote:

> On Mon, Feb 1, 2016 at 3:48 PM, Brooks Davis <[hidden email]> wrote:
>
> > On Mon, Feb 01, 2016 at 02:12:20PM -0700, Warner Losh wrote:
> > >
> > > > On Feb 1, 2016, at 2:02 PM, Mike Belopuhov <[hidden email]> wrote:
> > > >
> > > > On Mon, Feb 01, 2016 at 15:56 -0500, Ryan Stone wrote:
> > > >> On Mon, Feb 1, 2016 at 3:16 PM, Conrad Meyer <[hidden email]> wrote:
> > > >>
> > > >>>
> > > >>> 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).
> > >
> > > 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.
> >
>
> 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.
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

signature.asc (484 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: OpenBSD mallocarray

Bruce Evans-4
In reply to this post by Warner Losh
_______________________________________________
[hidden email] mailing list
https://lists.freebsd.org/mailman/listinfo/freebsd-arch
To unsubscribe, send any mail to "[hidden email]"
Reply | Threaded
Open this post in threaded view
|

Re: OpenBSD mallocarray

John Baldwin
In reply to this post by Warner Losh
On Monday, February 01, 2016 04:01:14 PM Warner Losh wrote:

> On Mon, Feb 1, 2016 at 3:48 PM, Brooks Davis <[hidden email]> wrote:
>
> > On Mon, Feb 01, 2016 at 02:12:20PM -0700, Warner Losh wrote:
> > >
> > > > On Feb 1, 2016, at 2:02 PM, Mike Belopuhov <[hidden email]> wrote:
> > > >
> > > > On Mon, Feb 01, 2016 at 15:56 -0500, Ryan Stone wrote:
> > > >> On Mon, Feb 1, 2016 at 3:16 PM, Conrad Meyer <[hidden email]> wrote:
> > > >>
> > > >>>
> > > >>> 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).
> > >
> > > 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.
> >
>
> 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
_______________________________________________
[hidden email] mailing list
https://lists.freebsd.org/mailman/listinfo/freebsd-arch
To unsubscribe, send any mail to "[hidden email]"
Reply | Threaded
Open this post in threaded view
|

Re: OpenBSD mallocarray

Warner Losh
On Wed, Feb 3, 2016 at 12:39 PM, John Baldwin <[hidden email]> wrote:

> On Monday, February 01, 2016 04:01:14 PM Warner Losh wrote:
> > On Mon, Feb 1, 2016 at 3:48 PM, Brooks Davis <[hidden email]> wrote:
> >
> > > On Mon, Feb 01, 2016 at 02:12:20PM -0700, Warner Losh wrote:
> > > >
> > > > > On Feb 1, 2016, at 2:02 PM, Mike Belopuhov <[hidden email]>
> wrote:
> > > > >
> > > > > On Mon, Feb 01, 2016 at 15:56 -0500, Ryan Stone wrote:
> > > > >> On Mon, Feb 1, 2016 at 3:16 PM, Conrad Meyer <[hidden email]>
> wrote:
> > > > >>
> > > > >>>
> > > > >>> 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).
> > > >
> > > > 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.
> > >
> >
> > 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.
>

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


> 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.


> 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
_______________________________________________
[hidden email] mailing list
https://lists.freebsd.org/mailman/listinfo/freebsd-arch
To unsubscribe, send any mail to "[hidden email]"
Reply | Threaded
Open this post in threaded view
|

Re: OpenBSD mallocarray

C Turt
In reply to this 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.

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`.

On Mon, Feb 1, 2016 at 7:57 PM, C Turt <[hidden email]> wrote:

> 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
> situations to detect an integer overflow before allocating:
>
> /*
>  * Copyright (c) 2008 Otto Moerbeek <[hidden email]>
>  *
>  * 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));
> }
>
>
_______________________________________________
[hidden email] mailing list
https://lists.freebsd.org/mailman/listinfo/freebsd-arch
To unsubscribe, send any mail to "[hidden email]"
Reply | Threaded
Open this post in threaded view
|

Re: OpenBSD mallocarray

Warner Losh

> On Feb 11, 2016, at 2:21 PM, C Turt <[hidden email]> wrote:
>
> 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?

> 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.

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.

> 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`.
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


> On Mon, Feb 1, 2016 at 7:57 PM, C Turt <[hidden email]> wrote:
>
>> 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
>> situations to detect an integer overflow before allocating:
>>
>> /*
>> * Copyright (c) 2008 Otto Moerbeek <[hidden email]>
>> *
>> * 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));
>> }
>>
>>
> _______________________________________________
> [hidden email] mailing list
> https://lists.freebsd.org/mailman/listinfo/freebsd-arch
> To unsubscribe, send any mail to "[hidden email]"


signature.asc (859 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: OpenBSD mallocarray

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.

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.

On Thu, Feb 11, 2016 at 9:36 PM, Warner Losh <[hidden email]> wrote:

>
> > On Feb 11, 2016, at 2:21 PM, C Turt <[hidden email]> wrote:
> >
> > 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?
>
> > 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.
>
> 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.
>
> > 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`.
>
> 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
>
>
> > On Mon, Feb 1, 2016 at 7:57 PM, C Turt <[hidden email]> wrote:
> >
> >> 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
> >> situations to detect an integer overflow before allocating:
> >>
> >> /*
> >> * Copyright (c) 2008 Otto Moerbeek <[hidden email]>
> >> *
> >> * 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));
> >> }
> >>
> >>
> > _______________________________________________
> > [hidden email] mailing list
> > https://lists.freebsd.org/mailman/listinfo/freebsd-arch
> > To unsubscribe, send any mail to "[hidden email]"
>
>
_______________________________________________
[hidden email] mailing list
https://lists.freebsd.org/mailman/listinfo/freebsd-arch
To unsubscribe, send any mail to "[hidden email]"
Reply | Threaded
Open this post in threaded view
|

Re: OpenBSD mallocarray

Ed Schouten-6
In reply to this post by C Turt
Hi there,

2016-02-01 20:57 GMT+01:00 C Turt <[hidden email]>:
>     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 <[hidden email]>
Nuxi, 's-Hertogenbosch, the Netherlands
KvK-nr.: 62051717
_______________________________________________
[hidden email] mailing list
https://lists.freebsd.org/mailman/listinfo/freebsd-arch
To unsubscribe, send any mail to "[hidden email]"
Reply | Threaded
Open this post in threaded view
|

Re: OpenBSD mallocarray

Bruce Evans-4
On Sat, 13 Feb 2016, Ed Schouten wrote:

> 2016-02-01 20:57 GMT+01:00 C Turt <[hidden email]>:
>>     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.

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().

> 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.

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
_______________________________________________
[hidden email] mailing list
https://lists.freebsd.org/mailman/listinfo/freebsd-arch
To unsubscribe, send any mail to "[hidden email]"
Reply | Threaded
Open this post in threaded view
|

Re: OpenBSD mallocarray

Warner Losh
In reply to this post by Ed Schouten-6
On Sat, Feb 13, 2016 at 6:21 AM, Ed Schouten <[hidden email]> wrote:

> Hi there,
>
> 2016-02-01 20:57 GMT+01:00 C Turt <[hidden email]>:
> >     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
>

This actually makes a great deal of sense to me.

Warner
_______________________________________________
[hidden email] mailing list
https://lists.freebsd.org/mailman/listinfo/freebsd-arch
To unsubscribe, send any mail to "[hidden email]"
12