Skip to contentSkip to conversation

/proc/sys/kernel/pid_max issues

DISCUSSION Albert Cahalan 7 participants 17 messages Sep 13, 2004 – Sep 24, 2004

lore
Share & tools
lore
#0 lore raw
Quoted 5 lines · Ingo Molnar

it's getting quite spaghetti ... do we really want to handle RESERVED_PID? There's no guarantee that any root daemon wont stray out of the 1...300 PID range anyway, so if it has an exploitable PID race bug then it's probably exploitable even without the RESERVED_PID protection.

Purpose:

1. weak security enhancement
2. cosmetic (backwards, IMHO)
3. speed (avoid PIDs likely to be used)

I'd much prefer LRU allocation. There are lots of system calls that take PID values. All such calls are hazardous. They're pretty much broken by design.

Better yet, make a random choice from the 50% of PID space that has been least recently used.

Another idea is to associate PIDs with users to some extent. You keep getting back the same set of PIDs unless the system runs low in some global pool and has to steal from one user to satisfy another.

BTW, since pid_max is now adjustable, reducing the default to 4 digits would make sense. Try a "ps j" to see the use. (column width changes if you change max_pid)

#1 lore raw
Quoted 5 lines · Ingo Molnar
Quoted 5 lines

it's getting quite spaghetti ... do we really want to handle RESERVED_PID? There's no guarantee that any root daemon wont stray out of the 1...300 PID range anyway, so if it has an exploitable PID race bug then it's probably exploitable even without the RESERVED_PID protection.

Quoted 4 lines · Albert Cahalan

Purpose:
1. weak security enhancement
2. cosmetic (backwards, IMHO)
3. speed (avoid PIDs likely to be used)

Well, weak security enhancement translates to "nop" in my book, but I guess if that's really what people were trying to arrange...

Quoted 7 lines · Albert Cahalan

I'd much prefer LRU allocation. There are lots of system calls that take PID values. All such calls are hazardous. They're pretty much broken by design.
Better yet, make a random choice from the 50% of PID space that has been least recently used.

I'd favor fully pseudorandom allocation over LRU or approximate LRU allocation, as at least pseudorandom is feasible without large impacts on resource scalability. OTOH the cache characteristics of pseudorandom allocation are usually poor; perhaps hierarchically pseudorandom allocation where one probes a sequence of cachelines of the bitmap according to one PRNG, and within each cacheline probes a random sequence of bits according to some other PRNG, would resolve that.

Quoted 5 lines · Albert Cahalan

Another idea is to associate PIDs with users to some extent. You keep getting back the same set of PIDs unless the system runs low in some global pool and has to steal from one user to satisfy another.

The resource tracking and locking implications of this are disturbing. Would fully pseudorandom allocation be acceptable?

Quoted 4 lines · Albert Cahalan

BTW, since pid_max is now adjustable, reducing the default to 4 digits would make sense. Try a "ps j" to see the use. (column width changes if you change max_pid)

Is the maximum possible pid exported by the kernel somehow? Perhaps it should be; the maximum number of decimal digits required to represent PID_MAX_LIMIT (4*1024*1024) should suffice in all cases. Perhaps you need to detect PID_MAX_LIMIT somehow?

-- wli

#2 lore raw
Quoted 19 lines · William Lee Irwin III
Quoted 7 lines · Albert Cahalan

I'd much prefer LRU allocation. There are lots of system calls that take PID values. All such calls are hazardous. They're pretty much broken by design.
Better yet, make a random choice from the 50% of PID space that has been least recently used.

I'd favor fully pseudorandom allocation over LRU or approximate LRU allocation, as at least pseudorandom is feasible without large impacts on resource scalability. OTOH the cache characteristics of pseudorandom allocation are usually poor; perhaps hierarchically pseudorandom allocation where one probes a sequence of cachelines of the bitmap according to one PRNG, and within each cacheline probes a random sequence of bits according to some other PRNG, would resolve that.

