Add a test for out-of-bounds write in trie_get_next_key() when a full
path from root to leaf exists and bpf_map_get_next_key() is called
with the leaf node. It may crashes the kernel on failure, so please
run in a VM.

Signed-off-by: Byeonguk Jeong <jungbu2855@gmail.com>
---
 .../bpf/map_tests/lpm_trie_map_get_next_key.c | 115 ++++++++++++++++++
 1 file changed, 115 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/map_tests/lpm_trie_map_get_next_key.c

diff --git a/tools/testing/selftests/bpf/map_tests/lpm_trie_map_get_next_key.c b/tools/testing/selftests/bpf/map_tests/lpm_trie_map_get_next_key.c
new file mode 100644
index 000000000000..85b916b69411
--- /dev/null
+++ b/tools/testing/selftests/bpf/map_tests/lpm_trie_map_get_next_key.c
@@ -0,0 +1,115 @@
+// SPDX-License-Identifier: GPL-2.0
+
+/*
+ * WARNING
+ * -------
+ *  This test suite may crash the kernel, thus should be run in a VM.
+ */
+
+#define _GNU_SOURCE
+#include <linux/bpf.h>
+#include <stdio.h>
+#include <stdbool.h>
+#include <unistd.h>
+#include <errno.h>
+#include <stdlib.h>
+#include <string.h>
+#include <pthread.h>
+
+#include <bpf/bpf.h>
+#include <bpf/libbpf.h>
+
+#include <test_maps.h>
+
+struct test_lpm_key {
+	__u32 prefix;
+	__u32 data;
+};
+
+struct get_next_key_ctx {
+	struct test_lpm_key key;
+	bool start;
+	bool stop;
+	int map_fd;
+	int loop;
+};
+
+static void *get_next_key_fn(void *arg)
+{
+	struct get_next_key_ctx *ctx = arg;
+	struct test_lpm_key next_key;
+	int i;
+
+	while (!ctx->start)
+		usleep(1);
+
+	while (!ctx->stop && i++ < ctx->loop)
+		bpf_map_get_next_key(ctx->map_fd, &ctx->key, &next_key);
+
+	return NULL;
+}
+
+static void abort_get_next_key(struct get_next_key_ctx *ctx, pthread_t *tids,
+			       unsigned int nr)
+{
+	unsigned int i;
+
+	ctx->stop = true;
+	ctx->start = true;
+	for (i = 0; i < nr; i++)
+		pthread_join(tids[i], NULL);
+}
+
+/* This test aims to prevent regression of future. As long as the kernel does
+ * not panic, it is considered as success.
+ */
+void test_lpm_trie_map_get_next_key(void)
+{
+#define MAX_NR_THREADS 256
+	LIBBPF_OPTS(bpf_map_create_opts, create_opts,
+		    .map_flags = BPF_F_NO_PREALLOC);
+	struct test_lpm_key key = {};
+	__u32 val = 0;
+	int map_fd;
+	const __u32 max_prefixlen = 8 * (sizeof(key) - sizeof(key.prefix));
+	const __u32 max_entries = max_prefixlen + 1;
+	unsigned int i, nr = MAX_NR_THREADS, loop = 4096;
+	pthread_t tids[MAX_NR_THREADS];
+	struct get_next_key_ctx ctx;
+	int err;
+
+	map_fd = bpf_map_create(BPF_MAP_TYPE_LPM_TRIE, "lpm_trie_map",
+				sizeof(struct test_lpm_key), sizeof(__u32),
+				max_entries, &create_opts);
+	CHECK(map_fd == -1, "bpf_map_create(), error:%s\n",
+	      strerror(errno));
+
+	for (i = 0; i <= max_prefixlen; i++) {
+		key.prefix = i;
+		err = bpf_map_update_elem(map_fd, &key, &val, BPF_ANY);
+		CHECK(err, "bpf_map_update_elem()", "error:%s\n",
+		      strerror(errno));
+	}
+
+	ctx.start = false;
+	ctx.stop = false;
+	ctx.map_fd = map_fd;
+	ctx.loop = loop;
+	memcpy(&ctx.key, &key, sizeof(key));
+
+	for (i = 0; i < nr; i++) {
+		err = pthread_create(&tids[i], NULL, get_next_key_fn, &ctx);
+		if (err) {
+			abort_get_next_key(&ctx, tids, i);
+			CHECK(err, "pthread_create", "error %d\n", err);
+		}
+	}
+
+	ctx.start = true;
+	for (i = 0; i < nr; i++)
+		pthread_join(tids[i], NULL);
+
+	printf("%s:PASS\n", __func__);
+
+	close(map_fd);
+}
-- 
2.43.5

