Fixing multithreaded set*id() AS-safety

Fixing multithreaded set*id() AS-safety

[Rich Felker]

Currently multithreaded set*id() functions fail to be AS-safe, despite
some of them being required to be AS-safe, due to the need for
locking. If they're called from a signal handler that interrupted
pthread_create or dlopen (or another set*id() function during a tiny
race window), attempting to obtain the lock (lock_ptc.c functions)
will deadlock. There are probably other ugly issues too.

I see two possible strategies for fixing this:

Strategy 1: Block signals during all uses of this lock to preclude the
possibility of a thread trying to take a lock it already holds. This
would mean adding signal blocking to dlopen (irrelevant to
performance) and pthread_create (a potentially serious cost). This
feels wrong since the common uses of this lock do not require
AS-safety; only the uncommon one (set*id() in a multithreaded program)
does. On the other hand, pthread_create already has to manipulate the
signal mask in some situations (priority attributes and when
pthread_create is called from a cancelled thread), and simply making
the signal masking and restoration unconditional would simplify the
code at the expense of some performance cost in the common cases. I
think some additional synchronization needs to be added to
pthread_exit for this strategy too, since the current logic seems to
have races where set*id() might deadlock due to miscounting thread
when racing with pthread_exit.

Strategy 2: Use the kernel, via /proc/self/task, to enumerate threads.
Multithreaded set*id() would have to fail on systems with /proc not
mounted or non-Linux systems that don't emulate /proc/self/task. The
benefit of this approach is that we can eliminate basically all need
for synchronization between important, performance-critical operations
(pthread_create and pthread_exist) and the ugly set*id() mess. The
only requirement seems to be ensuring that unboundedly many new
threads can't be created during set*id() (imagine a chain of threads
creating new threads and terminating, which reading /proc/self/task
might never catch up with), but this can easily be precluded with a
global flag that blocks forward progress in pthread_create (via a
futex wait) if it's set, and no synchronization would be required to
access the flag since it only needs to block unboundedly many new
threads. There may also be some complicated logic for handling threads
that exit after they're signaled but before the signal is delivered,
but I think it's doable.

Neither approach is really attractive. Strategy 1 feels less hackish
and more elegant (it actually makes the pthread_create code more
elegant than it is now by having fewer special cases), but the cost
feels wasteful. Strategy 2 is ugly but has the ugliness isolated to
synccall.c (the internals for set*id()) where it doesn't interact with
other parts of the code in any significant way.

Any opinions on which way we should go? I'll probably hold off to do
any of this until the next release cycle (or maybe even later), but I
want to go ahead and start thinking about and discussing it.

Rich

Re: Fixing multithreaded set*id() AS-safety

[Jens Gustedt]

