BPF Archive on lore.kernel.org
 help / color / Atom feed
* [bpf PATCH 0/3] verifier fix for assigning 32bit reg to 64bit reg
@ 2020-05-29 17:28 John Fastabend
  2020-05-29 17:28 ` [bpf PATCH 1/3] bpf: fix a verifier issue when assigning 32bit reg states to 64bit ones John Fastabend
                   ` (3 more replies)
  0 siblings, 4 replies; 7+ messages in thread
From: John Fastabend @ 2020-05-29 17:28 UTC (permalink / raw)
  To: yhs, alexei.starovoitov, daniel; +Cc: bpf, john.fastabend, kernel-team

These add a fix for 32 bit to 64 bit assignment introduced with
latest alu32 bounds tracking. The initial fix was proposed by
Yonghong and then I updated it slightly and added a test fix.

@Yonghong feel free to add your signed-off-by back if you want
or at minimal a ACK would be good.

---

John Fastabend (3):
      bpf: fix a verifier issue when assigning 32bit reg states to 64bit ones
      bpf, selftests: verifier bounds tests need to be updated
      bpf, selftests: add a verifier test for assigning 32bit reg states to 64bit ones


 kernel/bpf/verifier.c                         |   10 +++--
 tools/testing/selftests/bpf/verifier/bounds.c |   46 +++++++++++++++++--------
 2 files changed, 37 insertions(+), 19 deletions(-)

--
Signature

^ permalink raw reply	[flat|nested] 7+ messages in thread

* [bpf PATCH 1/3] bpf: fix a verifier issue when assigning 32bit reg states to 64bit ones
  2020-05-29 17:28 [bpf PATCH 0/3] verifier fix for assigning 32bit reg to 64bit reg John Fastabend
@ 2020-05-29 17:28 ` John Fastabend
  2020-05-29 18:40   ` Yonghong Song
  2020-05-29 17:28 ` [bpf PATCH 2/3] bpf, selftests: verifier bounds tests need to be updated John Fastabend
                   ` (2 subsequent siblings)
  3 siblings, 1 reply; 7+ messages in thread
From: John Fastabend @ 2020-05-29 17:28 UTC (permalink / raw)
  To: yhs, alexei.starovoitov, daniel; +Cc: bpf, john.fastabend, kernel-team

With the latest trunk llvm (llvm 11), I hit a verifier issue for
test_prog subtest test_verif_scale1.

The following simplified example illustrate the issue:
    w9 = 0  /* R9_w=inv0 */
    r8 = *(u32 *)(r1 + 80)  /* __sk_buff->data_end */
    r7 = *(u32 *)(r1 + 76)  /* __sk_buff->data */
    ......
    w2 = w9 /* R2_w=inv0 */
    r6 = r7 /* R6_w=pkt(id=0,off=0,r=0,imm=0) */
    r6 += r2 /* R6_w=inv(id=0) */
    r3 = r6 /* R3_w=inv(id=0) */
    r3 += 14 /* R3_w=inv(id=0) */
    if r3 > r8 goto end
    r5 = *(u32 *)(r6 + 0) /* R6_w=inv(id=0) */
       <== error here: R6 invalid mem access 'inv'
    ...
  end:

In real test_verif_scale1 code, "w9 = 0" and "w2 = w9" are in
different basic blocks.

In the above, after "r6 += r2", r6 becomes a scalar, which eventually
caused the memory access error. The correct register state should be
a pkt pointer.

The inprecise register state starts at "w2 = w9".
The 32bit register w9 is 0, in __reg_assign_32_into_64(),
the 64bit reg->smax_value is assigned to be U32_MAX.
The 64bit reg->smin_value is 0 and the 64bit register
itself remains constant based on reg->var_off.

In adjust_ptr_min_max_vals(), the verifier checks for a known constant,
smin_val must be equal to smax_val. Since they are not equal,
the verifier decides r6 is a unknown scalar, which caused later failure.

