BPF verifier fails because of invalid access to 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: invalid access to packet

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)) {
        if (data_end < (data + sizeof(struct extension))) {
            goto end;
        }

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

        data += sizeof(struct extension);

        ///////////////////// (A) ////////////////////
        if (data_end < ((char *) ext) + sizeof(struct extension)) {
            goto end;
        }

        if (ext->type == SERVER_NAME_EXTENSION) { // Error happens here
            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;
        }

        __u16 ext_len = __bpf_htons(ext->len);

        if (ext_len > 30000) {
            goto end;
        }

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

        data += ext_len;
        i += ext_len;
    }

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.

Here is the end of the error log when I attempt to load this program. The error at the end happens at if (ext->type == SERVER_NAME_EXTENSION) {:

from 31 to 12: R0_w=pkt(id=14,off=58,r=0,umax_value=42000,var_off=(0x0; 0xffffffff)) R1=inv(id=0) R2=pkt_end(id=0,off=0,imm=0) R3_w=inv(id=0,umin_value=56,umax_value=42056,var_off=(0x0; 0xffff),s32_min_value=0,s32_max_value=65535,u32_max_value=65535) R4=inv17179869184 R5_w=pkt(id=14,off=58,r=0,umax_value=42000,var_off=(0x0; 0xffffffff)) R6_w=inv(id=0,umax_value=255,var_off=(0x0; 0xff)) R7_w=inv(id=0) R10=fp0
; if (data_end < (data + sizeof(struct extension))) {
12: (07) r5 += 4
; if (data_end < (data + sizeof(struct extension))) {
13: (2d) if r5 > r2 goto pc+18
 R0_w=pkt(id=14,off=58,r=62,umax_value=42000,var_off=(0x0; 0xffffffff)) R1=inv(id=0) R2=pkt_end(id=0,off=0,imm=0) R3_w=inv(id=0,umin_value=56,umax_value=42056,var_off=(0x0; 0xffff),s32_min_value=0,s32_max_value=65535,u32_max_value=65535) R4=inv17179869184 R5_w=pkt(id=14,off=62,r=62,umax_value=42000,var_off=(0x0; 0xffffffff)) R6_w=inv(id=0,umax_value=255,var_off=(0x0; 0xff)) R7_w=inv(id=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+13
 R0_w=pkt(id=14,off=58,r=62,umax_value=42000,var_off=(0x0; 0xffffffff)) R1=inv(id=0) R2=pkt_end(id=0,off=0,imm=0) R3_w=inv(id=0,umin_value=56,umax_value=42056,var_off=(0x0; 0xffff),s32_min_value=0,s32_max_value=65535,u32_max_value=65535) R4=inv17179869184 R5_w=pkt(id=14,off=62,r=62,umax_value=42000,var_off=(0x0; 0xffffffff)) 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: (71) r0 = *(u8 *)(r0 +3)
21: (67) r0 <<= 8
22: (4f) r0 |= r6
23: (dc) r0 = be16 r0
; if (ext_len > 3000) {
24: (25) if r0 > 0xbb8 goto pc+7
 R0_w=inv(id=0,umax_value=3000,var_off=(0x0; 0xffffffff)) R1=inv(id=0) R2=pkt_end(id=0,off=0,imm=0) R3_w=inv(id=0,umin_value=56,umax_value=42056,var_off=(0x0; 0xffff),s32_min_value=0,s32_max_value=65535,u32_max_value=65535) R4=inv17179869184 R5_w=pkt(id=14,off=62,r=62,umax_value=42000,var_off=(0x0; 0xffffffff)) R6_w=inv(id=0,umax_value=255,var_off=(0x0; 0xff)) R7_w=inv(id=0) R10=fp0
25: (0f) r5 += r0
last_idx 25 first_idx 31
regs=1 stack=0 before 24: (25) if r0 > 0xbb8 goto pc+7
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)
26: (0f) r3 += r0
; for(int i = 0; i < extension_methods_len; i += sizeof(struct extension)) {
27: (67) r3 <<= 32
28: (0f) r3 += r4
29: (c7) r3 s>>= 32
30: (bf) r0 = r5
; for(int i = 0; i < extension_methods_len; i += sizeof(struct extension)) {
31: (6d) if r1 s> r3 goto pc-20

from 31 to 12: R0_w=pkt(id=15,off=62,r=0,umax_value=45000,var_off=(0x0; 0xffffffff)) R1=inv(id=0) R2=pkt_end(id=0,off=0,imm=0) R3_w=inv(id=0,umin_value=60,umax_value=45060,var_off=(0x0; 0xffff),s32_min_value=0,s32_max_value=65535,u32_max_value=65535) R4=inv17179869184 R5_w=pkt(id=15,off=62,r=0,umax_value=45000,var_off=(0x0; 0xffffffff)) R6_w=inv(id=0,umax_value=255,var_off=(0x0; 0xff)) R7_w=inv(id=0) R10=fp0
; if (data_end < (data + sizeof(struct extension))) {
12: (07) r5 += 4
; if (data_end < (data + sizeof(struct extension))) {
13: (2d) if r5 > r2 goto pc+18
 R0_w=pkt(id=15,off=62,r=66,umax_value=45000,var_off=(0x0; 0xffffffff)) R1=inv(id=0) R2=pkt_end(id=0,off=0,imm=0) R3_w=inv(id=0,umin_value=60,umax_value=45060,var_off=(0x0; 0xffff),s32_min_value=0,s32_max_value=65535,u32_max_value=65535) R4=inv17179869184 R5_w=pkt(id=15,off=66,r=66,umax_value=45000,var_off=(0x0; 0xffffffff)) R6_w=inv(id=0,umax_value=255,var_off=(0x0; 0xff)) R7_w=inv(id=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+13
 R0_w=pkt(id=15,off=62,r=66,umax_value=45000,var_off=(0x0; 0xffffffff)) R1=inv(id=0) R2=pkt_end(id=0,off=0,imm=0) R3_w=inv(id=0,umin_value=60,umax_value=45060,var_off=(0x0; 0xffff),s32_min_value=0,s32_max_value=65535,u32_max_value=65535) R4=inv17179869184 R5_w=pkt(id=15,off=66,r=66,umax_value=45000,var_off=(0x0; 0xffffffff)) 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: (71) r0 = *(u8 *)(r0 +3)
21: (67) r0 <<= 8
22: (4f) r0 |= r6
23: (dc) r0 = be16 r0
; if (ext_len > 3000) {
24: (25) if r0 > 0xbb8 goto pc+7
 R0_w=inv(id=0,umax_value=3000,var_off=(0x0; 0xffffffff)) R1=inv(id=0) R2=pkt_end(id=0,off=0,imm=0) R3_w=inv(id=0,umin_value=60,umax_value=45060,var_off=(0x0; 0xffff),s32_min_value=0,s32_max_value=65535,u32_max_value=65535) R4=inv17179869184 R5_w=pkt(id=15,off=66,r=66,umax_value=45000,var_off=(0x0; 0xffffffff)) R6_w=inv(id=0,umax_value=255,var_off=(0x0; 0xff)) R7_w=inv(id=0) R10=fp0
25: (0f) r5 += r0
last_idx 25 first_idx 31
regs=1 stack=0 before 24: (25) if r0 > 0xbb8 goto pc+7
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)
26: (0f) r3 += r0
; for(int i = 0; i < extension_methods_len; i += sizeof(struct extension)) {
27: (67) r3 <<= 32
28: (0f) r3 += r4
29: (c7) r3 s>>= 32
30: (bf) r0 = r5
; for(int i = 0; i < extension_methods_len; i += sizeof(struct extension)) {
31: (6d) if r1 s> r3 goto pc-20

from 31 to 12: R0_w=pkt(id=16,off=66,r=0,umax_value=48000,var_off=(0x0; 0xffffffff)) R1=inv(id=0) R2=pkt_end(id=0,off=0,imm=0) R3_w=inv(id=0,umin_value=64,umax_value=48064,var_off=(0x0; 0xffff),s32_min_value=0,s32_max_value=65535,u32_max_value=65535) R4=inv17179869184 R5_w=pkt(id=16,off=66,r=0,umax_value=48000,var_off=(0x0; 0xffffffff)) R6_w=inv(id=0,umax_value=255,var_off=(0x0; 0xff)) R7_w=inv(id=0) R10=fp0
; if (data_end < (data + sizeof(struct extension))) {
12: (07) r5 += 4
; if (data_end < (data + sizeof(struct extension))) {
13: (2d) if r5 > r2 goto pc+18
 R0_w=pkt(id=16,off=66,r=70,umax_value=48000,var_off=(0x0; 0xffffffff)) R1=inv(id=0) R2=pkt_end(id=0,off=0,imm=0) R3_w=inv(id=0,umin_value=64,umax_value=48064,var_off=(0x0; 0xffff),s32_min_value=0,s32_max_value=65535,u32_max_value=65535) R4=inv17179869184 R5_w=pkt(id=16,off=70,r=70,umax_value=48000,var_off=(0x0; 0xffffffff)) R6_w=inv(id=0,umax_value=255,var_off=(0x0; 0xff)) R7_w=inv(id=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+13
 R0_w=pkt(id=16,off=66,r=70,umax_value=48000,var_off=(0x0; 0xffffffff)) R1=inv(id=0) R2=pkt_end(id=0,off=0,imm=0) R3_w=inv(id=0,umin_value=64,umax_value=48064,var_off=(0x0; 0xffff),s32_min_value=0,s32_max_value=65535,u32_max_value=65535) R4=inv17179869184 R5_w=pkt(id=16,off=70,r=70,umax_value=48000,var_off=(0x0; 0xffffffff)) 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: (71) r0 = *(u8 *)(r0 +3)
21: (67) r0 <<= 8
22: (4f) r0 |= r6
23: (dc) r0 = be16 r0
; if (ext_len > 3000) {
24: (25) if r0 > 0xbb8 goto pc+7
 R0_w=inv(id=0,umax_value=3000,var_off=(0x0; 0xffffffff)) R1=inv(id=0) R2=pkt_end(id=0,off=0,imm=0) R3_w=inv(id=0,umin_value=64,umax_value=48064,var_off=(0x0; 0xffff),s32_min_value=0,s32_max_value=65535,u32_max_value=65535) R4=inv17179869184 R5_w=pkt(id=16,off=70,r=70,umax_value=48000,var_off=(0x0; 0xffffffff)) R6_w=inv(id=0,umax_value=255,var_off=(0x0; 0xff)) R7_w=inv(id=0) R10=fp0
25: (0f) r5 += r0
last_idx 25 first_idx 31
regs=1 stack=0 before 24: (25) if r0 > 0xbb8 goto pc+7
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)
26: (0f) r3 += r0
; for(int i = 0; i < extension_methods_len; i += sizeof(struct extension)) {
27: (67) r3 <<= 32
28: (0f) r3 += r4
29: (c7) r3 s>>= 32
30: (bf) r0 = r5
; for(int i = 0; i < extension_methods_len; i += sizeof(struct extension)) {
31: (6d) if r1 s> r3 goto pc-20

from 31 to 12: R0_w=pkt(id=17,off=70,r=0,umax_value=51000,var_off=(0x0; 0xffffffff)) R1=inv(id=0) R2=pkt_end(id=0,off=0,imm=0) R3_w=inv(id=0,umin_value=68,umax_value=51068,var_off=(0x0; 0xffff),s32_min_value=0,s32_max_value=65535,u32_max_value=65535) R4=inv17179869184 R5_w=pkt(id=17,off=70,r=0,umax_value=51000,var_off=(0x0; 0xffffffff)) R6_w=inv(id=0,umax_value=255,var_off=(0x0; 0xff)) R7_w=inv(id=0) R10=fp0
; if (data_end < (data + sizeof(struct extension))) {
12: (07) r5 += 4
; if (data_end < (data + sizeof(struct extension))) {
13: (2d) if r5 > r2 goto pc+18
 R0_w=pkt(id=17,off=70,r=74,umax_value=51000,var_off=(0x0; 0xffffffff)) R1=inv(id=0) R2=pkt_end(id=0,off=0,imm=0) R3_w=inv(id=0,umin_value=68,umax_value=51068,var_off=(0x0; 0xffff),s32_min_value=0,s32_max_value=65535,u32_max_value=65535) R4=inv17179869184 R5_w=pkt(id=17,off=74,r=74,umax_value=51000,var_off=(0x0; 0xffffffff)) R6_w=inv(id=0,umax_value=255,var_off=(0x0; 0xff)) R7_w=inv(id=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+13
 R0_w=pkt(id=17,off=70,r=74,umax_value=51000,var_off=(0x0; 0xffffffff)) R1=inv(id=0) R2=pkt_end(id=0,off=0,imm=0) R3_w=inv(id=0,umin_value=68,umax_value=51068,var_off=(0x0; 0xffff),s32_min_value=0,s32_max_value=65535,u32_max_value=65535) R4=inv17179869184 R5_w=pkt(id=17,off=74,r=74,umax_value=51000,var_off=(0x0; 0xffffffff)) 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: (71) r0 = *(u8 *)(r0 +3)
21: (67) r0 <<= 8
22: (4f) r0 |= r6
23: (dc) r0 = be16 r0
; if (ext_len > 3000) {
24: (25) if r0 > 0xbb8 goto pc+7
 R0_w=inv(id=0,umax_value=3000,var_off=(0x0; 0xffffffff)) R1=inv(id=0) R2=pkt_end(id=0,off=0,imm=0) R3_w=inv(id=0,umin_value=68,umax_value=51068,var_off=(0x0; 0xffff),s32_min_value=0,s32_max_value=65535,u32_max_value=65535) R4=inv17179869184 R5_w=pkt(id=17,off=74,r=74,umax_value=51000,var_off=(0x0; 0xffffffff)) R6_w=inv(id=0,umax_value=255,var_off=(0x0; 0xff)) R7_w=inv(id=0) R10=fp0
25: (0f) r5 += r0
last_idx 25 first_idx 31
regs=1 stack=0 before 24: (25) if r0 > 0xbb8 goto pc+7
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)
26: (0f) r3 += r0
; for(int i = 0; i < extension_methods_len; i += sizeof(struct extension)) {
27: (67) r3 <<= 32
28: (0f) r3 += r4
29: (c7) r3 s>>= 32
30: (bf) r0 = r5
; for(int i = 0; i < extension_methods_len; i += sizeof(struct extension)) {
31: (6d) if r1 s> r3 goto pc-20

from 31 to 12: R0=pkt(id=18,off=74,r=0,umax_value=54000,var_off=(0x0; 0xffffffff)) R1=inv(id=0) R2=pkt_end(id=0,off=0,imm=0) R3=inv(id=0,umin_value=72,umax_value=54072,var_off=(0x0; 0xffff),s32_min_value=0,s32_max_value=65535,u32_max_value=65535) R4=inv17179869184 R5=pkt(id=18,off=74,r=0,umax_value=54000,var_off=(0x0; 0xffffffff)) R6=inv(id=0,umax_value=255,var_off=(0x0; 0xff)) R7=inv(id=0) R10=fp0
; if (data_end < (data + sizeof(struct extension))) {
12: (07) r5 += 4
; if (data_end < (data + sizeof(struct extension))) {
13: (2d) if r5 > r2 goto pc+18
 R0=pkt(id=18,off=74,r=78,umax_value=54000,var_off=(0x0; 0xffffffff)) R1=inv(id=0) R2=pkt_end(id=0,off=0,imm=0) R3=inv(id=0,umin_value=72,umax_value=54072,var_off=(0x0; 0xffff),s32_min_value=0,s32_max_value=65535,u32_max_value=65535) R4=inv17179869184 R5_w=pkt(id=18,off=78,r=78,umax_value=54000,var_off=(0x0; 0xffffffff)) R6=inv(id=0,umax_value=255,var_off=(0x0; 0xff)) R7=inv(id=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+13
 R0=pkt(id=18,off=74,r=78,umax_value=54000,var_off=(0x0; 0xffffffff)) R1=inv(id=0) R2=pkt_end(id=0,off=0,imm=0) R3=inv(id=0,umin_value=72,umax_value=54072,var_off=(0x0; 0xffff),s32_min_value=0,s32_max_value=65535,u32_max_value=65535) R4=inv17179869184 R5_w=pkt(id=18,off=78,r=78,umax_value=54000,var_off=(0x0; 0xffffffff)) 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: (71) r0 = *(u8 *)(r0 +3)
21: (67) r0 <<= 8
22: (4f) r0 |= r6
23: (dc) r0 = be16 r0
; if (ext_len > 3000) {
24: (25) if r0 > 0xbb8 goto pc+7
 R0_w=inv(id=0,umax_value=3000,var_off=(0x0; 0xffffffff)) R1=inv(id=0) R2=pkt_end(id=0,off=0,imm=0) R3=inv(id=0,umin_value=72,umax_value=54072,var_off=(0x0; 0xffff),s32_min_value=0,s32_max_value=65535,u32_max_value=65535) R4=inv17179869184 R5_w=pkt(id=18,off=78,r=78,umax_value=54000,var_off=(0x0; 0xffffffff)) R6_w=inv(id=0,umax_value=255,var_off=(0x0; 0xff)) R7_w=inv(id=0) R10=fp0
25: (0f) r5 += r0
last_idx 25 first_idx 31
regs=1 stack=0 before 24: (25) if r0 > 0xbb8 goto pc+7
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)
26: (0f) r3 += r0
; for(int i = 0; i < extension_methods_len; i += sizeof(struct extension)) {
27: (67) r3 <<= 32
28: (0f) r3 += r4
29: (c7) r3 s>>= 32
30: (bf) r0 = r5
; for(int i = 0; i < extension_methods_len; i += sizeof(struct extension)) {
31: (6d) if r1 s> r3 goto pc-20

from 31 to 12: R0_w=pkt(id=19,off=78,r=0,umax_value=57000,var_off=(0x0; 0xffffffff)) R1=inv(id=0) R2=pkt_end(id=0,off=0,imm=0) R3_w=inv(id=0,umin_value=76,umax_value=57076,var_off=(0x0; 0xffff),s32_min_value=0,s32_max_value=65535,u32_max_value=65535) R4=inv17179869184 R5_w=pkt(id=19,off=78,r=0,umax_value=57000,var_off=(0x0; 0xffffffff)) R6_w=inv(id=0,umax_value=255,var_off=(0x0; 0xff)) R7_w=inv(id=0) R10=fp0
; if (data_end < (data + sizeof(struct extension))) {
12: (07) r5 += 4
; if (data_end < (data + sizeof(struct extension))) {
13: (2d) if r5 > r2 goto pc+18
 R0_w=pkt(id=19,off=78,r=82,umax_value=57000,var_off=(0x0; 0xffffffff)) R1=inv(id=0) R2=pkt_end(id=0,off=0,imm=0) R3_w=inv(id=0,umin_value=76,umax_value=57076,var_off=(0x0; 0xffff),s32_min_value=0,s32_max_value=65535,u32_max_value=65535) R4=inv17179869184 R5_w=pkt(id=19,off=82,r=82,umax_value=57000,var_off=(0x0; 0xffffffff)) R6_w=inv(id=0,umax_value=255,var_off=(0x0; 0xff)) R7_w=inv(id=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+13
 R0_w=pkt(id=19,off=78,r=82,umax_value=57000,var_off=(0x0; 0xffffffff)) R1=inv(id=0) R2=pkt_end(id=0,off=0,imm=0) R3_w=inv(id=0,umin_value=76,umax_value=57076,var_off=(0x0; 0xffff),s32_min_value=0,s32_max_value=65535,u32_max_value=65535) R4=inv17179869184 R5_w=pkt(id=19,off=82,r=82,umax_value=57000,var_off=(0x0; 0xffffffff)) 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: (71) r0 = *(u8 *)(r0 +3)
21: (67) r0 <<= 8
22: (4f) r0 |= r6
23: (dc) r0 = be16 r0
; if (ext_len > 3000) {
24: (25) if r0 > 0xbb8 goto pc+7
 R0_w=inv(id=0,umax_value=3000,var_off=(0x0; 0xffffffff)) R1=inv(id=0) R2=pkt_end(id=0,off=0,imm=0) R3_w=inv(id=0,umin_value=76,umax_value=57076,var_off=(0x0; 0xffff),s32_min_value=0,s32_max_value=65535,u32_max_value=65535) R4=inv17179869184 R5_w=pkt(id=19,off=82,r=82,umax_value=57000,var_off=(0x0; 0xffffffff)) R6_w=inv(id=0,umax_value=255,var_off=(0x0; 0xff)) R7_w=inv(id=0) R10=fp0
25: (0f) r5 += r0
last_idx 25 first_idx 31
regs=1 stack=0 before 24: (25) if r0 > 0xbb8 goto pc+7
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)
26: (0f) r3 += r0
; for(int i = 0; i < extension_methods_len; i += sizeof(struct extension)) {
27: (67) r3 <<= 32
28: (0f) r3 += r4
29: (c7) r3 s>>= 32
30: (bf) r0 = r5
; for(int i = 0; i < extension_methods_len; i += sizeof(struct extension)) {
31: (6d) if r1 s> r3 goto pc-20

from 31 to 12: R0_w=pkt(id=20,off=82,r=0,umax_value=60000,var_off=(0x0; 0xffffffff)) R1=inv(id=0) R2=pkt_end(id=0,off=0,imm=0) R3_w=inv(id=0,umin_value=80,umax_value=60080,var_off=(0x0; 0xffff),s32_min_value=0,s32_max_value=65535,u32_max_value=65535) R4=inv17179869184 R5_w=pkt(id=20,off=82,r=0,umax_value=60000,var_off=(0x0; 0xffffffff)) R6_w=inv(id=0,umax_value=255,var_off=(0x0; 0xff)) R7_w=inv(id=0) R10=fp0
; if (data_end < (data + sizeof(struct extension))) {
12: (07) r5 += 4
; if (data_end < (data + sizeof(struct extension))) {
13: (2d) if r5 > r2 goto pc+18
 R0_w=pkt(id=20,off=82,r=86,umax_value=60000,var_off=(0x0; 0xffffffff)) R1=inv(id=0) R2=pkt_end(id=0,off=0,imm=0) R3_w=inv(id=0,umin_value=80,umax_value=60080,var_off=(0x0; 0xffff),s32_min_value=0,s32_max_value=65535,u32_max_value=65535) R4=inv17179869184 R5_w=pkt(id=20,off=86,r=86,umax_value=60000,var_off=(0x0; 0xffffffff)) R6_w=inv(id=0,umax_value=255,var_off=(0x0; 0xff)) R7_w=inv(id=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+13
 R0_w=pkt(id=20,off=82,r=86,umax_value=60000,var_off=(0x0; 0xffffffff)) R1=inv(id=0) R2=pkt_end(id=0,off=0,imm=0) R3_w=inv(id=0,umin_value=80,umax_value=60080,var_off=(0x0; 0xffff),s32_min_value=0,s32_max_value=65535,u32_max_value=65535) R4=inv17179869184 R5_w=pkt(id=20,off=86,r=86,umax_value=60000,var_off=(0x0; 0xffffffff)) 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: (71) r0 = *(u8 *)(r0 +3)
21: (67) r0 <<= 8
22: (4f) r0 |= r6
23: (dc) r0 = be16 r0
; if (ext_len > 3000) {
24: (25) if r0 > 0xbb8 goto pc+7
 R0_w=inv(id=0,umax_value=3000,var_off=(0x0; 0xffffffff)) R1=inv(id=0) R2=pkt_end(id=0,off=0,imm=0) R3_w=inv(id=0,umin_value=80,umax_value=60080,var_off=(0x0; 0xffff),s32_min_value=0,s32_max_value=65535,u32_max_value=65535) R4=inv17179869184 R5_w=pkt(id=20,off=86,r=86,umax_value=60000,var_off=(0x0; 0xffffffff)) R6_w=inv(id=0,umax_value=255,var_off=(0x0; 0xff)) R7_w=inv(id=0) R10=fp0
25: (0f) r5 += r0
last_idx 25 first_idx 31
regs=1 stack=0 before 24: (25) if r0 > 0xbb8 goto pc+7
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)
26: (0f) r3 += r0
; for(int i = 0; i < extension_methods_len; i += sizeof(struct extension)) {
27: (67) r3 <<= 32
28: (0f) r3 += r4
29: (c7) r3 s>>= 32
30: (bf) r0 = r5
; for(int i = 0; i < extension_methods_len; i += sizeof(struct extension)) {
31: (6d) if r1 s> r3 goto pc-20

from 31 to 12: R0_w=pkt(id=21,off=86,r=0,umax_value=63000,var_off=(0x0; 0xffffffff)) R1=inv(id=0) R2=pkt_end(id=0,off=0,imm=0) R3_w=inv(id=0,umin_value=84,umax_value=63084,var_off=(0x0; 0xffff),s32_min_value=0,s32_max_value=65535,u32_max_value=65535) R4=inv17179869184 R5_w=pkt(id=21,off=86,r=0,umax_value=63000,var_off=(0x0; 0xffffffff)) R6_w=inv(id=0,umax_value=255,var_off=(0x0; 0xff)) R7_w=inv(id=0) R10=fp0
; if (data_end < (data + sizeof(struct extension))) {
12: (07) r5 += 4
; if (data_end < (data + sizeof(struct extension))) {
13: (2d) if r5 > r2 goto pc+18
 R0_w=pkt(id=21,off=86,r=90,umax_value=63000,var_off=(0x0; 0xffffffff)) R1=inv(id=0) R2=pkt_end(id=0,off=0,imm=0) R3_w=inv(id=0,umin_value=84,umax_value=63084,var_off=(0x0; 0xffff),s32_min_value=0,s32_max_value=65535,u32_max_value=65535) R4=inv17179869184 R5_w=pkt(id=21,off=90,r=90,umax_value=63000,var_off=(0x0; 0xffffffff)) R6_w=inv(id=0,umax_value=255,var_off=(0x0; 0xff)) R7_w=inv(id=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+13
 R0_w=pkt(id=21,off=86,r=90,umax_value=63000,var_off=(0x0; 0xffffffff)) R1=inv(id=0) R2=pkt_end(id=0,off=0,imm=0) R3_w=inv(id=0,umin_value=84,umax_value=63084,var_off=(0x0; 0xffff),s32_min_value=0,s32_max_value=65535,u32_max_value=65535) R4=inv17179869184 R5_w=pkt(id=21,off=90,r=90,umax_value=63000,var_off=(0x0; 0xffffffff)) 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: (71) r0 = *(u8 *)(r0 +3)
21: (67) r0 <<= 8
22: (4f) r0 |= r6
23: (dc) r0 = be16 r0
; if (ext_len > 3000) {
24: (25) if r0 > 0xbb8 goto pc+7
 R0_w=inv(id=0,umax_value=3000,var_off=(0x0; 0xffffffff)) R1=inv(id=0) R2=pkt_end(id=0,off=0,imm=0) R3_w=inv(id=0,umin_value=84,umax_value=63084,var_off=(0x0; 0xffff),s32_min_value=0,s32_max_value=65535,u32_max_value=65535) R4=inv17179869184 R5_w=pkt(id=21,off=90,r=90,umax_value=63000,var_off=(0x0; 0xffffffff)) R6_w=inv(id=0,umax_value=255,var_off=(0x0; 0xff)) R7_w=inv(id=0) R10=fp0
25: (0f) r5 += r0
last_idx 25 first_idx 31
regs=1 stack=0 before 24: (25) if r0 > 0xbb8 goto pc+7
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)
26: (0f) r3 += r0
; for(int i = 0; i < extension_methods_len; i += sizeof(struct extension)) {
27: (67) r3 <<= 32
28: (0f) r3 += r4
29: (c7) r3 s>>= 32
30: (bf) r0 = r5
; for(int i = 0; i < extension_methods_len; i += sizeof(struct extension)) {
31: (6d) if r1 s> r3 goto pc-20

from 31 to 12: R0_w=pkt(id=22,off=90,r=0,umax_value=66000,var_off=(0x0; 0xffffffff)) R1=inv(id=0) R2=pkt_end(id=0,off=0,imm=0) R3_w=inv(id=0,umin_value=88,umax_value=66088,var_off=(0x0; 0x1ffff),s32_min_value=0,s32_max_value=131071,u32_max_value=131071) R4=inv17179869184 R5_w=pkt(id=22,off=90,r=0,umax_value=66000,var_off=(0x0; 0xffffffff)) R6_w=inv(id=0,umax_value=255,var_off=(0x0; 0xff)) R7_w=inv(id=0) R10=fp0
; if (data_end < (data + sizeof(struct extension))) {
12: (07) r5 += 4
; if (data_end < (data + sizeof(struct extension))) {
13: (2d) if r5 > r2 goto pc+18
 R0_w=pkt(id=22,off=90,r=0,umax_value=66000,var_off=(0x0; 0xffffffff)) R1=inv(id=0) R2=pkt_end(id=0,off=0,imm=0) R3_w=inv(id=0,umin_value=88,umax_value=66088,var_off=(0x0; 0x1ffff),s32_min_value=0,s32_max_value=131071,u32_max_value=131071) R4=inv17179869184 R5_w=pkt(id=22,off=94,r=0,umax_value=66000,var_off=(0x0; 0xffffffff)) R6_w=inv(id=0,umax_value=255,var_off=(0x0; 0xff)) R7_w=inv(id=0) R10=fp0
; if (ext->type == SERVER_NAME_EXTENSION) {
14: (71) r6 = *(u8 *)(r0 +0)
invalid access to packet, off=90 size=1, R0(id=22,off=90,r=0)
R0 offset is outside of the packet
processed 477 insns (limit 1000000) max_states_per_insn 4 total_states 9 peak_states 9 mark_read 2

I would have thought if statement (A) would have been enough to validate the whether ext points to a valid address, although it shouldn't be needed in the first place because of the if (data_end < (data + sizeof(struct extension))) { check.

I get this error when I use __s16 ext_len. I also don't understand the instructions where it's failing at is 14: (71) r6 = *(u8 *)(r0 +0). Then len field is a __u16, so shouldn't it be doing *(u16 *)?

I am running kernel 5.13.0-19-generic.

Could you share the full verifier logs? Also, what kernel version are you running on? — pchaigno, Jan 18 '22 at 18:19
Could you try changing the type of `ext_len` to `int` and the bound check from `ext_len > 30000` to `ext_len < 0`? Based on https://stackoverflow.com/a/70773642/6884590, I think that should fix this issue. — pchaigno, Jan 19 '22 at 15:54
I get ```math between pkt pointer and register with unbounded min value is not allowed``` with those changes. — user2233706, Jan 19 '22 at 16:17
Changing `ext_len` to `int` causes this error since the return type of `__bpf_htons` is 16bit, but `int` is 32bit. Chaning the type to `__s16` gets rid of the math error. But we revert back to `offset is outside of the packet` even with the `ext_len < 0` check — Dylan Reimerink, Jan 19 '22 at 17:08
I updated the [other question](https://stackoverflow.com/questions/70750259) with the logs because the error is the same as that question. — user2233706, Jan 19 '22 at 17:23
Why is the generated code doing ```r6 = *(u8 *)(r0 +0)``` when the value being retrieved is a u16? — user2233706, Jan 19 '22 at 17:36
Because of the `__bpf_htons` function, it reads 2 bytes in host byte order and then shifts them so they are in network order. This is likely not needed since we are reading from bytes which are already in network order — Dylan Reimerink, Jan 19 '22 at 17:45
I discovered the next pieces of the puzzle, if we change the `if (ext_len < 0)` to `if (ext_len < 0 || ext_len > 16)` it no longer breaks. If we limit the upper bound the issue goes away, can't explain why yet. The next issue is that when this happens, that your loops are allowed to continue for to long: `The sequence of 8193 jumps is too complex.` — Dylan Reimerink, Jan 19 '22 at 17:48
That seems to be what's happening as well. I couldn't get the end of the log even when I changed the log size to 2 MB. — user2233706, Jan 19 '22 at 18:03
Let us [continue this discussion in chat](https://chat.stackoverflow.com/rooms/241223/discussion-between-dylan-reimerink-and-user2233706). — Dylan Reimerink, Jan 19 '22 at 18:24

Dylan Reimerink · Accepted Answer · 2022-01-19T19:18:52.543

I think I have found the core of the issue. The verifier tracks a couple of properties about variables which allow it to determine if the program might access data it shouldn't. One of these properties is umax_value which tracks that the max unsigned int value is, which might be dynamic.

Since packets have finite size the verifier asserts that the umax_value of an offset into the packet may never exceed MAX_PACKET_OFF(65536).

Every time the program loops we add ext_len to data, since ext_len is a __u16 its max uint value is 65536 by default. The program limits this to 30000 with the following statement:

if (ext_len > 30000) {
  goto end;
}

However, the umax_value of data accumulates over each iteration. We can see this in the verifier log:

; if (data_end < (data + sizeof(struct extension))) { 13: (2d) if r5 > r2 goto pc+18 R0_w=pkt(id=22,off=90,r=0,umax_value=66000,var_off=(0x0; 0xffffffff)) R1=inv(id=0) R2=pkt_end(id=0,off=0,imm=0) R3_w=inv(id=0,umin_value=88,umax_value=66088,var_off=(0x0; 0x1ffff),s32_min_value=0,s32_max_value=131071,u32_max_value=131071) R4=inv17179869184 R5_w=pkt(id=22,off=94,r=0,umax_value=66000,var_off=(0x0; 0xffffffff)) R6_w=inv(id=0,umax_value=255,var_off=(0x0; 0xff)) R7_w=inv(id=0) R10=fp0 ; if (ext->type == SERVER_NAME_EXTENSION) { 14: (71) r6 = *(u8 *)(r0 +0)

umax_value is larger then 65536, thus the error.

Now, to fix this we need to change the code so data can't exceed 65536. We do this by specifying a maximum amount of iterations(extensions) and setting the max size of each extension. I modified the program to add these constrains, I chose max 32 extensions and max 2048 bytes per extension which seems sane values (32 * 2048 = 65536), these can be changed.

#include <stddef.h>
#include <linux/bpf.h>
#include "./bpf_endian.h"

#define SEC(NAME) __attribute__((section(NAME), used))

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)
{
    void *data_end = (void *)(long)ctx->data_end;
    void *data = (void *)(long)ctx->data;
    void *cursor = (void *)(long)ctx->data;

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

    __s64 extension_method_len = *(__u16 *)cursor;
    if (extension_method_len < 0)
    {
        goto end;
    }

    cursor += sizeof(__u16);

    for (int i = 0; i < 32; i++)
    {
        struct extension *ext;

        if (cursor > extension_method_len + data)
        {
            goto end;
        }

        if (data_end < (cursor + sizeof(*ext)))
        {
            goto end;
        }

        ext = (struct extension *)cursor;

        cursor += sizeof(*ext);

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

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

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

            cursor += sizeof(struct sni_extension);

            __u16 server_name_len = sni->len;

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

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

                sn.server_name[sn_idx] = ((char *)cursor)[sn_idx];
            }

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

        if (ext->len > 2048)
        {
            goto end;
        }

        if (data_end < cursor + ext->len)
        {
            goto end;
        }

        cursor += ext->len;
    }

end:
    return XDP_PASS;
}

The limitation here is obvious, even if we have 31 extensions of just a few bytes, the 32'nd can never be larger than 2048 bytes. There might be a way to track the sum of all extensions so far and check that this sum never exceeds 65536, allowing us to get rid of these "worst-case-senario" constants and check the actual umax_value, but I will leave that as a research topic for someone else.

Thanks, that makes perfect sense. I was thinking about restricting the number of iterations before as well, but my reasoning was why shouldn't this work. — user2233706, Jan 19 '22 at 19:22
Why doesn't the verifier complain about the inner for loop, ```for (int sn_idx = 0; sn_idx < server_name_len; sn_idx++)```? ```server_name_len``` could also be 65K. — user2233706, Jan 19 '22 at 19:31
Not 100% sure, my guess is that because we already know the size of `sni_extension` and `extension` at compile/load time that these values don't contribute to the `umax_value` which is only records the worst case senario at runtime(after the verifier is done running) — Dylan Reimerink, Jan 19 '22 at 19:36
Also, I have to use __bpf_htons on the extensions length. Otherwise, I get garbage. Using __bpf_htons results in a BPF verification error, though. Since a TLS record is at most 16K, I just made sure the length is less than 16K. — user2233706, Jan 19 '22 at 21:11
```if (data_end < cursor + sn_idx)``` inside the inner for loop should be ```if (data_end < cursor + sn_idx + 1)```. Otherwise, if you attempt to use ```sn.server_name``` outside of the loop, such as in a printk or in updating a map, you get an another invalid access to packet error. — user2233706, Jan 20 '22 at 04:15

user2233706 · Answer 2 · 2022-01-23T01:44:18.527

In addition to Dylan's great answer, an alternative to the inner for loop that copies the server name from the SNI is to do this:

                        struct server_name sn = {"a"};
                        bpf_core_read(sn.server_name, server_name_len, data);

This copies from data into sn.server_name.

This avoids having to boundary checks. Initializing the struct to a default value is required. Otherwise, you get invalid indirect read from stack ... error if you call any of the BPF helper functions, such as bpf_map_update_elem.

BPF verifier fails because of invalid access to packet

2 Answers2

Linked