Re: [RFC] bpf: verifier check for dead branch

[Yonghong Song <yhs@fb.com>]

On 8/7/20 10:30 AM, Jiri Olsa wrote:
> hi,
> we have a customer facing some odd verifier fails on following
> sk_skb program:
> 
>     0. r2 = *(u32 *)(r1 + data_end)
>     1. r4 = *(u32 *)(r1 + data)
>     2. r3 = r4
>     3. r3 += 42
>     4. r1 = 0
>     5. if r3 > r2 goto 8
>     6. r4 += 14
>     7. r1 = r4
>     8. if r3 > r2 goto 10
>     9. r2 = *(u8 *)(r1 + 9)
>    10. r0 = 0
>    11. exit
> 
> The code checks if the skb data is big enough (5) and if it is,
> it prepares pointer in r1 (7), then there's again size check (8)
> and finally data load from r1 (9).
> 
> It's and odd code, but apparently this is something that can
> get produced by clang.

Could you provide a test case where clang generates the above code?
I would like to see whether clang can do a better job to avoid
such codes.

> 
> I made selftest out of it and it fails to load with:
> 
>    # test_verifier -v 267
>    #267/p dead path check FAIL
>    Failed to load prog 'Success'!
>    0: (61) r2 = *(u32 *)(r1 +80)
>    1: (61) r4 = *(u32 *)(r1 +76)
>    2: (bf) r3 = r4
>    3: (07) r3 += 42
>    4: (b7) r1 = 0
>    5: (2d) if r3 > r2 goto pc+2
> 
>    from 5 to 8: R1_w=inv0 R2_w=pkt_end(id=0,off=0,imm=0) R3_w=pkt(id=0,off=42,r=0,imm=0) R4_w=pkt(id=0,off=0,r=0,imm=0) R10=fp0
>    8: (2d) if r3 > r2 goto pc+1
>     R1_w=inv0 R2_w=pkt_end(id=0,off=0,imm=0) R3_w=pkt(id=0,off=42,r=42,imm=0) R4_w=pkt(id=0,off=0,r=42,imm=0) R10=fp0
>    9: (69) r2 = *(u16 *)(r1 +9)
>    R1 invalid mem access 'inv'
>    processed 15 insns (limit 1000000) max_states_per_insn 0 total_states 1 peak_states 1 mark_read 0
> 
> The verifier does not seem to take into account that code can't
> ever reach instruction 9 if the size check fails and r1 will be
> always valid when size check succeeds.
> 
> My guess is that verifier does not have such check, but I'm still
> scratching on the surface of it, so I could be totally wrong and
> missing something.. before I dive in I was wondering you guys
> could help me out with some insights or suggestions.

There are no bits in reg_state to indicate a pkt pointer already goes 
beyond the packet_end. So insn 8 cannot conclude the condition r3 > r2 
is always true...

If a bit to indicate packet pointer exceeding the end, it should work.
Fixing in verifier probably not too hard. But this should be a corner 
case and it will be good to check whether we can avoid it in clang.

> 
> thanks,
> jirka
> 
> 
> ---
>   .../testing/selftests/bpf/verifier/ctx_skb.c  | 21 +++++++++++++++++++
>   1 file changed, 21 insertions(+)
> 
> diff --git a/tools/testing/selftests/bpf/verifier/ctx_skb.c b/tools/testing/selftests/bpf/verifier/ctx_skb.c
> index 2e16b8e268f2..54578f1fb662 100644
> --- a/tools/testing/selftests/bpf/verifier/ctx_skb.c
> +++ b/tools/testing/selftests/bpf/verifier/ctx_skb.c
> @@ -346,6 +346,27 @@
>   	.result = ACCEPT,
>   	.prog_type = BPF_PROG_TYPE_SK_SKB,
>   },
> +{
> +	"dead path check",
> +	.insns = {
> +	BPF_LDX_MEM(BPF_W, BPF_REG_2, BPF_REG_1,		//  0. r2 = *(u32 *)(r1 + data_end)
> +		    offsetof(struct __sk_buff, data_end)),
> +	BPF_LDX_MEM(BPF_W, BPF_REG_4, BPF_REG_1,		//  1. r4 = *(u32 *)(r1 + data)
> +		    offsetof(struct __sk_buff, data)),
> +	BPF_MOV64_REG(BPF_REG_3, BPF_REG_4),			//  2. r3 = r4
> +	BPF_ALU64_IMM(BPF_ADD, BPF_REG_3, 42),			//  3. r3 += 42
> +	BPF_MOV64_IMM(BPF_REG_1, 0),				//  4. r1 = 0
> +	BPF_JMP_REG(BPF_JGT, BPF_REG_3, BPF_REG_2, 2),		//  5. if r3 > r2 goto 8
> +	BPF_ALU64_IMM(BPF_ADD, BPF_REG_4, 14),			//  6. r4 += 14
> +	BPF_MOV64_REG(BPF_REG_1, BPF_REG_4),			//  7. r1 = r4
> +	BPF_JMP_REG(BPF_JGT, BPF_REG_3, BPF_REG_2, 1),		//  8. if r3 > r2 goto 10
> +	BPF_LDX_MEM(BPF_H, BPF_REG_2, BPF_REG_1, 9),		//  9. r2 = *(u8 *)(r1 + 9)
> +	BPF_MOV64_IMM(BPF_REG_0, 0),				// 10. r0 = 0
> +	BPF_EXIT_INSN(),					// 11. exit
> +	},
> +	.result = ACCEPT,
> +	.prog_type = BPF_PROG_TYPE_SK_SKB,
> +},
>   {
>   	"overlapping checks for direct packet access SK_SKB",
>   	.insns = {
>