diff mbox series

[bpf-next,04/10] bpf: enforce exact retval range on subprog/callback exit

Message ID 20231122011656.1105943-5-andrii@kernel.org (mailing list archive)
State Superseded
Delegated to: BPF
Headers show
Series BPF verifier retval logic fixes | expand

Checks

Context Check Description
bpf/vmtest-bpf-next-PR success PR summary
netdev/series_format success Posting correctly formatted
netdev/codegen success Generated files up to date
netdev/tree_selection success Clearly marked for bpf-next
netdev/fixes_present success Fixes tag not required for -next series
netdev/header_inline success No static functions without inline keyword in header files
netdev/build_32bit success Errors and warnings before: 1197 this patch: 1197
netdev/cc_maintainers warning 8 maintainers not CCed: yonghong.song@linux.dev john.fastabend@gmail.com song@kernel.org haoluo@google.com jolsa@kernel.org kpsingh@kernel.org martin.lau@linux.dev sdf@google.com
netdev/build_clang success Errors and warnings before: 1162 this patch: 1162
netdev/verify_signedoff success Signed-off-by tag matches author and committer
netdev/deprecated_api success None detected
netdev/check_selftest success No net selftest shell script
netdev/verify_fixes success No Fixes tag
netdev/build_allmodconfig_warn success Errors and warnings before: 1224 this patch: 1224
netdev/checkpatch warning WARNING: line length of 82 exceeds 80 columns WARNING: line length of 93 exceeds 80 columns WARNING: line length of 95 exceeds 80 columns
netdev/build_clang_rust success No Rust files in patch. Skipping build
netdev/kdoc success Errors and warnings before: 0 this patch: 0
netdev/source_inline success Was 0 now: 0
bpf/vmtest-bpf-next-VM_Test-0 success Logs for Lint
bpf/vmtest-bpf-next-VM_Test-2 success Logs for Validate matrix.py
bpf/vmtest-bpf-next-VM_Test-1 success Logs for ShellCheck
bpf/vmtest-bpf-next-VM_Test-8 success Logs for aarch64-gcc / veristat
bpf/vmtest-bpf-next-VM_Test-3 success Logs for aarch64-gcc / build / build for aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-7 success Logs for aarch64-gcc / test (test_verifier, false, 360) / test_verifier on aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-6 success Logs for aarch64-gcc / test (test_progs_no_alu32, false, 360) / test_progs_no_alu32 on aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-4 success Logs for aarch64-gcc / test (test_maps, false, 360) / test_maps on aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-5 success Logs for aarch64-gcc / test (test_progs, false, 360) / test_progs on aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-9 success Logs for s390x-gcc / build / build for s390x with gcc
bpf/vmtest-bpf-next-VM_Test-14 success Logs for s390x-gcc / veristat
bpf/vmtest-bpf-next-VM_Test-15 success Logs for set-matrix
bpf/vmtest-bpf-next-VM_Test-16 success Logs for x86_64-gcc / build / build for x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-17 success Logs for x86_64-gcc / test (test_maps, false, 360) / test_maps on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-18 success Logs for x86_64-gcc / test (test_progs, false, 360) / test_progs on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-19 success Logs for x86_64-gcc / test (test_progs_no_alu32, false, 360) / test_progs_no_alu32 on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-20 success Logs for x86_64-gcc / test (test_progs_no_alu32_parallel, true, 30) / test_progs_no_alu32_parallel on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-21 success Logs for x86_64-gcc / test (test_progs_parallel, true, 30) / test_progs_parallel on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-22 success Logs for x86_64-gcc / test (test_verifier, false, 360) / test_verifier on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-23 success Logs for x86_64-gcc / veristat / veristat on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-24 success Logs for x86_64-llvm-16 / build / build for x86_64 with llvm-16
bpf/vmtest-bpf-next-VM_Test-25 success Logs for x86_64-llvm-16 / test (test_maps, false, 360) / test_maps on x86_64 with llvm-16
bpf/vmtest-bpf-next-VM_Test-26 success Logs for x86_64-llvm-16 / test (test_progs, false, 360) / test_progs on x86_64 with llvm-16
bpf/vmtest-bpf-next-VM_Test-27 success Logs for x86_64-llvm-16 / test (test_progs_no_alu32, false, 360) / test_progs_no_alu32 on x86_64 with llvm-16
bpf/vmtest-bpf-next-VM_Test-28 success Logs for x86_64-llvm-16 / test (test_verifier, false, 360) / test_verifier on x86_64 with llvm-16
bpf/vmtest-bpf-next-VM_Test-29 success Logs for x86_64-llvm-16 / veristat
bpf/vmtest-bpf-next-VM_Test-13 success Logs for s390x-gcc / test (test_verifier, false, 360) / test_verifier on s390x with gcc
bpf/vmtest-bpf-next-VM_Test-12 success Logs for s390x-gcc / test (test_progs_no_alu32, false, 360) / test_progs_no_alu32 on s390x with gcc
bpf/vmtest-bpf-next-VM_Test-10 success Logs for s390x-gcc / test (test_maps, false, 360) / test_maps on s390x with gcc
bpf/vmtest-bpf-next-VM_Test-11 success Logs for s390x-gcc / test (test_progs, false, 360) / test_progs on s390x with gcc

