[PATCH bpf-next 1/2] bpf: avoid verifier failure for 32bit pointer arithmetic

[PATCH bpf-next 1/2] bpf: avoid verifier failure for 32bit pointer arithmetic

[Yonghong Song]

When do experiments with llvm (disabling instcombine and
simplifyCFG), I hit the following error with test_seg6_loop.o.

  ; R1=pkt(id=0,off=0,r=48,imm=0), R7=pkt(id=0,off=40,r=48,imm=0)
  w2 = w7
  ; R2_w=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff))
  w2 -= w1
  R2 32-bit pointer arithmetic prohibited

The corresponding source code is:
  uint32_t srh_off
  // srh and skb->data are all packet pointers
  srh_off = (char *)srh - (char *)(long)skb->data;

The verifier does not support 32-bit pointer/scalar arithmetic.

Without my llvm change, the code looks like

  ; R3=pkt(id=0,off=40,r=48,imm=0), R8=pkt(id=0,off=0,r=48,imm=0)
  w3 -= w8
  ; R3_w=inv(id=0)

This is explicitly allowed in verifier if both registers are
pointers and the opcode is BPF_SUB.

To fix this problem, I changed the verifier to allow
32-bit pointer/scaler BPF_SUB operations.

At the source level, the issue could be workarounded with
inline asm or changing "uint32_t srh_off" to "uint64_t srh_off".
But I feel that verifier change might be the right thing to do.

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

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 22d90d47befa..bbf6d655d6ad 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -5052,6 +5052,11 @@ static int adjust_ptr_min_max_vals(struct bpf_verifier_env *env,
 
 	if (BPF_CLASS(insn->code) != BPF_ALU64) {
 		/* 32-bit ALU ops on pointers produce (meaningless) scalars */
+		if (opcode == BPF_SUB && env->allow_ptr_leaks) {
+			__mark_reg_unknown(env, dst_reg);
+			return 0;
+		}
+
 		verbose(env,
 			"R%d 32-bit pointer arithmetic prohibited\n",
 			dst);
-- 
2.24.1

[PATCH bpf-next 0/2] bpf: avoid verifier failure for 32bit pointer arithmetic

[Yonghong Song]

This patch set tried to fix a verifier failure
related to 32bit pointer arithmetic. Please see Patch #1
for the failure case and how to fix it in verifier.
Patch #2 added two test_verifier subtests to cover
the verifier change.

Yonghong Song (2):
  bpf: avoid verifier failure for 32bit pointer arithmetic
  tools/bpf: add verifier tests for 32bit pointer/scalar arithmetic

 kernel/bpf/verifier.c                         |  5 +++
 .../selftests/bpf/verifier/value_ptr_arith.c  | 38 +++++++++++++++++++
 2 files changed, 43 insertions(+)

-- 
2.24.1

[PATCH bpf-next 2/2] tools/bpf: add verifier tests for 32bit pointer/scalar arithmetic

[Yonghong Song]

Added two test_verifier subtests for 32bit pointer/scalar arithmetic
with BPF_SUB operator. They are passing verifier now.

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

diff --git a/tools/testing/selftests/bpf/verifier/value_ptr_arith.c b/tools/testing/selftests/bpf/verifier/value_ptr_arith.c
index 97ee658e1242..ed4e76b24649 100644
--- a/tools/testing/selftests/bpf/verifier/value_ptr_arith.c
+++ b/tools/testing/selftests/bpf/verifier/value_ptr_arith.c
@@ -836,3 +836,41 @@
 	.errstr = "R0 invalid mem access 'inv'",
 	.errstr_unpriv = "R0 pointer -= pointer prohibited",
 },
+{
+	"32bit pkt_ptr -= scalar",
+	.insns = {
+	BPF_LDX_MEM(BPF_W, BPF_REG_8, BPF_REG_1,
+		    offsetof(struct __sk_buff, data_end)),
+	BPF_LDX_MEM(BPF_W, BPF_REG_7, BPF_REG_1,
+		    offsetof(struct __sk_buff, data)),
+	BPF_MOV64_REG(BPF_REG_6, BPF_REG_7),
+	BPF_ALU64_IMM(BPF_ADD, BPF_REG_6, 40),
+	BPF_JMP_REG(BPF_JGT, BPF_REG_6, BPF_REG_8, 2),
+	BPF_ALU32_REG(BPF_MOV, BPF_REG_4, BPF_REG_7),
+	BPF_ALU32_REG(BPF_SUB, BPF_REG_6, BPF_REG_4),
+	BPF_MOV64_IMM(BPF_REG_0, 0),
+	BPF_EXIT_INSN(),
+	},
+	.prog_type = BPF_PROG_TYPE_SCHED_CLS,
+	.result = ACCEPT,
+	.flags = F_NEEDS_EFFICIENT_UNALIGNED_ACCESS,
+},
+{
+	"32bit scalar -= pkt_ptr",
+	.insns = {
+	BPF_LDX_MEM(BPF_W, BPF_REG_8, BPF_REG_1,
+		    offsetof(struct __sk_buff, data_end)),
+	BPF_LDX_MEM(BPF_W, BPF_REG_7, BPF_REG_1,
+		    offsetof(struct __sk_buff, data)),
+	BPF_MOV64_REG(BPF_REG_6, BPF_REG_7),
+	BPF_ALU64_IMM(BPF_ADD, BPF_REG_6, 40),
+	BPF_JMP_REG(BPF_JGT, BPF_REG_6, BPF_REG_8, 2),
+	BPF_ALU32_REG(BPF_MOV, BPF_REG_4, BPF_REG_6),
+	BPF_ALU32_REG(BPF_SUB, BPF_REG_4, BPF_REG_7),
+	BPF_MOV64_IMM(BPF_REG_0, 0),
+	BPF_EXIT_INSN(),
+	},
+	.prog_type = BPF_PROG_TYPE_SCHED_CLS,
+	.result = ACCEPT,
+	.flags = F_NEEDS_EFFICIENT_UNALIGNED_ACCESS,
+},
-- 
2.24.1

RE: [PATCH bpf-next 1/2] bpf: avoid verifier failure for 32bit pointer arithmetic

[John Fastabend]

Yonghong Song wrote:
> When do experiments with llvm (disabling instcombine and
> simplifyCFG), I hit the following error with test_seg6_loop.o.
> 
>   ; R1=pkt(id=0,off=0,r=48,imm=0), R7=pkt(id=0,off=40,r=48,imm=0)
>   w2 = w7
>   ; R2_w=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff))
>   w2 -= w1
>   R2 32-bit pointer arithmetic prohibited
> 
> The corresponding source code is:
>   uint32_t srh_off
>   // srh and skb->data are all packet pointers
>   srh_off = (char *)srh - (char *)(long)skb->data;
> 
> The verifier does not support 32-bit pointer/scalar arithmetic.
> 
> Without my llvm change, the code looks like
> 
>   ; R3=pkt(id=0,off=40,r=48,imm=0), R8=pkt(id=0,off=0,r=48,imm=0)
>   w3 -= w8
>   ; R3_w=inv(id=0)
> 
> This is explicitly allowed in verifier if both registers are
> pointers and the opcode is BPF_SUB.
> 
> To fix this problem, I changed the verifier to allow
> 32-bit pointer/scaler BPF_SUB operations.
> 
> At the source level, the issue could be workarounded with
> inline asm or changing "uint32_t srh_off" to "uint64_t srh_off".
> But I feel that verifier change might be the right thing to do.
> 
> Signed-off-by: Yonghong Song <yhs@fb.com>
> ---

