背景

我们在博客上花费了大量时间记录Lucid（我们的全系统快照模糊器）的开发过程，现在终于开始使用它进行实际的模糊测试。本文重点记录了我让Lucid在真实目标上运行模糊测试的过程。

离线博客快照开发

自上一篇文章以来，最大的变化是我们处理快照的方式。在简单的开发目标上，我发现旧的快照方法在紧密的模糊测试循环中扩展性迅速恶化。

旧快照方法回顾

模糊器通过将Bochs x86模拟器的静态PIE ELF镜像加载到模糊器进程中，并在运行目标的沙盒化模拟器与执行模糊操作的模糊器之间进行上下文切换。因为我们加载并沙盒化了Bochs，我们知道镜像中每个可写内存段的位置，以及动态内存的位置，因为我们不允许Bochs与操作系统交互来分配内存，模糊器会处理这些。

我们做的将可写内存段映射到内存中连续的位置。当我们对Bochs进行快照时，只需捕获该内存状态并保存。我们将内存保存为内存支持的文件。在Linux上，快照恢复变得非常简单，我们只需将内存支持的文件mmap回连续的可写内存区域。只需一个系统调用即可恢复内存。我们这样做主要是因为非常简单。

结果发现，当你要求内核每秒数千次地使数十亿字节的页面失效/销毁/覆盖时，扩展性很差。我记不清瓶颈是什么，但似乎mmap请求需要某种序列化，并且大部分CPU时间都花在销毁脏内存支持页面上。一旦我在开发箱上启动8个核心，我的扩展因子就变得非常糟糕。所以我必须找到另一种方法，可能是一种不依赖于每次迭代恢复所有可写内存，而是差异性地重置Bochs中脏内存的方法。

线性扩展的新策略

我们希望随着为模糊测试引入更多核心，Lucid能够线性扩展，因此我们希望扩展因子与使用的核心数量成一对一关系。100个核心应该比单核模糊测试带来100倍的速度提升。因此，我们需要一种方法仅差异性地恢复脏内存，而不是所有可写内存。我们还希望采用不通过系统调用调用内核的方法，因为这会跨核心产生瓶颈。

我决定采用的方法并不新颖，实际上类似于许多模糊器在黑盒目标上获取覆盖率反馈的方式。我最终将所有为Bochs加载的可写页面标记为无写入权限（严格为PROT_READ）。这样，当Bochs尝试写入页面时，会导致页面错误。在Linux上，每当发生这种情况时，你的进程会收到一个信号，你可以调用一个函数来处理信号。因此，我修补了Bochs来处理这些页面错误，在信号处理函数中，Bochs将故障地址标记为Bochs和Lucid都可以访问的数据结构中的脏页面。

现在，我们记录了一个被弄脏的页面，然后使该页面永久可写，并在每次快照重置时恢复该页面。这种设计将快照恢复简化为从快照内存到脏内存的一系列memcpy调用。现在我们实现了差异恢复，所有操作都通过memcpy在用户空间完成，在热路径中恢复快照时不调用系统调用。这似乎可以完美扩展，我们非常接近我们追求的一对一扩展因子。模糊器在执行热模糊循环时100%的时间都在用户空间。

 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

+----------------------------------------------+
| [1] 模糊测试用例开始                         |<---------------+
| Lucid开始在Bochs中执行目标代码。             |                |
+----------------------------------------------+                |
                               |                                |
                               v                                |
+----------------------------------------------+                |
| [2] Bochs写入页面                            |                |
| 尝试写入 -> 页面仅为PROT_READ。              |                |
+----------------------------------------------+                |
                               |                                |
                               v                                |
+----------------------------------------------+                |
| [3] 页面错误处理程序                         |                |
| 发生错误 -> 处理程序将页面添加到脏列表       |                |
| 并将保护设置为PROT_WRITE。                   |                |
+----------------------------------------------+                |
                               |                                |
                               v                                |
+----------------------------------------------+                |
| [4] 模糊测试用例结束                         |                |
| 执行完成                                    |                |
+----------------------------------------------+                |
                               |                                |
                               v                                |
+----------------------------------------------+                |
| [5] 快照恢复                                |                |
| Lucid迭代脏列表 -> memcpy快照               |                |
| 内容回到这些页面。                           |----------------+
| (无系统调用，全用户空间。)                   |
+----------------------------------------------+

