bpf: Fix out-of-bounds write in trie_get_next_key()
Subsystems (3)
PATCH v2 1/2 bpf: Fix out-of-bounds write in trie_get_next_key()
trie_get_next_key() allocates a node stack with size trie->max_prefixlen, while it writes (trie->max_prefixlen + 1) nodes to the stack when it has full paths from the root to leaves. For example, consider a trie with max_prefixlen is 8, and the nodes with key 0x00/0, 0x00/1, 0x00/2, ... 0x00/8 inserted. Subsequent calls to trie_get_next_key with _key with .prefixlen = 8 make 9 nodes be written on the node stack with size 8.
---
v1 -> v2: nothing changed
--- kernel/bpf/lpm_trie.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
kernel/bpf/lpm_trie.c +1 -1
@@ -655,7 +655,7 @@ static int trie_get_next_key(struct bpf_map *map, void *_key, void *_next_key)if (!key || key->prefixlen > trie->max_prefixlen) goto find_leftmost; - node_stack =kmalloc_array (trie->max_prefixlen, + node_stack =kmalloc_array (trie->max_prefixlen +1 ,sizeof (struct lpm_trie_node *),GFP_ATOMIC | __GFP_NOWARN);if (!node_stack)
Signature · 1 line
2.43.5
PATCH v2 2/2 selftests/bpf: Add test for trie_get_next_key()
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.
---
v1 -> v2:
- Fixed a build error.
- Removed unnecessary comments about crash-on-failure warning.
- Fix a variable to be initialized before using it.
--- .../bpf/map_tests/lpm_trie_map_get_next_key.c | 109 ++++++++++++++++++ 1 file changed, 109 insertions(+) create mode 100644 tools/testing/selftests/bpf/map_tests/lpm_trie_map_get_next_key.c
tools/testing/selftests/bpf/map_tests/lpm_trie_map_get_next_key.c new file +109 -0
@@ -0,0 +1,109 @@ +// SPDX-License-Identifier: GPL-2.0 + +#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 =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 8 +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 =65536 ; +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); +}
Signature · 1 line
2.43.5
Re: [PATCH v2 bpf 2/2] selftests/bpf: Add test for trie_get_next_key()
Quoted 5 lines · Byeonguk Jeong
Add a test for out-of-bounds write in
trie_get_next_key()when a full path from root to leaf exists andbpf_map_get_next_key()is called with the leaf node. It may crashes the kernel on failure, so please run in a VM.
Quoted 7 lines
Signed-off-by Byeonguk Jeong <[email protected]>---
v1 -> v2:
- Fixed a build error.
- Removed unnecessary comments about crash-on-failure warning.
- Fix a variable to be initialized before using it.
---
Quoted 7 lines · Byeonguk Jeong
trie_get_next_key()allocates a node stack with sizetrie->max_prefixlen, while it writes (trie->max_prefixlen+ 1) nodes to the stack when it has full paths from the root to leaves. For example, consider a trie withmax_prefixlenis 8, and the nodes with key 0x00/0, 0x00/1, 0x00/2, ... 0x00/8 inserted. Subsequent calls totrie_get_next_keywith_keywith .prefixlen = 8 make 9 nodes be written on the node stack with size 8.
Quoted 5 lines
Fixes b471f2f1de8b ("bpf: implement MAP_GET_NEXT_KEY command for LPM_TRIE map")Signed-off-by Byeonguk Jeong <[email protected]>Reviewed-by Toke Høiland-Jørgensen <[email protected]>Tested-by Hou Tao <[email protected]>---
This series was applied to bpf/bpf.git (master) by Alexei Starovoitov <[email protected]>:
Hello:
This series was applied to bpf/bpf.git (master)
by Alexei Starovoitov <[email protected]>:
Quoted 8 lines · On Sat, 26 Oct 2024 14:02:43 +0900 you wrote:
trie_get_next_key()allocates a node stack with sizetrie->max_prefixlen, while it writes (trie->max_prefixlen+ 1) nodes to the stack when it has full paths from the root to leaves. For example, consider a trie withmax_prefixlenis 8, and the nodes with key 0x00/0, 0x00/1, 0x00/2, ... 0x00/8 inserted. Subsequent calls totrie_get_next_keywith_keywith .prefixlen = 8 make 9 nodes be written on the node stack with size 8.[...]
Here is the summary with links:
- [v2,bpf,1/2] bpf: Fix out-of-bounds write in trie_get_next_key()
https://git.kernel.org/bpf/bpf/c/13400ac8fb80 - [v2,bpf,2/2] selftests/bpf: Add test for trie_get_next_key() https://git.kernel.org/bpf/bpf/c/d7f214aeacb9
You are awesome, thank you!
Signature · 2 lines
Deet-doot-dot, I am a bot. https://korg.docs.kernel.org/patchwork/pwbot.html