The llvm10 does not have this issue as it generates different code:
    w9 = 0  /* R9_w=inv0 */
    r8 = *(u32 *)(r1 + 80)  /* __sk_buff->data_end */
    r7 = *(u32 *)(r1 + 76)  /* __sk_buff->data */
    ......
    r6 = r7 /* R6_w=pkt(id=0,off=0,r=0,imm=0) */
    r6 += r9 /* R6_w=pkt(id=0,off=0,r=0,imm=0) */
    r3 = r6 /* R3_w=pkt(id=0,off=0,r=0,imm=0) */
    r3 += 14 /* R3_w=pkt(id=0,off=14,r=0,imm=0) */
    if r3 > r8 goto end
    ...

To fix the above issue, we can include zero in the test condition for
assigning the s32_max_value and s32_min_value to their 64-bit equivalents
smax_value and smin_value.

Further, fix the condition to avoid doing zero extension bounds checks
when s32_min_value <= 0. This could allow for the case where bounds
32-bit bounds (-1,1) get incorrectly translated to (0,1) 64-bit bounds.
When in-fact the -1 min value needs to force U32_MAX bound.

Fixes: 3f50f132d840 ("bpf: Verifier, do explicit ALU32 bounds tracking")
Signed-off-by: John Fastabend <john.fastabend@gmail.com>
---
 kernel/bpf/verifier.c |   10 +++++-----
 1 file changed, 5 insertions(+), 5 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index d2e27db..d0bdd55 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -1217,14 +1217,14 @@ static void __reg_assign_32_into_64(struct bpf_reg_state *reg)
 	 * but must be positive otherwise set to worse case bounds
 	 * and refine later from tnum.
 	 */
-	if (reg->s32_min_value > 0)
-		reg->smin_value = reg->s32_min_value;
-	else
-		reg->smin_value = 0;
-	if (reg->s32_max_value > 0)
+	if (reg->s32_min_value >= 0 && reg->s32_max_value >= 0)
 		reg->smax_value = reg->s32_max_value;
 	else
 		reg->smax_value = U32_MAX;
+	if (reg->s32_min_value >= 0)
+		reg->smin_value = reg->s32_min_value;
+	else
+		reg->smin_value = 0;
 }
 
 static void __reg_combine_32_into_64(struct bpf_reg_state *reg)


^ permalink raw reply	[flat|nested] 7+ messages in thread