用于比较求解的Redqueen

我还通过检测Bochs中的比较指令实现了Redqueen。当我们在模糊测试实验中启用比较覆盖并尝试确定它对特定目标有多大帮助时，我们将在下面更详细地介绍Redqueen。

测试工具开发

有了这些，我们需要一些东西来模糊测试！为此，我想做一些非常广泛和浅层的事情，所以我专注于研究可通过Netlink访问的Linux内核子系统。Netlink是一种网络/通信协议，允许用户空间通过套接字与内核通信，而不是像驱动程序或系统调用那样。过去5年中公开利用的许多漏洞都出现在具有Netlink管道的子系统中，例如：netfilter、数据包调度程序等。因为这些子系统设计为只接收Netlink缓冲区数据的字节，我认为这是开始模糊测试的好选择。

由于我们想要模糊测试多个子系统（广泛、浅层），我们首先必须弄清楚Netlink通信通常如何工作。想要通过Netlink与内核通信的用户空间程序或工具的典型工作流程是打开特定类型Netlink协议的Netlink套接字，例如测试工具中使用的以下内容：NETLINK_ROUTE、NETLINK_XFRM、NETLINK_NETFILTER和NETLINK_CRYPTO。例如：

1

socket(AF_NETLINK, SOCK_RAW, NETLINK_NETFILTER)

当用户空间程序将数据发送到具有关联协议的Netlink套接字时，我们最终会进入netlink_sendmsg。此函数的工作基本上是创建一个适当初始化的struct sk_buff，包装用户通过sendmsg系统调用发送的数据。然后，此套接字缓冲区被分派到适当的处理程序（在示例中，NETFILTER的处理程序将是nfnetlink_rcv）。

所以我想做的是在测试工具中跳过任何用户空间到内核的上下文切换，直接将我们的模糊测试输入注入内核空间，以分派到适当的处理程序。我最终将模糊测试输入结构化为一系列我称之为"消息"的内容，每个"消息"都是我们正在模糊测试的随机协议的自己的Netlink消息。我任意决定模糊测试输入最多为16条消息，因此我们可以每输入随机发送最多16条消息。在模糊测试工具中，我们使用这些数据结构创建模糊测试输入：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

// 输入结构
struct lf_input {
	u32 total_len;
	u32 num_msgs;
	u8 data[];
};

// 消息结构
struct lf_msg {
	u32 protocol;
	u32 msg_len;
	u8 data[];
};

因此，整个输入结构由struct lf_input描述，它告诉我们它包含的消息的总长度和消息数量，后跟所有消息堆叠在一起。单个消息由struct lf_msg描述，其中包含一个协议成员，对应于我们之前列出的NETLINK协议之一（NETLINK_ROUTE、NETLINK_XFRM、NETLINK_NETFILTER和NETLINK_CRYPTO），然后是消息的长度msg_len和之后的消息数据：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

============================= LUCID输入结构 =============================
lf_input {
  total_len: 4字节
  num_msgs:  4字节
  ────────────────────
  lf_msg {
    protocol: 4字节  (ROUTE=0, XFRM=1, NETFILTER=2, CRYPTO=3)
    msg_len:  4字节
    data:     变量 (netlink消息字节)
  },
  lf_msg {
    protocol: 4字节  (ROUTE=0, XFRM=1, NETFILTER=2, CRYPTO=3)
    msg_len:  4字节
    data:     变量 (netlink消息字节)
  },
  ... (最多16条消息)
}
=================================================================================

为了测试和开发目的，我利用快照模糊测试的灵活性/能力，在Linux内核中添加了一个新的系统调用，如下所示：

 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

SYSCALL_DEFINE2(lucid_fuzz, const void __user *, data, size_t, len)
{
    printk("Inside lucid fuzz!\n");
	int ret = 0;

	// 初始化模糊测试所需的一切
	ret = lf_init(data, len);
	if (ret)
		goto done;

    printk("Initialization done\n");

	// 处理模糊测试输入
	if (lf_handle_input()) {
		ret = -EINVAL;
		goto done;
	}

	// 清理资源，模糊测试时不需要，但测试时很好
	lf_cleanup();

done:
    printk("Inside done, returning %d!\n", ret);
	return ret;
}

