holywar: malloc() vs. OOM

holywar: malloc() vs. OOM

[Vasiliy Kulikov]

Rich,

This is more a question about your malloc() failure policy for musl than
an actual proposal.

When brk() or mmap() fails, libc usually returns NULL to the program.
If the program wants to gracefully handle OOM, it may do it.  If not, it
will likely generate SIGSEGV and will be killed without any problem.

However, there are potential issues with this behaviour:

1) If the program doesn't handle OOM at all, it can lead to security
problems.

 a) if NULL page is not mmap'ed (the case of all nonroot apps and most
of root apps), the page starting from vm.mmap_min_addr still may present
in the process' vm.  For some distros only one page was guarded this way
in the past.  So, if the allocation is bigger than ~4-64kb, and the
write begins from the end of the page, then some bad things may happen
before SIGSEGV (the worst case is privilege escalation).  This is a
patological case, I didn't see such cases myself, but it's possible in
theory.

 b) if NULL page is mmap'ed, the application might not identify OOM at
all as the page is mmap'ed and SIGSEGV is not sent.  (Yes, apps mmap'ing
NULL page must handle OOM, but see (2).)

2) If the program handle OOM, it might do it very bad way.  The OOM
handling code path is almost always not tested and contain bugs.  Even the
kernel, which obviously must handle OOM, doesn't properly handle it
(I found bugs in OOM handling code much more often than in other error
handling code) because this code is not tested.  DBUS daemon, which is
closely connected with init in modern distros, must not fail on OOM by
design (otherwise init would fail and the whole system would
hang/reboot), and it took much time to remove silent bugs in this code:

