Received-SPF: pass (google.com: domain of linux-kernel+bounces-336-linux.lists.archive=gmail.com@vger.kernel.org designates 2604:1380:4601:e00::3 as permitted sender) client-ip=2604:1380:4601:e00::3;
Precedence: bulk
MIME-Version: 1.0
References: <CACkBjsbj4y4EhqpV-ZVt645UtERJRTxfEab21jXD1ahPyzH4_g@mail.gmail.com>
 <CAEf4BzZ0xidVCqB47XnkXcNhkPWF6_nTV7yt+_Lf0kcFEut2Mg@mail.gmail.com>
 <CACkBjsaEQxCaZ0ERRnBXduBqdw3MXB5r7naJx_anqxi0Wa-M_Q@mail.gmail.com>
 <480a5cfefc23446f7c82c5b87eef6306364132b9.camel@gmail.com>
 <917DAD9F-8697-45B8-8890-D33393F6CDF1@gmail.com> <9dee19c7d39795242c15b2f7aa56fb4a6c3ebffa.camel@gmail.com>
 <73d021e3f77161668aae833e478b210ed5cd2f4d.camel@gmail.com>
 <CAEf4BzYuV3odyj8A77ZW8H9jyx_YLhAkSiM+1hkvtH=OYcHL3w@mail.gmail.com>
 <526d4ac8f6788d3323d29fdbad0e0e5d09a534db.camel@gmail.com> <2b49b96de9f8a1cd6d78cc5aebe7c35776cd2c19.camel@gmail.com>
In-Reply-To: <2b49b96de9f8a1cd6d78cc5aebe7c35776cd2c19.camel@gmail.com>
From: Alexei Starovoitov <alexei.starovoitov@gmail.com>
Date: Thu, 14 Dec 2023 18:16:50 -0800
Message-ID: <CAADnVQ+RVT1pO1hTzMawdkfc9B0xAxas2XmSk6+_EiqX9Xy9Ug@mail.gmail.com>
Subject: Re: [Bug Report] bpf: incorrectly pruning runtime execution path
To: Eduard Zingerman <eddyz87@gmail.com>
Cc: Andrii Nakryiko <andrii.nakryiko@gmail.com>, Hao Sun <sunhao.th@gmail.com>, 
	Alexei Starovoitov <ast@kernel.org>, Andrii Nakryiko <andrii@kernel.org>, 
	Daniel Borkmann <daniel@iogearbox.net>, bpf <bpf@vger.kernel.org>, 
	Linux Kernel Mailing List <linux-kernel@vger.kernel.org>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

On Thu, Dec 14, 2023 at 5:24=E2=80=AFPM Eduard Zingerman <eddyz87@gmail.com=
> wrote:
>
> On Fri, 2023-12-15 at 02:49 +0200, Eduard Zingerman wrote:
> > On Thu, 2023-12-14 at 16:06 -0800, Andrii Nakryiko wrote:
> > [...]
> > > If you agree with the analysis, we can start discussing what's the
> > > best way to fix this.
> >
> > Ok, yeap, I agree with you.
> > Backtracker marks both registers in 'if' statement if one of them is
> > tracked, but r8 is not marked at block entry and we miss r0.
>
> The brute-force solution is to keep a special mask for each
> conditional jump in jump history. In this mask, mark all registers and
> stack slots that gained range because of find_equal_scalars() executed
> for this conditional jump. Use this mask to extend precise registers set.
> However, such mask would be prohibitively large: (10+64)*8 bits.
>
> ---
>
> Here is an option that would fix the test in question, but I'm not
> sure if it covers all cases:
> 1. At the last instruction of each state (first instruction to be
>    backtracked) we know the set of IDs that should be tracked for
>    precision, as currently marked by mark_precise_scalar_ids().
> 2. In jump history we can record IDs for src and dst registers when new
>    entry is pushed.
> 3. While backtracking 'if' statement, if one of the recorded IDs is in
>    the set identified at (1), add src/dst regs to precise registers set.
>
> E.g. for the test-case at hand:
>
>   0: (85) call bpf_get_prandom_u32#7    ; R0=3Dscalar()
>   1: (bf) r7 =3D r0                       ; R0=3Dscalar(id=3D1) R7_w=3Dsc=
alar(id=3D1)
>   2: (bf) r8 =3D r0                       ; R0=3Dscalar(id=3D1) R8_w=3Dsc=
alar(id=3D1)
>   3: (85) call bpf_get_prandom_u32#7    ; R0=3Dscalar()
>   --- checkpoint #1 r7.id =3D 1, r8.id =3D 1 ---
>   4: (25) if r0 > 0x1 goto pc+0         ; R0=3Dscalar(smin=3Dsmin32=3D0,s=
max=3Dumax=3Dsmax32=3Dumax32=3D1,...)
>   --- checkpoint #2 r7.id =3D 1, r8.id =3D 1 ---
>   5: (3d) if r8 >=3D r0 goto pc+3         ; R0=3D1 R8=3D0 | record r8.id=
=3D1 in jump history
>   6: (0f) r8 +=3D r8                      ; R8=3D0

can we detect that any register link is broken and force checkpoint here?

>   --- checkpoint #3 r7.id =3D 1, r8.id =3D 0 ---
>   7: (15) if r7 =3D=3D 0x0 goto pc+1