[PATCH bpf 1/2] bpf: Fix racing between bpf_timer_cancel_and_free and bpf_timer_cancel

[PATCH bpf 1/2] bpf: Fix racing between bpf_timer_cancel_and_free and bpf_timer_cancel

[Martin KaFai Lau]

From: Martin KaFai Lau <martin.lau@kernel.org>

The following race is possible between bpf_timer_cancel_and_free
and bpf_timer_cancel. It will lead a UAF on the timer->timer.

bpf_timer_cancel();
	spin_lock();
	t = timer->time;
	spin_unlock();

					bpf_timer_cancel_and_free();
						spin_lock();
						t = timer->timer;
						timer->timer = NULL;
						spin_unlock();
						hrtimer_cancel(&t->timer);
						kfree(t);

	/* UAF on t */
	hrtimer_cancel(&t->timer);

In bpf_timer_cancel_and_free, this patch frees the timer->timer
after a rcu grace period. This requires a rcu_head addition
to the "struct bpf_hrtimer". Another kfree(t) happens in bpf_timer_init,
this does not need a kfree_rcu because it is still under the
spin_lock and timer->timer has not been visible by others yet.

In bpf_timer_cancel, rcu_read_lock() is added because this helper
can be used in a non rcu critical section context (e.g. from
a sleepable bpf prog). Other timer->timer usages in helpers.c
have been audited, bpf_timer_cancel() is the only place where
timer->timer is used outside of the spin_lock.

Another solution considered is to mark a t->flag in bpf_timer_cancel
and clear it after hrtimer_cancel() is done.  In bpf_timer_cancel_and_free,
it busy waits for the flag to be cleared before kfree(t). This patch
goes with a straight forward solution and frees timer->timer after
a rcu grace period.

Fixes: b00628b1c7d5 ("bpf: Introduce bpf timers.")
Suggested-by: Alexei Starovoitov <ast@kernel.org>
Signed-off-by: Martin KaFai Lau <martin.lau@kernel.org>
---
 kernel/bpf/helpers.c | 5 ++++-
 1 file changed, 4 insertions(+), 1 deletion(-)

diff --git a/kernel/bpf/helpers.c b/kernel/bpf/helpers.c
index be72824f32b2..d19cd863d294 100644
--- a/kernel/bpf/helpers.c
+++ b/kernel/bpf/helpers.c
@@ -1101,6 +1101,7 @@ struct bpf_hrtimer {
 	struct bpf_prog *prog;
 	void __rcu *callback_fn;
 	void *value;
+	struct rcu_head rcu;
 };
 
 /* the actual struct hidden inside uapi struct bpf_timer */
@@ -1332,6 +1333,7 @@ BPF_CALL_1(bpf_timer_cancel, struct bpf_timer_kern *, timer)
 
 	if (in_nmi())
 		return -EOPNOTSUPP;
+	rcu_read_lock();
 	__bpf_spin_lock_irqsave(&timer->lock);
 	t = timer->timer;
 	if (!t) {
@@ -1353,6 +1355,7 @@ BPF_CALL_1(bpf_timer_cancel, struct bpf_timer_kern *, timer)
 	 * if it was running.
 	 */
 	ret = ret ?: hrtimer_cancel(&t->timer);
+	rcu_read_unlock();
 	return ret;
 }
 
@@ -1407,7 +1410,7 @@ void bpf_timer_cancel_and_free(void *val)
 	 */
 	if (this_cpu_read(hrtimer_running) != t)
 		hrtimer_cancel(&t->timer);
-	kfree(t);
+	kfree_rcu(t, rcu);
 }
 
 BPF_CALL_2(bpf_kptr_xchg, void *, map_value, void *, ptr)
-- 
2.34.1

[PATCH bpf 2/2] selftests/bpf: Test racing between bpf_timer_cancel_and_free and bpf_timer_cancel

[Martin KaFai Lau]

From: Martin KaFai Lau <martin.lau@kernel.org>

This selftest is based on a Alexei's test adopted from an internal
user to troubleshoot another bug. During this exercise, a separate
racing bug was discovered between bpf_timer_cancel_and_free
and bpf_timer_cancel. The details can be found in the previous
patch.

This patch is to add a selftest that can trigger the bug.
I can trigger the UAF everytime in my qemu setup with KASAN. The idea
is to have multiple user space threads running in a tight loop to exercise
both bpf_map_update_elem (which calls into bpf_timer_cancel_and_free)
and bpf_timer_cancel.

