Message ID | 20231009-jmp-into-reserved-fields-v1-1-d8006e2ac1f6@gmail.com |
---|---|
State | New |
Headers |
Return-Path: <linux-kernel-owner@vger.kernel.org> Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:a888:0:b0:403:3b70:6f57 with SMTP id x8csp1792434vqo; Mon, 9 Oct 2023 04:13:00 -0700 (PDT) X-Google-Smtp-Source: AGHT+IHfFBTIUKDSBIuuJw6hl93y6FV38thLK2aGCrdna8JZ/9huNy1AhWuw1LrRAFKBQFpXZ6aK X-Received: by 2002:a17:90a:208:b0:277:1bd8:abe8 with SMTP id c8-20020a17090a020800b002771bd8abe8mr13018014pjc.18.1696849979994; Mon, 09 Oct 2023 04:12:59 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1696849979; cv=none; d=google.com; s=arc-20160816; b=j8ahmlS0thRiE4KQbdWqGmW9aCzAiQbeA1os4Yy/DFmvNhP0Wl0vvRY0fVX+GnDNYE f5ctRpH6x5g9diqk4kDz03s7s+78kimJd5qXOFPH/FE3SrQfIO85semdG5h3aKSP7e1V H/qbNsu/4QRMWnNPCMtxaEObA8tvKJ+hDC3PFU3k+Zp+royCrijKtGkktGyHfi8r3mg0 hO8a2KEwXY5gFqFZ1ATB4QMnt7kGbLaXmfv9oYkS+scL/AHn97T+YTl4R0VO/G5i6sTL H/B2PberEh0CazNkE2EIbvRBbW9otNOR16Wz63LrTdAfA4vzidI7Wt9m9DJgly76uboY HYmA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:cc:to:message-id:content-transfer-encoding :mime-version:subject:date:from:dkim-signature; bh=er7cddzQstZpFxcdLakPZUUkD06YhuxbDUUxJ2NUqkQ=; fh=mXBL/m2WqL131Kw3M+zu1H8f4iBK/X/nYOAw26JNs+8=; b=wAJ0vOfyNo/ijKmLBlaBEnl886ennoiGJ9WdeCmnMmIfHE4K7sbgsLK1sru7ftD5O4 GkbKKr8mwxP7jSqKp178AQvLvcXnKsGwEJcpY6f492jM81poMNn4Lw8aVFDlh5GMiD9J KoBCm+A4CfNw/UXfqLW5l9WfCsxTuh36GFGtDfhNLML7ttJcQCGL47UWbczvUkR6jc3y ddgwNBlAf0gCfFe8KcDEaStJOIC6MgT3IAHzW3I8ZFkvFHCjcIthfxzNypOX967E9EZI EoMAXfPRn6gvZz1Z4/B47GaBDnb/lHzLCHUD/RteHA5TLQO+Xeltp9Ah1Tap3dFjCgrG ZNEg== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gmail.com header.s=20230601 header.b=RyKZ8Xcu; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.34 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com Received: from howler.vger.email (howler.vger.email. [23.128.96.34]) by mx.google.com with ESMTPS id u4-20020a17090a6a8400b00277624ffa82si11533519pjj.86.2023.10.09.04.12.59 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 09 Oct 2023 04:12:59 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.34 as permitted sender) client-ip=23.128.96.34; Authentication-Results: mx.google.com; dkim=pass header.i=@gmail.com header.s=20230601 header.b=RyKZ8Xcu; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.34 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com Received: from out1.vger.email (depot.vger.email [IPv6:2620:137:e000::3:0]) by howler.vger.email (Postfix) with ESMTP id BE7DB8049122; Mon, 9 Oct 2023 04:12:57 -0700 (PDT) X-Virus-Status: Clean X-Virus-Scanned: clamav-milter 0.103.10 at howler.vger.email Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1346171AbjJILMk (ORCPT <rfc822;ezelljr.billy@gmail.com> + 18 others); Mon, 9 Oct 2023 07:12:40 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:54976 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1346139AbjJILMj (ORCPT <rfc822;linux-kernel@vger.kernel.org>); Mon, 9 Oct 2023 07:12:39 -0400 Received: from mail-wm1-x32a.google.com (mail-wm1-x32a.google.com [IPv6:2a00:1450:4864:20::32a]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 1A6E694; Mon, 9 Oct 2023 04:12:38 -0700 (PDT) Received: by mail-wm1-x32a.google.com with SMTP id 5b1f17b1804b1-405497850dbso40792215e9.0; Mon, 09 Oct 2023 04:12:38 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1696849956; x=1697454756; darn=vger.kernel.org; h=cc:to:message-id:content-transfer-encoding:mime-version:subject :date:from:from:to:cc:subject:date:message-id:reply-to; bh=er7cddzQstZpFxcdLakPZUUkD06YhuxbDUUxJ2NUqkQ=; b=RyKZ8XcuK5mhjvVE4OscfXV00ahPF7K8bV0JWsOdpcKGqTIWun3PSssg5ks4C7xHzo R8zbbr4NuyEtgOSmU9fjgQNSPOJdSgBNsw/y2Sp3foNHtpgwR22ZwbsjN7QRR3NfhDGW xxP4NQ/Z+p2f79jEJfeWNfVOXqVHOQSVP+M5+frLnzz2rMjFLM2Oi97MrvGEb/2MjSvg 3PXQ2zplh1raedE3UAz8MIiw89+BznXaH7zU/LdZptGImx6Vt5DHr22d3wdJu0wam5f/ gEZ4gm8KghLF1WtZMfTEFBTcC0RXS/sFKeY7WMuPYMECnWXnrK0jxpUlPbx1ikcEbnFx irYA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1696849956; x=1697454756; h=cc:to:message-id:content-transfer-encoding:mime-version:subject :date:from:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=er7cddzQstZpFxcdLakPZUUkD06YhuxbDUUxJ2NUqkQ=; b=tkI+/oG4bUj7Lux1yUgtl8H9PQPf2pi0qI/kRCDbxxDdMic/NmLetS8cOKzS8IKC6h PcqItoUHl/3A+/2RxdUCg4blhiSP5rzoFvFEvWkM2wZVjLdXWjZbVVI9wF7PcXZyH/fT Kapdez2krj3q55HwgDD8yl2fYGZ2ZOwfr4iTQ3bkkL1uV33U7nWBJ2dF0K5OzrKkBgVZ 6/CHAcp4TnfpH/3/6MRHMro8FXcb+hq5pattgW/Gd+9EtYjgIWGXl2ZLyJiKLQnhxeCd 8CHfINdiqsH1phywHEmyNgmEg2JhUxy3tGunMVn2bAJrgUoAz7EC4F5iIh32z9bPxNY3 N+Yw== X-Gm-Message-State: AOJu0YxuNwBbQ9p0gTmD1Mg5djzgQEqmmsuKHSIx2YoUjsuHXlVD6Pgw 9mh9/mnieFR8eO8TXWcMaO/Uw/eOUw== X-Received: by 2002:a5d:6a07:0:b0:314:350a:6912 with SMTP id m7-20020a5d6a07000000b00314350a6912mr13366375wru.36.1696849955951; Mon, 09 Oct 2023 04:12:35 -0700 (PDT) Received: from amdsuplus2.inf.ethz.ch (amdsuplus2.inf.ethz.ch. [129.132.31.88]) by smtp.gmail.com with ESMTPSA id n8-20020a5d4208000000b003253523d767sm9285019wrq.109.2023.10.09.04.12.35 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 09 Oct 2023 04:12:35 -0700 (PDT) From: Hao Sun <sunhao.th@gmail.com> Date: Mon, 09 Oct 2023 13:12:02 +0200 Subject: [PATCH bpf-next] Detect jumping to reserved code during check_cfg() MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: 7bit Message-Id: <20231009-jmp-into-reserved-fields-v1-1-d8006e2ac1f6@gmail.com> X-B4-Tracking: v=1; b=H4sIAAHgI2UC/x3MQQ6DIBBG4auYWXcS0EXFqzRdIPy001gkYIyJ4 e4Sl2/xvZMKsqDQ1J2UsUuRNbbQj47c18YPWHxr6lU/aKUM//6JJW4rZzS6w3MQLL5wcNqa0Y5 4ekeNp4wgx71+0ZwCRxwbvWu9AJ+Mgb90AAAA To: Alexei Starovoitov <ast@kernel.org>, Daniel Borkmann <daniel@iogearbox.net>, John Fastabend <john.fastabend@gmail.com>, Andrii Nakryiko <andrii@kernel.org>, Martin KaFai Lau <martin.lau@linux.dev>, Song Liu <song@kernel.org>, Yonghong Song <yonghong.song@linux.dev>, KP Singh <kpsingh@kernel.org>, Stanislav Fomichev <sdf@google.com>, Hao Luo <haoluo@google.com>, Jiri Olsa <jolsa@kernel.org> Cc: bpf@vger.kernel.org, linux-kernel@vger.kernel.org, Hao Sun <sunhao.th@gmail.com> X-Mailer: b4 0.12.3 X-Developer-Signature: v=1; a=ed25519-sha256; t=1696849955; l=2372; i=sunhao.th@gmail.com; s=20231009; h=from:subject:message-id; bh=wf3i1Iv2g4OKCrVAVIuikfMpT8jO6JJjtxyGZjBPh+c=; b=NXxUFgPTG86JjkxKihOaSnVsPPFSRBFPQbNOwB4RujNLdjlbxW0UY1ypBJs5EjMP9AhyMIfdC 8bAQvRSF97OC6Ska02pyK6OVt5hHPEL/fAU4xW3MB7c37zjIy8xsGdy X-Developer-Key: i=sunhao.th@gmail.com; a=ed25519; pk=AHFxrImGtyqXOuw4f5xTNh4PGReb7hzD86ayyTZCXd4= X-Spam-Status: No, score=3.0 required=5.0 tests=DKIM_SIGNED,DKIM_VALID, DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI,RCVD_IN_SBL_CSS, SPF_HELO_NONE,SPF_PASS autolearn=no autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on howler.vger.email Precedence: bulk List-ID: <linux-kernel.vger.kernel.org> X-Mailing-List: linux-kernel@vger.kernel.org X-Greylist: Sender passed SPF test, not delayed by milter-greylist-4.6.4 (howler.vger.email [0.0.0.0]); Mon, 09 Oct 2023 04:12:57 -0700 (PDT) X-Spam-Level: ** X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1779276164879841782 X-GMAIL-MSGID: 1779276164879841782 |
Series |
[bpf-next] Detect jumping to reserved code during check_cfg()
|
|
Commit Message
Hao Sun
Oct. 9, 2023, 11:12 a.m. UTC
Currently, we don't check if the branch-taken of a jump is reserved code of
ld_imm64. Instead, such a issue is captured in check_ld_imm(). The verifier
gives the following log in such case:
func#0 @0
0: R1=ctx(off=0,imm=0) R10=fp0
0: (18) r4 = 0xffff888103436000 ; R4_w=map_ptr(off=0,ks=4,vs=128,imm=0)
2: (18) r1 = 0x1d ; R1_w=29
4: (55) if r4 != 0x0 goto pc+4 ; R4_w=map_ptr(off=0,ks=4,vs=128,imm=0)
5: (1c) w1 -= w1 ; R1_w=0
6: (18) r5 = 0x32 ; R5_w=50
8: (56) if w5 != 0xfffffff4 goto pc-2
mark_precise: frame0: last_idx 8 first_idx 0 subseq_idx -1
mark_precise: frame0: regs=r5 stack= before 6: (18) r5 = 0x32
7: R5_w=50
7: BUG_ld_00
invalid BPF_LD_IMM insn
Here the verifier rejects the program because it thinks insn at 7 is an
invalid BPF_LD_IMM, but such a error log is not accurate since the issue
is jumping to reserved code not because the program contains invalid insn.
Therefore, make the verifier check the jump target during check_cfg(). For
the same program, the verifier reports the following log:
func#0 @0
jump to reserved code from insn 8 to 7
---
Signed-off-by: Hao Sun <sunhao.th@gmail.com>
---
kernel/bpf/verifier.c | 7 +++++++
1 file changed, 7 insertions(+)
---
base-commit: 3157b7ce14bbf468b0ca8613322a05c37b5ae25d
change-id: 20231009-jmp-into-reserved-fields-fc1a98a8e7dc
Best regards,
Comments
Hao Sun wrote: > Currently, we don't check if the branch-taken of a jump is reserved code of > ld_imm64. Instead, such a issue is captured in check_ld_imm(). The verifier > gives the following log in such case: > > func#0 @0 > 0: R1=ctx(off=0,imm=0) R10=fp0 > 0: (18) r4 = 0xffff888103436000 ; R4_w=map_ptr(off=0,ks=4,vs=128,imm=0) > 2: (18) r1 = 0x1d ; R1_w=29 > 4: (55) if r4 != 0x0 goto pc+4 ; R4_w=map_ptr(off=0,ks=4,vs=128,imm=0) > 5: (1c) w1 -= w1 ; R1_w=0 > 6: (18) r5 = 0x32 ; R5_w=50 > 8: (56) if w5 != 0xfffffff4 goto pc-2 > mark_precise: frame0: last_idx 8 first_idx 0 subseq_idx -1 > mark_precise: frame0: regs=r5 stack= before 6: (18) r5 = 0x32 > 7: R5_w=50 > 7: BUG_ld_00 > invalid BPF_LD_IMM insn > > Here the verifier rejects the program because it thinks insn at 7 is an > invalid BPF_LD_IMM, but such a error log is not accurate since the issue > is jumping to reserved code not because the program contains invalid insn. > Therefore, make the verifier check the jump target during check_cfg(). For > the same program, the verifier reports the following log: I think we at least would want a test case for this. Also how did you create this case? Is it just something you did manually and noticed a strange error? > > func#0 @0 > jump to reserved code from insn 8 to 7 > > --- > > > Signed-off-by: Hao Sun <sunhao.th@gmail.com> > --- > kernel/bpf/verifier.c | 7 +++++++ > 1 file changed, 7 insertions(+) > > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c > index eed7350e15f4..725ac0b464cf 100644 > --- a/kernel/bpf/verifier.c > +++ b/kernel/bpf/verifier.c > @@ -14980,6 +14980,7 @@ static int push_insn(int t, int w, int e, struct bpf_verifier_env *env, > { > int *insn_stack = env->cfg.insn_stack; > int *insn_state = env->cfg.insn_state; > + struct bpf_insn *insns = env->prog->insnsi; > > if (e == FALLTHROUGH && insn_state[t] >= (DISCOVERED | FALLTHROUGH)) > return DONE_EXPLORING; > @@ -14993,6 +14994,12 @@ static int push_insn(int t, int w, int e, struct bpf_verifier_env *env, > return -EINVAL; > } > > + if (e == BRANCH && insns[w].code == 0) { > + verbose_linfo(env, t, "%d", t); > + verbose(env, "jump to reserved code from insn %d to %d\n", t, w); > + return -EINVAL; > + } > + > if (e == BRANCH) { > /* mark branch target for state pruning */ > mark_prune_point(env, w); > > --- > base-commit: 3157b7ce14bbf468b0ca8613322a05c37b5ae25d > change-id: 20231009-jmp-into-reserved-fields-fc1a98a8e7dc > > Best regards, > -- > Hao Sun <sunhao.th@gmail.com> >
On 10/10/23 9:02 AM, John Fastabend wrote: > Hao Sun wrote: >> Currently, we don't check if the branch-taken of a jump is reserved code of >> ld_imm64. Instead, such a issue is captured in check_ld_imm(). The verifier >> gives the following log in such case: >> >> func#0 @0 >> 0: R1=ctx(off=0,imm=0) R10=fp0 >> 0: (18) r4 = 0xffff888103436000 ; R4_w=map_ptr(off=0,ks=4,vs=128,imm=0) >> 2: (18) r1 = 0x1d ; R1_w=29 >> 4: (55) if r4 != 0x0 goto pc+4 ; R4_w=map_ptr(off=0,ks=4,vs=128,imm=0) >> 5: (1c) w1 -= w1 ; R1_w=0 >> 6: (18) r5 = 0x32 ; R5_w=50 >> 8: (56) if w5 != 0xfffffff4 goto pc-2 >> mark_precise: frame0: last_idx 8 first_idx 0 subseq_idx -1 >> mark_precise: frame0: regs=r5 stack= before 6: (18) r5 = 0x32 >> 7: R5_w=50 >> 7: BUG_ld_00 >> invalid BPF_LD_IMM insn >> >> Here the verifier rejects the program because it thinks insn at 7 is an >> invalid BPF_LD_IMM, but such a error log is not accurate since the issue >> is jumping to reserved code not because the program contains invalid insn. >> Therefore, make the verifier check the jump target during check_cfg(). For >> the same program, the verifier reports the following log: > > I think we at least would want a test case for this. Also how did you create > this case? Is it just something you did manually and noticed a strange error? Curious as well. We do have test cases which try to jump into the middle of a double insn as can be seen that this patch breaks BPF CI with regards to log mismatch below (which still needs to be adapted, too). Either way, it probably doesn't hurt to also add the above snippet as a test. Hao, as I understand, the patch here is an usability improvement (not a fix per se) where we reject such cases earlier during cfg check rather than at a later point where we validate ld_imm instruction. Or are there cases you found which were not yet captured via current check_ld_imm()? test_verifier failure log : #458/u test1 ld_imm64 FAIL Unexpected verifier log! EXP: R1 pointer comparison RES: FAIL Unexpected error message! EXP: R1 pointer comparison RES: jump to reserved code from insn 0 to 2 verification time 22 usec stack depth 0 processed 0 insns (limit 1000000) max_states_per_insn 0 total_states 0 peak_states 0 mark_read 0 jump to reserved code from insn 0 to 2 verification time 22 usec stack depth 0 processed 0 insns (limit 1000000) max_states_per_insn 0 total_states 0 peak_states 0 mark_read 0 #458/p test1 ld_imm64 FAIL Unexpected verifier log! EXP: invalid BPF_LD_IMM insn RES: FAIL Unexpected error message! EXP: invalid BPF_LD_IMM insn RES: jump to reserved code from insn 0 to 2 verification time 9 usec stack depth 0 processed 0 insns (limit 1000000) max_states_per_insn 0 total_states 0 peak_states 0 mark_read 0 jump to reserved code from insn 0 to 2 verification time 9 usec stack depth 0 processed 0 insns (limit 1000000) max_states_per_insn 0 total_states 0 peak_states 0 mark_read 0 #459/u test2 ld_imm64 FAIL Unexpected verifier log! EXP: R1 pointer comparison RES: FAIL Unexpected error message! EXP: R1 pointer comparison RES: jump to reserved code from insn 0 to 2 verification time 11 usec stack depth 0 processed 0 insns (limit 1000000) max_states_per_insn 0 total_states 0 peak_states 0 mark_read 0 jump to reserved code from insn 0 to 2 verification time 11 usec stack depth 0 processed 0 insns (limit 1000000) max_states_per_insn 0 total_states 0 peak_states 0 mark_read 0 #459/p test2 ld_imm64 FAIL Unexpected verifier log! EXP: invalid BPF_LD_IMM insn RES: FAIL Unexpected error message! EXP: invalid BPF_LD_IMM insn RES: jump to reserved code from insn 0 to 2 verification time 8 usec stack depth 0 processed 0 insns (limit 1000000) max_states_per_insn 0 total_states 0 peak_states 0 mark_read 0 jump to reserved code from insn 0 to 2 verification time 8 usec stack depth 0 processed 0 insns (limit 1000000) max_states_per_insn 0 total_states 0 peak_states 0 mark_read 0 #460/u test3 ld_imm64 OK >> func#0 @0 >> jump to reserved code from insn 8 to 7 >> >> --- >> >> >> Signed-off-by: Hao Sun <sunhao.th@gmail.com> nit: This needs to be before the "---" line. >> --- >> kernel/bpf/verifier.c | 7 +++++++ >> 1 file changed, 7 insertions(+) >> >> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c >> index eed7350e15f4..725ac0b464cf 100644 >> --- a/kernel/bpf/verifier.c >> +++ b/kernel/bpf/verifier.c >> @@ -14980,6 +14980,7 @@ static int push_insn(int t, int w, int e, struct bpf_verifier_env *env, >> { >> int *insn_stack = env->cfg.insn_stack; >> int *insn_state = env->cfg.insn_state; >> + struct bpf_insn *insns = env->prog->insnsi; >> >> if (e == FALLTHROUGH && insn_state[t] >= (DISCOVERED | FALLTHROUGH)) >> return DONE_EXPLORING; >> @@ -14993,6 +14994,12 @@ static int push_insn(int t, int w, int e, struct bpf_verifier_env *env, >> return -EINVAL; >> } >> >> + if (e == BRANCH && insns[w].code == 0) { >> + verbose_linfo(env, t, "%d", t); >> + verbose(env, "jump to reserved code from insn %d to %d\n", t, w); >> + return -EINVAL; >> + } Other than that, lgtm. >> if (e == BRANCH) { >> /* mark branch target for state pruning */ >> mark_prune_point(env, w); >>
On Tue, Oct 10, 2023 at 10:33 AM Daniel Borkmann <daniel@iogearbox.net> wrote: > > On 10/10/23 9:02 AM, John Fastabend wrote: > > Hao Sun wrote: > >> Currently, we don't check if the branch-taken of a jump is reserved code of > >> ld_imm64. Instead, such a issue is captured in check_ld_imm(). The verifier > >> gives the following log in such case: > >> > >> func#0 @0 > >> 0: R1=ctx(off=0,imm=0) R10=fp0 > >> 0: (18) r4 = 0xffff888103436000 ; R4_w=map_ptr(off=0,ks=4,vs=128,imm=0) > >> 2: (18) r1 = 0x1d ; R1_w=29 > >> 4: (55) if r4 != 0x0 goto pc+4 ; R4_w=map_ptr(off=0,ks=4,vs=128,imm=0) > >> 5: (1c) w1 -= w1 ; R1_w=0 > >> 6: (18) r5 = 0x32 ; R5_w=50 > >> 8: (56) if w5 != 0xfffffff4 goto pc-2 > >> mark_precise: frame0: last_idx 8 first_idx 0 subseq_idx -1 > >> mark_precise: frame0: regs=r5 stack= before 6: (18) r5 = 0x32 > >> 7: R5_w=50 > >> 7: BUG_ld_00 > >> invalid BPF_LD_IMM insn > >> > >> Here the verifier rejects the program because it thinks insn at 7 is an > >> invalid BPF_LD_IMM, but such a error log is not accurate since the issue > >> is jumping to reserved code not because the program contains invalid insn. > >> Therefore, make the verifier check the jump target during check_cfg(). For > >> the same program, the verifier reports the following log: > > > > I think we at least would want a test case for this. Also how did you create > > this case? Is it just something you did manually and noticed a strange error? > > Curious as well. I just wrote a testing tool for the verifier, which uses a test oracle to capture incorrect verifier's states, capturing incorrect verifier logs is a bonus from this. The bug is captured during testing the testing tool :). I will publish the work when I think it's useful enough and ready. > > We do have test cases which try to jump into the middle of a double insn as can > be seen that this patch breaks BPF CI with regards to log mismatch below (which > still needs to be adapted, too). Either way, it probably doesn't hurt to also add > the above snippet as a test. > Will add a test case for this, and try to fix these broken tests, in patch v2. > Hao, as I understand, the patch here is an usability improvement (not a fix per se) > where we reject such cases earlier during cfg check rather than at a later point > where we validate ld_imm instruction. Or are there cases you found which were not > yet captured via current check_ld_imm()? > I regard this as a fix, because the verifier log is not correct, since the program does not contain any invalid ld_imm64 instructions in this case. I haven't met other cases not captured via check_ld_imm(), but somehow, I think we probably want to convert the check there as an internal bug, because we already have bpf_opcode_in_insntable() check in resolve_pseudo_ldimm64(). Once we meet invalid insn code here, then somewhere else in the verifier is probably wrong. But I'm not sure, maybe something like this: diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index eed7350e15f4..bed97de568a5 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -14532,8 +14532,8 @@ static int check_ld_imm(struct bpf_verifier_env *env, struct bpf_insn *insn) int err; if (BPF_SIZE(insn->code) != BPF_DW) { - verbose(env, "invalid BPF_LD_IMM insn\n"); - return -EINVAL; + verbose(env, "verifier internal bug, invalid BPF_LD_IMM\n"); + return -EFAULT; } if (insn->off != 0) { verbose(env, "BPF_LD_IMM64 uses reserved fields\n"); > test_verifier failure log : > > #458/u test1 ld_imm64 FAIL > Unexpected verifier log! > EXP: R1 pointer comparison > RES: > FAIL > Unexpected error message! > EXP: R1 pointer comparison > RES: jump to reserved code from insn 0 to 2 > verification time 22 usec > stack depth 0 > processed 0 insns (limit 1000000) max_states_per_insn 0 total_states 0 peak_states 0 mark_read 0 > > jump to reserved code from insn 0 to 2 > verification time 22 usec > stack depth 0 > processed 0 insns (limit 1000000) max_states_per_insn 0 total_states 0 peak_states 0 mark_read 0 > #458/p test1 ld_imm64 FAIL > Unexpected verifier log! > EXP: invalid BPF_LD_IMM insn > RES: > FAIL > Unexpected error message! > EXP: invalid BPF_LD_IMM insn > RES: jump to reserved code from insn 0 to 2 > verification time 9 usec > stack depth 0 > processed 0 insns (limit 1000000) max_states_per_insn 0 total_states 0 peak_states 0 mark_read 0 > > jump to reserved code from insn 0 to 2 > verification time 9 usec > stack depth 0 > processed 0 insns (limit 1000000) max_states_per_insn 0 total_states 0 peak_states 0 mark_read 0 > #459/u test2 ld_imm64 FAIL > Unexpected verifier log! > EXP: R1 pointer comparison > RES: > FAIL > Unexpected error message! > EXP: R1 pointer comparison > RES: jump to reserved code from insn 0 to 2 > verification time 11 usec > stack depth 0 > processed 0 insns (limit 1000000) max_states_per_insn 0 total_states 0 peak_states 0 mark_read 0 > > jump to reserved code from insn 0 to 2 > verification time 11 usec > stack depth 0 > processed 0 insns (limit 1000000) max_states_per_insn 0 total_states 0 peak_states 0 mark_read 0 > #459/p test2 ld_imm64 FAIL > Unexpected verifier log! > EXP: invalid BPF_LD_IMM insn > RES: > FAIL > Unexpected error message! > EXP: invalid BPF_LD_IMM insn > RES: jump to reserved code from insn 0 to 2 > verification time 8 usec > stack depth 0 > processed 0 insns (limit 1000000) max_states_per_insn 0 total_states 0 peak_states 0 mark_read 0 > > jump to reserved code from insn 0 to 2 > verification time 8 usec > stack depth 0 > processed 0 insns (limit 1000000) max_states_per_insn 0 total_states 0 peak_states 0 mark_read 0 > #460/u test3 ld_imm64 OK > > >> func#0 @0 > >> jump to reserved code from insn 8 to 7 > >> > >> --- > >> > >> > >> Signed-off-by: Hao Sun <sunhao.th@gmail.com> > > nit: This needs to be before the "---" line. > Noted. > >> --- > >> kernel/bpf/verifier.c | 7 +++++++ > >> 1 file changed, 7 insertions(+) > >> > >> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c > >> index eed7350e15f4..725ac0b464cf 100644 > >> --- a/kernel/bpf/verifier.c > >> +++ b/kernel/bpf/verifier.c > >> @@ -14980,6 +14980,7 @@ static int push_insn(int t, int w, int e, struct bpf_verifier_env *env, > >> { > >> int *insn_stack = env->cfg.insn_stack; > >> int *insn_state = env->cfg.insn_state; > >> + struct bpf_insn *insns = env->prog->insnsi; > >> > >> if (e == FALLTHROUGH && insn_state[t] >= (DISCOVERED | FALLTHROUGH)) > >> return DONE_EXPLORING; > >> @@ -14993,6 +14994,12 @@ static int push_insn(int t, int w, int e, struct bpf_verifier_env *env, > >> return -EINVAL; > >> } > >> > >> + if (e == BRANCH && insns[w].code == 0) { > >> + verbose_linfo(env, t, "%d", t); > >> + verbose(env, "jump to reserved code from insn %d to %d\n", t, w); > >> + return -EINVAL; > >> + } > > Other than that, lgtm. > > >> if (e == BRANCH) { > >> /* mark branch target for state pruning */ > >> mark_prune_point(env, w); > >>
On 10/10/23 11:17 AM, Hao Sun wrote: [...] > I regard this as a fix, because the verifier log is not correct, since > the program does > not contain any invalid ld_imm64 instructions in this case. > > I haven't met other cases not captured via check_ld_imm(), but somehow, I think > we probably want to convert the check there as an internal bug, > because we already > have bpf_opcode_in_insntable() check in resolve_pseudo_ldimm64(). Once we meet > invalid insn code here, then somewhere else in the verifier is > probably wrong. But > I'm not sure, maybe something like this: Makes sense, you could probably add this into your series as a separate commit. > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c > index eed7350e15f4..bed97de568a5 100644 > --- a/kernel/bpf/verifier.c > +++ b/kernel/bpf/verifier.c > @@ -14532,8 +14532,8 @@ static int check_ld_imm(struct > bpf_verifier_env *env, struct bpf_insn *insn) > int err; > > if (BPF_SIZE(insn->code) != BPF_DW) { > - verbose(env, "invalid BPF_LD_IMM insn\n"); > - return -EINVAL; > + verbose(env, "verifier internal bug, invalid BPF_LD_IMM\n"); If so please stick to the common style as we have in other locations: verbose(env, "verifier internal error: <xyz>\n"); > + return -EFAULT; > } > if (insn->off != 0) { > verbose(env, "BPF_LD_IMM64 uses reserved fields\n"); >
On Tue, Oct 10, 2023 at 1:33 AM Daniel Borkmann <daniel@iogearbox.net> wrote: > > On 10/10/23 9:02 AM, John Fastabend wrote: > > Hao Sun wrote: > >> Currently, we don't check if the branch-taken of a jump is reserved code of > >> ld_imm64. Instead, such a issue is captured in check_ld_imm(). The verifier > >> gives the following log in such case: > >> > >> func#0 @0 > >> 0: R1=ctx(off=0,imm=0) R10=fp0 > >> 0: (18) r4 = 0xffff888103436000 ; R4_w=map_ptr(off=0,ks=4,vs=128,imm=0) > >> 2: (18) r1 = 0x1d ; R1_w=29 > >> 4: (55) if r4 != 0x0 goto pc+4 ; R4_w=map_ptr(off=0,ks=4,vs=128,imm=0) > >> 5: (1c) w1 -= w1 ; R1_w=0 > >> 6: (18) r5 = 0x32 ; R5_w=50 > >> 8: (56) if w5 != 0xfffffff4 goto pc-2 > >> mark_precise: frame0: last_idx 8 first_idx 0 subseq_idx -1 > >> mark_precise: frame0: regs=r5 stack= before 6: (18) r5 = 0x32 > >> 7: R5_w=50 > >> 7: BUG_ld_00 > >> invalid BPF_LD_IMM insn > >> > >> Here the verifier rejects the program because it thinks insn at 7 is an > >> invalid BPF_LD_IMM, but such a error log is not accurate since the issue > >> is jumping to reserved code not because the program contains invalid insn. > >> Therefore, make the verifier check the jump target during check_cfg(). For > >> the same program, the verifier reports the following log: > > > > I think we at least would want a test case for this. Also how did you create > > this case? Is it just something you did manually and noticed a strange error? > > Curious as well. > > We do have test cases which try to jump into the middle of a double insn as can > be seen that this patch breaks BPF CI with regards to log mismatch below (which > still needs to be adapted, too). Either way, it probably doesn't hurt to also add > the above snippet as a test. > > Hao, as I understand, the patch here is an usability improvement (not a fix per se) > where we reject such cases earlier during cfg check rather than at a later point > where we validate ld_imm instruction. Or are there cases you found which were not > yet captured via current check_ld_imm()? > > test_verifier failure log : > > #458/u test1 ld_imm64 FAIL > Unexpected verifier log! > EXP: R1 pointer comparison > RES: > FAIL > Unexpected error message! > EXP: R1 pointer comparison > RES: jump to reserved code from insn 0 to 2 > verification time 22 usec > stack depth 0 > processed 0 insns (limit 1000000) max_states_per_insn 0 total_states 0 peak_states 0 mark_read 0 > > jump to reserved code from insn 0 to 2 > verification time 22 usec > stack depth 0 > processed 0 insns (limit 1000000) max_states_per_insn 0 total_states 0 peak_states 0 mark_read 0 > #458/p test1 ld_imm64 FAIL > Unexpected verifier log! > EXP: invalid BPF_LD_IMM insn > RES: > FAIL > Unexpected error message! > EXP: invalid BPF_LD_IMM insn > RES: jump to reserved code from insn 0 to 2 > verification time 9 usec > stack depth 0 > processed 0 insns (limit 1000000) max_states_per_insn 0 total_states 0 peak_states 0 mark_read 0 > > jump to reserved code from insn 0 to 2 > verification time 9 usec > stack depth 0 > processed 0 insns (limit 1000000) max_states_per_insn 0 total_states 0 peak_states 0 mark_read 0 > #459/u test2 ld_imm64 FAIL > Unexpected verifier log! > EXP: R1 pointer comparison > RES: > FAIL > Unexpected error message! > EXP: R1 pointer comparison > RES: jump to reserved code from insn 0 to 2 > verification time 11 usec > stack depth 0 > processed 0 insns (limit 1000000) max_states_per_insn 0 total_states 0 peak_states 0 mark_read 0 > > jump to reserved code from insn 0 to 2 > verification time 11 usec > stack depth 0 > processed 0 insns (limit 1000000) max_states_per_insn 0 total_states 0 peak_states 0 mark_read 0 > #459/p test2 ld_imm64 FAIL > Unexpected verifier log! > EXP: invalid BPF_LD_IMM insn > RES: > FAIL > Unexpected error message! > EXP: invalid BPF_LD_IMM insn > RES: jump to reserved code from insn 0 to 2 > verification time 8 usec > stack depth 0 > processed 0 insns (limit 1000000) max_states_per_insn 0 total_states 0 peak_states 0 mark_read 0 > > jump to reserved code from insn 0 to 2 > verification time 8 usec > stack depth 0 > processed 0 insns (limit 1000000) max_states_per_insn 0 total_states 0 peak_states 0 mark_read 0 > #460/u test3 ld_imm64 OK > > >> func#0 @0 > >> jump to reserved code from insn 8 to 7 > >> > >> --- > >> > >> > >> Signed-off-by: Hao Sun <sunhao.th@gmail.com> > > nit: This needs to be before the "---" line. > > >> --- > >> kernel/bpf/verifier.c | 7 +++++++ > >> 1 file changed, 7 insertions(+) > >> > >> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c > >> index eed7350e15f4..725ac0b464cf 100644 > >> --- a/kernel/bpf/verifier.c > >> +++ b/kernel/bpf/verifier.c > >> @@ -14980,6 +14980,7 @@ static int push_insn(int t, int w, int e, struct bpf_verifier_env *env, > >> { > >> int *insn_stack = env->cfg.insn_stack; > >> int *insn_state = env->cfg.insn_state; > >> + struct bpf_insn *insns = env->prog->insnsi; > >> > >> if (e == FALLTHROUGH && insn_state[t] >= (DISCOVERED | FALLTHROUGH)) > >> return DONE_EXPLORING; > >> @@ -14993,6 +14994,12 @@ static int push_insn(int t, int w, int e, struct bpf_verifier_env *env, > >> return -EINVAL; > >> } > >> > >> + if (e == BRANCH && insns[w].code == 0) { > >> + verbose_linfo(env, t, "%d", t); > >> + verbose(env, "jump to reserved code from insn %d to %d\n", t, w); > >> + return -EINVAL; > >> + } > > Other than that, lgtm. We do rely quite a lot on verifier not complaining eagerly about some potentially invalid instructions if it's provable that some portion of the code won't ever be reached (think using .rodata variables for feature gating, poisoning intructions due to failed CO-RE relocation, which libbpf does actively, except it's using a call to non-existing helper). As such, check_cfg() is a wrong place to do such validity checks because some of the branches might never be run and validated in practice. This seems like a pretty obscure case of fuzzer generated test with random jumps into the middle of ldimm64 instruction. I think the tool should be able to avoid this or handle verifier log just fine in such situations. On the other hand, valid code generated by compilers will never have such jumps. So perhaps we can improve existing "invalid BPF_LD_IMM insn" message, but let's not teach check_cfg() more checks than necessary? > > >> if (e == BRANCH) { > >> /* mark branch target for state pruning */ > >> mark_prune_point(env, w); > >> >
On Wed, Oct 11, 2023 at 4:42 AM Andrii Nakryiko <andrii.nakryiko@gmail.com> wrote: > > On Tue, Oct 10, 2023 at 1:33 AM Daniel Borkmann <daniel@iogearbox.net> wrote: > > > > On 10/10/23 9:02 AM, John Fastabend wrote: > > > Hao Sun wrote: > > >> Currently, we don't check if the branch-taken of a jump is reserved code of > > >> ld_imm64. Instead, such a issue is captured in check_ld_imm(). The verifier > > >> gives the following log in such case: > > >> > > >> func#0 @0 > > >> 0: R1=ctx(off=0,imm=0) R10=fp0 > > >> 0: (18) r4 = 0xffff888103436000 ; R4_w=map_ptr(off=0,ks=4,vs=128,imm=0) > > >> 2: (18) r1 = 0x1d ; R1_w=29 > > >> 4: (55) if r4 != 0x0 goto pc+4 ; R4_w=map_ptr(off=0,ks=4,vs=128,imm=0) > > >> 5: (1c) w1 -= w1 ; R1_w=0 > > >> 6: (18) r5 = 0x32 ; R5_w=50 > > >> 8: (56) if w5 != 0xfffffff4 goto pc-2 > > >> mark_precise: frame0: last_idx 8 first_idx 0 subseq_idx -1 > > >> mark_precise: frame0: regs=r5 stack= before 6: (18) r5 = 0x32 > > >> 7: R5_w=50 > > >> 7: BUG_ld_00 > > >> invalid BPF_LD_IMM insn > > >> > > >> Here the verifier rejects the program because it thinks insn at 7 is an > > >> invalid BPF_LD_IMM, but such a error log is not accurate since the issue > > >> is jumping to reserved code not because the program contains invalid insn. > > >> Therefore, make the verifier check the jump target during check_cfg(). For > > >> the same program, the verifier reports the following log: > > > > > > I think we at least would want a test case for this. Also how did you create > > > this case? Is it just something you did manually and noticed a strange error? > > > > Curious as well. > > > > We do have test cases which try to jump into the middle of a double insn as can > > be seen that this patch breaks BPF CI with regards to log mismatch below (which > > still needs to be adapted, too). Either way, it probably doesn't hurt to also add > > the above snippet as a test. > > > > Hao, as I understand, the patch here is an usability improvement (not a fix per se) > > where we reject such cases earlier during cfg check rather than at a later point > > where we validate ld_imm instruction. Or are there cases you found which were not > > yet captured via current check_ld_imm()? > > > > test_verifier failure log : > > > > #458/u test1 ld_imm64 FAIL > > Unexpected verifier log! > > EXP: R1 pointer comparison > > RES: > > FAIL > > Unexpected error message! > > EXP: R1 pointer comparison > > RES: jump to reserved code from insn 0 to 2 > > verification time 22 usec > > stack depth 0 > > processed 0 insns (limit 1000000) max_states_per_insn 0 total_states 0 peak_states 0 mark_read 0 > > > > jump to reserved code from insn 0 to 2 > > verification time 22 usec > > stack depth 0 > > processed 0 insns (limit 1000000) max_states_per_insn 0 total_states 0 peak_states 0 mark_read 0 > > #458/p test1 ld_imm64 FAIL > > Unexpected verifier log! > > EXP: invalid BPF_LD_IMM insn > > RES: > > FAIL > > Unexpected error message! > > EXP: invalid BPF_LD_IMM insn > > RES: jump to reserved code from insn 0 to 2 > > verification time 9 usec > > stack depth 0 > > processed 0 insns (limit 1000000) max_states_per_insn 0 total_states 0 peak_states 0 mark_read 0 > > > > jump to reserved code from insn 0 to 2 > > verification time 9 usec > > stack depth 0 > > processed 0 insns (limit 1000000) max_states_per_insn 0 total_states 0 peak_states 0 mark_read 0 > > #459/u test2 ld_imm64 FAIL > > Unexpected verifier log! > > EXP: R1 pointer comparison > > RES: > > FAIL > > Unexpected error message! > > EXP: R1 pointer comparison > > RES: jump to reserved code from insn 0 to 2 > > verification time 11 usec > > stack depth 0 > > processed 0 insns (limit 1000000) max_states_per_insn 0 total_states 0 peak_states 0 mark_read 0 > > > > jump to reserved code from insn 0 to 2 > > verification time 11 usec > > stack depth 0 > > processed 0 insns (limit 1000000) max_states_per_insn 0 total_states 0 peak_states 0 mark_read 0 > > #459/p test2 ld_imm64 FAIL > > Unexpected verifier log! > > EXP: invalid BPF_LD_IMM insn > > RES: > > FAIL > > Unexpected error message! > > EXP: invalid BPF_LD_IMM insn > > RES: jump to reserved code from insn 0 to 2 > > verification time 8 usec > > stack depth 0 > > processed 0 insns (limit 1000000) max_states_per_insn 0 total_states 0 peak_states 0 mark_read 0 > > > > jump to reserved code from insn 0 to 2 > > verification time 8 usec > > stack depth 0 > > processed 0 insns (limit 1000000) max_states_per_insn 0 total_states 0 peak_states 0 mark_read 0 > > #460/u test3 ld_imm64 OK > > > > >> func#0 @0 > > >> jump to reserved code from insn 8 to 7 > > >> > > >> --- > > >> > > >> > > >> Signed-off-by: Hao Sun <sunhao.th@gmail.com> > > > > nit: This needs to be before the "---" line. > > > > >> --- > > >> kernel/bpf/verifier.c | 7 +++++++ > > >> 1 file changed, 7 insertions(+) > > >> > > >> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c > > >> index eed7350e15f4..725ac0b464cf 100644 > > >> --- a/kernel/bpf/verifier.c > > >> +++ b/kernel/bpf/verifier.c > > >> @@ -14980,6 +14980,7 @@ static int push_insn(int t, int w, int e, struct bpf_verifier_env *env, > > >> { > > >> int *insn_stack = env->cfg.insn_stack; > > >> int *insn_state = env->cfg.insn_state; > > >> + struct bpf_insn *insns = env->prog->insnsi; > > >> > > >> if (e == FALLTHROUGH && insn_state[t] >= (DISCOVERED | FALLTHROUGH)) > > >> return DONE_EXPLORING; > > >> @@ -14993,6 +14994,12 @@ static int push_insn(int t, int w, int e, struct bpf_verifier_env *env, > > >> return -EINVAL; > > >> } > > >> > > >> + if (e == BRANCH && insns[w].code == 0) { > > >> + verbose_linfo(env, t, "%d", t); > > >> + verbose(env, "jump to reserved code from insn %d to %d\n", t, w); > > >> + return -EINVAL; > > >> + } > > > > Other than that, lgtm. > > We do rely quite a lot on verifier not complaining eagerly about some > potentially invalid instructions if it's provable that some portion of > the code won't ever be reached (think using .rodata variables for > feature gating, poisoning intructions due to failed CO-RE relocation, > which libbpf does actively, except it's using a call to non-existing > helper). As such, check_cfg() is a wrong place to do such validity > checks because some of the branches might never be run and validated > in practice. > Don't really agree. Jump to the middle of ld_imm64 is just like jumping out of bounds, both break the CFG integrity immediately. For those apparently incorrect jumps, rejecting early makes everything simple; otherwise, we probably need some rewrite in the end. Also, as you mentioned, libbpf relies on non-existing helpers, not jump to the middle of ld_imm64. It seems better and easier to not leave this hole. > This seems like a pretty obscure case of fuzzer generated test with > random jumps into the middle of ldimm64 instruction. I think the tool > should be able to avoid this or handle verifier log just fine in such > situations. On the other hand, valid code generated by compilers will > never have such jumps. > > So perhaps we can improve existing "invalid BPF_LD_IMM insn" message, > but let's not teach check_cfg() more checks than necessary? > Improving that `invalid BPF_LD_IMM` log does not solve the problem, the issue here is an invalid jump. Also, there could be various causes that make the verifier see an invalid BPF_LD_IMM in check_ld_imm(). > > > > >> if (e == BRANCH) { > > >> /* mark branch target for state pruning */ > > >> mark_prune_point(env, w); > > >> > >
On 10/11/23 8:46 AM, Hao Sun wrote: > On Wed, Oct 11, 2023 at 4:42 AM Andrii Nakryiko > <andrii.nakryiko@gmail.com> wrote: >> On Tue, Oct 10, 2023 at 1:33 AM Daniel Borkmann <daniel@iogearbox.net> wrote: >>> On 10/10/23 9:02 AM, John Fastabend wrote: >>>> Hao Sun wrote: >>>>> Currently, we don't check if the branch-taken of a jump is reserved code of >>>>> ld_imm64. Instead, such a issue is captured in check_ld_imm(). The verifier >>>>> gives the following log in such case: >>>>> >>>>> func#0 @0 >>>>> 0: R1=ctx(off=0,imm=0) R10=fp0 >>>>> 0: (18) r4 = 0xffff888103436000 ; R4_w=map_ptr(off=0,ks=4,vs=128,imm=0) >>>>> 2: (18) r1 = 0x1d ; R1_w=29 >>>>> 4: (55) if r4 != 0x0 goto pc+4 ; R4_w=map_ptr(off=0,ks=4,vs=128,imm=0) >>>>> 5: (1c) w1 -= w1 ; R1_w=0 >>>>> 6: (18) r5 = 0x32 ; R5_w=50 >>>>> 8: (56) if w5 != 0xfffffff4 goto pc-2 >>>>> mark_precise: frame0: last_idx 8 first_idx 0 subseq_idx -1 >>>>> mark_precise: frame0: regs=r5 stack= before 6: (18) r5 = 0x32 >>>>> 7: R5_w=50 >>>>> 7: BUG_ld_00 >>>>> invalid BPF_LD_IMM insn >>>>> >>>>> Here the verifier rejects the program because it thinks insn at 7 is an >>>>> invalid BPF_LD_IMM, but such a error log is not accurate since the issue >>>>> is jumping to reserved code not because the program contains invalid insn. >>>>> Therefore, make the verifier check the jump target during check_cfg(). For >>>>> the same program, the verifier reports the following log: >>>> >>>> I think we at least would want a test case for this. Also how did you create >>>> this case? Is it just something you did manually and noticed a strange error? >>> >>> Curious as well. >>> >>> We do have test cases which try to jump into the middle of a double insn as can >>> be seen that this patch breaks BPF CI with regards to log mismatch below (which >>> still needs to be adapted, too). Either way, it probably doesn't hurt to also add >>> the above snippet as a test. >>> >>> Hao, as I understand, the patch here is an usability improvement (not a fix per se) >>> where we reject such cases earlier during cfg check rather than at a later point >>> where we validate ld_imm instruction. Or are there cases you found which were not >>> yet captured via current check_ld_imm()? >>> >>> test_verifier failure log : >>> >>> #458/u test1 ld_imm64 FAIL >>> Unexpected verifier log! >>> EXP: R1 pointer comparison >>> RES: >>> FAIL >>> Unexpected error message! >>> EXP: R1 pointer comparison >>> RES: jump to reserved code from insn 0 to 2 >>> verification time 22 usec >>> stack depth 0 >>> processed 0 insns (limit 1000000) max_states_per_insn 0 total_states 0 peak_states 0 mark_read 0 >>> >>> jump to reserved code from insn 0 to 2 >>> verification time 22 usec >>> stack depth 0 >>> processed 0 insns (limit 1000000) max_states_per_insn 0 total_states 0 peak_states 0 mark_read 0 >>> #458/p test1 ld_imm64 FAIL >>> Unexpected verifier log! >>> EXP: invalid BPF_LD_IMM insn >>> RES: >>> FAIL >>> Unexpected error message! >>> EXP: invalid BPF_LD_IMM insn >>> RES: jump to reserved code from insn 0 to 2 >>> verification time 9 usec >>> stack depth 0 >>> processed 0 insns (limit 1000000) max_states_per_insn 0 total_states 0 peak_states 0 mark_read 0 >>> >>> jump to reserved code from insn 0 to 2 >>> verification time 9 usec >>> stack depth 0 >>> processed 0 insns (limit 1000000) max_states_per_insn 0 total_states 0 peak_states 0 mark_read 0 >>> #459/u test2 ld_imm64 FAIL >>> Unexpected verifier log! >>> EXP: R1 pointer comparison >>> RES: >>> FAIL >>> Unexpected error message! >>> EXP: R1 pointer comparison >>> RES: jump to reserved code from insn 0 to 2 >>> verification time 11 usec >>> stack depth 0 >>> processed 0 insns (limit 1000000) max_states_per_insn 0 total_states 0 peak_states 0 mark_read 0 >>> >>> jump to reserved code from insn 0 to 2 >>> verification time 11 usec >>> stack depth 0 >>> processed 0 insns (limit 1000000) max_states_per_insn 0 total_states 0 peak_states 0 mark_read 0 >>> #459/p test2 ld_imm64 FAIL >>> Unexpected verifier log! >>> EXP: invalid BPF_LD_IMM insn >>> RES: >>> FAIL >>> Unexpected error message! >>> EXP: invalid BPF_LD_IMM insn >>> RES: jump to reserved code from insn 0 to 2 >>> verification time 8 usec >>> stack depth 0 >>> processed 0 insns (limit 1000000) max_states_per_insn 0 total_states 0 peak_states 0 mark_read 0 >>> >>> jump to reserved code from insn 0 to 2 >>> verification time 8 usec >>> stack depth 0 >>> processed 0 insns (limit 1000000) max_states_per_insn 0 total_states 0 peak_states 0 mark_read 0 >>> #460/u test3 ld_imm64 OK >>> >>>>> func#0 @0 >>>>> jump to reserved code from insn 8 to 7 >>>>> >>>>> Signed-off-by: Hao Sun <sunhao.th@gmail.com> >>> >>> nit: This needs to be before the "---" line. >>> >>>>> --- >>>>> kernel/bpf/verifier.c | 7 +++++++ >>>>> 1 file changed, 7 insertions(+) >>>>> >>>>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c >>>>> index eed7350e15f4..725ac0b464cf 100644 >>>>> --- a/kernel/bpf/verifier.c >>>>> +++ b/kernel/bpf/verifier.c >>>>> @@ -14980,6 +14980,7 @@ static int push_insn(int t, int w, int e, struct bpf_verifier_env *env, >>>>> { >>>>> int *insn_stack = env->cfg.insn_stack; >>>>> int *insn_state = env->cfg.insn_state; >>>>> + struct bpf_insn *insns = env->prog->insnsi; >>>>> >>>>> if (e == FALLTHROUGH && insn_state[t] >= (DISCOVERED | FALLTHROUGH)) >>>>> return DONE_EXPLORING; >>>>> @@ -14993,6 +14994,12 @@ static int push_insn(int t, int w, int e, struct bpf_verifier_env *env, >>>>> return -EINVAL; >>>>> } >>>>> >>>>> + if (e == BRANCH && insns[w].code == 0) { >>>>> + verbose_linfo(env, t, "%d", t); >>>>> + verbose(env, "jump to reserved code from insn %d to %d\n", t, w); >>>>> + return -EINVAL; >>>>> + } >>> >>> Other than that, lgtm. >> >> We do rely quite a lot on verifier not complaining eagerly about some >> potentially invalid instructions if it's provable that some portion of >> the code won't ever be reached (think using .rodata variables for >> feature gating, poisoning intructions due to failed CO-RE relocation, >> which libbpf does actively, except it's using a call to non-existing >> helper). As such, check_cfg() is a wrong place to do such validity >> checks because some of the branches might never be run and validated >> in practice. > > Don't really agree. Jump to the middle of ld_imm64 is just like jumping > out of bounds, both break the CFG integrity immediately. For those > apparently incorrect jumps, rejecting early makes everything simple; > otherwise, we probably need some rewrite in the end. Could you elaborate on the 'breaking CFG integrity immediately'? This was what I was trying to gather earlier with log improvement vs actual fix. Do you mean /potentially/ breaking CFG integrity, if, say, we had a double insn jump in future and there is a back-jump to the 2nd part of the insn? > Also, as you mentioned, libbpf relies on non-existing helpers, not jump > to the middle of ld_imm64. It seems better and easier to not leave this > hole. Thanks, Daniel
On Wed, Oct 11, 2023 at 4:50 PM Daniel Borkmann <daniel@iogearbox.net> wrote: > > On 10/11/23 8:46 AM, Hao Sun wrote: > > On Wed, Oct 11, 2023 at 4:42 AM Andrii Nakryiko > > <andrii.nakryiko@gmail.com> wrote: > >> On Tue, Oct 10, 2023 at 1:33 AM Daniel Borkmann <daniel@iogearbox.net> wrote: > >>> On 10/10/23 9:02 AM, John Fastabend wrote: > >>>> Hao Sun wrote: > >>>>> Currently, we don't check if the branch-taken of a jump is reserved code of > >>>>> ld_imm64. Instead, such a issue is captured in check_ld_imm(). The verifier > >>>>> gives the following log in such case: > >>>>> > >>>>> func#0 @0 > >>>>> 0: R1=ctx(off=0,imm=0) R10=fp0 > >>>>> 0: (18) r4 = 0xffff888103436000 ; R4_w=map_ptr(off=0,ks=4,vs=128,imm=0) > >>>>> 2: (18) r1 = 0x1d ; R1_w=29 > >>>>> 4: (55) if r4 != 0x0 goto pc+4 ; R4_w=map_ptr(off=0,ks=4,vs=128,imm=0) > >>>>> 5: (1c) w1 -= w1 ; R1_w=0 > >>>>> 6: (18) r5 = 0x32 ; R5_w=50 > >>>>> 8: (56) if w5 != 0xfffffff4 goto pc-2 > >>>>> mark_precise: frame0: last_idx 8 first_idx 0 subseq_idx -1 > >>>>> mark_precise: frame0: regs=r5 stack= before 6: (18) r5 = 0x32 > >>>>> 7: R5_w=50 > >>>>> 7: BUG_ld_00 > >>>>> invalid BPF_LD_IMM insn > >>>>> > >>>>> Here the verifier rejects the program because it thinks insn at 7 is an > >>>>> invalid BPF_LD_IMM, but such a error log is not accurate since the issue > >>>>> is jumping to reserved code not because the program contains invalid insn. > >>>>> Therefore, make the verifier check the jump target during check_cfg(). For > >>>>> the same program, the verifier reports the following log: > >>>> > >>>> I think we at least would want a test case for this. Also how did you create > >>>> this case? Is it just something you did manually and noticed a strange error? > >>> > >>> Curious as well. > >>> > >>> We do have test cases which try to jump into the middle of a double insn as can > >>> be seen that this patch breaks BPF CI with regards to log mismatch below (which > >>> still needs to be adapted, too). Either way, it probably doesn't hurt to also add > >>> the above snippet as a test. > >>> > >>> Hao, as I understand, the patch here is an usability improvement (not a fix per se) > >>> where we reject such cases earlier during cfg check rather than at a later point > >>> where we validate ld_imm instruction. Or are there cases you found which were not > >>> yet captured via current check_ld_imm()? > >>> > >>> test_verifier failure log : > >>> > >>> #458/u test1 ld_imm64 FAIL > >>> Unexpected verifier log! > >>> EXP: R1 pointer comparison > >>> RES: > >>> FAIL > >>> Unexpected error message! > >>> EXP: R1 pointer comparison > >>> RES: jump to reserved code from insn 0 to 2 > >>> verification time 22 usec > >>> stack depth 0 > >>> processed 0 insns (limit 1000000) max_states_per_insn 0 total_states 0 peak_states 0 mark_read 0 > >>> > >>> jump to reserved code from insn 0 to 2 > >>> verification time 22 usec > >>> stack depth 0 > >>> processed 0 insns (limit 1000000) max_states_per_insn 0 total_states 0 peak_states 0 mark_read 0 > >>> #458/p test1 ld_imm64 FAIL > >>> Unexpected verifier log! > >>> EXP: invalid BPF_LD_IMM insn > >>> RES: > >>> FAIL > >>> Unexpected error message! > >>> EXP: invalid BPF_LD_IMM insn > >>> RES: jump to reserved code from insn 0 to 2 > >>> verification time 9 usec > >>> stack depth 0 > >>> processed 0 insns (limit 1000000) max_states_per_insn 0 total_states 0 peak_states 0 mark_read 0 > >>> > >>> jump to reserved code from insn 0 to 2 > >>> verification time 9 usec > >>> stack depth 0 > >>> processed 0 insns (limit 1000000) max_states_per_insn 0 total_states 0 peak_states 0 mark_read 0 > >>> #459/u test2 ld_imm64 FAIL > >>> Unexpected verifier log! > >>> EXP: R1 pointer comparison > >>> RES: > >>> FAIL > >>> Unexpected error message! > >>> EXP: R1 pointer comparison > >>> RES: jump to reserved code from insn 0 to 2 > >>> verification time 11 usec > >>> stack depth 0 > >>> processed 0 insns (limit 1000000) max_states_per_insn 0 total_states 0 peak_states 0 mark_read 0 > >>> > >>> jump to reserved code from insn 0 to 2 > >>> verification time 11 usec > >>> stack depth 0 > >>> processed 0 insns (limit 1000000) max_states_per_insn 0 total_states 0 peak_states 0 mark_read 0 > >>> #459/p test2 ld_imm64 FAIL > >>> Unexpected verifier log! > >>> EXP: invalid BPF_LD_IMM insn > >>> RES: > >>> FAIL > >>> Unexpected error message! > >>> EXP: invalid BPF_LD_IMM insn > >>> RES: jump to reserved code from insn 0 to 2 > >>> verification time 8 usec > >>> stack depth 0 > >>> processed 0 insns (limit 1000000) max_states_per_insn 0 total_states 0 peak_states 0 mark_read 0 > >>> > >>> jump to reserved code from insn 0 to 2 > >>> verification time 8 usec > >>> stack depth 0 > >>> processed 0 insns (limit 1000000) max_states_per_insn 0 total_states 0 peak_states 0 mark_read 0 > >>> #460/u test3 ld_imm64 OK > >>> > >>>>> func#0 @0 > >>>>> jump to reserved code from insn 8 to 7 > >>>>> > >>>>> Signed-off-by: Hao Sun <sunhao.th@gmail.com> > >>> > >>> nit: This needs to be before the "---" line. > >>> > >>>>> --- > >>>>> kernel/bpf/verifier.c | 7 +++++++ > >>>>> 1 file changed, 7 insertions(+) > >>>>> > >>>>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c > >>>>> index eed7350e15f4..725ac0b464cf 100644 > >>>>> --- a/kernel/bpf/verifier.c > >>>>> +++ b/kernel/bpf/verifier.c > >>>>> @@ -14980,6 +14980,7 @@ static int push_insn(int t, int w, int e, struct bpf_verifier_env *env, > >>>>> { > >>>>> int *insn_stack = env->cfg.insn_stack; > >>>>> int *insn_state = env->cfg.insn_state; > >>>>> + struct bpf_insn *insns = env->prog->insnsi; > >>>>> > >>>>> if (e == FALLTHROUGH && insn_state[t] >= (DISCOVERED | FALLTHROUGH)) > >>>>> return DONE_EXPLORING; > >>>>> @@ -14993,6 +14994,12 @@ static int push_insn(int t, int w, int e, struct bpf_verifier_env *env, > >>>>> return -EINVAL; > >>>>> } > >>>>> > >>>>> + if (e == BRANCH && insns[w].code == 0) { > >>>>> + verbose_linfo(env, t, "%d", t); > >>>>> + verbose(env, "jump to reserved code from insn %d to %d\n", t, w); > >>>>> + return -EINVAL; > >>>>> + } > >>> > >>> Other than that, lgtm. > >> > >> We do rely quite a lot on verifier not complaining eagerly about some > >> potentially invalid instructions if it's provable that some portion of > >> the code won't ever be reached (think using .rodata variables for > >> feature gating, poisoning intructions due to failed CO-RE relocation, > >> which libbpf does actively, except it's using a call to non-existing > >> helper). As such, check_cfg() is a wrong place to do such validity > >> checks because some of the branches might never be run and validated > >> in practice. > > > > Don't really agree. Jump to the middle of ld_imm64 is just like jumping > > out of bounds, both break the CFG integrity immediately. For those > > apparently incorrect jumps, rejecting early makes everything simple; > > otherwise, we probably need some rewrite in the end. > > Could you elaborate on the 'breaking CFG integrity immediately'? This was > what I was trying to gather earlier with log improvement vs actual fix. > > Do you mean /potentially/ breaking CFG integrity, if, say, we had a double > insn jump in future and there is a back-jump to the 2nd part of the insn? > I mean jumping to the middle of ld_imm64 is similar to jumping out-of-bound, both are CFG-related issues and can be handled early in one place. For the case you mentioned, the current code would handle such an issue in check_ld_imm64(), and again gives "BAD_LD_IMM" log, which is strange. > > Also, as you mentioned, libbpf relies on non-existing helpers, not jump > > to the middle of ld_imm64. It seems better and easier to not leave this > > hole. > > Thanks, > Daniel
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index eed7350e15f4..725ac0b464cf 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -14980,6 +14980,7 @@ static int push_insn(int t, int w, int e, struct bpf_verifier_env *env, { int *insn_stack = env->cfg.insn_stack; int *insn_state = env->cfg.insn_state; + struct bpf_insn *insns = env->prog->insnsi; if (e == FALLTHROUGH && insn_state[t] >= (DISCOVERED | FALLTHROUGH)) return DONE_EXPLORING; @@ -14993,6 +14994,12 @@ static int push_insn(int t, int w, int e, struct bpf_verifier_env *env, return -EINVAL; } + if (e == BRANCH && insns[w].code == 0) { + verbose_linfo(env, t, "%d", t); + verbose(env, "jump to reserved code from insn %d to %d\n", t, w); + return -EINVAL; + } + if (e == BRANCH) { /* mark branch target for state pruning */ mark_prune_point(env, w);