[PATCH V2 bpf 0/2] Check bloom filter map value size

[PATCH V2 bpf 0/2] Check bloom filter map value size

[Andrei Matei]

v1->v2:
- prepend a patch addressing the bloom map specifically
- change low-level rejection error to EFAULT, to indicate a bug

Andrei Matei (2):
  bpf: Check bloom filter map value size
  bpf: Protect against int overflow for stack access size

 kernel/bpf/bloom_filter.c                           | 13 +++++++++++++
 kernel/bpf/verifier.c                               |  5 +++++
 .../selftests/bpf/prog_tests/bloom_filter_map.c     |  6 ++++++
 3 files changed, 24 insertions(+)

-- 
2.40.1

[PATCH V2 bpf 1/2] bpf: Check bloom filter map value size

[Andrei Matei]

This patch adds a missing check to bloom filter creating, rejecting
values above KMALLOC_MAX_SIZE. This brings the bloom map in line with
many other map types.

The lack of this protection can cause kernel crashes for value sizes
that overflow int's. Such a crash was caught by syzkaller. The next
patch adds more guard-rails at a lower level.

Signed-off-by: Andrei Matei <andreimatei1@gmail.com>
---
 kernel/bpf/bloom_filter.c                           | 13 +++++++++++++
 .../selftests/bpf/prog_tests/bloom_filter_map.c     |  6 ++++++
 2 files changed, 19 insertions(+)

diff --git a/kernel/bpf/bloom_filter.c b/kernel/bpf/bloom_filter.c
index addf3dd57b59..35e1ddca74d2 100644
--- a/kernel/bpf/bloom_filter.c
+++ b/kernel/bpf/bloom_filter.c
@@ -80,6 +80,18 @@ static int bloom_map_get_next_key(struct bpf_map *map, void *key, void *next_key
 	return -EOPNOTSUPP;
 }
 
