企业官网建设流程全解析

• 应用安全
• 测试
• 漏洞扫描

导读

覆盖率映射（coverage map）是 AFL++ 判断"新路径"的核心数据结构，其密度分布直接决定了模糊测试的有效性与性能。本文以 frida_mode/MapDensity.md 为主线，系统讲解 AFL++ 覆盖率映射的工作原理、边 ID 碰撞的产生根源，以及 QEMU/FRIDA 等二进制插桩模式如何通过"哈希 + 旋转"取代经典"移位 + 异或"算法，使映射分布更均匀，并在并行模糊测试中利用不同哈希种子分散碰撞。读完本文，你将掌握覆盖率映射的完整生命周期，并能对照 instrument.c 等源码理解每个设计决策背后的性能与有效性权衡。

覆盖率是如何工作的

AFL++ 的覆盖率机制可以概括为三个步骤：

1. 块 ID 分配：为代码中的每个基本块（basic block）分配一个唯一 ID；
2. 边 ID 计算：在程序执行过程中，每当控制流在块之间转移（通过调用、跳转等），就根据"源块 ID 与目标块 ID"计算出该边（edge）的 ID；
3. 执行计数：用一张以边 ID 为下标的一维字节数组，记录每条边被遍历的次数。

单次执行计数与累计计数

对于目标的每一次独立执行，AFL++ 维护一张一维字节数组，下标即边 ID，值即该边在本轮执行中被遍历的次数。

与此同时，还维护一张一维累计字节数组：每个字节同样对应一个边 ID，但值不再代表精确次数，而是代表"该边被遍历次数落在哪个区间桶（bucket）"：

1, 2, 3, 4-7, 8-15, 16-31, 32-127, 128+

这样设计的理论依据是：一条边从被遍历 23 次变成 24 次，通常并不代表发现了有趣的新行为；但一条边第一次被遍历，或遍历次数跨入了一个新的区间桶，则意味着程序出现了值得保留的新路径。

新种子的判定流程

每次运行结束后，将本轮每条边的遍历次数与累计映射中的值逐一比较：

• 若不同，则说明本轮输入触达了新的边或新的次数桶，输入被保留为新的种子（seed），同时累计映射被更新；
• 若完全相同，则说明该输入没有带来新的覆盖率信息，予以丢弃。

这套机制最早由 lcamtuf 在 AFL 的技术白皮书（AFL technical_details）中做了详细阐述，AFL++ 继承了其基本设计，但在二进制插桩模式上做了重要演进（详见下文"改进"一节）。

碰撞：地图大小与覆盖率分辨率的权衡

在黑盒模糊测试场景下，我们无法预知控制流会从哪个块流向哪个块，因此必须假设任意两个块之间都可能存在一条边。对于一个拥有n个基本块的目标，潜在的边数为n * n。

以1024个基本块为例：

1024 * 1024 = 1048576 个潜在边 ID

即需要一张包含约 100 万条目（约 1MB）的映射才能为所有边分配独立 ID。虽然 1MB 看似不多，但它会带来两个严重问题：

1. 处理开销：每次执行结束后，覆盖率处理步骤都需要遍历并比对整张映射，映射越大，处理的数据量越大；
2. 缓存压力：1MB 的映射很难完整放进处理器的 L2 缓存，而覆盖率更新恰恰是整条执行链上最热门的代码路径（hot code path），缓存未命中会带来非常高昂的性能代价。

因此，AFL++ 必须接受一个现实：并非所有边都能获得唯一 ID，碰撞不可避免。碰撞的直接后果是：如果模糊器通过一条此前未被发现的边发现了新路径，但这条边的 ID 恰好与另一条边冲突，那么这次发现可能被完全忽略。

这显然不理想，但反过来，如果映射过大，单位时间内能处理的潜在输入就会变少，反而会因此错过更多边的发现。所以地图大小必须在"碰撞率"与"处理吞吐量"之间仔细权衡——这正是本文件名为"Map density"（地图密度）的原因：映射中每条边 ID 槽位的命中密度分布，决定了这个权衡是否划算。

