[PATCH bpf-next] bpf/verifier: enable ctx + const + 0.

[PATCH bpf-next] bpf/verifier: enable ctx + const + 0.

[William Tu]

Existing verifier does not allow 'ctx + const + const'.  However, due to
compiler optimization, there is a case where BPF compilerit generates
'ctx + const + 0', as shown below:

  599: (1d) if r2 == r4 goto pc+2
   R0=inv(id=0) R1=ctx(id=0,off=40,imm=0)
   R2=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff))
   R3=inv(id=0,umax_value=65535,var_off=(0x0; 0xffff)) R4=inv0
   R6=ctx(id=0,off=0,imm=0) R7=inv2
  600: (bf) r1 = r6			// r1 is ctx
  601: (07) r1 += 36			// r1 has offset 36
  602: (61) r4 = *(u32 *)(r1 +0)	// r1 + 0
  dereference of modified ctx ptr R1 off=36+0, ctx+const is allowed,
  ctx+const+const is not

The reason for BPF backend generating this code is due optimization
likes this, explained from Yonghong:
    if (...)
        *(ctx + 60)
    else
        *(ctx + 56)

The compiler translates it to
    if (...)
       ptr = ctx + 60
    else
       ptr = ctx + 56
    *(ptr + 0)

So load ptr memory become an example of 'ctx + const + 0'.  This patch
enables support for this case.

