* [PATCH net 0/2] bpf: fix verifier min/max handling in BPF_SUB
@ 2017-07-21 13:35 Edward Cree
2017-07-21 13:36 ` [PATCH net 1/2] selftests/bpf: subtraction bounds test Edward Cree
` (3 more replies)
0 siblings, 4 replies; 7+ messages in thread
From: Edward Cree @ 2017-07-21 13:35 UTC (permalink / raw)
To: davem, Alexei Starovoitov, Alexei Starovoitov, Daniel Borkmann
Cc: netdev, linux-kernel, iovisor-dev
I managed to come up with a test for the swapped bounds in BPF_SUB, so here
it is along with a patch that fixes it, separated out from my 'rewrite
everything' series so it can go to -stable.
Edward Cree (2):
selftests/bpf: subtraction bounds test
bpf/verifier: fix min/max handling in BPF_SUB
kernel/bpf/verifier.c | 21 +++++++++++++++------
tools/testing/selftests/bpf/test_verifier.c | 28 ++++++++++++++++++++++++++++
2 files changed, 43 insertions(+), 6 deletions(-)
^ permalink raw reply [flat|nested] 7+ messages in thread* [PATCH net 1/2] selftests/bpf: subtraction bounds test 2017-07-21 13:35 [PATCH net 0/2] bpf: fix verifier min/max handling in BPF_SUB Edward Cree @ 2017-07-21 13:36 ` Edward Cree 2017-07-21 14:29 ` Daniel Borkmann 2017-07-21 13:37 ` [PATCH net 2/2] bpf/verifier: fix min/max handling in BPF_SUB Edward Cree ` (2 subsequent siblings) 3 siblings, 1 reply; 7+ messages in thread From: Edward Cree @ 2017-07-21 13:36 UTC (permalink / raw) To: davem, Alexei Starovoitov, Alexei Starovoitov, Daniel Borkmann Cc: netdev, linux-kernel, iovisor-dev There is a bug in the verifier's handling of BPF_SUB: [a,b] - [c,d] yields was [a-c, b-d] rather than the correct [a-d, b-c]. So here is a test which, with the bogus handling, will produce ranges of [0,0] and thus allowed accesses; whereas the correct handling will give a range of [-255, 255] (and hence the right-shift will give a range of [0, 255]) and the accesses will be rejected. Signed-off-by: Edward Cree <ecree@solarflare.com> --- tools/testing/selftests/bpf/test_verifier.c | 28 ++++++++++++++++++++++++++++ 1 file changed, 28 insertions(+) diff --git a/tools/testing/selftests/bpf/test_verifier.c b/tools/testing/selftests/bpf/test_verifier.c index af7d173..addea82 100644 --- a/tools/testing/selftests/bpf/test_verifier.c +++ b/tools/testing/selftests/bpf/test_verifier.c @@ -5980,6 +5980,34 @@ static struct bpf_test tests[] = { .result = REJECT, .result_unpriv = REJECT, }, + { + "subtraction bounds (map value)", + .insns = { + BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0), + BPF_MOV64_REG(BPF_REG_2, BPF_REG_10), + BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8), + BPF_LD_MAP_FD(BPF_REG_1, 0), + BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, + BPF_FUNC_map_lookup_elem), + BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 9), + BPF_LDX_MEM(BPF_B, BPF_REG_1, BPF_REG_0, 0), + BPF_JMP_IMM(BPF_JGT, BPF_REG_1, 0xff, 7), + BPF_LDX_MEM(BPF_B, BPF_REG_3, BPF_REG_0, 1), + BPF_JMP_IMM(BPF_JGT, BPF_REG_3, 0xff, 5), + BPF_ALU64_REG(BPF_SUB, BPF_REG_1, BPF_REG_3), + BPF_ALU64_IMM(BPF_RSH, BPF_REG_1, 56), + BPF_ALU64_REG(BPF_ADD, BPF_REG_0, BPF_REG_1), + BPF_LDX_MEM(BPF_B, BPF_REG_0, BPF_REG_0, 0), + BPF_EXIT_INSN(), + BPF_MOV64_IMM(BPF_REG_0, 0), + BPF_EXIT_INSN(), + }, + .fixup_map1 = { 3 }, + .errstr_unpriv = "R0 pointer arithmetic prohibited", + .errstr = "R0 min value is negative, either use unsigned index or do a if (index >=0) check.", + .result = REJECT, + .result_unpriv = REJECT, + }, }; static int probe_filter_length(const struct bpf_insn *fp) ^ permalink raw reply related [flat|nested] 7+ messages in thread
* Re: [PATCH net 1/2] selftests/bpf: subtraction bounds test 2017-07-21 13:36 ` [PATCH net 1/2] selftests/bpf: subtraction bounds test Edward Cree @ 2017-07-21 14:29 ` Daniel Borkmann 0 siblings, 0 replies; 7+ messages in thread From: Daniel Borkmann @ 2017-07-21 14:29 UTC (permalink / raw) To: Edward Cree, davem, Alexei Starovoitov, Alexei Starovoitov Cc: netdev, linux-kernel, iovisor-dev, josef On 07/21/2017 03:36 PM, Edward Cree wrote: > There is a bug in the verifier's handling of BPF_SUB: [a,b] - [c,d] yields > was [a-c, b-d] rather than the correct [a-d, b-c]. So here is a test > which, with the bogus handling, will produce ranges of [0,0] and thus > allowed accesses; whereas the correct handling will give a range of > [-255, 255] (and hence the right-shift will give a range of [0, 255]) and > the accesses will be rejected. > > Signed-off-by: Edward Cree <ecree@solarflare.com> Acked-by: Daniel Borkmann <daniel@iogearbox.net> > tools/testing/selftests/bpf/test_verifier.c | 28 ++++++++++++++++++++++++++++ > 1 file changed, 28 insertions(+) > > diff --git a/tools/testing/selftests/bpf/test_verifier.c b/tools/testing/selftests/bpf/test_verifier.c > index af7d173..addea82 100644 > --- a/tools/testing/selftests/bpf/test_verifier.c > +++ b/tools/testing/selftests/bpf/test_verifier.c > @@ -5980,6 +5980,34 @@ static struct bpf_test tests[] = { > .result = REJECT, > .result_unpriv = REJECT, > }, > + { > + "subtraction bounds (map value)", > + .insns = { > + BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0), > + BPF_MOV64_REG(BPF_REG_2, BPF_REG_10), > + BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8), > + BPF_LD_MAP_FD(BPF_REG_1, 0), > + BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, > + BPF_FUNC_map_lookup_elem), > + BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 9), > + BPF_LDX_MEM(BPF_B, BPF_REG_1, BPF_REG_0, 0), > + BPF_JMP_IMM(BPF_JGT, BPF_REG_1, 0xff, 7), > + BPF_LDX_MEM(BPF_B, BPF_REG_3, BPF_REG_0, 1), > + BPF_JMP_IMM(BPF_JGT, BPF_REG_3, 0xff, 5), > + BPF_ALU64_REG(BPF_SUB, BPF_REG_1, BPF_REG_3), > + BPF_ALU64_IMM(BPF_RSH, BPF_REG_1, 56), > + BPF_ALU64_REG(BPF_ADD, BPF_REG_0, BPF_REG_1), > + BPF_LDX_MEM(BPF_B, BPF_REG_0, BPF_REG_0, 0), > + BPF_EXIT_INSN(), > + BPF_MOV64_IMM(BPF_REG_0, 0), > + BPF_EXIT_INSN(), > + }, > + .fixup_map1 = { 3 }, > + .errstr_unpriv = "R0 pointer arithmetic prohibited", > + .errstr = "R0 min value is negative, either use unsigned index or do a if (index >=0) check.", > + .result = REJECT, > + .result_unpriv = REJECT, > + }, > }; > > static int probe_filter_length(const struct bpf_insn *fp) > ^ permalink raw reply [flat|nested] 7+ messages in thread
* [PATCH net 2/2] bpf/verifier: fix min/max handling in BPF_SUB 2017-07-21 13:35 [PATCH net 0/2] bpf: fix verifier min/max handling in BPF_SUB Edward Cree 2017-07-21 13:36 ` [PATCH net 1/2] selftests/bpf: subtraction bounds test Edward Cree @ 2017-07-21 13:37 ` Edward Cree 2017-07-21 14:30 ` Daniel Borkmann 2017-07-21 15:54 ` [iovisor-dev] [PATCH net 0/2] bpf: fix verifier " Nadav Amit 2017-07-24 21:03 ` David Miller 3 siblings, 1 reply; 7+ messages in thread From: Edward Cree @ 2017-07-21 13:37 UTC (permalink / raw) To: davem, Alexei Starovoitov, Alexei Starovoitov, Daniel Borkmann Cc: netdev, linux-kernel, iovisor-dev We have to subtract the src max from the dst min, and vice-versa, since (e.g.) the smallest result comes from the largest subtrahend. Fixes: 484611357c19 ("bpf: allow access into map value arrays") Signed-off-by: Edward Cree <ecree@solarflare.com> --- kernel/bpf/verifier.c | 21 +++++++++++++++------ 1 file changed, 15 insertions(+), 6 deletions(-) diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index af9e84a..664d939 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -1865,10 +1865,12 @@ static void adjust_reg_min_max_vals(struct bpf_verifier_env *env, * do our normal operations to the register, we need to set the values * to the min/max since they are undefined. */ - if (min_val == BPF_REGISTER_MIN_RANGE) - dst_reg->min_value = BPF_REGISTER_MIN_RANGE; - if (max_val == BPF_REGISTER_MAX_RANGE) - dst_reg->max_value = BPF_REGISTER_MAX_RANGE; + if (opcode != BPF_SUB) { + if (min_val == BPF_REGISTER_MIN_RANGE) + dst_reg->min_value = BPF_REGISTER_MIN_RANGE; + if (max_val == BPF_REGISTER_MAX_RANGE) + dst_reg->max_value = BPF_REGISTER_MAX_RANGE; + } switch (opcode) { case BPF_ADD: @@ -1879,10 +1881,17 @@ static void adjust_reg_min_max_vals(struct bpf_verifier_env *env, dst_reg->min_align = min(src_align, dst_align); break; case BPF_SUB: + /* If one of our values was at the end of our ranges, then the + * _opposite_ value in the dst_reg goes to the end of our range. + */ + if (min_val == BPF_REGISTER_MIN_RANGE) + dst_reg->max_value = BPF_REGISTER_MAX_RANGE; + if (max_val == BPF_REGISTER_MAX_RANGE) + dst_reg->min_value = BPF_REGISTER_MIN_RANGE; if (dst_reg->min_value != BPF_REGISTER_MIN_RANGE) - dst_reg->min_value -= min_val; + dst_reg->min_value -= max_val; if (dst_reg->max_value != BPF_REGISTER_MAX_RANGE) - dst_reg->max_value -= max_val; + dst_reg->max_value -= min_val; dst_reg->min_align = min(src_align, dst_align); break; case BPF_MUL: ^ permalink raw reply related [flat|nested] 7+ messages in thread
* Re: [PATCH net 2/2] bpf/verifier: fix min/max handling in BPF_SUB 2017-07-21 13:37 ` [PATCH net 2/2] bpf/verifier: fix min/max handling in BPF_SUB Edward Cree @ 2017-07-21 14:30 ` Daniel Borkmann 0 siblings, 0 replies; 7+ messages in thread From: Daniel Borkmann @ 2017-07-21 14:30 UTC (permalink / raw) To: Edward Cree, davem, Alexei Starovoitov, Alexei Starovoitov Cc: netdev, linux-kernel, iovisor-dev, josef On 07/21/2017 03:37 PM, Edward Cree wrote: > We have to subtract the src max from the dst min, and vice-versa, since > (e.g.) the smallest result comes from the largest subtrahend. > > Fixes: 484611357c19 ("bpf: allow access into map value arrays") > Signed-off-by: Edward Cree <ecree@solarflare.com> LGTM, thanks for the fix! Acked-by: Daniel Borkmann <daniel@iogearbox.net> > --- > kernel/bpf/verifier.c | 21 +++++++++++++++------ > 1 file changed, 15 insertions(+), 6 deletions(-) > > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c > index af9e84a..664d939 100644 > --- a/kernel/bpf/verifier.c > +++ b/kernel/bpf/verifier.c > @@ -1865,10 +1865,12 @@ static void adjust_reg_min_max_vals(struct bpf_verifier_env *env, > * do our normal operations to the register, we need to set the values > * to the min/max since they are undefined. > */ > - if (min_val == BPF_REGISTER_MIN_RANGE) > - dst_reg->min_value = BPF_REGISTER_MIN_RANGE; > - if (max_val == BPF_REGISTER_MAX_RANGE) > - dst_reg->max_value = BPF_REGISTER_MAX_RANGE; > + if (opcode != BPF_SUB) { > + if (min_val == BPF_REGISTER_MIN_RANGE) > + dst_reg->min_value = BPF_REGISTER_MIN_RANGE; > + if (max_val == BPF_REGISTER_MAX_RANGE) > + dst_reg->max_value = BPF_REGISTER_MAX_RANGE; > + } > > switch (opcode) { > case BPF_ADD: > @@ -1879,10 +1881,17 @@ static void adjust_reg_min_max_vals(struct bpf_verifier_env *env, > dst_reg->min_align = min(src_align, dst_align); > break; > case BPF_SUB: > + /* If one of our values was at the end of our ranges, then the > + * _opposite_ value in the dst_reg goes to the end of our range. > + */ > + if (min_val == BPF_REGISTER_MIN_RANGE) > + dst_reg->max_value = BPF_REGISTER_MAX_RANGE; > + if (max_val == BPF_REGISTER_MAX_RANGE) > + dst_reg->min_value = BPF_REGISTER_MIN_RANGE; > if (dst_reg->min_value != BPF_REGISTER_MIN_RANGE) > - dst_reg->min_value -= min_val; > + dst_reg->min_value -= max_val; > if (dst_reg->max_value != BPF_REGISTER_MAX_RANGE) > - dst_reg->max_value -= max_val; > + dst_reg->max_value -= min_val; > dst_reg->min_align = min(src_align, dst_align); > break; > case BPF_MUL: > ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [iovisor-dev] [PATCH net 0/2] bpf: fix verifier min/max handling in BPF_SUB 2017-07-21 13:35 [PATCH net 0/2] bpf: fix verifier min/max handling in BPF_SUB Edward Cree 2017-07-21 13:36 ` [PATCH net 1/2] selftests/bpf: subtraction bounds test Edward Cree 2017-07-21 13:37 ` [PATCH net 2/2] bpf/verifier: fix min/max handling in BPF_SUB Edward Cree @ 2017-07-21 15:54 ` Nadav Amit 2017-07-24 21:03 ` David Miller 3 siblings, 0 replies; 7+ messages in thread From: Nadav Amit @ 2017-07-21 15:54 UTC (permalink / raw) To: Edward Cree Cc: David S. Miller, Alexei Starovoitov, Alexei Starovoitov, Daniel Borkmann, netdev, iovisor-dev, linux-kernel Edward Cree via iovisor-dev <iovisor-dev@lists.iovisor.org> wrote: > I managed to come up with a test for the swapped bounds in BPF_SUB, so here > it is along with a patch that fixes it, separated out from my 'rewrite > everything' series so it can go to -stable. > > Edward Cree (2): > selftests/bpf: subtraction bounds test > bpf/verifier: fix min/max handling in BPF_SUB > > kernel/bpf/verifier.c | 21 +++++++++++++++------ > tools/testing/selftests/bpf/test_verifier.c | 28 ++++++++++++++++++++++++++++ > 2 files changed, 43 insertions(+), 6 deletions(-) > > _______________________________________________ > iovisor-dev mailing list > iovisor-dev@lists.iovisor.org > https://lists.iovisor.org/mailman/listinfo/iovisor-dev Thanks for separating it. Nadav ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [PATCH net 0/2] bpf: fix verifier min/max handling in BPF_SUB 2017-07-21 13:35 [PATCH net 0/2] bpf: fix verifier min/max handling in BPF_SUB Edward Cree ` (2 preceding siblings ...) 2017-07-21 15:54 ` [iovisor-dev] [PATCH net 0/2] bpf: fix verifier " Nadav Amit @ 2017-07-24 21:03 ` David Miller 3 siblings, 0 replies; 7+ messages in thread From: David Miller @ 2017-07-24 21:03 UTC (permalink / raw) To: ecree; +Cc: alexei.starovoitov, ast, daniel, netdev, linux-kernel, iovisor-dev From: Edward Cree <ecree@solarflare.com> Date: Fri, 21 Jul 2017 14:35:17 +0100 > I managed to come up with a test for the swapped bounds in BPF_SUB, so here > it is along with a patch that fixes it, separated out from my 'rewrite > everything' series so it can go to -stable. Series applied and queued up for -stable, thanks. ^ permalink raw reply [flat|nested] 7+ messages in thread
end of thread, other threads:[~2017-07-24 21:03 UTC | newest] Thread overview: 7+ messages (download: mbox.gz follow: Atom feed -- links below jump to the message on this page -- 2017-07-21 13:35 [PATCH net 0/2] bpf: fix verifier min/max handling in BPF_SUB Edward Cree 2017-07-21 13:36 ` [PATCH net 1/2] selftests/bpf: subtraction bounds test Edward Cree 2017-07-21 14:29 ` Daniel Borkmann 2017-07-21 13:37 ` [PATCH net 2/2] bpf/verifier: fix min/max handling in BPF_SUB Edward Cree 2017-07-21 14:30 ` Daniel Borkmann 2017-07-21 15:54 ` [iovisor-dev] [PATCH net 0/2] bpf: fix verifier " Nadav Amit 2017-07-24 21:03 ` David Miller
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox