[PATCH net-next] bpf: fix verifier issue at check_packet_ptr_add

[PATCH net-next] bpf: fix verifier issue at check_packet_ptr_add

[William Tu]

When adding a zero value to the packet pointer, the verifer
reports the following error:

R0=imm0,min_value=0,max_value=0 R1=pkt(id=0,off=0,r=4) R2=pkt_end R3=fp-12 R4=imm4,min_value=4,max_value=4 R5=pkt(id=0,off=4,r=4) R6=ctx R7=imm0,min_value=0,max_value=0 R8=inv,min_value=0,max_value=0 R9=inv R10=fp
269: (bf) r2 = r0
270: (77) r2 >>= 3
271: (bf) r4 = r1
272: (0f) r4 += r2
addition of negative constant to packet pointer is not allowed

Signed-off-by: William Tu <u9012063@gmail.com>
Cc: Daniel Borkmann <daniel@iogearbox.net>
---
 kernel/bpf/verifier.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index fb3513b..1a754e5 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -1397,7 +1397,7 @@ static int check_packet_ptr_add(struct bpf_verifier_env *env,
 		imm = insn->imm;
 
 add_imm:
-		if (imm <= 0) {
+		if (imm < 0) {
 			verbose("addition of negative constant to packet pointer is not allowed\n");
 			return -EACCES;
 		}
-- 
2.7.4

Re: [PATCH net-next] bpf: fix verifier issue at check_packet_ptr_add

[Daniel Borkmann]

On 02/02/2017 08:59 PM, William Tu wrote:
> When adding a zero value to the packet pointer, the verifer
> reports the following error:
>
> R0=imm0,min_value=0,max_value=0 R1=pkt(id=0,off=0,r=4) R2=pkt_end R3=fp-12 R4=imm4,min_value=4,max_value=4 R5=pkt(id=0,off=4,r=4) R6=ctx R7=imm0,min_value=0,max_value=0 R8=inv,min_value=0,max_value=0 R9=inv R10=fp
> 269: (bf) r2 = r0
> 270: (77) r2 >>= 3
> 271: (bf) r4 = r1
> 272: (0f) r4 += r2
> addition of negative constant to packet pointer is not allowed

How do we get here? I mean compiler is not optimizing this away
as the reg is populated differently from various branches? Could
you elaborate more on that resp. how we end up with this? Thanks!

> Signed-off-by: William Tu <u9012063@gmail.com>
> Cc: Daniel Borkmann <daniel@iogearbox.net>
> ---
>   kernel/bpf/verifier.c | 2 +-
>   1 file changed, 1 insertion(+), 1 deletion(-)
>
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index fb3513b..1a754e5 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -1397,7 +1397,7 @@ static int check_packet_ptr_add(struct bpf_verifier_env *env,
>   		imm = insn->imm;
>
>   add_imm:
> -		if (imm <= 0) {
> +		if (imm < 0) {
>   			verbose("addition of negative constant to packet pointer is not allowed\n");
>   			return -EACCES;
>   		}
>

Re: [PATCH net-next] bpf: fix verifier issue at check_packet_ptr_add

[William Tu]

Thanks. below is my program. The verifier fails at line 272, when
writing to ICMP header.
-----
; ebpf_packetEnd = ((void*)(long)skb->data_end);
     206:       r2 = *(u32 *)(r6 + 4)
; ebpf_packetStart = ((void*)(long)skb->data);
     207:       r1 = *(u32 *)(r6 + 0)
...
r10 is "struct hd" at local stack
r1 is skb->data
...
; if (hd.icmp.ebpf_valid) {
     261:       r4 = *(u64 *)(r10 - 40)
     262:       if r4 == 0 goto 29
; if (ebpf_packetEnd < ebpf_packetStart + BYTES(ebpf_packetOffsetInBits + 32)) {
     263:       r4 = r0
     264:       r4 += 32
     265:       r4 >>= 3
     266:       r5 = r1
     267:       r5 += r4
     268:       if r5 > r2 goto 23
; write_byte(ebpf_packetStart, BYTES(ebpf_packetOffsetInBits) + 0,
(ebpf_byte) << 0);
     269:       r2 = r0
     270:       r2 >>= 3
     271:       r4 = r1
     272:       r4 += r2
     273:       r2 = *(u64 *)(r10 - 80)
     274:       *(u8 *)(r4 + 0) = r2

verifier log
========
from 208 to 260: R0=inv,min_value=0,max_value=0 R1=pkt(id=0,off=0,r=0)
R2=pkt_end R3=fp-12 R6=ctx R7=imm0,min_value=0,max_value=0
R8=inv,min_value=0,max_value=0 R9=inv R10=fp
260: (bf) r0 = r7
261: (79) r4 = *(u64 *)(r10 -40)
262: (15) if r4 == 0x0 goto pc+29
 R0=imm0,min_value=0,max_value=0 R1=pkt(id=0,off=0,r=0) R2=pkt_end
R3=fp-12 R4=inv R6=ctx R7=imm0,min_value=0,max_value=0
R8=inv,min_value=0,max_value=0 R9=inv R10=fp
263: (bf) r4 = r0
264: (07) r4 += 32
265: (77) r4 >>= 3
266: (bf) r5 = r1
267: (0f) r5 += r4
268: (2d) if r5 > r2 goto pc+23
 R0=imm0,min_value=0,max_value=0 R1=pkt(id=0,off=0,r=4) R2=pkt_end
R3=fp-12 R4=imm4,min_value=4,max_value=4 R5=pkt(id=0,off=4,r=4) R6=ctx
R7=imm0,min_value=0,max_value=0 R8=inv,min_value=0,max_value=0 R9=inv
R10=fp
269: (bf) r2 = r0
270: (77) r2 >>= 3
271: (bf) r4 = r1
272: (0f) r4 += r2
273: (79) r2 = *(u64 *)(r10 -80)
274: (73) *(u8 *)(r4 +0) = r2

---
The full C source code, llvm-objdump, and verifier log.
https://gist.github.com/williamtu/abaeb11563872508d47cfabed23ac9ea
https://gist.github.com/williamtu/3e308a14c5795c82d516f934be0560cc
https://gist.github.com/williamtu/1ae888cea019d065eab3057f74d38905#file-gistfile1-txt

On Thu, Feb 2, 2017 at 3:46 PM, Daniel Borkmann <daniel@iogearbox.net> wrote:
> On 02/02/2017 08:59 PM, William Tu wrote:
>>
>> When adding a zero value to the packet pointer, the verifer
>> reports the following error:
>>
>> R0=imm0,min_value=0,max_value=0 R1=pkt(id=0,off=0,r=4) R2=pkt_end R3=fp-12
>> R4=imm4,min_value=4,max_value=4 R5=pkt(id=0,off=4,r=4) R6=ctx
>> R7=imm0,min_value=0,max_value=0 R8=inv,min_value=0,max_value=0 R9=inv R10=fp
>> 269: (bf) r2 = r0
>> 270: (77) r2 >>= 3
>> 271: (bf) r4 = r1
>> 272: (0f) r4 += r2
>> addition of negative constant to packet pointer is not allowed
>
>
> How do we get here? I mean compiler is not optimizing this away
> as the reg is populated differently from various branches? Could
> you elaborate more on that resp. how we end up with this? Thanks!
>
>
>> Signed-off-by: William Tu <u9012063@gmail.com>
>> Cc: Daniel Borkmann <daniel@iogearbox.net>
>> ---
>>   kernel/bpf/verifier.c | 2 +-
>>   1 file changed, 1 insertion(+), 1 deletion(-)
>>
>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
>> index fb3513b..1a754e5 100644
>> --- a/kernel/bpf/verifier.c
>> +++ b/kernel/bpf/verifier.c
>> @@ -1397,7 +1397,7 @@ static int check_packet_ptr_add(struct
>> bpf_verifier_env *env,
>>                 imm = insn->imm;
>>
>>   add_imm:
>> -               if (imm <= 0) {
>> +               if (imm < 0) {
>>                         verbose("addition of negative constant to packet
>> pointer is not allowed\n");
>>                         return -EACCES;
>>                 }
>>
>

Re: [PATCH net-next] bpf: fix verifier issue at check_packet_ptr_add

[Alexei Starovoitov]

On Thu, Feb 02, 2017 at 07:26:44PM -0800, William Tu wrote:
> Thanks. below is my program. The verifier fails at line 272, when
> writing to ICMP header.
> -----
> ; ebpf_packetEnd = ((void*)(long)skb->data_end);
>      206:       r2 = *(u32 *)(r6 + 4)
> ; ebpf_packetStart = ((void*)(long)skb->data);
>      207:       r1 = *(u32 *)(r6 + 0)
> ...
> r10 is "struct hd" at local stack
> r1 is skb->data
> ...
> ; if (hd.icmp.ebpf_valid) {
>      261:       r4 = *(u64 *)(r10 - 40)
>      262:       if r4 == 0 goto 29
> ; if (ebpf_packetEnd < ebpf_packetStart + BYTES(ebpf_packetOffsetInBits + 32)) {
>      263:       r4 = r0
>      264:       r4 += 32
>      265:       r4 >>= 3
>      266:       r5 = r1
>      267:       r5 += r4
>      268:       if r5 > r2 goto 23
> ; write_byte(ebpf_packetStart, BYTES(ebpf_packetOffsetInBits) + 0,
> (ebpf_byte) << 0);
>      269:       r2 = r0
>      270:       r2 >>= 3
>      271:       r4 = r1
>      272:       r4 += r2
>      273:       r2 = *(u64 *)(r10 - 80)
>      274:       *(u8 *)(r4 + 0) = r2
> 
> verifier log
> ========
> from 208 to 260: R0=inv,min_value=0,max_value=0 R1=pkt(id=0,off=0,r=0)
> R2=pkt_end R3=fp-12 R6=ctx R7=imm0,min_value=0,max_value=0
> R8=inv,min_value=0,max_value=0 R9=inv R10=fp
> 260: (bf) r0 = r7
> 261: (79) r4 = *(u64 *)(r10 -40)
> 262: (15) if r4 == 0x0 goto pc+29
>  R0=imm0,min_value=0,max_value=0 R1=pkt(id=0,off=0,r=0) R2=pkt_end
> R3=fp-12 R4=inv R6=ctx R7=imm0,min_value=0,max_value=0
> R8=inv,min_value=0,max_value=0 R9=inv R10=fp
> 263: (bf) r4 = r0
> 264: (07) r4 += 32
> 265: (77) r4 >>= 3
> 266: (bf) r5 = r1
> 267: (0f) r5 += r4
> 268: (2d) if r5 > r2 goto pc+23
>  R0=imm0,min_value=0,max_value=0 R1=pkt(id=0,off=0,r=4) R2=pkt_end
> R3=fp-12 R4=imm4,min_value=4,max_value=4 R5=pkt(id=0,off=4,r=4) R6=ctx
> R7=imm0,min_value=0,max_value=0 R8=inv,min_value=0,max_value=0 R9=inv
> R10=fp
> 269: (bf) r2 = r0
> 270: (77) r2 >>= 3
> 271: (bf) r4 = r1
> 272: (0f) r4 += r2
> 273: (79) r2 = *(u64 *)(r10 -80)
> 274: (73) *(u8 *)(r4 +0) = r2
> 
> ---
> The full C source code, llvm-objdump, and verifier log.
> https://gist.github.com/williamtu/abaeb11563872508d47cfabed23ac9ea
> https://gist.github.com/williamtu/3e308a14c5795c82d516f934be0560cc
> https://gist.github.com/williamtu/1ae888cea019d065eab3057f74d38905#file-gistfile1-txt

thanks for sharing.
the C program looks auto-generated? Just curious what did you
use to do it?

The line 272 is r4 += r2
where R4=imm4 and R2=pkt_end
Right now verifier doesn't accept any arithmetic with pkt_end,
since it expects the programs to have cannonical form of
if (ptr > pkt_end)
  goto fail;

Even if we add it, I'm not sure what 'pkt_end + 4' suppose to do.
It's a pointer after the valid packet range.

I'm the most puzzled with the diff:
-               if (imm <= 0) {
+               if (imm < 0) {
how is it making the program to pass verifier?

PS
gentle reminder to avoid top posting.

Re: [PATCH net-next] bpf: fix verifier issue at check_packet_ptr_add

[William Tu]

On Thu, Feb 2, 2017 at 7:46 PM, Alexei Starovoitov
<alexei.starovoitov@gmail.com> wrote:
> On Thu, Feb 02, 2017 at 07:26:44PM -0800, William Tu wrote:
>> Thanks. below is my program. The verifier fails at line 272, when
>> writing to ICMP header.
>> -----
>> ; ebpf_packetEnd = ((void*)(long)skb->data_end);
>>      206:       r2 = *(u32 *)(r6 + 4)
>> ; ebpf_packetStart = ((void*)(long)skb->data);
>>      207:       r1 = *(u32 *)(r6 + 0)
>> ...
>> r10 is "struct hd" at local stack
>> r1 is skb->data
>> ...
>> ; if (hd.icmp.ebpf_valid) {
>>      261:       r4 = *(u64 *)(r10 - 40)
>>      262:       if r4 == 0 goto 29
>> ; if (ebpf_packetEnd < ebpf_packetStart + BYTES(ebpf_packetOffsetInBits + 32)) {
>>      263:       r4 = r0
>>      264:       r4 += 32
>>      265:       r4 >>= 3
>>      266:       r5 = r1
>>      267:       r5 += r4
>>      268:       if r5 > r2 goto 23
>> ; write_byte(ebpf_packetStart, BYTES(ebpf_packetOffsetInBits) + 0,
>> (ebpf_byte) << 0);
>>      269:       r2 = r0
>>      270:       r2 >>= 3
>>      271:       r4 = r1
>>      272:       r4 += r2
>>      273:       r2 = *(u64 *)(r10 - 80)
>>      274:       *(u8 *)(r4 + 0) = r2
>>
>> verifier log
>> ========
>> from 208 to 260: R0=inv,min_value=0,max_value=0 R1=pkt(id=0,off=0,r=0)
>> R2=pkt_end R3=fp-12 R6=ctx R7=imm0,min_value=0,max_value=0
>> R8=inv,min_value=0,max_value=0 R9=inv R10=fp
>> 260: (bf) r0 = r7
>> 261: (79) r4 = *(u64 *)(r10 -40)
>> 262: (15) if r4 == 0x0 goto pc+29
>>  R0=imm0,min_value=0,max_value=0 R1=pkt(id=0,off=0,r=0) R2=pkt_end
>> R3=fp-12 R4=inv R6=ctx R7=imm0,min_value=0,max_value=0
>> R8=inv,min_value=0,max_value=0 R9=inv R10=fp
>> 263: (bf) r4 = r0
>> 264: (07) r4 += 32
>> 265: (77) r4 >>= 3
>> 266: (bf) r5 = r1
>> 267: (0f) r5 += r4
>> 268: (2d) if r5 > r2 goto pc+23
>>  R0=imm0,min_value=0,max_value=0 R1=pkt(id=0,off=0,r=4) R2=pkt_end
>> R3=fp-12 R4=imm4,min_value=4,max_value=4 R5=pkt(id=0,off=4,r=4) R6=ctx
>> R7=imm0,min_value=0,max_value=0 R8=inv,min_value=0,max_value=0 R9=inv
>> R10=fp
>> 269: (bf) r2 = r0
>> 270: (77) r2 >>= 3
>> 271: (bf) r4 = r1
>> 272: (0f) r4 += r2
>> 273: (79) r2 = *(u64 *)(r10 -80)
>> 274: (73) *(u8 *)(r4 +0) = r2
>>
>> ---
>> The full C source code, llvm-objdump, and verifier log.
>> https://gist.github.com/williamtu/abaeb11563872508d47cfabed23ac9ea
>> https://gist.github.com/williamtu/3e308a14c5795c82d516f934be0560cc
>> https://gist.github.com/williamtu/1ae888cea019d065eab3057f74d38905#file-gistfile1-txt
>
> thanks for sharing.
> the C program looks auto-generated? Just curious what did you
> use to do it?

Yes, this is auto-generated. We want to use P4 2016 as front end to
generate ebpf for XDP.

>
> The line 272 is r4 += r2
> where R4=imm4 and R2=pkt_end

R2 is no longer pkt_end, it's R2 == R0 == 0
269: (bf) r2 = r0
270: (77) r2 >>= 3
271: (bf) r4 = r1
272: (0f) r4 += r2

So at line 272, it's pkt_ptr = pkt_ptr + 0
thus the following fix works for us.
-               if (imm <= 0) {
+               if (imm < 0) {

> Right now verifier doesn't accept any arithmetic with pkt_end,
> since it expects the programs to have cannonical form of
> if (ptr > pkt_end)
>   goto fail;
>
> Even if we add it, I'm not sure what 'pkt_end + 4' suppose to do.
> It's a pointer after the valid packet range.
>
> I'm the most puzzled with the diff:
> -               if (imm <= 0) {
> +               if (imm < 0) {
> how is it making the program to pass verifier?
>
> PS
> gentle reminder to avoid top posting.
thanks for letting me know we should avoid top posting.

--William

Re: [PATCH net-next] bpf: fix verifier issue at check_packet_ptr_add

[Alexei Starovoitov]

On Thu, Feb 02, 2017 at 09:31:06PM -0800, William Tu wrote:
> 
> Yes, this is auto-generated. We want to use P4 2016 as front end to
> generate ebpf for XDP.

P4 2016 front-end ? is it public? Is there a 2017 version? ;)
just curious.

> >
> > The line 272 is r4 += r2
> > where R4=imm4 and R2=pkt_end
> 
> R2 is no longer pkt_end, it's R2 == R0 == 0
> 269: (bf) r2 = r0
> 270: (77) r2 >>= 3
> 271: (bf) r4 = r1
> 272: (0f) r4 += r2
> 
> So at line 272, it's pkt_ptr = pkt_ptr + 0
> thus the following fix works for us.
> -               if (imm <= 0) {
> +               if (imm < 0) {

got it. I forgot that we have:
  if (src_reg->type == CONST_IMM) {
          /* pkt_ptr += reg where reg is known constant */
          imm = src_reg->imm;
          goto add_imm;
  }
and got confused by if (BPF_SRC(insn->code) == BPF_K) bit.
Thanks for explaining!
Could you respin with the extra test for it in the test_verifier.c ?
Since it's a rare case, would be good to keep it working.

Re: [PATCH net-next] bpf: fix verifier issue at check_packet_ptr_add

[Daniel Borkmann]

On 02/03/2017 06:31 AM, William Tu wrote:
[...]
> Yes, this is auto-generated. We want to use P4 2016 as front end to
> generate ebpf for XDP.
>
[...]
> R2 is no longer pkt_end, it's R2 == R0 == 0
> 269: (bf) r2 = r0
> 270: (77) r2 >>= 3
> 271: (bf) r4 = r1
> 272: (0f) r4 += r2
>
> So at line 272, it's pkt_ptr = pkt_ptr + 0
> thus the following fix works for us.
> -               if (imm <= 0) {
> +               if (imm < 0) {

Okay, makes sense. I'll wait with ACK for your respin with kselftest
case.

Thanks,
Daniel

Re: [PATCH net-next] bpf: fix verifier issue at check_packet_ptr_add

[William Tu]

On Thu, Feb 2, 2017 at 10:19 PM, Alexei Starovoitov
<alexei.starovoitov@gmail.com> wrote:
> On Thu, Feb 02, 2017 at 09:31:06PM -0800, William Tu wrote:
>>
>> Yes, this is auto-generated. We want to use P4 2016 as front end to
>> generate ebpf for XDP.
>
> P4 2016 front-end ? is it public? Is there a 2017 version? ;)
> just curious.
>
the P4_16 is the latest version.
https://github.com/p4lang/p4c
it has ebpf backend for tc, we want to add ebpf backend for xdp.

--William