netdev - Re: [syzbot] [bpf?] WARNING in reg_bounds_sanity

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: <e43c25b451395edff0886201ad3358acd9670eda.camel@gmail.com>
Date: Fri, 04 Jul 2025 14:13:15 -0700
From: Eduard Zingerman <eddyz87@...il.com>
To: Paul Chaignon <paul.chaignon@...il.com>
Cc: syzbot <syzbot+c711ce17dd78e5d4fdcf@...kaller.appspotmail.com>, 
	andrii@...nel.org, ast@...nel.org, bpf@...r.kernel.org,
 daniel@...earbox.net, 	haoluo@...gle.com, john.fastabend@...il.com,
 jolsa@...nel.org, kpsingh@...nel.org, 	linux-kernel@...r.kernel.org,
 martin.lau@...ux.dev, netdev@...r.kernel.org, 	sdf@...ichev.me,
 song@...nel.org, syzkaller-bugs@...glegroups.com, 	yonghong.song@...ux.dev
Subject: Re: [syzbot] [bpf?] WARNING in reg_bounds_sanity_check

On Fri, 2025-07-04 at 10:26 -0700, Eduard Zingerman wrote:
> On Fri, 2025-07-04 at 19:14 +0200, Paul Chaignon wrote:
> > On Thu, Jul 03, 2025 at 11:54:27AM -0700, Eduard Zingerman wrote:

[...]

> > > I think is_branch_taken() modification should not be too complicated.
> > > For JSET it only checks tnum, but does not take ranges into account.
> > > Reasoning about ranges is something along the lines:
> > > - for unsigned range a = b & CONST -> a is in [b_min & CONST, b_max & CONST];
> > > - for signed ranged same thing, but consider two unsigned sub-ranges;
> > > - for non CONST cases, I think same reasoning can apply, but more
> > >   min/max combinations need to be explored.
> > > - then check if zero is a member or 'a' range.
> > > 
> > > Wdyt?
> > 
> > I might be missing something, but I'm not sure that works. For the
> > unsigned range, if we have b & 0x2 with b in [2; 10], then we'd end up
> > with a in [2; 2] and would conclude that the jump is never taken. But
> > b=8 proves us wrong.
> 
> I see, what is really needed is an 'or' joined mask of all 'b' values.
> I need to think how that can be obtained (or approximated).

I think the mask can be computed as in or_range() function at the
bottom of the email. This gives the following algorithm, if only
unsigned range is considered:

- assume prediction is needed for "if a & b goto ..."
- bits that may be set in 'a' are or_range(a_min, a_max)
- bits that may be set in 'b' are or_range(b_min, b_max)
- if computed bit masks intersect: both branches are possible
- otherwise only false branch is possible.

Wdyt?

[...]

---

#include <stdint.h>
#include <stdio.h>

static uint64_t or_range(uint64_t lo, uint64_t hi)
{
  uint64_t m;
  uint32_t i;

  m = hi;
  i = 0;
  while (lo != hi) {
    m |= 1lu << i;
    lo >>= 1;
    hi >>= 1;
    i++;
  }
  return m;
}

static uint64_t or_range_simple(uint64_t lo, uint64_t hi)
{
  uint64_t m = 0;
  uint64_t v = 0;

  for (v = lo; v <= hi; v++)
    m |= v;
  return m;
}

int main(int argc, char *argv[])
{
  int max = 0x1000;
  for (int lo = 0; lo < max; lo++) {
    for (int hi = lo; hi < max; hi++) {
      uint64_t expected = or_range_simple(lo, hi);
      uint64_t result = or_range(lo, hi);

      if (expected != result) {
        printf("mismatch: %x..%x -> expecting %lx, result %lx\n",
               lo, hi, expected, result);
        return 1;
      }
    }
  }
  printf("all ok\n");
  return 0;
}