Agreed we have same logic in 64-bit case so LGTM.

Acked-by: John Fastabend <john.fastabend@gmail.com>

Re: [PATCH bpf-next 1/2] bpf: avoid verifier failure for 32bit pointer arithmetic

[Daniel Borkmann]

On 6/19/20 1:46 AM, Yonghong Song wrote:
> When do experiments with llvm (disabling instcombine and
> simplifyCFG), I hit the following error with test_seg6_loop.o.
> 
>    ; R1=pkt(id=0,off=0,r=48,imm=0), R7=pkt(id=0,off=40,r=48,imm=0)
>    w2 = w7
>    ; R2_w=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff))
>    w2 -= w1
>    R2 32-bit pointer arithmetic prohibited
> 
> The corresponding source code is:
>    uint32_t srh_off
>    // srh and skb->data are all packet pointers
>    srh_off = (char *)srh - (char *)(long)skb->data;
> 
> The verifier does not support 32-bit pointer/scalar arithmetic.
> 
> Without my llvm change, the code looks like
> 
>    ; R3=pkt(id=0,off=40,r=48,imm=0), R8=pkt(id=0,off=0,r=48,imm=0)
>    w3 -= w8
>    ; R3_w=inv(id=0)
> 
> This is explicitly allowed in verifier if both registers are
> pointers and the opcode is BPF_SUB.
> 
> To fix this problem, I changed the verifier to allow
> 32-bit pointer/scaler BPF_SUB operations.
> 
> At the source level, the issue could be workarounded with
> inline asm or changing "uint32_t srh_off" to "uint64_t srh_off".
> But I feel that verifier change might be the right thing to do.
> 
> Signed-off-by: Yonghong Song <yhs@fb.com>

