eBPF Verifier内存越界实例分析

语言: CN / TW / HK

时间 2022-09-09 16:31:22 Linux内核之旅

主题: eBPF

更多内核安全、eBPF分析和实践文章，请关注博客:

http://kernel-security.blog.csdn.net/

eBPF基础架构

eBPF程序分为两部分: 用户态和内核态代码。

eBPF内核代码:

这个代码首先需要经过编译器（比如LLVM）编译成eBPF字节码，然后字节码会被加载到内核执行。所以这部分代码理论上用什么语言编写都可以，只要编译器支持将该语言编译为eBPF字节码即可；
目前绝大多数工具都是用的C语言来编写eBPF内核代码，包括BCC。bpftrace提供了一种易用的脚本语言来帮助用户快速高效的使用eBPF功能，其背后的原理还是利用LLVM 将脚本转为eBPF字节码；

eBPF用户态代码:

这部分代码负责将eBPF内核程序加载到内核，与eBPF MAP交互，以及接收eBPF内核程序发送出来的数据；
这个功能的本质上是通过Linux OS提供的syscall（bpf syscall + perf_event_open syscall）完成的，因此这部分代码你可以用任何语言实现。比如BCC使用python，libbpf使用c或者c++，TRACEE使用Go等等；

eBPF数据源

性能分析大师Brendan Gregg(Intel Fellow)总结的Linux BPF Tracing Tools上展示了丰富多彩的eBPF钩子类型，这些钩子类型提供了可以加载BPF程序的范围。

fentry/fexit
Tracepoints
network devices (tc/xdp)
network routes
TCP congestion algorithms
sockets (data level)
kernel functions (kprobes)
userspace functions (uprobes)
system calls

eBPF框架的发展历程

2014年9月引入了bpf() syscall，将eBPF引入用户态空间。自带迷你libbpf库，简单对bpf()进行了封装，功能是将eBPF字节码加载到内核。
2015年2月份 Kernel 3.19 引入bpf_load.c/h文件，对上述迷你libbpf库再进行封装，功能是将eBPF elf二进制文件加载到内核（目前已过时，不建议使用）。
2015年4月 BCC项目创建，提供了eBPF一站式编程。

1.创建之初，基于上述迷你libbpf库来加载eBPF字节码。

2.提供了Python接口。

2015年11月 Kernel 4.3 引入标准库 libbpf

该标准库由Huawei 2012 OS内核实验室的王楠提交。

2018年为解决BCC的缺陷，CO-RE（Compile Once， Run Everywhere）的想法被提出并实现，最后达成共识：libbpf + BTF + CO-RE代表了eBPF的未来，BCC底层实现逐步转向libbpf。

eBPF可移植性痛点和解决方案

在内核版本A上编译的eBPF程序，无法直接在另外一个内核版本B上运行。造成可执行差的根本原因在于eBPF程序访问的内核数据结构(内存空间）是不稳定的，经常随内核版本更迭而变化。

目前使用BCC的方案通过在部署机器上动态编译eBPF源代码可以来解决移植性问题。每一次eBPF程序运行都需要进行一次编译，而且需要在部署机器上按照上百兆大小的依赖，如编译器和头文件Clang/LLVM + Linux headers等。同时在Clang/LLVM编译过程中需要消耗大量的资源（CPU/内存），对业务性能也会造成很大影响。

解决方案（CO-RE Compile Once，Run Everywhere）：

1)BTF：将内核数据结构信息高效压缩和存储（相比于DWARF，可达到超过100倍的压缩比）

2)LLVM/Clang编译器：编译eBPF代码的时候记录下relocation相关的信息

3)Libbpf：基于BTF和编译器提供的信息，动态relocate数据结构

其中BTF为重要组成部分，Linux Kernel 5.2及以上版本自带BTF文件，低版本需要手动移植。通过分析内核源码，可以发现BTF文件的生成并不需要改动内核，只依赖：

带有debug info的vmlinux image
pahole
LLVM

这意味着，我们可以自己为低版本内核生产BTF文件，以此让低内核版本支持CORE。

eBPF程序实例分析

eBPF程序会被LLVM编译为eBPF字节码，eBPF字节码需要通过eBPF Verifier的(静态)验证后，才能真正运行。边界检查是eBPF Verifier的重点工作，目的是为了防止eBPF程序内存越界访问。

接下来通过在eBPF程序中简单的增加、删减print打印信息触发不同原因的几种边界检查异常导致验证失败的例子，进一步讲解深层的原理。

程序实验环境：

1)LLVM 11

2)Linux Kernel 5.8

3)Libbpf commit @9c44c8a

1)内存越界：

SEC("kprobe/do_unlinkat")
int BPF_KPROBE(do_unlinkat, int dfd, struct filename *name) 
{ 
  // 获取一个数组指针array（数组MAX_SIZE为16个字节）
  u32 key = 0;
  char *array = bpf_map_lookup_elem(&array_map, &key);
  if (array == NULL) 
      return 0;
      // 获取当前运行程序的CPU编号(当前机器的CPU有16个核）
  unsigned int pos = bpf_get_smp_processor_id();
   // 根据下表修改数组的值 
  array[pos] = 1;
  return 0; 
}

上述代码编译运行后，提示Verifier失败，然后使用objdump命令来看一下具体的字节码，通过以下字节码程序，可以看到Verifier失败的原因在于第14行R6寄存器(变量pos)没有进行边界检查导致。

Root Cause:

当eBPF Verifier走到第14行的时候尝试去访问array数组，但是此时数组的下标pos是来自bpf_get_smp_processor_id获取到的unsigned int 类型的动态变量，此时Verifier无法判断变量的具体数值，所以会保守认为可能会达到最大值，这样的话就会超出array数组的范围，造成内存越界。

