eBPF验证器原理

原创

Jinrong

修改于 2022-07-25 11:48:56

2K0

文章被收录于专栏：Linux内核/eBPF/kvmLinux内核/eBPF/kvm

1.前言

之前对eBPF验证器的了解仅停留在概念层面，那么验证器究竟是如何保证eBPF程序的安全呢，本文揭开eBPF验证器的检查细节。

2.eBPF验证器

eBPF程序的安全性主要依赖验证器，验证器对eBPF的安全性检查分两步确定。

第一步做DAG检查，不允许循环和其他CFG验证。特别是它将检测出有不可达指令的程序。(经典的BPF检查器允许它们)。
第二步从第一个insn开始，遍历所有可能的路径。它模拟每个insn的执行，观察寄存器和堆栈的状态变化。

在程序开始时，寄存器R1包含一个指向上下文的指针，其类型为PTR_TO_CTX。如果验证器看到一个insn的R2=R1，那么R2现在的类型也是PTR_TO_CTX。如果R1=PTR_TO_CTX，而insn是R2=R1+R1，那么R2=SCALAR_VALUE，因为两个有效指针的相加会产生无效的指针。(在安全模式下，验证器将拒绝任何类型的指针运算，以确保内核地址不会泄露给非特权用户）。如果寄存器从来没有被写过，它是不可读的。

bpf_mov R0 = R2
bpf_exit

这样的操作将被拒绝，因为R2在程序开始时是不可读的。在内核函数调用后，R1-R5被重置为不可读，R0有一个函数的返回类型。由于R6-R9是被调用者保存的，它们的状态在整个调用过程中被保留下来。

bpf_mov R6 = 1
bpf_call foo
bpf_mov R0 = R6
bpf_exit

这样的操作是正确的，如果读取R1而不是R6，它就会被拒绝。load/store指令只允许使用有效类型的寄存器，即PTR_TO_CTX、PTR_TO_MAP、PTR_TO_STACK，它们是经过边界和对齐检查的。例如：

bpf_mov R1 = 1
bpf_mov R2 = 2
bpf_xadd *(u32 *)(R1 + 3) += R2
bpf_exit

这样的操作将会被拒绝，因为R1在执行指令bpf_xadd时没有有效的指针类型。在开始时，R1的类型是PTR_TO_CTX（一个指向通用结构bpf_context的指针）。回调用于定义验证器，用来限制eBPF程序只访问ctx结构中具有指定大小和对齐方式的某些字段。例如下面的insn：

bpf_ld R0 = *(u32 *)(R6 + 8)

如果R6=PTR_TO_CTX，通过is_valid_access()回调，验证器将知道大小为4字节偏移量为8的地址可以被访问，否则验证器将拒绝该程序。如果R6=PTR_TO_STACK，那么访问应该是对齐的，并且在堆栈的边界内，即[-MAX_BPF_STACK, 0]。在这个例子中，偏移量是8，所以它将无法通过验证，因为它超出了界限。只有eBPF程序在堆栈中写数据后，验证器才允许它从堆栈中读取数据。经典的BPF验证器对M0-15内存插槽做类似的检查，例如：

bpf_ld R0 = *(u32 *)(R10 - 4)
bpf_exit

这样的操作是无效的，虽然R10是正确的只读寄存器，并且类型为PTR_TO_STACK，R10 - 4在堆栈范围内，但没有数据存储到该位置。指针寄存器的溢出/填充也被跟踪，因为四个（R6-R9）被调用者保存的寄存器对某些程序来说可能是不够的。允许的函数调用是用bpf_verifier_ops->get_func_proto()定义的，eBPF验证器将检查寄存器是否符合参数约束，调用后寄存器R0将被设置为函数的返回类型。

函数调用是扩展eBPF程序功能的一个主要机制。套接字过滤器可能允许程序调用一组函数，而跟踪过滤器可能允许完全不同的一组函数。如果一个函数被eBPF程序访问，从安全的角度考虑，验证器将保证该函数的参数是有效的。seccomp与套接字过滤器对经典的BPF有不同的安全限制。Seccomp通过两个阶段的验证器来解决这个问题，经典BPF验证器之后是seccomp验证器。eBPF共享一个可配置的验证器。

3.跟踪寄存器的值

为了确定eBPF程序的安全性，验证器必须跟踪每个寄存器和堆栈，这是通过bpf_reg_state完成的，它定义在include/linux/bpf_verifier.h中。每个寄存器状态都有一个类型，这些类型有NOT_INIT（该寄存器未被写入）、SCALAR_VALUE（一些不能作为指针使用的值）和指针类型。指针的类型及其base描述如下：

指针类型	描述
PTR_TO_CTX	Pointer to bpf_context.
CONST_PTR_TO_MAP	Pointer to struct bpf_map. “Const” because arithmetic on these pointers is forbidden.
PTR_TO_MAP_VALUE	Pointer to the value stored in a map element.
PTR_TO_MAP_VALUE_OR_NULL	Either a pointer to a map value, or NULL; map accesses return this type, which becomes a PTR_TO_MAP_VALUE when checked != NULL. Arithmetic on these pointers is forbidden.
PTR_TO_STACK	Frame pointer.
PTR_TO_PACKET	skb->data.
PTR_TO_PACKET_END	skb->data + headlen; arithmetic forbidden.
PTR_TO_SOCKET	Pointer to struct bpf_sock_ops, implicitly refcounted.
PTR_TO_SOCKET_OR_NULL	Either a pointer to a socket, or NULL; socket lookup returns this type, which becomes a PTR_TO_SOCKET when checked != NULL. PTR_TO_SOCKET is reference-counted, so programs must release the reference through the socket release function before the end of the program. Arithmetic on these pointers is forbidden.

然而，一个指针可能会从这个base上偏移（作为指针运算的结果），分别在"固定偏移 "和 "可变偏移"两个部分跟踪它们。前者用于一个完全已知的值（例如一个即时操作数）被添加到一个指针上时，而后者则用于不完全已知的值。变量偏移量也用于SCALAR_VALUEs中，用来跟踪寄存器中可能的值的范围。验证器可以知道变量偏移的值是：

无符号的最小值和最大值
有符号的最小值和最大值
对于单个比特位的理解，需要知道“tnum”的形式：一个u64 "mask"和一个u64 "value"。mask中的1代表未知值的比特，value中的1已知值为1的比特。已知为0的比特在mask和value中都是0，不存在mask和value都是1的情况。如果从内存中往寄存器中读入一个字节，该寄存器的前56位是已知的0，而低8位是未知的，这被表示为tnum(0x0;0xff)。如果将其与0x40进行运算，就会得到(0x40;0xbf)，加上1就会得到(0x0;0x1ff)。

除了算术，寄存器的状态也可以通过条件分支更新。如果一个SCALAR_VALUE被比较>8，在 "真 "分支中它的umin_value（无符号最小值）是9，而在 "假 "分支中它的umax_value是8。一个有符号的比较（用BPF_JSGT或BPF_JSGE）将代替更新有符号的最小/最大值。来自有符号和无符号边界的信息可以结合起来；例如，如果一个值首先被测试<8，然后被测试s>4，验证器将得出结论，该值也>4并且s<8，因为这些限制可以防止跨越符号边界。

变量偏移部分的PTR_TO_PACKET有一个'id'，它对所有共享该变量偏移的指针来说是通用的。这对数据包范围检查很重要：在向数据包指针寄存器A添加一个变量后，如果把它复制到另一个寄存器B，然后向A添加一个常数4，两个寄存器将共享相同的'id'，但A将有一个固定的偏移量+4。然后如果A被边界检查并发现小于PTR_TO_PACKET_END，寄存器B就会有一个至少4字节的安全范围。关于PTR_TO_PACKET范围的细节，可以关注本文标题4“直接数据包访问”。

'id'字段也用于PTR_TO_MAP_VALUE_OR_NULL，对于从map查找返回的指针的所有copies来说是通用的。这意味着，当一个副本被检查并发现是非NULL时，所有的副本都可以成为PTR_TO_MAP_VALUEs。除了范围检查之外，跟踪的信息也被用来执行指针访问的对齐。例如，在大多数系统中，数据包指针在4字节对齐后是2字节。如果一个程序在此基础上增加14个字节以跳过以太网头，然后读取IHL并加上(IHL * 4)，得到的指针将有一个4n+2的可变偏移量，所以加上2个字节(NET_IP_ALIGN)就会4字节对齐，通过这个指针访问的地址是安全的。'id' 字段也用于PTR_TO_SOCKET和PTR_TO_SOCKET_OR_NULL，对从套接字查找返回的指针的所有copies都是通用的。这与PTR_TO_MAP_VALUE_OR_NULL->PTR_TO_MAP_VALUE的处理方式类似，但它也处理指针的引用跟踪。PTR_TO_SOCKET隐式地代表了对相应结构sock的引用。为了确保引用不被泄露，必须对引用进行NULL检查，在非NULL情况下，将有效的引用传递给socket释放函数。

4. 直接数据包访问

在cls_bpf和act_bpf程序中，验证器允许通过skb->data和skb->data_end指针直接访问包数据，例如：

1:  r4 = *(u32 *)(r1 +80)  /* load skb->data_end */
2:  r3 = *(u32 *)(r1 +76)  /* load skb->data */
3:  r5 = r3
4:  r5 += 14
5:  if r5 > r4 goto pc+16
R1=ctx R3=pkt(id=0,off=0,r=14) R4=pkt_end R5=pkt(id=0,off=14,r=14) R10=fp
6:  r0 = *(u16 *)(r3 +12) /* access 12 and 13 bytes of the packet */

从数据包中加载2个字节的做法是安全的，因为程序作者确实检查了如果(skb->data + 14 > skb->data_end) goto err at insn #5，这意味着寄存器R3（指向skb->data）至少有14个可直接访问的字节。验证器将其标记为R3=pkt(id=0,off=0,r=14)。id=0意味着没有额外的变量被添加到寄存器。off=0意味着没有额外的常量被添加。r=14是安全访问的范围，意味着字节[R3, R3 + 14]是确定的。R5被标记为R5=pkt(id=0,off=14,r=14)。它也指向数据包，但常数14被添加到寄存器中，所以它现在指向skb->data + 14，可访问范围是[R5, R5 + 14 - 14]，是0字节。更复杂的数据包访问示例：

R0=inv1 R1=ctx R3=pkt(id=0,off=0,r=14) R4=pkt_end R5=pkt(id=0,off=14,r=14) R10=fp
6:  r0 = *(u8 *)(r3 +7) /* load 7th byte from the packet */
7:  r4 = *(u8 *)(r3 +12)
8:  r4 *= 14
9:  r3 = *(u32 *)(r1 +76) /* load skb->data */
10:  r3 += r4
11:  r2 = r1
12:  r2 <<= 48
13:  r2 >>= 48
14:  r3 += r2
15:  r2 = r3
16:  r2 += 8
17:  r1 = *(u32 *)(r1 +80) /* load skb->data_end */
18:  if r2 > r1 goto pc+2
R0=inv(id=0,umax_value=255,var_off=(0x0; 0xff)) R1=pkt_end R2=pkt(id=2,off=8,r=8) R3=pkt(id=2,off=0,r=8) R4=inv(id=0,umax_value=3570,var_off=(0x0; 0xfffe)) R5=pkt(id=0,off=14,r=14) R10=fp
19:  r1 = *(u8 *)(r3 +4)

寄存器R3的状态是R3=pkt(id=2,off=0,r=8)，id=2意味着看到了两条r3 += rX指令，所以r3指向一个包内的某个偏移量，由于程序作者在insn #18处做了if (r3 + 8 > r1) goto err，安全范围是[R3, R3 + 8]。验证器只允许对数据包寄存器进行 "加"/"减 "操作。任何其它的操作都会将寄存器的状态设置为`SCALAR_VALUE'，它将不能被直接访问数据包。

操作r3 += rX可能会溢出，变得小于原始skb->data，验证器必须防止这种情况。因此，当它看到r3 += rX指令和rX超过16位值时，任何后续的r3与skb->data_end的边界检查都不会给我们提供 "范围 "信息，所以试图通过指针读取将产生 "无效访问数据包 "的错误。例如在insn r4 = *(u8 *)(r3 +12)(上面的insn #7)之后，r4的状态是R4=inv(id=0,umax_value=255,var_off=(0x0; 0xff))，这意味着寄存器的上56位被保证为零，而对下8位则一无所知。在insn r4 *= 14之后，状态变成R4=inv(id=0,umax_value=3570,var_off=(0x0; 0xfffe))，因为将一个8位的值乘以常数14将保持上面52位为零，同时由于14是偶数，最小有效位将为零。同样，r2 >>= 48将使R2=inv(id=0,umax_value=65535,var_off=(0x0; 0xffff))，因为移位是没有符号扩展。这个逻辑在调整_reg_min_max_vals()函数中实现，该函数调用调整_ptr_min_max_vals()来增加指针到标量（反之亦然），调整_scalar_min_max_vals()来对两个标量进行操作。

最终的结果是，bpf程序的作者可以直接使用正常的C代码访问数据包，因为：

void *data = (void *)(long)skb->data;
void *data_end = (void *)(long)skb->data_end;
struct eth_hdr *eth = data;
struct iphdr *iph = data + sizeof(*eth);
struct udphdr *udp = data + sizeof(*eth) + sizeof(*iph);

if (data + sizeof(*eth) + sizeof(*iph) + sizeof(*udp) > data_end)
        return 0;
if (eth->h_proto != htons(ETH_P_IP))
        return 0;
if (iph->protocol != IPPROTO_UDP || iph->ihl != 5)
        return 0;
if (udp->dest == 53 || udp->source == 9)
        ...;

这使得程序与LD_ABS insn相比更容易编写，而且速度明显加快。

5. 分支修剪

验证器实际上并没有走完程序中所有可能的路径。对于每一个要分析的新分支，验证器会查看它以前在这个指令时的所有状态。如果其中任何一个包含当前状态的子集，该分支就会被 "修剪"--也就是说，之前的状态被接受这一事实意味着当前的状态也会被接受。例如，如果在前一个状态下，r1持有一个数据包指针，而在当前状态下，r1持有一个范围一样长或更长的数据包指针，并且至少有同样严格的对齐方式，那么r1是安全的。同样，如果r2之前是NOT_INIT，那么从那时起它就不可能被任何路径使用，所以r2中的任何值（包括另一个NOT_INIT）都是安全的。具体的实现是在函数regsafe()中。修剪不仅考虑寄存器，而且考虑堆栈（以及它可能持有的任何溢出寄存器）。它们都必须是安全的，这样分支才能被剪除。这在 states_equal()中实现。

6. eBPF验证器报错信息

以下是在日志中看到的几个无效的eBPF程序和验证器错误信息的例子。

程序有不可到达的指令

static struct bpf_insn prog[] = {
BPF_EXIT_INSN(),
BPF_EXIT_INSN(),
};

Error: unreachable insn 1

程序读取未初始化的寄存器

BPF_MOV64_REG(BPF_REG_0, BPF_REG_2),
BPF_EXIT_INSN(),

Error: 0: (bf) r0 = r2 R2 !read_ok

程序在退出前没有初始化R0

BPF_MOV64_REG(BPF_REG_2, BPF_REG_1),
BPF_EXIT_INSN(),

Error: 0: (bf) r2 = r1 1: (95) exit R0 !read_ok

程序访问堆栈超出了边界

BPF_ST_MEM(BPF_DW, BPF_REG_10, 8, 0),
BPF_EXIT_INSN(),

Error: 0: (7a) (u64 )(r10 +8) = 0 invalid stack off=8 size=8

程序将地址传入函数之前没有初始化堆栈

BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
BPF_LD_MAP_FD(BPF_REG_1, 0),
BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
BPF_EXIT_INSN(),

Error: 0: (bf) r2 = r10 1: (07) r2 += -8 2: (b7) r1 = 0x0 3: (85) call 1 invalid indirect read from stack off -8+0 size 8

程序在调用map_lookup_elem()函数时使用无效的map_fd=0

BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
BPF_LD_MAP_FD(BPF_REG_1, 0),
BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
BPF_EXIT_INSN(),

Error: 0: (7a) (u64 )(r10 -8) = 0 1: (bf) r2 = r10 2: (07) r2 += -8 3: (b7) r1 = 0x0 4: (85) call 1 fd 0 is not pointing to valid bpf_map

程序在访问map element前没检查map_lookup_elem()的返回值。

BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
BPF_LD_MAP_FD(BPF_REG_1, 0),
BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
BPF_ST_MEM(BPF_DW, BPF_REG_0, 0, 0),
BPF_EXIT_INSN(),

Error: 0: (7a) (u64 )(r10 -8) = 0 1: (bf) r2 = r10 2: (07) r2 += -8 3: (b7) r1 = 0x0 4: (85) call 1 5: (7a) (u64 )(r0 +0) = 0 R0 invalid mem access 'map_value_or_null'

程序正确检查map_lookup_elem()返回值是否为NULL，但以不正确的对齐方式访问内存

BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
BPF_LD_MAP_FD(BPF_REG_1, 0),
BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 1),
BPF_ST_MEM(BPF_DW, BPF_REG_0, 4, 0),
BPF_EXIT_INSN(),

Error: 0: (7a) (u64 )(r10 -8) = 0 1: (bf) r2 = r10 2: (07) r2 += -8 3: (b7) r1 = 1 4: (85) call 1 5: (15) if r0 == 0x0 goto pc+1 R0=map_ptr R10=fp 6: (7a) (u64 )(r0 +4) = 0 misaligned access off 4 size 8

程序正确检查map_lookup_elem()的返回值是否为NULL，并在'if'分支的一侧以正确的对齐方式访问内存，但在'if'分支的另一侧却没这样做

BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
BPF_LD_MAP_FD(BPF_REG_1, 0),
BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 2),
BPF_ST_MEM(BPF_DW, BPF_REG_0, 0, 0),
BPF_EXIT_INSN(),
BPF_ST_MEM(BPF_DW, BPF_REG_0, 0, 1),
BPF_EXIT_INSN(),

