BPF verification error when trying to extract SNI from TLS packet

Question

I am trying to get the server name from the SNI extension of a TLS hello packet in a XDP program. When I try to load it, I get the following error from the BPF verifier: math between pkt pointer and register with unbounded min value is not allowed

struct server_name {
    char server_name[256];
};

struct extension {
    __u16 type;
    __u16 len;
} __attribute__((packed));

struct sni_extension {
    __u16 list_len;
    __u8 type;
    __u16 len;
} __attribute__((packed));

#define SERVER_NAME_EXTENSION 0

SEC("xdp")
int collect_ips_prog(struct xdp_md *ctx) {
    char *data_end = (char *)(long)ctx->data_end;
    char *data = (char *)(long)ctx->data;

    if (data_end < (data + sizeof(__u16))) {
        goto end;
    }

    __u16 extension_method_len = __bpf_htons(*(__u16 *) data);

    data += sizeof(__u16);

    for(int i = 0; i < extension_method_len; i += sizeof(struct extension)) { // A
        if (data_end < (data + sizeof(struct extension))) {
            goto end;
        }

        struct extension *ext = (struct extension *) data;

        data += sizeof(struct extension);

        if (ext->type == SERVER_NAME_EXTENSION) {
            struct server_name sn;

            if (data_end < (data + sizeof(struct sni_extension))) {
                goto end;
            }

            struct sni_extension *sni = (struct sni_extension *) data;

            data += sizeof(struct sni_extension);

            __u16 server_name_len = __bpf_htons(sni->len);

            for(int sn_idx = 0; sn_idx < server_name_len; sn_idx++) {
                if (data_end < data + sn_idx) {
                    goto end;
                }

                if (sn.server_name + sizeof(struct server_name) < sn.server_name + sn_idx) {
                    goto end;
                }

                sn.server_name[sn_idx] = data[sn_idx];
            }

            sn.server_name[server_name_len] = 0;
            goto end;
        }

        volatile int ext_len = __bpf_htons(ext->len);

        if (ext_len < 0) {
            goto end;
        }

        data += ext_len;
        i += ext_len; // B
    } // C

end:
    return XDP_PASS;
}

Ignore that data does not point to the beginning of the extension length field of a TLS packet; I did not include the code for getting to this field because the above code is enough to reproduce the issue I'm seeing.

I get this error when I attempt to load this program:

