[RFC][PATCH] fork bomb killer

[RFC][PATCH] fork bomb killer

[KAMEZAWA Hiroyuki]

While testing Andrey's case, I confirmed I need to reboot the system by
power off when I ran a fork-bomb. The speed of fork() is much faster
than some smart killing as pkill(1) and oom-killer cannot reach the speed.

I wonder it's better to have a fork-bomb killer even if it's a just heuristic
method. This is a one. This one works fine with Andrey's case and I don't need
to reboot more. And I confirmed this can kill a case like

	while True:
		os.fork()

BTW, does usual man see fork-bomb in a production system ?
I saw only once which was caused be a shell script.

==
A fork bomb killer.

When fork-bomb runs, the system exhausts memory and we need to
reboot the system, in usual. The oom-killer or admin's killall
is slower than fork-bomb if system memory is exhausted.

So, fork-bomb-killer is appreciated even if it's a just heuristic.

This patch implements a heuristic for fork-bomb. The logic finds
a fork bomb which
 - has spawned 10+ tasks recently (10 min).
 - aggregate score of bomb is larger than the baddest task's badness.

When fork-bomb found,
 - new fork in the session under where fork bomb is will return -ENOMEM
   for the next 30secs.
 - all tasks of fork-bomb will be killed.

Note:
 - I wonder I shoud add a sysctl knob for this.

Signed-off-by: KAMEZAWA Hiroyuki <kamezawa.hiroyu@jp.fujitsu.com>
---
 include/linux/mm_types.h |    3 
 include/linux/oom.h      |    6 +
 include/linux/sched.h    |    6 +
 kernel/fork.c            |    2 
 mm/oom_kill.c            |  148 +++++++++++++++++++++++++++++++++++++++++++++++
 5 files changed, 165 insertions(+)

Index: mmotm-temp/include/linux/oom.h
===================================================================
--- mmotm-temp.orig/include/linux/oom.h
+++ mmotm-temp/include/linux/oom.h
@@ -62,6 +62,12 @@ static inline void oom_killer_enable(voi
 	oom_killer_disabled = false;
 }
 
+extern struct pid *fork_bomb_session;
+static inline bool in_fork_bomb(void)
+{
+	return task_session(current) == fork_bomb_session;
+}
+
 /* The badness from the OOM killer */
 extern unsigned long badness(struct task_struct *p, struct mem_cgroup *mem,
 		      const nodemask_t *nodemask, unsigned long uptime);
Index: mmotm-temp/kernel/fork.c
===================================================================
--- mmotm-temp.orig/kernel/fork.c
+++ mmotm-temp/kernel/fork.c
@@ -1417,6 +1417,8 @@ long do_fork(unsigned long clone_flags,
 			return -EPERM;
 	}
 
+	if (in_fork_bomb())
+		return -ENOMEM;
 	/*
 	 * When called from kernel_thread, don't do user tracing stuff.
 	 */
Index: mmotm-temp/mm/oom_kill.c
===================================================================
--- mmotm-temp.orig/mm/oom_kill.c
+++ mmotm-temp/mm/oom_kill.c
@@ -332,6 +332,150 @@ static struct task_struct *select_bad_pr
 	return chosen;
 }
 
