A long overdue fork-bomb defense ?

A long overdue fork-bomb defense ?

[Robert Hailey]

(Non-subscriber, please CC me in responses)

An idea inspired by the Out-of-Memory Killer, to catch fork bombs at  
fork-time...

The principal indicator of a fork bomb is that it calls fork() too  
much, filling up the process table. What makes it nearly impossible to  
kill manually is that it continuously spawns new processes. It is  
precisely this odd behavior which should make it exceptionally easy to  
kill automatically in the kernel.

#1	per-process unsigned integer field "fork_count"
	increments at each fork() [if not max_int],
	new processes inherit incremented value from parent process, or
	zero if parent is init, exec() should *not* clear fork_count

(the above statistic alone might be interesting?)

#2 	global unsigned int "fork_alert_level" usually zero
	doubles both as a alert state switch & fork_count at which to kill  
processes
#3	global time value "fork_alert_time"
	to return the kernel to standard operation when threat is abated

fork would no longer return ELIMIT (or the like), but follow this  
pattern:

fork(proc) {
	unsigned fork_count=(proc->fork_count+1);
	//detect overflow
	if (fork_count>proc->fork_count) {
		proc->fork_count=fork_count;
	} else {
		log("fork_count generation");
		divide_all_process_fork_counts_by_two();
		fork_alert_level/=2;
	}
	if (fork_alert_level) {
		if (fork_count >= fork_alert_level) {
			signal(KILL, proc) && log('killed ...');
			//don't: fork_alert_time=now();
			return/dispatch?;
		}
		if (now()-fork_alert_time>10 seconds?) {
			fork_alert_level=0; //Relax
		}
	}

	child=allocate_new_process();
	if (!child) {
		//No more processes in process table
		Proc highest;
		Proc second_place;
		for ( p : process_table) {
			if (init || protected?) continue;
			if (!highest || p->fork_count>highest->fork_count) {
				second_place=highest;
				highest=p;
			}
		}
		assert(highest->fork_count != second_place->fork_count);
		if (afraid_of_killing_innocents) {
			fork_alert_level = second_place->fork_count;
		} else {
			fork_alert_level = second_place->fork_count -
				(highest->fork_count-second_place->fork_count);
		}
		fork_alert_time=now();
		if (fork_count >= fork_alert_level) {
			signal(KILL, proc)    && log('killed ...');
			signal(KILL, highest) && log('killed ...');
			return/dispatch;
		} else {
			signal(KILL, highest) && log('killed ...');
			child=takeover_process_place(highest);
		}
	}
	child->fork_count=fork_count;

	...continue with fork() logic...
}

So in normal operation it would only count forks.

Of course, the concern is killing processes that legitimately fork  
many times over the course of their life (e.g. inetd, cron...). Such a  
process is not really in danger from it's own children (as they  
inherit the fork_count), but might be in danger of another process'  
child.

Seeing that the new systemd puts each service in it's own process  
group, at first I was thinking this could be easily solved by  
isolating the fork-based-killing to the process group which contains  
the most processes at the moment the process table is found to be full.

Does this sound reasonable, or would an out-of-processes-killer also  
need to scan for session ids or be overly complicated (by uid, by tty)?

Would it even work? thoughts/ideas?

--
Robert Hailey


Seen: delivering a fork_bomb_defense as a kernel module
http://memset.wordpress.com/2011/02/10/syscall-hijacking-anti-fork-bomb-lkm-kernel-2-6-x/

Seen: fork bomb defense with OOM-killer by least_common_ancestor
http://lwn.net/Articles/134513/
http://lwn.net/Articles/136061/

Re: A long overdue fork-bomb defense ?

[Valdis.Kletnieks]

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

On Fri, 08 Apr 2011 15:47:13 CDT, Robert Hailey said:

> 		log("fork_count generation");
> 		divide_all_process_fork_counts_by_two();

This will involve painful locking on large systems with lots of procs running.