这将接受用户提供的数据缓冲区并将其发送到lf_init，这是我编写的一个函数，它预分配我们想要使用的套接字缓冲区（记住我们知道最多可以发送16条消息）并找到所有Netlink子系统接收处理程序，例如：nfnetlink_rcv、rtnetlink_rcv、crypto_netlink_rcv和xfrm_netlink_rcv。当不在Lucid下进行模糊测试时，系统调用会将用户提供的数据复制到全局"fuzzcase"变量中，然后lf_handle_input将负责将该fuzzcase包装到适当的预分配套接字缓冲区中并将其发送到适当的处理程序。

以下是lf_handle_input的样子，这是魔法发生的地方。请记住，fc变量是全局的，代表"fuzzcase"，这是Lucid注入模糊测试输入的地方：

 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

// 主要模糊测试用例处理逻辑
int lf_handle_input(void) {
	int i = 0;
	struct lf_input *curr = NULL;
	struct lf_msg *msg = NULL;
	u32 remaining = 0;
	u32 offset = 0;
	struct sk_buff *fuzz_skb = NULL;

	printk("Inside lf_handle_input\n");

	/** LUCID在此处获取快照 **/
	asm volatile("xchgw %dx, %dx");

	// 确保我们有足够的大小来创建`lf_input`结构
	if (fc.input_len < sizeof(struct lf_input))
		return 1;

	// 获取`lf_input`并进行健全性检查
	curr = (struct lf_input *)fc.input;
	if (curr->total_len != fc.input_len || curr->total_len > LF_MAX_INPUT_SIZE)
		return 1;

	if (curr->num_msgs > LF_MAX_MSGS)
		return 1;

	// 要消耗的剩余字节
	remaining = curr->total_len;

	// 由于我们创建了一个结构，我们已经消耗了`lf_input`头，
	// 我们可以将这些字节计为已消耗并更新剩余
	remaining -= LF_INPUT_HDR_SIZE;

	// 更新偏移量以指向第一条消息
	offset = LF_INPUT_HDR_SIZE;

	// 解析和处理消息
	for (i = 0; i < curr->num_msgs; i++) {
		// 确保我们有足够的大小来创建`lf_msg`结构
		if (remaining < LF_MSG_HDR_SIZE)
			return 1;

		// 创建`lf_msg`结构
		msg = (struct lf_msg *)(fc.input + offset);
		if (msg->msg_len > LF_MAX_MSG_SIZE || msg->protocol >= LF_NUM_PROTOCOLS)
			return 1;

		// 我们现在已经消耗了消息头字节
		remaining -= LF_MSG_HDR_SIZE;

		// 确保我们有足够的数据剩余来填充此消息
		if (remaining < msg->msg_len)
			return 1;

		// 创建要发送到netlink_rcv函数的模糊测试skb
		fuzz_skb = create_fuzz_skb(msg, i);
		if (!fuzz_skb)
			return 1;
		
		// 将skb分派到适当的处理程序
		dispatch_skb(msg, fuzz_skb);

		// 更新偏移量
		offset += (LF_MSG_HDR_SIZE + msg->msg_len);

		// 更新剩余
		remaining -= msg->msg_len;
	}

	// 检查是否有剩余，如果有，说明有问题
	if (remaining)
		return 1;

	/** LUCID在此处恢复快照 **/
	asm volatile("xchgw %bx, %bx");

	// 成功
	return 0;
}

我们遍历消息数组，解析它们，并将它们发送到适当的子系统。我还使这个测试工具非常严格，以便如果出现任何问题，即使在解析后还有剩余字节，我们也会失败。这将导致lf_input提前返回，不会到达快照恢复NOP指令。这将导致模糊测试用例"逃逸"模糊测试工具，并最终导致超时。在Lucid中，我们基于模拟指令的数量进行超时处理。因此，如果我们有某些变异器/生成器/测试工具错误，模糊测试用例会超时，这将立即显而易见。

在开发的这一部分，我真正专注于优化测试工具。我想跳过在初始netlink_sendmsg函数之后发生的所有Netlink健全性检查和管道，认为这将大幅加速模糊器。我非常小心地保留了与跳过代码的语义等价性。然而，最终，我犯了错误，你可能能够发现。例如，在正常的netlink_sendmsg调用期间，它创建的套接字缓冲区没有初始化所有相同的字段，并且它不使用内核套接字。所以实际上，在我最长的模糊测试会话中，我有一个误报的NULL指针解引用崩溃，如果我保留了100%的语义等价性，这个崩溃就不会存在。我认为在博客中，我将更多地转向侵入性较小的测试工具，并接受性能损失。当我们的模糊测试用例开始到达更深的代码路径时，很明显模糊器非常慢，测试工具中的积极优化实际上不会产生太大影响，所以我将跳过这一点。

