diff mbox series

[bpf-next,1/7] bpf: Improve verifier JEQ/JNE insn branch taken checking

Message ID 20230330055605.88807-1-yhs@fb.com (mailing list archive)
State Superseded
Delegated to: BPF
Headers show
Series bpf: Improve verifier for cond_op and spilled loop index variables | expand

Checks

Context Check Description
netdev/series_format success Posting correctly formatted
netdev/tree_selection success Clearly marked for bpf-next, async
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: 28 this patch: 28
netdev/cc_maintainers warning 7 maintainers not CCed: song@kernel.org sdf@google.com haoluo@google.com john.fastabend@gmail.com kpsingh@kernel.org jolsa@kernel.org martin.lau@linux.dev
netdev/build_clang success Errors and warnings before: 18 this patch: 18
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: 28 this patch: 28
netdev/checkpatch success total: 0 errors, 0 warnings, 0 checks, 28 lines checked
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-10 fail Logs for test_maps on s390x with gcc
bpf/vmtest-bpf-next-VM_Test-15 success Logs for test_progs on s390x with gcc
bpf/vmtest-bpf-next-PR success PR summary
bpf/vmtest-bpf-next-VM_Test-1 success Logs for ShellCheck
bpf/vmtest-bpf-next-VM_Test-2 success Logs for build for aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-3 success Logs for build for aarch64 with llvm-16
bpf/vmtest-bpf-next-VM_Test-5 success Logs for build for x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-6 success Logs for build for x86_64 with llvm-16
bpf/vmtest-bpf-next-VM_Test-7 success Logs for set-matrix
bpf/vmtest-bpf-next-VM_Test-4 success Logs for build for s390x with gcc
bpf/vmtest-bpf-next-VM_Test-8 success Logs for test_maps on aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-9 success Logs for test_maps on aarch64 with llvm-16
bpf/vmtest-bpf-next-VM_Test-11 success Logs for test_maps on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-12 success Logs for test_maps on x86_64 with llvm-16
bpf/vmtest-bpf-next-VM_Test-17 success Logs for test_progs on x86_64 with llvm-16
bpf/vmtest-bpf-next-VM_Test-18 success Logs for test_progs_no_alu32 on aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-19 success Logs for test_progs_no_alu32 on aarch64 with llvm-16
bpf/vmtest-bpf-next-VM_Test-21 success Logs for test_progs_no_alu32 on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-22 success Logs for test_progs_no_alu32 on x86_64 with llvm-16
bpf/vmtest-bpf-next-VM_Test-23 success Logs for test_progs_no_alu32_parallel on aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-24 success Logs for test_progs_no_alu32_parallel on aarch64 with llvm-16
bpf/vmtest-bpf-next-VM_Test-25 success Logs for test_progs_no_alu32_parallel on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-26 success Logs for test_progs_no_alu32_parallel on x86_64 with llvm-16
bpf/vmtest-bpf-next-VM_Test-27 success Logs for test_progs_parallel on aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-28 success Logs for test_progs_parallel on aarch64 with llvm-16
bpf/vmtest-bpf-next-VM_Test-29 success Logs for test_progs_parallel on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-30 success Logs for test_progs_parallel on x86_64 with llvm-16
bpf/vmtest-bpf-next-VM_Test-31 success Logs for test_verifier on aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-32 success Logs for test_verifier on aarch64 with llvm-16
bpf/vmtest-bpf-next-VM_Test-34 success Logs for test_verifier on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-35 success Logs for test_verifier on x86_64 with llvm-16
bpf/vmtest-bpf-next-VM_Test-13 success Logs for test_progs on aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-14 success Logs for test_progs on aarch64 with llvm-16
bpf/vmtest-bpf-next-VM_Test-16 success Logs for test_progs on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-20 success Logs for test_progs_no_alu32 on s390x with gcc
bpf/vmtest-bpf-next-VM_Test-33 success Logs for test_verifier on s390x with gcc

Commit Message

Yonghong Song March 30, 2023, 5:56 a.m. UTC 
Currently, for BPF_JEQ/BPF_JNE insn, verifier determines
whether the branch is taken or not only if both operands
are constants. Therefore, for the following code snippet,
  0: (85) call bpf_ktime_get_ns#5       ; R0_w=scalar()
  1: (a5) if r0 < 0x3 goto pc+2         ; R0_w=scalar(umin=3)
  2: (b7) r2 = 2                        ; R2_w=2
  3: (1d) if r0 == r2 goto pc+2 6

