Re: [PATCH for 4.1,4.4] bpf: fix incorrect sign extension in check_alu_op()

[Daniel Borkmann <daniel@xxxxxxxxxxxxx>]

On 03/19/2018 05:55 PM, Jann Horn wrote:
> commit 95a762e2c8c942780948091f8f2a4f32fce1ac6f upstream.
> 
> Distinguish between
> BPF_ALU64|BPF_MOV|BPF_K (load 32-bit immediate, sign-extended to 64-bit)
> and BPF_ALU|BPF_MOV|BPF_K (load 32-bit immediate, zero-padded to 64-bit);
> only perform sign extension in the first case.
> 
> This patch differs from the mainline one because the verifier's internals
> have changed in the meantime. Mainline tracks register values as 64-bit
> values; however, 4.4 still stores tracked register values as 32-bit
> values with sign extension. Therefore, in the case of a 32-bit op with
> negative immediate, the value can't be tracked; leave the register as
> UNKNOWN_VALUE (set by the preceding check_reg_arg() call).
> 
> 
> I have manually tested this patch on top of 4.4.122. For the following BPF
> bytecode:
> 
>         BPF_MOV64_IMM(BPF_REG_1, 1),
>         BPF_JMP_IMM(BPF_JEQ, BPF_REG_1, 1, 1),
>         BPF_EXIT_INSN(),
> 
>         BPF_MOV32_IMM(BPF_REG_1, 1),
>         BPF_JMP_IMM(BPF_JEQ, BPF_REG_1, 1, 1),
>         BPF_EXIT_INSN(),
> 
>         BPF_MOV64_IMM(BPF_REG_1, -1),
>         BPF_JMP_IMM(BPF_JEQ, BPF_REG_1, -1, 1),
>         BPF_EXIT_INSN(),
> 
>         BPF_MOV32_IMM(BPF_REG_1, -1),
>         BPF_JMP_IMM(BPF_JEQ, BPF_REG_1, -1, 2),
>         BPF_MOV32_IMM(BPF_REG_0, 42),
>         BPF_EXIT_INSN(),
> 
>         BPF_MOV32_IMM(BPF_REG_0, 43),
>         BPF_EXIT_INSN()
> 
> Verifier output on 4.4.122 without this patch:
> 
> 0: (b7) r1 = 1
> 1: (15) if r1 == 0x1 goto pc+1
> 3: (b4) (u32) r1 = (u32) 1
> 4: (15) if r1 == 0x1 goto pc+1
> 6: (b7) r1 = -1
> 7: (15) if r1 == 0xffffffff goto pc+1
> 9: (b4) (u32) r1 = (u32) -1
> 10: (15) if r1 == 0xffffffff goto pc+2
> 13: (b4) (u32) r0 = (u32) 43
> 14: (95) exit
> 
> Verifier output on 4.4.122+ with this patch:
> 
> 0: (b7) r1 = 1
> 1: (15) if r1 == 0x1 goto pc+1
> 3: (b4) (u32) r1 = (u32) 1
> 4: (15) if r1 == 0x1 goto pc+1
> 6: (b7) r1 = -1
> 7: (15) if r1 == 0xffffffff goto pc+1
> 9: (b4) (u32) r1 = (u32) -1
> 10: (15) if r1 == 0xffffffff goto pc+2
>  R1=inv R10=fp
> 11: (b4) (u32) r0 = (u32) 42
> 12: (95) exit
> 
> from 10 to 13: R1=imm-1 R10=fp
> 13: (b4) (u32) r0 = (u32) 43
> 14: (95) exit
> 
> 
> This patch should be applied to linux-4.4.y and linux-4.1.y.
> 
> Signed-off-by: Jann Horn <jannh@xxxxxxxxxx>

Acked-by: Daniel Borkmann <daniel@xxxxxxxxxxxxx>

Looks good, thanks Jann!