(http://blog.ometer.com/2008/02/04/out-of-memory-handling-d-bus-experience/)


In theory, these are bugs of applications and not of libc, and they
should be fully handled in programs, not in libc.  Period.

But looking at the problem from the pragmatic point of view we'll see
that libc is actually the easiest place where the problem may be 
workarounded (not fixed, surely).  The workaround would be simply
raising SIGKILL if malloc() fails (either because of brk() or mmap()).
For the rare programs craving to handle OOM such code should be used:

#define _OOM_MAY_FAIL_
#include <stdlib.h>

Then the workaround is disabled.


Probably I overestimate the importance of OOM errors, and (1) in
particular.   However, I think it is worth discussing.


Thanks,

-- 
Vasiliy

Re: holywar: malloc() vs. OOM

[Rich Felker]

On Sun, Jul 24, 2011 at 02:33:25PM +0400, Vasiliy Kulikov wrote:
> Rich,
> 
> This is more a question about your malloc() failure policy for musl than
> an actual proposal.
> 
> [...]
> 
> In theory, these are bugs of applications and not of libc, and they
> should be fully handled in programs, not in libc.  Period.
> 
> But looking at the problem from the pragmatic point of view we'll see
> that libc is actually the easiest place where the problem may be 
> workarounded (not fixed, surely).  The workaround would be simply
> raising SIGKILL if malloc() fails (either because of brk() or mmap()).
> For the rare programs craving to handle OOM such code should be used:

This is absolutely wrong and non-conformant. It will also ruin all
robust programs and result in massive data loss, deadlock with shared
locks due to failure to release locks before termination, and all
sorts of ills. It also creates trivial DoS opportunities; for example
you could kill a daemon that uses glob() simply by passing it a glob
expression that matches millions or billions of files. (It may be a
bad idea, from a load standpoint, to be using glob in a daemon, but it
should simply result in high load then failure, not crashing.)

> #define _OOM_MAY_FAIL_
> #include <stdlib.h>
> 
> Then the workaround is disabled.

Being broken by default is not acceptable to me. The other way around
could be acceptable, but I'm very doubtful that it would fix any
real-world bugs. The modern mmap min address is very high, and it's
quite rare for apps to access the end of their allocation before the
beginning anyway. The only common situation I can think of where it
might happen to initially access a high offset first is when calling
glibc's memcpy which sometimes chooses to copy backwards. musl's
memcpy does not take this liberty, even if it might be faster in some
cases, for that very reason - it's dangerous to access high offsets
first if a program was not careful about checking the return value of
malloc.

A better solution might be to have a gcc option to generate a read
from the base address the first time a function performs arithmetic on
a pointer it has not already checked. This is valid because the C
language does not allow pointer arithmetic to cross object boundaries,
and this approach could be made 100% correct rather than being a
heuristic that breaks correct applications. It would impose some
performance cost, but I doubt it would be high. (Note: Some special
handling might be required for "one past the end of an array" pointers
here. I'd have to think a bit longer to work out the details but I
think it's possible to handle them safely in a similar way.)

> Probably I overestimate the importance of OOM errors, and (1) in
> particular.   However, I think it is worth discussing.

I don't think you overestimate the importance of OOM errors. Actually
Linux desktop is full of OOM errors that ruin usability, like file
managers that hang the system for 5 minutes then crash if you navigate
to a directory with a 15000x15000 image file. Unfortunately I don't
think it's possible to fix at the libc level, and fixing the worst
issues (DoS from apps crashing when they should not crash) usually
involves both sanity-checking the size prior to calling malloc *and*
checking the return value of malloc...

BTW great subject line! :-)

Rich

Re: holywar: malloc() vs. OOM

[Szabolcs Nagy]

* Vasiliy Kulikov <segoon@openwall.com> [2011-07-24 14:33:25 +0400]:
> When brk() or mmap() fails, libc usually returns NULL to the program.

i thought that was a requirement in the standard

how else can one handle such failures?

Re: holywar: malloc() vs. OOM

[Szabolcs Nagy]

* Szabolcs Nagy <nsz@port70.net> [2011-07-24 14:44:18 +0200]:
> 
> how else can one handle such failures?

nevermind
i failed to read the mail until the end

Re: holywar: malloc() vs. OOM

[Rich Felker]

On Sun, Jul 24, 2011 at 03:29:14PM +0200, Szabolcs Nagy wrote:
> > > Probably I overestimate the importance of OOM errors, and (1) in
> > > particular.   However, I think it is worth discussing.
> > 
> > I don't think you overestimate the importance of OOM errors. Actually
> > Linux desktop is full of OOM errors that ruin usability, like file
> > managers that hang the system for 5 minutes then crash if you navigate
> > to a directory with a 15000x15000 image file. Unfortunately I don't
> > think it's possible to fix at the libc level, and fixing the worst
> > issues (DoS from apps crashing when they should not crash) usually
> > involves both sanity-checking the size prior to calling malloc *and*
> > checking the return value of malloc...
> 
> what about providing an alternative libc or libcwrapper api

I think this is definitely possible, probably just via
-I/path/to/alt/stdlib/h and some inline code and macros in the
stdlib.h there, along with #include_next <stdlib.h>, and it probably
doesn't really need cooperation with libc (i.e. if it's written
cleanly enough it would probably work with most libcs.

> it could "fix" deprecated/dangerous calls
> (maybe turn them into compiletime errors)
> and things like oom failures into runtime errors
> 
> so bad code can be compiled against this radical extremist libc

The only problem I see is that it only catches "known bad" code. As an
admin I would be inclined to simply look for another program that
performs the function I need, rather than trying to compile in
workarounds, if I knew a program had code that bad..

Rich

Re: holywar: malloc() vs. OOM

[Szabolcs Nagy]

* Rich Felker <dalias@aerifal.cx> [2011-07-24 08:40:34 -0400]:
> On Sun, Jul 24, 2011 at 02:33:25PM +0400, Vasiliy Kulikov wrote:
> > But looking at the problem from the pragmatic point of view we'll see
> > that libc is actually the easiest place where the problem may be 
> > workarounded (not fixed, surely).  The workaround would be simply
> > raising SIGKILL if malloc() fails (either because of brk() or mmap()).
> > For the rare programs craving to handle OOM such code should be used:
> 
> This is absolutely wrong and non-conformant. It will also ruin all


> A better solution might be to have a gcc option to generate a read
> from the base address the first time a function performs arithmetic on
> a pointer it has not already checked. This is valid because the C

sounds reasonable

> > Probably I overestimate the importance of OOM errors, and (1) in
> > particular.   However, I think it is worth discussing.
> 
> I don't think you overestimate the importance of OOM errors. Actually
> Linux desktop is full of OOM errors that ruin usability, like file
> managers that hang the system for 5 minutes then crash if you navigate
> to a directory with a 15000x15000 image file. Unfortunately I don't
> think it's possible to fix at the libc level, and fixing the worst
> issues (DoS from apps crashing when they should not crash) usually
> involves both sanity-checking the size prior to calling malloc *and*
> checking the return value of malloc...

what about providing an alternative libc or libcwrapper api

it could "fix" deprecated/dangerous calls
(maybe turn them into compiletime errors)
and things like oom failures into runtime errors

so bad code can be compiled against this radical extremist libc

i guess for now running code under valgrind can catch most
of these issues..

Re: holywar: malloc() vs. OOM

[Vasiliy Kulikov]

Rich,

On Sun, Jul 24, 2011 at 08:40 -0400, Rich Felker wrote:
> On Sun, Jul 24, 2011 at 02:33:25PM +0400, Vasiliy Kulikov wrote:
> > Rich,
> > 
> > This is more a question about your malloc() failure policy for musl than
> > an actual proposal.
> > 
> > [...]
> > 
> > In theory, these are bugs of applications and not of libc, and they
> > should be fully handled in programs, not in libc.  Period.
> > 
> > But looking at the problem from the pragmatic point of view we'll see
> > that libc is actually the easiest place where the problem may be 
> > workarounded (not fixed, surely).  The workaround would be simply
> > raising SIGKILL if malloc() fails (either because of brk() or mmap()).
> > For the rare programs craving to handle OOM such code should be used:
> 
> This is absolutely wrong and non-conformant. It will also ruin all
> robust programs and result in massive data loss, deadlock with shared
> locks due to failure to release locks before termination, and all
> sorts of ills.

Oh, I forgot one major detail - the kernel by default have memory
overcommit enabled (sysctl vm.overcommit_memory=0).  It means that even
root owned program may be killed by OOM killer in case of system global
OOM :-)  There are procfs adjustments for such processes, but the
history shows that OOM killer logic is often somehow unexpected (if not
broken).  Also it was rewritten almost from scratch in the latest
kernels, so I'd expect new bugs in it.

