Skip to contentSkip to conversation

bpf: fix verifier issue at check_packet_ptr_add

PATCH In review William Tu 3 participants 8 messages Feb 2, 2017 – Feb 3, 2017

Subsystems (4)
lore
Share & tools
lore

William Tu

author
#0 lore raw

PATCH 1/1 bpf: fix verifier issue at check_packet_ptr_add

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

Cc Daniel Borkmann <[email protected]>
---
 kernel/bpf/verifier.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
kernel/bpf/verifier.c +1 -1
index fb3513b..1a754e5 100644
@@ -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;
 		}
Signature · 1 line
2.7.4
maintainer
#1 lore raw
Quoted 9 lines · 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

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!

Quoted 20 lines
Cc Daniel Borkmann <[email protected]>
---
  kernel/bpf/verifier.c | 2 +-
  1 file changed, 1 insertion(+), 1 deletion(-)
kernel/bpf/verifier.c +1 -1
index fb3513b..1a754e5 100644
@@ -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;
  		}
author
#2 lore raw

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

Quoted 43 lines · Daniel Borkmann
Quoted 4 lines · William Tu

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

Quoted 8 lines

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!

Quoted 22 lines
Cc Daniel Borkmann <[email protected]>
---
  kernel/bpf/verifier.c | 2 +-
  1 file changed, 1 insertion(+), 1 deletion(-)
kernel/bpf/verifier.c +1 -1
index fb3513b..1a754e5 100644
@@ -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;
                }
#3 lore raw
Quoted 58 lines · 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

Quoted 5 lines

---
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.

author
#4 lore raw
Quoted 65 lines · Alexei Starovoitov
Quoted 58 lines · 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

Quoted 5 lines

---
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

Quoted 3 lines

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.

Quoted 3 lines

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) {

Quoted 13 lines

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:

kernel/bpf/verifier.c +1 -1
-               if (imm <= 0) {
+               if (imm < 0) {

how is it making the program to pass verifier?

Quoted 2 lines

PS
gentle reminder to avoid top posting.

thanks for letting me know we should avoid top posting.

--William

#5 lore raw
Quoted 3 lines · William Tu

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.

Quoted 12 lines
Quoted 3 lines

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.

kernel/bpf/verifier.c static int check_packet_ptr_add(struct bpf_verifier_env *env, · line 1400

Quoted 2 lines
kernel/bpf/verifier.c +1 -1
-               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.

author
#6 lore raw
Quoted 8 lines · Alexei Starovoitov
Quoted 3 lines · William Tu

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

maintainer
#7 lore raw
In reply to William Tu

On 02/03/2017 06:31 AM, William Tu wrote:
[...]

Quoted 3 lines

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

[...]

kernel/bpf/verifier.c static int check_packet_ptr_add(struct bpf_verifier_env *env, · line 1400

Quoted 10 lines

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.

kernel/bpf/verifier.c +1 -1
-               if (imm <= 0) {
+               if (imm < 0) {

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

Thanks,
Daniel