Error: 0: (7a) (u64 )(r10 -8) = 0 1: (bf) r2 = r10 2: (07) r2 += -8 3: (b7) r1 = 1 4: (85) call 1 5: (15) if r0 == 0x0 goto pc+2 R0=map_ptr R10=fp 6: (7a) (u64 )(r0 +0) = 0 7: (95) exitfrom 5 to 8: R0=imm0 R10=fp 8: (7a) (u64 )(r0 +0) = 1 R0 invalid mem access 'imm'

指针设置为NULL，执行套接字查找的程序未进行检查

BPF_MOV64_IMM(BPF_REG_2, 0),
BPF_STX_MEM(BPF_W, BPF_REG_10, BPF_REG_2, -8),
BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
BPF_MOV64_IMM(BPF_REG_3, 4),
BPF_MOV64_IMM(BPF_REG_4, 0),
BPF_MOV64_IMM(BPF_REG_5, 0),
BPF_EMIT_CALL(BPF_FUNC_sk_lookup_tcp),
BPF_MOV64_IMM(BPF_REG_0, 0),
BPF_EXIT_INSN(),

Error: 0: (b7) r2 = 0 1: (63) (u32 )(r10 -8) = r2 2: (bf) r2 = r10 3: (07) r2 += -8 4: (b7) r3 = 4 5: (b7) r4 = 0 6: (b7) r5 = 0 7: (85) call bpf_sk_lookup_tcp#65 8: (b7) r0 = 0 9: (95) exit Unreleased reference id=1, alloc_insn=7

执行套接字查询的程序未对返回值进行NULL检查

BPF_MOV64_IMM(BPF_REG_2, 0),
BPF_STX_MEM(BPF_W, BPF_REG_10, BPF_REG_2, -8),
BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
BPF_MOV64_IMM(BPF_REG_3, 4),
BPF_MOV64_IMM(BPF_REG_4, 0),
BPF_MOV64_IMM(BPF_REG_5, 0),
BPF_EMIT_CALL(BPF_FUNC_sk_lookup_tcp),
BPF_EXIT_INSN(),

Error: 0: (b7) r2 = 0 1: (63) (u32 )(r10 -8) = r2 2: (bf) r2 = r10 3: (07) r2 += -8 4: (b7) r3 = 4 5: (b7) r4 = 0 6: (b7) r5 = 0 7: (85) call bpf_sk_lookup_tcp#65 8: (95) exit Unreleased reference id=1, alloc_insn=7