应该注意的是，这不是发现错误的好方法。我们只是试图评估Lucid如何模糊测试一些真实代码。每输入向各种子系统发送随机消息，这些子系统之间几乎没有交互，并且不能以任何有意义的方式相互访问，这不是到达深层代码和发现复杂错误的策略。以这种方式进行模糊测试更可能揭示简单的浅层解析级别错误，而在2025年，这可能不会产生太多结果。

阶段1模糊测试：简单字节变异器

首先，让我们向这些Netlink处理程序抛出一些随机字节。为此，我改变了Lucid看待变异器代码的方式。现在，有一个顶级的Mutators crate，它定义了几个通用特征和特性，每个自定义变异器实现都必须具有这些。例如，像rand函数这样的东西。但是在实现了核心模糊器依赖的通用内容之后，你可以自由地拥有任何你喜欢的自定义变异器。现在你可以实现任何你想要的变异器，并将其放在源代码目录中的mutators/下。这允许一些相当好的灵活性。我添加了一个命令行标志，用于按名称指定变异器，然后它们通过mod.rs中的工厂类型函数创建：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

/// 通过名称创建变异器的简单工厂（根据需要扩展）。
pub fn create_mutator(
    name: &str,
    seed: Option<usize>,
    max_size: usize,
) -> Result<Box<dyn Mutator>, LucidErr> {
    match name {
        "toy" => Ok(Box::new(ToyMutator::new(seed, max_size))),
        "netlink" => Ok(Box::new(NetlinkMutator::new(seed, max_size))),
        _ => Err(LucidErr::from(&format!("Unrecognized mutator '{}'", name))),
    }
}

我首先实现了一些基本的变异策略：

• ByteInsert：随机将任意值的字节插入消息缓冲区
• ByteOverwrite：随机用任意值的字节覆盖消息中的一个字节
• ByteDelete：随机从消息缓冲区中删除一个字节
• BitFlip：随机翻转消息缓冲区中的一个位
• ProtocolChange：随机更改消息的协议（例如，从NETLINK_ROUTE切换到NETLINK_NETFILTER）

除了这些策略，变异器通常"堆叠"这些策略每输入。我定义了一个MAX_STACK为7（任意），因此变异器可能选择每迭代随机变异输入，最多使用7种这些策略。

这些变异策略实际上出乎意料地实现了相当多的代码覆盖率。最初，迭代非常短，因为我们发送的大多数Netlink消息都是无意义的。Netlink消息结构如下所示：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

/**
 * struct nlmsghdr - Netlink消息的固定格式元数据头
 * @nlmsg_len:   包括头在内的消息长度
 * @nlmsg_type:  消息内容类型
 * @nlmsg_flags: 附加标志
 * @nlmsg_seq:   序列号
 * @nlmsg_pid:   发送进程端口ID
 */
struct nlmsghdr {
	__u32		nlmsg_len;
	__u16		nlmsg_type;
	__u16		nlmsg_flags;
	__u32		nlmsg_seq;
	__u32		nlmsg_pid;
};

由于我们发送随机字节，我们很少有一个nlmsg_len对我们的随机消息字节数组有意义。因此，模糊器需要一段时间才能生成正确类型的输入来解决早期消息解析，以实际到达该健全性检查后面的代码。我们必须生成一个具有正确长度的输入。

在短时间内，我使用这个简单的变异器和我们前面提到的测试工具实现了以下结果：

1
2
3
4
5
6
7

[lucid stats (start time: 2025-09-19 08:57:11)]
globals: uptime: 0d 22h 26m 28s | fuzzers: 8 | crashes: 0 | timeouts: 0
perf: iters: 88.266M | iters/s: 206.81 | iters/s/f: 25.85
cpu: target: 92.7% | reset: 6.8% | mutator: 0.0% | coverage: 0.5% | redqueen: 0.0% | misc: 0.0%
coverage: edges: 16917 | last find: 0h 2m 6s | map: 25.81%
snapshot: dirty pages: 3841 | dirty / total: 0.00068% | reset memcpys: 438
corpus: inputs: 31000 | corpus size (MB): 318.303 | max input: 0x8088