On Sun, Sep 12, 2004 at 11:20:29PM -0400, Albert Cahalan wrote:

Quoted 8 lines
Quoted 5 lines

Another idea is to associate PIDs with users to some extent. You keep getting back the same set of PIDs unless the system runs low in some global pool and has to steal from one user to satisfy another.

The resource tracking and locking implications of this are disturbing. Would fully pseudorandom allocation be acceptable?

There's no point.

LRU reduces accidents that don't involve an attacker.

Strong crypto random can make some attacks a bit harder. OpenBSD does this. It doesn't work well enough to bother with if the implementation is problematic; there's not much you can do while avoiding 64-bit or 128-bit PIDs. Pseudorandom is 100% useless.

Per-user PID recycling would make it much harder for an attacker to grab a specific PID. Perhaps the attacker knows that a sched_setscheduler call is coming, and he has a way to make the right process restart or crash. Normally, this lets him get SCHED_FIFO or somesuch. With per-user PID recycling, it would be difficult for him to grab the desired PID.

Quoted 10 lines · Albert Cahalan
Quoted 4 lines

BTW, since pid_max is now adjustable, reducing the default to 4 digits would make sense. Try a "ps j" to see the use. (column width changes if you change max_pid)

Is the maximum possible pid exported by the kernel somehow? Perhaps it should be; the maximum number of decimal digits required to represent PID_MAX_LIMIT (4*1024*1024) should suffice in all cases. Perhaps you need to detect PID_MAX_LIMIT somehow?

I do indeed detect pid_max via /proc/sys/kernel/pid_max and adjust column widths as needed. (ps only, for now)

Since we're not getting the benefits of strong crypto PIDs anyway, we might as well have 4-digit PIDs be default. Very few people would need to increase this.

#3 lore raw
Quoted 2 lines · William Lee Irwin III
Quoted 2 lines

The resource tracking and locking implications of this are disturbing. Would fully pseudorandom allocation be acceptable?

Quoted 6 lines · Albert Cahalan

There's no point.
LRU reduces accidents that don't involve an attacker. Strong crypto random can make some attacks a bit harder. OpenBSD does this. It doesn't work well enough to bother with if the implementation is problematic; there's not much you can do while avoiding 64-bit or 128-bit PIDs.

Quoted 8 lines

Pseudorandom is 100% useless.
Per-user PID recycling would make it much harder for an attacker to grab a specific PID. Perhaps the attacker knows that a sched_setscheduler call is coming, and he has a way to make the right process restart or crash. Normally, this lets him get SCHED_FIFO or somesuch. With per-user PID recycling, it would be difficult for him to grab the desired PID.

I'd suggest pushing for 64-bit+ pid's, then. IIRC most of the work there is in userspace (the in-kernel part is trivial).

-- wli

#4 lore raw
Quoted 20 lines · William Lee Irwin III
Quoted 2 lines · William Lee Irwin III
Quoted 2 lines

The resource tracking and locking implications of this are disturbing. Would fully pseudorandom allocation be acceptable?

Quoted 6 lines · Albert Cahalan

There's no point.
LRU reduces accidents that don't involve an attacker. Strong crypto random can make some attacks a bit harder. OpenBSD does this. It doesn't work well enough to bother with if the implementation is problematic; there's not much you can do while avoiding 64-bit or 128-bit PIDs.

Quoted 8 lines

Pseudorandom is 100% useless.
Per-user PID recycling would make it much harder for an attacker to grab a specific PID. Perhaps the attacker knows that a sched_setscheduler call is coming, and he has a way to make the right process restart or crash. Normally, this lets him get SCHED_FIFO or somesuch. With per-user PID recycling, it would be difficult for him to grab the desired PID.

Quoted 2 lines

I'd suggest pushing for 64-bit+ pid's, then. IIRC most of the work there is in userspace (the in-kernel part is trivial).

except for the various 'assumptions' done in procfs to create the inode numbers ... but that is a different story ...

best,
Herbert

Quoted 6 lines

