diff mbox series

[bpf-next,3/3] bpf: relax MUL range computation check

Message ID 20240411173732.221881-3-cupertino.miranda@oracle.com (mailing list archive)
State Changes Requested
Delegated to: BPF
Headers show
Series [bpf-next,1/3] bpf: fix to XOR and OR range computation | expand

Checks

Context Check Description
bpf/vmtest-bpf-next-PR success PR summary
netdev/series_format warning Series does not have a cover letter
netdev/tree_selection success Clearly marked for bpf-next
netdev/ynl success Generated files up to date; no warnings/errors; no diff in generated;
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: 955 this patch: 955
netdev/build_tools success Errors and warnings before: 0 this patch: 0
netdev/cc_maintainers warning 13 maintainers not CCed: john.fastabend@gmail.com eddyz87@gmail.com sdf@google.com jolsa@kernel.org kpsingh@kernel.org mykolal@fb.com daniel@iogearbox.net martin.lau@linux.dev shuah@kernel.org haoluo@google.com andrii@kernel.org linux-kselftest@vger.kernel.org song@kernel.org
netdev/build_clang success Errors and warnings before: 955 this patch: 955
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: 966 this patch: 966
netdev/checkpatch warning WARNING: Avoid line continuations in quoted strings
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-1 success Logs for ShellCheck
bpf/vmtest-bpf-next-VM_Test-2 success Logs for Unittests
bpf/vmtest-bpf-next-VM_Test-3 success Logs for Validate matrix.py
bpf/vmtest-bpf-next-VM_Test-5 success Logs for aarch64-gcc / build-release
bpf/vmtest-bpf-next-VM_Test-4 success Logs for aarch64-gcc / build / build for aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-10 success Logs for aarch64-gcc / veristat
bpf/vmtest-bpf-next-VM_Test-12 success Logs for s390x-gcc / build-release
bpf/vmtest-bpf-next-VM_Test-11 success Logs for s390x-gcc / build / build for s390x with gcc
bpf/vmtest-bpf-next-VM_Test-9 success Logs for aarch64-gcc / test (test_verifier, false, 360) / test_verifier on aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-17 success Logs for s390x-gcc / veristat
bpf/vmtest-bpf-next-VM_Test-19 success Logs for x86_64-gcc / build / build for x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-18 success Logs for set-matrix
bpf/vmtest-bpf-next-VM_Test-20 success Logs for x86_64-gcc / build-release
bpf/vmtest-bpf-next-VM_Test-6 success Logs for aarch64-gcc / test (test_maps, false, 360) / test_maps on aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-7 success Logs for aarch64-gcc / test (test_progs, false, 360) / test_progs on aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-28 success Logs for x86_64-llvm-17 / build / build for x86_64 with llvm-17
bpf/vmtest-bpf-next-VM_Test-29 success Logs for x86_64-llvm-17 / build-release / build for x86_64 with llvm-17 and -O2 optimization
bpf/vmtest-bpf-next-VM_Test-34 success Logs for x86_64-llvm-17 / veristat
bpf/vmtest-bpf-next-VM_Test-35 success Logs for x86_64-llvm-18 / build / build for x86_64 with llvm-18
bpf/vmtest-bpf-next-VM_Test-36 success Logs for x86_64-llvm-18 / build-release / build for x86_64 with llvm-18 and -O2 optimization
bpf/vmtest-bpf-next-VM_Test-42 success Logs for x86_64-llvm-18 / veristat
bpf/vmtest-bpf-next-VM_Test-8 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-33 success Logs for x86_64-llvm-17 / test (test_verifier, false, 360) / test_verifier on x86_64 with llvm-17
bpf/vmtest-bpf-next-VM_Test-26 success Logs for x86_64-gcc / test (test_verifier, false, 360) / test_verifier on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-21 success Logs for x86_64-gcc / test (test_maps, false, 360) / test_maps on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-24 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-27 success Logs for x86_64-gcc / veristat / veristat on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-25 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-30 success Logs for x86_64-llvm-17 / test (test_maps, false, 360) / test_maps on x86_64 with llvm-17
bpf/vmtest-bpf-next-VM_Test-41 success Logs for x86_64-llvm-18 / test (test_verifier, false, 360) / test_verifier on x86_64 with llvm-18
bpf/vmtest-bpf-next-VM_Test-37 success Logs for x86_64-llvm-18 / test (test_maps, false, 360) / test_maps on x86_64 with llvm-18
bpf/vmtest-bpf-next-VM_Test-22 success Logs for x86_64-gcc / test (test_progs, false, 360) / test_progs on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-23 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-32 success Logs for x86_64-llvm-17 / test (test_progs_no_alu32, false, 360) / test_progs_no_alu32 on x86_64 with llvm-17
bpf/vmtest-bpf-next-VM_Test-31 success Logs for x86_64-llvm-17 / test (test_progs, false, 360) / test_progs on x86_64 with llvm-17
bpf/vmtest-bpf-next-VM_Test-38 success Logs for x86_64-llvm-18 / test (test_progs, false, 360) / test_progs on x86_64 with llvm-18
bpf/vmtest-bpf-next-VM_Test-40 success Logs for x86_64-llvm-18 / test (test_progs_no_alu32, false, 360) / test_progs_no_alu32 on x86_64 with llvm-18
bpf/vmtest-bpf-next-VM_Test-39 success Logs for x86_64-llvm-18 / test (test_progs_cpuv4, false, 360) / test_progs_cpuv4 on x86_64 with llvm-18
bpf/vmtest-bpf-next-VM_Test-16 success Logs for s390x-gcc / test (test_verifier, false, 360) / test_verifier on s390x with gcc
bpf/vmtest-bpf-next-VM_Test-13 success Logs for s390x-gcc / test (test_maps, false, 360) / test_maps on s390x with gcc
bpf/vmtest-bpf-next-VM_Test-14 success Logs for s390x-gcc / test (test_progs, false, 360) / test_progs on s390x with gcc
bpf/vmtest-bpf-next-VM_Test-15 success Logs for s390x-gcc / test (test_progs_no_alu32, false, 360) / test_progs_no_alu32 on s390x with gcc

