* [PATCH bpf 0/2] bpf: fix a verifier issue when assigning 32bit reg states to 64bit ones
@ 2020-05-28 16:50 Yonghong Song
2020-05-28 16:50 ` [PATCH bpf 1/2] " Yonghong Song
2020-05-28 16:50 ` [PATCH bpf 2/2] tools/bpf: add a verifier test for " Yonghong Song
0 siblings, 2 replies; 7+ messages in thread
From: Yonghong Song @ 2020-05-28 16:50 UTC (permalink / raw)
To: bpf; +Cc: Alexei Starovoitov, Daniel Borkmann, kernel-team
Commit 3f50f132d840 ("bpf: Verifier, do explicit ALU32 bounds tracking")
added 32bit register states to verifier for explicit ALU32 bounds
tracking. When assigning 32bit register states to 64bit register states,
if 32bit register is a constant value of 0, the 64bit register smax_val
will get U32_MAX(0xffffFFFF). Such an inprecise information may impact
downward verification. Patch #1 has detailed explanation of the program
and how to fix it. Patch #2 provides a verifier test to cover the change.
Yonghong Song (2):
bpf: fix a verifier issue when assigning 32bit reg states to 64bit
tools/bpf: add a verifier test for assigning 32bit reg states to 64bit
kernel/bpf/verifier.c | 3 +++
tools/testing/selftests/bpf/verifier/bounds.c | 22 +++++++++++++++++++
2 files changed, 25 insertions(+)
--
2.24.1
^ permalink raw reply [flat|nested] 7+ messages in thread* [PATCH bpf 1/2] bpf: fix a verifier issue when assigning 32bit reg states to 64bit ones 2020-05-28 16:50 [PATCH bpf 0/2] bpf: fix a verifier issue when assigning 32bit reg states to 64bit ones Yonghong Song @ 2020-05-28 16:50 ` Yonghong Song 2020-05-28 20:36 ` Alexei Starovoitov 2020-05-28 21:30 ` John Fastabend 2020-05-28 16:50 ` [PATCH bpf 2/2] tools/bpf: add a verifier test for " Yonghong Song 1 sibling, 2 replies; 7+ messages in thread From: Yonghong Song @ 2020-05-28 16:50 UTC (permalink / raw) To: bpf; +Cc: Alexei Starovoitov, Daniel Borkmann, kernel-team, John Fastabend 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 issue, if 32bit register is a const 0, then just assign max vaue 0 to 64bit register smax_value as well. Fixes: 3f50f132d840 ("bpf: Verifier, do explicit ALU32 bounds tracking") Cc: John Fastabend <john.fastabend@gmail.com> Signed-off-by: Yonghong Song <yhs@fb.com> --- kernel/bpf/verifier.c | 3 +++ 1 file changed, 3 insertions(+) diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 8d7ee40e2748..5123ce54695f 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -1174,6 +1174,9 @@ static void __reg_assign_32_into_64(struct bpf_reg_state *reg) reg->smin_value = 0; if (reg->s32_max_value > 0) reg->smax_value = reg->s32_max_value; + else if (reg->s32_max_value == 0 && reg->s32_min_value == 0 && + tnum_is_const(reg->var_off)) + reg->smax_value = 0; /* const 0 */ else reg->smax_value = U32_MAX; } -- 2.24.1 ^ permalink raw reply related [flat|nested] 7+ messages in thread
* Re: [PATCH bpf 1/2] bpf: fix a verifier issue when assigning 32bit reg states to 64bit ones 2020-05-28 16:50 ` [PATCH bpf 1/2] " Yonghong Song @ 2020-05-28 20:36 ` Alexei Starovoitov 2020-05-28 21:22 ` Yonghong Song 2020-05-28 21:30 ` John Fastabend 1 sibling, 1 reply; 7+ messages in thread From: Alexei Starovoitov @ 2020-05-28 20:36 UTC (permalink / raw) To: Yonghong Song Cc: bpf, Alexei Starovoitov, Daniel Borkmann, kernel-team, John Fastabend On Thu, May 28, 2020 at 09:50:43AM -0700, Yonghong Song 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 issue, if 32bit register is a const 0, > then just assign max vaue 0 to 64bit register smax_value as well. > > Fixes: 3f50f132d840 ("bpf: Verifier, do explicit ALU32 bounds tracking") > Cc: John Fastabend <john.fastabend@gmail.com> > Signed-off-by: Yonghong Song <yhs@fb.com> > --- > kernel/bpf/verifier.c | 3 +++ > 1 file changed, 3 insertions(+) > > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c > index 8d7ee40e2748..5123ce54695f 100644 > --- a/kernel/bpf/verifier.c > +++ b/kernel/bpf/verifier.c > @@ -1174,6 +1174,9 @@ static void __reg_assign_32_into_64(struct bpf_reg_state *reg) > reg->smin_value = 0; > if (reg->s32_max_value > 0) > reg->smax_value = reg->s32_max_value; > + else if (reg->s32_max_value == 0 && reg->s32_min_value == 0 && > + tnum_is_const(reg->var_off)) > + reg->smax_value = 0; /* const 0 */ > else > reg->smax_value = U32_MAX; wouldn't this be a more general fix ? diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 01c7d3634151..83450d5d24ab 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -1217,11 +1217,11 @@ 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) + 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_max_value >= 0) reg->smax_value = reg->s32_max_value; else reg->smax_value = U32_MAX; ^ permalink raw reply related [flat|nested] 7+ messages in thread
* Re: [PATCH bpf 1/2] bpf: fix a verifier issue when assigning 32bit reg states to 64bit ones 2020-05-28 20:36 ` Alexei Starovoitov @ 2020-05-28 21:22 ` Yonghong Song 0 siblings, 0 replies; 7+ messages in thread From: Yonghong Song @ 2020-05-28 21:22 UTC (permalink / raw) To: Alexei Starovoitov Cc: bpf, Alexei Starovoitov, Daniel Borkmann, kernel-team, John Fastabend On 5/28/20 1:36 PM, Alexei Starovoitov wrote: > On Thu, May 28, 2020 at 09:50:43AM -0700, Yonghong Song 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 issue, if 32bit register is a const 0, >> then just assign max vaue 0 to 64bit register smax_value as well. >> >> Fixes: 3f50f132d840 ("bpf: Verifier, do explicit ALU32 bounds tracking") >> Cc: John Fastabend <john.fastabend@gmail.com> >> Signed-off-by: Yonghong Song <yhs@fb.com> >> --- >> kernel/bpf/verifier.c | 3 +++ >> 1 file changed, 3 insertions(+) >> >> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c >> index 8d7ee40e2748..5123ce54695f 100644 >> --- a/kernel/bpf/verifier.c >> +++ b/kernel/bpf/verifier.c >> @@ -1174,6 +1174,9 @@ static void __reg_assign_32_into_64(struct bpf_reg_state *reg) >> reg->smin_value = 0; >> if (reg->s32_max_value > 0) >> reg->smax_value = reg->s32_max_value; >> + else if (reg->s32_max_value == 0 && reg->s32_min_value == 0 && >> + tnum_is_const(reg->var_off)) >> + reg->smax_value = 0; /* const 0 */ >> else >> reg->smax_value = U32_MAX; > > wouldn't this be a more general fix ? > > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c > index 01c7d3634151..83450d5d24ab 100644 > --- a/kernel/bpf/verifier.c > +++ b/kernel/bpf/verifier.c > @@ -1217,11 +1217,11 @@ 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) > + 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_max_value >= 0) > reg->smax_value = reg->s32_max_value; I thought this way, but not 100% sure about s32_max_value == 0 means actually the max_value of 0 or some kind of default value (e.g. from kzalloc). Hence my conservative approach. I guess you probably right. Let me double check the code. > else > reg->smax_value = U32_MAX; > ^ permalink raw reply [flat|nested] 7+ messages in thread
* RE: [PATCH bpf 1/2] bpf: fix a verifier issue when assigning 32bit reg states to 64bit ones 2020-05-28 16:50 ` [PATCH bpf 1/2] " Yonghong Song 2020-05-28 20:36 ` Alexei Starovoitov @ 2020-05-28 21:30 ` John Fastabend 2020-05-28 21:58 ` Yonghong Song 1 sibling, 1 reply; 7+ messages in thread From: John Fastabend @ 2020-05-28 21:30 UTC (permalink / raw) To: Yonghong Song, bpf Cc: Alexei Starovoitov, Daniel Borkmann, kernel-team, John Fastabend Yonghong Song 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 issue, if 32bit register is a const 0, > then just assign max vaue 0 to 64bit register smax_value as well. > > Fixes: 3f50f132d840 ("bpf: Verifier, do explicit ALU32 bounds tracking") > Cc: John Fastabend <john.fastabend@gmail.com> > Signed-off-by: Yonghong Song <yhs@fb.com> Thanks! > --- > kernel/bpf/verifier.c | 3 +++ > 1 file changed, 3 insertions(+) > > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c > index 8d7ee40e2748..5123ce54695f 100644 > --- a/kernel/bpf/verifier.c > +++ b/kernel/bpf/verifier.c > @@ -1174,6 +1174,9 @@ static void __reg_assign_32_into_64(struct bpf_reg_state *reg) > reg->smin_value = 0; > if (reg->s32_max_value > 0) > reg->smax_value = reg->s32_max_value; > + else if (reg->s32_max_value == 0 && reg->s32_min_value == 0 && > + tnum_is_const(reg->var_off)) > + reg->smax_value = 0; /* const 0 */ > else > reg->smax_value = U32_MAX; > } > -- > 2.24.1 > How about the following, I think it will also cover the case above. We should be checking 'smin_value > 0' as well I believe. diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index b3d2590..80d22de 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->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; - if (reg->s32_min_value >= 0 && reg->s32_max_value > 0) - reg->smax_value = reg->s32_max_value; - else - reg->smax_value = U32_MAX; } This causes selftests failure I pasted it at the end of the email. By my analysis what happens here is after line 10 we get different bounds and this falls out so that we just miss triggering the failure case in 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; } However (would need to check, improve verifier test) that should still fail as soon as its read. WDYT? I can try to roll it into your test if you want or if you have time go for it. Let me know. # ./test_verifier -v 66 #66/p bounds check after truncation of boundary-crossing range (2) FAIL Unexpected success to load! func#0 @0 0: R1=ctx(id=0,off=0,imm=0) R10=fp0 0: (7a) *(u64 *)(r10 -8) = 0 1: R1=ctx(id=0,off=0,imm=0) R10=fp0 fp-8_w=mmmmmmmm 1: (bf) r2 = r10 2: R1=ctx(id=0,off=0,imm=0) R2_w=fp0 R10=fp0 fp-8_w=mmmmmmmm 2: (07) r2 += -8 3: R1=ctx(id=0,off=0,imm=0) R2_w=fp-8 R10=fp0 fp-8_w=mmmmmmmm 3: (18) r1 = 0xffff8883dba1e800 5: R1_w=map_ptr(id=0,off=0,ks=8,vs=8,imm=0) R2_w=fp-8 R10=fp0 fp-8_w=mmmmmmmm 5: (85) call bpf_map_lookup_elem#1 6: R0_w=map_value_or_null(id=1,off=0,ks=8,vs=8,imm=0) R10=fp0 fp-8_w=mmmmmmmm 6: (15) if r0 == 0x0 goto pc+9 R0_w=map_value(id=0,off=0,ks=8,vs=8,imm=0) R10=fp0 fp-8_w=mmmmmmmm 7: R0_w=map_value(id=0,off=0,ks=8,vs=8,imm=0) R10=fp0 fp-8_w=mmmmmmmm 7: (71) r1 = *(u8 *)(r0 +0) R0_w=map_value(id=0,off=0,ks=8,vs=8,imm=0) R10=fp0 fp-8_w=mmmmmmmm 8: R0_w=map_value(id=0,off=0,ks=8,vs=8,imm=0) R1_w=inv(id=0,umax_value=255,var_off=(0x0; 0xff)) R10=fp0 fp-8_w=mmmmmmmm 8: (07) r1 += 2147483584 9: R0_w=map_value(id=0,off=0,ks=8,vs=8,imm=0) R1_w=inv(id=0,umin_value=2147483584,umax_value=2147483839,var_off=(0x0; 0xffffffff)) R10=fp0 fp-8_w=mmmmmmmm 9: (07) r1 += 2147483584 10: R0_w=map_value(id=0,off=0,ks=8,vs=8,imm=0) R1_w=inv(id=0,umin_value=4294967168,umax_value=4294967423,var_off=(0x0; 0x1ffffffff)) 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,umax_value=4294967295,var_off=(0x0; 0xffffffff)) R10=fp0 fp-8_w=mmmmmmmm 11: (17) r1 -= 2147483584 12: R0_w=map_value(id=0,off=0,ks=8,vs=8,imm=0) R1_w=inv(id=0,smin_value=-2147483584,smax_value=2147483711) R10=fp0 fp-8_w=mmmmmmmm 12: (17) r1 -= 2147483584 13: R0_w=map_value(id=0,off=0,ks=8,vs=8,imm=0) R1_w=inv(id=0,smin_value=-4294967168,smax_value=127) R10=fp0 fp-8_w=mmmmmmmm 13: (77) r1 >>= 8 14: R0_w=map_value(id=0,off=0,ks=8,vs=8,imm=0) R1_w=inv(id=0,umax_value=72057594037927935,var_off=(0x0; 0xffffffffffffff)) R10=fp0 fp-8_w=mmmmmmmm 14: (0f) r0 += r1 last_idx 14 first_idx 0 regs=2 stack=0 before 13: (77) r1 >>= 8 regs=2 stack=0 before 12: (17) r1 -= 2147483584 regs=2 stack=0 before 11: (17) r1 -= 2147483584 regs=2 stack=0 before 10: (bc) w1 = w1 regs=2 stack=0 before 9: (07) r1 += 2147483584 regs=2 stack=0 before 8: (07) r1 += 2147483584 regs=2 stack=0 before 7: (71) r1 = *(u8 *)(r0 +0) 15: R0_w=map_value(id=0,off=0,ks=8,vs=8,umax_value=72057594037927935,var_off=(0x0; 0xffffffffffffff)) R1_w=invP(id=0,umax_value=72057594037927935,var_off=(0x0; 0xffffffffffffff)) R10=fp0 fp-8_w=mmmmmmmm 15: (b7) r0 = 0 16: R0=inv0 R1=invP(id=0,umax_value=72057594037927935,var_off=(0x0; 0xffffffffffffff)) R10=fp0 fp-8=mmmmmmmm 16: (95) exit from 6 to 16: safe processed 17 insns (limit 1000000) max_states_per_insn 0 total_states 1 peak_states 1 mark_read 1 ^ permalink raw reply related [flat|nested] 7+ messages in thread
* Re: [PATCH bpf 1/2] bpf: fix a verifier issue when assigning 32bit reg states to 64bit ones 2020-05-28 21:30 ` John Fastabend @ 2020-05-28 21:58 ` Yonghong Song 0 siblings, 0 replies; 7+ messages in thread From: Yonghong Song @ 2020-05-28 21:58 UTC (permalink / raw) To: John Fastabend, bpf; +Cc: Alexei Starovoitov, Daniel Borkmann, kernel-team On 5/28/20 2:30 PM, John Fastabend wrote: > Yonghong Song 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 issue, if 32bit register is a const 0, >> then just assign max vaue 0 to 64bit register smax_value as well. >> >> Fixes: 3f50f132d840 ("bpf: Verifier, do explicit ALU32 bounds tracking") >> Cc: John Fastabend <john.fastabend@gmail.com> >> Signed-off-by: Yonghong Song <yhs@fb.com> > > > Thanks! > >> --- >> kernel/bpf/verifier.c | 3 +++ >> 1 file changed, 3 insertions(+) >> >> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c >> index 8d7ee40e2748..5123ce54695f 100644 >> --- a/kernel/bpf/verifier.c >> +++ b/kernel/bpf/verifier.c >> @@ -1174,6 +1174,9 @@ static void __reg_assign_32_into_64(struct bpf_reg_state *reg) >> reg->smin_value = 0; >> if (reg->s32_max_value > 0) >> reg->smax_value = reg->s32_max_value; >> + else if (reg->s32_max_value == 0 && reg->s32_min_value == 0 && >> + tnum_is_const(reg->var_off)) >> + reg->smax_value = 0; /* const 0 */ >> else >> reg->smax_value = U32_MAX; >> } >> -- >> 2.24.1 >> > > How about the following, I think it will also cover the case above. We should be > checking 'smin_value > 0' as well I believe. > > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c > index b3d2590..80d22de 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->s32_max_value >= 0) I agree that s32_min_value needs to be checked. Otherwise, a negative s32_min_value, not sure how to derive reg->smax_value.... > + 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; > - if (reg->s32_min_value >= 0 && reg->s32_max_value > 0) > - reg->smax_value = reg->s32_max_value; > - else > - reg->smax_value = U32_MAX; > } > > This causes selftests failure I pasted it at the end of the email. By my > analysis what happens here is after line 10 we get different bounds > and this falls out so that we just miss triggering the failure case in > 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; > } > > > However (would need to check, improve verifier test) that should still > fail as soon as its read. WDYT? I can try to roll it into your test if Which read, you mean r0 += r1? Yes, r1 range seems pretty big, R1_w=inv(id=0,umax_value=72057594037927935,var_off=(0x0; 0xffffffffffffff)) so a failure should be right, I guess. > you want or if you have time go for it. Let me know. Since this is a little more involved and you are more familiar with the code, please go ahead to make the change. Thanks! > > # ./test_verifier -v 66 > #66/p bounds check after truncation of boundary-crossing range (2) FAIL > Unexpected success to load! > func#0 @0 > 0: R1=ctx(id=0,off=0,imm=0) R10=fp0 > 0: (7a) *(u64 *)(r10 -8) = 0 > 1: R1=ctx(id=0,off=0,imm=0) R10=fp0 fp-8_w=mmmmmmmm > 1: (bf) r2 = r10 > 2: R1=ctx(id=0,off=0,imm=0) R2_w=fp0 R10=fp0 fp-8_w=mmmmmmmm > 2: (07) r2 += -8 > 3: R1=ctx(id=0,off=0,imm=0) R2_w=fp-8 R10=fp0 fp-8_w=mmmmmmmm > 3: (18) r1 = 0xffff8883dba1e800 > 5: R1_w=map_ptr(id=0,off=0,ks=8,vs=8,imm=0) R2_w=fp-8 R10=fp0 fp-8_w=mmmmmmmm > 5: (85) call bpf_map_lookup_elem#1 > 6: R0_w=map_value_or_null(id=1,off=0,ks=8,vs=8,imm=0) R10=fp0 fp-8_w=mmmmmmmm > 6: (15) if r0 == 0x0 goto pc+9 > R0_w=map_value(id=0,off=0,ks=8,vs=8,imm=0) R10=fp0 fp-8_w=mmmmmmmm > 7: R0_w=map_value(id=0,off=0,ks=8,vs=8,imm=0) R10=fp0 fp-8_w=mmmmmmmm > 7: (71) r1 = *(u8 *)(r0 +0) > R0_w=map_value(id=0,off=0,ks=8,vs=8,imm=0) R10=fp0 fp-8_w=mmmmmmmm > 8: R0_w=map_value(id=0,off=0,ks=8,vs=8,imm=0) R1_w=inv(id=0,umax_value=255,var_off=(0x0; 0xff)) R10=fp0 fp-8_w=mmmmmmmm > 8: (07) r1 += 2147483584 > 9: R0_w=map_value(id=0,off=0,ks=8,vs=8,imm=0) R1_w=inv(id=0,umin_value=2147483584,umax_value=2147483839,var_off=(0x0; 0xffffffff)) R10=fp0 fp-8_w=mmmmmmmm > 9: (07) r1 += 2147483584 > 10: R0_w=map_value(id=0,off=0,ks=8,vs=8,imm=0) R1_w=inv(id=0,umin_value=4294967168,umax_value=4294967423,var_off=(0x0; 0x1ffffffff)) 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,umax_value=4294967295,var_off=(0x0; 0xffffffff)) R10=fp0 fp-8_w=mmmmmmmm > 11: (17) r1 -= 2147483584 > 12: R0_w=map_value(id=0,off=0,ks=8,vs=8,imm=0) R1_w=inv(id=0,smin_value=-2147483584,smax_value=2147483711) R10=fp0 fp-8_w=mmmmmmmm > 12: (17) r1 -= 2147483584 > 13: R0_w=map_value(id=0,off=0,ks=8,vs=8,imm=0) R1_w=inv(id=0,smin_value=-4294967168,smax_value=127) R10=fp0 fp-8_w=mmmmmmmm > 13: (77) r1 >>= 8 > 14: R0_w=map_value(id=0,off=0,ks=8,vs=8,imm=0) R1_w=inv(id=0,umax_value=72057594037927935,var_off=(0x0; 0xffffffffffffff)) R10=fp0 fp-8_w=mmmmmmmm > 14: (0f) r0 += r1 > last_idx 14 first_idx 0 > regs=2 stack=0 before 13: (77) r1 >>= 8 > regs=2 stack=0 before 12: (17) r1 -= 2147483584 > regs=2 stack=0 before 11: (17) r1 -= 2147483584 > regs=2 stack=0 before 10: (bc) w1 = w1 > regs=2 stack=0 before 9: (07) r1 += 2147483584 > regs=2 stack=0 before 8: (07) r1 += 2147483584 > regs=2 stack=0 before 7: (71) r1 = *(u8 *)(r0 +0) > 15: R0_w=map_value(id=0,off=0,ks=8,vs=8,umax_value=72057594037927935,var_off=(0x0; 0xffffffffffffff)) R1_w=invP(id=0,umax_value=72057594037927935,var_off=(0x0; 0xffffffffffffff)) R10=fp0 fp-8_w=mmmmmmmm > 15: (b7) r0 = 0 > 16: R0=inv0 R1=invP(id=0,umax_value=72057594037927935,var_off=(0x0; 0xffffffffffffff)) R10=fp0 fp-8=mmmmmmmm > 16: (95) exit > > from 6 to 16: safe > processed 17 insns (limit 1000000) max_states_per_insn 0 total_states 1 peak_states 1 mark_read 1 > ^ permalink raw reply [flat|nested] 7+ messages in thread
* [PATCH bpf 2/2] tools/bpf: add a verifier test for assigning 32bit reg states to 64bit ones 2020-05-28 16:50 [PATCH bpf 0/2] bpf: fix a verifier issue when assigning 32bit reg states to 64bit ones Yonghong Song 2020-05-28 16:50 ` [PATCH bpf 1/2] " Yonghong Song @ 2020-05-28 16:50 ` Yonghong Song 1 sibling, 0 replies; 7+ messages in thread From: Yonghong Song @ 2020-05-28 16:50 UTC (permalink / raw) To: bpf; +Cc: Alexei Starovoitov, Daniel Borkmann, kernel-team, John Fastabend 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. Cc: John Fastabend <john.fastabend@gmail.com> Signed-off-by: Yonghong Song <yhs@fb.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 a253a064e6e0..e2739ca2abec 100644 --- a/tools/testing/selftests/bpf/verifier/bounds.c +++ b/tools/testing/selftests/bpf/verifier/bounds.c @@ -539,3 +539,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, +}, -- 2.24.1 ^ permalink raw reply related [flat|nested] 7+ messages in thread
end of thread, other threads:[~2020-05-28 22:00 UTC | newest] Thread overview: 7+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2020-05-28 16:50 [PATCH bpf 0/2] bpf: fix a verifier issue when assigning 32bit reg states to 64bit ones Yonghong Song 2020-05-28 16:50 ` [PATCH bpf 1/2] " Yonghong Song 2020-05-28 20:36 ` Alexei Starovoitov 2020-05-28 21:22 ` Yonghong Song 2020-05-28 21:30 ` John Fastabend 2020-05-28 21:58 ` Yonghong Song 2020-05-28 16:50 ` [PATCH bpf 2/2] tools/bpf: add a verifier test for " Yonghong Song
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for NNTP newsgroup(s).