search

vincentmli / xdp-tools

Utilities and example programs for use with XDP
Other
1 stars 0 forks source link

XDP program DNS query name parsing verifier error : R2 offset is outside of the packet #1

Closed vincentmli closed 1 month ago

vincentmli commented 2 months ago

A simplified DNS XDP test program to extract domain name from packet and domain name lookup in bpf map https://github.com/vincentmli/xdp-tools/blob/dns-deny/xdp-dns/xdp_dns.bpf.c.

            qname = parse_dname(&c);
            if (!qname) {
                return XDP_ABORTED; // Return FORMERR?
            }

                        // avoid R2 offset is outside of the packet error
                        //if (qname + MAX_DOMAIN_SIZE + 1 > c.end)
            //  return XDP_ABORTED; // Return FORMERR?

                        // Check against the domain denylist
                        if (bpf_map_lookup_elem(&domain_denylist, qname))
                                return XDP_DROP;

            break;

without if (qname + MAX_DOMAIN_SIZE + 1 > c.end), the verifier complains error R2 offset is outside of the packet below, but if (qname + MAX_DOMAIN_SIZE + 1 > c.end) always return XDP_ABORTED while sending DNS test, so the packet bound check here is incorrect, what is the proper packet bound check then?

full verifier error

libbpf: prog 'xdp_dns': -- BEGIN PROG LOAD LOG -- Validating xdp_dns() func#0... 0: R1=ctx(off=0,imm=0) R10=fp0 ; int xdp_dns(struct xdp_md ctx) 0: (bf) r6 = r1 ; R1=ctx(off=0,imm=0) R6_w=ctx(off=0,imm=0) ; if (bpf_xdp_adjust_meta(ctx, -(int)sizeof(struct meta_data))) 1: (18) r2 = 0xfffffff8 ; R2_w=4294967288 3: (85) call bpf_xdp_adjust_meta#54 ; R0_w=scalar() 4: (bf) r1 = r0 ; R0_w=scalar(id=1) R1_w=scalar(id=1) 5: (b7) r0 = 2 ; R0_w=2 ; if (bpf_xdp_adjust_meta(ctx, -(int)sizeof(struct meta_data))) 6: (55) if r1 != 0x0 goto pc+81 ; R1_w=0 ; c->end = (void )(long)ctx->data_end; 7: (61) r2 = (u32 )(r6 +4) ; R2_w=pkt_end(off=0,imm=0) R6_w=ctx(off=0,imm=0) ; c->end = (void )(long)ctx->data_end; 8: (7b) (u64 )(r10 -8) = r2 ; R2_w=pkt_end(off=0,imm=0) R10=fp0 fp-8_w=pkt_end ; c->pos = (void )(long)ctx->data; 9: (61) r4 = (u32 )(r6 +0) ; R4_w=pkt(off=0,r=0,imm=0) R6_w=ctx(off=0,imm=0) ; md = (void )(long)ctx->data_meta; 10: (61) r3 = (u32 )(r6 +8) ; R3_w=pkt_meta(off=0,r=0,imm=0) R6_w=ctx(off=0,imm=0) ; if ((void )(md + 1) > c.pos) 11: (bf) r1 = r3 ; R1_w=pkt_meta(off=0,r=0,imm=0) R3_w=pkt_meta(off=0,r=0,imm=0) 12: (07) r1 += 8 ; R1=pkt_meta(off=8,r=0,imm=0) ; if ((void )(md + 1) > c.pos) 13: (2d) if r1 > r4 goto pc+74 ; R1=pkt_meta(off=8,r=8,imm=0) R4=pkt(off=0,r=0,imm=0) ; PARSE_FUNC_DECLARATION(ethhdr) 14: (bf) r1 = r4 ; R1_w=pkt(off=0,r=0,imm=0) R4=pkt(off=0,r=0,imm=0) 15: (07) r1 += 14 ; R1_w=pkt(off=14,r=0,imm=0) ; PARSE_FUNC_DECLARATION(ethhdr) 16: (2d) if r1 > r2 goto pc+71 ; R1_w=pkt(off=14,r=14,imm=0) R2=pkt_end(off=0,imm=0) 17: (15) if r4 == 0x0 goto pc+70 ; R4=pkt(off=0,r=14,imm=0) ; eth_proto = eth->h_proto; 18: (71) r0 = (u8 )(r4 +12) ; R0_w=scalar(umax=255,var_off=(0x0; 0xff)) R4=pkt(off=0,r=14,imm=0) 19: (71) r5 = (u8 )(r4 +13) ; R4=pkt(off=0,r=14,imm=0) R5_w=scalar(umax=255,var_off=(0x0; 0xff)) 20: (67) r5 <<= 8 ; R5_w=scalar(umax=65280,var_off=(0x0; 0xff00)) 21: (4f) r5 |= r0 ; R0_w=scalar(umax=255,var_off=(0x0; 0xff)) R5_w=scalar() ; eth_proto = eth->h_proto; 22: (6b) (u16 )(r3 +0) = r5 ; R3=pkt_meta(off=0,r=8,imm=0) R5=scalar() ; || eth_proto == bpf_htons(ETH_P_8021AD)) { 23: (15) if r5 == 0xa888 goto pc+1 ; R5=scalar() 24: (55) if r5 != 0x81 goto pc+16 ; R5=129 ; PARSE_FUNC_DECLARATION(vlanhdr) 25: (bf) r6 = r4 ; R4=pkt(off=0,r=14,imm=0) R6_w=pkt(off=0,r=14,imm=0) 26: (07) r6 += 18 ; R6_w=pkt(off=18,r=14,imm=0) 27: (b7) r0 = 2 ; R0_w=2 ; PARSE_FUNC_DECLARATION(vlanhdr) 28: (2d) if r6 > r2 goto pc+59 ; R2=pkt_end(off=0,imm=0) R6_w=pkt(off=18,r=18,imm=0) 29: (15) if r1 == 0x0 goto pc+58 ; R1=pkt(off=14,r=18,imm=0) ; eth_proto = vlan->encap_proto; 30: (69) r5 = (u16 )(r4 +16) ; R4=pkt(off=0,r=18,imm=0) R5_w=scalar(umax=65535,var_off=(0x0; 0xffff)) ; eth_proto = vlan->encap_proto; 31: (6b) (u16 )(r3 +0) = r5 ; R3=pkt_meta(off=0,r=8,imm=0) R5=scalar(umax=65535,var_off=(0x0; 0xffff)) ; || eth_proto == __bpf_htons(ETH_P_8021AD)) { 32: (15) if r5 == 0xa888 goto pc+2 ; R5=scalar(umax=65535,var_off=(0x0; 0xffff)) 33: (bf) r1 = r6 ; R1_w=pkt(off=18,r=18,imm=0) R6=pkt(off=18,r=18,imm=0) 34: (55) if r5 != 0x81 goto pc+6 ; R5=129 ; PARSE_FUNC_DECLARATION(vlanhdr) 35: (bf) r1 = r4 ; R1_w=pkt(off=0,r=18,imm=0) R4=pkt(off=0,r=18,imm=0) 36: (07) r1 += 22 ; R1_w=pkt(off=22,r=18,imm=0) ; PARSE_FUNC_DECLARATION(vlanhdr) 37: (2d) if r1 > r2 goto pc+50 ; R1_w=pkt(off=22,r=22,imm=0) R2=pkt_end(off=0,imm=0) 38: (15) if r6 == 0x0 goto pc+49 ; R6=pkt(off=18,r=22,imm=0) ; eth_proto = vlan->encap_proto; 39: (69) r5 = (u16 )(r4 +20) ; R4=pkt(off=0,r=22,imm=0) R5_w=scalar(umax=65535,var_off=(0x0; 0xffff)) ; eth_proto = vlan->encap_proto; 40: (6b) (u16 )(r3 +0) = r5 ; R3=pkt_meta(off=0,r=8,imm=0) R5=scalar(umax=65535,var_off=(0x0; 0xffff)) ; md->ip_pos = c.pos - (void )eth; 41: (bf) r0 = r1 ; R0_w=pkt(off=22,r=22,imm=0) R1=pkt(off=22,r=22,imm=0) 42: (1f) r0 -= r4 ; R0_w=scalar() R4=pkt(off=0,r=22,imm=0) ; md->ip_pos = c.pos - (void )eth; 43: (6b) (u16 )(r3 +2) = r0 ; R0_w=scalar() R3=pkt_meta(off=0,r=8,imm=0) ; if (md->eth_proto == __bpf_htons(ETH_P_IP)) { 44: (55) if r5 != 0x8 goto pc+42 ; R5=8 ; PARSE_FUNC_DECLARATION(iphdr) 45: (bf) r4 = r1 ; R1=pkt(off=22,r=22,imm=0) R4_w=pkt(off=22,r=22,imm=0) 46: (07) r4 += 20 ; R4_w=pkt(off=42,r=22,imm=0) 47: (b7) r0 = 2 ; R0_w=2 ; PARSE_FUNC_DECLARATION(iphdr) 48: (2d) if r4 > r2 goto pc+39 ; R2=pkt_end(off=0,imm=0) R4_w=pkt(off=42,r=42,imm=0) 49: (15) if r1 == 0x0 goto pc+38 ; R1=pkt(off=22,r=42,imm=0) ; switch (ipv4->protocol) { 50: (71) r3 = (u8 *)(r1 +9) ; R1=pkt(off=22,r=42,imm=0) R3_w=scalar(umax=255,var_off=(0x0; 0xff)) ; switch (ipv4->protocol) { 51: (55) if r3 != 0x11 goto pc+35 ; R3_w=17 ; PARSE_FUNC_DECLARATION(udphdr) 52: (bf) r3 = r1 ; R1=pkt(off=22,r=42,imm=0) R3_w=pkt(off=22,r=42,imm=0) 53: (07) r3 += 28 ; R3_w=pkt(off=50,r=42,imm=0) ; PARSE_FUNC_DECLARATION(udphdr) 54: (2d) if r3 > r2 goto pc+33 ; R2=pkt_end(off=0,imm=0) R3_w=pkt(off=50,r=50,imm=0) 55: (15) if r4 == 0x0 goto pc+32 ; R4=pkt(off=42,r=50,imm=0) ; || !(udp->dest == bpf_htons(DNS_PORT)) 56: (69) r4 = (u16 )(r1 +22) ; R1=pkt(off=22,r=50,imm=0) R4=scalar(umax=65535,var_off=(0x0; 0xffff)) ; || !(dns = parse_dnshdr(&c))) 57: (55) if r4 != 0x3500 goto pc+30 ; R4=13568 ; PARSE_FUNC_DECLARATION(dnshdr) 58: (bf) r4 = r1 ; R1=pkt(off=22,r=50,imm=0) R4_w=pkt(off=22,r=50,imm=0) 59: (07) r4 += 40 ; R4_w=pkt(off=62,r=50,imm=0) ; PARSE_FUNC_DECLARATION(dnshdr) 60: (2d) if r4 > r2 goto pc+27 ; R2=pkt_end(off=0,imm=0) R4_w=pkt(off=62,r=62,imm=0) 61: (7b) (u64 )(r10 -16) = r4 ; R4_w=pkt(off=62,r=62,imm=0) R10=fp0 fp-16_w=pkt ; if (!(udp = parse_udphdr(&c)) 62: (15) if r3 == 0x0 goto pc+25 ; R3=pkt(off=50,r=62,imm=0) 63: (b7) r0 = 0 ; R0_w=0 ; if (dns->flags.as_bits_and_pieces.qr 64: (69) r2 = (u16 )(r1 +30) ; R1=pkt(off=22,r=62,imm=0) R2_w=scalar(umax=65535,var_off=(0x0; 0xffff)) ; if (dns->flags.as_bits_and_pieces.qr 65: (57) r2 &= 128 ; R2=scalar(umax=128,var_off=(0x0; 0x80)) ; || dns->qdcount != bpf_htons(1) 66: (55) if r2 != 0x0 goto pc+21 ; R2=0 ; || dns->qdcount != __bpf_htons(1) 67: (69) r2 = (u16 )(r1 +32) ; R1=pkt(off=22,r=62,imm=0) R2_w=scalar(umax=65535,var_off=(0x0; 0xffff)) ; || dns->ancount || dns->nscount 68: (55) if r2 != 0x100 goto pc+19 ; R2_w=256 ; || dns->ancount || dns->nscount 69: (69) r2 = (u16 )(r1 +34) ; R1=pkt(off=22,r=62,imm=0) R2_w=scalar(umax=65535,var_off=(0x0; 0xffff)) ; || dns->ancount || dns->nscount 70: (55) if r2 != 0x0 goto pc+17 ; R2_w=0 ; || dns->ancount || dns->nscount 71: (69) r2 = (u16 )(r1 +36) ; R1=pkt(off=22,r=62,imm=0) R2_w=scalar(umax=65535,var_off=(0x0; 0xffff)) ; || dns->arcount > bpf_htons(2)) 72: (55) if r2 != 0x0 goto pc+15 ; R2_w=0 ; || dns->arcount > __bpf_htons(2)) 73: (69) r1 = (u16 )(r1 +38) ; R1=scalar(umax=65535,var_off=(0x0; 0xffff)) ; if (dns->flags.as_bits_and_pieces.qr 74: (25) if r1 > 0x200 goto pc+13 ; R1=scalar(umax=512,var_off=(0x0; 0x3ff)) 75: (bf) r1 = r10 ; R1_w=fp0 R10=fp0 ; qname = parse_dname(&c); 76: (07) r1 += -16 ; R1_w=fp-16 77: (85) call pc+11 reg type unsupported for arg#0 function parse_dname#26 caller: R6=pkt(off=18,r=62,imm=0) R10=fp0 fp-8=pkt_end fp-16=pkt callee: frame1: R1_w=fp-16 R2=0 R3=pkt(off=50,r=62,imm=0) R4=pkt(off=62,r=62,imm=0) R5=8 R10=fp0 ; char parse_dname(struct cursor c) 89: (b7) r3 = 0 ; frame1: R3_w=0 90: (79) r4 = (u64 )(r1 +8) ; frame1: R1_w=fp-16 R4_w=pkt_end(off=0,imm=0) ; __u8 dname = c->pos; 91: (79) r2 = (u64 )(r1 +0) ; frame1: R1_w=fp-16 R2_w=pkt(off=62,r=62,imm=0) 92: (18) r6 = 0x100000000000000 ; frame1: R6_w=72057594037927936 94: (bf) r5 = r2 ; frame1: R2_w=pkt(off=62,r=62,imm=0) R5_w=pkt(off=62,r=62,imm=0) 95: (05) goto pc+5 ; if (c->pos + 1 > c->end) 101: (bf) r7 = r5 ; frame1: R5=pkt(off=62,r=62,imm=0) R7_w=pkt(off=62,r=62,imm=0) 102: (07) r7 += 1 ; frame1: R7_w=pkt(off=63,r=62,imm=0) 103: (b7) r0 = 0 ; frame1: R0_w=0 ; if (c->pos + 1 > c->end) 104: (2d) if r7 > r4 goto pc+21 ; frame1: R4=pkt_end(off=0,imm=0) R7_w=pkt(off=63,r=63,imm=0) ; if ((o & 0xC0) == 0xC0) { 105: (71) r7 = (u8 )(r5 +0) ; frame1: R5=pkt(off=62,r=63,imm=0) R7_w=scalar(umax=255,var_off=(0x0; 0xff)) ; if ((o & 0xC0) == 0xC0) { 106: (bf) r0 = r7 ; frame1: R0_w=scalar(id=2,umax=255,var_off=(0x0; 0xff)) R7_w=scalar(id=2,umax=255,var_off=(0x0; 0xff)) 107: (57) r0 &= 192 ; frame1: R0_w=scalar(umax=192,var_off=(0x0; 0xc0)) ; if ((o & 0xC0) == 0xC0) { 108: (55) if r0 != 0xc0 goto pc+4 ; frame1: R0_w=192 ; c->pos += 2; 109: (07) r5 += 2 ; frame1: R5_w=pkt(off=64,r=63,imm=0) 110: (7b) (u64 *)(r1 +0) = r5 ; frame1: R1=fp-16 R5_w=pkt(off=64,r=63,imm=0) 111: (bf) r0 = r2 ; frame1: R0_w=pkt(off=62,r=63,imm=0) R2=pkt(off=62,r=63,imm=0) 112: (05) goto pc+13 ; } 126: (95) exit returning from callee: frame1: R0=pkt(off=62,r=63,imm=0) R1=fp-16 R2=pkt(off=62,r=63,imm=0) R3=0 R4=pkt_end(off=0,imm=0) R5=pkt(off=64,r=63,imm=0) R6=72057594037927936 R7=scalar(id=2,umax=255,var_off=(0x0; 0xff)) R10=fp0 to caller at 78: R0=pkt(off=62,r=63,imm=0) R6=pkt(off=18,r=63,imm=0) R10=fp0 fp-8=pkt_end fp-16=pkt ; qname = parse_dname(&c); 78: (bf) r2 = r0 ; R0=pkt(off=62,r=63,imm=0) R2_w=pkt(off=62,r=63,imm=0) 79: (b7) r0 = 0 ; R0_w=0 ; if (!qname) { 80: (15) if r2 == 0x0 goto pc+7 ; R2_w=pkt(off=62,r=63,imm=0) ; if (bpf_map_lookup_elem(&domain_denylist, qname)) 81: (18) r1 = 0xffff93604d4c2400 ; R1_w=map_ptr(off=0,ks=254,vs=1,imm=0) 83: (85) call bpf_map_lookup_elem#1 invalid access to packet, off=62 size=254, R2(id=0,off=62,r=63) R2 offset is outside of the packet processed 101 insns (limit 1000000) max_states_per_insn 0 total_states 10 peak_states 10 mark_read 8 -- END PROG LOAD LOG -- libbpf: prog 'xdp_dns': failed to load: -13 libbpf: failed to load object 'xdp-dns/xdp_dns.bpf.o' libxdp: Failed to load program xdp_dns: Permission denied Couldn't attach XDP program on iface 'lo': Permission denied(-13)

