Syzkaller 中用到 kcov 记录覆盖分析

0x00 写在前面

现代模糊测试技术都需要观察一些反馈信息来引导模糊测试，而当下最常用的方式是使用覆盖率信息，因此，本文又是一篇目的导向性的探索类文本。旨在探索 Linux 内核提供的 kcov 的使用进行一定的探索，让其能在脑海中进行实例化，有个理性的认知。

0x01 基本概念

官方文档 对 kcov 的介绍是，这是个用于帮助进行覆盖率引导的 fuzz 的好东西。运行的内核的覆盖率数据将会被导出到一个 kcov 的 debugfs 文件中。`kcov 能够精确地捕捉到每个单独的系统调用的覆盖率。kcov 不是为了收集尽可能多的覆盖率，而是为了收集一些与系统调用输入有关且相对稳定的覆盖率。为了实现这个目标，kcov 不会收集软/硬中断中的覆盖率，并且禁用了一些内核中本质上不确定的部分的插桩。kcov 还能够从检测代码中收集比较操作数（此功能目前需要使用 clang 编译内核）。

0x02 进行实验

对于官网中给出的记录覆盖率的代码，我是在 QEMU 托起的系统中编译并运行的，会打印一些地址，但是当我在系统中执行了一些命令之后，这些地址还是这些，并没有什么变化。

使用 qemu 托起一个内核。

1
2
3
4
5
6
7
8
9
10
11
12
sudo qemu-system-x86_64 \
	-m 2G \
	-smp 2 \
	-kernel /home/th1nk5t4ti0n/Desktop/Ron/fuzz/Syzkaller/linux/arch/x86/boot/bzImage \
	-append "console=ttyS0 root=/dev/sda earlyprintk=serial net.ifnames=0" \
	-drive file=/home/th1nk5t4ti0n/Desktop/Ron/fuzz/Syzkaller/image/stretch.img,format=raw \
	-net user,host=10.0.2.10,hostfwd=tcp:127.0.0.1:10021-:22 \
	-net nic,model=e1000 \
	-enable-kvm \
	-nographic \
	-pidfile vm.pid \
	2>&1 | tee vm.log

在内核中编译运行官网中的例子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
// code come frome：https://www.kernel.org/doc/html/latest/dev-tools/kcov.html

#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <sys/ioctl.h>
#include <sys/mman.h>
#include <unistd.h>

#define KCOV_INIT_TRACE             _IOR('c', 1, unsigned long) // 读方向，字符设备类型，序号为1，数据的尺寸为unsigned long
#define KCOV_ENABLE                 _IO('c', 100)
#define KCOV_DISABLE                _IO('c', 101)
#define COVER_SIZE                  (64<<10)

#define KCOV_TRACE_PC  0 // Coverage collection
#define KCOV_TRACE_CMP 1 // Comparison operands collection

int main(int argc, char **argv){
    int fd;
    unsigned long *cover;

    // 单个fd只允许单个线程使用
    fd = open("/sys/kernel/debug/kcov",O_RDWR);
    if(fd == -1){
        perror("open");
        exit(1);
    }

    // Setup trace 的模式和大小
    if(ioctl(fd,KCOV_INIT_TRACE,COVER_SIZE)){
        perror("ioctl");
        exit(1);
    }

    // Mmap buffer shared between kernel- and user-space. 
    cover = (unsigned long*)mmap(NULL,COVER_SIZE*sizeof(unsigned long),PROT_READ|PROT_WRITE, MAP_SHARED,fd,0);
    if((void*)cover == MAP_FAILED){
        perror("mmap");
        exit(1);
    }

    // 允许收集当前线程的内核代码覆盖率
    if(ioctl(fd,KCOV_ENABLE,KCOV_TRACE_PC)){
        perror("ioctl");
        exit(1);
    }

    // 在ioctl调用之后，重启代码覆盖率收集
    // gcc内置函数
    __atomic_store_n(&cover[0],0,__ATOMIC_RELAXED);

    // 系统调用
    // char tmp[100];
    // int fd2 = open("/etc/passwd",O_RDONLY);
    // read(fd2,tmp,99);
    // close(fd2);
    read(-1,NULL,0);

    // 读取收集到的代码覆盖情况
    int i,n;
    n = __atomic_load_n(&cover[0],__ATOMIC_RELAXED);
    for(int i=0; i<n; i++){
        printf("0x%lx\n",cover[i+1]);
    }

    // 取消当前进程的内核代码覆盖率收集
    if(ioctl(fd,KCOV_DISABLE,KCOV_TRACE_PC)){
        perror("ioctl");
        exit(1);
    }

    // 释放资源
    if(munmap(cover,COVER_SIZE*sizeof(unsigned int))){
        perror("munmap");
        exit(0);
    }
    if(close(fd)){
        perror("close");
        exit(1);
    }

    return 0;
}

然后输出的数据可以重定向到文件，也可以直接打印到缓冲区，反正也不多。

1
2
3
4
5
6
7
8
9
10
11
12
0xffffffff81730ff1
0xffffffff81730deb
0xffffffff817a9840
0xffffffff817a5f62
0xffffffff817a5fe2
0xffffffff817a60f3
0xffffffff817a98b0
0xffffffff81730f1e
0xffffffff810a43c6
0xffffffff810a4414
0xffffffff810a4444
0xffffffff81313f76

可以看到 kcov 成功对上述测试例子中的系统调用的执行进行了记录。并且打印的数据是一系列的地址，这些地址显然都是内核中的地址（高位全ff）。

0x03 代码分析

事实上， kcov 总共支持的所有插桩都在 kcov.c 和 kcov.h 中进行了注明，尽管不同版本有些许差别，但是基本上是一致的。通过查看内核中的代码，这些插桩函数总结如下

1
2
3
4
5
6
7
8
9
10
__sanitizer_cov_trace_const_cmp1
__sanitizer_cov_trace_const_cmp2
__sanitizer_cov_trace_const_cmp4
__sanitizer_cov_trace_const_cmp8
__sanitizer_cov_trace_cmp1
__sanitizer_cov_trace_cmp2
__sanitizer_cov_trace_cmp4
__sanitizer_cov_trace_cmp8
__sanitizer_cov_trace_switch
__sanitizer_cov_trace_pc

这些函数应该分成两类，一类是 __sanitizer_cov_trace_pc 这个主要是对基本块进行插桩的函数，用于记录基本块覆盖情况。另一类是其他剩下的，主要功能是记录对应的比较指令及其实际的 op 值。

覆盖率插桩

函数定义在 kernel/kcov.c:185 中，该函数不接收参数，当其被调用时就会将自己函数退出时的返回地址写入到文件中。于是后期通过读取这个文件中的返回地址就能定位到相应的基本块是否被执行了。由于在模糊测试内核时是关闭了 KASLR 的，因此同一个基本块中的指令的地址始终是不变的，就由此来判断基本块是否已经执行了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/*
 * Entry point from instrumented code.
 * This is called once per basic-block/edge.
 */
void notrace __sanitizer_cov_trace_pc(void)
{
	struct task_struct *t;
	unsigned long *area;
	unsigned long ip = canonicalize_ip(_RET_IP_);
	unsigned long pos;

	t = current;
	if (!check_kcov_mode(KCOV_MODE_TRACE_PC, t))
		return;

	area = t->kcov_area;
	/* The first 64-bit word is the number of subsequent PCs. */
	pos = READ_ONCE(area[0]) + 1;
	if (likely(pos < t->kcov_size)) {
		area[pos] = ip;
		WRITE_ONCE(area[0], pos);
	}
}
EXPORT_SYMBOL(__sanitizer_cov_trace_pc);

Syzkaller 与 AFL 一致，是使用边覆盖率来统计覆盖情况的，因此他会将实际记录得到的每个基本块的记录值 PC 和前一个基本块的 PC 值进行一个哈希之后的异或值来唯一标识一条边，将该值称为 signal ，这个过程中存在过滤函数和去重函数，会进行一定的筛选。然后 Syzkaller 通过维护一个字典，该字典的键是 signal 来判断每次执行是否有新覆盖产生。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
void write_coverage_signal(cover_t* cov, uint32* signal_count_pos, uint32* cover_count_pos, uint32* hit_num_pos)
{
	// Write out feedback signals.
	// Currently it is code edges computed as xor of two subsequent basic block PCs.
	cover_data_t* cover_data = (cover_data_t*)(cov->kcov_area + cov->data_offset);
	if (flag_collect_signal) {
		uint32 nsig = 0;
		cover_data_t prev_pc = 0;
		bool prev_filter = true;
		for (uint32 i = 0; i < cov->size; i++) {
			cover_data_t pc = cover_data[i] + cov->pc_offset;
			uint32 sig = pc;
			if (use_cover_edges(pc))
				sig ^= hash(prev_pc);
			bool filter = coverage_filter(pc);
			// Ignore the edge only if both current and previous PCs are filtered out
			// to capture all incoming and outcoming edges into the interesting code.
			bool ignore = !filter && !prev_filter;
			prev_pc = pc;
			prev_filter = filter;
			if (ignore || dedup(sig))
				continue;
			write_output(sig);
			nsig++;
		}
		// Write out number of signals.
		*signal_count_pos = nsig;
	}
	//...
}

但 kcov 也不是傻傻的都插桩，具体而言，基于 LLVM 方式进行插桩时，会通过 dominator 树等方法判断一个基本块是否可以不插桩，但不影响统计边覆盖。即通过仅插桩部分基本块便可以实现有效捕获所有通过的情况。

比较指令插桩

其他的指令我们按照他们的情况分成两类，其实根据名字不能理解，就是针对不同的情况进行的插桩。

__sanitizer_cov_trace_cmpx 就是插桩的两个 op 值都是来自变量的情况，其中 x 标识比较数的位宽。

__sanitizer_cov_trace_const_cmpx 就是插桩一个变量与一个 const 类型的 op 进行比较的情况，其中 x 标识比较数的位宽。

__sanitizer_cov_trace_switch 则是对 switch 指令进行的插桩。

1
2
3
4
5
6
7
8
9
10
11
12
// 类型 I
__sanitizer_cov_trace_const_cmp1
__sanitizer_cov_trace_const_cmp2
__sanitizer_cov_trace_const_cmp4
__sanitizer_cov_trace_const_cmp8
__sanitizer_cov_trace_cmp1
__sanitizer_cov_trace_cmp2
__sanitizer_cov_trace_cmp4
__sanitizer_cov_trace_cmp8

// 类型 II
__sanitizer_cov_trace_switch

比较指令类

由于这类指令大多都是雷同的，这里就拿一类进行简单说明，代码定义是在 kernel/kcov.c:244 。看代码就是非常简单明了，接受两个参数就是其对应的两个 op 的值。在写入到文件时，分成了4个部分，先写了这个比较指令的类型，然后是两个 op ，最后是这个函数被调用时的返回地址。

1
2
3
4
5
void notrace __sanitizer_cov_trace_cmp1(u8 arg1, u8 arg2)
{
	write_comp_data(KCOV_CMP_SIZE(0), arg1, arg2, _RET_IP_);
}
EXPORT_SYMBOL(__sanitizer_cov_trace_cmp1);

switch指令

代码定义是在 kernel/kcov.c:296 。这个就略微复杂一点，传进来两个值，第一个值是变量，即根据这个变量进行 switch 的分支选择。第二个值是一个数组，数组第一个元素是 switch 中的 case 数量，第二个元素是 case 值的位宽，后面依次是每个 case 值。

于是通过一通计算，写入文件的第一个值是同事表明了这是一个 switch 类型的，与前面的 cmp 类型区分，同时还包含了 case 值的位宽信息，然后将所有的 case 依次写入，写入很多行，每行表示一个 case 的执行情况，最后还是给定一个该指令的返回地址。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void notrace __sanitizer_cov_trace_switch(u64 val, u64 *cases)
{
	u64 i;
	u64 count = cases[0];
	u64 size = cases[1];
	u64 type = KCOV_CMP_CONST;

	switch (size) {
	case 8:
		type |= KCOV_CMP_SIZE(0);
		break;
	case 16:
		type |= KCOV_CMP_SIZE(1);
		break;
	case 32:
		type |= KCOV_CMP_SIZE(2);
		break;
	case 64:
		type |= KCOV_CMP_SIZE(3);
		break;
	default:
		return;
	}
	for (i = 0; i < count; i++)
		write_comp_data(type, cases[i + 2], val, _RET_IP_);
}
EXPORT_SYMBOL(__sanitizer_cov_trace_switch);
#endif /* ifdef CONFIG_KCOV_ENABLE_COMPARISONS */

这是 LLVM 中的代码，情况和描述也一致

1
2
3
4
5
6
7
8
9
// Called before a switch statement.
// Val is the switch operand.
// Cases[0] is the number of case constants.
// Cases[1] is the size of Val in bits.
// Cases[2:] are the case constants.
void __sanitizer_cov_trace_switch(uint64_t Val, uint64_t *Cases);

// 然后根据 case 的值的位,直接调用相应的写函数(所以不会被__sanitizer_cov_trace_const_cmp*捕获到)
// 枚举所有 case,每个单独写一次,就写:比较位数,case值,当前switch值,返回地址.

Syzkaller获取

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
void kcov_comparison_t::write()
{
	if (type > (KCOV_CMP_CONST | KCOV_CMP_SIZE_MASK))
		failmsg("invalid kcov comp type", "type=%llx", type);

	// Write order: type arg1 arg2 pc.
	write_output((uint32)type);

	// KCOV converts all arguments of size x first to uintx_t and then to
	// uint64. We want to properly extend signed values, e.g we want
	// int8 c = 0xfe to be represented as 0xfffffffffffffffe.
	// Note that uint8 c = 0xfe will be represented the same way.
	// This is ok because during hints processing we will anyways try
	// the value 0x00000000000000fe.
	switch (type & KCOV_CMP_SIZE_MASK) {
	case KCOV_CMP_SIZE1:
		arg1 = (uint64)(long long)(signed char)arg1;
		arg2 = (uint64)(long long)(signed char)arg2;
		break;
	case KCOV_CMP_SIZE2:
		arg1 = (uint64)(long long)(short)arg1;
		arg2 = (uint64)(long long)(short)arg2;
		break;
	case KCOV_CMP_SIZE4:
		arg1 = (uint64)(long long)(int)arg1;
		arg2 = (uint64)(long long)(int)arg2;
		break;
	}
	bool is_size_8 = (type & KCOV_CMP_SIZE_MASK) == KCOV_CMP_SIZE8;
	if (!is_size_8) {
		write_output((uint32)arg1);
		write_output((uint32)arg2);
	} else {
		write_output_64(arg1);
		write_output_64(arg2);
	}
}

0x04 逆向分析测试

有了上述源代码分析过程，还可以将编译完成的 vmlinux 放入 IDA 中对其进行查看，可以看到确实只有必要的基本块被插桩了，其余的基本块可以通过这些插桩的基本块来计算出是否经过了。

trace_pc逆向

而当我们在编译内核时，打开了 CONFIG_KCOV_ENABLE_COMPARISONS 时，再进行编译得到 vmlinux 后，通过 IDA 反汇编也能看到对比较指令的插桩情况。

比较指令插桩情况

0x05 动态分析

内核编译好之后，通过其调试信息和记录的返回地址可以很好将执行情况与源码进行对应。 Syzkaller也是基于这一技术在 web 端进行实时代码行数覆盖监控的。

使用 objdump 可以提取出 vmlinux 中的汇编指令，如下所示

1
2
3
4
5
6
$ objdump -d --no-show-raw-insn  vmlinux|grep __sanitizer_cov_trace_const_cmp

# 得到的数据如下
# 该call指令的地址 xxx 被call函数的地址 被call函数的名字
ffffffff81002381:	callq  ffffffff814e8fb0 <__sanitizer_cov_trace_const_cmp8>
ffffffff810024f7:	callq  ffffffff814e8f90 <__sanitizer_cov_trace_const_cmp4>

然后使用 addr2line 可以结合 vmlinux 将指令地址映射回源码位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
$ addr2line -afip -e vmlinux
0xffffffff81730ff1: __x64_sys_read at ??:?
0xffffffff81730deb: ksys_read at ??:?
0xffffffff817a9840: __fdget_pos at ??:?
0xffffffff817a5f62: __fget_light at file.c:?
0xffffffff817a5fe2: __fget_light at file.c:?
0xffffffff817a60f3: __fget_light at file.c:?
0xffffffff817a98b0: __fdget_pos at ??:?
0xffffffff81730f1e: ksys_read at ??:?
0xffffffff810a43c6: fpregs_assert_state_consistent at ??:?
0xffffffff810a4414: fpregs_assert_state_consistent at ??:?
0xffffffff810a4444: fpregs_assert_state_consistent at ??:?
0xffffffff81313f76: exit_to_user_mode_prepare at common.c:?

然后结合上述两个工具，可以实现实时得到模糊测试过程中，内核代码执行到了什么位置。

需要注意的是，直接 ojbdump 得到的地址是 call xxx_trace_xx 的指令地址，而他的返回地址即函数写出来的值是下一条指令的地址，因此应该将这个 call 指令的地址的值增加 5 以和模糊测试过程中的日志相对应。

将模糊测试中的数据打印出来可以观测到下面的这一的信息，这就是屏蔽掉高32位后的覆盖数据。

1
[2203351236, 2203351172, 2179552298, 2179608616, 2201270029, 2203350567, 2179525419, 2179552243, 2197504823, 2177430266, 2197556903, 2171773570, 2177387257, 2177387333, 2197449769, 2197492194,...

0x06 参考链接

kcov

kcov-用于内核模糊测试的代码覆盖

SanitizerCoverage