[bpf-next,1/3] bpf: fix to XOR and OR range computation

Commit Message

Cupertino Miranda April 11, 2024, 5:37 p.m. UTC

Range for XOR and OR operators would not be attempted unless src_reg
would resolve to a single value, i.e. a known constant value.
This condition seems excessive, relative to how easy it is to compute a
safe range for these operators.

BPF self-tests were added to validate the new functionality.

Signed-off-by: Cupertino Miranda <[e-mail]>
---
 kernel/bpf/verifier.c                         |  3 +-
 .../selftests/bpf/progs/verifier_bounds.c     | 64 +++++++++++++++++++
 2 files changed, 66 insertions(+), 1 deletion(-)

Comments

Yonghong Song April 15, 2024, 6:07 p.m. UTC | #1

On 4/11/24 10:37 AM, Cupertino Miranda wrote:
> Range for XOR and OR operators would not be attempted unless src_reg
> would resolve to a single value, i.e. a known constant value.
> This condition seems excessive, relative to how easy it is to compute a
> safe range for these operators.

Please break this patch into two patches. One for verifier and another
for selftest. This will make it easy for possible backport.

As the number of patches grows, it would be great if you can add
a cover letter for the series.

For the subject, the following seems better:
    improve XOR and OR range computation

I would not call the previous implementation as a bug. It is just
conservative.

For the following:
   This condition seems excessive, relative to how easy it is to compute a
   safe range for these operators.

You can just say:
   This condition is unnecessary, and the following XOR/OR operator handling
   could compute a possible better range.

>
> BPF self-tests were added to validate the new functionality.
>
> Signed-off-by: Cupertino Miranda <[e-mail]>
> ---
>   kernel/bpf/verifier.c                         |  3 +-
>   .../selftests/bpf/progs/verifier_bounds.c     | 64 +++++++++++++++++++
>   2 files changed, 66 insertions(+), 1 deletion(-)
>
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 2aad6d90550f..a219f601569a 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -13764,7 +13764,8 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
>   	}
>   
>   	if (!src_known &&
> -	    opcode != BPF_ADD && opcode != BPF_SUB && opcode != BPF_AND) {
> +	    opcode != BPF_ADD && opcode != BPF_SUB && opcode != BPF_AND &&
> +	    opcode != BPF_XOR && opcode != BPF_OR) {
>   		__mark_reg_unknown(env, dst_reg);
>   		return 0;
>   	}
> diff --git a/tools/testing/selftests/bpf/progs/verifier_bounds.c b/tools/testing/selftests/bpf/progs/verifier_bounds.c
> index 960998f16306..2fcf46341b30 100644
> --- a/tools/testing/selftests/bpf/progs/verifier_bounds.c
> +++ b/tools/testing/selftests/bpf/progs/verifier_bounds.c
> @@ -885,6 +885,70 @@ l1_%=:	r0 = 0;						\
>   	: __clobber_all);
>   }
>   
> +SEC("socket")
> +__description("bounds check for reg32 <= 1, 0 xor (0,1)")
> +__success __failure_unpriv
> +__msg_unpriv("R0 min value is outside of the allowed memory range")
> +__retval(0)
> +__naked void t_0_xor_01(void)
> +{
> +	asm volatile ("					\
> +	call %[bpf_get_prandom_u32];                    \
> +	r6 = r0;                                        \
> +	r1 = 0;						\
> +	*(u64*)(r10 - 8) = r1;				\
> +	r2 = r10;					\
> +	r2 += -8;					\
> +	r1 = %[map_hash_8b] ll;				\
> +	call %[bpf_map_lookup_elem];			\
> +	if r0 != 0 goto l0_%=;				\
> +	exit;						\
> +l0_%=:	w1 = 0;						\
> +	r6 >>= 63;					\
> +	w1 ^= w6;					\
> +	if w1 <= 1 goto l1_%=;				\
> +	r0 = *(u64*)(r0 + 8);				\
> +l1_%=:	r0 = 0;						\
> +	exit;						\
> +"	:
> +	: __imm(bpf_map_lookup_elem),
> +	  __imm_addr(map_hash_8b),
> +	  __imm(bpf_get_prandom_u32)
> +	: __clobber_all);
> +}
> +
> +SEC("socket")
> +__description("bounds check for reg32 <= 1, 0 or (0,1)")
> +__success __failure_unpriv
> +__msg_unpriv("R0 min value is outside of the allowed memory range")
> +__retval(0)
> +__naked void t_0_or_01(void)
> +{
> +	asm volatile ("					\
> +	call %[bpf_get_prandom_u32];                    \
> +	r6 = r0;                                        \
> +	r1 = 0;						\
> +	*(u64*)(r10 - 8) = r1;				\
> +	r2 = r10;					\
> +	r2 += -8;					\
> +	r1 = %[map_hash_8b] ll;				\
> +	call %[bpf_map_lookup_elem];			\
> +	if r0 != 0 goto l0_%=;				\
> +	exit;						\
> +l0_%=:	w1 = 0;						\
> +	r6 >>= 63;					\
> +	w1 |= w6;					\
> +	if w1 <= 1 goto l1_%=;				\
> +	r0 = *(u64*)(r0 + 8);				\
> +l1_%=:	r0 = 0;						\
> +	exit;						\
> +"	:
> +	: __imm(bpf_map_lookup_elem),
> +	  __imm_addr(map_hash_8b),
> +	  __imm(bpf_get_prandom_u32)
> +	: __clobber_all);
> +}
> +
>   SEC("socket")
>   __description("bounds checks after 32-bit truncation. test 1")
>   __success __failure_unpriv __msg_unpriv("R0 leaks addr")