* [bpf PATCH 2/3] bpf, selftests: verifier bounds tests need to be updated
  2020-05-29 17:28 [bpf PATCH 0/3] verifier fix for assigning 32bit reg to 64bit reg John Fastabend
  2020-05-29 17:28 ` [bpf PATCH 1/3] bpf: fix a verifier issue when assigning 32bit reg states to 64bit ones John Fastabend
@ 2020-05-29 17:28 ` John Fastabend
  2020-05-29 18:41   ` Yonghong Song
  2020-05-29 17:29 ` [bpf PATCH 3/3] bpf, selftests: add a verifier test for assigning 32bit reg states to 64bit ones John Fastabend
  2020-05-29 20:53 ` [bpf PATCH 0/3] verifier fix for assigning 32bit reg to 64bit reg Alexei Starovoitov
  3 siblings, 1 reply; 7+ messages in thread
From: John Fastabend @ 2020-05-29 17:28 UTC (permalink / raw)
  To: yhs, alexei.starovoitov, daniel; +Cc: bpf, john.fastabend, kernel-team

After previous fix for zero extension test_verifier tests #65 and #66 now
fail. Before the fix we can see the alu32 mov op at insn 10

10: R0_w=map_value(id=0,off=0,ks=8,vs=8,imm=0)
    R1_w=invP(id=0,
              smin_value=4294967168,smax_value=4294967423,
              umin_value=4294967168,umax_value=4294967423,
              var_off=(0x0; 0x1ffffffff),
              s32_min_value=-2147483648,s32_max_value=2147483647,
              u32_min_value=0,u32_max_value=-1)
    R10=fp0 fp-8_w=mmmmmmmm
10: (bc) w1 = w1
11: R0_w=map_value(id=0,off=0,ks=8,vs=8,imm=0)
    R1_w=invP(id=0,
              smin_value=0,smax_value=2147483647,
              umin_value=0,umax_value=4294967295,
              var_off=(0x0; 0xffffffff),
              s32_min_value=-2147483648,s32_max_value=2147483647,
              u32_min_value=0,u32_max_value=-1)
    R10=fp0 fp-8_w=mmmmmmmm

After the fix at insn 10 because we have 's32_min_value < 0' the following
step 11 now has 'smax_value=U32_MAX' where before we pulled the s32_max_value
bound into the smax_value as seen above in 11 with smax_value=2147483647.

10: R0_w=map_value(id=0,off=0,ks=8,vs=8,imm=0)
    R1_w=inv(id=0,
             smin_value=4294967168,smax_value=4294967423,
             umin_value=4294967168,umax_value=4294967423,
             var_off=(0x0; 0x1ffffffff),
             s32_min_value=-2147483648, s32_max_value=2147483647,
             u32_min_value=0,u32_max_value=-1)
    R10=fp0 fp-8_w=mmmmmmmm
10: (bc) w1 = w1
11: R0_w=map_value(id=0,off=0,ks=8,vs=8,imm=0)
    R1_w=inv(id=0,
             smin_value=0,smax_value=4294967295,
             umin_value=0,umax_value=4294967295,
             var_off=(0x0; 0xffffffff),
             s32_min_value=-2147483648, s32_max_value=2147483647,
             u32_min_value=0, u32_max_value=-1)
    R10=fp0 fp-8_w=mmmmmmmm

The fall out of this is by the time we get to the failing instruction at
step 14 where previously we had the following:

14: R0_w=map_value(id=0,off=0,ks=8,vs=8,imm=0)
    R1_w=inv(id=0,
             smin_value=72057594021150720,smax_value=72057594029539328,
             umin_value=72057594021150720,umax_value=72057594029539328,
             var_off=(0xffffffff000000; 0xffffff),
             s32_min_value=-16777216,s32_max_value=-1,
             u32_min_value=-16777216,u32_max_value=-1)
    R10=fp0 fp-8_w=mmmmmmmm
14: (0f) r0 += r1

We now have,

14: R0_w=map_value(id=0,off=0,ks=8,vs=8,imm=0)
    R1_w=inv(id=0,
             smin_value=0,smax_value=72057594037927935,
             umin_value=0,umax_value=72057594037927935,
             var_off=(0x0; 0xffffffffffffff),
             s32_min_value=-2147483648,s32_max_value=2147483647,
             u32_min_value=0,u32_max_value=-1)
    R10=fp0 fp-8_w=mmmmmmmm
14: (0f) r0 += r1

In the original step 14 'smin_value=72057594021150720' this trips the logic
in the verifier function check_reg_sane_offset(),

 if (smin >= BPF_MAX_VAR_OFF || smin <= -BPF_MAX_VAR_OFF) {
	verbose(env, "value %lld makes %s pointer be out of bounds\n",
		smin, reg_type_str[type]);
	return false;
 }

Specifically, the 'smin <= -BPF_MAX_VAR_OFF' check. But with the fix
at step 14 we have bounds 'smin_value=0' so the above check is not tripped
because BPF_MAX_VAR_OFF=1<<29.

We have a smin_value=0 here because at step 10 the smaller smin_value=0 means
the subtractions at steps 11 and 12 bring the smin_value negative.

11: (17) r1 -= 2147483584
12: (17) r1 -= 2147483584
13: (77) r1 >>= 8

Then the shift clears the top bit and smin_value is set to 0. Note we still
have the smax_value in the fixed code so any reads will fail. An alternative
would be to have reg_sane_check() do both smin and smax value tests.

To fix the test we can omit the 'r1 >>=8' at line 13. This will change the
err string, but keeps the intention of the test as suggseted by the title,
"check after truncation of boundary-crossing range". If the verifier logic
changes a different value is likely to be thrown in the error or the error
will no longer be thrown forcing this test to be examined. With this change
we see the new state at step 13.

13: R0_w=map_value(id=0,off=0,ks=8,vs=8,imm=0)
    R1_w=invP(id=0,
              smin_value=-4294967168,smax_value=127,
              umin_value=0,umax_value=18446744073709551615,
              s32_min_value=-2147483648,s32_max_value=2147483647,
              u32_min_value=0,u32_max_value=-1)
    R10=fp0 fp-8_w=mmmmmmmm

Giving the expected out of bounds error, "value -4294967168 makes map_value
pointer be out of bounds" However, for unpriv case we see a different error
now because of the mixed signed bounds pointer arithmatic. This seems OK so
I've only added the unpriv_errstr for this. Another optino may have been to
do addition on r1 instead of subtraction but I favor the approach above
slightly.

Signed-off-by: John Fastabend <john.fastabend@gmail.com>
---
 tools/testing/selftests/bpf/verifier/bounds.c |   24 ++++++++++--------------
 1 file changed, 10 insertions(+), 14 deletions(-)

diff --git a/tools/testing/selftests/bpf/verifier/bounds.c b/tools/testing/selftests/bpf/verifier/bounds.c
index a253a06..fafa540 100644
--- a/tools/testing/selftests/bpf/verifier/bounds.c
+++ b/tools/testing/selftests/bpf/verifier/bounds.c
@@ -238,7 +238,7 @@
 	BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
 	BPF_LD_MAP_FD(BPF_REG_1, 0),
 	BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
-	BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 9),
+	BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 8),
 	/* r1 = [0x00, 0xff] */
 	BPF_LDX_MEM(BPF_B, BPF_REG_1, BPF_REG_0, 0),
 	BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, 0xffffff80 >> 1),
@@ -253,10 +253,6 @@
 	 *      [0xffff'ffff'0000'0080, 0xffff'ffff'ffff'ffff]
 	 */
 	BPF_ALU64_IMM(BPF_SUB, BPF_REG_1, 0xffffff80 >> 1),
-	/* r1 = 0 or
-	 *      [0x00ff'ffff'ff00'0000, 0x00ff'ffff'ffff'ffff]
-	 */
-	BPF_ALU64_IMM(BPF_RSH, BPF_REG_1, 8),
 	/* error on OOB pointer computation */
 	BPF_ALU64_REG(BPF_ADD, BPF_REG_0, BPF_REG_1),
 	/* exit */
@@ -265,8 +261,10 @@
 	},
 	.fixup_map_hash_8b = { 3 },
 	/* not actually fully unbounded, but the bound is very high */
-	.errstr = "value 72057594021150720 makes map_value pointer be out of bounds",
-	.result = REJECT
+	.errstr_unpriv = "R1 has unknown scalar with mixed signed bounds, pointer arithmetic with it prohibited for !root",
+	.result_unpriv = REJECT,
+	.errstr = "value -4294967168 makes map_value pointer be out of bounds",
+	.result = REJECT,
 },
 {
 	"bounds check after truncation of boundary-crossing range (2)",
@@ -276,7 +274,7 @@
 	BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
 	BPF_LD_MAP_FD(BPF_REG_1, 0),
 	BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
-	BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 9),
+	BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 8),
 	/* r1 = [0x00, 0xff] */
 	BPF_LDX_MEM(BPF_B, BPF_REG_1, BPF_REG_0, 0),
 	BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, 0xffffff80 >> 1),
@@ -293,10 +291,6 @@
 	 *      [0xffff'ffff'0000'0080, 0xffff'ffff'ffff'ffff]
 	 */
 	BPF_ALU64_IMM(BPF_SUB, BPF_REG_1, 0xffffff80 >> 1),
-	/* r1 = 0 or
-	 *      [0x00ff'ffff'ff00'0000, 0x00ff'ffff'ffff'ffff]
-	 */
-	BPF_ALU64_IMM(BPF_RSH, BPF_REG_1, 8),
 	/* error on OOB pointer computation */
 	BPF_ALU64_REG(BPF_ADD, BPF_REG_0, BPF_REG_1),
 	/* exit */
@@ -305,8 +299,10 @@
 	},
 	.fixup_map_hash_8b = { 3 },
 	/* not actually fully unbounded, but the bound is very high */
-	.errstr = "value 72057594021150720 makes map_value pointer be out of bounds",
-	.result = REJECT
+	.errstr_unpriv = "R1 has unknown scalar with mixed signed bounds, pointer arithmetic with it prohibited for !root",
+	.result_unpriv = REJECT,
+	.errstr = "value -4294967168 makes map_value pointer be out of bounds",
+	.result = REJECT,
 },
 {
 	"bounds check after wrapping 32-bit addition",


^ permalink raw reply	[flat|nested] 7+ messages in thread

* [bpf PATCH 3/3] bpf, selftests: add a verifier test for assigning 32bit reg states to 64bit ones
  2020-05-29 17:28 [bpf PATCH 0/3] verifier fix for assigning 32bit reg to 64bit reg John Fastabend
  2020-05-29 17:28 ` [bpf PATCH 1/3] bpf: fix a verifier issue when assigning 32bit reg states to 64bit ones John Fastabend
  2020-05-29 17:28 ` [bpf PATCH 2/3] bpf, selftests: verifier bounds tests need to be updated John Fastabend
@ 2020-05-29 17:29 ` John Fastabend
  2020-05-29 20:53 ` [bpf PATCH 0/3] verifier fix for assigning 32bit reg to 64bit reg Alexei Starovoitov
  3 siblings, 0 replies; 7+ messages in thread
From: John Fastabend @ 2020-05-29 17:29 UTC (permalink / raw)
  To: yhs, alexei.starovoitov, daniel; +Cc: bpf, john.fastabend, kernel-team

Added a verifier test for assigning 32bit reg states to
64bit where 32bit reg holds a constant value of 0.

Without previous kernel verifier.c fix, the test in
this patch will fail.

Signed-off-by: Yonghong Song <yhs@fb.com>
Signed-off-by: John Fastabend <john.fastabend@gmail.com>
---
 tools/testing/selftests/bpf/verifier/bounds.c |   22 ++++++++++++++++++++++
 1 file changed, 22 insertions(+)

diff --git a/tools/testing/selftests/bpf/verifier/bounds.c b/tools/testing/selftests/bpf/verifier/bounds.c
index fafa540..58f4aa59 100644
--- a/tools/testing/selftests/bpf/verifier/bounds.c
+++ b/tools/testing/selftests/bpf/verifier/bounds.c
@@ -535,3 +535,25 @@
 	},
 	.result = ACCEPT
 },
+{
+	"assigning 32bit bounds to 64bit for wA = 0, wB = wA",
+	.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_MOV32_IMM(BPF_REG_9, 0),
+	BPF_MOV32_REG(BPF_REG_2, BPF_REG_9),
+	BPF_MOV64_REG(BPF_REG_6, BPF_REG_7),
+	BPF_ALU64_REG(BPF_ADD, BPF_REG_6, BPF_REG_2),
+	BPF_MOV64_REG(BPF_REG_3, BPF_REG_6),
+	BPF_ALU64_IMM(BPF_ADD, BPF_REG_3, 8),
+	BPF_JMP_REG(BPF_JGT, BPF_REG_3, BPF_REG_8, 1),
+	BPF_LDX_MEM(BPF_W, BPF_REG_5, BPF_REG_6, 0),
+	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,
+},


^ permalink raw reply	[flat|nested] 7+ messages in thread

* Re: [bpf PATCH 1/3] bpf: fix a verifier issue when assigning 32bit reg states to 64bit ones
  2020-05-29 17:28 ` [bpf PATCH 1/3] bpf: fix a verifier issue when assigning 32bit reg states to 64bit ones John Fastabend