Hi,

On 10/24/2024 5:08 PM, Byeonguk Jeong wrote:
> Add a test for out-of-bounds write in trie_get_next_key() when a full
> path from root to leaf exists and bpf_map_get_next_key() is called
> with the leaf node. It may crashes the kernel on failure, so please
> run in a VM.
>
> Signed-off-by: Byeonguk Jeong <jungbu2855@gmail.com>
> ---
>  .../bpf/map_tests/lpm_trie_map_get_next_key.c | 115 ++++++++++++++++++
>  1 file changed, 115 insertions(+)
>  create mode 100644 tools/testing/selftests/bpf/map_tests/lpm_trie_map_get_next_key.c
>
> diff --git a/tools/testing/selftests/bpf/map_tests/lpm_trie_map_get_next_key.c b/tools/testing/selftests/bpf/map_tests/lpm_trie_map_get_next_key.c
> new file mode 100644
> index 000000000000..85b916b69411
> --- /dev/null
> +++ b/tools/testing/selftests/bpf/map_tests/lpm_trie_map_get_next_key.c
> @@ -0,0 +1,115 @@
> +// SPDX-License-Identifier: GPL-2.0
> +
> +/*
> + * WARNING
> + * -------
> + *  This test suite may crash the kernel, thus should be run in a VM.
> + */
> +

The comments above are unnecessary, please remove it.
> +#define _GNU_SOURCE
> +#include <linux/bpf.h>
> +#include <stdio.h>
> +#include <stdbool.h>
> +#include <unistd.h>
> +#include <errno.h>
> +#include <stdlib.h>
> +#include <string.h>
> +#include <pthread.h>
> +
> +#include <bpf/bpf.h>
> +#include <bpf/libbpf.h>
> +
> +#include <test_maps.h>
> +
> +struct test_lpm_key {
> +	__u32 prefix;
> +	__u32 data;
> +};
> +
> +struct get_next_key_ctx {
> +	struct test_lpm_key key;
> +	bool start;
> +	bool stop;
> +	int map_fd;
> +	int loop;
> +};
> +
> +static void *get_next_key_fn(void *arg)
> +{
> +	struct get_next_key_ctx *ctx = arg;
> +	struct test_lpm_key next_key;
> +	int i;

int i = 0;
> +
> +	while (!ctx->start)
> +		usleep(1);
> +
> +	while (!ctx->stop && i++ < ctx->loop)
> +		bpf_map_get_next_key(ctx->map_fd, &ctx->key, &next_key);
> +
> +	return NULL;
> +}
> +
> +static void abort_get_next_key(struct get_next_key_ctx *ctx, pthread_t *tids,
> +			       unsigned int nr)
> +{
> +	unsigned int i;
> +
> +	ctx->stop = true;
> +	ctx->start = true;
> +	for (i = 0; i < nr; i++)
> +		pthread_join(tids[i], NULL);
> +}
> +
> +/* This test aims to prevent regression of future. As long as the kernel does
> + * not panic, it is considered as success.
> + */
> +void test_lpm_trie_map_get_next_key(void)
> +{
> +#define MAX_NR_THREADS 256

Are 8 threads sufficient to reproduce the problem ?
> +	LIBBPF_OPTS(bpf_map_create_opts, create_opts,
> +		    .map_flags = BPF_F_NO_PREALLOC);
> +	struct test_lpm_key key = {};
> +	__u32 val = 0;
> +	int map_fd;
> +	const __u32 max_prefixlen = 8 * (sizeof(key) - sizeof(key.prefix));
> +	const __u32 max_entries = max_prefixlen + 1;
> +	unsigned int i, nr = MAX_NR_THREADS, loop = 4096;
> +	pthread_t tids[MAX_NR_THREADS];
> +	struct get_next_key_ctx ctx;
> +	int err;
> +
> +	map_fd = bpf_map_create(BPF_MAP_TYPE_LPM_TRIE, "lpm_trie_map",
> +				sizeof(struct test_lpm_key), sizeof(__u32),
> +				max_entries, &create_opts);
> +	CHECK(map_fd == -1, "bpf_map_create(), error:%s\n",
> +	      strerror(errno));

CHECK(map_fd == -1, "bpf_map_create()", "error:%s\n", strerror(errno));
It seems you didn't build test it.
> +
> +	for (i = 0; i <= max_prefixlen; i++) {
> +		key.prefix = i;
> +		err = bpf_map_update_elem(map_fd, &key, &val, BPF_ANY);
> +		CHECK(err, "bpf_map_update_elem()", "error:%s\n",
> +		      strerror(errno));
> +	}
> +
> +	ctx.start = false;
> +	ctx.stop = false;
> +	ctx.map_fd = map_fd;
> +	ctx.loop = loop;
> +	memcpy(&ctx.key, &key, sizeof(key));
> +
> +	for (i = 0; i < nr; i++) {
> +		err = pthread_create(&tids[i], NULL, get_next_key_fn, &ctx);
> +		if (err) {
> +			abort_get_next_key(&ctx, tids, i);
> +			CHECK(err, "pthread_create", "error %d\n", err);
> +		}
> +	}
> +
> +	ctx.start = true;
> +	for (i = 0; i < nr; i++)
> +		pthread_join(tids[i], NULL);
> +
> +	printf("%s:PASS\n", __func__);
> +
> +	close(map_fd);
> +}

