On Fri, Dec 07, 2018 at 12:16:18PM -0500, Jiong Wang wrote:
> Currently, the destination register is marked as unknown for 32-bit
> sub-register move (BPF_MOV | BPF_ALU) whenever the source register type is
> SCALAR_VALUE.
>
> This is too conservative that some valid cases will be rejected.
> Especially, this may turn a constant scalar value into unknown value that
> could break some assumptions of verifier.
>
> For example, test_l4lb_noinline.c has the following C code:
>
> struct real_definition *dst
>
> 1: if (!get_packet_dst(&dst, &pckt, vip_info, is_ipv6))
> 2: return TC_ACT_SHOT;
> 3:
> 4: if (dst->flags & F_IPV6) {
>
> get_packet_dst is responsible for initializing "dst" into valid pointer and
> return true (1), otherwise return false (0). The compiled instruction
> sequence using alu32 will be:
>
> 412: (54) (u32) r7 &= (u32) 1
> 413: (bc) (u32) r0 = (u32) r7
> 414: (95) exit
>
> insn 413, a BPF_MOV | BPF_ALU, however will turn r0 into unknown value even
> r7 contains SCALAR_VALUE 1.
>
> This causes trouble when verifier is walking the code path that hasn't
> initialized "dst" inside get_packet_dst, for which case 0 is returned and
> we would then expect verifier concluding line 1 in the above C code pass
> the "if" check, therefore would skip fall through path starting at line 4.
> Now, because r0 returned from callee has became unknown value, so verifier
> won't skip analyzing path starting at line 4 and "dst->flags" requires
> dereferencing the pointer "dst" which actually hasn't be initialized for
> this path.
>
> This patch relaxed the code marking sub-register move destination. For a
> SCALAR_VALUE, it is safe to just copy the value from source then truncate
> it into 32-bit.
>
> A unit test also included to demonstrate this issue. This test will fail
> before this patch.
>
> This relaxation could let verifier skipping more paths for conditional
> comparison against immediate. It also let verifier recording a more
> accurate/strict value for one register at one state, if this state end up
> with going through exit without rejection and it is used for state
> comparison later, then it is possible an inaccurate/permissive value is
> better. So the real impact on verifier processed insn number is complex.
> But in all, without this fix, valid program could be rejected.
>
> From real benchmarking on kernel selftests and Cilium bpf tests, there is
> no impact on processed instruction number when tests ares compiled with
> default compilation options. There is slightly improvements when they are
> compiled with -mattr=+alu32 after this patch.
>
> Also, test_xdp_noinline/-mattr=+alu32 now passed verification. It is
> rejected before this fix.
>
> Insn processed before/after this patch:
>
> default -mattr=+alu32
>
> Kernel selftest
> ===
> test_xdp.o 371/371 369/369
> test_l4lb.o 6345/6345 5623/5623
> test_xdp_noinline.o 2971/2971 rejected/2727
> test_tcp_estates.o 429/429 430/430
>
> Cilium bpf
> ===
> bpf_lb-DLB_L3.o: 2085/2085 1685/1687
> bpf_lb-DLB_L4.o: 2287/2287 1986/1982
> bpf_lb-DUNKNOWN.o: 690/690 622/622
> bpf_lxc.o: 95033/95033 N/A
> bpf_netdev.o: 7245/7245 N/A
> bpf_overlay.o: 2898/2898 3085/2947
>
> NOTE:
> - bpf_lxc.o and bpf_netdev.o compiled by -mattr=+alu32 are rejected by
> verifier due to another issue inside verifier on supporting alu32
> binary.
> - Each cilium bpf program could generate several processed insn number,
> above number is sum of them.
>
> v1->v2:
> - Restrict the change on SCALAR_VALUE.
> - Update benchmark numbers on Cilium bpf tests.
>
> Signed-off-by: Jiong Wang <jiong.w...@netronome.com>
> ---
> kernel/bpf/verifier.c | 16 ++++++++++++----
> tools/testing/selftests/bpf/test_verifier.c | 13 +++++++++++++
> 2 files changed, 25 insertions(+), 4 deletions(-)
>
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 9584438..777720a 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -3583,12 +3583,15 @@ static int check_alu_op(struct bpf_verifier_env *env,
> struct bpf_insn *insn)
> return err;
>
> if (BPF_SRC(insn->code) == BPF_X) {
> + struct bpf_reg_state *src_reg = regs + insn->src_reg;
> + struct bpf_reg_state *dst_reg = regs + insn->dst_reg;
> +
> if (BPF_CLASS(insn->code) == BPF_ALU64) {
> /* case: R1 = R2
> * copy register state to dest reg
> */
> - regs[insn->dst_reg] = regs[insn->src_reg];
> - regs[insn->dst_reg].live |= REG_LIVE_WRITTEN;
> + *dst_reg = *src_reg;
> + dst_reg->live |= REG_LIVE_WRITTEN;
> } else {
> /* R1 = (u32) R2 */
> if (is_pointer_value(env, insn->src_reg)) {
> @@ -3596,9 +3599,14 @@ static int check_alu_op(struct bpf_verifier_env *env,
> struct bpf_insn *insn)
> "R%d partial copy of pointer\n",
> insn->src_reg);
> return -EACCES;
> + } else if (src_reg->type == SCALAR_VALUE) {
> + *dst_reg = *src_reg;
> + dst_reg->live |= REG_LIVE_WRITTEN;
> + } else {
> + mark_reg_unknown(env, regs,
> + insn->dst_reg);
shouldn't we do dst_reg->live |= REG_LIVE_WRITTEN here as well ?
Not a new issue, but probably should fix in the same patch?
> }
> - mark_reg_unknown(env, regs, insn->dst_reg);
> - coerce_reg_to_size(®s[insn->dst_reg], 4);
> + coerce_reg_to_size(dst_reg, 4);
> }
> } else {
> /* case: R = imm
> diff --git a/tools/testing/selftests/bpf/test_verifier.c
> b/tools/testing/selftests/bpf/test_verifier.c
> index 17021d2..18d0b7f 100644
> --- a/tools/testing/selftests/bpf/test_verifier.c
> +++ b/tools/testing/selftests/bpf/test_verifier.c
> @@ -2936,6 +2936,19 @@ static struct bpf_test tests[] = {
> .result = ACCEPT,
> },
> {
> + "alu32: mov u32 const",
> + .insns = {
> + BPF_MOV32_IMM(BPF_REG_7, 0),
> + BPF_ALU32_IMM(BPF_AND, BPF_REG_7, 1),
> + BPF_MOV32_REG(BPF_REG_0, BPF_REG_7),
> + BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 1),
> + BPF_LDX_MEM(BPF_DW, BPF_REG_0, BPF_REG_7, 0),
> + BPF_EXIT_INSN(),
> + },
> + .result = ACCEPT,
> + .retval = 0,
> + },
> + {
> "unpriv: partial copy of pointer",
> .insns = {
> BPF_MOV32_REG(BPF_REG_1, BPF_REG_10),
> --
> 2.7.4
>
