3

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
user2233706
  • 6,148
  • 5
  • 44
  • 86
  • can you add the `bpf` command line ? – OrenIshShalom Jan 18 '22 at 05:01
  • I added the ```xdp-loader``` command that results in the same error. – user2233706 Jan 18 '22 at 05:30
  • What the verifier says: `if (data_end < data + ext_len)` is rejected because `math between pkt pointer and register with unbounded min value is not allowed`. Your packet pointer is `data`, while the value from `ext_len` has no minimal value in the eyes of the verifier. Can you try to add another check before this one that returns early if `ext_len < 0`? (Regarding the error disappearing when you comment out the block or the outer loop, this is likely because `data` becomes unused in the resulting program, and the compiler discards the check that the verifier is complaining about.) – Qeole Jan 18 '22 at 09:48
  • Could you try to load the program with LogLevel=2 instead of 1? That should provide us with a more verbose verifier output in this case, showing the state of R0 from the verifier's point of view. – pchaigno Jan 18 '22 at 10:38
  • @Qeole I get the same behavior. I put the check both as a separate if statement and inside ```if (data_end < data + ext_len)```. – user2233706 Jan 18 '22 at 14:42
  • @user2233706 Thanks for the additional verifier logs. Could you try to add an upper-bound check on variable `ext_len` (maybe 30000) instead of a lower-bound check as suggested by @Qeole? It's a bit counter-intuitive but I suspect it might help the verifier deduce both upper and lower bounds for the variable. – pchaigno Jan 18 '22 at 15:11
  • Thanks, I made that change and the error moved to somewhere else. It's interesting that using 3000 results in a different error. – user2233706 Jan 18 '22 at 18:03
  • Hm, that's a different issue. Let's treat it in a different post please. I'll write an answer to explain what's happening. – pchaigno Jan 18 '22 at 18:08
  • Thanks, I created [this](https://stackoverflow.com/questions/70760516/bpf-verifier-fails-because-invalid-access-to-packet-when-extracting-sni-from-tls). – user2233706 Jan 18 '22 at 18:18

1 Answers1

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.

pchaigno
  • 11,313
  • 2
  • 29
  • 54
  • I updated the code with your suggestion, but I get the same issue. – user2233706 Jan 19 '22 at 17:26
  • Ah, the compiler optimized the bound check out again. Could you try to make `ext_len` `volatile`? – pchaigno Jan 19 '22 at 17:41
  • I get a different error, this time at ```for(int i = 0; i < extension_methods_len; i += sizeof(struct extension)) {``` (include the log above). I get the same error if I use __u16 instead of int. – user2233706 Jan 19 '22 at 18:21
  • Ok. That looks like a different issue. For that last issue, you may want to try compiling with `mcpu=v3` or `mattr=+alu32`. See https://pchaigno.github.io/bpf/2021/10/20/ebpf-instruction-sets.html for the requirements. – pchaigno Jan 19 '22 at 18:31