[RFC] bpf: verifier check for dead branch

[Jiri Olsa <jolsa@redhat.com>]

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.

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.

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 = {
-- 
2.25.4