Netdev Archive on lore.kernel.org
help / color / mirror / Atom feed
* [PATCH] bpf: Fix integer overflow involving bucket_size
@ 2021-08-05 14:05 Tatsuhiko Yasumatsu
  2021-08-05 14:26 ` Kees Cook
  0 siblings, 1 reply; 3+ messages in thread
From: Tatsuhiko Yasumatsu @ 2021-08-05 14:05 UTC (permalink / raw)
  To: Alexei Starovoitov, Daniel Borkmann, Andrii Nakryiko
  Cc: th.yasumatsu, Martin KaFai Lau, Song Liu, Yonghong Song,
	John Fastabend, KP Singh, netdev, bpf, linux-kernel

In __htab_map_lookup_and_delete_batch(), hash buckets are iterated over
to count the number of elements in each bucket (bucket_size).
If bucket_size is large enough, the multiplication to calculate
kvmalloc() size could overflow, resulting in out-of-bounds write
as reported by KASAN.

[...]
[  104.986052] BUG: KASAN: vmalloc-out-of-bounds in __htab_map_lookup_and_delete_batch+0x5ce/0xb60
[  104.986489] Write of size 4194224 at addr ffffc9010503be70 by task crash/112
[  104.986889]
[  104.987193] CPU: 0 PID: 112 Comm: crash Not tainted 5.14.0-rc4 #13
[  104.987552] Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.13.0-1ubuntu1.1 04/01/2014
[  104.988104] Call Trace:
[  104.988410]  dump_stack_lvl+0x34/0x44
[  104.988706]  print_address_description.constprop.0+0x21/0x140
[  104.988991]  ? __htab_map_lookup_and_delete_batch+0x5ce/0xb60
[  104.989327]  ? __htab_map_lookup_and_delete_batch+0x5ce/0xb60
[  104.989622]  kasan_report.cold+0x7f/0x11b
[  104.989881]  ? __htab_map_lookup_and_delete_batch+0x5ce/0xb60
[  104.990239]  kasan_check_range+0x17c/0x1e0
[  104.990467]  memcpy+0x39/0x60
[  104.990670]  __htab_map_lookup_and_delete_batch+0x5ce/0xb60
[  104.990982]  ? __wake_up_common+0x4d/0x230
[  104.991256]  ? htab_of_map_free+0x130/0x130
[  104.991541]  bpf_map_do_batch+0x1fb/0x220
[...]

In hashtable, if the elements' keys have the same jhash() value, the
elements will be put into the same bucket. By putting a lot of elements
into a single bucket, the value of bucket_size can be increased to
trigger the integer overflow.

Triggering the overflow is possible for both callers with CAP_SYS_ADMIN
and callers without CAP_SYS_ADMIN.

It will be trivial for a caller with CAP_SYS_ADMIN to intentionally
reach this overflow by enabling BPF_F_ZERO_SEED. As this flag will set
the random seed passed to jhash() to 0, it will be easy for the caller
to prepare keys which will be hashed into the same value, and thus put
all the elements into the same bucket.

If the caller does not have CAP_SYS_ADMIN, BPF_F_ZERO_SEED cannot be
used. However, it will be still technically possible to trigger the
overflow, by guessing the random seed value passed to jhash() (32bit)
and repeating the attempt to trigger the overflow. In this case,
the probability to trigger the overflow will be low and will take
a very long time.

Fix the integer overflow by casting 1 operand to u64.

Fixes: 057996380a42 ("bpf: Add batch ops to all htab bpf map")
Signed-off-by: Tatsuhiko Yasumatsu <th.yasumatsu@gmail.com>
---
 kernel/bpf/hashtab.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/kernel/bpf/hashtab.c b/kernel/bpf/hashtab.c
index 72c58cc516a3..e29283c3b17f 100644
--- a/kernel/bpf/hashtab.c
+++ b/kernel/bpf/hashtab.c
@@ -1565,8 +1565,8 @@ __htab_map_lookup_and_delete_batch(struct bpf_map *map,
 	/* We cannot do copy_from_user or copy_to_user inside
 	 * the rcu_read_lock. Allocate enough space here.
 	 */
-	keys = kvmalloc(key_size * bucket_size, GFP_USER | __GFP_NOWARN);
-	values = kvmalloc(value_size * bucket_size, GFP_USER | __GFP_NOWARN);
+	keys = kvmalloc((u64)key_size * bucket_size, GFP_USER | __GFP_NOWARN);
+	values = kvmalloc((u64)value_size * bucket_size, GFP_USER | __GFP_NOWARN);
 	if (!keys || !values) {
 		ret = -ENOMEM;
 		goto after_loop;
-- 
2.25.1


^ permalink raw reply	[flat|nested] 3+ messages in thread

* Re: [PATCH] bpf: Fix integer overflow involving bucket_size
  2021-08-05 14:05 [PATCH] bpf: Fix integer overflow involving bucket_size Tatsuhiko Yasumatsu
@ 2021-08-05 14:26 ` Kees Cook
  2021-08-06 14:25   ` Tatsuhiko Yasumatsu
  0 siblings, 1 reply; 3+ messages in thread
From: Kees Cook @ 2021-08-05 14:26 UTC (permalink / raw)
  To: Tatsuhiko Yasumatsu
  Cc: Alexei Starovoitov, Daniel Borkmann, Andrii Nakryiko,
	Martin KaFai Lau, Song Liu, Yonghong Song, John Fastabend,
	KP Singh, netdev, bpf

On Thu, Aug 05, 2021 at 11:05:15PM +0900, Tatsuhiko Yasumatsu wrote:
> In __htab_map_lookup_and_delete_batch(), hash buckets are iterated over
> to count the number of elements in each bucket (bucket_size).
> If bucket_size is large enough, the multiplication to calculate
> kvmalloc() size could overflow, resulting in out-of-bounds write
> as reported by KASAN.
> 
> [...]
> [  104.986052] BUG: KASAN: vmalloc-out-of-bounds in __htab_map_lookup_and_delete_batch+0x5ce/0xb60
> [  104.986489] Write of size 4194224 at addr ffffc9010503be70 by task crash/112
> [  104.986889]
> [  104.987193] CPU: 0 PID: 112 Comm: crash Not tainted 5.14.0-rc4 #13
> [  104.987552] Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.13.0-1ubuntu1.1 04/01/2014
> [  104.988104] Call Trace:
> [  104.988410]  dump_stack_lvl+0x34/0x44
> [  104.988706]  print_address_description.constprop.0+0x21/0x140
> [  104.988991]  ? __htab_map_lookup_and_delete_batch+0x5ce/0xb60
> [  104.989327]  ? __htab_map_lookup_and_delete_batch+0x5ce/0xb60
> [  104.989622]  kasan_report.cold+0x7f/0x11b
> [  104.989881]  ? __htab_map_lookup_and_delete_batch+0x5ce/0xb60
> [  104.990239]  kasan_check_range+0x17c/0x1e0
> [  104.990467]  memcpy+0x39/0x60
> [  104.990670]  __htab_map_lookup_and_delete_batch+0x5ce/0xb60
> [  104.990982]  ? __wake_up_common+0x4d/0x230
> [  104.991256]  ? htab_of_map_free+0x130/0x130
> [  104.991541]  bpf_map_do_batch+0x1fb/0x220
> [...]
> 
> In hashtable, if the elements' keys have the same jhash() value, the
> elements will be put into the same bucket. By putting a lot of elements
> into a single bucket, the value of bucket_size can be increased to
> trigger the integer overflow.
> 
> Triggering the overflow is possible for both callers with CAP_SYS_ADMIN
> and callers without CAP_SYS_ADMIN.
> 
> It will be trivial for a caller with CAP_SYS_ADMIN to intentionally
> reach this overflow by enabling BPF_F_ZERO_SEED. As this flag will set
> the random seed passed to jhash() to 0, it will be easy for the caller
> to prepare keys which will be hashed into the same value, and thus put
> all the elements into the same bucket.
> 
> If the caller does not have CAP_SYS_ADMIN, BPF_F_ZERO_SEED cannot be
> used. However, it will be still technically possible to trigger the
> overflow, by guessing the random seed value passed to jhash() (32bit)
> and repeating the attempt to trigger the overflow. In this case,
> the probability to trigger the overflow will be low and will take
> a very long time.
> 
> Fix the integer overflow by casting 1 operand to u64.
> 
> Fixes: 057996380a42 ("bpf: Add batch ops to all htab bpf map")
> Signed-off-by: Tatsuhiko Yasumatsu <th.yasumatsu@gmail.com>
> ---
>  kernel/bpf/hashtab.c | 4 ++--
>  1 file changed, 2 insertions(+), 2 deletions(-)
> 
> diff --git a/kernel/bpf/hashtab.c b/kernel/bpf/hashtab.c
> index 72c58cc516a3..e29283c3b17f 100644
> --- a/kernel/bpf/hashtab.c
> +++ b/kernel/bpf/hashtab.c
> @@ -1565,8 +1565,8 @@ __htab_map_lookup_and_delete_batch(struct bpf_map *map,
>  	/* We cannot do copy_from_user or copy_to_user inside
>  	 * the rcu_read_lock. Allocate enough space here.
>  	 */
> -	keys = kvmalloc(key_size * bucket_size, GFP_USER | __GFP_NOWARN);
> -	values = kvmalloc(value_size * bucket_size, GFP_USER | __GFP_NOWARN);
> +	keys = kvmalloc((u64)key_size * bucket_size, GFP_USER | __GFP_NOWARN);
> +	values = kvmalloc((u64)value_size * bucket_size, GFP_USER | __GFP_NOWARN);

Please, no open-coded multiplication[1]. This should use kvmalloc_array()
instead.

-Kees

[1] https://www.kernel.org/doc/html/latest/process/deprecated.html#open-coded-arithmetic-in-allocator-arguments

>  	if (!keys || !values) {
>  		ret = -ENOMEM;
>  		goto after_loop;
> -- 
> 2.25.1
> 

-- 
Kees Cook

^ permalink raw reply	[flat|nested] 3+ messages in thread

* Re: [PATCH] bpf: Fix integer overflow involving bucket_size
  2021-08-05 14:26 ` Kees Cook
