这篇题为“Jigsaw: Efficient and Scalable Path Constraints Fuzzing”的文档，属于类型a：报告一项原创性研究的学术论文。
Jigsaw: 高效的路径约束模糊测试系统 ——一项提升自动化测试生成速度的新方法
本研究的作者为Ju Chen， Jinghan Wang， Chengyu Song和Heng Yin，他们均来自加州大学河滨分校计算机科学与工程系。该研究以《Jigsaw: Efficient and Scalable Path Constraints Fuzzing》为题，发表于2022年的IEEE安全与隐私研讨会（2022 IEEE Symposium on Security and Privacy, SP）。这篇论文提出了一种全新的设计，旨在通过即时编译（Just-in-Time, JIT）技术将路径约束转换为本地函数来评估输入，从而大幅提高覆盖率引导测试（Coverage-Guided Testing）的搜索吞吐量（search throughput）和分支翻转率（branch flipping rate）。
研究的核心领域是软件安全与漏洞发现，具体聚焦于自动化测试生成技术，尤其是覆盖率引导模糊测试和符号执行。覆盖率引导测试（例如模糊测试Fuzzing）通过寻找能够覆盖程序新分支的输入来发现漏洞。它的效率主要受两个因素影响：搜索算法（search accuracy）的准确性以及单位时间内可以评估的输入数量（search throughput，搜索吞吐量）。传统模糊测试通过运行整个被测程序（Program Under Test, PUT）来评估新输入，开销巨大；而符号执行（Symbolic Execution）虽然更系统，但依赖于速度较慢的约束求解器（如SMT求解器）。近年来，虽然搜索算法不断改进，但提升搜索吞吐量的潜力尚未被充分挖掘。
本研究的目标正是将搜索吞吐量推向新的高度。其核心洞察是：符号执行器收集的路径约束是纯粹的（pure）、无分支的（straight-line）函数。因此，相比于运行整个程序，通过即时编译（JIT）将路径约束编译成本地函数来评估新输入，将带来巨大的速度优势：1. 函数执行速度远快于整个程序；2. 纯函数无副作用，无需昂贵的状态重置（如进程分叉）；3. 可通过内存而非文件系统传递输入，消除I/O瓶颈；4. 无依赖的纯函数易于多核并行化；5. 无分支代码利于处理器指令级并行和数据并行（如SIMD）。Jigsaw原型系统的目标，就是验证这一设计思想的有效性。
1. 获取路径约束 Jigsaw本身是一个约束求解器，它需要一个前端工具来收集路径约束。研究者实现了一个基于数据流检测器（Data-flow Sanitizer, DFSan）的协同执行（Concolic Execution）引擎，在LLVM IR级别收集路径约束。这些约束以抽象语法树（Abstract Syntax Tree, AST）的形式表示，并支持识别数据依赖的嵌套分支（Nested Branches），以确保解决方案不会导致控制流偏离目标路径。
2. 预处理与任务分解 收到求解请求（即一个分支的AST形式路径约束）后，Jigsaw首先进行预处理以适配其搜索算法。步骤包括：将逻辑或（lor）运算符转换为析取范式（DNF），以便并行求解每个子句；将连接逻辑与（land）的约束分解为独立的比较指令子任务，但会联合求解；去除逻辑非（lnot）运算符，并反转比较条件。随后，为了最大化函数复用，Jigsaw对AST进行规范化，将输入字节和常量都视为函数参数，并按先序遍历顺序映射到参数数组中。经过此步骤，像a > 10和b > 20这样的不同约束，其AST被归一化为相同的结构ugt(arg0, arg1)，从而可以共享同一个JIT编译的函数。
3. 代码生成与即时编译 对于每个分解出的比较指令子任务（如ugt），Jigsaw将其转换为一个能返回“距离”的损失函数，这借鉴了Angora等工作中梯度引导搜索的思想。转换规则已表格化，例如，将无符号大于比较ugt(a, b)转换为损失函数max(zext(b, 64) - zext(a, 64) + ε, 0)，其中ε是一个小正数。之后，通过遍历AST生成LLVM中间表示（IR），并使用LLVM的ORC JIT引擎在内存中即时编译为本地函数。值得注意的是，为了权衡编译开销，研究中决定在JIT编译时不启用优化，因为路径约束本身不复杂，且优化编译耗时可能抵消快速求解的收益。
4. 梯度引导搜索求解 Jigsaw采用一个简化的梯度引导搜索算法（源自Angora和Matryoshka）来寻找满足约束的输入。对于多个需要联合求解的子任务，它采用“优先满足性”策略：先尝试解决当前目标分支谓词；找到满足输入后，使用联合优化损失函数（如G(x) = Σ f_i(x) / N）来同时解决所有嵌套分支约束，并避免已满足的约束被破坏。算法通过向输入字节添加微小扰动（±1）来数值近似梯度。同时，为了避免除零异常，在JIT生成的函数中，除法指令前会插入除数为零的检查。
5. 关键性能优化：函数缓存与锁竞争规避 为了提高可扩展性，Jigsaw引入了两项关键优化。第一是函数缓存（Function Cache）。由于许多路径约束本质上是针对不同数据执行的相同检查，Jigsaw将规范化后的AST（不含叶节点）作为键，缓存已编译的JIT函数。为了加速查找，每个AST节点都计算了一个哈希值。这一设计显著提高了缓存命中率（实验中达到99.9%），极大减少了重复编译的开销。第二是避免锁竞争。为了在多线程下实现线性扩展，Jigsaw尽可能减少锁的使用：每个任务构建线程拥有独立的LLVM JIT引擎；使用无锁队列在线程间通信；函数缓存基于无锁哈希表实现；并使用TCMalloc等高性能内存分配器。
研究者通过一系列实验验证Jigsaw的性能，主要回答四个研究问题（RQ）。
RQ1 & RQ3: 搜索吞吐量与多核扩展性 在单线程下，Jigsaw在求解嵌套分支约束时，平均搜索吞吐量达到637.2k inputs/sec（几何平均数），最高可达4.6M inputs/sec；对于单分支约束（无依赖），吞吐量高达3.1M inputs/sec。与同样采用本地搜索的SMT求解器Bitwuzla（局部搜索模式）相比，Jigsaw的平均吞吐量高出20倍以上；而相比于直接在原程序上进行梯度搜索的Angora，Jigsaw的吞吐量提升了约373倍。更重要的是，Jigsaw在多核上展现出近乎线性的扩展能力。使用48个物理核心时，嵌套分支约束求解吞吐量提升至12.5M inputs/sec，单分支约束吞吐量达到74.7M inputs/sec。这证实了基于纯JIT函数评估的方法能有效消除并行瓶颈（如fork和文件系统）。
RQ2: 分支翻转率 在可比的时间预算设置下（使各求解器解决约94% Z3能在60秒内解决的约束），Jigsaw展示了极高的分支翻转效率。在求解嵌套分支约束时，Jigsaw单线程的平均分支翻转率为588.9 branches/sec，优于Z3（41.0 branches/sec）、Bitwuzla（61.0 branches/sec）和Yices2（204.4 branches/sec）。对于单分支约束，Jigsaw的优势更明显，平均翻转率达35.7k branches/sec，远超其他求解器（通常低于1k branches/sec）。这有力地证明，即使使用相对简单的梯度引导搜索启发式算法，只要拥有足够高的搜索吞吐量，也能在求解大量真实世界程序约束时击败采用复杂启发式的SMT求解器。
RQ4: 端到端覆盖率引导测试性能 为了评估Jigsaw在实际测试场景中的效果，研究者构建了一个以Jigsaw为约束求解器的混合模糊器（Hybrid Fuzzer），并与多种先进工具进行对比。 * 协同执行性能测试：在固定种子集上翻转所有符号分支的测试中，Jigsaw完成所有分支翻转所需的时间远少于Angora、SymCC、Fuzzolic以及使用Z3（10秒或50毫秒超时）的相同驱动框架。这显示了从约束收集到求解的端到端速度优势。 * 本地模糊测试：在多个真实程序（如readelf， objdump）上进行24小时覆盖测试，Jigsaw的覆盖率增长速度通常最快，并且最终覆盖度与或优于AFL++、Qsym、NEUZZ等工具。 * FuzzBench基准测试：在Google FuzzBench基准平台上，Jigsaw在13个模糊器中平均得分排名第一（与Z3版本并列），在多个基准程序上取得了领先的覆盖率。
局限性分析：实验结果也揭示了当前原型的限制。1. 求解能力：受限于梯度引导搜索启发式，Jigsaw无法判定约束不可满足（UNSAT），且在涉及除法（udiv/urem）、按位异或（xor）或非凸优化问题时可能失败。这导致其可解约束比例略低于Z3（嵌套分支94%，单分支99%）。2. 端到端测试：由于依赖编译时插桩，Jigsaw无法收集非插桩库和系统调用中的约束，可能错过一些分支；同时，现有的混合测试框架未能充分利用Jigsaw的高速求解能力，导致其经常处于空闲状态。
本研究提出并验证了一种通过JIT编译路径约束来极大提升自动化测试生成搜索吞吐量的新颖方法。其实验证明，这种方法能够实现比现有模糊测试高数个数量级的输入评估速度，并具备优秀的多核扩展性。由此带来的超高分支翻转率，使得一个简单的梯度引导搜索算法就能在求解现实程序约束时超越复杂的SMT求解器。将Jigsaw集成到混合模糊器中，也使其在端到端的覆盖率引导测试中表现出色，能够更快地达到更高的代码覆盖率。
研究的科学价值在于，它指出了一个被忽视的性能优化维度（搜索吞吐量），并提供了实现这一目标的创新技术路径（JIT化纯函数评估），为自动化软件测试和漏洞发现领域开辟了新的设计思路。其应用价值则直接体现在能更快速、更高效地进行软件安全测试，有助于在资源有限的情况下发现更多深层漏洞。研究者已开源Jigsaw原型（GitHub: r-fuzz/jigsaw）和收集的路径约束数据集，可供学术界和工业界进一步研究与使用。
论文还探讨了与SMT求解器的对比、未来工作方向以及相关工作的梳理。作者指出，Jigsaw在方法论层面为SMT求解器提供了一种快速评估具体模型的新途径，两者可以互补。未来的工作包括采用更快的JIT引擎（如QEMU TCG）、设计更智能的任务调度器、扩展对字符串和浮点数约束的支持，以及集成更强大的搜索启发式算法（如SMT求解器中的位爆破和重写规则），以克服当前梯度搜索的局限性。这些讨论为后续研究指明了有潜力的改进方向。