应用安全测试漏洞扫描【免费下载链接】AFLplusplusAFL is a state-of-the-art fuzzer, and #1 in benchmarks. It was originally based on AFL. Today it comes with qemu 5.1, collision-free coverage, enhanced laf-intel redqueen, AFLfast power schedules, MOpt mutators, unicorn_mode, and a lot more!项目地址https://gitcode.com/gh_mirrors/af/AFLplusplus点击查看免费下载导读覆盖率映射coverage map是 AFL 判断新路径的核心数据结构其密度分布直接决定了模糊测试的有效性与性能。本文以 frida_mode/MapDensity.md 为主线系统讲解 AFL 覆盖率映射的工作原理、边 ID 碰撞的产生根源以及 QEMU/FRIDA 等二进制插桩模式如何通过哈希 旋转取代经典移位 异或算法使映射分布更均匀并在并行模糊测试中利用不同哈希种子分散碰撞。读完本文你将掌握覆盖率映射的完整生命周期并能对照 instrument.c 等源码理解每个设计决策背后的性能与有效性权衡。覆盖率是如何工作的AFL 的覆盖率机制可以概括为三个步骤块 ID 分配为代码中的每个基本块basic block分配一个唯一 ID边 ID 计算在程序执行过程中每当控制流在块之间转移通过调用、跳转等就根据源块 ID 与目标块 ID计算出该边edge的 ID执行计数用一张以边 ID 为下标的一维字节数组记录每条边被遍历的次数。单次执行计数与累计计数对于目标的每一次独立执行AFL 维护一张一维字节数组下标即边 ID值即该边在本轮执行中被遍历的次数。与此同时还维护一张一维累计字节数组每个字节同样对应一个边 ID但值不再代表精确次数而是代表该边被遍历次数落在哪个区间桶bucket1, 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 看似不多但它会带来两个严重问题处理开销每次执行结束后覆盖率处理步骤都需要遍历并比对整张映射映射越大处理的数据量越大缓存压力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设计已经演进它们采用两阶段执行流程每个块先被编译/插桩compile/instrument之后才被执行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 模式默认映射大小为 64KBFRIDA_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.cinstrument_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 模式的整体使用方式。赞分享应用安全测试漏洞扫描【免费下载链接】AFLplusplusAFL is a state-of-the-art fuzzer, and #1 in benchmarks. It was originally based on AFL. Today it comes with qemu 5.1, collision-free coverage, enhanced laf-intel redqueen, AFLfast power schedules, MOpt mutators, unicorn_mode, and a lot more!项目地址https://gitcode.com/gh_mirrors/af/AFLplusplus点击查看免费下载相关推荐imagededup 哈希算法详解感知哈希、差异哈希、小波哈希深度解析imagededup 哈希算法详解感知哈希、差异哈希、小波哈希深度解析 在数字图像管理领域imagededup 项目提供了一套简单高效的图像去重解决方案。这计算机视觉图像处理人工智能终极指南Aya eBPF映射系统详解——从数组映射到哈希映射的实战教程终极指南Aya eBPF映射系统详解——从数组映射到哈希映射的实战教程 Aya是Rust编程语言的eBPF库专注于开发者体验和可操作性。本文将深入解析Aya系统编程Robin Hood哈希映射C高性能哈希表的终极突破指南Robin Hood哈希映射C高性能哈希表的终极突破指南 在C开发中哈希表是日常编程不可或缺的数据结构但标准库的 std::unordered_m开发工具上一篇终极指南如何用Photon光影包让Minecraft画面焕然一新下一篇终极免费解锁Microsoft 365完整功能Ohook激活方案完全指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考