你可以看到，我们在开发VM上使用这个变异器迭代模糊测试了测试工具几乎一整天。它出乎意料地捕获了相当多的边，大约17k。我们还可以看到，我们能够处理相当多的迭代，因为在那段时间内我们几乎达到了1亿次迭代。当最后一个统计横幅打印时，全局所有8个模糊器我们大约每秒200次迭代。相对于后续版本的变异器，这是相当多的吞吐量。这是因为，正如我们讨论的，大多数输入根本没有通过初始解析，因此它们提前返回；换句话说，我们的变异器创建了大量没有做任何有价值事情的垃圾。因此，虽然吞吐量在纸面上看起来不错，但实际上对我们来说并不好。我们还可以通过相对较高的重置CPU时间来判断这一点，意味着我们花费了近7%的时间执行快照重置。

在进一步比较不同迭代的模糊器结果之前，应该注意这些结果可能没有太大意义。我们可能可以推断出大的结论，比如：发送具有合理nlmsg_len的输入更好，但当我们没有进行10倍改进时，结果可能太随机，无法收集太多其他信息。所以请记住，我们在这里没有进行适当的实验。我对模糊器进行更改，运行一天左右，检查结果，比较，重复。由于我们的吞吐量如此低（Lucid非常慢），并且我们的模糊测试时间有限，我们无法产生高质量的统计数据。

还应该注意的是，当我发推文关于使用这个变异器进行模糊测试时，我提到模糊器确实发现了一个边缘情况OOB读取错误，但它是人为的，因为我们的测试工具跳过的上游健全性检查会阻止它发生。所以我不算它是Lucid的第一个0day。

阶段2模糊测试：更多变异策略

下一步是稍微充实变异器。对于下一步，我添加了几个新的变异方法，这些方法将使我们能够提高效率（不发送太多垃圾）并创建以前几乎不可能创建的输入。

我添加了以下变异策略：

• UniProtocol：使输入中的每条消息都针对相同的协议
• DuplicateMessage：复制输入中的一条消息
• ShuffleMessages：随机打乱输入中消息的顺序
• SpliceMessage：从另一个输入中窃取一条消息并将其拼接到当前输入中
• PatchHeaderLen：确定正确的nlmsghdr->nlmsg_len值应该是什么并修补它
• PatchHeaderType：有点智能地，为我们目标子系统放置消息类型值代替nlmsghdr->nlmsg_type
• PatchHeaderFlags：随机创建有点逻辑合理的nlmsghdr->nlmsg_flags值

这一步对我们帮助很大，基本上将我们的效率提高了2倍：

1
2
3
4
5
6
7

[lucid stats (start time: 2025-09-20 16:24:38)]
globals: uptime: 0d 14h 8m 35s | fuzzers: 8 | crashes: 0 | timeouts: 0
perf: iters: 2.821M | iters/s: 31.18 | iters/s/f: 3.90
cpu: target: 97.4% | reset: 2.4% | mutator: 0.0% | coverage: 0.1% | redqueen: 0.0% | misc: 0.0%
coverage: edges: 17740 | last find: 1h 4m 52s | map: 27.07%
snapshot: dirty pages: 7455 | dirty / total: 0.00132% | reset memcpys: 648
corpus: inputs: 313510 | corpus size (MB): 3779.988 | max input: 0x8088

如你所见，我们能够在大约一半的挂钟时间内捕获更多的边。在迭代方面，我们能够在少40倍的迭代中捕获更多的边。所以这是一个相当巨大的效率提升。我认为这大部分来自于将合理的nlmsghdr->nlmsg_len值保存到语料库中，以及允许我们创建更复杂输入的变异策略。

以前，如果我们能够随机生成一条实现相当多代码覆盖率的消息，我们有点受限，因为我们必须非常幸运才能让同一输入中的另一条消息通过简单的字节翻转随机变得同样成功。相反，现在我们有了新的策略，如消息复制、消息拼接和统一协议，以便每条消息都有机会发送到相同的子系统等，并且我们可以实现更深的代码覆盖率，因为我们的消息现在可以建立在同一输入中先前消息的基础上。