Commit Message

Andrii Nakryiko Nov. 22, 2023, 1:16 a.m. UTC 
Instead of relying on potentially imprecise tnum representation of
expected return value range for callbacks and subprogs, validate that
both tnum and umin/umax range satisfy exact expected range of return
values.

E.g., if callback would need to return [0, 2] range, tnum can't
represent this precisely and instead will allow [0, 3] range. By
additionally checking umin/umax range, we can make sure that
subprog/callback indeed returns only valid [0, 2] range.

Signed-off-by: Andrii Nakryiko <andrii@kernel.org>
---
 include/linux/bpf_verifier.h |  7 +++++-
 kernel/bpf/verifier.c        | 45 +++++++++++++++++++++++++++---------
 2 files changed, 40 insertions(+), 12 deletions(-)

Comments

Eduard Zingerman Nov. 22, 2023, 3:13 p.m. UTC | #1 
On Tue, 2023-11-21 at 17:16 -0800, Andrii Nakryiko wrote:
> Instead of relying on potentially imprecise tnum representation of
> expected return value range for callbacks and subprogs, validate that
> both tnum and umin/umax range satisfy exact expected range of return
> values.
> 
> E.g., if callback would need to return [0, 2] range, tnum can't
> represent this precisely and instead will allow [0, 3] range. By
> additionally checking umin/umax range, we can make sure that
> subprog/callback indeed returns only valid [0, 2] range.
> 
> Signed-off-by: Andrii Nakryiko <andrii@kernel.org>
> ---

Acked-by: Eduard Zingerman <eddyz87@gmail.com>
(but please see a question below)

[...]

> @@ -9464,6 +9477,16 @@ static bool in_rbtree_lock_required_cb(struct bpf_verifier_env *env)
>  	return is_rbtree_lock_required_kfunc(kfunc_btf_id);
>  }
>  
> +static bool retval_range_within(struct bpf_retval_range range, const struct bpf_reg_state *reg)
> +{
> +	struct tnum trange = retval_range_as_tnum(range);
> +
> +	if (!tnum_in(trange, reg->var_off))
> +		return false;

Q: When is it necessary to do this check?
   I tried commenting it and test_{verifier,progs} still pass.
   Are there situations when umin/umax change is not sufficient?

> +
> +	return range.minval <= reg->umin_value && reg->umax_value <= range.maxval;
> +}
> +

