linux-kernel - Re: [PATCH bpf-next] Fix latent unsoundness in and/or/xor value tracking

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: <CAM=Ch04JAJDS84xYHFUfjrShwqSSc8gQ5a_sLCoRNAsf6tyjYQ@mail.gmail.com>
Date: Fri, 29 Mar 2024 23:24:57 -0400
From: Harishankar Vishwanathan <harishankar.vishwanathan@...il.com>
To: Eduard Zingerman <eddyz87@...il.com>
Cc: ast@...nel.org, harishankar.vishwanathan@...gers.edu, sn624@...rutgers.edu, 
	sn349@...rutgers.edu, m.shachnai@...gers.edu, paul@...valent.com, 
	Srinivas Narayana <srinivas.narayana@...gers.edu>, 
	Santosh Nagarakatte <santosh.nagarakatte@...gers.edu>, Daniel Borkmann <daniel@...earbox.net>, 
	John Fastabend <john.fastabend@...il.com>, Andrii Nakryiko <andrii@...nel.org>, 
	Martin KaFai Lau <martin.lau@...ux.dev>, Song Liu <song@...nel.org>, 
	Yonghong Song <yonghong.song@...ux.dev>, KP Singh <kpsingh@...nel.org>, 
	Stanislav Fomichev <sdf@...gle.com>, Hao Luo <haoluo@...gle.com>, Jiri Olsa <jolsa@...nel.org>, 
	bpf@...r.kernel.org, linux-kernel@...r.kernel.org
Subject: Re: [PATCH bpf-next] Fix latent unsoundness in and/or/xor value tracking

On Fri, Mar 29, 2024 at 6:27 AM Eduard Zingerman <eddyz87@...il.com> wrote:
>
> On Thu, 2024-03-28 at 23:01 -0400, Harishankar Vishwanathan wrote:
>
> [...]
>
> > @@ -13387,18 +13389,19 @@ static void scalar32_min_max_or(struct bpf_reg_state *dst_reg,
> >        */
> >       dst_reg->u32_min_value = max(dst_reg->u32_min_value, umin_val);
> >       dst_reg->u32_max_value = var32_off.value | var32_off.mask;
> > -     if (dst_reg->s32_min_value < 0 || smin_val < 0) {
> > +     if (dst_reg->s32_min_value > 0 && smin_val > 0 &&
>
> Hello,
>
> Could you please elaborate a bit, why do you use "> 0" not ">= 0" here?
> It seems that having one of the min values as 0 shouldn't be an issue,
> but maybe I miss something.

You are right, this is a mistake, I sent the wrong version of the patch. Thanks
for catching it. I will send a new patch.

Note that in the correct version i'll be sending, instead of the following
if condition,

if (dst_reg->s32_min_value >= 0 && smin_val >= 0 &&
(s32)dst_reg->u32_min_value <= (s32)dst_reg->u32_max_value)

it will use this if condition:

if ((s32)dst_reg->u32_min_value <= (s32)dst_reg->u32_max_value)

Inside the if, the output signed bounds are updated using the unsigned
bounds; the only case in which this is unsafe is when the unsigned
bounds cross the sign boundary.  The shortened if condition is enough to
prevent this. The shortened has the added benefit of being more
precise. We will make a note of this in the new commit message.

This applies to all scalar(32)_min_max_and/or/xor.

> > +             (s32)dst_reg->u32_min_value <= (s32)dst_reg->u32_max_value) {
> > +             /* ORing two positives gives a positive, so safe to cast
> > +              * u32 result into s32 when u32 doesn't cross sign boundary.
> > +              */
> > +             dst_reg->s32_min_value = dst_reg->u32_min_value;
> > +             dst_reg->s32_max_value = dst_reg->u32_max_value;
> > +     } else {
> >               /* Lose signed bounds when ORing negative numbers,
> >                * ain't nobody got time for that.
> >                */
> >               dst_reg->s32_min_value = S32_MIN;
> >               dst_reg->s32_max_value = S32_MAX;
> > -     } else {
> > -             /* ORing two positives gives a positive, so safe to
> > -              * cast result into s64.
> > -              */
> > -             dst_reg->s32_min_value = dst_reg->u32_min_value;
> > -             dst_reg->s32_max_value = dst_reg->u32_max_value;
> >       }
> >  }
>
> [...]
>
> > @@ -13453,10 +13457,10 @@ static void scalar32_min_max_xor(struct bpf_reg_state *dst_reg,
> >       /* We get both minimum and maximum from the var32_off. */
> >       dst_reg->u32_min_value = var32_off.value;
> >       dst_reg->u32_max_value = var32_off.value | var32_off.mask;
> > -
> > -     if (dst_reg->s32_min_value >= 0 && smin_val >= 0) {
> > -             /* XORing two positive sign numbers gives a positive,
> > -              * so safe to cast u32 result into s32.
> > +     if (dst_reg->s32_min_value > 0 && smin_val > 0 &&
>
> Same question here.
>
> > +             (s32)dst_reg->u32_min_value <= (s32)dst_reg->u32_max_value) {
> > +             /* XORing two positives gives a positive, so safe to cast
> > +              * u32 result into s32 when u32 doesn't cross sign boundary.
> >                */
> >               dst_reg->s32_min_value = dst_reg->u32_min_value;
> >               dst_reg->s32_max_value = dst_reg->u32_max_value;
>
> [...]