EcoFuzz: Adaptive Energy-Saving Greybox Fuzzing as a Variant of the Adversarial Multi-Armed Bandit

AFL花费过多能量测试高频路径，无法自适应调整能量分配，导致浪费很多能量。现有的基于Markov模型基于覆盖率的灰盒测试不够深刻。本文提出了Adversarial Multi-Armed Bandit变种(VAMAB)模型来对能量调度流程进行建模。首先通过使用生成发现新路径的测试用例奖励概率解释了AFL的调度算法的不足，刻画了种子集的三个阶段并开发了一种自适应调度算法和基于概率的搜索策略。这些方法基于AFL实现，在一个自适应能量保存灰盒测试EcoFuzz中。和其他6个AFL类型的工具对比，EcoFuzz可以获取214%路径覆盖率并减少32%测试用例生成，识别了GNU Binutils和其它软件的12个漏洞。扩展了EcoFuzz测试IoT设备，找到了SNMP组件中的一个新漏洞

Motivation

使用AFL fuzz现实程序时，主要的挑战是大多数测试用例会测试相同的少数路径，因此导致能量浪费在了高频路径上。尤其是在后续fuzz阶段，测试高频路径的种子无法帮助提升新路径。AFL的常量能量调度机制无法合理给种子分配能量，给高频路径的种子分配了太多能量，AFL的能量调度算法没有建立在一个科学的理论模型上。

Method

本文提出了一种VAMAB模型来对CGF(覆盖率导向的灰盒测试)建模，将每一个种子建模为一个VAMAB的bandit，解释了每个VAMAB模型的CFG中搜索和利用的权衡，并从概率的视角利用Markov链理解细节。和AFLFast相反，本文关于能量调度的模型视角源自博弈论，和Markov链相比可以更好的理解调度算法中的挑战。本文根据VAMAB模型还开发了一个基于平均花费自适应的能量调度算法和一个基于自转换的概率估计方法，在EcoFuzz实现。

Result

和AFL和AFLFast相比，EcoFuzz实现了自适应调度方法，可以减少能量浪费，最大化路径覆盖率，在有限性能下表现良好，例如通过QEMU fuzz IoT设备。和6个最新AFL类型的fuzzer相比有更好性能。

贡献