@ 2020-05-29 18:40   ` Yonghong Song
  0 siblings, 0 replies; 7+ messages in thread
From: Yonghong Song @ 2020-05-29 18:40 UTC (permalink / raw)
  To: John Fastabend, alexei.starovoitov, daniel; +Cc: bpf, kernel-team



On 5/29/20 10:28 AM, John Fastabend wrote:
> With the latest trunk llvm (llvm 11), I hit a verifier issue for
> test_prog subtest test_verif_scale1.
> 
> The following simplified example illustrate the issue:
>      w9 = 0  /* R9_w=inv0 */
>      r8 = *(u32 *)(r1 + 80)  /* __sk_buff->data_end */
>      r7 = *(u32 *)(r1 + 76)  /* __sk_buff->data */
>      ......
>      w2 = w9 /* R2_w=inv0 */
>      r6 = r7 /* R6_w=pkt(id=0,off=0,r=0,imm=0) */
>      r6 += r2 /* R6_w=inv(id=0) */
>      r3 = r6 /* R3_w=inv(id=0) */
>      r3 += 14 /* R3_w=inv(id=0) */
>      if r3 > r8 goto end
>      r5 = *(u32 *)(r6 + 0) /* R6_w=inv(id=0) */
>         <== error here: R6 invalid mem access 'inv'
>      ...
>    end:
> 
> In real test_verif_scale1 code, "w9 = 0" and "w2 = w9" are in
> different basic blocks.
> 
> In the above, after "r6 += r2", r6 becomes a scalar, which eventually
> caused the memory access error. The correct register state should be
> a pkt pointer.
> 
> The inprecise register state starts at "w2 = w9".
> The 32bit register w9 is 0, in __reg_assign_32_into_64(),
> the 64bit reg->smax_value is assigned to be U32_MAX.
> The 64bit reg->smin_value is 0 and the 64bit register
> itself remains constant based on reg->var_off.
> 
> In adjust_ptr_min_max_vals(), the verifier checks for a known constant,
> smin_val must be equal to smax_val. Since they are not equal,
> the verifier decides r6 is a unknown scalar, which caused later failure.
> 
> The llvm10 does not have this issue as it generates different code:
>      w9 = 0  /* R9_w=inv0 */
>      r8 = *(u32 *)(r1 + 80)  /* __sk_buff->data_end */
>      r7 = *(u32 *)(r1 + 76)  /* __sk_buff->data */
>      ......
>      r6 = r7 /* R6_w=pkt(id=0,off=0,r=0,imm=0) */
>      r6 += r9 /* R6_w=pkt(id=0,off=0,r=0,imm=0) */
>      r3 = r6 /* R3_w=pkt(id=0,off=0,r=0,imm=0) */
>      r3 += 14 /* R3_w=pkt(id=0,off=14,r=0,imm=0) */
>      if r3 > r8 goto end
>      ...
> 
> To fix the above issue, we can include zero in the test condition for
> assigning the s32_max_value and s32_min_value to their 64-bit equivalents
> smax_value and smin_value.
> 
> Further, fix the condition to avoid doing zero extension bounds checks
> when s32_min_value <= 0. This could allow for the case where bounds
> 32-bit bounds (-1,1) get incorrectly translated to (0,1) 64-bit bounds.
> When in-fact the -1 min value needs to force U32_MAX bound.
> 
> Fixes: 3f50f132d840 ("bpf: Verifier, do explicit ALU32 bounds tracking")
> Signed-off-by: John Fastabend <john.fastabend@gmail.com>
> ---
>   kernel/bpf/verifier.c |   10 +++++-----
>   1 file changed, 5 insertions(+), 5 deletions(-)

Thanks for the fix. LGTM.
Acked-by: Yonghong Song <yhs@fb.com>

^ permalink raw reply	[flat|nested] 7+ messages in thread

* Re: [bpf PATCH 2/3] bpf, selftests: verifier bounds tests need to be updated
  2020-05-29 17:28 ` [bpf PATCH 2/3] bpf, selftests: verifier bounds tests need to be updated John Fastabend