-- wli
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

#5 lore raw
Quoted 2 lines · William Lee Irwin III
Quoted 2 lines

I'd suggest pushing for 64-bit+ pid's, then. IIRC most of the work there is in userspace (the in-kernel part is trivial).

Quoted 3 lines · Herbert Poetzl

except for the various 'assumptions' done in procfs to create the inode numbers ... but that is a different story ...

The overflow conditions in there are ugly and need someone willing to do more intensive work with that code to address them. It's not difficult per se, merely a lot of grubbing around with ugly code.

-- wli

#6 lore raw
In reply to William Lee Irwin III

Hi!

Quoted 5 lines
Quoted 2 lines

With per-user PID recycling, it would be difficult for him to grab the desired PID.

I'd suggest pushing for 64-bit+ pid's, then. IIRC most of the work there is in userspace (the in-kernel part is trivial).

Actually 64-bit pids would be very nice for clustering. mj did that once, IIRC, maybe he still has a patch?

Signature · 1 line
64 bytes from 195.113.31.123: icmp_seq=28 ttl=51 time=448769.1 ms         
#7 lore raw

Hi!

Quoted 2 lines

Actually 64-bit pids would be very nice for clustering. mj did that once, IIRC, maybe he still has a patch?

No, it was 32-bit pids in the 16-bit pid times :)

Have a nice fortnight

