From: Daniel Borkmann <daniel@iogearbox.net>
To: Kuee k1r0a <liulin063@gmail.com>, haoluo@google.com
Cc: Alexei Starovoitov <ast@kernel.org>,
john.fastabend@gmail.com, Andrii Nakryiko <andrii@kernel.org>,
martin.lau@linux.dev, song@kernel.org, yhs@fb.com,
kpsingh@kernel.org, sdf@google.com, jolsa@kernel.org,
bpf@vger.kernel.org, linux-kernel@vger.kernel.org
Subject: Re: Fwd: [PATCH bpf] bpf: Do more tight ALU bounds tracking
Date: Mon, 8 Aug 2022 17:42:48 +0200 [thread overview]
Message-ID: <9f954e67-67fc-e3b9-d810-22bfea95d2aa@iogearbox.net> (raw)
In-Reply-To: <CANdZH3V64LdfYpWrX9teQQU8LGj10_ecXpupRfnyKQ47gvtOoQ@mail.gmail.com>
On 8/8/22 5:14 PM, Kuee k1r0a wrote:
> ---------- Forwarded message ---------
> From: Kuee k1r0a <liulin063@gmail.com>
> Date: Mon, Aug 8, 2022 at 11:11 PM
> Subject: Re: [PATCH bpf] bpf: Do more tight ALU bounds tracking
> To: Daniel Borkmann <daniel@iogearbox.net>
>
>
> On Mon, Aug 8, 2022 at 9:25 PM Daniel Borkmann <daniel@iogearbox.net> wrote:
>>
>> On 7/30/22 12:48 AM, Hao Luo wrote:
>>> On Fri, Jul 29, 2022 at 3:43 PM Youlin Li <liulin063@gmail.com> wrote:
>>>>
>>>> In adjust_scalar_min_max_vals(), let 32bit bounds learn from 64bit bounds
>>>> to get more tight bounds tracking. Similar operation can be found in
>>>> reg_set_min_max().
>>>>
>>>> Also, we can now fold reg_bounds_sync() into zext_32_to_64().
>>>>
>>>> Before:
>>>>
>>>> func#0 @0
>>>> 0: R1=ctx(off=0,imm=0) R10=fp0
>>>> 0: (b7) r0 = 0 ; R0_w=0
>>>> 1: (b7) r1 = 0 ; R1_w=0
>>>> 2: (87) r1 = -r1 ; R1_w=scalar()
>>>> 3: (87) r1 = -r1 ; R1_w=scalar()
>>>> 4: (c7) r1 s>>= 63 ; R1_w=scalar(smin=-1,smax=0)
>>>> 5: (07) r1 += 2 ; R1_w=scalar(umin=1,umax=2,var_off=(0x0; 0xffffffff)) <--- [*]
>>>> 6: (95) exit
>>>>
>>>> It can be seen that even if the 64bit bounds is clear here, the 32bit
>>>> bounds is still in the state of 'UNKNOWN'.
>>>>
>>>> After:
>>>>
>>>> func#0 @0
>>>> 0: R1=ctx(off=0,imm=0) R10=fp0
>>>> 0: (b7) r0 = 0 ; R0_w=0
>>>> 1: (b7) r1 = 0 ; R1_w=0
>>>> 2: (87) r1 = -r1 ; R1_w=scalar()
>>>> 3: (87) r1 = -r1 ; R1_w=scalar()
>>>> 4: (c7) r1 s>>= 63 ; R1_w=scalar(smin=-1,smax=0)
>>>> 5: (07) r1 += 2 ; R1_w=scalar(umin=1,umax=2,var_off=(0x0; 0x3)) <--- [*]
>>>> 6: (95) exit
>>>>
>>>> Signed-off-by: Youlin Li <liulin063@gmail.com>
>>>
>>> Looks good to me. Thanks Youlin.
>>>
>>> Acked-by: Hao Luo <haoluo@google.com>
>>
>> Thanks Youlin! Looks like the patch breaks CI [0] e.g.:
>>
>> #142/p bounds check after truncation of non-boundary-crossing range FAIL
>> Failed to load prog 'Permission denied'!
>> invalid access to map value, value_size=8 off=16777215 size=1
>> R0 max value is outside of the allowed memory range
>> verification time 296 usec
>> stack depth 8
>> processed 15 insns (limit 1000000) max_states_per_insn 0 total_states 0 peak_states 0 mark_read 0
>>
>> Please take a look. Also it would be great to add a test_verifier selftest to
>> assert above case from commit log against future changes.
>>
>> Thanks,
>> Daniel
>>
>> [0] https://github.com/kernel-patches/bpf/runs/7696324041?check_suite_focus=true
>
> This test case fails because the 32bit boundary information is lost
> after the 11th instruction is executed:
> Before:
> 11: (07) r1 += 2147483647 ;
> R1_w=scalar(umin=70866960383,umax=70866960638,var_off=(0x1000000000;
> 0xffffffff),u32_min=2147483647,u32_max=-2147483394)
> After:
> 11: (07) r1 += 2147483647 ;
> R1_w=scalar(umin=70866960383,umax=70866960638,var_off=(0x1000000000;
> 0xffffffff))
>
> This may be because, in previous versions of the code, when
> __reg_combine_64_into_32() was called, the 32bit boundary was
> completely deduced from the 64bit boundary, so there was a call to
> __mark_reg32_unbounded() in __reg_combine_64_into_32().
>
> But now, before adjust_scalar_min_max_vals() calls
> __reg_combine_64_into_32() , the 32bit bounds are already calculated
> to some extent, and __mark_reg32_unbounded() will eliminate these
> information.
>
> Simply copying a code without __mark_reg32_unbounded() should work,
> perhaps it would be more elegant to introduce a flag into
> __reg_combine_64_into_32()?
>
> Sorry for not completing the tests because I did not 'make selftests'
> successfully, and uploaded the code that caused the error.
Under tools/testing/selftests/bpf/, you can run test_progs and test_verifier
through the vmtest script, e.g. `./vmtest.sh -- ./test_progs` should ease
running it. The whole `make selftests` is not necessary given here we care
about BPF, CI is running these where 2 failed and need investigation:
test_progs: PASS
test_progs-no_alu32: FAIL (returned 1)
test_maps: PASS
test_verifier: FAIL (returned 1)
Fwiw, for the test_verifier failure case at least, we should then adapt it
in a separate commit with an analysis explaining why it is okay to alter the
test; plus a 3rd commit adding new test cases as mentioned earlier.
Thanks a lot, Kuee!
Daniel
next prev parent reply other threads:[~2022-08-08 15:43 UTC|newest]
Thread overview: 14+ messages / expand[flat|nested] mbox.gz Atom feed top
2022-07-29 3:30 [PATCH bpf] bpf: Do more tight ALU bounds tracking Kuee K1r0a
2022-07-29 3:51 ` Hao Luo
2022-07-29 4:43 ` Youlin Li
2022-07-29 17:11 ` Hao Luo
2022-07-29 22:42 ` Youlin Li
2022-07-29 22:48 ` Hao Luo
2022-08-08 13:25 ` Daniel Borkmann
[not found] ` <CANdZH3U7axKg6zDY+iswF2d1fBYY1Xo2jeVsbgMYMoJfd1AYJg@mail.gmail.com>
2022-08-08 15:14 ` Fwd: " Kuee k1r0a
2022-08-08 15:42 ` Daniel Borkmann [this message]
2022-08-10 10:08 ` [PATCH 1/2] bpf: Fix 32bit bounds update in ALU64 Youlin Li
2022-08-17 20:31 ` Daniel Borkmann
2022-08-27 13:57 ` [PATCH bpf v2 1/2] bpf: Do more tight ALU bounds tracking Youlin Li
2022-08-30 0:19 ` Hao Luo
2022-08-10 10:09 ` [PATCH 2/2] bpf, selftests: Add verifier test case for ALU64 Youlin Li
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=9f954e67-67fc-e3b9-d810-22bfea95d2aa@iogearbox.net \
--to=daniel@iogearbox.net \
--cc=andrii@kernel.org \
--cc=ast@kernel.org \
--cc=bpf@vger.kernel.org \
--cc=haoluo@google.com \
--cc=john.fastabend@gmail.com \
--cc=jolsa@kernel.org \
--cc=kpsingh@kernel.org \
--cc=linux-kernel@vger.kernel.org \
--cc=liulin063@gmail.com \
--cc=martin.lau@linux.dev \
--cc=sdf@google.com \
--cc=song@kernel.org \
--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 a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).