vincentmli commented 2 months ago

Dylan suggested here https://stackoverflow.com/questions/78958420/ebpf-xdp-program-r2-offset-is-outside-of-the-packet/78960532#78960532, so I made the changes, now got error invalid indirect access to stack R2 off=-64 size=65, note when I use memcpy which is __builtin_memcpy, I just give a hard code number like memcpy(domain_key, qname, 64);, use memcpy(domain_key, qname, len); result compiler error:

in function xdp_dns i32 (ptr): A call to built-in function 'memcpy' is not supported.

attached full verifier error
error.txt

vincentmli commented 2 months ago

used custom memcpy below that sort of worked around thein function xdp_dns i32 (ptr): A call to built-in function 'memcpy' is not supported. compiler error, but still got same invalid indirect access to stack R2 off=-64 size=65

+static __always_inline void *custom_memcpy(void *dest, const void *src, __u8 len) {
+    __u8 i;
+
+    // Perform the copy byte-by-byte to satisfy the BPF verifier
+    for (i = 0; i < len; i++) {
+        *((__u8 *)dest + i) = *((__u8 *)src + i);
+    }
+
+    return dest;
+}
vincentmli commented 2 months ago

the verifier error:

; if (bpf_map_lookup_elem(&domain_denylist, domain_key))
748: (18) r1 = 0xffff93604d4c0c00     ; R1_w=map_ptr(off=0,ks=65,vs=1,imm=0)
750: (85) call bpf_map_lookup_elem#1
invalid indirect access to stack R2 off=-64 size=65