Signature · 3 lines
Martin `MJ' Mares   <[email protected]>   http://atrey.karlin.mff.cuni.cz/~mj/
Faculty of Math and Physics, Charles University, Prague, Czech Rep., Earth
IBM = Inside Black Magic
#8 lore raw
In reply to William Lee Irwin III

Hi!

Quoted 7 lines
Quoted 3 lines

1. weak security enhancement
2. cosmetic (backwards, IMHO)
3. speed (avoid PIDs likely to be used)

Well, weak security enhancement translates to "nop" in my book, but I guess if that's really what people were trying to arrange...

Well, how many times did you do kill <pid> from command line after doing ps? If you randomly kill some other process because pids wrapped too fast, it is bad.

Signature · 1 line
64 bytes from 195.113.31.123: icmp_seq=28 ttl=51 time=448769.1 ms         
#9 lore raw
In reply to Albert Cahalan
Quoted 4 lines · Albert Cahalan

I'd much prefer LRU allocation. There are lots of system calls that take PID values. All such calls are hazardous. They're pretty much broken by design.

this is a pretty sweeping assertion. Would you
care to mention a few examples of such hazards?

Quoted 2 lines

BTW, since pid_max is now adjustable, reducing the default to 4 digits would make sense. [...]

i'm not sure what you mean by 'now', pid_max has
been adjustable for quite some time.

Ingo

#10 lore raw
Quoted 9 lines · Ingo Molnar
Quoted 4 lines · Albert Cahalan

I'd much prefer LRU allocation. There are lots of system calls that take PID values. All such calls are hazardous. They're pretty much broken by design.

this is a pretty sweeping assertion. Would you
care to mention a few examples of such hazards?

kill(12345,9) setpriority(PRIO_PROCESS,12345,-20) sched_setscheduler(12345, SCHED_FIFO, &sp)

Prior to the call being handled, the process may die and be replaced. Some random innocent process, or a not-so-innocent one, will get acted upon by mistake. This is broken and dangerous.

Well, it's in the UNIX standard. The best one can do is to make the race window hard to hit, with LRU.

Quoted 5 lines
Quoted 2 lines

BTW, since pid_max is now adjustable, reducing the default to 4 digits would make sense. [...]

i'm not sure what you mean by 'now', pid_max has
been adjustable for quite some time.

2.6.x series I believe, not 2.4.xx series

#11 lore raw
Quoted 2 lines · Ingo Molnar
Quoted 2 lines

this is a pretty sweeping assertion. Would you
care to mention a few examples of such hazards?

Quoted 9 lines · Albert Cahalan

kill(12345,9) setpriority(PRIO_PROCESS,12345,-20) sched_setscheduler(12345, SCHED_FIFO, &sp) Prior to the call being handled, the process may die and be replaced. Some random innocent process, or a not-so-innocent one, will get acted upon by mistake. This is broken and dangerous.
Well, it's in the UNIX standard. The best one can do is to make the race window hard to hit, with LRU.

How do you propose to queue pid's? This is space constrained. I don't believe it's feasible and/or desirable to attempt this, as there are 4 million objects to track independent of machine size. The general tactic of cyclic order allocation is oriented toward making this rare and/or hard to trigger by having a reuse period long enough that what processes there are after a pid wrap are likely to have near-indefinite lifetimes. i.e. it's the closest feasible approximation of LRU. If you truly want/need reuse to be gone, 64-bit+ pid's are likely best.

-- wli

#12 lore raw
Quoted 15 lines · William Lee Irwin III
Quoted 2 lines · Ingo Molnar
Quoted 2 lines

this is a pretty sweeping assertion. Would you
care to mention a few examples of such hazards?

Quoted 9 lines · Albert Cahalan

kill(12345,9) setpriority(PRIO_PROCESS,12345,-20) sched_setscheduler(12345, SCHED_FIFO, &sp) Prior to the call being handled, the process may die and be replaced. Some random innocent process, or a not-so-innocent one, will get acted upon by mistake. This is broken and dangerous.
Well, it's in the UNIX standard. The best one can do is to make the race window hard to hit, with LRU.

Quoted 3 lines

How do you propose to queue pid's? This is space constrained. I don't believe it's feasible and/or desirable to attempt this, as there are 4 million objects to track independent of machine size.

As we've seen elsewhere in this thread, things break when you go above 0xffff anyway. So 128 KiB of RAM should do the job. With a 4-digit PID, 20000 bytes would be enough.

Supposing you fix rwsem counts and /proc inodes and so on, a large machine could handle 4 million objects easily. A small machine has far, far, less need to support that.

Quoted 6 lines

The general
tactic of cyclic order allocation is oriented toward making this rare and/or hard to trigger by having a reuse period long enough that what processes there are after a pid wrap are likely to have near-indefinite lifetimes. i.e. it's the closest feasible approximation of LRU. If you truly want/need reuse to be gone, 64-bit+ pid's are likely best.

That's too unwieldy for the users, it breaks glibc, and you'll still hit the problems after wrap-around. Besides, Linus vetoed this a year or two ago.

Reducing the dangers of a small PID space allows for just the opposite size change, which is much nicer for the users.

#13 lore raw
Quoted 3 lines · William Lee Irwin III
Quoted 3 lines

How do you propose to queue pid's? This is space constrained. I don't believe it's feasible and/or desirable to attempt this, as there are 4 million objects to track independent of machine size.

Quoted 7 lines · Albert Cahalan

As we've seen elsewhere in this thread, things break when you go above 0xffff anyway. So 128 KiB of RAM should do the job. With a 4-digit PID, 20000 bytes would be enough.
Supposing you fix rwsem counts and /proc inodes and so on, a large machine could handle 4 million objects easily. A small machine has far, far, less need to support that.

The feature of supporting more threads is there and meant to be supported, so "> 32K breaks anyway" doesn't really fly; it should be fixed.

The rwsems just want ia32 to use generic rwsems. /proc/ is a much bigger mess but far from insurmountable. I suppose someone has to be willing to mess with it for that to be fixed, and it may need other vfs-related help (ino64_t support?).

Quoted 6 lines · William Lee Irwin III
Quoted 6 lines

The general
tactic of cyclic order allocation is oriented toward making this rare and/or hard to trigger by having a reuse period long enough that what processes there are after a pid wrap are likely to have near-indefinite lifetimes. i.e. it's the closest feasible approximation of LRU. If you truly want/need reuse to be gone, 64-bit+ pid's are likely best.

Quoted 6 lines · Albert Cahalan

That's too unwieldy for the users, it breaks glibc, and you'll still hit the problems after wrap-around. Besides, Linus vetoed this a year or two ago. Reducing the dangers of a small PID space allows for just the opposite size change, which is much nicer for the users.

Reducing the PID space so the pid's can be formatted in 4 digits doesn't sound particularly compelling. 64-bit pid's wrapping sounds rather unlikely, but if so, 128-bit pids are more likely to withstand various physical arguments against pid wrapping ever happening.

The middle ground is already where kernel/pid.c stands, so I'd prefer to leave this alone unless you have deeper concerns about it than 4-column displays and pid reuse problems (which want larger pid spaces, not smaller). The primary complaint I've heard about pid reuse is actually that smaller pid spaces (e.g. 32K) wrap far too quickly, sometimes numerous times per second on larger systems with parallel process creation activity. It's unclear what the pid wrap speeds are for the workloads they reported is with the now-permissible pid_max (in fact, I've since forgotten who reported this).

-- wli

#14 lore raw
In reply to Albert Cahalan
Quoted 8 lines · Albert Cahalan
Quoted 7 lines
Quoted 4 lines

I'd much prefer LRU allocation. There are lots of system calls that take PID values. All such calls are hazardous. They're pretty much broken by design.

this is a pretty sweeping assertion. Would you
care to mention a few examples of such hazards?

Quoted 8 lines

kill(12345,9) setpriority(PRIO_PROCESS,12345,-20) sched_setscheduler(12345, SCHED_FIFO, &sp)

Prior to the call being handled, the process may die and be replaced. Some random innocent process, or a not-so-innocent one, will get acted upon by mistake. This is broken and dangerous.

easy to fix: SIGSTOP the task, check it's really the one you want and then do the setpriority / setscheduler call and SIGCONT it. Any privileged code that is about to spread some of its privileges via asynchronous system-calls need to be careful.

Ingo

#15 lore raw

Hi!

Quoted 17 lines
Quoted 8 lines
Quoted 7 lines
Quoted 4 lines

I'd much prefer LRU allocation. There are lots of system calls that take PID values. All such calls are hazardous. They're pretty much broken by design.

this is a pretty sweeping assertion. Would you
care to mention a few examples of such hazards?

Quoted 8 lines

kill(12345,9) setpriority(PRIO_PROCESS,12345,-20) sched_setscheduler(12345, SCHED_FIFO, &sp)

Prior to the call being handled, the process may die and be replaced. Some random innocent process, or a not-so-innocent one, will get acted upon by mistake. This is broken and dangerous.

Quoted 5 lines

easy to fix: SIGSTOP the task, check it's really the one you want and then do the setpriority / setscheduler call and SIGCONT it. Any privileged code that is about to spread some of its privileges via asynchronous system-calls need to be careful.

What if OOM killer decides it wants that memory in between? Attacker could probably help it...
Pavel

Signature · 2 lines
People were complaining that M$ turns users into beta-testers...
...jr ghea gurz vagb qrirybcref, naq gurl frrz gb yvxr vg gung jnl!
#16 lore raw
In reply to Albert Cahalan

Hi!

Quoted 7 lines
Quoted 2 lines

this is a pretty sweeping assertion. Would you
care to mention a few examples of such hazards?

kill(12345,9) setpriority(PRIO_PROCESS,12345,-20) sched_setscheduler(12345, SCHED_FIFO, &sp)

Quoted 7 lines

Prior to the call being handled, the process may die and be replaced. Some random innocent process, or a not-so-innocent one, will get acted upon by mistake. This is broken and dangerous.

Well, it's in the UNIX standard. The best one can do is to make the race window hard to hit, with LRU.

Well, you could create new state "DEAD" and enforce that every process stays there for 5 seconds after death. Throttle fork if no pids are free. Hide "DEAD" processes from ps/top.
Pavel

Signature · 1 line
64 bytes from 195.113.31.123: icmp_seq=28 ttl=51 time=448769.1 ms