[PATCH net] bpf, array: fix heap out-of-bounds access when updating elements

[PATCH net] bpf, array: fix heap out-of-bounds access when updating elements

[Daniel Borkmann]

During own review but also reported by Dmitry's syzkaller [1] it has been
noticed that we trigger a heap out-of-bounds access on eBPF array maps
when updating elements. This happens with each map whose map->value_size
(specified during map creation time) is not multiple of 8 bytes.

In array_map_alloc(), elem_size is round_up(attr->value_size, 8) and
used to align array map slots for faster access. However, in function
array_map_update_elem(), we update the element as ...

memcpy(array->value + array->elem_size * index, value, array->elem_size);

... where we access 'value' out-of-bounds, since it was allocated from
map_update_elem() from syscall side as kmalloc(map->value_size, GFP_USER)
and later on copied through copy_from_user(value, uvalue, map->value_size).
Thus, up to 7 bytes, we can access out-of-bounds.

Same could happen from within an eBPF program, where in worst case we
access beyond an eBPF program's designated stack.

Since 1be7f75d1668 ("bpf: enable non-root eBPF programs") didn't hit an
official release yet, it only affects priviledged users.

In case of array_map_lookup_elem(), the verifier prevents eBPF programs
from accessing beyond map->value_size through check_map_access(). Also
from syscall side map_lookup_elem() only copies map->value_size back to
user, so nothing could leak.

  [1] http://github.com/google/syzkaller

Fixes: 28fbcfa08d8e ("bpf: add array type of eBPF maps")
Reported-by: Dmitry Vyukov <dvyukov@google.com>
Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
---
 kernel/bpf/arraymap.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/kernel/bpf/arraymap.c b/kernel/bpf/arraymap.c
index 3f4c99e..4c67ce3 100644
--- a/kernel/bpf/arraymap.c
+++ b/kernel/bpf/arraymap.c
@@ -105,7 +105,7 @@ static int array_map_update_elem(struct bpf_map *map, void *key, void *value,
 		/* all elements already exist */
 		return -EEXIST;
 
-	memcpy(array->value + array->elem_size * index, value, array->elem_size);
+	memcpy(array->value + array->elem_size * index, value, map->value_size);
 	return 0;
 }
 
-- 
1.9.3

Re: [PATCH net] bpf, array: fix heap out-of-bounds access when updating elements

[Alexei Starovoitov]

On Mon, Nov 30, 2015 at 01:02:55PM +0100, Daniel Borkmann wrote:
> During own review but also reported by Dmitry's syzkaller [1] it has been
> noticed that we trigger a heap out-of-bounds access on eBPF array maps
> when updating elements. This happens with each map whose map->value_size
> (specified during map creation time) is not multiple of 8 bytes.
...
> In case of array_map_lookup_elem(), the verifier prevents eBPF programs
> from accessing beyond map->value_size through check_map_access(). Also
> from syscall side map_lookup_elem() only copies map->value_size back to
> user, so nothing could leak.
> 
>   [1] http://github.com/google/syzkaller
> 
> Fixes: 28fbcfa08d8e ("bpf: add array type of eBPF maps")
> Reported-by: Dmitry Vyukov <dvyukov@google.com>
> Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>

Dmitry, thanks a lot for applying syzkaller to bpf. The issues
got cought much sooner than they would have been discovered otherwise.
Looks like the fuzzing has limited dependency chains described
in sys/sys.txt. Can they be improved into doing something like:
single call to map_create followed by many calls to update to
stress oom ? I did it manually so far without kasan.

Daniel, thanks for the fix. Commit log is all good.
Acked-by: Alexei Starovoitov <ast@kernel.org>

Re: [PATCH net] bpf, array: fix heap out-of-bounds access when updating elements

[Dmitry Vyukov]

On Mon, Nov 30, 2015 at 7:29 PM, Alexei Starovoitov
<alexei.starovoitov@gmail.com> wrote:
> On Mon, Nov 30, 2015 at 01:02:55PM +0100, Daniel Borkmann wrote:
>> During own review but also reported by Dmitry's syzkaller [1] it has been
>> noticed that we trigger a heap out-of-bounds access on eBPF array maps
>> when updating elements. This happens with each map whose map->value_size
>> (specified during map creation time) is not multiple of 8 bytes.
> ...
>> In case of array_map_lookup_elem(), the verifier prevents eBPF programs
>> from accessing beyond map->value_size through check_map_access(). Also
>> from syscall side map_lookup_elem() only copies map->value_size back to
>> user, so nothing could leak.
>>
>>   [1] http://github.com/google/syzkaller
>>
>> Fixes: 28fbcfa08d8e ("bpf: add array type of eBPF maps")
>> Reported-by: Dmitry Vyukov <dvyukov@google.com>
>> Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
>
> Dmitry, thanks a lot for applying syzkaller to bpf. The issues
> got cought much sooner than they would have been discovered otherwise.
> Looks like the fuzzing has limited dependency chains described
> in sys/sys.txt. Can they be improved into doing something like:
> single call to map_create followed by many calls to update to
> stress oom ? I did it manually so far without kasan.

Hi Alexei,

Please elaborate.
sys.txt describes signatures of syscalls. Based on that syzkaller
generates programs that can contain a map_create call followed by
multiple map update calls. Though, it won't generate millions of
update calls on a single map, because it directly conflicts with the
idea of coverage guided fuzzing. For OOMs I guess you want to try
kmalloc fault injection.

Re: [PATCH net] bpf, array: fix heap out-of-bounds access when updating elements

[Daniel Borkmann]