@ 2020-05-29 18:41   ` Yonghong Song
  0 siblings, 0 replies; 7+ messages in thread
From: Yonghong Song @ 2020-05-29 18:41 UTC (permalink / raw)
  To: John Fastabend, alexei.starovoitov, daniel; +Cc: bpf, kernel-team



On 5/29/20 10:28 AM, John Fastabend wrote:
> After previous fix for zero extension test_verifier tests #65 and #66 now
> fail. Before the fix we can see the alu32 mov op at insn 10
> 
> 10: R0_w=map_value(id=0,off=0,ks=8,vs=8,imm=0)
>      R1_w=invP(id=0,
>                smin_value=4294967168,smax_value=4294967423,
>                umin_value=4294967168,umax_value=4294967423,
>                var_off=(0x0; 0x1ffffffff),
>                s32_min_value=-2147483648,s32_max_value=2147483647,
>                u32_min_value=0,u32_max_value=-1)
>      R10=fp0 fp-8_w=mmmmmmmm
> 10: (bc) w1 = w1
> 11: R0_w=map_value(id=0,off=0,ks=8,vs=8,imm=0)
>      R1_w=invP(id=0,
>                smin_value=0,smax_value=2147483647,
>                umin_value=0,umax_value=4294967295,
>                var_off=(0x0; 0xffffffff),
>                s32_min_value=-2147483648,s32_max_value=2147483647,
>                u32_min_value=0,u32_max_value=-1)
>      R10=fp0 fp-8_w=mmmmmmmm
> 
> After the fix at insn 10 because we have 's32_min_value < 0' the following
> step 11 now has 'smax_value=U32_MAX' where before we pulled the s32_max_value
> bound into the smax_value as seen above in 11 with smax_value=2147483647.
> 
> 10: R0_w=map_value(id=0,off=0,ks=8,vs=8,imm=0)
>      R1_w=inv(id=0,
>               smin_value=4294967168,smax_value=4294967423,
>               umin_value=4294967168,umax_value=4294967423,
>               var_off=(0x0; 0x1ffffffff),
>               s32_min_value=-2147483648, s32_max_value=2147483647,
>               u32_min_value=0,u32_max_value=-1)
>      R10=fp0 fp-8_w=mmmmmmmm
> 10: (bc) w1 = w1
> 11: R0_w=map_value(id=0,off=0,ks=8,vs=8,imm=0)
>      R1_w=inv(id=0,
>               smin_value=0,smax_value=4294967295,
>               umin_value=0,umax_value=4294967295,
>               var_off=(0x0; 0xffffffff),
>               s32_min_value=-2147483648, s32_max_value=2147483647,
>               u32_min_value=0, u32_max_value=-1)
>      R10=fp0 fp-8_w=mmmmmmmm
> 
> The fall out of this is by the time we get to the failing instruction at
> step 14 where previously we had the following:
> 
> 14: R0_w=map_value(id=0,off=0,ks=8,vs=8,imm=0)
>      R1_w=inv(id=0,
>               smin_value=72057594021150720,smax_value=72057594029539328,
>               umin_value=72057594021150720,umax_value=72057594029539328,
>               var_off=(0xffffffff000000; 0xffffff),
>               s32_min_value=-16777216,s32_max_value=-1,
>               u32_min_value=-16777216,u32_max_value=-1)
>      R10=fp0 fp-8_w=mmmmmmmm
> 14: (0f) r0 += r1
> 
> We now have,
> 
> 14: R0_w=map_value(id=0,off=0,ks=8,vs=8,imm=0)
>      R1_w=inv(id=0,
>               smin_value=0,smax_value=72057594037927935,
>               umin_value=0,umax_value=72057594037927935,
>               var_off=(0x0; 0xffffffffffffff),
>               s32_min_value=-2147483648,s32_max_value=2147483647,
>               u32_min_value=0,u32_max_value=-1)
>      R10=fp0 fp-8_w=mmmmmmmm
> 14: (0f) r0 += r1
> 
> In the original step 14 'smin_value=72057594021150720' this trips the logic
> in the verifier function check_reg_sane_offset(),
> 
>   if (smin >= BPF_MAX_VAR_OFF || smin <= -BPF_MAX_VAR_OFF) {
> 	verbose(env, "value %lld makes %s pointer be out of bounds\n",
> 		smin, reg_type_str[type]);
> 	return false;
>   }
> 
> Specifically, the 'smin <= -BPF_MAX_VAR_OFF' check. But with the fix
> at step 14 we have bounds 'smin_value=0' so the above check is not tripped
> because BPF_MAX_VAR_OFF=1<<29.
> 
> We have a smin_value=0 here because at step 10 the smaller smin_value=0 means
> the subtractions at steps 11 and 12 bring the smin_value negative.
> 
> 11: (17) r1 -= 2147483584
> 12: (17) r1 -= 2147483584
> 13: (77) r1 >>= 8
> 
> Then the shift clears the top bit and smin_value is set to 0. Note we still
> have the smax_value in the fixed code so any reads will fail. An alternative
> would be to have reg_sane_check() do both smin and smax value tests.
> 
> To fix the test we can omit the 'r1 >>=8' at line 13. This will change the
> err string, but keeps the intention of the test as suggseted by the title,
> "check after truncation of boundary-crossing range". If the verifier logic
> changes a different value is likely to be thrown in the error or the error
> will no longer be thrown forcing this test to be examined. With this change
> we see the new state at step 13.
> 
> 13: R0_w=map_value(id=0,off=0,ks=8,vs=8,imm=0)
>      R1_w=invP(id=0,
>                smin_value=-4294967168,smax_value=127,
>                umin_value=0,umax_value=18446744073709551615,
>                s32_min_value=-2147483648,s32_max_value=2147483647,
>                u32_min_value=0,u32_max_value=-1)
>      R10=fp0 fp-8_w=mmmmmmmm
> 
> Giving the expected out of bounds error, "value -4294967168 makes map_value
> pointer be out of bounds" However, for unpriv case we see a different error
> now because of the mixed signed bounds pointer arithmatic. This seems OK so
> I've only added the unpriv_errstr for this. Another optino may have been to
> do addition on r1 instead of subtraction but I favor the approach above
> slightly.
> 
> Signed-off-by: John Fastabend <john.fastabend@gmail.com>
> ---
>   tools/testing/selftests/bpf/verifier/bounds.c |   24 ++++++++++--------------
>   1 file changed, 10 insertions(+), 14 deletions(-)

Acked-by: Yonghong Song <yhs@fb.com>

^ permalink raw reply	[flat|nested] 7+ messages in thread

* Re: [bpf PATCH 0/3] verifier fix for assigning 32bit reg to 64bit reg
  2020-05-29 17:28 [bpf PATCH 0/3] verifier fix for assigning 32bit reg to 64bit reg John Fastabend
                   ` (2 preceding siblings ...)
  2020-05-29 17:29 ` [bpf PATCH 3/3] bpf, selftests: add a verifier test for assigning 32bit reg states to 64bit ones John Fastabend
@ 2020-05-29 20:53 ` Alexei Starovoitov
  3 siblings, 0 replies; 7+ messages in thread
