linux-kernel - Re: [PATCH bpf-next v5 4/5] bpf: verifier: Support eliding map lookup nullness

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] [thread-next>] [day] [month] [year] [list]

Message-ID: <f7taicw6c3f3yae4d6lrdagv26jiuihumklo4tkmqduvauargi@ld4bcmsbbiqn>
Date: Thu, 19 Dec 2024 17:40:30 -0700
From: Daniel Xu <dxu@...uu.xyz>
To: Eduard Zingerman <eddyz87@...il.com>
Cc: Andrii Nakryiko <andrii.nakryiko@...il.com>, andrii@...nel.org, 
	ast@...nel.org, shuah@...nel.org, daniel@...earbox.net, john.fastabend@...il.com, 
	martin.lau@...ux.dev, song@...nel.org, yonghong.song@...ux.dev, kpsingh@...nel.org, 
	sdf@...ichev.me, haoluo@...gle.com, jolsa@...nel.org, mykolal@...com, 
	bpf@...r.kernel.org, linux-kernel@...r.kernel.org, linux-kselftest@...r.kernel.org, 
	netdev@...r.kernel.org
Subject: Re: [PATCH bpf-next v5 4/5] bpf: verifier: Support eliding map
 lookup nullness

On Thu, Dec 19, 2024 at 04:04:43PM -0800, Eduard Zingerman wrote:
> On Thu, 2024-12-19 at 14:41 -0700, Daniel Xu wrote:
> 
> [...]
> 
> > > > I think that if test operates on a key like:
> > > > 
> > > >       valid key 15
> > > >              v
> > > >       0000000f   <-- written to stack as a single u64 value
> > > >       ^^^^^^^
> > > >     stack zero marks
> > > > 
> > > > and is executed (e.g. using __retval annotation),
> > > > then CI passing for s390 should be enough.
> > > 
> > > +1, something like that where for big-endian it will be all zero while
> > > for little endian it would be 0xf (and then make sure that the test
> > > should *fail* by making sure that 0xf is not a valid index, so NULL
> > > check is necessary)
> > 
> > How would it work for LE to be 0xF but BE to be 0x0?
> > 
> > The prog passes a pointer to the beginning of the u32 to
> > bpf_map_lookup_elem(). The kernel does a 4 byte read starting from that
> > address. On both BE and LE all 4 bytes will be interpreted. So set bits
> > cannot just go away.
> > 
> > Am I missing something?
> 
> Ok, thinking a bit more, the best test I can come up with is:
> 
>   u8 vals[8];
>   vals[0] = 0;
>   ...
>   vals[6] = 0;
>   vals[7] = 0xf;
>   p = bpf_map_lookup_elem(... vals ...);
>   *p = 42;
> 
> For LE vals as u32 should be 0x0f;
> For BE vals as u32 should be 0xf000_0000.
> Hence, it is not safe to remove null check for this program.
> What would verifier think about the value of such key?
> As far as I understand, there would be stack zero for for vals[0-6]
> and u8 stack spill for vals[7].

Right. By checking that spill size is same as key size, we stay endian
neutral, as constant values are tracked in native endianness.

However, if we were to start interpreting combinations of STACK_ZERO,
STACK_MISC, and STACK_SPILL, the verifier would have to be endian aware
(IIUC). Which makes it a somewhat interesting problem but also requires
some thought to correctly handle the state space.

> You were going to add a check for the spill size, which should help here.
> So, a negative test like above that checks that verifier complains
> that 'p' should be checked for nullness first?
> 
> If anyone has better test in mind, please speak-up.

I think this case reduces down to a spill_size != key_size test. As long
as the sizes match, we don't have to worry about endianness.

Thanks,
Daniel