+/* Called from syscall */
+static int bloom_map_alloc_check(union bpf_attr *attr)
+{
+	if (attr->value_size > KMALLOC_MAX_SIZE)
+		/* if value_size is bigger, the user space won't be able to
+		 * access the elements.
+		 */
+		return -E2BIG;
+
+	return 0;
+}
+
 static struct bpf_map *bloom_map_alloc(union bpf_attr *attr)
 {
 	u32 bitset_bytes, bitset_mask, nr_hash_funcs, nr_bits;
@@ -191,6 +203,7 @@ static u64 bloom_map_mem_usage(const struct bpf_map *map)
 BTF_ID_LIST_SINGLE(bpf_bloom_map_btf_ids, struct, bpf_bloom_filter)
 const struct bpf_map_ops bloom_filter_map_ops = {
 	.map_meta_equal = bpf_map_meta_equal,
+	.map_alloc_check = bloom_map_alloc_check,
 	.map_alloc = bloom_map_alloc,
 	.map_free = bloom_map_free,
 	.map_get_next_key = bloom_map_get_next_key,
diff --git a/tools/testing/selftests/bpf/prog_tests/bloom_filter_map.c b/tools/testing/selftests/bpf/prog_tests/bloom_filter_map.c
index 053f4d6da77a..cc184e4420f6 100644
--- a/tools/testing/selftests/bpf/prog_tests/bloom_filter_map.c
+++ b/tools/testing/selftests/bpf/prog_tests/bloom_filter_map.c
@@ -2,6 +2,7 @@
 /* Copyright (c) 2021 Facebook */
 
 #include <sys/syscall.h>
+#include <limits.h>
 #include <test_progs.h>
 #include "bloom_filter_map.skel.h"
 
@@ -21,6 +22,11 @@ static void test_fail_cases(void)
 	if (!ASSERT_LT(fd, 0, "bpf_map_create bloom filter invalid value size 0"))
 		close(fd);
 
+	/* Invalid value size: too big */
+	fd = bpf_map_create(BPF_MAP_TYPE_BLOOM_FILTER, NULL, 0, INT32_MAX, 100, NULL);
+	if (!ASSERT_LT(fd, 0, "bpf_map_create bloom filter invalid value too large"))
+		close(fd);
+
 	/* Invalid max entries size */
 	fd = bpf_map_create(BPF_MAP_TYPE_BLOOM_FILTER, NULL, 0, sizeof(value), 0, NULL);
 	if (!ASSERT_LT(fd, 0, "bpf_map_create bloom filter invalid max entries size"))
-- 
2.40.1

Re: [PATCH V2 bpf 1/2] bpf: Check bloom filter map value size

[Andrii Nakryiko]

On Tue, Mar 26, 2024 at 7:43 PM Andrei Matei <andreimatei1@gmail.com> wrote:
>
> This patch adds a missing check to bloom filter creating, rejecting
> values above KMALLOC_MAX_SIZE. This brings the bloom map in line with
> many other map types.
>
> The lack of this protection can cause kernel crashes for value sizes
> that overflow int's. Such a crash was caught by syzkaller. The next
> patch adds more guard-rails at a lower level.
>
> Signed-off-by: Andrei Matei <andreimatei1@gmail.com>
> ---
>  kernel/bpf/bloom_filter.c                           | 13 +++++++++++++
>  .../selftests/bpf/prog_tests/bloom_filter_map.c     |  6 ++++++
>  2 files changed, 19 insertions(+)
>

Acked-by: Andrii Nakryiko <andrii@kernel.org>

> diff --git a/kernel/bpf/bloom_filter.c b/kernel/bpf/bloom_filter.c
> index addf3dd57b59..35e1ddca74d2 100644
> --- a/kernel/bpf/bloom_filter.c
> +++ b/kernel/bpf/bloom_filter.c
> @@ -80,6 +80,18 @@ static int bloom_map_get_next_key(struct bpf_map *map, void *key, void *next_key
>         return -EOPNOTSUPP;
>  }
>
> +/* Called from syscall */
> +static int bloom_map_alloc_check(union bpf_attr *attr)
> +{
> +       if (attr->value_size > KMALLOC_MAX_SIZE)
> +               /* if value_size is bigger, the user space won't be able to
> +                * access the elements.
> +                */
> +               return -E2BIG;
> +
> +       return 0;
> +}
> +
>  static struct bpf_map *bloom_map_alloc(union bpf_attr *attr)
>  {
>         u32 bitset_bytes, bitset_mask, nr_hash_funcs, nr_bits;
> @@ -191,6 +203,7 @@ static u64 bloom_map_mem_usage(const struct bpf_map *map)
>  BTF_ID_LIST_SINGLE(bpf_bloom_map_btf_ids, struct, bpf_bloom_filter)
>  const struct bpf_map_ops bloom_filter_map_ops = {
>         .map_meta_equal = bpf_map_meta_equal,
> +       .map_alloc_check = bloom_map_alloc_check,
>         .map_alloc = bloom_map_alloc,
>         .map_free = bloom_map_free,
>         .map_get_next_key = bloom_map_get_next_key,
> diff --git a/tools/testing/selftests/bpf/prog_tests/bloom_filter_map.c b/tools/testing/selftests/bpf/prog_tests/bloom_filter_map.c
> index 053f4d6da77a..cc184e4420f6 100644
> --- a/tools/testing/selftests/bpf/prog_tests/bloom_filter_map.c
> +++ b/tools/testing/selftests/bpf/prog_tests/bloom_filter_map.c
> @@ -2,6 +2,7 @@
>  /* Copyright (c) 2021 Facebook */
>
>  #include <sys/syscall.h>
> +#include <limits.h>
>  #include <test_progs.h>
>  #include "bloom_filter_map.skel.h"
>
> @@ -21,6 +22,11 @@ static void test_fail_cases(void)
>         if (!ASSERT_LT(fd, 0, "bpf_map_create bloom filter invalid value size 0"))
>                 close(fd);
>
> +       /* Invalid value size: too big */
> +       fd = bpf_map_create(BPF_MAP_TYPE_BLOOM_FILTER, NULL, 0, INT32_MAX, 100, NULL);
> +       if (!ASSERT_LT(fd, 0, "bpf_map_create bloom filter invalid value too large"))
> +               close(fd);
> +
>         /* Invalid max entries size */
>         fd = bpf_map_create(BPF_MAP_TYPE_BLOOM_FILTER, NULL, 0, sizeof(value), 0, NULL);
>         if (!ASSERT_LT(fd, 0, "bpf_map_create bloom filter invalid max entries size"))
> --
> 2.40.1
>
>

[PATCH V2 bpf 2/2] bpf: Protect against int overflow for stack access size

[Andrei Matei]

This patch re-introduces protection against the size of access to stack
memory being negative; the access size can appear negative as a result
of overflowing its signed int representation. This should not actually
happen, as there are other protections along the way, but we should
protect against it anyway. One code path was missing such protections
(fixed in the previous patch in the series), causing out-of-bounds array
accesses in check_stack_range_initialized(). This patch causes the
verification of a program with such a non-sensical access size to fail.

This check used to exist in a more indirect way, but was inadvertendly
removed in a833a17aeac7.

Fixes: a833a17aeac7 ("bpf: Fix verification of indirect var-off stack access")
Reported-by: syzbot+33f4297b5f927648741a@syzkaller.appspotmail.com
Reported-by: syzbot+aafd0513053a1cbf52ef@syzkaller.appspotmail.com
Closes: https://lore.kernel.org/bpf/CAADnVQLORV5PT0iTAhRER+iLBTkByCYNBYyvBSgjN1T31K+gOw@mail.gmail.com/
Signed-off-by: Andrei Matei <andreimatei1@gmail.com>
---
 kernel/bpf/verifier.c | 5 +++++
 1 file changed, 5 insertions(+)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 0bfc0050db28..353985b2b6a2 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -6701,6 +6701,11 @@ static int check_stack_access_within_bounds(
 	err = check_stack_slot_within_bounds(env, min_off, state, type);
 	if (!err && max_off > 0)
 		err = -EINVAL; /* out of stack access into non-negative offsets */
+	if (!err && access_size < 0)
+		/* access_size should not be negative (or overflow an int); others checks
+		 * along the way should have prevented such an access.
+		 */
+		err = -EFAULT; /* invalid negative access size; integer overflow? */
 
 	if (err) {
 		if (tnum_is_const(reg->var_off)) {
-- 
2.40.1

Re: [PATCH V2 bpf 2/2] bpf: Protect against int overflow for stack access size

[Andrii Nakryiko]

On Tue, Mar 26, 2024 at 7:43 PM Andrei Matei <andreimatei1@gmail.com> wrote:
>
> This patch re-introduces protection against the size of access to stack
> memory being negative; the access size can appear negative as a result
> of overflowing its signed int representation. This should not actually
> happen, as there are other protections along the way, but we should
> protect against it anyway. One code path was missing such protections
> (fixed in the previous patch in the series), causing out-of-bounds array
> accesses in check_stack_range_initialized(). This patch causes the
> verification of a program with such a non-sensical access size to fail.
>
> This check used to exist in a more indirect way, but was inadvertendly
> removed in a833a17aeac7.
>
> Fixes: a833a17aeac7 ("bpf: Fix verification of indirect var-off stack access")
> Reported-by: syzbot+33f4297b5f927648741a@syzkaller.appspotmail.com
> Reported-by: syzbot+aafd0513053a1cbf52ef@syzkaller.appspotmail.com
> Closes: https://lore.kernel.org/bpf/CAADnVQLORV5PT0iTAhRER+iLBTkByCYNBYyvBSgjN1T31K+gOw@mail.gmail.com/
> Signed-off-by: Andrei Matei <andreimatei1@gmail.com>
> ---
>  kernel/bpf/verifier.c | 5 +++++
>  1 file changed, 5 insertions(+)
>

LGTM

Acked-by: Andrii Nakryiko <andrii@kernel.org>

> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 0bfc0050db28..353985b2b6a2 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -6701,6 +6701,11 @@ static int check_stack_access_within_bounds(
>         err = check_stack_slot_within_bounds(env, min_off, state, type);
>         if (!err && max_off > 0)
>                 err = -EINVAL; /* out of stack access into non-negative offsets */
> +       if (!err && access_size < 0)
> +               /* access_size should not be negative (or overflow an int); others checks
> +                * along the way should have prevented such an access.
> +                */
> +               err = -EFAULT; /* invalid negative access size; integer overflow? */
>
>         if (err) {
>                 if (tnum_is_const(reg->var_off)) {
> --
> 2.40.1
>
>

Re: [PATCH V2 bpf 0/2] Check bloom filter map value size

[patchwork-bot+netdevbpf]

Hello:

This series was applied to bpf/bpf.git (master)
by Alexei Starovoitov <ast@kernel.org>:

On Tue, 26 Mar 2024 22:42:43 -0400 you wrote:
> v1->v2:
> - prepend a patch addressing the bloom map specifically
> - change low-level rejection error to EFAULT, to indicate a bug
> 
> Andrei Matei (2):
>   bpf: Check bloom filter map value size
>   bpf: Protect against int overflow for stack access size
> 
> [...]

Here is the summary with links:
  - [V2,bpf,1/2] bpf: Check bloom filter map value size
    https://git.kernel.org/bpf/bpf/c/b018c30d030a
  - [V2,bpf,2/2] bpf: Protect against int overflow for stack access size
    https://git.kernel.org/bpf/bpf/c/8a1f008933b6

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