Looks good to me, I tested with several complex program without any
problem. Thanks for the patch.
--William
On Mon, Jan 23, 2017 at 4:06 PM, Daniel Borkmann wrote:
> William reported couple of issues in relation to direct packet
> access. Typical scheme is to check for data + [off] <= data_end,
> where [off] can be either immediate or coming from a tracked
> register that contains an immediate, depending on the branch, we
> can then access the data. However, in case of calculating [off]
> for either the mentioned test itself or for access after the test
> in a more "complex" way, then the verifier will stop tracking the
> CONST_IMM marked register and will mark it as UNKNOWN_VALUE one.
>
> Adding that UNKNOWN_VALUE typed register to a pkt() marked
> register, the verifier then bails out in check_packet_ptr_add()
> as it finds the registers imm value below 48. In the first below
> example, that is due to evaluate_reg_imm_alu() not handling right
> shifts and thus marking the register as UNKNOWN_VALUE via helper
> __mark_reg_unknown_value() that resets imm to 0.
>
> In the second case the same happens at the time when r4 is set
> to r4 &= r5, where it transitions to UNKNOWN_VALUE from
> evaluate_reg_imm_alu(). Later on r4 we shift right by 3 inside
> evaluate_reg_alu(), where the register's imm turns into 3. That
> is, for registers with type UNKNOWN_VALUE, imm of 0 means that
> we don't know what value the register has, and for imm > 0 it
> means that the value has [imm] upper zero bits. F.e. when shifting
> an UNKNOWN_VALUE register by 3 to the right, no matter what value
> it had, we know that the 3 upper most bits must be zero now.
> This is to make sure that ALU operations with unknown registers
> don't overflow. Meaning, once we know that we have more than 48
> upper zero bits, or, in other words cannot go beyond 0x offset
> with ALU ops, such an addition will track the target register
> as a new pkt() register with a new id, but 0 offset and 0 range,
> so for that a new data/data_end test will be required. Is the source
> register a CONST_IMM one that is to be added to the pkt() register,
> or the source instruction is an add instruction with immediate
> value, then it will get added if it stays within max 0x bounds.
> From there, pkt() type, can be accessed should reg->off + imm be
> within the access range of pkt().
>
> [...]
> from 28 to 30: R0=imm1,min_value=1,max_value=1
> R1=pkt(id=0,off=0,r=22) R2=pkt_end
> R3=imm144,min_value=144,max_value=144
> R4=imm0,min_value=0,max_value=0
> R5=inv48,min_value=2054,max_value=2054 R10=fp
> 30: (bf) r5 = r3
> 31: (07) r5 += 23
> 32: (77) r5 >>= 3
> 33: (bf) r6 = r1
> 34: (0f) r6 += r5
> cannot add integer value with 0 upper zero bits to ptr_to_packet
>
> [...]
> from 52 to 80: R0=imm1,min_value=1,max_value=1
> R1=pkt(id=0,off=0,r=34) R2=pkt_end R3=inv
> R4=imm272 R5=inv56,min_value=17,max_value=17
> R6=pkt(id=0,off=26,r=34) R10=fp
> 80: (07) r4 += 71
> 81: (18) r5 = 0xfff8
> 83: (5f) r4 &= r5
> 84: (77) r4 >>= 3
> 85: (0f) r1 += r4
> cannot add integer value with 3 upper zero bits to ptr_to_packet
>
> Thus to get above use-cases working, evaluate_reg_imm_alu() has
> been extended for further ALU ops. This is fine, because we only
> operate strictly within realm of CONST_IMM types, so here we don't
> care about overflows as they will happen in the simulated but also
> real execution and interaction with pkt() in check_packet_ptr_add()
> will check actual imm value once added to pkt(), but it's irrelevant
> before.
>
> With regards to 06c1c049721a ("bpf: allow helpers access to variable
> memory") that works on UNKNOWN_VALUE registers, the verifier becomes
> now a bit smarter as it can better resolve ALU ops, so we need to
> adapt two test cases there, as min/max bound tracking only becomes
> necessary when registers were spilled to stack. So while mask was
> set before to track upper bound for UNKNOWN_VALUE case, it's now
> resolved directly as CONST_IMM, and such contructs are only necessary
> when f.e. registers are spilled.
>
> For commit 6b17387307ba ("bpf: recognize 64bit immediate loads as
> consts") that initially enabled dw load tracking only for nfp jit/
> analyzer, I did couple of tests on large, complex programs and we
> don't increase complexity badly (my tests were in ~3% range on avg).
> I've added a couple of tests similar to affected code above, and
> it works fine with verifier now.
>
> Reported-by: William Tu
> Signed-off-by: Daniel Borkmann
> Cc: Gianluca Borello
> Cc: William Tu
> Acked-by: Alexei Starovoitov
> ---
> kernel/bpf/verifier.c | 64 +++---
> tools/testing/selftests/bpf/test_verifier.c | 82
> +
> 2 files changed, 127 insertions(+), 19 deletions(-)
>
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 8f69df7..fb3513b 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kern