Commit Message

Cupertino Miranda April 11, 2024, 5:37 p.m. UTC 
MUL instruction required that src_reg would be a known value (i.e.
src_reg would be evaluate as a const value). The condition in this case
can be relaxed, since multiplication is a commutative operator and the
range computation is still valid if at least one of its registers is
known.

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

Signed-off-by: Cupertino Miranda <cupertino.miranda@oracle.com>
---
 kernel/bpf/verifier.c                         | 10 +-
 .../selftests/bpf/progs/verifier_bounds.c     | 99 +++++++++++++++++++
 2 files changed, 105 insertions(+), 4 deletions(-)

Comments

Yonghong Song April 15, 2024, 6:38 p.m. UTC | #1 
On 4/11/24 10:37 AM, Cupertino Miranda wrote:
> MUL instruction required that src_reg would be a known value (i.e.
> src_reg would be evaluate as a const value). The condition in this case
> can be relaxed, since multiplication is a commutative operator and the
> range computation is still valid if at least one of its registers is
> known.
>
> BPF self-tests were added to check the new functionality.
>
> Signed-off-by: Cupertino Miranda <cupertino.miranda@oracle.com>
> ---
>   kernel/bpf/verifier.c                         | 10 +-
>   .../selftests/bpf/progs/verifier_bounds.c     | 99 +++++++++++++++++++
>   2 files changed, 105 insertions(+), 4 deletions(-)
>
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 7894af2e1bdb..a326ec024d82 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -13741,15 +13741,17 @@ static bool is_const_reg_and_valid(struct bpf_reg_state reg, bool alu32,
>   }
>   
>   static bool is_safe_to_compute_dst_reg_ranges(struct bpf_insn *insn,
> +					      struct bpf_reg_state dst_reg,
>   					      struct bpf_reg_state src_reg)
>   {
> -	bool src_known;
> +	bool src_known, dst_known;
>   	u64 insn_bitness = (BPF_CLASS(insn->code) == BPF_ALU64) ? 64 : 32;
>   	bool alu32 = (BPF_CLASS(insn->code) != BPF_ALU64);
>   	u8 opcode = BPF_OP(insn->code);
>   
>   	bool valid_known = true;
>   	src_known = is_const_reg_and_valid(src_reg, alu32, &valid_known);
> +	dst_known = is_const_reg_and_valid(dst_reg, alu32, &valid_known);

Is it a possible the above could falsely reject some operation since
in the original code, dst_reg is not checked here?

>   
>   	/* Taint dst register if offset had invalid bounds
>   	 * derived from e.g. dead branches.
> @@ -13765,10 +13767,10 @@ static bool is_safe_to_compute_dst_reg_ranges(struct bpf_insn *insn,
>   	case BPF_OR:
>   		return true;
>   
> -	/* Compute range for MUL if the src_reg is known.
> +	/* Compute range for MUL if at least one of its registers is know.

know => known

>   	 */
>   	case BPF_MUL:
> -		return src_known;
> +		return src_known || dst_known;
>   
>   	/* Shift operators range is only computable if shift dimension operand
>   	 * is known. Also, shifts greater than 31 or 63 are undefined. This
> @@ -13799,7 +13801,7 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
>   	bool alu32 = (BPF_CLASS(insn->code) != BPF_ALU64);
>   	int ret;
>   
> -	if (!is_safe_to_compute_dst_reg_ranges(insn, src_reg)) {
> +	if (!is_safe_to_compute_dst_reg_ranges(insn, *dst_reg, src_reg)) {
>   		__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

Let us break this commit into two patches: verifier change and selftest change. This will make possible backport easier.

> index 2fcf46341b30..09bb1b270ca7 100644
> --- a/tools/testing/selftests/bpf/progs/verifier_bounds.c
> +++ b/tools/testing/selftests/bpf/progs/verifier_bounds.c
> @@ -949,6 +949,105 @@ l1_%=:	r0 = 0;						\
>   	: __clobber_all);
>   }
>   
[...]
Cupertino Miranda April 16, 2024, 8:57 a.m. UTC | #2 
Hi Yonghong,

Thanks for the reviews. I will prepare a patch series with your
recomendations soon.

> On 4/11/24 10:37 AM, Cupertino Miranda wrote:
>> MUL instruction required that src_reg would be a known value (i.e.
>> src_reg would be evaluate as a const value). The condition in this case
>> can be relaxed, since multiplication is a commutative operator and the
>> range computation is still valid if at least one of its registers is
>> known.
>>
>> BPF self-tests were added to check the new functionality.
>>
>> Signed-off-by: Cupertino Miranda <cupertino.miranda@oracle.com>
>> ---
>>   kernel/bpf/verifier.c                         | 10 +-
>>   .../selftests/bpf/progs/verifier_bounds.c     | 99 +++++++++++++++++++
>>   2 files changed, 105 insertions(+), 4 deletions(-)
>>
>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
>> index 7894af2e1bdb..a326ec024d82 100644
>> --- a/kernel/bpf/verifier.c
>> +++ b/kernel/bpf/verifier.c
>> @@ -13741,15 +13741,17 @@ static bool is_const_reg_and_valid(struct bpf_reg_state reg, bool alu32,
>>   }
>>     static bool is_safe_to_compute_dst_reg_ranges(struct bpf_insn *insn,
>> +					      struct bpf_reg_state dst_reg,
>>   					      struct bpf_reg_state src_reg)
>>   {
>> -	bool src_known;
>> +	bool src_known, dst_known;
>>   	u64 insn_bitness = (BPF_CLASS(insn->code) == BPF_ALU64) ? 64 : 32;
>>   	bool alu32 = (BPF_CLASS(insn->code) != BPF_ALU64);
>>   	u8 opcode = BPF_OP(insn->code);
>>     	bool valid_known = true;
>>   	src_known = is_const_reg_and_valid(src_reg, alu32, &valid_known);
>> +	dst_known = is_const_reg_and_valid(dst_reg, alu32, &valid_known);
>
> Is it a possible the above could falsely reject some operation since
> in the original code, dst_reg is not checked here?
I guess, I believe in the case where min/max information is not matching
tnum value/mask, when the value is known.
My thoguht was that there would be no arm, since it could not
rely on that known value to compute MUL ranges anyway.
Still, I just realized this applies for all the other expressions, so
indeed it is rejecting and need some more patching.

>>     	/* Taint dst register if offset had invalid bounds
>>   	 * derived from e.g. dead branches.
>> @@ -13765,10 +13767,10 @@ static bool is_safe_to_compute_dst_reg_ranges(struct bpf_insn *insn,
>>   	case BPF_OR:
>>   		return true;
>>   -	/* Compute range for MUL if the src_reg is known.
>> +	/* Compute range for MUL if at least one of its registers is know.
>
> know => known
>
>>   	 */
>>   	case BPF_MUL:
>> -		return src_known;
>> +		return src_known || dst_known;
>>     	/* Shift operators range is only computable if shift dimension operand
>>   	 * is known. Also, shifts greater than 31 or 63 are undefined. This
>> @@ -13799,7 +13801,7 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
>>   	bool alu32 = (BPF_CLASS(insn->code) != BPF_ALU64);
>>   	int ret;
>>   -	if (!is_safe_to_compute_dst_reg_ranges(insn, src_reg)) {
>> +	if (!is_safe_to_compute_dst_reg_ranges(insn, *dst_reg, src_reg)) {
>>   		__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
>
> Let us break this commit into two patches: verifier change and selftest change. This will make possible backport easier.
>
>> index 2fcf46341b30..09bb1b270ca7 100644
>> --- a/tools/testing/selftests/bpf/progs/verifier_bounds.c
>> +++ b/tools/testing/selftests/bpf/progs/verifier_bounds.c
>> @@ -949,6 +949,105 @@ l1_%=:	r0 = 0;						\
>>   	: __clobber_all);
>>   }
>>
> [...]
diff mbox series

Patch

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 7894af2e1bdb..a326ec024d82 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -13741,15 +13741,17 @@  static bool is_const_reg_and_valid(struct bpf_reg_state reg, bool alu32,
 }
 
 static bool is_safe_to_compute_dst_reg_ranges(struct bpf_insn *insn,
+					      struct bpf_reg_state dst_reg,
 					      struct bpf_reg_state src_reg)
 {
-	bool src_known;
+	bool src_known, dst_known;
 	u64 insn_bitness = (BPF_CLASS(insn->code) == BPF_ALU64) ? 64 : 32;
 	bool alu32 = (BPF_CLASS(insn->code) != BPF_ALU64);
 	u8 opcode = BPF_OP(insn->code);
 
 	bool valid_known = true;
 	src_known = is_const_reg_and_valid(src_reg, alu32, &valid_known);
+	dst_known = is_const_reg_and_valid(dst_reg, alu32, &valid_known);
 
 	/* Taint dst register if offset had invalid bounds
 	 * derived from e.g. dead branches.
@@ -13765,10 +13767,10 @@  static bool is_safe_to_compute_dst_reg_ranges(struct bpf_insn *insn,
 	case BPF_OR:
 		return true;
 
-	/* Compute range for MUL if the src_reg is known.
+	/* Compute range for MUL if at least one of its registers is know.
 	 */
 	case BPF_MUL:
-		return src_known;
+		return src_known || dst_known;
 
 	/* Shift operators range is only computable if shift dimension operand
 	 * is known. Also, shifts greater than 31 or 63 are undefined. This
@@ -13799,7 +13801,7 @@  static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
 	bool alu32 = (BPF_CLASS(insn->code) != BPF_ALU64);
 	int ret;
 
-	if (!is_safe_to_compute_dst_reg_ranges(insn, src_reg)) {
+	if (!is_safe_to_compute_dst_reg_ranges(insn, *dst_reg, src_reg)) {
 		__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 2fcf46341b30..09bb1b270ca7 100644
--- a/tools/testing/selftests/bpf/progs/verifier_bounds.c
+++ b/tools/testing/selftests/bpf/progs/verifier_bounds.c
@@ -949,6 +949,105 @@  l1_%=:	r0 = 0;						\
 	: __clobber_all);
 }
 
+SEC("socket")
+__description("bounds check for reg32 <= 9, 3 mul (0,3)")
+__success __failure_unpriv
+__msg_unpriv("R0 min value is outside of the allowed memory range")
+__retval(0)
+__naked void reg32_3_mul_reg_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 = 3;						\
+	r6 >>= 62;					\
+	w1 *= w6;					\
+	if w1 <= 9 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 <= 9, (0,3) mul 3")
+__success __failure_unpriv
+__msg_unpriv("R0 min value is outside of the allowed memory range")
+__retval(0)
+__naked void reg32_13_mul_reg_3(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 = 3;						\
+	r6 >>= 62;					\
+	w6 *= w1;					\
+	if w6 <= 9 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 >= 6 && reg32 <= 15, (2,5) mul 3")
+__success __failure_unpriv
+__msg_unpriv("R0 min value is outside of the allowed memory range")
+__retval(0)
+__naked void reg32_25_mul_reg_3(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 = 3;						\
+	r6 >>= 62;					\
+	r6 += 2;					\
+	w6 *= w1;					\
+	if w6 > 15 goto l1_%=;				\
+	if w6 < 6 goto l1_%=;				\
+	r0 = 0;						\
+	exit;						\
+l1_%=:  r0 = *(u64*)(r0 + 8);				\
+	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")