JIGSAW: Efficient and Scalable Path Constraints Fuzzing
JIGSAW: Efficient and Scalable Path Constraints Fuzzing
复制标题
DOI：
10.1109/sp46214.2022.9833796
复制
发表时间：
2022-05
期刊：
影响因子：
--
通讯作者：
Ju Chen;Jinghan Wang;Chengyu Song;Hengda Yin
中科院分区：
文献类型：
--
作者：
Ju Chen;Jinghan Wang;Chengyu Song;Hengda Yin
覆盖率指导的测试已被证明是发现错误的一种有效方法。如果我们将覆盖率指导的测试建模为一个搜索问题(即找到可以覆盖更多分支的输入)，那么其效率主要取决于两个因素：(1)搜索算法的准确性和(2)每单位时间可以评估的输入的数量。因此，提高搜索吞吐量已被证明是提高覆盖引导测试性能的有效方法。在该工作中，我们提出了一种新的设计来提高搜索吞吐量：通过使用JIT编译的路径约束来评估新生成的输入。这种方法使我们能够显著提高单线程吞吐量以及扩展到多核。我们还开发了几种优化技术，以消除这一过程中的主要瓶颈。对我们的原型Jigsaw的评估表明，我们的方法可以获得比现有Fuzzer高三个数量级的搜索吞吐量，并且可以扩展到多个核。我们还发现，在如此高的吞吐量下，简单的梯度引导搜索启发式算法可以比使用更复杂的搜索启发式算法的SMT求解器更快地求解从大量真实程序中收集的路径约束。对端到端覆盖指导测试的评估还表明，我们的拼图动力混合绒毛器的性能优于最先进的测试工具。
Coverage-guided testing has shown to be an effective way to find bugs. If we model coverage-guided testing as a search problem (i.e., finding inputs that can cover more branches), then its efficiency mainly depends on two factors: (1) the accuracy of the searching algorithm and (2) the number of inputs that can be evaluated per unit time. Therefore, improving the search throughput has shown to be an effective way to improve the performance of coverage-guided testing.In this work, we present a novel design to improve the search throughput: by evaluating newly generated inputs with JIT-compiled path constraints. This approach allows us to significantly improve the single thread throughput as well as scaling to multiple cores. We also developed several optimization techniques to eliminate major bottlenecks during this process. Evaluation of our prototype JIGSAW shows that our approach can achieve three orders of magnitude higher search throughput than existing fuzzers and can scale to multiple cores. We also find that with such high throughput, a simple gradient-guided search heuristic can solve path constraints collected from a large set of real-world programs faster than SMT solvers with much more sophisticated search heuristics. Evaluation of end-to-end coverage-guided testing also shows that our JIGSAW-powered hybrid fuzzer can outperform state-of-the-art testing tools.