Signed-off-by: Martin KaFai Lau <martin.lau@kernel.org>
---
 .../testing/selftests/bpf/prog_tests/timer.c  | 35 ++++++++++++++++++-
 tools/testing/selftests/bpf/progs/timer.c     | 34 +++++++++++++++++-
 2 files changed, 67 insertions(+), 2 deletions(-)

diff --git a/tools/testing/selftests/bpf/prog_tests/timer.c b/tools/testing/selftests/bpf/prog_tests/timer.c
index 760ad96b4be0..d66687f1ee6a 100644
--- a/tools/testing/selftests/bpf/prog_tests/timer.c
+++ b/tools/testing/selftests/bpf/prog_tests/timer.c
@@ -4,10 +4,29 @@
 #include "timer.skel.h"
 #include "timer_failure.skel.h"
 
+#define NUM_THR 8
+
+static void *spin_lock_thread(void *arg)
+{
+	int i, err, prog_fd = *(int *)arg;
+	LIBBPF_OPTS(bpf_test_run_opts, topts);
+
+	for (i = 0; i < 10000; i++) {
+		err = bpf_prog_test_run_opts(prog_fd, &topts);
+		if (!ASSERT_OK(err, "test_run_opts err") ||
+		    !ASSERT_OK(topts.retval, "test_run_opts retval"))
+			break;
+	}
+
+	pthread_exit(arg);
+}
+
 static int timer(struct timer *timer_skel)
 {
-	int err, prog_fd;
+	int i, err, prog_fd;
 	LIBBPF_OPTS(bpf_test_run_opts, topts);
+	pthread_t thread_id[NUM_THR];
+	void *ret;
 
 	err = timer__attach(timer_skel);
 	if (!ASSERT_OK(err, "timer_attach"))
@@ -43,6 +62,20 @@ static int timer(struct timer *timer_skel)
 	/* check that code paths completed */
 	ASSERT_EQ(timer_skel->bss->ok, 1 | 2 | 4, "ok");
 
+	prog_fd = bpf_program__fd(timer_skel->progs.race);
+	for (i = 0; i < NUM_THR; i++) {
+		err = pthread_create(&thread_id[i], NULL,
+				     &spin_lock_thread, &prog_fd);
+		if (!ASSERT_OK(err, "pthread_create"))
+			break;
+	}
+
+	while (i) {
+		err = pthread_join(thread_id[--i], &ret);
+		if (ASSERT_OK(err, "pthread_join"))
+			ASSERT_EQ(ret, (void *)&prog_fd, "pthread_join");
+	}
+
 	return 0;
 }
 
diff --git a/tools/testing/selftests/bpf/progs/timer.c b/tools/testing/selftests/bpf/progs/timer.c
index 8b946c8188c6..f615da97df26 100644
--- a/tools/testing/selftests/bpf/progs/timer.c
+++ b/tools/testing/selftests/bpf/progs/timer.c
@@ -51,7 +51,8 @@ struct {
 	__uint(max_entries, 1);
 	__type(key, int);
 	__type(value, struct elem);
-} abs_timer SEC(".maps"), soft_timer_pinned SEC(".maps"), abs_timer_pinned SEC(".maps");
+} abs_timer SEC(".maps"), soft_timer_pinned SEC(".maps"), abs_timer_pinned SEC(".maps"),
+	race_array SEC(".maps");
 
 __u64 bss_data;
 __u64 abs_data;
@@ -390,3 +391,34 @@ int BPF_PROG2(test5, int, a)
 
 	return 0;
 }
+
+static int race_timer_callback(void *race_array, int *race_key, struct bpf_timer *timer)
+{
+	bpf_timer_start(timer, 1000000, 0);
+	return 0;
+}
+
+SEC("syscall")
+int race(void *ctx)
+{
+	struct bpf_timer *timer;
+	int err, race_key = 0;
+	struct elem init;
+
+	__builtin_memset(&init, 0, sizeof(struct elem));
+	bpf_map_update_elem(&race_array, &race_key, &init, BPF_ANY);
+
+	timer = bpf_map_lookup_elem(&race_array, &race_key);
+	if (!timer)
+		return 1;
+
+	err = bpf_timer_init(timer, &race_array, CLOCK_MONOTONIC);
+	if (err && err != -EBUSY)
+		return 1;
+
+	bpf_timer_set_callback(timer, race_timer_callback);
+	bpf_timer_start(timer, 0, 0);
+	bpf_timer_cancel(timer);
+
+	return 0;
+}
-- 
2.34.1