Patch

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 2aad6d90550f..a219f601569a 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -13764,7 +13764,8 @@  static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
 	}
 
 	if (!src_known &&
-	    opcode != BPF_ADD && opcode != BPF_SUB && opcode != BPF_AND) {
+	    opcode != BPF_ADD && opcode != BPF_SUB && opcode != BPF_AND &&
+	    opcode != BPF_XOR && opcode != BPF_OR) {
 		__mark_reg_unknown(env, dst_reg);
 		return 0;
 	}
diff --git a/tools/testing/selftests/bpf/progs/verifier_bounds.c b/tools/testing/selftests/bpf/progs/verifier_bounds.c
index 960998f16306..2fcf46341b30 100644
--- a/tools/testing/selftests/bpf/progs/verifier_bounds.c
+++ b/tools/testing/selftests/bpf/progs/verifier_bounds.c
@@ -885,6 +885,70 @@  l1_%=:	r0 = 0;						\
 	: __clobber_all);
 }
 
+SEC("socket")
+__description("bounds check for reg32 <= 1, 0 xor (0,1)")
+__success __failure_unpriv
+__msg_unpriv("R0 min value is outside of the allowed memory range")
+__retval(0)
+__naked void t_0_xor_01(void)
+{
+	asm volatile ("					\
+	call %[bpf_get_prandom_u32];                    \
+	r6 = r0;                                        \
+	r1 = 0;						\
+	*(u64*)(r10 - 8) = r1;				\
+	r2 = r10;					\
+	r2 += -8;					\
+	r1 = %[map_hash_8b] ll;				\
+	call %[bpf_map_lookup_elem];			\
+	if r0 != 0 goto l0_%=;				\
+	exit;						\
+l0_%=:	w1 = 0;						\
+	r6 >>= 63;					\
+	w1 ^= w6;					\
+	if w1 <= 1 goto l1_%=;				\
+	r0 = *(u64*)(r0 + 8);				\
+l1_%=:	r0 = 0;						\
+	exit;						\
+"	:
+	: __imm(bpf_map_lookup_elem),
+	  __imm_addr(map_hash_8b),
+	  __imm(bpf_get_prandom_u32)
+	: __clobber_all);
+}
+
+SEC("socket")
+__description("bounds check for reg32 <= 1, 0 or (0,1)")
+__success __failure_unpriv
+__msg_unpriv("R0 min value is outside of the allowed memory range")
+__retval(0)
+__naked void t_0_or_01(void)
+{
+	asm volatile ("					\
+	call %[bpf_get_prandom_u32];                    \
+	r6 = r0;                                        \
+	r1 = 0;						\
+	*(u64*)(r10 - 8) = r1;				\
+	r2 = r10;					\
+	r2 += -8;					\
+	r1 = %[map_hash_8b] ll;				\
+	call %[bpf_map_lookup_elem];			\
+	if r0 != 0 goto l0_%=;				\
+	exit;						\
+l0_%=:	w1 = 0;						\
+	r6 >>= 63;					\
+	w1 |= w6;					\
+	if w1 <= 1 goto l1_%=;				\
+	r0 = *(u64*)(r0 + 8);				\
+l1_%=:	r0 = 0;						\
+	exit;						\
+"	:
+	: __imm(bpf_map_lookup_elem),
+	  __imm_addr(map_hash_8b),
+	  __imm(bpf_get_prandom_u32)
+	: __clobber_all);
+}
+
 SEC("socket")
 __description("bounds checks after 32-bit truncation. test 1")
 __success __failure_unpriv __msg_unpriv("R0 leaks addr")