bpf: fix verifier issue at check_packet_ptr_add
Subsystems (4)
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
--- kernel/bpf/verifier.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
kernel/bpf/verifier.c +1 -1
@@ -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
Daniel Borkmann
maintainerQuoted 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
Signed-off-by William Tu <[email protected]>Cc Daniel Borkmann <[email protected]>--- kernel/bpf/verifier.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)kernel/bpf/verifier.c +1
-1@@ -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 ; }
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) = r2verifier 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 allowedHow 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
Signed-off-by William Tu <[email protected]>Cc Daniel Borkmann <[email protected]>--- kernel/bpf/verifier.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)kernel/bpf/verifier.c +1
-1@@ -1397,7 +1397,7 @@ static int check_packet_ptr_add(structbpf_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; }
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 isskb->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) = r2verifier 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 ==0x0goto 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.
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 isskb->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) = r2verifier 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 ==0x0goto 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) = r2Quoted 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
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_endR2 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 += r2So 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.
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
Daniel Borkmann
maintainerOn 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 += r2So 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