For overcommit disabled OOM graceful handling should be possible, but
I'm not sure it is _guaranteed_ that memory allocated by brk() and
mmap() will be really available in the future.

So, yes, if the program guarantees that it gracefully handle OOM *for
sure*, then the workaround is indeed a breakage.  But I'm sure such
programs are hell rare.  BTW, do you know such programs, except DBUS? :)


> The only common situation I can think of where it
> might happen to initially access a high offset first is when calling
> glibc's memcpy which sometimes chooses to copy backwards. musl's
> memcpy does not take this liberty, even if it might be faster in some
> cases, for that very reason - it's dangerous to access high offsets
> first if a program was not careful about checking the return value of
> malloc.

Also the program/libs might (re)implement such functions for the
performance gain.


> A better solution might be to have a gcc option to generate a read
> from the base address the first time a function performs arithmetic on
> a pointer it has not already checked. This is valid because the C
> language does not allow pointer arithmetic to cross object boundaries,
> and this approach could be made 100% correct rather than being a
> heuristic that breaks correct applications.

A good idea.  It would be interesting to show actual numbers of the
slowdown.  However, most of the time it would be a slowdown for no
actual gain.

Thanks,

-- 
Vasiliy

Re: holywar: malloc() vs. OOM

[Vasiliy Kulikov]

On Sun, Jul 24, 2011 at 09:27 -0400, Rich Felker wrote:
> > it could "fix" deprecated/dangerous calls
> > (maybe turn them into compiletime errors)
> > and things like oom failures into runtime errors
> > 
> > so bad code can be compiled against this radical extremist libc
> 
> The only problem I see is that it only catches "known bad" code.

Sure, as almost any workaround of API misdesign.


> As an
> admin I would be inclined to simply look for another program that
> performs the function I need, rather than trying to compile in
> workarounds, if I knew a program had code that bad..

It depends on the requirements and level of paranoia :)  It could be the
only program in the required programs class.  It could be the only
program you may use for non-technical reasons.  Other programs could be
not much better (re: desktop).  In the ideal world any hardening would be
redundant ;)

-- 
Vasiliy

Re: holywar: malloc() vs. OOM

[Rich Felker]

On Sun, Jul 24, 2011 at 10:25:33PM +0400, Vasiliy Kulikov wrote:
> Oh, I forgot one major detail - the kernel by default have memory
> overcommit enabled (sysctl vm.overcommit_memory=0).  It means that even
> [...]
> For overcommit disabled OOM graceful handling should be possible, but
> I'm not sure it is _guaranteed_ that memory allocated by brk() and
> mmap() will be really available in the future.

Any system without this guarantee is a TOY, nothing more. I'm aware
that the default sucks, but that's not an excuse to break things for
competent admins who know how to fix the default...

> So, yes, if the program guarantees that it gracefully handle OOM *for
> sure*, then the workaround is indeed a breakage.  But I'm sure such
> programs are hell rare.  BTW, do you know such programs, except DBUS? :)