Looks good, both applied, thanks!

> ---
>   kernel/bpf/verifier.c | 5 +++++
>   1 file changed, 5 insertions(+)
> 
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 22d90d47befa..bbf6d655d6ad 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -5052,6 +5052,11 @@ static int adjust_ptr_min_max_vals(struct bpf_verifier_env *env,
>   
>   	if (BPF_CLASS(insn->code) != BPF_ALU64) {
>   		/* 32-bit ALU ops on pointers produce (meaningless) scalars */
> +		if (opcode == BPF_SUB && env->allow_ptr_leaks) {
> +			__mark_reg_unknown(env, dst_reg);
> +			return 0;
> +		}
> +

We could have also allowed ADD case while at it, but ok either way. Wrt pointer
sanitation, nothing additional seems to be needed here as we 'destroy' the reg
to fully unknown.

>   		verbose(env,
>   			"R%d 32-bit pointer arithmetic prohibited\n",
>   			dst);
> 

Re: [PATCH bpf-next 1/2] bpf: avoid verifier failure for 32bit pointer arithmetic

[Yonghong Song]

On 6/19/20 2:49 PM, Daniel Borkmann wrote:
> On 6/19/20 1:46 AM, Yonghong Song wrote:
>> When do experiments with llvm (disabling instcombine and
>> simplifyCFG), I hit the following error with test_seg6_loop.o.
>>
>>    ; R1=pkt(id=0,off=0,r=48,imm=0), R7=pkt(id=0,off=40,r=48,imm=0)
>>    w2 = w7
>>    ; R2_w=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff))
>>    w2 -= w1
>>    R2 32-bit pointer arithmetic prohibited
>>
>> The corresponding source code is:
>>    uint32_t srh_off
>>    // srh and skb->data are all packet pointers
>>    srh_off = (char *)srh - (char *)(long)skb->data;
>>
>> The verifier does not support 32-bit pointer/scalar arithmetic.
>>
>> Without my llvm change, the code looks like
>>
>>    ; R3=pkt(id=0,off=40,r=48,imm=0), R8=pkt(id=0,off=0,r=48,imm=0)
>>    w3 -= w8
>>    ; R3_w=inv(id=0)
>>
>> This is explicitly allowed in verifier if both registers are
>> pointers and the opcode is BPF_SUB.
>>
>> To fix this problem, I changed the verifier to allow
>> 32-bit pointer/scaler BPF_SUB operations.
>>
>> At the source level, the issue could be workarounded with
>> inline asm or changing "uint32_t srh_off" to "uint64_t srh_off".
>> But I feel that verifier change might be the right thing to do.
>>
>> Signed-off-by: Yonghong Song <yhs@fb.com>
> 
> Looks good, both applied, thanks!
> 
>> ---
>>   kernel/bpf/verifier.c | 5 +++++
>>   1 file changed, 5 insertions(+)
>>
>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
>> index 22d90d47befa..bbf6d655d6ad 100644
>> --- a/kernel/bpf/verifier.c
>> +++ b/kernel/bpf/verifier.c
>> @@ -5052,6 +5052,11 @@ static int adjust_ptr_min_max_vals(struct 
>> bpf_verifier_env *env,
>>       if (BPF_CLASS(insn->code) != BPF_ALU64) {
>>           /* 32-bit ALU ops on pointers produce (meaningless) scalars */
>> +        if (opcode == BPF_SUB && env->allow_ptr_leaks) {
>> +            __mark_reg_unknown(env, dst_reg);
>> +            return 0;
>> +        }
>> +
> 
> We could have also allowed ADD case while at it, but ok either way. Wrt 
> pointer
> sanitation, nothing additional seems to be needed here as we 'destroy' 
> the reg
> to fully unknown.

Right. This may happen for use case like `(w1 + off) - w2` where w1 and 
w2 are packet pointers and off is a register to encode a scalar. I will 
do a followup on this.

> 
>>           verbose(env,
>>               "R%d 32-bit pointer arithmetic prohibited\n",
>>               dst);
>>
>