From: Yonghong Song <yhs@meta.com>
To: Shung-Hsi Yu <shung-hsi.yu@suse.com>, Yonghong Song <yhs@fb.com>
Cc: bpf@vger.kernel.org, Alexei Starovoitov <ast@kernel.org>,
Andrii Nakryiko <andrii@kernel.org>,
Daniel Borkmann <daniel@iogearbox.net>,
kernel-team@fb.com, Martin KaFai Lau <martin.lau@kernel.org>
Subject: Re: [PATCH bpf-next 1/2] bpf: Improve verifier u32 scalar equality checking
Date: Tue, 18 Apr 2023 10:54:39 -0700 [thread overview]
Message-ID: <0378bb31-dc0a-f656-c0e7-733ff1c78990@meta.com> (raw)
In-Reply-To: <ZD0+ULVuyhDtl8Aq@syu-laptop.lan>
On 4/17/23 5:40 AM, Shung-Hsi Yu wrote:
> On Sun, Apr 16, 2023 at 04:28:08PM -0700, Yonghong Song wrote:
>> In [1], I tried to remove bpf-specific codes to prevent certain
>> llvm optimizations, and add llvm TTI (target transform info) hooks
>> to prevent those optimizations. During this process, I found
>> if I enable llvm SimplifyCFG:shouldFoldTwoEntryPHINode
>> transformation, I will hit the following verification failure with selftests:
>>
>> ...
>> 8: (18) r1 = 0xffffc900001b2230 ; R1_w=map_value(off=560,ks=4,vs=564,imm=0)
>> 10: (61) r1 = *(u32 *)(r1 +0) ; R1_w=scalar(umax=4294967295,var_off=(0x0; 0xffffffff))
>> ; if (skb->tstamp == EGRESS_ENDHOST_MAGIC)
>> 11: (79) r2 = *(u64 *)(r6 +152) ; R2_w=scalar() R6=ctx(off=0,imm=0)
>> ; if (skb->tstamp == EGRESS_ENDHOST_MAGIC)
>> 12: (55) if r2 != 0xb9fbeef goto pc+10 ; R2_w=195018479
>> 13: (bc) w2 = w1 ; R1_w=scalar(umax=4294967295,var_off=(0x0; 0xffffffff)) R2_w=scalar(umax=4294967295,var_off=(0x0; 0xffffffff))
>> ; if (test < __NR_TESTS)
>> 14: (a6) if w1 < 0x9 goto pc+1 16: R0=2 R1_w=scalar(umax=8,var_off=(0x0; 0xf)) R2_w=scalar(umax=4294967295,var_off=(0x0; 0xffffffff)) R6=ctx(off=0,imm=0) R10=fp0
>> ;
>> 16: (27) r2 *= 28 ; R2_w=scalar(umax=120259084260,var_off=(0x0; 0x1ffffffffc),s32_max=2147483644,u32_max=-4)
>> 17: (18) r3 = 0xffffc900001b2118 ; R3_w=map_value(off=280,ks=4,vs=564,imm=0)
>> 19: (0f) r3 += r2 ; R2_w=scalar(umax=120259084260,var_off=(0x0; 0x1ffffffffc),s32_max=2147483644,u32_max=-4) R3_w=map_value(off=280,ks=4,vs=564,umax=120259084260,var_off=(0x0; 0x1ffffffffc),s32_max=2147483644,u32_max=-4)
>> 20: (61) r2 = *(u32 *)(r3 +0)
>> R3 unbounded memory access, make sure to bounds check any such access
>> processed 97 insns (limit 1000000) max_states_per_insn 1 total_states 10 peak_states 10 mark_read 6
>> -- END PROG LOAD LOG --
>> libbpf: prog 'ingress_fwdns_prio100': failed to load: -13
>> libbpf: failed to load object 'test_tc_dtime'
>> libbpf: failed to load BPF skeleton 'test_tc_dtime': -13
>> ...
>>
>> At insn 14, with condition 'w1 < 9', register r1 is changed from an arbitrary
>> u32 value to `scalar(umax=8,var_off=(0x0; 0xf))`. Register r2, however, remains
>> as an arbitrary u32 value. Current verifier won't claim r1/r2 equality if
>> the previous mov is alu32 ('w2 = w1').
>>
>> If r1 upper 32bit value is not 0, we indeed cannot clamin r1/r2 equality
>> after 'w2 = w1'. But in this particular case, we know r1 upper 32bit value
>> is 0, so it is safe to claim r1/r2 equality. This patch exactly did this.
>> For a 32bit subreg mov, if the src register upper 32bit is 0,
>> it is okay to claim equality between src and dst registers.
>
> Perhaps mention in the above paragraph that this works because 32-bit ALU
> operations clear the upper bits? Some along the line of
>
> A special case where r1/r2 equality can be claimed after 'w2 = w1' is when
> r1 upper 32bit value is 0. This is because 32bit ALU operations always
> clear the upper 32 bits of the destination, so 'w2 = w1' in this case is
> the same as 'r2 = r1'...
In BPF documentation (Documentation/bpf/instruction-set.rst), we have
...
for ``BPF_ALU`` the upper
32 bits of the destination register are zeroed
I asssume this is known and that is why I didn't explicitly mention
this in the commit message. The patch has been merged...
>
>> With this patch, the above verification sequence becomes
>>
>> ...
>> 8: (18) r1 = 0xffffc9000048e230 ; R1_w=map_value(off=560,ks=4,vs=564,imm=0)
>> 10: (61) r1 = *(u32 *)(r1 +0) ; R1_w=scalar(umax=4294967295,var_off=(0x0; 0xffffffff))
>> ; if (skb->tstamp == EGRESS_ENDHOST_MAGIC)
>> 11: (79) r2 = *(u64 *)(r6 +152) ; R2_w=scalar() R6=ctx(off=0,imm=0)
>> ; if (skb->tstamp == EGRESS_ENDHOST_MAGIC)
>> 12: (55) if r2 != 0xb9fbeef goto pc+10 ; R2_w=195018479
>> 13: (bc) w2 = w1 ; R1_w=scalar(id=6,umax=4294967295,var_off=(0x0; 0xffffffff)) R2_w=scalar(id=6,umax=4294967295,var_off=(0x0; 0xffffffff))
>> ; if (test < __NR_TESTS)
>> 14: (a6) if w1 < 0x9 goto pc+1 ; R1_w=scalar(id=6,umin=9,umax=4294967295,var_off=(0x0; 0xffffffff))
>> ...
>> from 14 to 16: R0=2 R1_w=scalar(id=6,umax=8,var_off=(0x0; 0xf)) R2_w=scalar(id=6,umax=8,var_off=(0x0; 0xf)) R6=ctx(off=0,imm=0) R10=fp0
>> 16: (27) r2 *= 28 ; R2_w=scalar(umax=224,var_off=(0x0; 0xfc))
>> 17: (18) r3 = 0xffffc9000048e118 ; R3_w=map_value(off=280,ks=4,vs=564,imm=0)
>> 19: (0f) r3 += r2
>> 20: (61) r2 = *(u32 *)(r3 +0) ; R2_w=scalar(umax=4294967295,var_off=(0x0; 0xffffffff)) R3_w=map_value(off=280,ks=4,vs=564,umax=224,var_off=(0x0; 0xfc),s32_max=252,u32_max=252)
>> ...
>>
>> and eventually the bpf program can be verified successfully.
>>
>> [1] https://reviews.llvm.org/D147968
>>
>> Signed-off-by: Yonghong Song <yhs@fb.com>
>
> Acked-by: Shung-Hsi Yu <shung-hsi.yu@suse.com>
>
>> ---
>> kernel/bpf/verifier.c | 9 +++++++--
>> 1 file changed, 7 insertions(+), 2 deletions(-)
>>
>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
>> index d6db6de3e9ea..468f002d3248 100644
>> --- a/kernel/bpf/verifier.c
>> +++ b/kernel/bpf/verifier.c
>> @@ -12409,12 +12409,17 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)
>> insn->src_reg);
>> return -EACCES;
>> } else if (src_reg->type == SCALAR_VALUE) {
>> + bool is_src_reg_u32 = src_reg->umax_value <= U32_MAX;
>> +
>> + if (is_src_reg_u32 && !src_reg->id)
>> + src_reg->id = ++env->id_gen;
>> copy_register_state(dst_reg, src_reg);
>> - /* Make sure ID is cleared otherwise
>> + /* Make sure ID is cleared if src_reg is not in u32 range otherwise
>> * dst_reg min/max could be incorrectly
>> * propagated into src_reg by find_equal_scalars()
>> */
>> - dst_reg->id = 0;
>> + if (!is_src_reg_u32)
>> + dst_reg->id = 0;
>> dst_reg->live |= REG_LIVE_WRITTEN;
>> dst_reg->subreg_def = env->insn_idx + 1;
>> } else {
>> --
>> 2.34.1
>>
next prev parent reply other threads:[~2023-04-18 17:55 UTC|newest]
Thread overview: 8+ messages / expand[flat|nested] mbox.gz Atom feed top
2023-04-16 23:28 [PATCH bpf-next 1/2] bpf: Improve verifier u32 scalar equality checking Yonghong Song
2023-04-16 23:28 ` [PATCH bpf-next 2/2] selftests/bpf: Add a selftest for checking subreg equality Yonghong Song
2023-04-17 17:44 ` Eduard Zingerman
2023-04-17 17:52 ` Eduard Zingerman
2023-04-17 21:54 ` Yonghong Song
2023-04-17 12:40 ` [PATCH bpf-next 1/2] bpf: Improve verifier u32 scalar equality checking Shung-Hsi Yu
2023-04-18 17:54 ` Yonghong Song [this message]
2023-04-20 9:16 ` Shung-Hsi Yu
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=0378bb31-dc0a-f656-c0e7-733ff1c78990@meta.com \
--to=yhs@meta.com \
--cc=andrii@kernel.org \
--cc=ast@kernel.org \
--cc=bpf@vger.kernel.org \
--cc=daniel@iogearbox.net \
--cc=kernel-team@fb.com \
--cc=martin.lau@kernel.org \
--cc=shung-hsi.yu@suse.com \
--cc=yhs@fb.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.