BPF Archive on lore.kernel.org
 help / color / Atom feed
From: Yonghong Song <yhs@fb.com>
To: John Fastabend <john.fastabend@gmail.com>,
	<alexei.starovoitov@gmail.com>, <daniel@iogearbox.net>
Cc: <bpf@vger.kernel.org>, <kernel-team@fb.com>
Subject: Re: [bpf PATCH 2/3] bpf, selftests: verifier bounds tests need to be updated
Date: Fri, 29 May 2020 11:41:16 -0700
Message-ID: <ec4438b6-4dc0-9310-b14f-f288078fec85@fb.com> (raw)
In-Reply-To: <159077333942.6014.14004320043595756079.stgit@john-Precision-5820-Tower>



On 5/29/20 10:28 AM, John Fastabend wrote:
> After previous fix for zero extension test_verifier tests #65 and #66 now
> fail. Before the fix we can see the alu32 mov op at insn 10
> 
> 10: R0_w=map_value(id=0,off=0,ks=8,vs=8,imm=0)
>      R1_w=invP(id=0,
>                smin_value=4294967168,smax_value=4294967423,
>                umin_value=4294967168,umax_value=4294967423,
>                var_off=(0x0; 0x1ffffffff),
>                s32_min_value=-2147483648,s32_max_value=2147483647,
>                u32_min_value=0,u32_max_value=-1)
>      R10=fp0 fp-8_w=mmmmmmmm
> 10: (bc) w1 = w1
> 11: R0_w=map_value(id=0,off=0,ks=8,vs=8,imm=0)
>      R1_w=invP(id=0,
>                smin_value=0,smax_value=2147483647,
>                umin_value=0,umax_value=4294967295,
>                var_off=(0x0; 0xffffffff),
>                s32_min_value=-2147483648,s32_max_value=2147483647,
>                u32_min_value=0,u32_max_value=-1)
>      R10=fp0 fp-8_w=mmmmmmmm
> 
> After the fix at insn 10 because we have 's32_min_value < 0' the following
> step 11 now has 'smax_value=U32_MAX' where before we pulled the s32_max_value
> bound into the smax_value as seen above in 11 with smax_value=2147483647.
> 
> 10: R0_w=map_value(id=0,off=0,ks=8,vs=8,imm=0)
>      R1_w=inv(id=0,
>               smin_value=4294967168,smax_value=4294967423,
>               umin_value=4294967168,umax_value=4294967423,
>               var_off=(0x0; 0x1ffffffff),
>               s32_min_value=-2147483648, s32_max_value=2147483647,
>               u32_min_value=0,u32_max_value=-1)
>      R10=fp0 fp-8_w=mmmmmmmm
> 10: (bc) w1 = w1
> 11: R0_w=map_value(id=0,off=0,ks=8,vs=8,imm=0)
>      R1_w=inv(id=0,
>               smin_value=0,smax_value=4294967295,
>               umin_value=0,umax_value=4294967295,
>               var_off=(0x0; 0xffffffff),
>               s32_min_value=-2147483648, s32_max_value=2147483647,
>               u32_min_value=0, u32_max_value=-1)
>      R10=fp0 fp-8_w=mmmmmmmm
> 
> The fall out of this is by the time we get to the failing instruction at
> step 14 where previously we had the following:
> 
> 14: R0_w=map_value(id=0,off=0,ks=8,vs=8,imm=0)
>      R1_w=inv(id=0,
>               smin_value=72057594021150720,smax_value=72057594029539328,
>               umin_value=72057594021150720,umax_value=72057594029539328,
>               var_off=(0xffffffff000000; 0xffffff),
>               s32_min_value=-16777216,s32_max_value=-1,
>               u32_min_value=-16777216,u32_max_value=-1)
>      R10=fp0 fp-8_w=mmmmmmmm
> 14: (0f) r0 += r1
> 
> We now have,
> 
> 14: R0_w=map_value(id=0,off=0,ks=8,vs=8,imm=0)
>      R1_w=inv(id=0,
>               smin_value=0,smax_value=72057594037927935,
>               umin_value=0,umax_value=72057594037927935,
>               var_off=(0x0; 0xffffffffffffff),
>               s32_min_value=-2147483648,s32_max_value=2147483647,
>               u32_min_value=0,u32_max_value=-1)
>      R10=fp0 fp-8_w=mmmmmmmm
> 14: (0f) r0 += r1
> 
> In the original step 14 'smin_value=72057594021150720' this trips the logic
> in the verifier function check_reg_sane_offset(),
> 
>   if (smin >= BPF_MAX_VAR_OFF || smin <= -BPF_MAX_VAR_OFF) {
> 	verbose(env, "value %lld makes %s pointer be out of bounds\n",
> 		smin, reg_type_str[type]);
> 	return false;
>   }
> 
> Specifically, the 'smin <= -BPF_MAX_VAR_OFF' check. But with the fix
> at step 14 we have bounds 'smin_value=0' so the above check is not tripped
> because BPF_MAX_VAR_OFF=1<<29.
> 
> We have a smin_value=0 here because at step 10 the smaller smin_value=0 means
> the subtractions at steps 11 and 12 bring the smin_value negative.
> 
> 11: (17) r1 -= 2147483584
> 12: (17) r1 -= 2147483584
> 13: (77) r1 >>= 8
> 
> Then the shift clears the top bit and smin_value is set to 0. Note we still
> have the smax_value in the fixed code so any reads will fail. An alternative
> would be to have reg_sane_check() do both smin and smax value tests.
> 
> To fix the test we can omit the 'r1 >>=8' at line 13. This will change the
> err string, but keeps the intention of the test as suggseted by the title,
> "check after truncation of boundary-crossing range". If the verifier logic
> changes a different value is likely to be thrown in the error or the error
> will no longer be thrown forcing this test to be examined. With this change
> we see the new state at step 13.
> 
> 13: R0_w=map_value(id=0,off=0,ks=8,vs=8,imm=0)
>      R1_w=invP(id=0,
>                smin_value=-4294967168,smax_value=127,
>                umin_value=0,umax_value=18446744073709551615,
>                s32_min_value=-2147483648,s32_max_value=2147483647,
>                u32_min_value=0,u32_max_value=-1)
>      R10=fp0 fp-8_w=mmmmmmmm
> 
> Giving the expected out of bounds error, "value -4294967168 makes map_value
> pointer be out of bounds" However, for unpriv case we see a different error
> now because of the mixed signed bounds pointer arithmatic. This seems OK so
> I've only added the unpriv_errstr for this. Another optino may have been to
> do addition on r1 instead of subtraction but I favor the approach above
> slightly.
> 
> Signed-off-by: John Fastabend <john.fastabend@gmail.com>
> ---
>   tools/testing/selftests/bpf/verifier/bounds.c |   24 ++++++++++--------------
>   1 file changed, 10 insertions(+), 14 deletions(-)