因为我们的输入现在通过初始解析器检查的机会如此戏剧性地更高，我们的吞吐量已暴跌到大约每秒2-4次迭代/模糊器。我不得不承认，这比我对模糊器的期望低得多。我知道Bochs模拟比本机执行有相当大的减速，大约100倍，但我还没有真正看到它，因为到目前为止我们只模糊测试了玩具目标以进行模糊器开发。这就是为什么人们说不要过早优化，我们不知道我们的Bochs模拟瓶颈如此明显，我们本可以花费大量时间微优化核心模糊器代码，但它根本不会产生任何影响。

阶段3：使用Redqueen添加比较覆盖

到目前为止，我们还没有使用Lucid内置的Redqueen工具。对于那些不知道的人，Redqueen是波鸿鲁尔大学天才们的一篇模糊测试论文的名称，解决了模糊测试中的比较求解问题。

通常在模糊测试中，目标希望将从你的输入派生的值与它知道应该/可以存在的值进行比较。例如，以下可能在语义上存在于模糊测试目标中：

1
2
3

if (*(uint32_t *)(&fuzzing_input[0x1337]) == 0xdeadbeef) {
  buggy_function();
}

在这个例子中，目标正在检查我们的输入是否存在魔术值，在这种情况下是0xdeadbeef。很多时候，这些简单的魔术字节值检查代表了在没有人工干预的自动化模糊测试中的巨大障碍。使用我们的简单字节翻转变异，我们必须连续针对4个连续字节，并随机使它们都具有正确的值。这在很多情况下基本上是不可能的。

Redqueen的贡献是，这些类型的检查通常归结为x86架构上的cmp指令，其中两个"操作数值"相互比较，这些是左操作数和右操作数。现在从确定哪一侧来自输入，哪一侧来自程序的角度来看，通常不可能做出这种区分。所以Redqueen做的是在输入中搜索两个操作数，如果它找到一个操作数，它在输入中用另一个操作数值替换它，希望我们现在可以通过检查。

这通常在模糊测试期间非常昂贵，因此为了最小化开销，Redqueen只对最近找到新代码覆盖率的输入执行这种类型的变异，这样开销主要是一次性成本，并且随着活动的进行和新的覆盖率变得越来越罕见，开销渐近为零。

这不是对该技术的公平概述，但这传达了要点。如果你感兴趣，请阅读链接的论文，它可能是我迄今为止最喜欢的模糊测试论文。

我们可以在我们的模糊器中实现这一点，因为我们可以免费访问Bochs中所有大小的所有比较指令。所以现在，当我找到一个新的输入时，我在Lucid和Bochs之间的共享执行上下文数据结构中切换一些东西，称为"CPU模式"，这告诉Bochs我们正在做什么类型的模拟。一旦我们找到一个新的输入，我重放输入，但将CPU模式设置为Cmplog。这将导致Bochs报告它在比较指令中看到的所有操作数值、指令指针值和操作数的大小回Lucid。Lucid现在可以创建一个值数据库，并尝试Redqueen策略以获得更多覆盖率。

然而，我们遇到了一个巨大的问题，查看启用Redqueen运行的统计数据：

1
2
3
4
5
6
7

[lucid stats (start time: 2025-09-21 20:13:29)]
globals: uptime: 0d 14h 18m 23s | fuzzers: 8 | crashes: 0 | timeouts: 0
perf: iters: 369.79K | iters/s: 0.10 | iters/s/f: 0.01
cpu: target: 9.1% | reset: 0.0% | mutator: 0.0% | coverage: 0.0% | redqueen: 90.9% | misc: 0.0%
coverage: edges: 15829 | last find: 0h 17m 16s | map: 24.15%
snapshot: dirty pages: 7224 | dirty / total: 0.00128% | reset memcpys: 532
corpus: inputs: 32272 | corpus size (MB): 430.671 | max input: 0x8088

我们基本上在整个14小时的模糊测试运行中只进行了Redqueen分析，其中我们大约每秒获得7次全局迭代。这意味着Redqueen已成为一个禁止性的瓶颈。我们可以通过我们发现的边的数量判断它没有太大帮助，至少最初没有。可以预期这种一般模式：

• 在活动早期，我们经常找到新的覆盖率
• 输入经常被发送到Redqueen

这并不奇怪。然而，我发现Redqueen实现本身存在几个问题。

问题1