Fixes: f8ddadc4db6c7 ("Merge git://git.kernel.org/pub/scm/linux/kernel/git/davem/net")
Cc: Yonghong Song <yhs@fb.com>
Signed-off-by: Yifeng Sun <pkusunyifeng@gmail.com>
Signed-off-by: William Tu <u9012063@gmail.com>
---
 kernel/bpf/verifier.c                       |  2 +-
 tools/testing/selftests/bpf/test_verifier.c | 13 +++++++++++++
 2 files changed, 14 insertions(+), 1 deletion(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 712d8655e916..c9a791b9cf2a 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -1638,7 +1638,7 @@ static int check_mem_access(struct bpf_verifier_env *env, int insn_idx, u32 regn
 		/* ctx accesses must be at a fixed offset, so that we can
 		 * determine what type of data were returned.
 		 */
-		if (reg->off) {
+		if (reg->off && off != reg->off) {
 			verbose(env,
 				"dereference of modified ctx ptr R%d off=%d+%d, ctx+const is allowed, ctx+const+const is not\n",
 				regno, reg->off, off - reg->off);
diff --git a/tools/testing/selftests/bpf/test_verifier.c b/tools/testing/selftests/bpf/test_verifier.c
index 1acafe26498b..95ad5d5723ae 100644
--- a/tools/testing/selftests/bpf/test_verifier.c
+++ b/tools/testing/selftests/bpf/test_verifier.c
@@ -8452,6 +8452,19 @@ static struct bpf_test tests[] = {
 		.prog_type = BPF_PROG_TYPE_SCHED_CLS,
 	},
 	{
+		"arithmetic ops make PTR_TO_CTX + const + 0 valid",
+		.insns = {
+			BPF_ALU64_IMM(BPF_ADD, BPF_REG_1,
+				      offsetof(struct __sk_buff, data) -
+				      offsetof(struct __sk_buff, mark)),
+			BPF_LDX_MEM(BPF_W, BPF_REG_0, BPF_REG_1, 0),
+			BPF_MOV64_IMM(BPF_REG_0, 0),
+			BPF_EXIT_INSN(),
+		},
+		.result = ACCEPT,
+		.prog_type = BPF_PROG_TYPE_SCHED_CLS,
+	},
+	{
 		"pkt_end - pkt_start is allowed",
 		.insns = {
 			BPF_LDX_MEM(BPF_W, BPF_REG_0, BPF_REG_1,
-- 
2.7.4

Re: [PATCH bpf-next] bpf/verifier: enable ctx + const + 0.

[Alexei Starovoitov]

On Mon, Apr 30, 2018 at 10:15:05AM -0700, William Tu wrote:
> Existing verifier does not allow 'ctx + const + const'.  However, due to
> compiler optimization, there is a case where BPF compilerit generates
> 'ctx + const + 0', as shown below:
> 
>   599: (1d) if r2 == r4 goto pc+2
>    R0=inv(id=0) R1=ctx(id=0,off=40,imm=0)
>    R2=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff))
>    R3=inv(id=0,umax_value=65535,var_off=(0x0; 0xffff)) R4=inv0
>    R6=ctx(id=0,off=0,imm=0) R7=inv2
>   600: (bf) r1 = r6			// r1 is ctx
>   601: (07) r1 += 36			// r1 has offset 36
>   602: (61) r4 = *(u32 *)(r1 +0)	// r1 + 0
>   dereference of modified ctx ptr R1 off=36+0, ctx+const is allowed,
>   ctx+const+const is not
> 
> The reason for BPF backend generating this code is due optimization
> likes this, explained from Yonghong:
>     if (...)
>         *(ctx + 60)
>     else
>         *(ctx + 56)
> 
> The compiler translates it to
>     if (...)
>        ptr = ctx + 60
>     else
>        ptr = ctx + 56
>     *(ptr + 0)
> 
> So load ptr memory become an example of 'ctx + const + 0'.  This patch
> enables support for this case.
> 
> Fixes: f8ddadc4db6c7 ("Merge git://git.kernel.org/pub/scm/linux/kernel/git/davem/net")
> Cc: Yonghong Song <yhs@fb.com>
> Signed-off-by: Yifeng Sun <pkusunyifeng@gmail.com>
> Signed-off-by: William Tu <u9012063@gmail.com>
> ---
>  kernel/bpf/verifier.c                       |  2 +-
>  tools/testing/selftests/bpf/test_verifier.c | 13 +++++++++++++
>  2 files changed, 14 insertions(+), 1 deletion(-)
> 
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 712d8655e916..c9a791b9cf2a 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -1638,7 +1638,7 @@ static int check_mem_access(struct bpf_verifier_env *env, int insn_idx, u32 regn
>  		/* ctx accesses must be at a fixed offset, so that we can
>  		 * determine what type of data were returned.
>  		 */
> -		if (reg->off) {
> +		if (reg->off && off != reg->off) {
>  			verbose(env,
>  				"dereference of modified ctx ptr R%d off=%d+%d, ctx+const is allowed, ctx+const+const is not\n",
>  				regno, reg->off, off - reg->off);
> diff --git a/tools/testing/selftests/bpf/test_verifier.c b/tools/testing/selftests/bpf/test_verifier.c
> index 1acafe26498b..95ad5d5723ae 100644
> --- a/tools/testing/selftests/bpf/test_verifier.c
> +++ b/tools/testing/selftests/bpf/test_verifier.c
> @@ -8452,6 +8452,19 @@ static struct bpf_test tests[] = {
>  		.prog_type = BPF_PROG_TYPE_SCHED_CLS,
>  	},
>  	{
> +		"arithmetic ops make PTR_TO_CTX + const + 0 valid",
> +		.insns = {
> +			BPF_ALU64_IMM(BPF_ADD, BPF_REG_1,
> +				      offsetof(struct __sk_buff, data) -
> +				      offsetof(struct __sk_buff, mark)),
> +			BPF_LDX_MEM(BPF_W, BPF_REG_0, BPF_REG_1, 0),

How rewritten code looks here?

The patch is allowing check_ctx_access() to proceed with sort-of
correct 'off' and remember ctx_field_size,
but in convert_ctx_accesses() it's using insn->off to do conversion.
Which is zero in this case, so it will convert
struct __sk_buff {
        __u32 len; // offset 0

into access of 'struct sk_buff'->len
and then will add __sk_buff's &data - &mark delta to in-kernel len field.
Which will point to some random field further down in struct sk_buff.
Doesn't look correct at all.

How did you test this patch?

Re: [PATCH bpf-next] bpf/verifier: enable ctx + const + 0.

[William Tu]

On Tue, May 1, 2018 at 4:16 PM, Alexei Starovoitov
<alexei.starovoitov@gmail.com> wrote:
> On Mon, Apr 30, 2018 at 10:15:05AM -0700, William Tu wrote:
>> Existing verifier does not allow 'ctx + const + const'.  However, due to
>> compiler optimization, there is a case where BPF compilerit generates
>> 'ctx + const + 0', as shown below:
>>
>>   599: (1d) if r2 == r4 goto pc+2
>>    R0=inv(id=0) R1=ctx(id=0,off=40,imm=0)
>>    R2=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff))
>>    R3=inv(id=0,umax_value=65535,var_off=(0x0; 0xffff)) R4=inv0
>>    R6=ctx(id=0,off=0,imm=0) R7=inv2
>>   600: (bf) r1 = r6                   // r1 is ctx
>>   601: (07) r1 += 36                  // r1 has offset 36
>>   602: (61) r4 = *(u32 *)(r1 +0)      // r1 + 0
>>   dereference of modified ctx ptr R1 off=36+0, ctx+const is allowed,
>>   ctx+const+const is not
>>
>> The reason for BPF backend generating this code is due optimization
>> likes this, explained from Yonghong:
>>     if (...)
>>         *(ctx + 60)
>>     else
>>         *(ctx + 56)
>>
>> The compiler translates it to
>>     if (...)
>>        ptr = ctx + 60
>>     else
>>        ptr = ctx + 56
>>     *(ptr + 0)
>>
>> So load ptr memory become an example of 'ctx + const + 0'.  This patch
>> enables support for this case.
>>
>> Fixes: f8ddadc4db6c7 ("Merge git://git.kernel.org/pub/scm/linux/kernel/git/davem/net")
>> Cc: Yonghong Song <yhs@fb.com>
>> Signed-off-by: Yifeng Sun <pkusunyifeng@gmail.com>
>> Signed-off-by: William Tu <u9012063@gmail.com>
>> ---
>>  kernel/bpf/verifier.c                       |  2 +-
>>  tools/testing/selftests/bpf/test_verifier.c | 13 +++++++++++++
>>  2 files changed, 14 insertions(+), 1 deletion(-)
>>
>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
>> index 712d8655e916..c9a791b9cf2a 100644
>> --- a/kernel/bpf/verifier.c
>> +++ b/kernel/bpf/verifier.c
>> @@ -1638,7 +1638,7 @@ static int check_mem_access(struct bpf_verifier_env *env, int insn_idx, u32 regn
>>               /* ctx accesses must be at a fixed offset, so that we can
>>                * determine what type of data were returned.
>>                */
>> -             if (reg->off) {
>> +             if (reg->off && off != reg->off) {
>>                       verbose(env,
>>                               "dereference of modified ctx ptr R%d off=%d+%d, ctx+const is allowed, ctx+const+const is not\n",
>>                               regno, reg->off, off - reg->off);
>> diff --git a/tools/testing/selftests/bpf/test_verifier.c b/tools/testing/selftests/bpf/test_verifier.c
>> index 1acafe26498b..95ad5d5723ae 100644
>> --- a/tools/testing/selftests/bpf/test_verifier.c
>> +++ b/tools/testing/selftests/bpf/test_verifier.c
>> @@ -8452,6 +8452,19 @@ static struct bpf_test tests[] = {
>>               .prog_type = BPF_PROG_TYPE_SCHED_CLS,
>>       },
>>       {
>> +             "arithmetic ops make PTR_TO_CTX + const + 0 valid",
>> +             .insns = {
>> +                     BPF_ALU64_IMM(BPF_ADD, BPF_REG_1,
>> +                                   offsetof(struct __sk_buff, data) -
>> +                                   offsetof(struct __sk_buff, mark)),

This is:
   r1 += N     // r1 has offset N: the offset between data and mark)

>> +                     BPF_LDX_MEM(BPF_W, BPF_REG_0, BPF_REG_1, 0),

This is:
   r0 = *(u32 *)(r1 +0)      // r1 + 0

So the above two lines create similar case I hit
  601: (07) r1 += 36                       // r1 has offset 36
  602: (61) r4 = *(u32 *)(r1 +0)      // r1 + 0

>
> How rewritten code looks here?
>
> The patch is allowing check_ctx_access() to proceed with sort-of
> correct 'off' and remember ctx_field_size,
> but in convert_ctx_accesses() it's using insn->off to do conversion.
> Which is zero in this case, so it will convert
> struct __sk_buff {
>         __u32 len; // offset 0
>
> into access of 'struct sk_buff'->len
> and then will add __sk_buff's &data - &mark delta to in-kernel len field.
> Which will point to some random field further down in struct sk_buff.
> Doesn't look correct at all.

why?
So it points to ctx + "offsetof(struct __sk_buff, data) -
offsetof(struct __sk_buff, mark)",
which is ctx + const
then I tested that 'ctx + const + 0' should pass the verifier

> How did you test this patch?
>
Without the patch, the test case will fail.
With the patch, the test case passes.

William

Re: [PATCH bpf-next] bpf/verifier: enable ctx + const + 0.

[Alexei Starovoitov]

On Tue, May 01, 2018 at 09:35:29PM -0700, William Tu wrote:
> 
> > How did you test this patch?
> >
> Without the patch, the test case will fail.
> With the patch, the test case passes.

Please test it with real program and you'll see crashes and garbage returned.

Re: [PATCH bpf-next] bpf/verifier: enable ctx + const + 0.

[Daniel Borkmann]

On 05/02/2018 06:52 AM, Alexei Starovoitov wrote:
> On Tue, May 01, 2018 at 09:35:29PM -0700, William Tu wrote:
>>
>>> How did you test this patch?
>>>
>> Without the patch, the test case will fail.
>> With the patch, the test case passes.
> 
> Please test it with real program and you'll see crashes and garbage returned.

+1, *convert_ctx_access() use bpf_insn's off to determine what to rewrite,
so this is definitely buggy, and wasn't properly tested as it should have
been. The test case is also way too simple, just the LDX and then doing a
return 0 will get you past verifier, but won't give you anything in terms
of runtime testing that test_verifier is doing. A single test case for a
non trivial verifier change like this is also _completely insufficient_,
this really needs to test all sort of weird corner cases (involving out of
bounds accesses, overflows, etc).

Re: [PATCH bpf-next] bpf/verifier: enable ctx + const + 0.

[William Tu]

On Wed, May 2, 2018 at 1:29 AM, Daniel Borkmann <daniel@iogearbox.net> wrote:
> On 05/02/2018 06:52 AM, Alexei Starovoitov wrote:
>> On Tue, May 01, 2018 at 09:35:29PM -0700, William Tu wrote:
>>>
>>>> How did you test this patch?
>>>>
>>> Without the patch, the test case will fail.
>>> With the patch, the test case passes.
>>
>> Please test it with real program and you'll see crashes and garbage returned.
>
> +1, *convert_ctx_access() use bpf_insn's off to determine what to rewrite,
> so this is definitely buggy, and wasn't properly tested as it should have
> been. The test case is also way too simple, just the LDX and then doing a
> return 0 will get you past verifier, but won't give you anything in terms
> of runtime testing that test_verifier is doing. A single test case for a
> non trivial verifier change like this is also _completely insufficient_,
> this really needs to test all sort of weird corner cases (involving out of
> bounds accesses, overflows, etc).

Thanks, now I understand.
It's much more complicated than I thought.

William

Re: [PATCH bpf-next] bpf/verifier: enable ctx + const + 0.

[Jakub Kicinski]

On Wed, 2 May 2018 10:54:56 -0700, William Tu wrote:
> On Wed, May 2, 2018 at 1:29 AM, Daniel Borkmann <daniel@iogearbox.net> wrote:
> > On 05/02/2018 06:52 AM, Alexei Starovoitov wrote:  
> >> On Tue, May 01, 2018 at 09:35:29PM -0700, William Tu wrote:  
> >> Please test it with real program and you'll see crashes and garbage returned.  
> >
> > +1, *convert_ctx_access() use bpf_insn's off to determine what to rewrite,
> > so this is definitely buggy, and wasn't properly tested as it should have
> > been. The test case is also way too simple, just the LDX and then doing a
> > return 0 will get you past verifier, but won't give you anything in terms
> > of runtime testing that test_verifier is doing. A single test case for a
> > non trivial verifier change like this is also _completely insufficient_,
> > this really needs to test all sort of weird corner cases (involving out of
> > bounds accesses, overflows, etc).  
> 
> Thanks, now I understand.
> It's much more complicated than I thought.

FWIW NFP JIT would also have to be updated, similarly to
*convert_ctx_access() in mem_ldx_skb()/mem_ldx_xdp() we are currently
looking at insn.off.  In case you find a way to solve this.. :)