from chatgpt:

The verifier error you're seeing, "invalid indirect access to stack R2 off=-64 size=65", indicates that you're trying to access 65 bytes of memory (from the stack) starting at offset -64, but the BPF verifier sees an issue: the map lookup expects a key of size 65 bytes, but it only sees 64 bytes of initialized stack space at that offset (fp-64).

The issue arises because you're attempting to pass a buffer (domain_key) of 64 bytes to a map with a key size of 65 bytes.

Why the Error Happens: The key size for the bpf_map_lookup_elem() function is 65 bytes, but the stack only has 64 bytes initialized at domain_key (starting at fp-64). The verifier expects that you're reading exactly 65 bytes, but in this case, it's seeing one less byte. Solution: You need to ensure that you're allocating 65 bytes for domain_key, not just 64. This extra byte can either be zero-initialized or part of your key, depending on your use case.

Adjustments to Fix the Verifier Error: Increase domain_key size: Ensure that domain_key is at least 65 bytes, which matches the map key size.

Correct stack offset: Ensure you’re using the correct offset for accessing all 65 bytes.

so following diff fix the verifier error:

diff --git a/xdp-dns/xdp_dns.bpf.c b/xdp-dns/xdp_dns.bpf.c
index 125e563..18daba4 100644
--- a/xdp-dns/xdp_dns.bpf.c
+++ b/xdp-dns/xdp_dns.bpf.c
@@ -163,6 +163,18 @@ static __always_inline char *parse_dname(struct cursor *c) {
     return 0;
 }

