Re: [bpf PATCH v3] bpf: verifier, do_refine_retval_range may clamp umin to 0 incorrectly

From: Alexei Starovoitov <alexei.starovoitov@gmail.com>
To: John Fastabend <john.fastabend@gmail.com>
Cc: Daniel Borkmann <daniel@iogearbox.net>, bpf <bpf@vger.kernel.org>,
	Yonghong Song <yhs@fb.com>, Alexei Starovoitov <ast@kernel.org>
Subject: Re: [bpf PATCH v3] bpf: verifier, do_refine_retval_range may clamp umin to 0 incorrectly
Date: Wed, 29 Jan 2020 16:04:17 -0800	[thread overview]
Message-ID: <20200130000415.dwd7zn6wj7qlms7g@ast-mbp> (raw)
In-Reply-To: <5e320c9a30f64_2a332aadcd1385bc3f@john-XPS-13-9370.notmuch>

On Wed, Jan 29, 2020 at 02:52:10PM -0800, John Fastabend wrote:
> Daniel Borkmann wrote:
> > On 1/29/20 8:28 PM, Alexei Starovoitov wrote:
> > > On Wed, Jan 29, 2020 at 8:25 AM Daniel Borkmann <daniel@iogearbox.net> wrote:
> > >>>
> > >>> Fixes: 849fa50662fbc ("bpf/verifier: refine retval R0 state for bpf_get_stack helper")
> > >>> Signed-off-by: John Fastabend <john.fastabend@gmail.com>
> > >>
> > >> Applied, thanks!
> > > 
> > > Daniel,
> > > did you run the selftests before applying?
> > > This patch breaks two.
> > > We have to find a different fix.
> > > 
> > > ./test_progs -t get_stack
> > > 68: (85) call bpf_get_stack#67
> > >   R0=inv(id=0,smax_value=800) R1_w=ctx(id=0,off=0,imm=0)
> > > R2_w=map_value(id=0,off=0,ks=4,vs=1600,umax_value=4294967295,var_off=(0x0;
> > > 0xffffffff)) R3_w=inv(id=0,umax_value=4294967295,var_off=(0x0;
> > > 0xffffffff)) R4_w=inv0 R6=ctx(id=0,off=0,im?
> > > R2 unbounded memory access, make sure to bounds check any array access
> > > into a map
> > 
> > Sigh, had it in my wip pre-rebase tree when running tests. I've revert it from the
> > tree since this needs to be addressed. Sorry for the trouble.
> 
> Thanks I'm looking into it now. Not sure how I missed it on
> selftests either older branch or I missed the test somehow. I've
> updated toolchain and kernel now so shouldn't happen again.

Looks like smax_value was nuked by <<32 >>32 shifts.
53: (bf) r8 = r0   // R0=inv(id=0,smax_value=800)
54: (67) r8 <<= 32  // R8->smax_value = S64_MAX; in adjust_scalar_min_max_vals()
55: (c7) r8 s>>= 32
; if (usize < 0)
56: (c5) if r8 s< 0x0 goto pc+28
// and here "less than zero check" doesn't help anymore.

Not sure how to fix it yet, but the code pattern used in
progs/test_get_stack_rawtp.c
is real. Plenty of bpf progs rely on this.