Pretty much any decent httpd, sshd, database, etc. should handle OOM
just fine - rejecting any connections for which the necessary
allocation fails. Having the daemon crash and not accept further
connections after the OOM condition is over would be very bad
behavior. Of course DJB liked writing software that way and using a
secondary daemon to restart his daemons when they crash, but that's
really unprofessional... and you can certainly come up with
applications where it would be very bad to have to restart when
somebody OOM'd it - a multiplayer game server comes to mind...

> > A better solution might be to have a gcc option to generate a read
> > from the base address the first time a function performs arithmetic on
> > a pointer it has not already checked. This is valid because the C
> > language does not allow pointer arithmetic to cross object boundaries,
> > and this approach could be made 100% correct rather than being a
> > heuristic that breaks correct applications.
> 
> A good idea.  It would be interesting to show actual numbers of the
> slowdown.  However, most of the time it would be a slowdown for no
> actual gain.

Actually it might be a speedup since it would act like a prefetch...
:)

Rich

Re: holywar: malloc() vs. OOM

[Rich Felker]

On Sun, Jul 24, 2011 at 10:33:41PM +0400, Vasiliy Kulikov wrote:
> > As an
> > admin I would be inclined to simply look for another program that
> > performs the function I need, rather than trying to compile in
> > workarounds, if I knew a program had code that bad..
> 
> It depends on the requirements and level of paranoia :)  It could be the
> only program in the required programs class.  It could be the only
> program you may use for non-technical reasons.  Other programs could be
> not much better (re: desktop).  In the ideal world any hardening would be
> redundant ;)

I think there's a big difference in *actual* *risk* between attempting
to harden a known-broken application to avoid getting stung by the
flaws, and hardening an application that's written with security in
mind. For instance OpenSSH's (or better yet vsftpd's) privsep model is
a form of hardening, but it's not a band-aid for known-bad code. It's
a second line of defense in case the primary line (good
security-conscious design and auditing) fails.

On the other hand, if you already *know* an application is full of
flaws that would lead to privilege elevation without some hardening,
it's reasonable to assume that's positively correlated with the
existence of other flaws the hardening won't protect you from...

Indeed there may be instances where you still need to run the buggy
software anyway (hopefully isolating it from the outside world as much
as possible and pre-screening any outside data it will be exposed to),
but I'd always look for other options first...

Rich

Re: holywar: malloc() vs. OOM

[Vasiliy Kulikov]

Rich,

On Sun, Jul 24, 2011 at 18:19 -0400, Rich Felker wrote:
> Any system without this guarantee is a TOY, nothing more. I'm aware
> that the default sucks,

I don't think the default sucks, it is just targeted to other programs.
Think about Java/Python programs, which request hundreds megabytes, but
using only tens of them.  Also daemons with fork() model being able to
handle hundreds/thousands connections actively using COW would not be
able to fully exploit COW potential.

-- 
Vasiliy

Re: holywar: malloc() vs. OOM

[Rich Felker]

On Mon, Jul 25, 2011 at 09:43:43PM +0400, Vasiliy Kulikov wrote:
> Rich,
> 
> On Sun, Jul 24, 2011 at 18:19 -0400, Rich Felker wrote:
> > Any system without this guarantee is a TOY, nothing more. I'm aware
> > that the default sucks,
> 
> I don't think the default sucks, it is just targeted to other programs.

I disagree. I think the default discourages writing safe, robust
applications (people always say "Why should I check the result of
malloc? It will return success then crash later anyway because of
overcommit.") and encourages writing broken hackware that depends on
the availability of overcommit.

> Think about Java/Python programs, which request hundreds megabytes, but
> using only tens of them.

This is not a valid way to write applications. It's basically the same
as the classic joke about Windows 95 containing:

    if (rand()%1000==42) bsod();

I'm also a bit unsure how a Java or Python program would allocate
hundreds of megs but leave them completely untouched. Usually HLL's
dirty memory as soon as they allocate it with initialization, object
construction, etc. so I'm doubtful your example has anything to do
with the real world...

> Also daemons with fork() model being able to
> handle hundreds/thousands connections actively using COW would not be
> able to fully exploit COW potential.

As long as the main daemon (prior to accepting connections) does not
use much memory, it's not an issue. If it is an issue, just throw in
an extra hard drive that's always spun down with a few TB of swap
space and the commit allowance will go through the roof.

Also, if you'll be calling exec after fork, posix_spawn is available
as an option. On a good implementation, it can/will use vfork or some
other clone variant to avoid increasing the commit charge in the
window between fork and exec.

Rich