Re: [PATCH bpf-next 1/2] bpf: fix a verifier failure with xor

From: Andrii Nakryiko <andrii.nakryiko@gmail.com>
To: Yonghong Song <yhs@fb.com>
Cc: bpf <bpf@vger.kernel.org>, Alexei Starovoitov <ast@kernel.org>,
	Daniel Borkmann <daniel@iogearbox.net>,
	Kernel Team <kernel-team@fb.com>,
	John Fastabend <john.fastabend@gmail.com>
Subject: Re: [PATCH bpf-next 1/2] bpf: fix a verifier failure with xor
Date: Tue, 1 Sep 2020 13:07:09 -0700	[thread overview]
Message-ID: <CAEf4Bzb89dz_Sjy14LjQSDWrQ=TpSHAfgf=_Sa=bWUKGqJHCgQ@mail.gmail.com> (raw)
In-Reply-To: <20200825064608.2017937-1-yhs@fb.com>

On Mon, Aug 24, 2020 at 11:47 PM Yonghong Song <yhs@fb.com> 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

Does this mean that some perfectly working BPF programs will now fail
to verify on older kernels, if compiled with llvm 11 or llvm 12? If
yes, is there something that one can do to prevent Clang from using
xor in such situations?

> 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@gmail.com>
> Signed-off-by: Yonghong Song <yhs@fb.com>
> ---
>  kernel/bpf/verifier.c | 66 +++++++++++++++++++++++++++++++++++++++++++
>  1 file changed, 66 insertions(+)
>

[...]