netdev - Re: [PATCH bpf-next v2 5/9] bpf, verifier: improve signed ranges inference for BPF

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 linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [day] [month] [year] [list]

Message-ID: <CAADnVQLZ+fDDR9cFSD8QZghXP6nEmmPP23YWd5-ysA1sZ9ZsGA@mail.gmail.com>
Date: Tue, 23 Jul 2024 18:17:39 -0700
From: Alexei Starovoitov <alexei.starovoitov@...il.com>
To: Shung-Hsi Yu <shung-hsi.yu@...e.com>
Cc: Eduard Zingerman <eddyz87@...il.com>, Xu Kuohai <xukuohai@...weicloud.com>, 
	bpf <bpf@...r.kernel.org>, Network Development <netdev@...r.kernel.org>, 
	LSM List <linux-security-module@...r.kernel.org>, Alexei Starovoitov <ast@...nel.org>, 
	Andrii Nakryiko <andrii@...nel.org>, Daniel Borkmann <daniel@...earbox.net>, 
	Yonghong Song <yonghong.song@...ux.dev>, KP Singh <kpsingh@...nel.org>, 
	Roberto Sassu <roberto.sassu@...wei.com>, Matt Bobrowski <mattbobrowski@...gle.com>, 
	Yafang Shao <laoar.shao@...il.com>, Ilya Leoshkevich <iii@...ux.ibm.com>, 
	"Jose E . Marchesi" <jose.marchesi@...cle.com>, James Morris <jamorris@...ux.microsoft.com>, 
	Kees Cook <kees@...nel.org>, Brendan Jackman <jackmanb@...gle.com>, 
	Florent Revest <revest@...gle.com>
Subject: Re: [PATCH bpf-next v2 5/9] bpf, verifier: improve signed ranges
 inference for BPF_AND

On Tue, Jul 23, 2024 at 12:07 AM Shung-Hsi Yu <shung-hsi.yu@...e.com> wrote:
>
> On Tue, Jul 23, 2024 at 02:36:18PM GMT, Shung-Hsi Yu wrote:
> [...]
> > > +1
> > > Pls document the logic in the code.
> > > commit log is good, but good chunk of it probably should be copied
> > > as a comment.
> > >
> > > I've applied the rest of the patches and removed 'test 3' selftest.
> > > Pls respin this patch and a test.
> > > More than one test would be nice too.
> >
> > Ack. Will send send another series that:
> >
> > 1. update current patch
> >   - add code comment explanation how signed ranges are deduced in
> >     scalar*_min_max_and()
> >   - revert 229d6db14942 "selftests/bpf: Workaround strict bpf_lsm return
> >     value check."
> > 2. reintroduce Xu Kuohai's "test 3" into verifier_lsm.c
> > 3. add a few tests for BPF_AND's signed range deduction
> >    - should it be added to verifier_bounds*.c or verifier_and.c?
> >
> >      I think former, because if we later add signed range deduction for
> >      BPF_OR as well...
>
> I was curious whether there would be imminent need for signed range
> deduction for BPF_OR, though looks like there is _not_.
>
> Looking at DAGCombiner::SimplifySelectCC() it does not do the
> bitwise-OR variant of what we've encountered[1,2], that is
>
>     fold (select_cc seteq (and x, y), 0, A, -1) -> (or (sra (shl x)) A)
>
> In other words, transforming the following theoretial C code that
> returns -EACCES when certain bit is unset, and -1 when certain bit is
> set
>
>     if (fmode & FMODE_WRITE)
>         return -1;
>
>     return -EACCESS;
>
> into the following instructions
>
>     r0  <<= 62
>     r0 s>>= 63 /* set => r0 = -1, unset => r0 = 0 */
>     r0  |= -13 /* set => r0 = (-1 | -13) = -1, unset => r0 = (0 | -13) = -13 = -EACCESS */
>         exit       /* returns either -1 or -EACCESS */
>
> So signed ranged deduction with BPF_OR is probably just a nice-to-have
> for now.

Yeah. Let's not complicate the verifier until really necessary.

But I wonder whether we should override shouldFoldSelectWithSingleBitTest()
in the backend to suppress this optimization.
I guess not, since removal of a branch is a good thing.