Skip to contentSkip to conversation

Change in functionality of futex() system call.

DISCUSSION George Spelvin 5 participants 10 messages Jun 9, 2011

lore
Share & tools
lore
#0 lore raw

I'm not sure if it's best, but the risk of RO waiters interfering could be solved by giving them a lower prioirty for wakeup and always waking RW-mapped waiters first.

In most cases, there would only be one type of waiter, so this would have no effect, but if there were, a RO-mapped reader couldn't "steal" wakeup from someone who had it RW-mapped.

It might conflict with a fairness goal, but it does solve the problem without any extension to the API.

#1 lore raw
Quoted 3 lines · George Spelvin

I'm not sure if it's best, but the risk of RO waiters interfering could be solved by giving them a lower prioirty for wakeup and always waking RW-mapped waiters first.

This strikes me as bending over backwards and jumping through hoops inside the kernel to avoid having to do proper permissions management in userspace.

Quoted 6 lines

In most cases, there would only be one type of waiter, so this would have no effect, but if there were, a RO-mapped reader couldn't "steal" wakeup from someone who had it RW-mapped.

It might conflict with a fairness goal, but it does solve the problem without any extension to the API.

Signature · 3 lines
Darren Hart
Intel Open Source Technology Center
Yocto Project - Linux Kernel
#2 lore raw
Quoted 8 lines · Darren Hart
Quoted 3 lines · George Spelvin

I'm not sure if it's best, but the risk of RO waiters interfering could be solved by giving them a lower prioirty for wakeup and always waking RW-mapped waiters first.

This strikes me as bending over backwards and jumping through hoops inside the kernel to avoid having to do proper permissions management in userspace.

Huh?