[...]
Andrii Nakryiko Nov. 22, 2023, 5:45 p.m. UTC | #2 
On Wed, Nov 22, 2023 at 7:13 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Tue, 2023-11-21 at 17:16 -0800, Andrii Nakryiko wrote:
> > Instead of relying on potentially imprecise tnum representation of
> > expected return value range for callbacks and subprogs, validate that
> > both tnum and umin/umax range satisfy exact expected range of return
> > values.
> >
> > E.g., if callback would need to return [0, 2] range, tnum can't
> > represent this precisely and instead will allow [0, 3] range. By
> > additionally checking umin/umax range, we can make sure that
> > subprog/callback indeed returns only valid [0, 2] range.
> >
> > Signed-off-by: Andrii Nakryiko <andrii@kernel.org>
> > ---
>
> Acked-by: Eduard Zingerman <eddyz87@gmail.com>
> (but please see a question below)
>
> [...]
>
> > @@ -9464,6 +9477,16 @@ static bool in_rbtree_lock_required_cb(struct bpf_verifier_env *env)
> >       return is_rbtree_lock_required_kfunc(kfunc_btf_id);
> >  }
> >
> > +static bool retval_range_within(struct bpf_retval_range range, const struct bpf_reg_state *reg)
> > +{
> > +     struct tnum trange = retval_range_as_tnum(range);
> > +
> > +     if (!tnum_in(trange, reg->var_off))
> > +             return false;
>
> Q: When is it necessary to do this check?
>    I tried commenting it and test_{verifier,progs} still pass.
>    Are there situations when umin/umax change is not sufficient?

I believe not. But we still check tnum in check_cond_jmp_op, for
example, so I decided to keep it to not have to argue and prove why
it's ok to ditch tnum.

Generally speaking, I think tnum is useful in only one use case:
checking (un)aligned memory accesses. This is the only representation
that can make sure we have lower 2-3 bits as zero to prove that memory
access is 4- or 8-byte aligned.

Other than this, I think ranges are more precise and easier to work with.

But I'm not ready to go on the quest to eliminate tnum usage everywhere :)

>
> > +
> > +     return range.minval <= reg->umin_value && reg->umax_value <= range.maxval;
> > +}
> > +
>
> [...]
>
>
Shung-Hsi Yu Nov. 27, 2023, 10:55 a.m. UTC | #3 
On Wed, Nov 22, 2023 at 09:45:27AM -0800, Andrii Nakryiko wrote:
> On Wed, Nov 22, 2023 at 7:13 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
> >
> > On Tue, 2023-11-21 at 17:16 -0800, Andrii Nakryiko wrote:
> > > Instead of relying on potentially imprecise tnum representation of
> > > expected return value range for callbacks and subprogs, validate that
> > > both tnum and umin/umax range satisfy exact expected range of return
> > > values.
> > >
> > > E.g., if callback would need to return [0, 2] range, tnum can't
> > > represent this precisely and instead will allow [0, 3] range. By
> > > additionally checking umin/umax range, we can make sure that
> > > subprog/callback indeed returns only valid [0, 2] range.
> > >
> > > Signed-off-by: Andrii Nakryiko <andrii@kernel.org>
> > > ---
> >
> > Acked-by: Eduard Zingerman <eddyz87@gmail.com>
> > (but please see a question below)
> >
> > [...]
> >
> > > +static bool retval_range_within(struct bpf_retval_range range, const struct bpf_reg_state *reg)
> > > +{
> > > +     struct tnum trange = retval_range_as_tnum(range);
> > > +
> > > +     if (!tnum_in(trange, reg->var_off))
> > > +             return false;
> >
> > Q: When is it necessary to do this check?
> >    I tried commenting it and test_{verifier,progs} still pass.
> >    Are there situations when umin/umax change is not sufficient?
> 
> I believe not. But we still check tnum in check_cond_jmp_op, for
> example, so I decided to keep it to not have to argue and prove why
> it's ok to ditch tnum.

Semi-related proof[1] from awhile back :)

> Generally speaking, I think tnum is useful in only one use case:
> checking (un)aligned memory accesses. This is the only representation
> that can make sure we have lower 2-3 bits as zero to prove that memory
> access is 4- or 8-byte aligned.
> 
> Other than this, I think ranges are more precise and easier to work with.

Agree with the above.

I'd vote for ditching tnum for the retval check here. With umin/umax
check in place there really isn't a need for an additional tnum check at
all. Keeping it probably does more harm (in the form of confusion) than
good.

1: https://lore.kernel.org/bpf/20220831031907.16133-3-shung-hsi.yu@suse.com/