块与边的编号方式

自经典 AFL 以来，块与边的编号一直沿用白皮书中的 C 代码片段所展示的方式：

cur_location = (block_address >> 4) ^ (block_address << 8); shared_mem[cur_location ^ prev_location]++; prev_location = cur_location >> 1;

其工作流程为：

• 每个块的 ID 由其地址经过一次**移位（shift）与异或（XOR）**生成；
• 边的 ID 由源块 ID 与目标块 ID 计算得出：E = B ^ (B' >> 1)；
• 计算出的边 ID 还会被掩码（mask），确保其小于所用映射的大小。

这个看似精巧的算法，在"地图密度"上却存在两个先天弱点。

块 ID：熵分布不佳

块 ID 由地址直接变换而来，而程序地址的分布并非均匀的：

• 高位：为满足地址规范化（canonical form），高位的二进制可能是全0或全1，几乎没有熵；
• 中位：如果所有块都位于同一个二进制文件内，它们在内存中彼此相邻，中位部分对所有块几乎是相同的；
• 低位：在某些系统上，由于使用定长对齐指令（fixed length aligned instructions），低位也可能缺乏熵；
• 空洞：每个二进制文件中还包含.data、.bss等数据段，这些区域根本不含任何代码块。

综合来看，块 ID 虽然唯一，但分布很不均匀。

边 ID：白白丢弃一位熵

在由源块 ID 与目标块 ID 生成边 ID 时，会对源块 ID 执行一次右移操作。虽然白皮书中解释了这样变换的合理理由，但代价是丢掉了源块 ID 中的 1 位宝贵熵。

两个弱点叠加的结果是：部分边 ID 槽位"门庭若市"，映射的某些区域被大量边密集填充；而另一些区域则稀疏甚至完全空白。这种密度不均正是本文件的主题——地图密度——所描述的问题核心。

改进：哈希与旋转算法

经典算法选择移位 + 异或的一个重要原因是性能：所有操作都能极快地完成，而这个计算可能要对执行的每一个基本块进行，性能至关重要。

但 AFL++ 的二进制插桩模式（QEMU 与 FRIDA）设计已经演进：它们采用两阶段执行流程：

1. 每个块先被编译/插桩（compile/instrument）；
2. 之后才被执行（execute）。

编译好的块在目标每次执行到它们时都可以直接复用。

关键洞察在于：块的 ID 基于其地址生成，而地址在编译期就是已知的，因此每个块的 ID 只需生成一次，块 ID 生成不再需要追求极致性能。于是可以改用哈希算法来生成块 ID，从而让块 ID 在映射中分布得更加均匀。

而边 ID 只能在运行时确定——因为我们只有实际运行某个输入，才知道它会遍历哪些块。不过，既然块 ID 已经均匀分布，生成均匀分布的边 ID 就变得简单：唯一需要做的改动，是把右移（shift）换成循环右移（rotate），从而不再丢失源 ID 中的那一位熵。

改进后的新算法如下：

cur_location = hash(block_address) shared_mem[cur_location ^ prev_location]++; prev_location = rotate(cur_location, 1);

此外，经典设计中每次运行开始时cur_location总是被置为0；新设计中则改为将cur_location初始化为hash(0)。

源码实现印证

新算法在 FRIDA 模式的插桩代码中有完整的落地实现：

• 块 ID 哈希：instrument.c 中的instrument_get_offset_hash()调用hash64()（其原型声明于 include/hash.h，实际实现基于 XXH3 系列哈希，见 src/afl-performance.c），并将结果用(1 << map_size_pow2) - 1掩码到映射大小范围内；
• 边 ID 计算与计数：instrument.c 中的on_basic_block()回调按edge = current_pc ^ previous_pc计算边 ID，随后通过instrument_increment_map()对该边执行计数（值达到0xff时回绕为 1，防止溢出）；
• 旋转操作：prev_location的更新调用util_rotate(current_pc, 1, map_size_pow2)，其实现位于 frida_mode/src/util.c：将高位移到低位、低位移到高位，再掩码回映射大小，保证不丢失任何一位熵；
• hash(0) 初始化：instrument_init()中通过instrument_hash_zero = instrument_get_offset_hash(0)计算hash(0)（instrument.c），并在每次 fork 后由instrument_on_fork()将prev_location重置为该值（instrument.c）。

映射大小的选择

FRIDA 模式默认映射大小为 64KB（FRIDA_DEFAULT_MAP_SIZE (64UL << 10)，见 instrument.c），而插桩编译器（如 LLVM 模式）的默认映射由 include/config.h 定义：MAP_SIZE_POW2 16，即MAP_SIZE = 1 << 16 = 65536个槽位。运行时可通过AFL_MAP_SIZE环境变量覆盖。哈希掩码操作正是为了把块 ID 与边 ID 压缩进这个有限大小的映射中。

并行模糊测试：用不同种子打散碰撞

经典设计还有一个次优之处：无论并行运行多少个模糊器实例，每个实例都以完全相同的方式给块和边编号，因此所有实例遇到碰撞的边集合也完全相同。一旦某条边 ID 发生碰撞，所有实例会同时撞上同一堵"墙"，谁都无法发现那条被掩盖的新路径。

改进方案非常优雅：为每个实例的哈希函数使用不同的种子（seed）。这样，每个实例会给每个块分配不同的 ID，从而每条边也获得不同的边 ID：

• 某个实例中发生碰撞的一对边，在另一个实例中极大概率不会发生同样的碰撞；
• 由于并行模糊测试具有协作共享的特性，一个实例因碰撞而苦苦无法发现的路径，另一个实例很可能不受该碰撞影响、能够成功区分这条新路径，并将它共享给其他实例。

种子的产生与覆盖

种子生成的源码逻辑位于 instrument.c：

instrument_hash_seed = g_get_monotonic_time() ^ (((guint64)getpid()) << 32) ^ tid;

即种子由单调时钟、进程号（左移 32 位）与线程 ID异或生成。源码注释明确指出：种子本身不必是随机的，只需对每个实例不同即可。

同时，FRIDA 模式还提供了诊断/调试用的固定种子选项：

• 设置环境变量AFL_FRIDA_INST_SEED即可启用固定种子（instrument_use_fixed_seed = TRUE），其值通过AFL_FRIDA_INST_SEED读取（instrument.c）；
• 这在需要复现某个实例的碰撞行为、进行覆盖分析或调试时非常有用。

关于单边发现的现实考量

从理论上说，如果并行实例 A 只发现了一条新边，并将新路径共享给实例 B，而这条边恰好与 B 中的某条已有边碰撞，B 可能会将其判定为无关输入而丢弃。但在实践中，发现一条新边之后，通常会连带发现其下游的多条边；要让所有这些边在另一个实例中全部碰撞，概率微乎其微。因此，基于不同哈希种子的并行策略在实际运行中非常稳健。

总结

从经典 AFL 的(block_address >> 4) ^ (block_address << 8)到 FRIDA/QEMU 模式的hash(block_address)+rotate(cur_location, 1)，AFL++ 对覆盖率映射的改进始终围绕同一个目标：在保证执行热路径性能的前提下，让边 ID 在映射中分布得更均匀、让并行实例的碰撞彼此错开。块 ID 因编译期可确定而改用强哈希，边 ID 因运行时才能确定而用循环旋转保住全部熵位，hash(0)取代0作为运行起点——这四步改动共同显著改善了地图密度，也提升了二进制插桩模式下模糊测试的路径发现能力。对实现细节感兴趣的读者，可直接阅读 frida_mode/src/instrument/instrument.c 与 frida_mode/src/util.c 中的对应函数，并结合 frida_mode/README.md 了解 FRIDA 模式的整体使用方式。

• 应用安全
• 测试
• 漏洞扫描