0000000000000000 <do_unlinkat>:
; int BPF_KPROBE(do_unlinkat, int dfd, struct filename *name) 0:  r1 = 0
;  u32 key = 0;
1:  *(u32 *)(r10 - 4) = r1
2:  r2 = r10
3:  r2 += -4
;    char *array = bpf_map_lookup_elem(&array_map, &key); 4:    r1 = 0 ll
6:  call 1
7:  r6 = r0
;  if (array == NULL)
8:  if r6 == 0 goto +6 <LBB0_2>
;    unsigned int pos = bpf_get_smp_processor_id();; 9:  call 8
;    array[pos] = 1; 10:  r0 <<= 32
11:  r0 >>= 32
12:  r6 += r0
13:  r1 = 1
;  array[pos] = 1;
14:  *(u8 *)(r6 + 0) = r1

添加边界检查代码

if (pos < MAX_SIZE)
  if r0 > 15 goto +3 <LBB0_3>

2)Verifier验证机制和编译器优化机制不一致导致边界检查不通过

①使用错误寄存器做边界检查：

SEC("kprobe/do_unlinkat")
int BPF_KPROBE(do_unlinkat, int dfd, struct filename *name)
{
  // 获取一个数组指针array（数组MAX_SIZE为16个字节）
  u32 key = 0;
  char *array = bpf_map_lookup_elem(&array_map, &key); if (array == NULL)
  return 0;
  // 获取当前运行程序的CPU编号(当前机器的CPU有16个核）
  unsigned int pos = bpf_get_smp_processor_id();;
  // 修改数值
  if (pos < MAX_SIZE){
    array[pos] = 1;
  pos += 1;
}
// debug代码，输出一些上下文信息
  bpf_printk("debug %d %d %d\n", bpf_get_current_pid_tgid() >> 32, bpf_get_current_pid_tgid(), array[1]);
  // 修改数值
  if (pos < MAX_SIZE)
    array[pos] = 1;
  return 0;
}

编译这个代码后Verifier验证通过，可以正常运行。但是此时如果把bpf_printk打印信息删掉，竟然提示Verifier验证失败，原因是R0寄存器（变量pos）没有通过边界检查，但是明明已经加了边界检查代码，怎么还会出现问题，这么神奇！

Root Cause:

由于编译器的优化策略，导致删减bpf_printk后编译生成的eBPF字节码使用寄存器r1(表示pos变量）来进行边界检查，但是却用r0+1（同样表示pos变量）来访问数组array；
相比之下，从eBPF verifier的角度来看，由于在编译过程中，r1和r0+1的关联性丢失了，导致eBPF verifier无法知道pos变量已经通过了检查，因此错误的认为pos变量没有进行边界检查，不允许程序运行；

②寄存器溢出或重新加载后，状态丢失：

SEC("kprobe/do_unlinkat")
int BPF_KPROBE(do_unlinkat, int dfd, struct filename *name)
{
  // 获取一个数组指针array（数组MAX_SIZE为16个字节）
  u32 key = 0;
  char *array = bpf_map_lookup_elem(&array_map, &key); if (array == NULL)
  return 0;
  // 获取当前运行程序的CPU编号(当前机器的CPU有16个核）
  unsigned long pos = bpf_get_smp_processor_id();;
  // 修改数值
  if (pos < MAX_SIZE){
    for (unsigned long i = 0; i < MAX_SIZE; i++) 
      bpf_printk("debug %d %d %d\n", bpf_get_current_pid_tgid() >> 32, \
       bpf_get_current_pid_tgid(), array[i]);
    array[pos] = 1;
  }
  return 0;
}

在上述边界检查代码中添加一段print调试打印信息后编译验证又会出现Verifier失败，通过排查发现不是已知的两类问题，依然使用objdump查看添加后的字节码信息。

Root Cause:

加入bpf_printk后通过字节码可以看到,代码先使用R0（表示pos变量）进行边界检查。由于当前寄存器数量不足，编译器决定将将R0临时保存到栈上的空间（R10-16，在eBPF字节码中，R10存储存放着 eBPF 栈空间的栈帧指针的地址)，这样R0就可以空闲出来，留给其他代码使用，我们称这种行为为寄存器溢出（register spill）；
当真正需要使用pos变量的时候，编译器会从栈上（R10-16）将之前保存的内容取出来赋给R1（也表示pos变量），然后使用R1对数组array进行访问。但神奇的是，当寄存器溢出发生时，pos变量的状态丢失了，eBPF忘记了该变量曾经进行了边界检查，导致程序无法通过验证；

解决方案：

在源码中加入 &= 操作符，引导编译器生成理想的eBPF字节码

array[pos &= MAX_SIZE - 1] = 1;

如果上述方法失效，无法引导编译器，那么针对出错的部分源代码人工编写eBPF字节码，替代编译器生成的字节码

#define STR(s) #s #define XSTR(s) STR(s)
#define asm_variable_bound_check(variable)    \
({                  \
  asm volatile (            \
  "%[tmp] &= " XSTR(MAX_SIZE - 1) " \n"  \
  :[tmp]"+&r"(variable)        \
  );                \
})
asm_check(pos); 
array[pos] = 1;

总结

eBPF 作为 Linux 内核一项革命性的技术，起源于 Linux 内核，该技术可以安全而高效地拓展内核的能力，但快速发展的同时，也会存在很多新鲜出炉的问题，给广大开发者尤其是入门者带来个很大的困扰，本文从几个实例的角度来对问题进行分析和解答，有相关开发疑惑的同学可以参考借鉴。

「其他文章」