Hi Byeonguk,

On 10/24/24 11:08 AM, Byeonguk Jeong wrote:
> Add a test for out-of-bounds write in trie_get_next_key() when a full
> path from root to leaf exists and bpf_map_get_next_key() is called
> with the leaf node. It may crashes the kernel on failure, so please
> run in a VM.
> 
> Signed-off-by: Byeonguk Jeong <jungbu2855@gmail.com>

Could you submit the fix + this selftest as a 2-patch series, otherwise BPF CI
cannot test both in combination (pls make sure subject has [PATCH bpf] so that
our CI adds this on top of the bpf tree).

Right now the CI selftest build threw an error:

   /tmp/work/bpf/bpf/tools/testing/selftests/bpf/map_tests/lpm_trie_map_get_next_key.c: In function ‘test_lpm_trie_map_get_next_key’:
   /tmp/work/bpf/bpf/tools/testing/selftests/bpf/map_tests/lpm_trie_map_get_next_key.c:84:9: error: format not a string literal and no format arguments [-Werror=format-security]
      84 |         CHECK(map_fd == -1, "bpf_map_create(), error:%s\n",
         |         ^~~~~
     TEST-OBJ [test_maps] task_storage_map.test.o
     TEST-OBJ [test_progs] access_variable_array.test.o
   cc1: all warnings being treated as errors
     TEST-OBJ [test_progs] align.test.o
     TEST-OBJ [test_progs] arena_atomics.test.o
   make: *** [Makefile:765: /tmp/work/bpf/bpf/tools/testing/selftests/bpf/lpm_trie_map_get_next_key.test.o] Error 1
   make: *** Waiting for unfinished jobs....
     GEN-SKEL [test_progs-no_alu32] test_usdt.skel.h
   make: Leaving directory '/tmp/work/bpf/bpf/tools/testing/selftests/bpf'

Also on quick glance, please use ASSERT_*() macros instead of CHECK() as the
latter is deprecated.

Thanks,
Daniel

Hi Daniel,

Okay, I will submit them in a series of patches. Btw, ASSERT_* macros
are not defined for map_tests. Should I add the definitions for them,
or just go with CHECK?

Thanks,
Byeonguk

On Thu, Oct 24, 2024 at 11:41:19AM +0200, Daniel Borkmann wrote:
> Hi Byeonguk,
> 
> On 10/24/24 11:08 AM, Byeonguk Jeong wrote:
> > Add a test for out-of-bounds write in trie_get_next_key() when a full
> > path from root to leaf exists and bpf_map_get_next_key() is called
> > with the leaf node. It may crashes the kernel on failure, so please
> > run in a VM.
> > 
> > Signed-off-by: Byeonguk Jeong <jungbu2855@gmail.com>
> 
> Could you submit the fix + this selftest as a 2-patch series, otherwise BPF CI
> cannot test both in combination (pls make sure subject has [PATCH bpf] so that
> our CI adds this on top of the bpf tree).
> 
> Right now the CI selftest build threw an error:
> 
>   /tmp/work/bpf/bpf/tools/testing/selftests/bpf/map_tests/lpm_trie_map_get_next_key.c: In function ‘test_lpm_trie_map_get_next_key’:
>   /tmp/work/bpf/bpf/tools/testing/selftests/bpf/map_tests/lpm_trie_map_get_next_key.c:84:9: error: format not a string literal and no format arguments [-Werror=format-security]
>      84 |         CHECK(map_fd == -1, "bpf_map_create(), error:%s\n",
>         |         ^~~~~
>     TEST-OBJ [test_maps] task_storage_map.test.o
>     TEST-OBJ [test_progs] access_variable_array.test.o
>   cc1: all warnings being treated as errors
>     TEST-OBJ [test_progs] align.test.o
>     TEST-OBJ [test_progs] arena_atomics.test.o
>   make: *** [Makefile:765: /tmp/work/bpf/bpf/tools/testing/selftests/bpf/lpm_trie_map_get_next_key.test.o] Error 1
>   make: *** Waiting for unfinished jobs....
>     GEN-SKEL [test_progs-no_alu32] test_usdt.skel.h
>   make: Leaving directory '/tmp/work/bpf/bpf/tools/testing/selftests/bpf'
> 
> Also on quick glance, please use ASSERT_*() macros instead of CHECK() as the
> latter is deprecated.
> 
> Thanks,
> Daniel

Hi,

On 10/25/2024 6:26 AM, Byeonguk Jeong wrote:
> Hi Daniel,
>
> Okay, I will submit them in a series of patches. Btw, ASSERT_* macros
> are not defined for map_tests. Should I add the definitions for them,
> or just go with CHECK?

For tests in map_tests, I think using CHECK() will be fine.
>
> Thanks,
> Byeonguk
>
> On Thu, Oct 24, 2024 at 11:41:19AM +0200, Daniel Borkmann wrote:
>> Hi Byeonguk,
>>
>> On 10/24/24 11:08 AM, Byeonguk Jeong wrote:
>>> Add a test for out-of-bounds write in trie_get_next_key() when a full
>>> path from root to leaf exists and bpf_map_get_next_key() is called
>>> with the leaf node. It may crashes the kernel on failure, so please
>>> run in a VM.
>>>
>>> Signed-off-by: Byeonguk Jeong <jungbu2855@gmail.com>
>> Could you submit the fix + this selftest as a 2-patch series, otherwise BPF CI
>> cannot test both in combination (pls make sure subject has [PATCH bpf] so that
>> our CI adds this on top of the bpf tree).
>>
>> Right now the CI selftest build threw an error:
>>
>>   /tmp/work/bpf/bpf/tools/testing/selftests/bpf/map_tests/lpm_trie_map_get_next_key.c: In function ‘test_lpm_trie_map_get_next_key’:
>>   /tmp/work/bpf/bpf/tools/testing/selftests/bpf/map_tests/lpm_trie_map_get_next_key.c:84:9: error: format not a string literal and no format arguments [-Werror=format-security]
>>      84 |         CHECK(map_fd == -1, "bpf_map_create(), error:%s\n",
>>         |         ^~~~~
>>     TEST-OBJ [test_maps] task_storage_map.test.o
>>     TEST-OBJ [test_progs] access_variable_array.test.o
>>   cc1: all warnings being treated as errors
>>     TEST-OBJ [test_progs] align.test.o
>>     TEST-OBJ [test_progs] arena_atomics.test.o
>>   make: *** [Makefile:765: /tmp/work/bpf/bpf/tools/testing/selftests/bpf/lpm_trie_map_get_next_key.test.o] Error 1
>>   make: *** Waiting for unfinished jobs....
>>     GEN-SKEL [test_progs-no_alu32] test_usdt.skel.h
>>   make: Leaving directory '/tmp/work/bpf/bpf/tools/testing/selftests/bpf'
>>
>> Also on quick glance, please use ASSERT_*() macros instead of CHECK() as the
>> latter is deprecated.
>>
>> Thanks,
>> Daniel
> .

On 10/25/24 1:54 PM, Hou Tao wrote:
> On 10/25/2024 6:26 AM, Byeonguk Jeong wrote:
>>
>> Okay, I will submit them in a series of patches. Btw, ASSERT_* macros
>> are not defined for map_tests. Should I add the definitions for them,
>> or just go with CHECK?
> 
> For tests in map_tests, I think using CHECK() will be fine.

Given there is no alternative infra, agree. Would be nice to convert this
over at some point.

Best,
Daniel