lists.openwall.net   lists  /  announce  owl-users  owl-dev  john-users  john-dev  passwdqc-users  yescrypt  popa3d-users  /  oss-security  kernel-hardening  musl  sabotage  tlsify  passwords  /  crypt-dev  xvendor  /  Bugtraq  Full-Disclosure  linux-kernel  linux-netdev  linux-ext4  linux-hardening  PHC 
Open Source and information security mailing list archives
 
Hash Suite: Windows password security audit tool. GUI, reports in PDF.
[<prev] [next>] [thread-next>] [day] [month] [year] [list]
Date:   Fri, 7 Aug 2020 19:30:45 +0200
From:   Jiri Olsa <jolsa@...hat.com>
To:     Alexei Starovoitov <ast@...nel.org>,
        Daniel Borkmann <daniel@...earbox.net>
Cc:     bpf@...r.kernel.org, netdev@...r.kernel.org,
        Andrii Nakryiko <andriin@...com>,
        Martin KaFai Lau <kafai@...com>,
        Song Liu <songliubraving@...com>, Yonghong Song <yhs@...com>,
        John Fastabend <john.fastabend@...il.com>,
        KP Singh <kpsingh@...omium.org>
Subject: [RFC] bpf: verifier check for dead branch

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

Powered by blists - more mailing lists