Redqueen论文还指出，有时输入数据在比较之前被转换或编码。例如，也许输入数据最初是一个u64值，但在比较之前被转换为i32。如果是这种情况，我们永远不会在输入中找到i32的比较操作数值，因此我们需要预计算一些常见编码，而是搜索它们。如果我们找到了比较操作数->编码值，我们会用另一个操作数值的相同编码替换它。这很有意义。然而，我的实现中有一个逻辑错误，试图通过为找到的操作数值生成所有可能的编码来求解比较，而不是单个匹配编码。这将尝试的输入补丁数量增加了15-20倍。

Redqueen论文还发现，替换操作数值但对值进行-1或+1的算术运算有助于通过小于/大于比较。请记住，我们只挂钩可能设置CPU标志的比较操作，我们不知道程序之后如何处理这些信息，所以这也有助于我们绕过这些检查。所以在我错误的实现中，这将3倍我们尝试的补丁数量，这已经是15-20倍太多，所以现在大约是45-60倍太多的补丁要测试。

所以这里有一个我做什么的具体例子：

• 我收到一个操作数值对0x1337和0xdead的报告。这些是2字节值。
• 我预计算了两对的所有可能编码（这部分是正确的）
• 如果我找到了0x1337的编码变体，比如零扩展到u32，所以在输入中是0x00001337，我应该做的是对其伙伴值应用相同的编码方案并创建0x0000dead。然后我会用0x0000dead替换输入中的0x00001337。
• 相反，我用0xdead的每个可能类似大小的编码替换0x00001337

问题2

但等等，它变得更糟！我也没有基于cmp指令的RIP值对操作数进行去重。现在通常，这可以，因为它允许你潜在地通过更多动态比较，其中也许两个操作数值都基于你的输入不断变化，比如校验和。然而，由于我们的吞吐量问题，并且只想在这里做最低限度的工作并击败经典的魔术数字比较，我们可以通过忽略从我们已经收集的RIP值收集的操作数来显著减少尝试的输入补丁数量。如果我们需要击败校验和类型的比较，我们将依赖人工干预。

问题3

为了盖过一切，我在尝试所有之前创建了所有修补的输入。因此，我会预计算修补的输入并将它们塞入输入队列，然后Lucid会优先于正常变异处理它们。这导致我的模糊器被内核SIGKILL，因为它们开始在一夜之间在内存中保存太多输入。这实际上结束了这个实验阶段。所以这个模糊测试阶段是一个彻底的灾难，我们在下一次迭代中进行了大量改进。

问题4

次要说明：Redqueen论文还采用了一种它称之为"着色"的技术，其中输入将被随机字节"着色"，直到着色改变输入的执行路径。因此，它会用随机字节覆盖输入数据，并检查这是否影响执行路径。它从最大可能的随机化量开始，然后使用类似二进制搜索的东西，继续缩小将被着色的输入部分，直到其执行跟踪与原始匹配。这样做的目的是使在输入中找到操作数值更容易。例如，输入不是充满0x0值，而是现在包含随机数据，当你捕获比较操作数值时，捕获中的随机数据更容易在输入中发现，并且你不会冒重复候选插入的风险。这实际上是天才。Lucid也有这个功能，但我发现我花了数十秒为大型输入着色。这是因为我们太慢了。我认为果汁不值得挤压，并使其现在为了使用着色，你必须传递一个命令行标志来选择加入它。

阶段4：修复Redqueen

除了修复前面提到的逻辑错误，我还向实现添加了一些新逻辑。首先，我开始通过RIP值对收集的操作数值进行去重。因此，我们不再对相同的RIP比较操作数进行多次Redqueen分析。

此外，我停止收集至少不是4字节大小的值的比较操作数。我认为大多数变异器应该能够通过纯粹的运气随机通过1和2字节比较。

我还将你可以放入模糊器测试队列的Redqueen输入数量限制在500。在我的测试中，通过固定的编码搜索、RIP去重和删除<32字节比较，我们甚至从未真正接近测试队列中的500个输入。以前，在损坏的实现中，一些模糊器携带了多达100万个输入进行测试！

修复错误并向Redqueen代码添加这两个新东西极大地帮助了我们，我们实现了以下模糊测试运行：

1
2
3
4
5
6
7

