linux-kernel - Re: [Bug Report] bpf: incorrectly pruning runtime execution path

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: <CAEf4BzaTTv7oP2vcfVYXjUnA958MqohkRDJ9J7qOCtGfpijROw@mail.gmail.com>
Date: Thu, 14 Dec 2023 21:20:43 -0800
From: Andrii Nakryiko <andrii.nakryiko@...il.com>
To: Eduard Zingerman <eddyz87@...il.com>
Cc: Alexei Starovoitov <alexei.starovoitov@...il.com>, Hao Sun <sunhao.th@...il.com>, 
	Alexei Starovoitov <ast@...nel.org>, Andrii Nakryiko <andrii@...nel.org>, 
	Daniel Borkmann <daniel@...earbox.net>, bpf <bpf@...r.kernel.org>, 
	Linux Kernel Mailing List <linux-kernel@...r.kernel.org>
Subject: Re: [Bug Report] bpf: incorrectly pruning runtime execution path

On Thu, Dec 14, 2023 at 6:28 PM Eduard Zingerman <eddyz87@...il.com> wrote:
>
> On Thu, 2023-12-14 at 18:16 -0800, Alexei Starovoitov wrote:
> [...]
> > > E.g. for the test-case at hand:
> > >
> > >   0: (85) call bpf_get_prandom_u32#7    ; R0=scalar()
> > >   1: (bf) r7 = r0                       ; R0=scalar(id=1) R7_w=scalar(id=1)
> > >   2: (bf) r8 = r0                       ; R0=scalar(id=1) R8_w=scalar(id=1)
> > >   3: (85) call bpf_get_prandom_u32#7    ; R0=scalar()
> > >   --- checkpoint #1 r7.id = 1, r8.id = 1 ---
> > >   4: (25) if r0 > 0x1 goto pc+0         ; R0=scalar(smin=smin32=0,smax=umax=smax32=umax32=1,...)
> > >   --- checkpoint #2 r7.id = 1, r8.id = 1 ---
> > >   5: (3d) if r8 >= r0 goto pc+3         ; R0=1 R8=0 | record r8.id=1 in jump history
> > >   6: (0f) r8 += r8                      ; R8=0
> >
> > can we detect that any register link is broken and force checkpoint here?
>
> Should be possible. I'll try this in the morning and check veristat results.
>
> By the way, I added some stats collection for find_equal_scalars() and see
> the following results when run on ./test_progs:
> - maximal number of registers with same id per call: 3
> - average number of registers with same id per call: 1.4


What if we keep 8 extra bytes in jump/instruction history and encode
up to 8 linked registers/slots:

1. 1 bit to mark whether it's a src_reg set, or dst_reg set
2. 1 bit to mark whether it's a stack slot or register
3. 6 bits (0..63 values) to record register or slot number

If we ever need more than 8 linked registers, we can just forcefully
some "links" by resetting some IDs?

BTW, is it only conditional jumps that need to record this linked
register sets? Did we previously discuss why we don't need this for
any other operation?