Re: [PATCH bpf 2/2] selftests/bpf: Test racing between bpf_timer_cancel_and_free and bpf_timer_cancel

[Hou Tao]

On 2/16/2024 5:12 AM, Martin KaFai Lau wrote:
> From: Martin KaFai Lau <martin.lau@kernel.org>
>
> This selftest is based on a Alexei's test adopted from an internal
> user to troubleshoot another bug. During this exercise, a separate
> racing bug was discovered between bpf_timer_cancel_and_free
> and bpf_timer_cancel. The details can be found in the previous
> patch.
>
> This patch is to add a selftest that can trigger the bug.
> I can trigger the UAF everytime in my qemu setup with KASAN. The idea
> is to have multiple user space threads running in a tight loop to exercise
> both bpf_map_update_elem (which calls into bpf_timer_cancel_and_free)
> and bpf_timer_cancel.
>
> Signed-off-by: Martin KaFai Lau <martin.lau@kernel.org>

Acked-by: Hou Tao <houtao1@huawei.com>

Re: [PATCH bpf 1/2] bpf: Fix racing between bpf_timer_cancel_and_free and bpf_timer_cancel

[Hou Tao]

On 2/16/2024 5:12 AM, Martin KaFai Lau wrote:
> From: Martin KaFai Lau <martin.lau@kernel.org>
>
> The following race is possible between bpf_timer_cancel_and_free
> and bpf_timer_cancel. It will lead a UAF on the timer->timer.
>
> bpf_timer_cancel();
> 	spin_lock();
> 	t = timer->time;
> 	spin_unlock();
>
> 					bpf_timer_cancel_and_free();
> 						spin_lock();
> 						t = timer->timer;
> 						timer->timer = NULL;
> 						spin_unlock();
> 						hrtimer_cancel(&t->timer);
> 						kfree(t);
>
> 	/* UAF on t */
> 	hrtimer_cancel(&t->timer);
>
> In bpf_timer_cancel_and_free, this patch frees the timer->timer
> after a rcu grace period. This requires a rcu_head addition
> to the "struct bpf_hrtimer". Another kfree(t) happens in bpf_timer_init,
> this does not need a kfree_rcu because it is still under the
> spin_lock and timer->timer has not been visible by others yet.
>
> In bpf_timer_cancel, rcu_read_lock() is added because this helper
> can be used in a non rcu critical section context (e.g. from
> a sleepable bpf prog). Other timer->timer usages in helpers.c
> have been audited, bpf_timer_cancel() is the only place where
> timer->timer is used outside of the spin_lock.
>
> Another solution considered is to mark a t->flag in bpf_timer_cancel
> and clear it after hrtimer_cancel() is done.  In bpf_timer_cancel_and_free,
> it busy waits for the flag to be cleared before kfree(t). This patch
> goes with a straight forward solution and frees timer->timer after
> a rcu grace period.
>
> Fixes: b00628b1c7d5 ("bpf: Introduce bpf timers.")
> Suggested-by: Alexei Starovoitov <ast@kernel.org>
> Signed-off-by: Martin KaFai Lau <martin.lau@kernel.org>

Acked-by: Hou Tao <houtao1@huawei.com>

Re: [PATCH bpf 1/2] bpf: Fix racing between bpf_timer_cancel_and_free and bpf_timer_cancel

[patchwork-bot+netdevbpf]

Hello:

This series was applied to bpf/bpf.git (master)
by Daniel Borkmann <daniel@iogearbox.net>:

On Thu, 15 Feb 2024 13:12:17 -0800 you wrote:
> From: Martin KaFai Lau <martin.lau@kernel.org>
> 
> The following race is possible between bpf_timer_cancel_and_free
> and bpf_timer_cancel. It will lead a UAF on the timer->timer.
> 
> bpf_timer_cancel();
> 	spin_lock();
> 	t = timer->time;
> 	spin_unlock();
> 
> [...]

Here is the summary with links:
  - [bpf,1/2] bpf: Fix racing between bpf_timer_cancel_and_free and bpf_timer_cancel
    https://git.kernel.org/bpf/bpf/c/0281b919e175
  - [bpf,2/2] selftests/bpf: Test racing between bpf_timer_cancel_and_free and bpf_timer_cancel
    https://git.kernel.org/bpf/bpf/c/3f00e4a9c96f

You are awesome, thank you!
-- 
Deet-doot-dot, I am a bot.
https://korg.docs.kernel.org/patchwork/pwbot.html