* [PATCH net] bpf: fix verifier memory corruption
@ 2015-04-14 22:57 Alexei Starovoitov
2015-04-15 15:59 ` Hannes Frederic Sowa
` (2 more replies)
0 siblings, 3 replies; 6+ messages in thread
From: Alexei Starovoitov @ 2015-04-14 22:57 UTC (permalink / raw)
To: David S. Miller; +Cc: Daniel Borkmann, Hannes Frederic Sowa, netdev
Due to missing bounds check the DAG pass of the BPF verifier can corrupt
the memory which can cause random crashes during program loading:
[8.449451] BUG: unable to handle kernel paging request at ffffffffffffffff
[8.451293] IP: [<ffffffff811de33d>] kmem_cache_alloc_trace+0x8d/0x2f0
[8.452329] Oops: 0000 [#1] SMP
[8.452329] Call Trace:
[8.452329] [<ffffffff8116cc82>] bpf_check+0x852/0x2000
[8.452329] [<ffffffff8116b7e4>] bpf_prog_load+0x1e4/0x310
[8.452329] [<ffffffff811b190f>] ? might_fault+0x5f/0xb0
[8.452329] [<ffffffff8116c206>] SyS_bpf+0x806/0xa30
Fixes: f1bca824dabb ("bpf: add search pruning optimization to verifier")
Signed-off-by: Alexei Starovoitov <ast@plumgrid.com>
---
Many things need to align for this crash to be seen, yet I managed to hit it.
In my case JA was last insn, 't' was 255 and explored_states array
had 256 elements. I've double checked other similar paths and all seems clean.
kernel/bpf/verifier.c | 3 ++-
1 file changed, 2 insertions(+), 1 deletion(-)
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index a28e09c7825d..36508e69e92a 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -1380,7 +1380,8 @@ peek_stack:
/* tell verifier to check for equivalent states
* after every call and jump
*/
- env->explored_states[t + 1] = STATE_LIST_MARK;
+ if (t + 1 < insn_cnt)
+ env->explored_states[t + 1] = STATE_LIST_MARK;
} else {
/* conditional jump with two edges */
ret = push_insn(t, t + 1, FALLTHROUGH, env);
--
1.7.9.5
^ permalink raw reply related [flat|nested] 6+ messages in thread
* Re: [PATCH net] bpf: fix verifier memory corruption
2015-04-14 22:57 [PATCH net] bpf: fix verifier memory corruption Alexei Starovoitov
@ 2015-04-15 15:59 ` Hannes Frederic Sowa
2015-04-15 16:07 ` Alexei Starovoitov
2015-04-15 17:05 ` Daniel Borkmann
2015-04-16 16:07 ` David Miller
2 siblings, 1 reply; 6+ messages in thread
From: Hannes Frederic Sowa @ 2015-04-15 15:59 UTC (permalink / raw)
To: Alexei Starovoitov; +Cc: David S. Miller, Daniel Borkmann, netdev
On Di, 2015-04-14 at 15:57 -0700, Alexei Starovoitov wrote:
> Due to missing bounds check the DAG pass of the BPF verifier can corrupt
> the memory which can cause random crashes during program loading:
>
> [8.449451] BUG: unable to handle kernel paging request at ffffffffffffffff
> [8.451293] IP: [<ffffffff811de33d>] kmem_cache_alloc_trace+0x8d/0x2f0
> [8.452329] Oops: 0000 [#1] SMP
> [8.452329] Call Trace:
> [8.452329] [<ffffffff8116cc82>] bpf_check+0x852/0x2000
> [8.452329] [<ffffffff8116b7e4>] bpf_prog_load+0x1e4/0x310
> [8.452329] [<ffffffff811b190f>] ? might_fault+0x5f/0xb0
> [8.452329] [<ffffffff8116c206>] SyS_bpf+0x806/0xa30
>
> Fixes: f1bca824dabb ("bpf: add search pruning optimization to verifier")
> Signed-off-by: Alexei Starovoitov <ast@plumgrid.com>
> ---
> Many things need to align for this crash to be seen, yet I managed to hit it.
> In my case JA was last insn, 't' was 255 and explored_states array
> had 256 elements. I've double checked other similar paths and all seems clean.
>
> kernel/bpf/verifier.c | 3 ++-
> 1 file changed, 2 insertions(+), 1 deletion(-)
>
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index a28e09c7825d..36508e69e92a 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -1380,7 +1380,8 @@ peek_stack:
> /* tell verifier to check for equivalent states
> * after every call and jump
> */
> - env->explored_states[t + 1] = STATE_LIST_MARK;
> + if (t + 1 < insn_cnt)
> + env->explored_states[t + 1] = STATE_LIST_MARK;
> } else {
> /* conditional jump with two edges */
> ret = push_insn(t, t + 1, FALLTHROUGH, env);
Quick review:
We have env->explored_states[t+1] access in the
} else {
/* conditional jump with two edges */
ret = push_insn(t, t + 1, FALLTHROUGH, env);
if (ret == 1)
goto peek_stack;
else if (ret < 0)
goto err_free;
>>> ret = push_insn(t, t + insns[t].off + 1, BRANCH, env);
if (ret == 1)
goto peek_stack;
else if (ret < 0)
goto err_free;
}
} else {
push_insn call. At this point insn[t].off could be 0, no?
Thanks,
Hannes
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH net] bpf: fix verifier memory corruption
2015-04-15 15:59 ` Hannes Frederic Sowa
@ 2015-04-15 16:07 ` Alexei Starovoitov
2015-04-15 16:12 ` Hannes Frederic Sowa
0 siblings, 1 reply; 6+ messages in thread
From: Alexei Starovoitov @ 2015-04-15 16:07 UTC (permalink / raw)
To: Hannes Frederic Sowa; +Cc: David S. Miller, Daniel Borkmann, netdev
On 4/15/15 8:59 AM, Hannes Frederic Sowa wrote:
> On Di, 2015-04-14 at 15:57 -0700, Alexei Starovoitov wrote:
>> Due to missing bounds check the DAG pass of the BPF verifier can corrupt
>> the memory which can cause random crashes during program loading:
>>
>> [8.449451] BUG: unable to handle kernel paging request at ffffffffffffffff
>> [8.451293] IP: [<ffffffff811de33d>] kmem_cache_alloc_trace+0x8d/0x2f0
>> [8.452329] Oops: 0000 [#1] SMP
>> [8.452329] Call Trace:
>> [8.452329] [<ffffffff8116cc82>] bpf_check+0x852/0x2000
>> [8.452329] [<ffffffff8116b7e4>] bpf_prog_load+0x1e4/0x310
>> [8.452329] [<ffffffff811b190f>] ? might_fault+0x5f/0xb0
>> [8.452329] [<ffffffff8116c206>] SyS_bpf+0x806/0xa30
>>
>> Fixes: f1bca824dabb ("bpf: add search pruning optimization to verifier")
>> Signed-off-by: Alexei Starovoitov <ast@plumgrid.com>
>> ---
>> Many things need to align for this crash to be seen, yet I managed to hit it.
>> In my case JA was last insn, 't' was 255 and explored_states array
>> had 256 elements. I've double checked other similar paths and all seems clean.
>>
>> kernel/bpf/verifier.c | 3 ++-
>> 1 file changed, 2 insertions(+), 1 deletion(-)
>>
>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
>> index a28e09c7825d..36508e69e92a 100644
>> --- a/kernel/bpf/verifier.c
>> +++ b/kernel/bpf/verifier.c
>> @@ -1380,7 +1380,8 @@ peek_stack:
>> /* tell verifier to check for equivalent states
>> * after every call and jump
>> */
>> - env->explored_states[t + 1] = STATE_LIST_MARK;
>> + if (t + 1 < insn_cnt)
>> + env->explored_states[t + 1] = STATE_LIST_MARK;
>> } else {
>> /* conditional jump with two edges */
>> ret = push_insn(t, t + 1, FALLTHROUGH, env);
>
> Quick review:
>
> We have env->explored_states[t+1] access in the
>
> } else {
> /* conditional jump with two edges */
> ret = push_insn(t, t + 1, FALLTHROUGH, env);
> if (ret == 1)
> goto peek_stack;
> else if (ret < 0)
> goto err_free;
>
>>>> ret = push_insn(t, t + insns[t].off + 1, BRANCH, env);
> if (ret == 1)
> goto peek_stack;
> else if (ret < 0)
> goto err_free;
> }
> } else {
>
>
> push_insn call. At this point insn[t].off could be 0, no?
insn[t].off can be anything, but the first thing that push_insn()
checks is:
if (w < 0 || w >= env->prog->len)
only then it does:
env->explored_states[w] = STATE_LIST_MARK;
so we're good there.
Though thanks for triple checking :)
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH net] bpf: fix verifier memory corruption
2015-04-15 16:07 ` Alexei Starovoitov
@ 2015-04-15 16:12 ` Hannes Frederic Sowa
0 siblings, 0 replies; 6+ messages in thread
From: Hannes Frederic Sowa @ 2015-04-15 16:12 UTC (permalink / raw)
To: Alexei Starovoitov; +Cc: David S. Miller, Daniel Borkmann, netdev
On Wed, Apr 15, 2015, at 18:07, Alexei Starovoitov wrote:
> On 4/15/15 8:59 AM, Hannes Frederic Sowa wrote:
> > On Di, 2015-04-14 at 15:57 -0700, Alexei Starovoitov wrote:
> >> Due to missing bounds check the DAG pass of the BPF verifier can corrupt
> >> the memory which can cause random crashes during program loading:
> >>
> >> [8.449451] BUG: unable to handle kernel paging request at ffffffffffffffff
> >> [8.451293] IP: [<ffffffff811de33d>] kmem_cache_alloc_trace+0x8d/0x2f0
> >> [8.452329] Oops: 0000 [#1] SMP
> >> [8.452329] Call Trace:
> >> [8.452329] [<ffffffff8116cc82>] bpf_check+0x852/0x2000
> >> [8.452329] [<ffffffff8116b7e4>] bpf_prog_load+0x1e4/0x310
> >> [8.452329] [<ffffffff811b190f>] ? might_fault+0x5f/0xb0
> >> [8.452329] [<ffffffff8116c206>] SyS_bpf+0x806/0xa30
> >>
> >> Fixes: f1bca824dabb ("bpf: add search pruning optimization to verifier")
> >> Signed-off-by: Alexei Starovoitov <ast@plumgrid.com>
> >> ---
> >> Many things need to align for this crash to be seen, yet I managed to hit it.
> >> In my case JA was last insn, 't' was 255 and explored_states array
> >> had 256 elements. I've double checked other similar paths and all seems clean.
> >>
> >> kernel/bpf/verifier.c | 3 ++-
> >> 1 file changed, 2 insertions(+), 1 deletion(-)
> >>
> >> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> >> index a28e09c7825d..36508e69e92a 100644
> >> --- a/kernel/bpf/verifier.c
> >> +++ b/kernel/bpf/verifier.c
> >> @@ -1380,7 +1380,8 @@ peek_stack:
> >> /* tell verifier to check for equivalent states
> >> * after every call and jump
> >> */
> >> - env->explored_states[t + 1] = STATE_LIST_MARK;
> >> + if (t + 1 < insn_cnt)
> >> + env->explored_states[t + 1] = STATE_LIST_MARK;
> >> } else {
> >> /* conditional jump with two edges */
> >> ret = push_insn(t, t + 1, FALLTHROUGH, env);
> >
> > Quick review:
> >
> > We have env->explored_states[t+1] access in the
> >
> > } else {
> > /* conditional jump with two edges */
> > ret = push_insn(t, t + 1, FALLTHROUGH, env);
> > if (ret == 1)
> > goto peek_stack;
> > else if (ret < 0)
> > goto err_free;
> >
> >>>> ret = push_insn(t, t + insns[t].off + 1, BRANCH, env);
> > if (ret == 1)
> > goto peek_stack;
> > else if (ret < 0)
> > goto err_free;
> > }
> > } else {
> >
> >
> > push_insn call. At this point insn[t].off could be 0, no?
>
> insn[t].off can be anything, but the first thing that push_insn()
> checks is:
> if (w < 0 || w >= env->prog->len)
> only then it does:
> env->explored_states[w] = STATE_LIST_MARK;
> so we're good there.
> Though thanks for triple checking :)
Sorry, yes. That check was too obvious to me. ;)
Acked-by: Hannes Frederic Sowa <hannes@stressinduktion.org>
Bye,
Hannes
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH net] bpf: fix verifier memory corruption
2015-04-14 22:57 [PATCH net] bpf: fix verifier memory corruption Alexei Starovoitov
2015-04-15 15:59 ` Hannes Frederic Sowa
@ 2015-04-15 17:05 ` Daniel Borkmann
2015-04-16 16:07 ` David Miller
2 siblings, 0 replies; 6+ messages in thread
From: Daniel Borkmann @ 2015-04-15 17:05 UTC (permalink / raw)
To: Alexei Starovoitov, David S. Miller; +Cc: Hannes Frederic Sowa, netdev
On 04/15/2015 12:57 AM, Alexei Starovoitov wrote:
> Due to missing bounds check the DAG pass of the BPF verifier can corrupt
> the memory which can cause random crashes during program loading:
>
> [8.449451] BUG: unable to handle kernel paging request at ffffffffffffffff
> [8.451293] IP: [<ffffffff811de33d>] kmem_cache_alloc_trace+0x8d/0x2f0
> [8.452329] Oops: 0000 [#1] SMP
> [8.452329] Call Trace:
> [8.452329] [<ffffffff8116cc82>] bpf_check+0x852/0x2000
> [8.452329] [<ffffffff8116b7e4>] bpf_prog_load+0x1e4/0x310
> [8.452329] [<ffffffff811b190f>] ? might_fault+0x5f/0xb0
> [8.452329] [<ffffffff8116c206>] SyS_bpf+0x806/0xa30
>
> Fixes: f1bca824dabb ("bpf: add search pruning optimization to verifier")
> Signed-off-by: Alexei Starovoitov <ast@plumgrid.com>
As far as I can tell, looks good to me. Any other access to a next
instruction elsewhere would be blocked from push_insn() with an error.
Acked-by: Daniel Borkmann <daniel@iogearbox.net>
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH net] bpf: fix verifier memory corruption
2015-04-14 22:57 [PATCH net] bpf: fix verifier memory corruption Alexei Starovoitov
2015-04-15 15:59 ` Hannes Frederic Sowa
2015-04-15 17:05 ` Daniel Borkmann
@ 2015-04-16 16:07 ` David Miller
2 siblings, 0 replies; 6+ messages in thread
From: David Miller @ 2015-04-16 16:07 UTC (permalink / raw)
To: ast; +Cc: daniel, hannes, netdev
From: Alexei Starovoitov <ast@plumgrid.com>
Date: Tue, 14 Apr 2015 15:57:13 -0700
> Due to missing bounds check the DAG pass of the BPF verifier can corrupt
> the memory which can cause random crashes during program loading:
>
> [8.449451] BUG: unable to handle kernel paging request at ffffffffffffffff
> [8.451293] IP: [<ffffffff811de33d>] kmem_cache_alloc_trace+0x8d/0x2f0
> [8.452329] Oops: 0000 [#1] SMP
> [8.452329] Call Trace:
> [8.452329] [<ffffffff8116cc82>] bpf_check+0x852/0x2000
> [8.452329] [<ffffffff8116b7e4>] bpf_prog_load+0x1e4/0x310
> [8.452329] [<ffffffff811b190f>] ? might_fault+0x5f/0xb0
> [8.452329] [<ffffffff8116c206>] SyS_bpf+0x806/0xa30
>
> Fixes: f1bca824dabb ("bpf: add search pruning optimization to verifier")
> Signed-off-by: Alexei Starovoitov <ast@plumgrid.com>
Applied and queued up for -stable, thanks.
^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~2015-04-16 16:07 UTC | newest]
Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2015-04-14 22:57 [PATCH net] bpf: fix verifier memory corruption Alexei Starovoitov
2015-04-15 15:59 ` Hannes Frederic Sowa
2015-04-15 16:07 ` Alexei Starovoitov
2015-04-15 16:12 ` Hannes Frederic Sowa
2015-04-15 17:05 ` Daniel Borkmann
2015-04-16 16:07 ` David Miller
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.