关键词:
动态符号执行
模糊测试
混合测试
分层强化学习
摘要:
软件测试作为保证功能交付,提前发现软件项目问题的主要手段日益受到学术界和产业界的重视,自动化软件测试是其中一个热门领域。自动化软件测试技术通过程序分析等方式,不断生成测试用例执行程序,目的主要是覆盖尽可能多的程序路径以及发现能够导致程序崩溃的漏洞。基于覆盖率引导的模糊测试与动态符号执行作为两大主流的自动化软件测试技术已被广泛研究并应用到学术界与工业界中,这两种技术有明显的特点:模糊测试通过对测试用例变异来生成新的测试用例,效率高但测试用例的可靠性一般。动态符号执行根据路径约束取反生成可靠的测试用例,但面临路径爆炸和约束求解器的限制,而且生成测试用例的代价较高。搜索策略的设计在一定程度上缓解了路径爆炸,但大多数搜索策略都由人工设计并且在测试过程中不可变。也有学者将动态符号执行与模糊测试相结合,称为混合测试,以突破它们各自的局限。但目前混合测试主要由两种方法轮替执行,缺乏灵活性。强化学习场景中智能体根据环境的反馈不断调整的策略,可用于动态符号执行搜索策略的设计。分层强化学习框架能够出色的解决控制转移问题,可用于混合测试算法的设计。在强化学习算法的启发下,本文提出了一种基于分层强化学习的混合测试算法LCCT(Learnable Cooperative Concolic Testing),主要工作内容如下:(1)将动态符号执行过程抽象为马尔可夫决策过程,定义动态符号执行器并使用强化学习算法学习条件取反策略。执行器状态为测试用例已覆盖分支组成的程序执行树,动作空间为执行树中所有可以取反的条件分支节点。选择取反节点时,执行器将路径序列的嵌入表达作为当前状态的部分表示,使用DDQN算法对路径上所有可取反的动作进行价值预测,最后根据改进的(?)-greedy策略选择取反节点生成当前时刻的测试用例。环境根据执行测试用例后的新增分支覆盖数和生成时间反馈奖励,执行器根据奖励优化状态动作价值预测函数。(2)为了突破动态符号执行的固有局限,引入模糊测试执行器作为动态符号执行器的补充,使用分层强化学习框架通过协调器控制两个执行器,算法命名为LCCT。LCCT由顶层协调器和底层执行器组成,协调器的状态为测试用例覆盖分支组成程序执行树的统计量,动作空间为模糊测试执行器以及动态符号执行器。协调器使用DQN算法进行价值预测并根据(?)-greedy策略选择执行器生成测试用例,最后根据测试用例的表现优化状态价值预测函数。LCCT通过引入模糊测试执行器避免动态符号执行器陷入局部最优并降低了路径爆炸影响。通过协调器让执行器之间灵活切换。同时还根据执行器各自的特点进行数据传输,提高了整体算法的效率。(3)将动态符号执行器以及LCCT算法与目前主流的动态符号执行策略Chameleon等在expat等一系列开源程序上进行实验测试。实验结果表明,动态符号执行器优于当前的大部分固定策略,LCCT的表现优于动态符号执行器,并且在部分程序上覆盖了最多的分支。