At insn 3, since r0 is not a constant, verifier assumes both branch
can be taken which may lead inproper verification failure.

Add comparing umin value and the constant. If the umin value
is greater than the constant, for JEQ the branch must be
not-taken, and for JNE the branch must be taken.
The jmp32 mode JEQ/JNE branch taken checking is also
handled similarly.

Signed-off-by: Yonghong Song <yhs@fb.com>
---
 kernel/bpf/verifier.c | 8 ++++++++
 1 file changed, 8 insertions(+)

Comments

Dave Marchevsky March 30, 2023, 9:14 p.m. UTC | #1 
On 3/30/23 1:56 AM, Yonghong Song wrote:
> Currently, for BPF_JEQ/BPF_JNE insn, verifier determines
> whether the branch is taken or not only if both operands
> are constants. Therefore, for the following code snippet,
>   0: (85) call bpf_ktime_get_ns#5       ; R0_w=scalar()
>   1: (a5) if r0 < 0x3 goto pc+2         ; R0_w=scalar(umin=3)
>   2: (b7) r2 = 2                        ; R2_w=2
>   3: (1d) if r0 == r2 goto pc+2 6
> 
> At insn 3, since r0 is not a constant, verifier assumes both branch
> can be taken which may lead inproper verification failure.
> 
> Add comparing umin value and the constant. If the umin value
> is greater than the constant, for JEQ the branch must be
> not-taken, and for JNE the branch must be taken.
> The jmp32 mode JEQ/JNE branch taken checking is also
> handled similarly.
> 
> Signed-off-by: Yonghong Song <yhs@fb.com>
> ---
>  kernel/bpf/verifier.c | 8 ++++++++
>  1 file changed, 8 insertions(+)
> 
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 20eb2015842f..90bb6d25bc9c 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -12597,10 +12597,14 @@ static int is_branch32_taken(struct bpf_reg_state *reg, u32 val, u8 opcode)
>  	case BPF_JEQ:
>  		if (tnum_is_const(subreg))
>  			return !!tnum_equals_const(subreg, val);
> +		else if (reg->u32_min_value > val)
> +			return 0;
>  		break;

The explanation makes sense to me, and I see similar min_value logic elsewhere
in the switch for other jmp types. But those other jmp types are bounding the
value from one side. Since JEQ and JNE test equality, can't we also add logic
for u32_max_value here? e.g.

        case BPF_JEQ:
                if (tnum_is_const(subreg))
                        return !!tnum_equals_const(subreg, val);
                else if (reg->u32_min_value > val || reg->u32_max_value < val)
                        return 0;
                break;

Similar comment for rest of additions.