[-- Attachment #1: Type: text/plain, Size: 1521 bytes --]

Hello

Am Freitag, den 19.12.2014, 22:39 -0500 schrieb Rich Felker:
> Neither approach is really attractive. Strategy 1 feels less hackish
> and more elegant (it actually makes the pthread_create code more
> elegant than it is now by having fewer special cases), but the cost
> feels wasteful. Strategy 2 is ugly but has the ugliness isolated to
> synccall.c (the internals for set*id()) where it doesn't interact with
> other parts of the code in any significant way.
> 
> Any opinions on which way we should go? I'll probably hold off to do
> any of this until the next release cycle (or maybe even later), but I
> want to go ahead and start thinking about and discussing it.

I am much more in favor of version 2 or something equivalent, because
it keeps the complexity where it belongs. As our implementation is
currently, all changes to pthread_create would equally impact
thrd_create.

C threads are an interface that knows nothing about unistd.h and that
is mean to be simple and efficient. A program that builds entirely on
C11 features to be portable will never use any of these, so the impact
of weird border cases from POSIX should be minimal, wherever we can
avoid it.

Jens


-- 
:: INRIA Nancy Grand Est ::: AlGorille ::: ICube/ICPS :::
:: ::::::::::::::: office Strasbourg : +33 368854536   ::
:: :::::::::::::::::::::: gsm France : +33 651400183   ::
:: ::::::::::::::: gsm international : +49 15737185122 ::
:: http://icube-icps.unistra.fr/index.php/Jens_Gustedt ::



[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 181 bytes --]

Re: Fixing multithreaded set*id() AS-safety

[Rich Felker]

On Sat, Dec 20, 2014 at 09:48:16AM +0100, Jens Gustedt wrote:
> Hello
> 
> Am Freitag, den 19.12.2014, 22:39 -0500 schrieb Rich Felker:
> > Neither approach is really attractive. Strategy 1 feels less hackish
> > and more elegant (it actually makes the pthread_create code more
> > elegant than it is now by having fewer special cases), but the cost
> > feels wasteful. Strategy 2 is ugly but has the ugliness isolated to
> > synccall.c (the internals for set*id()) where it doesn't interact with
> > other parts of the code in any significant way.
> > 
> > Any opinions on which way we should go? I'll probably hold off to do
> > any of this until the next release cycle (or maybe even later), but I
> > want to go ahead and start thinking about and discussing it.
> 
> I am much more in favor of version 2 or something equivalent, because
> it keeps the complexity where it belongs. As our implementation is
> currently, all changes to pthread_create would equally impact
> thrd_create.

I'm open to your view, but I don't think it follows from your
reasoning. Strategy 1 does not really add complexity to
pthread_create. It makes fewer special cases in pthread_create I
think. In effect what it's doing is just making the method of blocking
thread creation AS-safe.

Strategy 2 does add some code to pthread_create, but it just looks
like:

if (libc.block_new_threads) __wait(&libc.block_new_threads, 1, 1);

or similar. This mechanism could also be used by dlopen to block new
threads, freeing pthread_create from having to touch the __acquire_ptc
lock it does now, but since this eliminates the ability for dlopen to
wait for all threads to exit pthread_create, it would have to assume
all threads are currently in pthread_create and might be about to
create a new thread, and would thus have to pre-allocate twice the
needed amount of TLS. I'm not sure that would be a good trade-off...

Rich

Re: Fixing multithreaded set*id() AS-safety

[Rich Felker]

On Fri, Dec 19, 2014 at 10:39:18PM -0500, Rich Felker wrote:
> Strategy 2: Use the kernel, via /proc/self/task, to enumerate threads.
> Multithreaded set*id() would have to fail on systems with /proc not
> mounted or non-Linux systems that don't emulate /proc/self/task. The
> benefit of this approach is that we can eliminate basically all need
> for synchronization between important, performance-critical operations
> (pthread_create and pthread_exist) and the ugly set*id() mess. The
> only requirement seems to be ensuring that unboundedly many new
> threads can't be created during set*id() (imagine a chain of threads
> creating new threads and terminating, which reading /proc/self/task
> might never catch up with), but this can easily be precluded with a
> global flag that blocks forward progress in pthread_create (via a
> futex wait) if it's set, and no synchronization would be required to
> access the flag since it only needs to block unboundedly many new
> threads. There may also be some complicated logic for handling threads
> that exit after they're signaled but before the signal is delivered,
> but I think it's doable.

I think we _have_ to go with strategy 2 to guarantee a security
invariant I want: the impossibility of code sharing a memory space and
maintaining elevated privileged after setuid() has reported that
privileges were successfully dropped. With strategy 1 (and the current
code), __synccall happily ignores threads that have already "passed
the point of no return" in exiting; signaling them is impossible since
they've already blocked all signals, and may not even have a stack
anymore. But such a thread with elevated privileges is still
dangerous: while it's in this state, the unprivileged, post-setuid()
process could mmap() over top of the code it's running and thereby
execute arbitrary code with the elevated privileges which were
supposed to have been fully relinquished.

In order to avoid this issue, __synccall MUST ensure that it has
captured all kernel threads which are still part of the process (the
set of threads sharing memory). It's not enough to know that the
logical thread (from a userspace perspective) is dead.

This could be solved via the kernel's clearing of the tid futex when a
thread exits, but that would require having a reaper thread for
detached threads rather than having them unmap their own stacks, and
would impose lots of expensive bookkeeping and design constraints on
the implementation. I don't think that's remotely acceptable.

So we're left with the alternative: using /proc/self/task/ to observe
the set of live kernel threads. Unfortunately, this is not easy
either. I was actually almost to the point of ruling out strategy 2
because it's so hard.

What makes it hard is that we lack any good way to ensure that other
threads make forward progress. The thread calling set*id() has no way
to relinquish control until the signaled thread(s) respond, because it
doesn't even know there are any left to respond. It's possible that
all the threads it signaled were in the exiting state and exit before
they get the signal. So it has to keep re-scanning the list until it's
caught them all. However, if any threads have priority lower than the
signaling thread, they may never get a chance to run. Sleeping is the
only obvious way to let them run, but that's rather hideous and going
to be observably slow.