+/*
+ * If there is a quick fork-bomb and it locks memory (allocating anon
+ * when nr_swap_pages==0), users feel very bad response and will not
+ * be able to recover because fork-bomb tend to be faster than killall
+ * and oom-kill. This is for killing a group of process which seems to
+ * be a fork-bomb.
+ *
+ * This can kill a fork-bomb when
+ *  - Threads in a bomb are enough young.(10min)
+ *  - The number of new process are enough large (10)
+ *
+ *  And this will prevent new fork() in the session for 30secs.
+ */
+#define FORK_BOMB_THRESH	(10*HZ)
+#define FORK_BOMB_RECOVER_JIFFIES	(30*HZ)
+
+struct pid *fork_bomb_session __read_mostly;
+static struct delayed_work forkbomb_timeout;
+
+static void clear_fork_bomb(struct work_struct *w)
+{
+	fork_bomb_session = NULL;
+}
+
+static bool is_ancestor(struct task_struct *t, struct task_struct *p)
+{
+	while (t != &init_task) {
+		if (t == p)
+			return true;
+		t = t->real_parent;
+	}
+	return false;
+}
+
+static bool fork_bomb_detection(unsigned long totalpages, struct mem_cgroup *mem,
+		const nodemask_t *nodemask)
+{
+	unsigned long start_time, fork_bomb_thresh, score, bomb_score;
+	struct task_struct *p, *t, *child, *bomb_task;
+	struct mm_struct *mm;
+	struct pid *bomb_session;
+	int family, bomb_family;
+
+	/* A forkbomb killer works and killing someone ? */
+	if (fork_bomb_session)
+		return true;
+
+	if (jiffies > FORK_BOMB_THRESH*10)
+		fork_bomb_thresh = jiffies/2;
+	else
+		fork_bomb_thresh = FORK_BOMB_THRESH;
+
+	bomb_task = NULL;
+	bomb_score = 0;
+	bomb_session = NULL;
+	bomb_family = 0;
+
+	for_each_process_reverse(p) {
+
+		start_time = timespec_to_jiffies(&p->start_time);
+		start_time += fork_bomb_thresh;
+		/* if the process is not young, ignore this */
+		if (time_after(start_time, jiffies))
+			break;
+		if (!p->mm || oom_unkillable_task(p, mem, nodemask))
+			continue;
+
+		score = oom_badness(p, mem, nodemask, totalpages);
+		/* the task itself is a burden for the system */
+		score += 1;
+		/* If this task has no children, we have no interests */
+		family = 1;
+		t = p;
+		do {
+			list_for_each_entry(child, &t->children, sibling) {
+				struct task_struct *temp;
+
+				/* Ignore task in other session */
+				if (task_session(child) != task_session(p))
+					continue;
+				/* All children are younger than p. */
+				temp = find_lock_task_mm(child);
+				if (temp) {
+					score += temp->mm->fork_bomb_score;
+					family += temp->mm->fork_bomb_family;
+					task_unlock(temp);
+				}
+			}
+		} while_each_thread(p, t);
+		/* Here, we have an aggregate score of a process tree */
+		p = find_lock_task_mm(p);
+		if (p) {
+			mm = p->mm;
+			mm->fork_bomb_score = score;
+			mm->fork_bomb_family = family;
+			task_unlock(p);
+		} else
+			continue;
+
+		if (bomb_score < score) {
+			bomb_task = p;
+			bomb_score = score;
+			bomb_family = family;
+			bomb_session = task_session(p);
+		}
+    	}
+	/* if a usual shell script run by a shell is found, ignore */
+	if (!bomb_task || bomb_family < 10)
+		return false;
+
+	fork_bomb_session = task_session(bomb_task);
+	INIT_DELAYED_WORK(&forkbomb_timeout, clear_fork_bomb);
+	schedule_delayed_work(&forkbomb_timeout, FORK_BOMB_RECOVER_JIFFIES);
+
+	/*
+	 * Now, we found a bomb task. kill all children of bomb_task.
+	 * and disallow new fork() in this session for a while.
+	 * If bomb_task is a session leader, don't kill it.
+	 */
+	pr_err("Possible fork-bomb. Killing all bomb threadsi\n");
+	pr_err("Killed all young children shares session of %d (%s)"
+		"aggregated badness %ld\n",
+		task_pid_nr(bomb_task), bomb_task->comm, bomb_score);
+
+	do_each_pid_task(bomb_session, PIDTYPE_SID, p) {
+
+		start_time = timespec_to_jiffies(&p->start_time);
+		start_time += fork_bomb_thresh;
+
+		if (!thread_group_leader(p))
+			continue;
+		if (oom_unkillable_task(p, mem, nodemask))
+			continue;
+		if (time_after(start_time, jiffies))
+			continue;
+		if (!is_ancestor(p, bomb_task))
+			continue;
+		pr_err("    kill %d(%s)\n", task_pid_nr(p), p->comm);
+		force_sig(SIGKILL, p);
+	} while_each_pid_task(bomb_session, PIDTYPE_SID, p);
+
+	return true;
+}
+
 /**
  * dump_tasks - dump current memory state of all system tasks
  * @mem: current's memory controller, if constrained
@@ -522,6 +666,8 @@ void mem_cgroup_out_of_memory(struct mem
 	check_panic_on_oom(CONSTRAINT_MEMCG, gfp_mask, 0, NULL);
 	limit = mem_cgroup_get_limit(mem) >> PAGE_SHIFT;
 	read_lock(&tasklist_lock);
+	if (fork_bomb_detection(limit, mem, NULL))
+		goto out;
 retry:
 	p = select_bad_process(&points, limit, mem, NULL);
 	if (!p || PTR_ERR(p) == -1UL)
@@ -698,6 +844,8 @@ void out_of_memory(struct zonelist *zone
 			goto out;
 	}
 
+	if (fork_bomb_detection(totalpages, NULL, mpol_mask))
+		goto out;
 retry:
 	p = select_bad_process(&points, totalpages, NULL, mpol_mask);
 	if (PTR_ERR(p) == -1UL)
Index: mmotm-temp/include/linux/mm_types.h
===================================================================
--- mmotm-temp.orig/include/linux/mm_types.h
+++ mmotm-temp/include/linux/mm_types.h
@@ -317,6 +317,9 @@ struct mm_struct {
 #ifdef CONFIG_TRANSPARENT_HUGEPAGE
 	pgtable_t pmd_huge_pte; /* protected by page_table_lock */
 #endif