On 12/01/2015 10:38 AM, Dmitry Vyukov wrote:
> On Mon, Nov 30, 2015 at 7:29 PM, Alexei Starovoitov
> <alexei.starovoitov@gmail.com> wrote:
...
>> Dmitry, thanks a lot for applying syzkaller to bpf. The issues
>> got cought much sooner than they would have been discovered otherwise.
>> Looks like the fuzzing has limited dependency chains described
>> in sys/sys.txt. Can they be improved into doing something like:
>> single call to map_create followed by many calls to update to
>> stress oom ? I did it manually so far without kasan.
>
> Hi Alexei,
>
> Please elaborate.
> sys.txt describes signatures of syscalls. Based on that syzkaller
> generates programs that can contain a map_create call followed by
> multiple map update calls. Though, it won't generate millions of
> update calls on a single map, because it directly conflicts with the
> idea of coverage guided fuzzing. For OOMs I guess you want to try
> kmalloc fault injection.

Wrt dependency chains, I believe what is meant is that there are some
options that could only be covered by the fuzzer after having succeeded
a couple of dependencies first.

Perhaps not directly related to BPF, but f.e. some things can only be
reached after having a session established, like the transfer of fds via
SCM_RIGHTS, options that are being fuzzed while having a tcp/udp/sctp/
netlink/etc session established and such.

Perhaps in BPF case, f.e. updating of a program array, which itself would
require some semi-autogenerated program to get loaded first. (The latter
is already a different beast by itself wrt testing the verifier, though.)

Cheers,
Daniel

Re: [PATCH net] bpf, array: fix heap out-of-bounds access when updating elements

[David Miller]

From: Daniel Borkmann <daniel@iogearbox.net>
Date: Mon, 30 Nov 2015 13:02:55 +0100

> During own review but also reported by Dmitry's syzkaller [1] it has been
> noticed that we trigger a heap out-of-bounds access on eBPF array maps
> when updating elements. This happens with each map whose map->value_size
> (specified during map creation time) is not multiple of 8 bytes.
> 
> In array_map_alloc(), elem_size is round_up(attr->value_size, 8) and
> used to align array map slots for faster access. However, in function
> array_map_update_elem(), we update the element as ...
> 
> memcpy(array->value + array->elem_size * index, value, array->elem_size);
> 
> ... where we access 'value' out-of-bounds, since it was allocated from
> map_update_elem() from syscall side as kmalloc(map->value_size, GFP_USER)
> and later on copied through copy_from_user(value, uvalue, map->value_size).
> Thus, up to 7 bytes, we can access out-of-bounds.
> 
> Same could happen from within an eBPF program, where in worst case we
> access beyond an eBPF program's designated stack.
> 
> Since 1be7f75d1668 ("bpf: enable non-root eBPF programs") didn't hit an
> official release yet, it only affects priviledged users.
> 
> In case of array_map_lookup_elem(), the verifier prevents eBPF programs
> from accessing beyond map->value_size through check_map_access(). Also
> from syscall side map_lookup_elem() only copies map->value_size back to
> user, so nothing could leak.
> 
>   [1] http://github.com/google/syzkaller
> 
> Fixes: 28fbcfa08d8e ("bpf: add array type of eBPF maps")
> Reported-by: Dmitry Vyukov <dvyukov@google.com>
> Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>

Applied, thanks.

Re: [PATCH net] bpf, array: fix heap out-of-bounds access when updating elements

[Dmitry Vyukov]

On Tue, Dec 1, 2015 at 11:30 AM, Daniel Borkmann <daniel@iogearbox.net> wrote:
> On 12/01/2015 10:38 AM, Dmitry Vyukov wrote:
>>
>> On Mon, Nov 30, 2015 at 7:29 PM, Alexei Starovoitov
>> <alexei.starovoitov@gmail.com> wrote:
>
> ...
>>>
>>> Dmitry, thanks a lot for applying syzkaller to bpf. The issues
>>> got cought much sooner than they would have been discovered otherwise.
>>> Looks like the fuzzing has limited dependency chains described
>>> in sys/sys.txt. Can they be improved into doing something like:
>>> single call to map_create followed by many calls to update to
>>> stress oom ? I did it manually so far without kasan.
>>
>>
>> Hi Alexei,
>>
>> Please elaborate.
>> sys.txt describes signatures of syscalls. Based on that syzkaller
>> generates programs that can contain a map_create call followed by
>> multiple map update calls. Though, it won't generate millions of
>> update calls on a single map, because it directly conflicts with the
>> idea of coverage guided fuzzing. For OOMs I guess you want to try
>> kmalloc fault injection.
>
>
> Wrt dependency chains, I believe what is meant is that there are some
> options that could only be covered by the fuzzer after having succeeded
> a couple of dependencies first.
>
> Perhaps not directly related to BPF, but f.e. some things can only be
> reached after having a session established, like the transfer of fds via
> SCM_RIGHTS, options that are being fuzzed while having a tcp/udp/sctp/
> netlink/etc session established and such.
>
> Perhaps in BPF case, f.e. updating of a program array, which itself would
> require some semi-autogenerated program to get loaded first. (The latter
> is already a different beast by itself wrt testing the verifier, though.)


Well, that's the whole idea of syzkaller to build longer sequences of
syscalls that use resources in sensible ways. In fact, you can see
that in the reproducer program syzkaller creates a map and then does
two update operations on it.
However, it does not work ideally at the moment. Description of
syscalls can be improved, description of syscalls can contain plain
bugs, lots of implicit syscalls are not described (e.g. ioctls, or
functionalities available via opening of magical files), algorithm of
program generation can be improved (currently syzkaller generates
random syscalls and then tries to reuse some resources across these
syscalls, but I am thinking about explicitly centering the process
around resources: here are resources that we have, what can we do with
them?), and of course there are lots of heuristics and tuning
involved. Help is welcome.