[lucid stats (start time: 2025-09-22 11:47:27)]
globals: uptime: 0d 5h 49m 26s | fuzzers: 8 | crashes: 0 | timeouts: 0
perf: iters: 738.01K | iters/s: 34.30 | iters/s/f: 4.29
cpu: target: 98.1% | reset: 1.8% | mutator: 0.0% | coverage: 0.1% | redqueen: 0.0% | misc: 0.0%
coverage: edges: 16100 | last find: 0h 1m 10s | map: 24.57%
snapshot: dirty pages: 7290 | dirty / total: 0.00129% | reset memcpys: 557
corpus: inputs: 70366 | corpus size (MB): 877.591 | max input: 0x8088

如你所见，我们在挂钟时间的一半内将吞吐量翻了一番。我们也没有使用那么多内存以至于模糊器被杀死，所以这很好。现在Redqueen已修复，我们可以继续前进。

Redqueen成功示例

一旦我们摆脱了前30分钟左右的模糊测试，Redqueen被证明在找到新边方面非常有帮助。这是一个我必须分享的 awesome 例子：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

[lucid stats (start time: 2025-09-24 15:23:35)]
globals: uptime: 0d 0h 56m 54s | fuzzers: 8 | crashes: 0 | timeouts: 0
perf: iters: 96.08K | iters/s: 18.05 | iters/s/f: 2.26
cpu: target: 97.7% | reset: 1.4% | mutator: 0.0% | coverage: 0.0% | redqueen: 0.7% | misc: 0.0%
coverage: edges: 19920 | last find: 0h 0m 56s | map: 30.40%
snapshot: dirty pages: 8122 | dirty / total: 0.00144% | reset memcpys: 982
corpus: inputs: 2581 | corpus size (MB): 8.827 | max input: 0x10088
fuzzer-2: Fuzzing increased edge count 19475 -> 19476 (+1)
fuzzer-1: Fuzzing increased edge count 19505 -> 19507 (+2)
fuzzer-7: Fuzzing increased edge count 19194 -> 19196 (+2)
fuzzer-4: Fuzzing increased edge count 19365 -> 19370 (+5)
fuzzer-4: Redqueen increased edge count 19370 -> 19721 (+351)
fuzzer-4: Redqueen increased edge count 19721 -> 19784 (+63)
fuzzer-4: Redqueen increased edge count 19784 -> 20925 (+1141)

fuzzer-4开始时远远落后于记录边数（19920），只发现了19365条边。它使用正常的模糊测试变异策略并将其边数增加到19370。然后，那个找到新边的输入被发送到Redqueen进行处理，Redqueen显著增加了模糊器的边发现进度。它迅速发现了1555条新边，这比它刚刚通过模糊测试达到的边数增加了8%。

阶段5：添加种子、变异器调整、杂项

种子

在这个阶段，重点主要是创建种子输入，这些输入将以大量覆盖率开始模糊测试活动。到目前为止，我们为此模糊测试目标/测试工具发现的边最多约为17.5k，这是我们在改进的变异器中看到的，但没有比较覆盖率，运行了大约14小时。现在，这并不意味着比较覆盖率阻碍边发现，它只是意味着早期它在找到新边方面不如正常模糊测试策略有效。通过种子，我希望看到发现的边数显著增加，因为我们将向变异器提供一些它需要生成的复杂输入。

为了创建种子输入，我实际上只是创建了一个LD_PRELOAD共享对象，它劫持了sendmsg libc调用，该调用在几个通常打包在Ubuntu中的命令行实用程序中发现，以与这些子系统交互。我说的是用于设置qdiscs或NETLINK_ROUTE的网络调度程序的tc，或用于与NETLINK_NETFILTER的nf_tables交互的nft等。我只是挂钩sendmsg libc函数，并让它将消息内容以十六进制转储到终端。这是一个例子：

1
2

root@luciddev:/home/h0mbre/netlink_fuzzing# LD_PRELOAD=./hexdump_netlink.so tc qdisc add dev dummy0 root pfifo_fast
echo "3400000024000506fa2cd46800000000000000000700000000000000ffffffff000000000f000100706669666f5f666173740000"

然后我只是将该echo字符串粘贴到终端中，将十六进制写入文件，然后使用Python将这些字节包装在我们的模糊测试输入数据结构中：

1
2
3
4
5
6

#!/usr/bin/env python3
import sys

# lf_protocols = {0: ROUTE, 1: XFRM, 2: NETFILTER, 3: CRYPTO}

def build_seed(hex_string: str, protocol: int, out_file: str):