+	/* fork bomb detector */
+	unsigned int fork_bomb_score;
+	unsigned int fork_bomb_family;
 };
 
 /* Future-safe accessor for struct mm_struct's cpu_vm_mask. */
Index: mmotm-temp/include/linux/sched.h
===================================================================
--- mmotm-temp.orig/include/linux/sched.h
+++ mmotm-temp/include/linux/sched.h
@@ -2198,6 +2198,12 @@ static inline unsigned long wait_task_in
 #define for_each_process(p) \
 	for (p = &init_task ; (p = next_task(p)) != &init_task ; )
 
+/* can only be used under tasklist lock. This is heavy. */
+#define prev_task(p) \
+	list_entry((p)->tasks.prev, struct task_struct, tasks)
+#define for_each_process_reverse(p) \
+	for (p = &init_task; (p = prev_task(p)) != &init_task ; )
+
 extern bool current_is_single_threaded(void);
 
 /*

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Fight unfair telecom internet charges in Canada: sign http://stopthemeter.ca/
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [RFC][PATCH] fork bomb killer

[Kirill A. Shutemov]

On Tue, Mar 15, 2011 at 06:52:42PM +0900, KAMEZAWA Hiroyuki wrote:
> While testing Andrey's case, I confirmed I need to reboot the system by
> power off when I ran a fork-bomb. The speed of fork() is much faster
> than some smart killing as pkill(1) and oom-killer cannot reach the speed.
> 
> I wonder it's better to have a fork-bomb killer even if it's a just heuristic
> method. This is a one. This one works fine with Andrey's case and I don't need
> to reboot more. And I confirmed this can kill a case like
> 
> 	while True:
> 		os.fork()
> 
> BTW, does usual man see fork-bomb in a production system ?
> I saw only once which was caused be a shell script.
> 
> ==
> A fork bomb killer.
> 
> When fork-bomb runs, the system exhausts memory and we need to
> reboot the system, in usual. The oom-killer or admin's killall
> is slower than fork-bomb if system memory is exhausted.
> 
> So, fork-bomb-killer is appreciated even if it's a just heuristic.
> 
> This patch implements a heuristic for fork-bomb. The logic finds
> a fork bomb which
>  - has spawned 10+ tasks recently (10 min).
>  - aggregate score of bomb is larger than the baddest task's badness.
> 
> When fork-bomb found,
>  - new fork in the session under where fork bomb is will return -ENOMEM
>    for the next 30secs.

-EAGAIN is more appropiate, I think. At least -EAGAIN returns if
RLIMIT_NPROC resource limit was encountered.

Will the fork-bomb-killer work, if a fork-bomb calls setsid() before
fork()?

>  - all tasks of fork-bomb will be killed.
> 
> Note:
>  - I wonder I shoud add a sysctl knob for this.
> 
> Signed-off-by: KAMEZAWA Hiroyuki <kamezawa.hiroyu@jp.fujitsu.com>

-- 
 Kirill A. Shutemov

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Fight unfair telecom internet charges in Canada: sign http://stopthemeter.ca/
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [RFC][PATCH] fork bomb killer

[KAMEZAWA Hiroyuki]

On Tue, 15 Mar 2011 12:42:26 +0200
"Kirill A. Shutemov" <kirill@shutemov.name> wrote:

> On Tue, Mar 15, 2011 at 06:52:42PM +0900, KAMEZAWA Hiroyuki wrote:
> > While testing Andrey's case, I confirmed I need to reboot the system by
> > power off when I ran a fork-bomb. The speed of fork() is much faster
> > than some smart killing as pkill(1) and oom-killer cannot reach the speed.
> > 
> > I wonder it's better to have a fork-bomb killer even if it's a just heuristic
> > method. This is a one. This one works fine with Andrey's case and I don't need
> > to reboot more. And I confirmed this can kill a case like
> > 
> > 	while True:
> > 		os.fork()
> > 
> > BTW, does usual man see fork-bomb in a production system ?
> > I saw only once which was caused be a shell script.
> > 
> > ==
> > A fork bomb killer.
> > 
> > When fork-bomb runs, the system exhausts memory and we need to
> > reboot the system, in usual. The oom-killer or admin's killall
> > is slower than fork-bomb if system memory is exhausted.
> > 
> > So, fork-bomb-killer is appreciated even if it's a just heuristic.
> > 
> > This patch implements a heuristic for fork-bomb. The logic finds
> > a fork bomb which
> >  - has spawned 10+ tasks recently (10 min).
> >  - aggregate score of bomb is larger than the baddest task's badness.
> > 
> > When fork-bomb found,
> >  - new fork in the session under where fork bomb is will return -ENOMEM
> >    for the next 30secs.
> 
> -EAGAIN is more appropiate, I think. At least -EAGAIN returns if
> RLIMIT_NPROC resource limit was encountered.
> 
> Will the fork-bomb-killer work, if a fork-bomb calls setsid() before
> fork()?
> 

This function just kills "young" children and cannot guarantee the core
of fork-bomb will be killed. By limiting fork() in the fork-bomb session
by -ENOMEM,  I hope careless fork-bomb will die. Then, I selected -ENOMEM
rather than -EAGAIN. By -ENOMEM, session leader (and user) can see there
was memory shortage.

Thanks,
-Kame



--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Fight unfair telecom internet charges in Canada: sign http://stopthemeter.ca/
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [RFC][PATCH] fork bomb killer

[Oleg Nesterov]

On 03/15, KAMEZAWA Hiroyuki wrote:
>
> I wonder it's better to have a fork-bomb killer

I am not going do discuss the idea, I never know when it comes to the
new features. Although personally I think this makes sense.

Just a couple of nits about the patch itself. Which I didn't read carefully
yet ;)

> +extern struct pid *fork_bomb_session;
> +static inline bool in_fork_bomb(void)
> +{
> +	return task_session(current) == fork_bomb_session;
> +}

Well, at first glance it is easy to write the fork-bomb which does setsid()...

> --- mmotm-temp.orig/kernel/fork.c
> +++ mmotm-temp/kernel/fork.c
> @@ -1417,6 +1417,8 @@ long do_fork(unsigned long clone_flags,
>  			return -EPERM;
>  	}
>
> +	if (in_fork_bomb())
> +		return -ENOMEM;

This is not clear to me. fork_bomb_detection() does do_each_pid_task(SID)
and sends SIGKILL to the hostile processes. After that none of the killed
processes can fork. Assuming the "bomb_task" was detected correctly, why
do we punish the whole session?

Once again, I didn't read the patch. This is the question, not the comment.

> +static bool is_ancestor(struct task_struct *t, struct task_struct *p)
> +{
> +	while (t != &init_task) {
> +		if (t == p)
> +			return true;
> +		t = t->real_parent;
> +	}
> +	return false;
> +}

No, this is not right. In fact, in theory this can crash if /sbin/init is
multithreaded. This needs same_thread_group() istead of "==" or "!=". Or
it should use t->real_parent->group_leader, assuming that both t and p
are the group-leaders (this seems to be true).

IOW. If a main thream M does pthread_create() and creates the thread T,
and T forks the child C after that, then C->real_parent == T, not M.

> +static bool fork_bomb_detection(unsigned long totalpages, struct mem_cgroup *mem,
> +		const nodemask_t *nodemask)
> +{
> ...
> +
> +	fork_bomb_session = task_session(bomb_task);

Hmm. In theory this needs fork_bomb_session = get_pid(task_session()).
Otherwise, all tasks in this session can be killed or can exit before
forkbomb_timeout runs. In this case this pid's memory can be reused
and in in_fork_bomb() can be false positive.

> +	INIT_DELAYED_WORK(&forkbomb_timeout, clear_fork_bomb);

OK, we already checked that fork_bomb_session == NULL. But isn't it
possible that multiple threads call fork_bomb_detection() at the same
time? We have sysrq_handle_moom, and __alloc_pages_may_oom() can lock
different zonelist's. No?

> +	 * Now, we found a bomb task. kill all children of bomb_task.

Again, this is not clear to me. We could literally kill all children,
why do we scan the session instead?

> +	do_each_pid_task(bomb_session, PIDTYPE_SID, p) {
> +
> +		start_time = timespec_to_jiffies(&p->start_time);
> +		start_time += fork_bomb_thresh;
> +
> +		if (!thread_group_leader(p))
> +			continue;

This is unneded, it must be thread_group_leader().

Oleg.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Fight unfair telecom internet charges in Canada: sign http://stopthemeter.ca/
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [RFC][PATCH] fork bomb killer

[KAMEZAWA Hiroyuki]

On Tue, 15 Mar 2011 15:33:57 +0100
Oleg Nesterov <oleg@redhat.com> wrote:

> On 03/15, KAMEZAWA Hiroyuki wrote:
> >
> > I wonder it's better to have a fork-bomb killer
> 
> I am not going do discuss the idea, I never know when it comes to the
> new features. Although personally I think this makes sense.
> 
> Just a couple of nits about the patch itself. Which I didn't read carefully
> yet ;)
> 

Thank you for review. 

> > +extern struct pid *fork_bomb_session;
> > +static inline bool in_fork_bomb(void)
> > +{
> > +	return task_session(current) == fork_bomb_session;
> > +}
> 
> Well, at first glance it is easy to write the fork-bomb which does setsid()...
> 
This is for disallowing new fork() in guilty session.

But yes, setsid script can kill the system. I'll leave this check (with improvement)
but will try to remove session check in killing loop.

I never think 'a carefully programmed fork-bomb to crash system' can be 
catched. But...

I'd like to catch all cases in wikipedia, finally ;)
http://en.wikipedia.org/wiki/Fork_bomb
Now, I can't.



> > --- mmotm-temp.orig/kernel/fork.c
> > +++ mmotm-temp/kernel/fork.c
> > @@ -1417,6 +1417,8 @@ long do_fork(unsigned long clone_flags,
> >  			return -EPERM;
> >  	}
> >
> > +	if (in_fork_bomb())
> > +		return -ENOMEM;
> 
> This is not clear to me. fork_bomb_detection() does do_each_pid_task(SID)
> and sends SIGKILL to the hostile processes. After that none of the killed
> processes can fork. Assuming the "bomb_task" was detected correctly, why
> do we punish the whole session?
> 
> Once again, I didn't read the patch. This is the question, not the comment.
> 

This killer kills only young tasks. So, we can't guarantee we removed all
bombs. I'd like to stop new bomb for a while.




> > +static bool is_ancestor(struct task_struct *t, struct task_struct *p)
> > +{
> > +	while (t != &init_task) {
> > +		if (t == p)
> > +			return true;
> > +		t = t->real_parent;
> > +	}
> > +	return false;
> > +}
> 
> No, this is not right. In fact, in theory this can crash if /sbin/init is
> multithreaded. This needs same_thread_group() istead of "==" or "!=". Or
> it should use t->real_parent->group_leader, assuming that both t and p
> are the group-leaders (this seems to be true).
> 
> IOW. If a main thream M does pthread_create() and creates the thread T,
> and T forks the child C after that, then C->real_parent == T, not M.
> 

I'll fix this.


> > +static bool fork_bomb_detection(unsigned long totalpages, struct mem_cgroup *mem,
> > +		const nodemask_t *nodemask)
> > +{
> > ...
> > +
> > +	fork_bomb_session = task_session(bomb_task);
> 
> Hmm. In theory this needs fork_bomb_session = get_pid(task_session()).
> Otherwise, all tasks in this session can be killed or can exit before
> forkbomb_timeout runs. In this case this pid's memory can be reused
> and in in_fork_bomb() can be false positive.
> 

ok, will fix.


> > +	INIT_DELAYED_WORK(&forkbomb_timeout, clear_fork_bomb);
> 
> OK, we already checked that fork_bomb_session == NULL. But isn't it
> possible that multiple threads call fork_bomb_detection() at the same
> time? We have sysrq_handle_moom, and __alloc_pages_may_oom() can lock
> different zonelist's. No?
> 

Hmm, yes. I'll add some lock. (I really forgot sysrq...thank you.)


> > +	 * Now, we found a bomb task. kill all children of bomb_task.
> 
> Again, this is not clear to me. We could literally kill all children,
> why do we scan the session instead?
> 

I'll write a process tree walk code and remove session scan.



> > +	do_each_pid_task(bomb_session, PIDTYPE_SID, p) {
> > +
> > +		start_time = timespec_to_jiffies(&p->start_time);
> > +		start_time += fork_bomb_thresh;
> > +
> > +		if (!thread_group_leader(p))
> > +			continue;
> 
> This is unneded, it must be thread_group_leader().
> 
Ok.

Thanks,
-Kame

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Fight unfair telecom internet charges in Canada: sign http://stopthemeter.ca/
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>