基于DDPG强化学习算法的模糊测试技术研究

摘要：

传统模糊测试技术在对样本进行变异时存在较大的盲目性，严重影响其工作效率。现有基于强化学习改进传统模糊测试技术的研究均采用仅基于值函数的强化学习算法来指导样本变异的方向，难以解决模糊测试过程中具有高维状态空间和动作空间的问题。

基于上述背景，文章提出一种基于DDPG强化学习算法来改进传统模糊测试技术的方法。首先将传统模糊测试技术建模为马尔可夫决策过程，即将程序样本输入作为环境状态、将变异函数作为动作策略、将代码覆盖率作为反馈奖励。然后选择综合值函数和策略函数的DDPG强化学习算法来求解该过程，从中学习得到最优的动作选择策略，实现根据当前的输入样本数据智能地选择变异动作，降低样本变异的盲目性，使得变异后的样本能够获得最大的代码覆盖率奖励，减少无效样本的生成，从而提高传统模糊测试技术的效率。

文章设计并实现了基于强化学习的通用型模糊测试系统RLFUZZ，通过基于LAVA-M 数据集进行的实验测试表明，相较于传统模糊测试的随机变异和现有工作中基于DQN等值函数求解的强化学习算法指导样本变异的方法，基于DDPG强化学习算法指导样本变异在代码覆盖率和有效样本分布等方面均有明显提高，同时RLFUZZ在现实软件上进行测试并发现了新的漏洞。

背景：

现有的主流模糊测试工具在解决如何高效的对程序输入进行变异这一问题的过程中探索了不同的方法，但是均难以在实际操作环境中详尽地检查整个输入空间，也不能探索目标软件程序所有的执行路径。因此，当前前沿的模糊测试工具通常使用启发式的探索方法来确定模糊变异策略的优先级。这些启发式的方法可能纯粹是随机过程，或者试图最大化特定的目标反馈，例如程序崩溃次数、代码覆盖率、执行超时次数等。

目的：找出一种根据程序运行时反馈的代码覆盖率来指引样本变异的方向，并且快速智能地选择模糊测试变异策略的方法，从而提高有效样本的生成概率，这将有助于改善由于传统样本随机变异的盲目性带来的效率低下的问题。

基于机器学习的模糊测试技术：

(1)在种子文件生成环节，SmartSeed利用生成对抗网络(Generative AdversarialNetworks,GAN)从来自AFL找到的有效样本数据出发生成新的二进制样本，较AFL和其它选择策略触发更多的崩溃和执行路径。REINAM利用强化学习算法辅助生成程序输入语法，提高生成变异样本的质量。Luong 等人利用Q-Learning 算法对Android应用程序进行测试，即选择编排触发GUI事件的操作序列，实现较高的代码覆盖率并触发更多的应用错误。MTFUZZ基于编解码器网络得到高维离散样本输入空间的压缩编码表示，据此计算输入字节的重要性分布，并优先变异拥有top-k重要性的字节位置处的数据，有效提高了生成样本的覆盖率且实现可迁移的嵌入层网络。

（2）在测试样例生成环节, Montage基于长短期记忆网络(Long Short Term Memory,LSTM生成JavaScript 文件用于针对浏览器的模糊测试，它将JavaScript文件转化为抽象语法树(Abstract Syntax Tree，AST)并通过前序遍历得到子树序列，然后通过LSTM学习子树之间的位置和逻辑关系。

（3）在测试样例过滤环节，FuzzGuard基于卷积神经网络(Convolutional NeuralNetwork，CNN)预测变异样本的可达性(reachability)来过滤低质量样本，并与AFLGo整合来提高模糊测试的效率，实验中最高提速到达17.1倍。

（4）在变异策略选择环节，研究人员主要尝试引入强化学习的相关技术来提高模糊测试效率。Bottinger等人利用强化学习的深度Q网络(Deep Q Network，DQN)对目标程序pdftotext进行模糊测试，设计以字符串为状态，以自定义的6种变异方法为动作，以代码覆盖率和运行时间为奖励，相较于传统的随机变异动作选择策略明显提高了代码覆盖率并降低了运行时间。

文章主要工作与创新点：

以提高传统基于变异的模糊测试工作效率为目标，创新性地提出基于强化学习算法改进传统模糊测试技术效率的设计方案。

（1）将强化学习技术引入模糊测试技术的过程中，设计模糊测试的马尔可夫决策过程建模方法，使其抽象为强化学习算法可求解的问题。

（2）基于强化学习算法来指导模糊测试过程中样本变异策略的选择，采用基于值函数和策略函数的综合强化学习算法，即深度确定性策略梯度算法(Deep Deterministic PolicyGradient，DDPG)，来求解马尔可夫决策过程，在较好解决高维连续动作空间问题的同时保持着较高的执行和计算效率，减少传统模糊测试过程中样本变异的随机性和盲目性。

（3）开发完成基于强化学习的通用模糊测试框架RLFUZZ，在可用性、稳定性以及性能方面均有良好表现。