Acked-by: Yonghong Song <yhs@fb.com>

  reply index

Thread overview: 7+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2020-05-29 17:28 [bpf PATCH 0/3] verifier fix for assigning 32bit reg to 64bit reg John Fastabend
2020-05-29 17:28 ` [bpf PATCH 1/3] bpf: fix a verifier issue when assigning 32bit reg states to 64bit ones John Fastabend
2020-05-29 18:40   ` Yonghong Song
2020-05-29 17:28 ` [bpf PATCH 2/3] bpf, selftests: verifier bounds tests need to be updated John Fastabend
2020-05-29 18:41   ` Yonghong Song [this message]
2020-05-29 17:29 ` [bpf PATCH 3/3] bpf, selftests: add a verifier test for assigning 32bit reg states to 64bit ones John Fastabend
2020-05-29 20:53 ` [bpf PATCH 0/3] verifier fix for assigning 32bit reg to 64bit reg Alexei Starovoitov

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=ec4438b6-4dc0-9310-b14f-f288078fec85@fb.com \
    --to=yhs@fb.com \
    --cc=alexei.starovoitov@gmail.com \
    --cc=bpf@vger.kernel.org \
    --cc=daniel@iogearbox.net \
    --cc=john.fastabend@gmail.com \
    --cc=kernel-team@fb.com \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

BPF Archive on lore.kernel.org

Archives are clonable:
	git clone --mirror https://lore.kernel.org/bpf/0 bpf/git/0.git

	# If you have public-inbox 1.1+ installed, you may
	# initialize and index your mirror using the following commands:
	public-inbox-init -V2 bpf bpf/ https://lore.kernel.org/bpf \
		bpf@vger.kernel.org
	public-inbox-index bpf

Example config snippet for mirrors

Newsgroup available over NNTP:
	nntp://nntp.lore.kernel.org/org.kernel.vger.bpf


AGPL code for this site: git clone https://public-inbox.org/public-inbox.git