I still don't understand why userspace ought to need to deny read access to a file to prevent DoS. I think it's entirely reasonable for userspace to make the assumption that users with read access cannot make changes visible to writers unless explicitly documented (i.e. file locking, which is so thoroughly broken that it shouldn't be taken as an example of how to design anything).

Given that current kernels make this use safe and the proposal is to make it unsafe, I think it's worth designing the interface to avoid introducing new security problems.

--Andy

#3 lore raw
Quoted 9 lines · Andrew Lutomirski

Huh?

I still don't understand why userspace ought to need to deny read access to a file to prevent DoS. I think it's entirely reasonable for userspace to make the assumption that users with read access cannot make changes visible to writers unless explicitly documented (i.e. file locking, which is so thoroughly broken that it shouldn't be taken as an example of how to design anything).

Quoted 3 lines

Given that current kernels make this use safe and the proposal is to make it unsafe, I think it's worth designing the interface to avoid introducing new security problems.

I am very tired of this discussion, you repeat the same arguments over and over.

You can not prevent DOS on a machine if you allow a process to RO map your critical files (where you put futexes), because you allow this process to interfere with critical cache lines bouncing between cpus.

Really, please forget about this crazy idea of allowing foreigners to _read_ or memory _map_ your files. Dont do it.

#4 lore raw
Quoted 4 lines · Eric Dumazet

You can not prevent DOS on a machine if you allow a process to RO map your critical files (where you put futexes), because you allow this process to interfere with critical cache lines bouncing between cpus.

The cacheline bounce DoS slows things down and they go back to normal when you kill the DoS-ing task.

The wakeup-eating DoS is permanent. Seems a good deal worse to me.

If you make this change, please at least document it in the man page.

Quoted 4 lines

Really, please forget about this crazy idea of allowing foreigners to _read_ or memory _map_ your files. Dont do it.

Then how am I supposed to efficiently broadcast information to untrusted processes? I'll have to put any futexes involved into different files, but one way or another the actual data will have to be memory mapped to avoid syscall overhead.

--Andy

#5 lore raw
Quoted 6 lines · Andrew Lutomirski
Quoted 4 lines · Eric Dumazet

You can not prevent DOS on a machine if you allow a process to RO map your critical files (where you put futexes), because you allow this process to interfere with critical cache lines bouncing between cpus.

Quoted 7 lines

The cacheline bounce DoS slows things down and they go back to normal when you kill the DoS-ing task.

The wakeup-eating DoS is permanent. Seems a good deal worse to me.

If you make this change, please at least document it in the man page.

This is how futexes had working for years.

It was very obvious from the beginning. Please submit a man page change since you raised the point. You own the credit to open a CVE and immediately release a fix to all 2.6 versions !

How come a critical fix (according to you) went without being noticed and documented ?

Quoted 4 lines

Then how am I supposed to efficiently broadcast information to untrusted processes? I'll have to put any futexes involved into different files, but one way or another the actual data will have to be memory mapped to avoid syscall overhead.

futexes are a linux extension over standard VM games.

If you dont know how to share a memory segment between a group of processes, disallowing others to come spy on you, maybe its better to use another IPC ?

Instead of 'fixing' futexes, what about educating people how to correctly use memory segments ?

#6 lore raw
Quoted 16 lines · Eric Dumazet
Quoted 6 lines · Andrew Lutomirski
Quoted 4 lines · Eric Dumazet

You can not prevent DOS on a machine if you allow a process to RO map your critical files (where you put futexes), because you allow this process to interfere with critical cache lines bouncing between cpus.

Quoted 7 lines

The cacheline bounce DoS slows things down and they go back to normal when you kill the DoS-ing task.

The wakeup-eating DoS is permanent.  Seems a good deal worse to me.

If you make this change, please at least document it in the man page.

Quoted 9 lines

This is how futexes had working for years.

It was very obvious from the beginning. Please submit a man page change since you raised the point. You own the credit to open a CVE and immediately release a fix to all 2.6 versions !

How come a critical fix (according to you) went without being noticed and documented ?

<cynical answer>Because Linux system calls aren't really documented.

It's reasonable to ask people to read a specification of how a system call works to see if it's well-thought-out, usable, and has good security properties.

It's also reasonable to ask people to read an implementation of a system call and check to see that it conforms to the spec.

It's IMO a little less reasonable to ask people to review complicated mm code to see if the interface it implements is well-designed.

The futex(2) and futex(7) manpages are very incomplete, even today.</cynical answer>

Quoted 3 lines

If its useful, then it needs a futex extension (and this must be emulated on old kernels without this extension)

I'm arguing for the extension. I don't think the kernel has any obligation to make sure that new use-cases are possible on old versions, though.

--Andy

#7 lore raw
In reply to Eric Dumazet
Quoted 6 lines

You can not prevent DOS on a machine if you allow a process to RO map your critical files (where you put futexes), because you allow this process to interfere with critical cache lines bouncing between cpus.

Really, please forget about this crazy idea of allowing foreigners to _read_ or memory _map_ your files. Don't do it.

Hold on. There's a significant difference between making a system run slowly (there are a hundred ways to achieve that, starting with the classic fork bomb), and a permanent hard lockup caused by losing a FUTEX_WAIT.

Among other things, you can notice a DoS after a while and kill it. Things should then return to normal.

There may well be a reason to share a file containing futexes read-only.

Just for example, consider a circular buffer that a few (trusted) processes can write to, but many (less trusted) can read. Obviously, being able to sleep on the head pointer is useful.

We are already dealing with one problem caused by a too-narrow idea of how futexes would be used. Let's not add another "nobody would ever want to do that!" unnecessarily.

#8 lore raw
Quoted 3 lines · George Spelvin

Just for example, consider a circular buffer that a few (trusted) processes can write to, but many (less trusted) can read. Obviously, being able to sleep on the head pointer is useful.

If its useful, then it needs a futex extension (and this must be emulated on old kernels without this extension)

Remember futex_wake() call would just have to wakeup _all_ threads instead of one, if kernel lacks this function.

If you dont trust futex_wait() users, just use futex_wake(ALL)

Its should not be a consequence of a previous (unrelated) patch, it should be an added functionality, dully documented.

#9 lore raw
In reply to Eric Dumazet
Quoted 17 lines · Eric Dumazet
Quoted 9 lines · Andrew Lutomirski

Huh?

I still don't understand why userspace ought to need to deny read access to a file to prevent DoS.  I think it's entirely reasonable for userspace to make the assumption that users with read access cannot make changes visible to writers unless explicitly documented (i.e. file locking, which is so thoroughly broken that it shouldn't be taken as an example of how to design anything).

Quoted 3 lines

Given that current kernels make this use safe and the proposal is to make it unsafe, I think it's worth designing the interface to avoid introducing new security problems.

I am very tired of this discussion, you repeat the same arguments over and over.

Quoted 6 lines

You can not prevent DOS on a machine if you allow a process to RO map your critical files (where you put futexes), because you allow this process to interfere with critical cache lines bouncing between cpus.

Really, please forget about this crazy idea of allowing foreigners to _read_ or memory _map_ your files. Dont do it.

The issue is NOT that things get "slow". There are lots of ways to do that in an untrusted process on a normal Linux system. Chewing CPU time and reading random small files from all over the disk are the easiest ones, and most Linux distributions usually ship lots of such files in directories such as /usr/share/doc, /usr/share/zoneinfo, various locales directories, etc.

The issue is that this allows you to eat wakeups and make processes hang.

One relatively trivial example would be a database library like libdb or similar. The library could very reasonably use futexes to communicate between multiple simultaneous threads writing to the same database file. Since the library wants to be well-behaved and avoid thundering herd problems, it only issues a single wakeup for each lock release.

Now you have another program which uses the same database library to do lockless queries of the of the DB file. This is all well and good except that it can now permanently hang an unlimited number of writer threads in FUTEX_WAIT with trivial effort and virtually zero CPU.

All the attacker process needs to do is mmap() one page containing one lock that the victim threads take occasionally and do this in a loop:

    int *victimfutex = [...];
    while(1)
        futex(victimfutex, *victimfutex, FUTEX_WAIT, NULL, NULL, 0);

Suddenly read-only access to *ANY* database file that happens to use an in-file futex means that you can hang the database... period. If you write it in ASM, you could even probably start a whole bunch of threads in parallel by sharing the same stack.

Even better from a DoS standpoint, this does not trigger any resource limits the way other attacks would, because you are sleeping 99.999% of the time and are using no memory. On top of that, once all of the program's threads are stuck you can exit and it will just stay stuck.

This kind of thing is incredibly common in web-applications and other similar environments, where "www-data" should be allowed to query various file databases which are maintained by another daemon.

If the C library happens to use an in-file futex for arbitrating processes writing to /var/log/utmp or /var/log/lastlog, it suddenly becomes trivial to lock up every login process.

That is why FUTEX_WAIT needs separate handling for read-only files.

Cheers,
Kyle Moffett