> 		for ( p : process_table) {

Ditto.

>	if (fork_alert_level) {
>		if (fork_count >= fork_alert_level) {
>			signal(KILL, proc) && log('killed ...');
>			//don't: fork_alert_time=now();
>			return/dispatch?;
>		}
>		if (now()-fork_alert_time>10 seconds?) {
>			fork_alert_level=0; //Relax
>		}
>	}

A smart attacker can probably use this to  game the fork rate to fly just under
the wire, while still piling up lots of processes, *and* adding extra overhead
as it goes. If the rate limit is 5000 forks every 10 seconds, it can do 4500
every 10 seconds, and in a few minutes the poor scaling sections will eat your
system alive.

(And don't say "but it can be detected and stopped in those few minutes" -
because the *reality* in the security world is that people will say "We have
this great anti-forkbomb patch in the kernel, and don't need to check anymore".
Yes, they *will* do that.  Users that will blindly click on stuff because their AV
will stop anything bad are one of the banes of my existence. ;)


[-- Attachment #2: Type: application/pgp-signature, Size: 227 bytes --]

Re: A long overdue fork-bomb defense ?

[Robert Hailey]

On 2011/04/09 (Apr), at 3:12 PM, Valdis.Kletnieks@vt.edu wrote:

> On Fri, 08 Apr 2011 15:47:13 CDT, Robert Hailey said:
>
>> 		log("fork_count generation");
>> 		divide_all_process_fork_counts_by_two();
>
> This will involve painful locking on large systems with lots of  
> procs running.

This logic (and the related painful locks) would be triggered only  
once in a small fractional proportion to the number of forks of the  
single greatest forker. But it is a solid observation, that if such a  
patch was in place there would be an overhead to it's use; I imagine  
it would take a considerable amount of time for a long running system  
to wrap it's fork counts.

Is there a better way to handle the integer overflows?

>
>
>> 		for ( p : process_table) {
>
> Ditto.

Thankfully, this logic would only be triggered when the process table  
is full. At that point I doubt anyone would miss the compute time of  
even the most painful lock :)

>
>> 	if (fork_alert_level) {
>> 		if (fork_count >= fork_alert_level) {
>> 			signal(KILL, proc) && log('killed ...');
>> 			//don't: fork_alert_time=now();
>> 			return/dispatch?;
>> 		}
>> 		if (now()-fork_alert_time>10 seconds?) {
>> 			fork_alert_level=0; //Relax
>> 		}
>> 	}
>
> A smart attacker can probably use this to  game the fork rate to fly  
> just under
> the wire, while still piling up lots of processes, *and* adding  
> extra overhead
> as it goes. If the rate limit is 5000 forks every 10 seconds, it can  
> do 4500
> every 10 seconds, and in a few minutes the poor scaling sections  
> will eat your
> system alive.

Perhaps there is a misunderstanding.... Although this logic is  
*sensitive* to forking rate, this is not directly acting on (or  
measuring) a forking rate. It is simply providing a metric by which  
processes can be compared (number of forks in self and ancestors), and  
providing something to do if we find that we are out of process table  
space (the limited resource in question). Of course... if the memory  
ceiling is reached first (fork/malloc), then that is a concern of the  
OOM-killer (a separate but related discussion).

Presuming for a moment that it works, I think the worst case is  
actually a single (perhaps compromised) process spawning child fork  
bombs. For that matter it could be a bash shell with the user setting  
them off. In that case it might *never* cause enough forking it to get  
itself automatically killed, but the system would still be [somewhat?]  
responsive through the attack b/c it no longer denies a legitimate  
fork, i.e. logging in & using a shell work, even while the process  
table is *FULL* of active fork bombs.

Even if a fork bomb is downgraded from "fatal" to "makes things darn  
slow", it's worth considering, no?

--
Robert Hailey

Re: A long overdue fork-bomb defense ?

[Valdis.Kletnieks]

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

On Sat, 09 Apr 2011 17:25:48 CDT, Robert Hailey said:

> Is there a better way to handle the integer overflows?

Oh, is that for overflow handling? My (admittedly quick) review
of the code made it look like it was an exponential-decay feature.

Might want to think about what situations will cause an integer overflow
here.  What has to happen before an overflow is a concern?

> >> 		for ( p : process_table) {
> >
> > Ditto.
>
> Thankfully, this logic would only be triggered when the process table
> is full. At that point I doubt anyone would miss the compute time of
> even the most painful lock :)

If you get to the point where it's full, you've already lost.

> Presuming for a moment that it works, I think the worst case is
> actually a single (perhaps compromised) process spawning child fork
> bombs. For that matter it could be a bash shell with the user setting
> them off. In that case it might *never* cause enough forking it to get
> itself automatically killed, but the system would still be [somewhat?]

bash$ :(){ :|:&};:

Try it and see. ;)

> responsive through the attack b/c it no longer denies a legitimate  
> fork, i.e. logging in & using a shell work, even while the process  
> table is *FULL* of active fork bombs.

I suspect recent patches that allow an entire process tree to be sent SIGSTOP
will be a more productive approach.

> Even if a fork bomb is downgraded from "fatal" to "makes things darn  
> slow", it's worth considering, no?

Depends why a fork bomb was allowed to be fatal in the first place...

[-- Attachment #2: Type: application/pgp-signature, Size: 227 bytes --]

Re: A long overdue fork-bomb defense ?

[Robert Hailey]

On 2011/04/09 (Apr), at 5:44 PM, Valdis.Kletnieks@vt.edu wrote:

> On Sat, 09 Apr 2011 17:25:48 CDT, Robert Hailey said:
>
>> Is there a better way to handle the integer overflows?
> ...
> Might want to think about what situations will cause an integer  
> overflow
> here.  What has to happen before an overflow is a concern?

It's counting forks per-process, so it is theoretically bound to  
overflow eventually.

If we use an unsigned 32-bit counter and take 'cron' as an example  
(say it forks 20 times / minute), it would take about 400 years to  
overflow. If on the other hand, we have a naive transaction processor  
using inetd (which if i'm not mistaken forks at every inbound  
connection) at 60,000/second (!) it will wrap about every 48 days.  
Using the div-2 method the next will come sooner, so maybe every  
month....

I think the cost of lock is well amortized even at 32-bits.

>> Thankfully, this logic would only be triggered when the process table
>> is full. At that point I doubt anyone would miss the compute time of
>> even the most painful lock :)
>
> If you get to the point where it's full, you've already lost.
> ...
> Depends why a fork bomb was allowed to be fatal in the first place...

Can you elaborate as to why "you've already lost" if the process table  
is full?

I am particularly interested in any additional information as to why  
fork bombs are fatal, and what the most evil/elusive fork bomb would  
be. At present I think it's about this:

bomb (rate, memory) {
	while(true) {
		if (root) {
			daemonize();
			new_session();
			new_process_group();
			new_executable_name();
			if (some_chance) change_uid;
		}
		leak_some(memory);
		bomb(rate*2, memory);
		delay(rate);
	}
}
bomb(time_on_target, memory_ceiling_tuned);

>
>> Presuming for a moment that it works, I think the worst case is
>> actually a single (perhaps compromised) process spawning child fork
>> bombs. For that matter it could be a bash shell with the user setting
>> them off. In that case it might *never* cause enough forking it to  
>> get
>> itself automatically killed, but the system would still be  
>> [somewhat?]
>
> bash$ :(){ :|:&};:
>
> Try it and see. ;)

Not yet, but maybe soon... ;-)

>
>> responsive through the attack b/c it no longer denies a legitimate
>> fork, i.e. logging in & using a shell work, even while the process
>> table is *FULL* of active fork bombs.
>
> I suspect recent patches that allow an entire process tree to be  
> sent SIGSTOP
> will be a more productive approach.

Surely you're not relying on a user to catch the fork bomb, so how is  
it detected?

BTW, already starting to get off discussion of original idea & psuedo- 
code.

--
Robert Hailey