19: R0=pkt(id=0,off=2,r=6,imm=0) R1=inv(id=0) R2=pkt_end(id=0,off=0,imm=0) R3=inv0 R4=inv17179869184 R5_w=pkt(id=0,off=6,r=6,imm=0) R6_w=inv(id=0,umax_value=255,var_off=(0x0; 0xff)) R7_w=inv(id=0) R10=fp0
; __u16 ext_len = __bpf_htons(ext->len);
19: (71) r6 = *(u8 *)(r0 +2)
20: R0=pkt(id=0,off=2,r=6,imm=0) R1=inv(id=0) R2=pkt_end(id=0,off=0,imm=0) R3=inv0 R4=inv17179869184 R5_w=pkt(id=0,off=6,r=6,imm=0) R6_w=inv(id=0,umax_value=255,var_off=(0x0; 0xff)) R7_w=inv(id=0) R10=fp0
20: (71) r0 = *(u8 *)(r0 +3)
21: R0_w=inv(id=0,umax_value=255,var_off=(0x0; 0xff)) R1=inv(id=0) R2=pkt_end(id=0,off=0,imm=0) R3=inv0 R4=inv17179869184 R5_w=pkt(id=0,off=6,r=6,imm=0) R6_w=inv(id=0,umax_value=255,var_off=(0x0; 0xff)) R7_w=inv(id=0) R10=fp0
21: (67) r0 <<= 8
22: R0_w=inv(id=0,umax_value=65280,var_off=(0x0; 0xff00)) R1=inv(id=0) R2=pkt_end(id=0,off=0,imm=0) R3=inv0 R4=inv17179869184 R5_w=pkt(id=0,off=6,r=6,imm=0) R6_w=inv(id=0,umax_value=255,var_off=(0x0; 0xff)) R7_w=inv(id=0) R10=fp0
22: (4f) r0 |= r6
23: R0_w=inv(id=0) R1=inv(id=0) R2=pkt_end(id=0,off=0,imm=0) R3=inv0 R4=inv17179869184 R5_w=pkt(id=0,off=6,r=6,imm=0) R6_w=inv(id=0,umax_value=255,var_off=(0x0; 0xff)) R7_w=inv(id=0) R10=fp0
23: (dc) r0 = be16 r0
24: R0_w=inv(id=0) R1=inv(id=0) R2=pkt_end(id=0,off=0,imm=0) R3=inv0 R4=inv17179869184 R5_w=pkt(id=0,off=6,r=6,imm=0) R6_w=inv(id=0,umax_value=255,var_off=(0x0; 0xff)) R7_w=inv(id=0) R10=fp0
; if (data_end < (data + ext_len)) {
24: (0f) r5 += r0
last_idx 24 first_idx 12
regs=1 stack=0 before 23: (dc) r0 = be16 r0
regs=1 stack=0 before 22: (4f) r0 |= r6
regs=41 stack=0 before 21: (67) r0 <<= 8
regs=41 stack=0 before 20: (71) r0 = *(u8 *)(r0 +3)
regs=40 stack=0 before 19: (71) r6 = *(u8 *)(r0 +2)
math between pkt pointer and register with unbounded min value is not allowed
processed 24 insns (limit 1000000) max_states_per_insn 0 total_states 1 peak_states 1 mark_read 1  

If I comment out points A, B, and C, the outer for loop, the program loads successfully. If I comment the if (ext->type == SERVER_NAME_EXTENSION) { block, the program loads successfully. So I'm confused where the error actually is. In general my experience with the BPF verifier has been that commenting out unrelated pieces affects other pieces of code.

I am loading this program using using a Go library, but I get the same error if load the program using xdp-loader: xdp-loader load -m skb -vv -s collect_ips enp0s8 dist/collect_ips.o

When I updated the code as per pchaigno's answer, I get this error:

0: (61) r2 = *(u32 *)(r1 +4)
; char *data = (char *)(long)ctx->data;
1: (61) r1 = *(u32 *)(r1 +0)
; if (data_end < (data + EXTENSION_METHODS_LEN_FIELD_SIZE)) {
2: (bf) r0 = r1
3: (07) r0 += 2
; if (data_end < (data + EXTENSION_METHODS_LEN_FIELD_SIZE)) {
4: (2d) if r0 > r2 goto pc+37
 R0_w=pkt(id=0,off=2,r=2,imm=0) R1_w=pkt(id=0,off=0,r=2,imm=0) R2_w=pkt_end(id=0,off=0,imm=0) R10=fp0
; __u16 extension_methods_len = __bpf_htons(*(__u16 *) data);
5: (69) r1 = *(u16 *)(r1 +0)
; for(int i = 0; i < extension_methods_len; i += sizeof(struct extension)) {
6: (15) if r1 == 0x0 goto pc+35
 R0_w=pkt(id=0,off=2,r=2,imm=0) R1_w=inv(id=0,umax_value=65535,var_off=(0x0; 0xffff)) R2_w=pkt_end(id=0,off=0,imm=0) R10=fp0
7: (dc) r1 = be16 r1
8: (b7) r3 = 0
9: (18) r4 = 0x400000000
; if (data_end < (data + sizeof(struct extension))) {
11: (bf) r5 = r0
12: (07) r5 += 4
; if (data_end < (data + sizeof(struct extension))) {
13: (2d) if r5 > r2 goto pc+28
 R0=pkt(id=0,off=2,r=6,imm=0) R1=inv(id=0) R2=pkt_end(id=0,off=0,imm=0) R3=inv0 R4=inv17179869184 R5_w=pkt(id=0,off=6,r=6,imm=0) R10=fp0
; if (ext->type == SERVER_NAME_EXTENSION) {
14: (71) r6 = *(u8 *)(r0 +0)
15: (71) r7 = *(u8 *)(r0 +1)
16: (67) r7 <<= 8
17: (4f) r7 |= r6
; if (ext->type == SERVER_NAME_EXTENSION) {
18: (15) if r7 == 0x0 goto pc+23
 R0=pkt(id=0,off=2,r=6,imm=0) R1=inv(id=0) R2=pkt_end(id=0,off=0,imm=0) R3=inv0 R4=inv17179869184 R5_w=pkt(id=0,off=6,r=6,imm=0) R6_w=inv(id=0,umax_value=255,var_off=(0x0; 0xff)) R7_w=inv(id=0) R10=fp0
; volatile int ext_len = __bpf_htons(ext->len);
19: (71) r6 = *(u8 *)(r0 +2)
20: (71) r0 = *(u8 *)(r0 +3)
21: (67) r0 <<= 8
22: (4f) r0 |= r6
23: (dc) r0 = be16 r0
; volatile int ext_len = __bpf_htons(ext->len);
24: (63) *(u32 *)(r10 -4) = r0
; if (ext_len < 0) {
25: (61) r0 = *(u32 *)(r10 -4)
26: (67) r0 <<= 32
27: (c7) r0 s>>= 32
; if (ext_len < 0) {
28: (65) if r0 s> 0xffffffff goto pc+1

from 28 to 30: R0=inv(id=0,umax_value=2147483647,var_off=(0x0; 0xffffffff)) R1=inv(id=0) R2=pkt_end(id=0,off=0,imm=0) R3=inv0 R4=inv17179869184 R5=pkt(id=0,off=6,r=6,imm=0) R6=inv(id=0,umax_value=255,var_off=(0x0; 0xff)) R7=inv(id=0) R10=fp0 fp-8=mmmm????
; data += ext_len;
30: (61) r0 = *(u32 *)(r10 -4)
; i += ext_len;
31: (61) r6 = *(u32 *)(r10 -4)
; i += ext_len;
32: (0f) r3 += r6
; for(int i = 0; i < extension_methods_len; i += sizeof(struct extension)) {
33: (67) r3 <<= 32
34: (0f) r3 += r4
35: (c7) r3 s>>= 32
; for(int i = 0; i < extension_methods_len; i += sizeof(struct extension)) {
36: (7d) if r3 s>= r1 goto pc+5
 R0=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff)) R1=inv(id=0) R2=pkt_end(id=0,off=0,imm=0) R3=inv(id=0,smin_value=-2147483648,smax_value=2147483647) R4=inv17179869184 R5=pkt(id=0,off=6,r=6,imm=0) R6=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff)) R7=inv(id=0) R10=fp0 fp-8=mmmm????
; 
37: (67) r0 <<= 32
38: (c7) r0 s>>= 32
39: (0f) r5 += r0
last_idx 39 first_idx 36
regs=1 stack=0 before 38: (c7) r0 s>>= 32
regs=1 stack=0 before 37: (67) r0 <<= 32
regs=1 stack=0 before 36: (7d) if r3 s>= r1 goto pc+5
 R0_rw=invP(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff)) R1_r=inv(id=0) R2=pkt_end(id=0,off=0,imm=0) R3_rw=inv(id=0,smin_value=-2147483648,smax_value=2147483647) R4=inv17179869184 R5_r=pkt(id=0,off=6,r=6,imm=0) R6_w=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff)) R7=inv(id=0) R10=fp0 fp-8=mmmm????
parent didn't have regs=1 stack=0 marks
last_idx 35 first_idx 28
regs=1 stack=0 before 35: (c7) r3 s>>= 32
regs=1 stack=0 before 34: (0f) r3 += r4
regs=1 stack=0 before 33: (67) r3 <<= 32
regs=1 stack=0 before 32: (0f) r3 += r6
regs=1 stack=0 before 31: (61) r6 = *(u32 *)(r10 -4)
regs=1 stack=0 before 30: (61) r0 = *(u32 *)(r10 -4)
value -2147483648 makes pkt pointer be out of bounds
processed 41 insns (limit 1000000) max_states_per_insn 0 total_states 3 peak_states 3 mark_read 3 

Answer 1

Both change it into int and adding bound check doesn't work for me.
But this work for me:
index &= 134217727u;
One limitation is 134217727u has to be power of 2 minus 1.

Answer 2

TL;DR. From the verifier's point of view, ext_len is unbounded because of how it was computed. To allow you to add this value to the packet pointer, you need to add a new bound check. See below for full explanation.

---

Explanation of the verifier error

22: R0_w=inv(id=0,umax_value=65280,var_off=(0x0; 0xff00)) R1=inv(id=0) R2=pkt_end(id=0,off=0,imm=0) R3=inv0 R4=inv17179869184 R5_w=pkt(id=0,off=6,r=6,imm=0) R6_w=inv(id=0,umax_value=255,var_off=(0x0;     0xff)) R7_w=inv(id=0) R10=fp0
22: (4f) r0 |= r6
23: R0_w=inv(id=0) R1=inv(id=0) R2=pkt_end(id=0,off=0,imm=0) R3=inv0 R4=inv17179869184 R5_w=pkt(id=0,off=6,r=6,imm=0) R6_w=inv(id=0,umax_value=255,var_off=(0x0; 0xff)) R7_w=inv(id=0) R10=fp0
23: (dc) r0 = be16 r0
24: R0_w=inv(id=0) R1=inv(id=0) R2=pkt_end(id=0,off=0,imm=0) R3=inv0 R4=inv17179869184 R5_w=pkt(id=0,off=6,r=6,imm=0) R6_w=inv(id=0,umax_value=255,var_off=(0x0; 0xff)) R7_w=inv(id=0) R10=fp0
; if (data_end < (data + ext_len)) {
24: (0f) r5 += r0
[...]
math between pkt pointer and register with unbounded min value is not allowed

The verifier rejects the program because it sees the addition of an unbounded register (R0) to a register holding the packet pointer (R5). In particular it requires R0 to have a minimum value to be added to the packet pointer. Without that, you may subtract any value from the packet pointer and read arbitrary kernel memory.

Why is R0 unbounded?

Before instruction 22 (r0 |= r6), R0 had bounds (umax_value=65280,var_off=(0x0; 0xff00)). R6 did as well. Unfortunately, the verifier doesn't seem to be able to track those bounds after the logic OR, and loses them. Newer kernel versions may be able to track this better.

Why does adding a 0 minimum bound not work?

@Qeole suggested in comments to add a minimum bounds check for 0:

if (ext_len < 0)
    goto end;

That probably didn't work because ext_len has type __u16 (i.e., unsigned short) so the compiler probably optimize out the check for a negative sign.

Why does adding an upper bound check work?

Adding an upper bound check (e.g., 30000) works because the verifier can deduce a lower signed bound from the upper unsigned bound check.

How to solve it?

The best way to solve this is probably to add a lower bound check as suggested by Quentin. You will however need to make the ext_len variable signed so that the compiler doesn't optimize out the bound check.