@ 2021-08-06 14:25   ` Tatsuhiko Yasumatsu
  0 siblings, 0 replies; 3+ messages in thread
From: Tatsuhiko Yasumatsu @ 2021-08-06 14:25 UTC (permalink / raw)
  To: Kees Cook
  Cc: Alexei Starovoitov, Daniel Borkmann, Andrii Nakryiko,
	Martin KaFai Lau, Song Liu, Yonghong Song, John Fastabend,
	KP Singh, netdev, bpf

On Thu, Aug 05, 2021 at 07:26:49AM -0700, Kees Cook wrote:
> On Thu, Aug 05, 2021 at 11:05:15PM +0900, Tatsuhiko Yasumatsu wrote:
> > In __htab_map_lookup_and_delete_batch(), hash buckets are iterated over
> > to count the number of elements in each bucket (bucket_size).
> > If bucket_size is large enough, the multiplication to calculate
> > kvmalloc() size could overflow, resulting in out-of-bounds write
> > as reported by KASAN.
> > 
> > [...]
> > [  104.986052] BUG: KASAN: vmalloc-out-of-bounds in __htab_map_lookup_and_delete_batch+0x5ce/0xb60
> > [  104.986489] Write of size 4194224 at addr ffffc9010503be70 by task crash/112
> > [  104.986889]
> > [  104.987193] CPU: 0 PID: 112 Comm: crash Not tainted 5.14.0-rc4 #13
> > [  104.987552] Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.13.0-1ubuntu1.1 04/01/2014
> > [  104.988104] Call Trace:
> > [  104.988410]  dump_stack_lvl+0x34/0x44
> > [  104.988706]  print_address_description.constprop.0+0x21/0x140
> > [  104.988991]  ? __htab_map_lookup_and_delete_batch+0x5ce/0xb60
> > [  104.989327]  ? __htab_map_lookup_and_delete_batch+0x5ce/0xb60
> > [  104.989622]  kasan_report.cold+0x7f/0x11b
> > [  104.989881]  ? __htab_map_lookup_and_delete_batch+0x5ce/0xb60
> > [  104.990239]  kasan_check_range+0x17c/0x1e0
> > [  104.990467]  memcpy+0x39/0x60
> > [  104.990670]  __htab_map_lookup_and_delete_batch+0x5ce/0xb60
> > [  104.990982]  ? __wake_up_common+0x4d/0x230
> > [  104.991256]  ? htab_of_map_free+0x130/0x130
> > [  104.991541]  bpf_map_do_batch+0x1fb/0x220
> > [...]
> > 
> > In hashtable, if the elements' keys have the same jhash() value, the
> > elements will be put into the same bucket. By putting a lot of elements
> > into a single bucket, the value of bucket_size can be increased to
> > trigger the integer overflow.
> > 
> > Triggering the overflow is possible for both callers with CAP_SYS_ADMIN
> > and callers without CAP_SYS_ADMIN.
> > 
> > It will be trivial for a caller with CAP_SYS_ADMIN to intentionally
> > reach this overflow by enabling BPF_F_ZERO_SEED. As this flag will set
> > the random seed passed to jhash() to 0, it will be easy for the caller
> > to prepare keys which will be hashed into the same value, and thus put
> > all the elements into the same bucket.
> > 
> > If the caller does not have CAP_SYS_ADMIN, BPF_F_ZERO_SEED cannot be
> > used. However, it will be still technically possible to trigger the
> > overflow, by guessing the random seed value passed to jhash() (32bit)
> > and repeating the attempt to trigger the overflow. In this case,
> > the probability to trigger the overflow will be low and will take
> > a very long time.
> > 
> > Fix the integer overflow by casting 1 operand to u64.
> > 
> > Fixes: 057996380a42 ("bpf: Add batch ops to all htab bpf map")
> > Signed-off-by: Tatsuhiko Yasumatsu <th.yasumatsu@gmail.com>
> > ---
> >  kernel/bpf/hashtab.c | 4 ++--
> >  1 file changed, 2 insertions(+), 2 deletions(-)
> > 
> > diff --git a/kernel/bpf/hashtab.c b/kernel/bpf/hashtab.c
> > index 72c58cc516a3..e29283c3b17f 100644
> > --- a/kernel/bpf/hashtab.c
> > +++ b/kernel/bpf/hashtab.c
> > @@ -1565,8 +1565,8 @@ __htab_map_lookup_and_delete_batch(struct bpf_map *map,
> >  	/* We cannot do copy_from_user or copy_to_user inside
> >  	 * the rcu_read_lock. Allocate enough space here.
> >  	 */
> > -	keys = kvmalloc(key_size * bucket_size, GFP_USER | __GFP_NOWARN);
> > -	values = kvmalloc(value_size * bucket_size, GFP_USER | __GFP_NOWARN);
> > +	keys = kvmalloc((u64)key_size * bucket_size, GFP_USER | __GFP_NOWARN);
> > +	values = kvmalloc((u64)value_size * bucket_size, GFP_USER | __GFP_NOWARN);
> 
> Please, no open-coded multiplication[1]. This should use kvmalloc_array()
> instead.
> 
> -Kees
> 
> [1] https://www.kernel.org/doc/html/latest/process/deprecated.html#open-coded-arithmetic-in-allocator-arguments
> 
> >  	if (!keys || !values) {
> >  		ret = -ENOMEM;
> >  		goto after_loop;
> > -- 
> > 2.25.1
> > 
> 
> -- 
> Kees Cook
Thank you for pointing out.
I'll modify the patch.

Regards,
Tatsuhiko Yasumatsu

^ permalink raw reply	[flat|nested] 3+ messages in thread

end of thread, other threads:[~2021-08-06 14:25 UTC | newest]

Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2021-08-05 14:05 [PATCH] bpf: Fix integer overflow involving bucket_size Tatsuhiko Yasumatsu
2021-08-05 14:26 ` Kees Cook
2021-08-06 14:25   ` Tatsuhiko Yasumatsu

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).