So here's the best alternative I came up with:

1. Pick any thread from /proc/self/task that hasn't yet responded yet,
   write its tid to a futex, and use FUTEX_LOCK_PI to donate priority
   to it. However (!) it's possible that the thread already exited and
   the tid was recycled to another process. So use a very short
   timeout so that, in this worst-case, we just get a minor slowdown
   if this (extremely rare) tid reuse race happens.

2. When a target thread gets the signal, it uses FUTEX_UNLOCK_PI to
   relinquish the donated priority and notify the signaling thread
   that it got the signal.

3. Repeat until there are no threads in the /proc/self/task list that
   haven't already been caught.

There should be a lot of opportunities to make this more efficient in
typical cases, e.g. just signaling all threads without any waiting
first and only doing the fancy stuff for threads that haven't already
responded.

Rich

Re: Fixing multithreaded set*id() AS-safety

[stephen Turner]

[-- Attachment #1: Type: text/plain, Size: 224 bytes --]

Does that require any special requirementd in the way of modules or
settings to use from the kernel? If proc doesnt exist what will happen? A
kernel panic, absence of threading or will it create the missing folders or
such?

[-- Attachment #2: Type: text/html, Size: 242 bytes --]

Re: Fixing multithreaded set*id() AS-safety

[Rich Felker]

On Sat, Jan 10, 2015 at 05:52:45PM -0500, stephen Turner wrote:
> Does that require any special requirementd in the way of modules or
> settings to use from the kernel? If proc doesnt exist what will happen? A
> kernel panic, absence of threading or will it create the missing folders or
> such?

No. As mentioned (I think) earlier, if /proc is not mounted,
multi-threaded set*id would not be able to work, but would just report
failure. Nothing would blow up. I'm not sure if it's a problem for
multi-threaded set*id not to work without /proc mounted, but in
general:

- Various functions in musl already require /proc to operate correctly
  because the kernel does not provide a way to do the necessary
  operations without /proc. Some of these are less arcane than
  multi-threaded set*id.

- It's rather a bad design to be calling setuid in a multi-threaded
  process to begin with; usually it happens only in Java or other
  "higher level" langs where you're calling out to setuid via some
  native interface and it's hard to prevent multiple threads from
  already existing at that point. These sorts of programs should not
  be running early boot before /proc is mounted.

If failure when /proc is not mounted is really a problem, I'm not sure
how we solve it. But in any case, I think we should start pushing for
the kernel to fix this issue properly: with a syscall that affects all
threads atomically, so that all this mess is used only as a fallback
for old kernels.

Rich

Re: Fixing multithreaded set*id() AS-safety

[stephen Turner]

[-- Attachment #1: Type: text/plain, Size: 1875 bytes --]

On Jan 10, 2015 11:07 PM, "Rich Felker" <dalias@libc.org> wrote:
>
> On Sat, Jan 10, 2015 at 05:52:45PM -0500, stephen Turner wrote:
> > Does that require any special requirementd in the way of modules or
> > settings to use from the kernel? If proc doesnt exist what will happen?
A
> > kernel panic, absence of threading or will it create the missing
folders or
> > such?
>
> No. As mentioned (I think) earlier, if /proc is not mounted,
> multi-threaded set*id would not be able to work, but would just report
> failure. Nothing would blow up. I'm not sure if it's a problem for
> multi-threaded set*id not to work without /proc mounted, but in
> general:
>
> - Various functions in musl already require /proc to operate correctly
>   because the kernel does not provide a way to do the necessary
>   operations without /proc. Some of these are less arcane than
>   multi-threaded set*id.
>
> - It's rather a bad design to be calling setuid in a multi-threaded
>   process to begin with; usually it happens only in Java or other
>   "higher level" langs where you're calling out to setuid via some
>   native interface and it's hard to prevent multiple threads from
>   already existing at that point. These sorts of programs should not
>   be running early boot before /proc is mounted.
>
> If failure when /proc is not mounted is really a problem, I'm not sure
> how we solve it. But in any case, I think we should start pushing for
> the kernel to fix this issue properly: with a syscall that affects all
> threads atomically, so that all this mess is used only as a fallback
> for old kernels.
>
> Rich

Thanks Rich for the details. You had mentioned it would fail but my
experience says that any failure leads to a system meltdown. Im not used to
failures not being the end of the world.

I include proc so for me theres no issue. I guess my devils advocate kicked
in.

[-- Attachment #2: Type: text/html, Size: 2302 bytes --]