* [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.