From: Alexei Starovoitov @ 2020-05-29 20:53 UTC (permalink / raw)
  To: John Fastabend; +Cc: Yonghong Song, Daniel Borkmann, bpf, Kernel Team

On Fri, May 29, 2020 at 10:28 AM John Fastabend
<john.fastabend@gmail.com> wrote:
>
> These add a fix for 32 bit to 64 bit assignment introduced with
> latest alu32 bounds tracking. The initial fix was proposed by
> Yonghong and then I updated it slightly and added a test fix.

Applied. Thanks

^ permalink raw reply	[flat|nested] 7+ messages in thread

end of thread, back to index

Thread overview: 7+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2020-05-29 17:28 [bpf PATCH 0/3] verifier fix for assigning 32bit reg to 64bit reg John Fastabend
2020-05-29 17:28 ` [bpf PATCH 1/3] bpf: fix a verifier issue when assigning 32bit reg states to 64bit ones John Fastabend
2020-05-29 18:40   ` Yonghong Song
2020-05-29 17:28 ` [bpf PATCH 2/3] bpf, selftests: verifier bounds tests need to be updated John Fastabend
2020-05-29 18:41   ` Yonghong Song
2020-05-29 17:29 ` [bpf PATCH 3/3] bpf, selftests: add a verifier test for assigning 32bit reg states to 64bit ones John Fastabend
2020-05-29 20:53 ` [bpf PATCH 0/3] verifier fix for assigning 32bit reg to 64bit reg Alexei Starovoitov

BPF Archive on lore.kernel.org

Archives are clonable:
	git clone --mirror https://lore.kernel.org/bpf/0 bpf/git/0.git

	# If you have public-inbox 1.1+ installed, you may
	# initialize and index your mirror using the following commands:
	public-inbox-init -V2 bpf bpf/ https://lore.kernel.org/bpf \
		bpf@vger.kernel.org
	public-inbox-index bpf

Example config snippet for mirrors

Newsgroup available over NNTP:
	nntp://nntp.lore.kernel.org/org.kernel.vger.bpf


AGPL code for this site: git clone https://public-inbox.org/public-inbox.git