>  	case BPF_JNE:
>  		if (tnum_is_const(subreg))
>  			return !tnum_equals_const(subreg, val);
> +		else if (reg->u32_min_value > val)
> +			return 1;
>  		break;
>  	case BPF_JSET:
>  		if ((~subreg.mask & subreg.value) & val)
> @@ -12670,10 +12674,14 @@ static int is_branch64_taken(struct bpf_reg_state *reg, u64 val, u8 opcode)
>  	case BPF_JEQ:
>  		if (tnum_is_const(reg->var_off))
>  			return !!tnum_equals_const(reg->var_off, val);
> +		else if (reg->umin_value > val)
> +			return 0;
>  		break;
>  	case BPF_JNE:
>  		if (tnum_is_const(reg->var_off))
>  			return !tnum_equals_const(reg->var_off, val);
> +		else if (reg->umin_value > val)
> +			return 1;
>  		break;
>  	case BPF_JSET:
>  		if ((~reg->var_off.mask & reg->var_off.value) & val)
Yonghong Song March 31, 2023, 6:40 a.m. UTC | #2 
On 3/30/23 2:14 PM, Dave Marchevsky wrote:
> 
> 
> On 3/30/23 1:56 AM, Yonghong Song wrote:
>> Currently, for BPF_JEQ/BPF_JNE insn, verifier determines
>> whether the branch is taken or not only if both operands
>> are constants. Therefore, for the following code snippet,
>>    0: (85) call bpf_ktime_get_ns#5       ; R0_w=scalar()
>>    1: (a5) if r0 < 0x3 goto pc+2         ; R0_w=scalar(umin=3)
>>    2: (b7) r2 = 2                        ; R2_w=2
>>    3: (1d) if r0 == r2 goto pc+2 6
>>
>> At insn 3, since r0 is not a constant, verifier assumes both branch
>> can be taken which may lead inproper verification failure.
>>
>> Add comparing umin value and the constant. If the umin value
>> is greater than the constant, for JEQ the branch must be
>> not-taken, and for JNE the branch must be taken.
>> The jmp32 mode JEQ/JNE branch taken checking is also
>> handled similarly.
>>
>> Signed-off-by: Yonghong Song <yhs@fb.com>
>> ---
>>   kernel/bpf/verifier.c | 8 ++++++++
>>   1 file changed, 8 insertions(+)
>>
>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
>> index 20eb2015842f..90bb6d25bc9c 100644
>> --- a/kernel/bpf/verifier.c
>> +++ b/kernel/bpf/verifier.c
>> @@ -12597,10 +12597,14 @@ static int is_branch32_taken(struct bpf_reg_state *reg, u32 val, u8 opcode)
>>   	case BPF_JEQ:
>>   		if (tnum_is_const(subreg))
>>   			return !!tnum_equals_const(subreg, val);
>> +		else if (reg->u32_min_value > val)
>> +			return 0;
>>   		break;
> 
> The explanation makes sense to me, and I see similar min_value logic elsewhere
> in the switch for other jmp types. But those other jmp types are bounding the
> value from one side. Since JEQ and JNE test equality, can't we also add logic
> for u32_max_value here? e.g.
> 
>          case BPF_JEQ:
>                  if (tnum_is_const(subreg))
>                          return !!tnum_equals_const(subreg, val);
>                  else if (reg->u32_min_value > val || reg->u32_max_value < val)
>                          return 0;
>                  break;
> 
> Similar comment for rest of additions.
> 

Sounds good. I agree reg->u32_max_value < val should ensure the branch
not taken too. Will accommodate this change in the next revision.

>>   	case BPF_JNE:
>>   		if (tnum_is_const(subreg))
>>   			return !tnum_equals_const(subreg, val);
>> +		else if (reg->u32_min_value > val)
>> +			return 1;
>>   		break;
>>   	case BPF_JSET:
>>   		if ((~subreg.mask & subreg.value) & val)
>> @@ -12670,10 +12674,14 @@ static int is_branch64_taken(struct bpf_reg_state *reg, u64 val, u8 opcode)
>>   	case BPF_JEQ:
>>   		if (tnum_is_const(reg->var_off))
>>   			return !!tnum_equals_const(reg->var_off, val);
>> +		else if (reg->umin_value > val)
>> +			return 0;
>>   		break;
>>   	case BPF_JNE:
>>   		if (tnum_is_const(reg->var_off))
>>   			return !tnum_equals_const(reg->var_off, val);
>> +		else if (reg->umin_value > val)
>> +			return 1;
>>   		break;
>>   	case BPF_JSET:
>>   		if ((~reg->var_off.mask & reg->var_off.value) & val)
diff mbox series

Patch

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 20eb2015842f..90bb6d25bc9c 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -12597,10 +12597,14 @@  static int is_branch32_taken(struct bpf_reg_state *reg, u32 val, u8 opcode)
 	case BPF_JEQ:
 		if (tnum_is_const(subreg))
 			return !!tnum_equals_const(subreg, val);
+		else if (reg->u32_min_value > val)
+			return 0;
 		break;
 	case BPF_JNE:
 		if (tnum_is_const(subreg))
 			return !tnum_equals_const(subreg, val);
+		else if (reg->u32_min_value > val)
+			return 1;
 		break;
 	case BPF_JSET:
 		if ((~subreg.mask & subreg.value) & val)
@@ -12670,10 +12674,14 @@  static int is_branch64_taken(struct bpf_reg_state *reg, u64 val, u8 opcode)
 	case BPF_JEQ:
 		if (tnum_is_const(reg->var_off))
 			return !!tnum_equals_const(reg->var_off, val);
+		else if (reg->umin_value > val)
+			return 0;
 		break;
 	case BPF_JNE:
 		if (tnum_is_const(reg->var_off))
 			return !tnum_equals_const(reg->var_off, val);
+		else if (reg->umin_value > val)
+			return 1;
 		break;
 	case BPF_JSET:
 		if ((~reg->var_off.mask & reg->var_off.value) & val)