> But I'm not ready to go on the quest to eliminate tnum usage everywhere :)
> 
> > > +
> > > +     return range.minval <= reg->umin_value && reg->umax_value <= range.maxval;
> > > +}
> > > +
> >
> > [...]
Andrii Nakryiko Nov. 27, 2023, 6:19 p.m. UTC | #4 
On Mon, Nov 27, 2023 at 2:55 AM Shung-Hsi Yu <shung-hsi.yu@suse.com> wrote:
>
> On Wed, Nov 22, 2023 at 09:45:27AM -0800, Andrii Nakryiko wrote:
> > On Wed, Nov 22, 2023 at 7:13 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > >
> > > On Tue, 2023-11-21 at 17:16 -0800, Andrii Nakryiko wrote:
> > > > Instead of relying on potentially imprecise tnum representation of
> > > > expected return value range for callbacks and subprogs, validate that
> > > > both tnum and umin/umax range satisfy exact expected range of return
> > > > values.
> > > >
> > > > E.g., if callback would need to return [0, 2] range, tnum can't
> > > > represent this precisely and instead will allow [0, 3] range. By
> > > > additionally checking umin/umax range, we can make sure that
> > > > subprog/callback indeed returns only valid [0, 2] range.
> > > >
> > > > Signed-off-by: Andrii Nakryiko <andrii@kernel.org>
> > > > ---
> > >
> > > Acked-by: Eduard Zingerman <eddyz87@gmail.com>
> > > (but please see a question below)
> > >
> > > [...]
> > >
> > > > +static bool retval_range_within(struct bpf_retval_range range, const struct bpf_reg_state *reg)
> > > > +{
> > > > +     struct tnum trange = retval_range_as_tnum(range);
> > > > +
> > > > +     if (!tnum_in(trange, reg->var_off))
> > > > +             return false;
> > >
> > > Q: When is it necessary to do this check?
> > >    I tried commenting it and test_{verifier,progs} still pass.
> > >    Are there situations when umin/umax change is not sufficient?
> >
> > I believe not. But we still check tnum in check_cond_jmp_op, for
> > example, so I decided to keep it to not have to argue and prove why
> > it's ok to ditch tnum.
>
> Semi-related proof[1] from awhile back :)
>
> > Generally speaking, I think tnum is useful in only one use case:
> > checking (un)aligned memory accesses. This is the only representation
> > that can make sure we have lower 2-3 bits as zero to prove that memory
> > access is 4- or 8-byte aligned.
> >
> > Other than this, I think ranges are more precise and easier to work with.
>
> Agree with the above.
>
> I'd vote for ditching tnum for the retval check here. With umin/umax
> check in place there really isn't a need for an additional tnum check at
> all. Keeping it probably does more harm (in the form of confusion) than
> good.

Ok, I think it's as trivial as removing two lines of code. So I'll add
it as the last patch to the series and will let BPF maintainers decide
if they want this change or not.

>
> 1: https://lore.kernel.org/bpf/20220831031907.16133-3-shung-hsi.yu@suse.com/
>
> > But I'm not ready to go on the quest to eliminate tnum usage everywhere :)
> >
> > > > +
> > > > +     return range.minval <= reg->umin_value && reg->umax_value <= range.maxval;
> > > > +}
> > > > +
> > >
> > > [...]
diff mbox series

Patch

diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index f019da8bf423..00702a3cca62 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -275,6 +275,11 @@  struct bpf_reference_state {
 	int callback_ref;
 };
 
+struct bpf_retval_range {
+	u32 minval;
+	u32 maxval;
+};
+
 /* state of the program:
  * type of all registers and stack info
  */
