Skip to contentSkip to conversation

bpf: avoid verifier failure for 32bit pointer arithmetic

PATCH In review Yonghong Song 3 participants 6 messages Jun 18, 2020 – Jun 19, 2020

Subsystems (4)
lore
Share & tools
lore
#0 lore raw

cover bpf: avoid verifier failure for 32bit pointer arithmetic

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(+)
Signature · 1 line
2.24.1
#1 lore raw

PATCH 1/2 bpf: avoid verifier failure for 32bit pointer arithmetic

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.

---
 kernel/bpf/verifier.c | 5 +++++
 1 file changed, 5 insertions(+)
kernel/bpf/verifier.c +5 -0
index 22d90d47befa..bbf6d655d6ad 100644
@@ -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);
Signature · 1 line
2.24.1
reviewer Acked-by on v1 1/2
#2 lore raw
Quoted 28 lines · 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.

Quoted 6 lines

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.

---

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

maintainer
#3 lore raw
In reply to Yonghong Song
Quoted 25 lines · 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.

Quoted 8 lines

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.

Looks good, both applied, thanks!

Quoted 9 lines
---
  kernel/bpf/verifier.c | 5 +++++
  1 file changed, 5 insertions(+)
kernel/bpf/verifier.c +0 -0
index 22d90d47befa..bbf6d655d6ad 100644

kernel/bpf/verifier.c static int adjust_ptr_min_max_vals(struct bpf_verifier_env *env, · line 5059

Quoted 8 lines
kernel/bpf/verifier.c +5 -0
@@ -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.

Quoted 4 lines
kernel/bpf/verifier.c +0 -0
  		verbose(env,
  			"R%d 32-bit pointer arithmetic prohibited\n",
  			dst);
#4 lore raw
Quoted 50 lines · Daniel Borkmann
Quoted 25 lines · 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.

Quoted 8 lines

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.

Looks good, both applied, thanks!

Quoted 13 lines

---
  kernel/bpf/verifier.c | 5 +++++

  1 file changed, 5 insertions(+)
kernel/bpf/verifier.c +1 -0
index 22d90d47befa..bbf6d655d6ad 100644
@@ -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) {
Quoted 8 lines

kernel/bpf/verifier.c static int adjust_ptr_min_max_vals(struct bpf_verifier_env *env, · line 5059

Quoted 4 lines
kernel/bpf/verifier.c +4 -0
+            __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.

Quoted 6 lines
Quoted 5 lines
kernel/bpf/verifier.c +0 -0
           verbose(env,
               "R%d 32-bit pointer arithmetic prohibited\n",
               dst);
#5 lore raw

PATCH 2/2 tools/bpf: add verifier tests for 32bit pointer/scalar arithmetic

In reply to Yonghong Song

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

---
 .../selftests/bpf/verifier/value_ptr_arith.c  | 38 +++++++++++++++++++
 1 file changed, 38 insertions(+)
tools/testing/selftests/bpf/verifier/value_ptr_arith.c +38 -0
index 97ee658e1242..ed4e76b24649 100644
@@ -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,
+},
Signature · 1 line
2.24.1