On Mon, Aug 24, 2020 at 11:46:08PM -0700, Yonghong Song wrote:
> bpf selftest test_progs/test_sk_assign failed with llvm 11 and llvm 12.
> Compared to llvm 10, llvm 11 and 12 generates xor instruction which
> is not handled properly in verifier. The following illustrates the
> problem:
>
> 16: (b4) w5 = 0
> 17: ... R5_w=inv0 ...
> ...
> 132: (a4) w5 ^= 1
> 133: ... R5_w=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff)) ...
> ...
> 37: (bc) w8 = w5
> 38: ... R5=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff))
> R8_w=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff)) ...
> ...
> 41: (bc) w3 = w8
> 42: ... R3_w=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff)) ...
> 45: (56) if w3 != 0x0 goto pc+1
> ... R3_w=inv0 ...
> 46: (b7) r1 = 34
> 47: R1_w=inv34 R7=pkt(id=0,off=26,r=38,imm=0)
> 47: (0f) r7 += r1
> 48: R1_w=invP34 R3_w=inv0 R7_w=pkt(id=0,off=60,r=38,imm=0)
> 48: (b4) w9 = 0
> 49: R1_w=invP34 R3_w=inv0 R7_w=pkt(id=0,off=60,r=38,imm=0)
> 49: (69) r1 = *(u16 *)(r7 +0)
> invalid access to packet, off=60 size=2, R7(id=0,off=60,r=38)
> R7 offset is outside of the packet
>
> At above insn 132, w5 = 0, but after w5 ^= 1, we give a really conservative
> value of w5. At insn 45, in reality the condition should be always false.
> But due to conservative value for w3, the verifier evaluates it could be
> true and this later leads to verifier failure complaining potential
> packet out-of-bound access.
>
> This patch implemented proper XOR support in verifier.
> In the above example, we have:
> 132: R5=invP0
> 132: (a4) w5 ^= 1
> 133: R5_w=invP1
> ...
> 37: (bc) w8 = w5
> ...
> 41: (bc) w3 = w8
> 42: R3_w=invP1
> ...
> 45: (56) if w3 != 0x0 goto pc+1
> 47: R3_w=invP1
> ...
> processed 353 insns ...
> and the verifier can verify the program successfully.
>
> Cc: John Fastabend <john.fastabend@xxxxxxxxx>
> Signed-off-by: Yonghong Song <yhs@xxxxxx>
> ---
> kernel/bpf/verifier.c | 66 +++++++++++++++++++++++++++++++++++++++++++
> 1 file changed, 66 insertions(+)
>
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index dd24503ab3d3..a08cabc0f683 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -5801,6 +5801,67 @@ static void scalar_min_max_or(struct bpf_reg_state *dst_reg,
> __update_reg_bounds(dst_reg);
> }
>
> +static void scalar32_min_max_xor(struct bpf_reg_state *dst_reg,
> + struct bpf_reg_state *src_reg)
> +{
> + bool src_known = tnum_subreg_is_const(src_reg->var_off);
> + bool dst_known = tnum_subreg_is_const(dst_reg->var_off);
> + struct tnum var32_off = tnum_subreg(dst_reg->var_off);
> + s32 smin_val = src_reg->s32_min_value;
> +
> + /* Assuming scalar64_min_max_xor will be called so it is safe
> + * to skip updating register for known case.
> + */
> + if (src_known && dst_known)
> + return;
why?
I've looked at _and() and _or() variants that do the same and
couldn't quite remember why it's ok to do so.
> +
> + /* We get both minimum and maximum from the var32_off. */
> + dst_reg->u32_min_value = var32_off.value;
> + dst_reg->u32_max_value = var32_off.value | var32_off.mask;
> +
> + if (dst_reg->s32_min_value >= 0 && smin_val >= 0) {
> + /* XORing two positive sign numbers gives a positive,
> + * so safe to cast u32 result into s32.
> + */
> + dst_reg->s32_min_value = dst_reg->u32_min_value;
> + dst_reg->s32_max_value = dst_reg->u32_max_value;
> + } else {
> + dst_reg->s32_min_value = S32_MIN;
> + dst_reg->s32_max_value = S32_MAX;
> + }
> +}
> +
> +static void scalar_min_max_xor(struct bpf_reg_state *dst_reg,
> + struct bpf_reg_state *src_reg)
> +{
> + bool src_known = tnum_is_const(src_reg->var_off);
> + bool dst_known = tnum_is_const(dst_reg->var_off);
> + s64 smin_val = src_reg->smin_value;
> +
> + if (src_known && dst_known) {
> + /* dst_reg->var_off.value has been updated earlier */
right, but that means that there is sort-of 'bug' (unnecessary operation)
that caused me a lot of head scratching.
scalar_min_max_and() and scalar_min_max_or() do the alu in similar situation:
if (src_known && dst_known) {
__mark_reg_known(dst_reg, dst_reg->var_off.value |
src_reg->var_off.value);
I guess it's still technically correct to repeat alu operation.
second & and second | won't change the value of dst_reg,
but it feels that it's correct by accident?
John ?
> + __mark_reg_known(dst_reg, dst_reg->var_off.value);
> + return;
> + }
> +
> + /* We get both minimum and maximum from the var_off. */
> + dst_reg->umin_value = dst_reg->var_off.value;
> + dst_reg->umax_value = dst_reg->var_off.value | dst_reg->var_off.mask;
I think this is correct, but I hope somebody else can analyze this as well.
John, Ed ?
> +
> + if (dst_reg->smin_value >= 0 && smin_val >= 0) {
> + /* XORing two positive sign numbers gives a positive,
> + * so safe to cast u64 result into s64.
> + */
> + dst_reg->smin_value = dst_reg->umin_value;
> + dst_reg->smax_value = dst_reg->umax_value;
> + } else {
> + dst_reg->smin_value = S64_MIN;
> + dst_reg->smax_value = S64_MAX;
> + }
> +
> + __update_reg_bounds(dst_reg);
> +}