@@ -297,7 +302,7 @@  struct bpf_func_state {
 	 * void foo(void) { bpf_timer_set_callback(,foo); }
 	 */
 	u32 async_entry_cnt;
-	struct tnum callback_ret_range;
+	struct bpf_retval_range callback_ret_range;
 	bool in_callback_fn;
 	bool in_async_callback_fn;
 	bool in_exception_callback_fn;
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index b227f23e063d..fc103fd03896 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -2272,6 +2272,19 @@  static void init_reg_state(struct bpf_verifier_env *env,
 	regs[BPF_REG_FP].frameno = state->frameno;
 }
 
+static struct bpf_retval_range retval_range(u32 minval, u32 maxval)
+{
+	return (struct bpf_retval_range){ minval, maxval };
+}
+
+static struct tnum retval_range_as_tnum(struct bpf_retval_range range)
+{
+	if (range.minval == range.maxval)
+		return tnum_const(range.minval);
+	else
+		return tnum_range(range.minval, range.maxval);
+}
+
 #define BPF_MAIN_FUNC (-1)
 static void init_func_state(struct bpf_verifier_env *env,
 			    struct bpf_func_state *state,
@@ -2280,7 +2293,7 @@  static void init_func_state(struct bpf_verifier_env *env,
 	state->callsite = callsite;
 	state->frameno = frameno;
 	state->subprogno = subprogno;
-	state->callback_ret_range = tnum_range(0, 0);
+	state->callback_ret_range = retval_range(0, 0);
 	init_reg_state(env, state);
 	mark_verifier_state_scratched(env);
 }
@@ -9300,7 +9313,7 @@  static int set_map_elem_callback_state(struct bpf_verifier_env *env,
 		return err;
 
 	callee->in_callback_fn = true;
-	callee->callback_ret_range = tnum_range(0, 1);
+	callee->callback_ret_range = retval_range(0, 1);
 	return 0;
 }
 
@@ -9322,7 +9335,7 @@  static int set_loop_callback_state(struct bpf_verifier_env *env,
 	__mark_reg_not_init(env, &callee->regs[BPF_REG_5]);
 
 	callee->in_callback_fn = true;
-	callee->callback_ret_range = tnum_range(0, 1);
+	callee->callback_ret_range = retval_range(0, 1);
 	return 0;
 }
 
@@ -9352,7 +9365,7 @@  static int set_timer_callback_state(struct bpf_verifier_env *env,
 	__mark_reg_not_init(env, &callee->regs[BPF_REG_4]);
 	__mark_reg_not_init(env, &callee->regs[BPF_REG_5]);
 	callee->in_async_callback_fn = true;
-	callee->callback_ret_range = tnum_range(0, 1);
+	callee->callback_ret_range = retval_range(0, 1);
 	return 0;
 }
 
@@ -9380,7 +9393,7 @@  static int set_find_vma_callback_state(struct bpf_verifier_env *env,
 	__mark_reg_not_init(env, &callee->regs[BPF_REG_4]);
 	__mark_reg_not_init(env, &callee->regs[BPF_REG_5]);
 	callee->in_callback_fn = true;
-	callee->callback_ret_range = tnum_range(0, 1);
+	callee->callback_ret_range = retval_range(0, 1);
 	return 0;
 }
 
@@ -9403,7 +9416,7 @@  static int set_user_ringbuf_callback_state(struct bpf_verifier_env *env,
 	__mark_reg_not_init(env, &callee->regs[BPF_REG_5]);
 
 	callee->in_callback_fn = true;
-	callee->callback_ret_range = tnum_range(0, 1);
+	callee->callback_ret_range = retval_range(0, 1);
 	return 0;
 }
 
@@ -9435,7 +9448,7 @@  static int set_rbtree_add_callback_state(struct bpf_verifier_env *env,
 	__mark_reg_not_init(env, &callee->regs[BPF_REG_4]);
 	__mark_reg_not_init(env, &callee->regs[BPF_REG_5]);
 	callee->in_callback_fn = true;
-	callee->callback_ret_range = tnum_range(0, 1);
+	callee->callback_ret_range = retval_range(0, 1);
 	return 0;
 }
 
@@ -9464,6 +9477,16 @@  static bool in_rbtree_lock_required_cb(struct bpf_verifier_env *env)
 	return is_rbtree_lock_required_kfunc(kfunc_btf_id);
 }
 
+static bool retval_range_within(struct bpf_retval_range range, const struct bpf_reg_state *reg)
+{
+	struct tnum trange = retval_range_as_tnum(range);
+
+	if (!tnum_in(trange, reg->var_off))
+		return false;
+
+	return range.minval <= reg->umin_value && reg->umax_value <= range.maxval;
+}
+
 static int prepare_func_exit(struct bpf_verifier_env *env, int *insn_idx)
 {
 	struct bpf_verifier_state *state = env->cur_state;
@@ -9486,9 +9509,6 @@  static int prepare_func_exit(struct bpf_verifier_env *env, int *insn_idx)
 
 	caller = state->frame[state->curframe - 1];
 	if (callee->in_callback_fn) {
-		/* enforce R0 return value range [0, 1]. */
-		struct tnum range = callee->callback_ret_range;
-
 		if (r0->type != SCALAR_VALUE) {
 			verbose(env, "R0 not a scalar value\n");
 			return -EACCES;
@@ -9500,7 +9520,10 @@  static int prepare_func_exit(struct bpf_verifier_env *env, int *insn_idx)
 		if (err)
 			return err;
 
-		if (!tnum_in(range, r0->var_off)) {
+		/* enforce R0 return value range */
+		if (!retval_range_within(callee->callback_ret_range, r0)) {
+			struct tnum range = retval_range_as_tnum(callee->callback_ret_range);
+
 			verbose_invalid_scalar(env, r0, &range, "callback return", "R0");
 			return -EINVAL;
 		}