+static __always_inline void *custom_memcpy(void *dest, const void *src, __u8 len) {
+    __u8 i;
+
+    // Perform the copy byte-by-byte to satisfy the BPF verifier
+    for (i = 0; i < len; i++) {
+        *((__u8 *)dest + i) = *((__u8 *)src + i);
+    }
+
+    return dest;
+}
+
+
 // Custom strlen function for BPF
 static __always_inline __u8 custom_strlen(const char *str, struct cursor *c) {
     __u8 len = 0;
@@ -192,7 +204,7 @@ int xdp_dns(struct xdp_md *ctx)
        struct dnshdr    *dns;
        char    *qname;
        __u8 len = 0;
-       char domain_key[MAX_DOMAIN_SIZE] = {0};  // Buffer for map lookup
+       char domain_key[MAX_DOMAIN_SIZE + 1 ] = {0};  // Buffer for map lookup

        if (bpf_xdp_adjust_meta(ctx, -(int)sizeof(struct meta_data)))
                return XDP_PASS;
@@ -231,10 +243,11 @@ int xdp_dns(struct xdp_md *ctx)
                        bpf_printk("%s len is %d from %pI4", qname, len, &ipv4->saddr);

                         //avoid R2 offset is outside of the packet error
-                        if (qname + len + 1 > c.end)
+                        if (qname + len > c.end)
                                return XDP_ABORTED; // Return FORMERR?

-                       memcpy(domain_key, qname, 64);
+                       int copy_len = len < MAX_DOMAIN_SIZE ? len : MAX_DOMAIN_SIZE;
+                       custom_memcpy(domain_key, qname, copy_len);

                         // Check against the domain denylist
                         if (bpf_map_lookup_elem(&domain_denylist, domain_key))
vincentmli commented 2 months ago

another issue I noticed is that MAX_DOMAIN_SIZE can't be 253, the domain_key[253] may take bigger stack space which may cause some issue, there is no verifier error, but the program will fail to load with:

xdp-loader load lo -m skb -vvv xdp-dns/xdp_dns.bpf.o 

 libxdp: Loaded XDP program xdp_pass, got fd 6
 libxdp: Duplicated fd 6 to 7 for prog xdp_pass
 libxdp: Kernel supports XDP programs with frags
 libxdp: XDP program xdp_dns is already loaded with fd -2
 libxdp: Error on fcntl: Bad file descriptorCouldn't attach XDP program on iface 'lo': Bad file descriptor(-9)

64, or 128 seems ok with MAX_DOMAIN_SIZE