| Message ID | 158507159511.15666.6943798089263377114.stgit@john-Precision-5820-Tower |
|---|---|
| State | Changes Requested |
| Delegated to: | BPF Maintainers |
| Headers | show |
| Series | ALU32 bounds tracking support | expand |
On Tue, Mar 24, 2020 at 10:39:55AM -0700, John Fastabend wrote: > diff --git a/tools/testing/selftests/bpf/verifier/bpf_get_stack.c b/tools/testing/selftests/bpf/verifier/bpf_get_stack.c > index f24d50f..24aa6a0 100644 > --- a/tools/testing/selftests/bpf/verifier/bpf_get_stack.c > +++ b/tools/testing/selftests/bpf/verifier/bpf_get_stack.c > @@ -7,7 +7,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, 28), > + BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 29), > BPF_MOV64_REG(BPF_REG_7, BPF_REG_0), > BPF_MOV64_IMM(BPF_REG_9, sizeof(struct test_val)), > BPF_MOV64_REG(BPF_REG_1, BPF_REG_6), > @@ -16,6 +16,7 @@ > BPF_MOV64_IMM(BPF_REG_4, 256), > BPF_EMIT_CALL(BPF_FUNC_get_stack), > BPF_MOV64_IMM(BPF_REG_1, 0), > + BPF_JMP32_REG(BPF_JSLT, BPF_REG_0, BPF_REG_1, 20), > BPF_MOV64_REG(BPF_REG_8, BPF_REG_0), > BPF_ALU64_IMM(BPF_LSH, BPF_REG_8, 32), > BPF_ALU64_IMM(BPF_ARSH, BPF_REG_8, 32), Yep. The test is wrong. But this is cheating ;) JSLT should be after shifts. The test should have been written as: diff --git a/tools/testing/selftests/bpf/verifier/bpf_get_stack.c b/tools/testing/selftests/bpf/verifier/bpf_get_stack.c index f24d50f09dbe..be0758c1bfbd 100644 --- a/tools/testing/selftests/bpf/verifier/bpf_get_stack.c +++ b/tools/testing/selftests/bpf/verifier/bpf_get_stack.c @@ -19,7 +19,7 @@ BPF_MOV64_REG(BPF_REG_8, BPF_REG_0), BPF_ALU64_IMM(BPF_LSH, BPF_REG_8, 32), BPF_ALU64_IMM(BPF_ARSH, BPF_REG_8, 32), - BPF_JMP_REG(BPF_JSLT, BPF_REG_1, BPF_REG_8, 16), + BPF_JMP_REG(BPF_JSGT, BPF_REG_1, BPF_REG_8, 16), BPF_ALU64_REG(BPF_SUB, BPF_REG_9, BPF_REG_8), BPF_MOV64_REG(BPF_REG_2, BPF_REG_7), BPF_ALU64_REG(BPF_ADD, BPF_REG_2, BPF_REG_8), That was the intent of the test. But in such form it won't work with the current patch set, but it should. More so the patches 1 and 5 make test_progs pass, but test_progs-no_alu32 fails tests 20 and 61. Because clang generates the following: 14: (85) call bpf_get_stack#67 15: (b7) r1 = 0 16: (bf) r8 = r0 17: (67) r8 <<= 32 18: (c7) r8 s>>= 32 19: (6d) if r1 s> r8 goto pc+16 (which is exactly what bpf_get_stack.c test tried to capture) I guess no_alu32 may be passing for you because you have that special clang optimization that replaces <<32 s>>32 with more efficient insn, but not everyone will be using new clang, so we have to teach verifier recognize <<32 s>>32. Thankfully with your new infra for s32 it should be easy to do. In scalar_min_max_lsh() we don't need to do dst_reg->smax_value = S64_MAX; When we have _positive_ s32_max_value we can set smax_value = s32_max_value << 32 and I think that will be correct. scalar_min_max_arsh() shouldn't need any changes. And the verifier will restore valid smax_value after <<32 s>>32 sequence. And this test will pass (after fixing s/JSLT/JSGT/) and test_progs-no_alu32 will do too. wdyt?
Alexei Starovoitov wrote: > On Tue, Mar 24, 2020 at 10:39:55AM -0700, John Fastabend wrote: > > diff --git a/tools/testing/selftests/bpf/verifier/bpf_get_stack.c b/tools/testing/selftests/bpf/verifier/bpf_get_stack.c > > index f24d50f..24aa6a0 100644 > > --- a/tools/testing/selftests/bpf/verifier/bpf_get_stack.c > > +++ b/tools/testing/selftests/bpf/verifier/bpf_get_stack.c > > @@ -7,7 +7,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, 28), > > + BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 29), > > BPF_MOV64_REG(BPF_REG_7, BPF_REG_0), > > BPF_MOV64_IMM(BPF_REG_9, sizeof(struct test_val)), > > BPF_MOV64_REG(BPF_REG_1, BPF_REG_6), > > @@ -16,6 +16,7 @@ > > BPF_MOV64_IMM(BPF_REG_4, 256), > > BPF_EMIT_CALL(BPF_FUNC_get_stack), > > BPF_MOV64_IMM(BPF_REG_1, 0), > > + BPF_JMP32_REG(BPF_JSLT, BPF_REG_0, BPF_REG_1, 20), > > BPF_MOV64_REG(BPF_REG_8, BPF_REG_0), > > BPF_ALU64_IMM(BPF_LSH, BPF_REG_8, 32), > > BPF_ALU64_IMM(BPF_ARSH, BPF_REG_8, 32), > > Yep. The test is wrong. > But this is cheating ;) > JSLT should be after shifts. > > The test should have been written as: > diff --git a/tools/testing/selftests/bpf/verifier/bpf_get_stack.c b/tools/testing/selftests/bpf/verifier/bpf_get_stack.c > index f24d50f09dbe..be0758c1bfbd 100644 > --- a/tools/testing/selftests/bpf/verifier/bpf_get_stack.c > +++ b/tools/testing/selftests/bpf/verifier/bpf_get_stack.c > @@ -19,7 +19,7 @@ > BPF_MOV64_REG(BPF_REG_8, BPF_REG_0), > BPF_ALU64_IMM(BPF_LSH, BPF_REG_8, 32), > BPF_ALU64_IMM(BPF_ARSH, BPF_REG_8, 32), > - BPF_JMP_REG(BPF_JSLT, BPF_REG_1, BPF_REG_8, 16), > + BPF_JMP_REG(BPF_JSGT, BPF_REG_1, BPF_REG_8, 16), > BPF_ALU64_REG(BPF_SUB, BPF_REG_9, BPF_REG_8), > BPF_MOV64_REG(BPF_REG_2, BPF_REG_7), > BPF_ALU64_REG(BPF_ADD, BPF_REG_2, BPF_REG_8), > > That was the intent of the test. > But in such form it won't work with the current patch set, > but it should. > > More so the patches 1 and 5 make test_progs pass, > but test_progs-no_alu32 fails tests 20 and 61. > Because clang generates the following: > 14: (85) call bpf_get_stack#67 > 15: (b7) r1 = 0 > 16: (bf) r8 = r0 > 17: (67) r8 <<= 32 > 18: (c7) r8 s>>= 32 > 19: (6d) if r1 s> r8 goto pc+16 > > (which is exactly what bpf_get_stack.c test tried to capture) Ah OK well its good we have the pattern captured in verifier tests so we don't have to rely yon clang generating it. > > I guess no_alu32 may be passing for you because you have that special > clang optimization that replaces <<32 s>>32 with more efficient insn, > but not everyone will be using new clang, so we have to teach verifier > recognize <<32 s>>32. Ah dang yes I added that patch to our toolchain because it helps so much. But I need to remember to pull from upstream branch for selftests. I would prefer we apply that patch upstream but maybe we need to encode the old behavior in some more verifier test cases so we avoid breaking it like I did here. > Thankfully with your new infra for s32 it should be easy to do. > In scalar_min_max_lsh() we don't need to do dst_reg->smax_value = S64_MAX; > When we have _positive_ s32_max_value > we can set smax_value = s32_max_value << 32 > and I think that will be correct. > scalar_min_max_arsh() shouldn't need any changes. > And the verifier will restore valid smax_value after <<32 s>>32 sequence. > And this test will pass (after fixing s/JSLT/JSGT/) and test_progs-no_alu32 > will do too. wdyt? Looks correct to me for the specific case of <<32 seeing its common enough special case for it makes sense. I'll add a patch for this with above explanation.
diff --git a/tools/testing/selftests/bpf/verifier/bpf_get_stack.c b/tools/testing/selftests/bpf/verifier/bpf_get_stack.c index f24d50f..24aa6a0 100644 --- a/tools/testing/selftests/bpf/verifier/bpf_get_stack.c +++ b/tools/testing/selftests/bpf/verifier/bpf_get_stack.c @@ -7,7 +7,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, 28), + BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 29), BPF_MOV64_REG(BPF_REG_7, BPF_REG_0), BPF_MOV64_IMM(BPF_REG_9, sizeof(struct test_val)), BPF_MOV64_REG(BPF_REG_1, BPF_REG_6), @@ -16,6 +16,7 @@ BPF_MOV64_IMM(BPF_REG_4, 256), BPF_EMIT_CALL(BPF_FUNC_get_stack), BPF_MOV64_IMM(BPF_REG_1, 0), + BPF_JMP32_REG(BPF_JSLT, BPF_REG_0, BPF_REG_1, 20), BPF_MOV64_REG(BPF_REG_8, BPF_REG_0), BPF_ALU64_IMM(BPF_LSH, BPF_REG_8, 32), BPF_ALU64_IMM(BPF_ARSH, BPF_REG_8, 32),
With current ALU32 subreg handling and retval refine fix from last patches we see an expected failure in test_verifier. With verbose verifier state being printed at each step for clarity we have the following relavent lines [I omit register states that are not necessarily useful to see failure cause], #101/p bpf_get_stack return R0 within range FAIL Failed to load prog 'Success'! [..] 14: (85) call bpf_get_stack#67 R0_w=map_value(id=0,off=0,ks=8,vs=48,imm=0) R3_w=inv48 15: R0=inv(id=0,smax_value=48,var32_off=(0x0; 0xffffffff)) 15: (b7) r1 = 0 16: R0=inv(id=0,smax_value=48,var32_off=(0x0; 0xffffffff)) R1_w=inv0 16: (bf) r8 = r0 17: R0=inv(id=0,smax_value=48,var32_off=(0x0; 0xffffffff)) R1_w=inv0 R8_w=inv(id=0,smax_value=48,var32_off=(0x0; 0xffffffff)) 17: (67) r8 <<= 32 18: R0=inv(id=0,smax_value=48,var32_off=(0x0; 0xffffffff)) R1_w=inv0 R8_w=inv(id=0,smax_value=9223372032559808512, umax_value=18446744069414584320, var_off=(0x0; 0xffffffff00000000), s32_min_value=0, s32_max_value=0, u32_max_value=0, var32_off=(0x0; 0x0)) 18: (c7) r8 s>>= 32 19 R0=inv(id=0,smax_value=48,var32_off=(0x0; 0xffffffff)) R1_w=inv0 R8_w=inv(id=0,smin_value=-2147483648, smax_value=2147483647, var32_off=(0x0; 0xffffffff)) 19: (cd) if r1 s< r8 goto pc+16 R0=inv(id=0,smax_value=48,var32_off=(0x0; 0xffffffff)) R1_w=inv0 R8_w=inv(id=0,smin_value=-2147483648, smax_value=0, var32_off=(0x0; 0xffffffff)) 20: R0=inv(id=0,smax_value=48,var32_off=(0x0; 0xffffffff)) R1_w=inv0 R8_w=inv(id=0,smin_value=-2147483648, smax_value=0, R9=inv48 20: (1f) r9 -= r8 21: (bf) r2 = r7 22: R2_w=map_value(id=0,off=0,ks=8,vs=48,imm=0) 22: (0f) r2 += r8 value -2147483648 makes map_value pointer be out of bounds After call bpf_get_stack() on line 14 and some moves we have at line 16 an r8 bound with max_value 48 but an unknown min value. This is to be expected bpf_get_stack call can only return a max of the input size but is free to return any negative error in the 32-bit register space. And further C signature returns 'int' which provides no guarantee on the upper 32-bits of the register. Lines 17 and 18 clear the top 32 bits with a left/right shift but use ARSH so we still have worst case min bound before line 19 of -2147483648. At this point the signed check 'r1 s< r8' meant to protect the addition on line 22 where dst reg is a map_value pointer may very well return true with a large negative number. Then the final line 22 will detect this as an invalid operation and fail the program. To fix add a signed less than check to ensure r8 is greater than 0 at line 19 so the bounds check works as expected. Programs _must_ check for negative return codes or they will fail to load now. But on the other hand they were buggy before so for correctness the check really is needed. Signed-off-by: John Fastabend <john.fastabend@gmail.com> --- .../testing/selftests/bpf/verifier/bpf_get_stack.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-)